REVIEW 1 major objections 4 minor 37 references
Computing $H$-equations with 2-by-2 integral matrices
T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves that for 2-by-2 integral matrix groups one can decide whether a matrix satisfies a nontrivial equation over a finitely generated subgroup, compute all such equations when they exist, and that the analogous task is…
desk verdict A solid, useful algorithm paper for H-equations in PSL2(Z), with a fixable gap in the finite-index transfer proof and one under-verified example. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the ideal $I_H(g)=\ker\varphi_{H,g}$ in the free product $H*\langle x\rangle$, where $\varphi_{H,g}$ evaluates $x$ at $g$; it is a normal subgroup consisting exactly of the $H$-equations satisfied by $g$. The transfer mechanism is a short exact sequence $1\to F\to G\to L\to 1$ with $F$ finite-index and $L$ finite, from which the paper builds $I_H(g;F)=\{w(x): w(g)\in F\}=\varphi_{H,g}^{-1}(F)$. Since $L$ is finite and membership in $L$ is decidable, $I_H(g;F)$ has finite index in $H*\langle x\rangle$ and can be explicitly computed via the Schreier graph of the action of $H*\langle x\rangle$ on the cosets of $I_H(g;F)$. Applying this to $G=\mathrm{PSL}_2(\mathbb{Z})$ with free $F=\langle p,q\rangle$, each generator $w_i(x)$ of $I_H(g;F)$ evaluates to $v_i=w_i(g)\in F$; the effective coherence of free groups (via Stallings automata) produces a finite presentation of $V=\langle v_1,\ldots,v_p\rangle$, and appropriate substitution of the $w_i(x)$ into those relations yields a finite normal generating set for $I_H(g)$.
What would settle it
On the paper's first worked example, with $h_1=\begin{pmatrix}2&-1\\-1&1\end{pmatrix}$, $h_2=\begin{pmatrix}2&-5\\1&-2\end{pmatrix}$, and $g=\begin{pmatrix}5&3\\3&2\end{pmatrix}$ in $\mathrm{PSL}_2(\mathbb{Z})$, the algorithm concludes that $g$ is transcendental over $H=\langle h_1,h_2\rangle$; a single concrete $H$-equation $w(x)$ with $w(g)=I$ would falsify that conclusion and hence the claimed correctness of the algorithm.
Extended reading notes
Core claim
The central claim is that effective eq-coherence is the right algorithmic counterpart of algebraic dependence, and that it passes through finite-index extensions in both directions. Concretely, the paper proves Theorem 3.5: if $F \leqslant_{\mathrm{f.i.}} G$ is an effectively coherent finite-index subgroup of a finitely presented group $G$, then $G$ is effectively eq-coherent; the converse also holds. Applying this to $G=\mathrm{PSL}_2(\mathbb{Z})$, which has the free group $F=\langle p,q\rangle$ as a normal finite-index subgroup, yields Corollary 4.2: there is an algorithm that, given $h_1,\ldots,h_s$ and $g$, decides whether $g$ is algebraic over $H=\langle h_1,\ldots,h_s\rangle$, and if so outputs $w_1(x),\ldots,w_p(x)\in H*\langle x\rangle$ with $w_i(g)=1$ such that every $w(x)$ with $w(g)=1$ is a product of conjugates of the $w_i(x)$. The argument constructs the finite-index preimage $I_H(g;F)=\{w(x): w(g)\in F\}$, computes its generators from the Schreier graph of the quotient $G/F$, evaluates them at $g$ to get elements of $F$, and invokes the free-group subroutine to find the relations among those elements; substituting the original equations back gives generators for $I_H(g)$. The corresponding problem for $n\ge 4$ is unsolvable because those matrix groups contain $\mathrm{F}_2\times\mathrm{F}_2$ and fail coherence.
Load-bearing premise
The procedure rests on having a finite-index subgroup whose finitely generated subgroups have computable finite presentations, together with a way to rewrite elements of that subgroup in its given generators; for $\mathrm{PSL}_2(\mathbb{Z})$ this is the free group generated by two explicit matrices, and the method inherits both the power and the theoretical limitations of that free-group subroutine.
Editorial extensions
If this is right
- For every finitely generated subgroup $H$ of $\mathrm{PSL}_2(\mathbb{Z})$ and every $g$, the algorithm outputs either a certificate that $g$ is transcendental over $H$ or a finite family of $H$-equations that generate the entire ideal $I_H(g)$.
- The same finite-output description is available for $\mathrm{GL}_2(\mathbb{Z})$, $\mathrm{PGL}_2(\mathbb{Z})$, and $\mathrm{SL}_2(\mathbb{Z})$, because each contains a finite-index free subgroup and the transfer theorem applies.
- The equivalence between coherence and eq-coherence means the computed equations are not a separate data type: a finite presentation of $\langle H,g\rangle$ on the generators $h_1,\ldots,h_s,g$ already encodes generators for $I_H(g)$.
- For $n\ge 4$, the paper gives a specific obstruction: there are matrices $h_1,\ldots,h_s$ and $g$ with $g$ algebraic over $H$ but $I_H(g)$ not finitely generated, so any algorithm with finite output solving the problem is impossible for those groups.
- The transfer theorem applies to any finitely presented group with an effectively coherent finite-index subgroup, making the 2-by-2 matrix algorithm an instance of a general principle rather than a one-off computation.
Reading between the lines
- The same transfer recipe should work for any group known to contain a computable finite-index free subgroup with solvable membership, so virtually free groups beyond $\mathrm{PSL}_2(\mathbb{Z})$ are a natural place to look for further instances of the algorithm.
- For $n=3$, where the paper leaves the question open, a plausible next test is whether any finitely generated subgroup $H\le \mathrm{SL}_3(\mathbb{Z})$ and element $g$ yield an infinitely generated $I_H(g)$; the paper's methods do not yet reach this case.
- The brute-force rewriting step has no complexity bound; a practical extension would be to analyze how the lengths of the output equations grow as functions of the entries of the input matrices.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies equationally coherent groups and their effective algorithmic counterpart. The main theoretical result, Theorem 3.5, states that coherence and effective coherence transfer through finite-index subgroups. The proof of the effective direction reduces the problem to equations, using a finite-index subgroup I_H(g;F) of H * <x> with solvable membership problem together with the effective coherence of the finite-index subgroup F. The paper then applies this to the modular group PSL2(Z) and its relatives GL2(Z), PGL2(Z), SL2(Z), obtaining Corollary 4.2: an algorithm that, given h_1,...,h_s and g, decides whether g is algebraic over H = <h_1,...,h_s> and, if so, computes a finite generating set of the ideal I_H(g). Two detailed worked examples in Section 4 illustrate the algorithm. The paper also shows that for GL_n(Z), PGL_n(Z), SL_n(Z), and PSL_n(Z) with n >= 4, there are instances where I_H(g) is not finitely generated, so the corresponding computational task cannot be solved in general.
Significance. If correct, the paper provides a new and explicit instance of an effectively equationally coherent group beyond free groups, with a concrete algorithmic outcome for 2-by-2 integral matrices. The proof strategy is natural: it transfers effective eq-coherence through finite index via a finite quotient and a free kernel, importing the known effective coherence of free groups as a black box. The worked examples are detailed and appear to check out. The paper is clearly written, and the references to prior work are appropriate. The main theoretical contribution is the transfer theorem and its algorithmic formulation. The principal issue is a formal gap in the proof of the transfer theorem, discussed below, which is readily repairable without changing the substance of the results.
major comments (1)
- [Section 3, proof of Theorem 3.5(ii)] Proposition 3.3 is applied to the ambient group H * <x> to compute generators for I_H(g;F), but at that point H * <x> is only known to be finitely generated; no finite presentation of H (and hence of H * <x>) has been computed. Proposition 3.3 as stated requires a finite presentation of the ambient group. The generators-only part of the proof of Proposition 3.3 does not use the relators of the ambient group and works with any finite generating set together with a membership oracle for the finite-index subgroup. Please state and prove a membership-only version of Proposition 3.3 (or explicitly extract it from the existing proof) and invoke that version in Theorem 3.5(ii). The same comment applies to the constructions in Section 4, where Schreier graphs of I_H(g;F) in H * <x> are drawn and used to compute generators.
minor comments (4)
- [Section 4, Example 4.4] The sentence 'According to the algorithm from the proof of Proposition 3.3, this requires to draw a flower automaton...' refers to the Rosenmann–Ventura effective coherence algorithm for free groups, not to Proposition 3.3; please correct the reference.
- [Section 4, Corollary 4.2] The corollary is stated for GL2(Z), PGL2(Z), SL2(Z), and PSL2(Z), but the detailed materialization is only given for PSL2(Z). It would improve readability to briefly explain how the same argument applies to the other three groups, for example by pointing to explicit normal free subgroups and finite quotients from the cited reference.
- [Abstract and Corollary 4.5] The word 'unsolvable' may be misread as undecidability of the algebraicity decision problem. What is proved is that for n >= 4 there are inputs for which no finite generating set for I_H(g) exists, so the problem of computing such a generating set is impossible in those cases; please phrase accordingly.
- [Section 3, proof of Theorem 3.5(ii)] The rewriting of v_i = w_i(g) as words on {f_1,...,f_r} is justified only by brute-force search; this is correct, but the presentation would benefit from a remark that termination follows from the solvability of the membership problem in F, which is available because F has finite index in G.
Circularity Check
No significant circularity: the derivation transfers effective coherence from an explicit free subgroup of PSL2(Z) to PSL2(Z) itself, with no fitted data or conclusion-as-input.
full rationale
No circularity found. The main derivation chain is: free groups are effectively coherent (folklore, with proof sketch in Example 2.6 and published algorithms); Theorem 3.5 transfers effective coherence from a finite-index subgroup F to the ambient group G, assuming membership in F and an algorithm that computes presentations of finitely generated subgroups of F; and in the application to PSL2(Z), the subgroup F is explicitly constructed as the free group on p=[a,b] and q=[b^2,a] and shown to be the kernel of the abelianization map to C2 x C3. The algorithm then computes generators for IH(g;F) as a finite-index subgroup of H*<x> using Schreier graph methods, evaluates them at g to obtain v_i in F, computes a presentation for V=<v_i> using effective coherence of the free group F, and substitutes the w_i(x) into that presentation to obtain generators for IH(g). The proof that the resulting normal closure equals IH(g) is a direct set-theoretic argument that does not assume the conclusion. No parameter is fitted to the target datum, and no prediction is renamed from an input. The paper does invoke prior work by the authors ([12], [33]) as an algorithm for effective coherence of free groups, but this is an independent, parameter-free theorem about free groups, not about PSL2(Z), and it does not contain the target result; under the stated rules this is real evidence, not circularity. The one notable issue is a formal proof gap: in Theorem 3.5(ii), Proposition 3.3 is applied to H*<x> as if the ambient group were finitely presented, although no finite presentation for H is available at that stage. This is a correctness/completeness concern about the written proof, not a circularity: the generators-only part of Proposition 3.3 can be formulated with a membership oracle and without needing relators of the ambient group. Since every nontrivial mathematical step is either proved from established independent facts or explicitly assumed as a hypothesis (effective coherence of F), the paper is not circular.
Assumptions & free parameters
assumptions (5)
- standard math Nielsen-Schreier and Kurosh subgroup theorems: subgroups of free groups are free, and subgroups of free products decompose as free products of free groups and conjugates of vertex subgroups.
- standard math Todd-Coxeter procedure computes Schreier graphs and membership for finite-index subgroups of finitely presented groups.
- standard math Reidemeister-Schreier process computes presentations of finite-index subgroups.
- domain assumption Free groups are effectively coherent via Stallings foldings, as established by Rosenmann and Ventura and by Delgado and Ventura.
- domain assumption A finite-index subgroup of a finitely generated group can have its Schreier graph and a finite generating set computed from a membership oracle alone, even without a finite presentation of the ambient group.
Cite this review
Pith. "Pith review of Computing $H$-equations with 2-by-2 integral matrices." pith.science (2026). https://pith.science/paper/V3AS2JE2
@misc{pith2026250605272,
author = {Pith},
title = {Pith review of: Computing $H$-equations with 2-by-2 integral matrices},
year = {2026},
howpublished = {\url{https://pith.science/paper/V3AS2JE2}},
note = {Machine review of arXiv:2506.05272}
}
abstract
We study the transference through finite index extensions of the notion of equational coherence, as well as its effective counterpart. We deduce an explicit algorithm for solving the following algorithmic problem about size two integral invertible matrices: ''given $h_1,\ldots, h_r; g\in \operatorname{PSL}_2(\mathbb{Z})$, decide whether $g$ is algebraic over the subgroup $H=\langle h_1,\ldots ,h_r\rangle \leqslant \operatorname{PSL}_2(\mathbb{Z})$ (i.e., whether there exist a non-trivial $H$-equation $w(x)\in H*\langle x\rangle$ such that $w(g)=1$) and, in the affirmative case, compute finitely many such $H$-equations $w_1(x),\ldots ,w_s(x)\in H*\langle x\rangle$ further satisfying that any $w(x)\in H*\langle x\rangle$ with $w(g)=1$ is a product of conjugates of $w_1(x),\ldots ,w_s(x)$''. The same problem for square matrices of size 4 and bigger is unsolvable.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
Free groups and Stallings’ foldings
D. Ascari, “Free groups and Stallings’ foldings”, PhD Thesis, Oxford University Research Archive
-
[2]
Ideals of equations for elements in a free group and Stallings folding
D. Ascari, “Ideals of equations for elements in a free group and Stallings folding”, Proceedings of the Edinburgh Mathematical Society, published online (2024), 1–42. doi:10.1017/S0013091524000439
-
[3]
Algebraic geometry over groups. I. Algebraic sets and ideal theory
G. Baumslag, A. Myasnikov, V. Remeslennikov, “Algebraic geometry over groups. I. Algebraic sets and ideal theory”, J. Algebra 219(1) (1999), 16–79
work page 1999
-
[4]
O.Bogopolski, “Introduction to group theory”, European Mathematical Society Publishing House, 2008
work page 2008
-
[5]
Orbit decidability and the conjugacy problem for some extensions of groups
O. Bogopolski, A. Martino, E. Ventura, “Orbit decidability and the conjugacy problem for some extensions of groups”, Transactions of the American Mathematical Society 362 (2010), 2003–2036
work page 2010
-
[6]
Solving one-variable equations in free groups
D. Bormotov, R. Gilman, A. Myasnikov, “Solving one-variable equations in free groups”, J. Group Theory 12 (2009), 317–330
work page 2009
-
[7]
On the finite presentation of subdirect products and the nature of residually free groups
M.R. Bridson, J. Howie, C.F. Miller III, H. Short, “On the finite presentation of subdirect products and the nature of residually free groups”, American Journal of Mathematics 135(4) (2013), 891–933
work page 2013
-
[8]
On the dificulty of presenting finitely presentable groups
M.R. Bridson, H. Wilton, “On the dificulty of presenting finitely presentable groups”, Groups Geom. Dyn. 5(2) (2011), 301–325
work page 2011
Show all 37 references
-
[9]
Effective coherence of groups discriminated by a locally quasi-convex hyperbolic group
I. Bumagin, J. Macdonald, “Effective coherence of groups discriminated by a locally quasi-convex hyperbolic group”, Groups Geom. Dyn. 10 (2016), 545–582
2016
-
[10]
The word, power and order problems in finitely presented groups
D.J. Collins, “The word, power and order problems in finitely presented groups”, in “Word Problems”, ed. by Boone, Cannonito, and Lyndon, pages 401–420. North-Holland, Amsterdam, 1973
1973
-
[11]
A fast algorithm for Stallings foldings over virtually free groups
S. Cookson, N. Touikan, “A fast algorithm for Stallings foldings over virtually free groups”,International Journal of Algebra and Computation 34(8) (2024), 1225–1252
2024
-
[12]
Stallings graphs
J. Delgado, E. Ventura, “Stallings graphs”, a chapter in the GAGTA BOOK 3 “Languages and Automata” edited by B. Steinberg, Berlin, Boston: De Gruyter, 2024. https://doi.org/10.1515/9783110984323
2024 doi
-
[13]
Groups acting on graphs
W. Dicks, M.J. Dunwoody, “Groups acting on graphs”, Cambridge studies in advanced mathematics 17, CUP, Cambridge (1989)
1989
-
[14]
Graph groups, coherence, and three-manifolds
C. Droms, “Graph groups, coherence, and three-manifolds”, Journal of Algebra 106 (1987), 484–489
1987
-
[15]
Mapping tori of free group automorphisms are coherent
M. Feighn, M. Handel, “Mapping tori of free group automorphisms are coherent”, Annals of Mathematics 149(3), 1999, 1061–1077
1999
-
[16]
Enumerating limit groups
D. Groves, H. Wilton, “Enumerating limit groups”, Groups, Geometry and Dynamics 3(3) (2009), 389–399
2009
-
[17]
On some groups which cannot be finitely presented
F.J. Grunewald, “On some groups which cannot be finitely presented”, J. London Math. Soc. 17(2) (1978), 427–436
1978
-
[18]
Computing angles in hyperbolic groups
Z. Grunschlag, “Computing angles in hyperbolic groups”, in R.H. Gilman (ed.), “Groups, languages and geom- etry”, Mathematical Society, Providence, R.I., 1999, 59–88
1999
-
[19]
On subgroups of R. Thompson group and other diagram groups
V.S. Guba, M.V. Sapir, “On subgroups of R. Thompson group and other diagram groups”, Mat. Sb. 190(8) (1999), 3–60. Translated at Sb. Math. 190(7-8) (1999), 1077–1130
1999
-
[20]
On the coherence of one-relator groups and their group algebras
A. Jaikin-Zapirain, M. Linton, “On the coherence of one-relator groups and their group algebras”, Annals of Mathematics 201(3) (2025), 909–959
2025
-
[21]
Presentations of groups
D.L. Johnson, “Presentations of groups”, London Math. Soc. Student Texts 15, Cambridge University Press, 1990
1990
-
[22]
Foldings, graphs of groups and the membership problem
I. Kapovich, R. Weidmann, A. Miasnikov, “Foldings, graphs of groups and the membership problem”, Internat. J. Algebra Comput. 15(1) (2005), 95–128
2005
-
[23]
Subgroup membership in GL(2,Z)
M. Lohrey, “Subgroup membership in GL(2,Z)”, in Markus Bl¨ aser and Benjamin Monmege, editors,38th Inter- national Symposium on Theoretical Aspects of Computer Science (STACS 2021) vol. 187 of Leibniz Interna- tional Proceedings in Informatics (LIPIcs), pages 51:1–51:17, Dagst...
2021
-
[24]
Equations in a free group
G. Makanin, “Equations in a free group”, Izv. Akad. Nauk SSSR Ser. Mat. 46(6) (1982), 1199–1273, 1344
1982
-
[25]
The occurrence problem for direct products of groups
K.A. Mihailova, “The occurrence problem for direct products of groups”, Dokl. Acad. Nauk SSRR 119 (1958), 1103–1105
1958
-
[26]
Combinatorial Group Theory
C.F. Miller III, “Combinatorial Group Theory”, handwritten notes (2002), available at https://www.macs.hw.ac.uk/∼lc45/Teaching/kggt/miller.pdf
2002
-
[27]
On systems of equations in a free group
A.A. Razborov, “On systems of equations in a free group”, Izv. Akad. Nauk SSSR Ser. Mat. 48(4) (1984), 779–832; Math. USSR-Izv. 25(1) (1985), 115–162
1984
-
[28]
On systems of equations in free groups
A. Razborov, “On systems of equations in free groups”, London Math. Soc. Lecture Note Ser. (Cambridge Univ. Press, Cambridge) 204 (1995), 269–283
1995
-
[29]
Coherent groups of units of integral group rings and direct products of free groups
A. del R ´ ıo, P. Zalesskii, “Coherent groups of units of integral group rings and direct products of free groups”, Math. Proc. Cambridge Philos. Soc. 162(2) (2017), 191–209
2017
-
[30]
Subgroups of small cancellation groups
E. Rips, “Subgroups of small cancellation groups”, Bull. London Math. Soc. 14(1) (1982), 45–47
1982
-
[31]
On rank, root and equations in free groups
A. Rosenmann, “On rank, root and equations in free groups”, Internat. J. Algebra Comput. 11(3) (2001), 375–390
2001
-
[32]
Dependence and algebraicity over subgroups of free groups
A. Rosenmann, E. Ventura, “Dependence and algebraicity over subgroups of free groups”, preprint available at arXiv:2107.03154v1, July 2021
2021 arXiv
-
[33]
Dependence over subgroups of free groups
A. Rosenmann, E. Ventura, “Dependence over subgroups of free groups”, Intenational Journal of Algebra and Computation 34(4), (2024), 439–470
2024
-
[34]
Coxeter groups, 2-completion, perimeter reduction and subgroup separability
P.E. Schupp, “Coxeter groups, 2-completion, perimeter reduction and subgroup separability”, Geometriae Ded- icata 96 (2003), 179–198
2003
-
[35]
Finitely generated 3-manifold groups are finitely presented
P. Scott, “Finitely generated 3-manifold groups are finitely presented”, J. London Math. Soc. 6, (1973), 437–440
1973
-
[36]
Problem section. In Proceedings of the Second International Conference on the Theory of Groups (Canberra, 1973)
J.P. Serre, “Problem section. In Proceedings of the Second International Conference on the Theory of Groups (Canberra, 1973)”, Lecture Notes in Mathematics 372, (1974), Springer-Verlag
1974
-
[37]
An invitation to coherent groups. What’s next?-the mathematical legacy of William P. Thurston
D. Wise, “An invitation to coherent groups. What’s next?-the mathematical legacy of William P. Thurston”, 326–414, Ann. of Math. Stud., 205, Princeton Univ. Press, Princeton, NJ, 2020. Departament de Matem`atiques, Universitat Polit`ecnica de Catalunya, CATALONIA. Email addres...
2020
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.