pith. sign in

arxiv: 1906.10423 · v1 · pith:5DMANROAnew · submitted 2019-06-25 · 🧮 math.GR

Algorithms for arithmetic groups with the congruence subgroup property

A. S. Detinko , D. L. Flannery , A. Hulpke This is my paper

Pith reviewed 2026-05-25 16:06 UTC · model grok-4.3

classification 🧮 math.GR
keywords arithmetic groupscongruence subgroup propertycomputational group theorySL(n,Q)principal congruence subgroupGAP implementationmembership testingorbit-stabilizer problem
0
0 comments X

The pith

Algorithms reduce computations with arithmetic groups H in SL(n,Q) to finite calculations by constructing principal congruence subgroups.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops practical techniques for computing with arithmetic groups H in SL(n,Q) for n greater than 2. The approach depends on constructing a principal congruence subgroup within H. This enables solving problems like testing membership in H, analyzing its subnormal structure, and addressing the orbit-stabilizer problem. These reductions rely on effective computations with subgroups of GL(n, Z_m). All the algorithms are implemented in GAP.

Core claim

We develop practical techniques to compute with arithmetic groups H≤SL(n,Q) for n>2. Our approach relies on constructing a principal congruence subgroup in H. Problems solved include testing membership in H, analyzing the subnormal structure of H, and the orbit-stabilizer problem for H. Effective computation with subgroups of GL(n,Z_m) is vital to this work. All algorithms have been implemented in GAP.

What carries the argument

The principal congruence subgroup in H, which allows reduction of the computational problems to calculations in finite groups.

If this is right

  • Membership testing in H becomes effective.
  • The subnormal structure of H can be analyzed computationally.
  • The orbit-stabilizer problem for H can be solved.
  • Computations with subgroups of GL(n, Z_m) support the overall method.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The methods may apply to other matrix groups satisfying the congruence subgroup property.
  • Implementation in GAP allows researchers to perform these computations without developing new code.
  • Similar congruence-based reductions could be explored for related problems in infinite group theory.

Load-bearing premise

The arithmetic groups have the congruence subgroup property, ensuring a principal congruence subgroup exists that can be constructed.

What would settle it

An arithmetic group in SL(n,Q) for n>2 with the congruence subgroup property for which no algorithm constructs a principal congruence subgroup would show the method does not work.

read the original abstract

We develop practical techniques to compute with arithmetic groups $H\leq \mathrm{SL}(n,\mathbb{Q})$ for $n>2$. Our approach relies on constructing a principal congruence subgroup in $H$. Problems solved include testing membership in $H$, analyzing the subnormal structure of $H$, and the orbit-stabilizer problem for $H$. Effective computation with subgroups of $\mathrm{GL}(n,\mathbb{Z}_m)$ is vital to this work. All algorithms have been implemented in GAP.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper develops practical algorithms for computing with arithmetic groups H ≤ SL(n, Q) (n > 2) possessing the congruence subgroup property. The central technique is the explicit construction of a principal congruence subgroup of finite index in H, which reduces membership testing in H, computation of the subnormal series of H, and the orbit-stabilizer problem for H to finite-group calculations inside subgroups of GL(n, Z_m). All algorithms are implemented in GAP.

Significance. If the reductions are non-circular and the implementations correct, the work supplies the first systematic practical toolkit for these computational problems in higher-rank arithmetic groups, extending the reach of computational group theory beyond SL(2, Z) and similar low-dimensional cases. The emphasis on effective finite-group computations in GL(n, Z_m) is a useful byproduct.

major comments (2)
  1. [Section describing construction of principal congruence subgroup] The description of the construction of the principal congruence subgroup (the step that finds a level m such that the kernel of reduction mod m lies inside H) must be shown to be non-circular. It is not sufficient to invoke the CSP for existence; the explicit procedure must be spelled out using only the given matrix generators of H and arithmetic operations in SL(n, Q) or GL(n, Z_m), without presupposing membership or orbit computations in H itself.
  2. [Membership testing algorithm] The reduction of the membership problem for H to a finite-group calculation inside the principal congruence subgroup must be verified to terminate and to be correct for arbitrary input matrices in SL(n, Q). The paper should supply a complexity bound or at least a termination argument that does not rely on the very membership oracle being constructed.
minor comments (2)
  1. [Abstract and §1] The abstract and introduction should cite the precise statement of the congruence subgroup property used and the reference establishing it for the groups under consideration.
  2. [Notation and definitions] Clarify the precise definition of 'principal congruence subgroup' employed when H is not the full SL(n, Z); the standard kernel of reduction mod m may need adjustment.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major comment below and will revise the manuscript to incorporate the requested clarifications on non-circularity and termination.

read point-by-point responses

  1. Referee: [Section describing construction of principal congruence subgroup] The description of the construction of the principal congruence subgroup (the step that finds a level m such that the kernel of reduction mod m lies inside H) must be shown to be non-circular. It is not sufficient to invoke the CSP for existence; the explicit procedure must be spelled out using only the given matrix generators of H and arithmetic operations in SL(n, Q) or GL(n, Z_m), without presupposing membership or orbit computations in H itself.

    Authors: We agree the construction must be presented explicitly and non-circularly. The revised manuscript will include a dedicated subsection spelling out the procedure: given generators of H, compute candidate levels m by taking the lcm of all denominators appearing in the entries of the generators and their inverses (via arithmetic in SL(n,Q)), then verify the kernel condition by direct matrix reduction and multiplication in GL(n,Z_m) to confirm the congruence subgroup lies in H. This uses only the input generators and standard arithmetic operations, with no appeal to membership testing or orbit computations inside H. revision: yes

  2. Referee: [Membership testing algorithm] The reduction of the membership problem for H to a finite-group calculation inside the principal congruence subgroup must be verified to terminate and to be correct for arbitrary input matrices in SL(n, Q). The paper should supply a complexity bound or at least a termination argument that does not rely on the very membership oracle being constructed.

    Authors: We will add an explicit termination argument in the revised version. For an arbitrary input matrix g in SL(n,Q), first reduce g modulo the precomputed level m and test membership in the finite image of H inside GL(n,Z_m) (a terminating finite-group computation). If it lies in the image, solve for the correcting element in the principal congruence subgroup by enumerating coset representatives, whose number is bounded by the finite index [H : principal congruence subgroup], which is itself computed via the finite-group calculation in GL(n,Z_m). This bound ensures termination independent of any membership oracle for H, and we will include a complexity estimate in terms of the index and bit-size of m. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is self-contained via CSP and explicit construction

full rationale

The paper presents algorithms that construct a principal congruence subgroup of H using the congruence subgroup property (CSP) and then reduce membership testing, subnormal structure analysis, and orbit-stabilizer problems to finite-group computations inside GL(n, Z_m). No equations, fitted parameters, or self-citations are shown that reduce any claimed result to its own inputs by construction. The approach is described as using only the matrix generators of H together with arithmetic in SL(n, Q) and GL(n, Z_m), without invoking the target problems to build the subgroup. This satisfies the criteria for an independent, non-circular derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that the groups possess the congruence subgroup property and that principal congruence subgroups can be effectively constructed and used to reduce infinite-group problems to finite ones; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • domain assumption Arithmetic groups H ≤ SL(n, Q) for n > 2 that satisfy the congruence subgroup property admit an effectively constructible principal congruence subgroup that reduces membership and orbit problems to computations in GL(n, Z_m).
    This premise is stated in the title and abstract as the foundation for all listed algorithms.

pith-pipeline@v0.9.0 · 5610 in / 1323 out tokens · 52043 ms · 2026-05-25T16:06:01.114896+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    B¨ a¨ arnhielm, D

    H. B¨ a¨ arnhielm, D. F. Holt, C. R. Leedham-Green, and E.A. O’Brien, A practical model for computation with matrix groups, J. Symbolic Comput. 68 (2015), 27–60

    work page 2015

  2. [2]

    Babai, R

    L. Babai, R. Beals, and D. N. Rockmore, Deciding finiteness of matrix groups in deterministic polyn omial time, Proc. of International Symposium on Symbolic and Algebraic Compu tation ISSAC ’93 (ACM Press), 1993, pp. 117–126. ALGORITHMS FOR ARITHMETIC GROUPS 19

    work page 1993

  3. [3]

    H. Bass, M. Lazard, and J-P . Serre, Sous-groupes d’indice fini dans SL(n, Z), Bull. Amer. Math. Soc. 70 (1964), 385–392

    work page 1964

  4. [4]

    H. Bass, J. Milnor, and J.-P . Serre, Solution of the congruence subgroup problem for SLn (n ≥ 3) and Sp2n (n ≥ 2), Inst. Hautes ´Etudes Sci. Publ. Math. (1967), no. 33, 59–137

    work page 1967

  5. [5]

    Brenner, The linear homogeneous group, III , Ann

    J. Brenner, The linear homogeneous group, III , Ann. of Math. (2) 71 (1960), no. 2, 210–223

    work page 1960

  6. [6]

    A. S. Detinko, B. Eick, and D. L. Flannery, Computing with matrix groups over infinite fields , London Math. Soc. Lecture Note Ser. 387, 256–270, 2011

    work page 2011

  7. [7]

    A. S. Detinko, D. L. Flannery, and W. de Graaf, Integrality and arithmeticity of solvable linear groups , J. Symbolic Comput. 68 (2015), part 1, 138–145

    work page 2015

  8. [8]

    A. S. Detinko, D. L. Flannery, and E. A. O’Brien, Algorithms for the Tits alternative and related problems , J. Algebra 344 (2011), 397–406

    work page 2011

  9. [9]

    A. S. Detinko, D. L. Flannery, and E. A. O’Brien, Recognizing finite matrix groups over infinite fields , J. Symbolic Comput. 50 (2013), 100–109

    work page 2013

  10. [10]

    A. S. Detinko, D. L. Flannery, and E. A. O’Brien, Algorithms for linear groups of finite rank , J. Algebra 393 (2013), 187–196

    work page 2013

  11. [11]

    A. S. Detinko, D. L. Flannery, and A. Hulpke, Algorithms for arithmetic groups with the congruence subgroup property, J. Algebra 421 (2015), 234–259

    work page 2015

  12. [12]

    A. S. Detinko, D. L. Flannery, and A. Hulpke, Zariski density and computing in arithmetic groups , Math. Comp. 87 (2018), 967–986

    work page 2018

  13. [13]

    A. S. Detinko, D. L. Flannery, and A. Hulpke, Algorithms for experimenting with Zariski dense subgroups , Exp. Math., https://doi.org/10.1080/10586458.2018.1466217

    work page doi:10.1080/10586458.2018.1466217 2018

  14. [14]

    J. D. Dixon, The orbit-stabilizer problem for linear groups , Canad. J. Math. 37 (1985), no. 2, 238–259

    work page 1985

  15. [15]

    Eick and G

    B. Eick and G. Ostheimer, On the orbit-stabilizer problem for integral matrix actions of polycyclic groups, Math. Comp. 72 (2003), no. 243, 1511–1529

    work page 2003

  16. [16]

    The GAP Group, GAP – Groups, Algorithms, and Programming , http://www.gap-system.org

    work page

  17. [17]

    Grunewald and D

    F. Grunewald and D. Segal, Some general algorithms. I. Arithmetic groups , Ann. of Math. (2) 112 (1980), no. 3, 531– 583

    work page 1980

  18. [18]

    Grunewald and D

    F. Grunewald and D. Segal, Decision problems concerning S-arithmetic groups, J. Symbolic Logic 50 (1985), no. 3, 743–772

    work page 1985

  19. [19]

    A. J. Hahn and O. T. O’Meara, The classical groups and K-theory, Grundlehren der Mathematischen Wissenschaften, vol. 291, Springer-V erlag, Berlin, 1989

    work page 1989

  20. [20]

    Hulpke, Computing conjugacy classes of elements in matrix groups , J

    A. Hulpke, Computing conjugacy classes of elements in matrix groups , J. Algebra 387 (2013), 268–286

    work page 2013

  21. [21]

    Humphreys, Arithmetic groups, Lecture Notes in Mathematics, vol

    J. Humphreys, Arithmetic groups, Lecture Notes in Mathematics, vol. 789, Springer, Berlin, 1980

    work page 1980

  22. [22]

    D. D. Long and A. W. Reid, Small subgroups of SL(3, Z), Exp. Math. 20 (2011), no. 4, 412–425

    work page 2011

  23. [23]

    Lubotzky, Dimension function for discrete groups, London Math

    A. Lubotzky, Dimension function for discrete groups, London Math. Soc. Lecture Note Ser. 121, 254–262, 1986

    work page 1986

  24. [24]

    Lubotzky, One for almost all: generation of SL(n, p) by subsets of SL(n, Z), Contemp

    A. Lubotzky, One for almost all: generation of SL(n, p) by subsets of SL(n, Z), Contemp. Math. 243, 125–128, 1999

    work page 1999

  25. [25]

    Lubotzky and D

    A. Lubotzky and D. Segal, Subgroup growth, Birkh¨ auser, Basel, 2003

    work page 2003

  26. [26]

    Meiri, Generating pairs for finite index subgroups of SL(n, Z), J

    C. Meiri, Generating pairs for finite index subgroups of SL(n, Z), J. Algebra 470 (2017), 420–424

    work page 2017

  27. [27]

    J. L. Mennicke, Finite factor groups of the unimodular group , Ann. of Math. (2) 81 (1965), 31–37

    work page 1965

  28. [28]

    C. F. Miller III, personal communication

    work page

  29. [29]

    Milnor, Introduction to algebraic K-theory, Princeton Univ

    J. Milnor, Introduction to algebraic K-theory, Princeton Univ. Press, Princeton, NJ, 1971, Ann. of Math. S tud., no. 72

    work page 1971

  30. [30]

    Neunh¨ offer and ´A

    M. Neunh¨ offer and ´A. Seress, A data structure for a uniform approach to computations with finite groups, in ISSAC 2006, pp. 254–261. ACM, New Y ork, 2006

    work page 2006

  31. [31]

    Newman, Integral matrices, Academic Press, New Y ork, 1972, Pure and Applied Mathemati cs, V ol

    M. Newman, Integral matrices, Academic Press, New Y ork, 1972, Pure and Applied Mathemati cs, V ol. 45

    work page 1972

  32. [32]

    Sarnak, Notes on thin matrix groups , in: Thin groups and superstrong approximation, Math

    P . Sarnak, Notes on thin matrix groups , in: Thin groups and superstrong approximation, Math. Sci. Res. Inst. Publ. 61, pp. 343–362. Cambridge Univ. Press, Cambridge, 2014

    work page 2014

  33. [33]

    Sharma and T

    R. Sharma and T. N. V enkataramana, Generations for arithmetic groups, Geom. Dedicata 114 (2005), 103–146

    work page 2005

  34. [34]

    D. A. Suprunenko, Matrix groups, Transl. Math. Monogr., vol. 45, American Mathematical Soc iety, Providence, RI, 1976

    work page 1976

  35. [35]

    Sury, The congruence subgroup problem, J

    B. Sury, The congruence subgroup problem, J. Indian Inst. Sci. (4) 87 (2007), 457–465

    work page 2007

  36. [36]

    Sury and T

    B. Sury and T. N. V enkataramana, Generators for all principal congruence subgroups of SL(n, Z) with n ≥ 3, Proc. Amer. Math. Soc. 122 (1994), no. 2, 355–358

    work page 1994

  37. [37]

    J. S. Wilson, The normal and subnormal structure of general linear groups , Proc. Cambridge Philos. Soc. 71 (1972), 163–177

    work page 1972