The Diophantine problem in Thompson’s group 𝐹

Elliott, Luna; Levine, Alex

doi:10.1090/mcom/4113

The Diophantine problem in Thompson’s group $F$
HTML articles powered by AMS MathViewer

by Luna Elliott and Alex Levine;

Math. Comp.

DOI: https://doi.org/10.1090/mcom/4113

Published electronically: June 9, 2025

PDF | Request permission

Abstract:

We show that the Diophantine problem in Thompson’s group $F$ is undecidable. Our proof uses the facts that $F$ has finite commutator width and rank $2$ abelianisation, then uses similar arguments used by Büchi and Senger [Z. Math. Logik Grundlag. Math. 34 (1988), pp. 337–342] and Ciobanu and Garreta [Int. Math. Res. Not. IMRN 5 (2024), pp. 4119–4159] to show the Diophantine problem in free groups and monoids with abelianisation constraints is undecidable.

References

Valery Bardakov and Vladimir Tolstykh, Interpreting the arithmetic in Thompson’s group $F$, J. Pure Appl. Algebra 211 (2007), no. 3, 633–637. MR 2344220, DOI 10.1016/j.jpaa.2007.02.011
James Belk and Francesco Matucci, Conjugacy and dynamics in Thompson’s groups, Geom. Dedicata 169 (2014), 239–261. MR 3175247, DOI 10.1007/s10711-013-9853-2
Matthew G. Brin, Coherence of associativity in categories with multiplication, J. Pure Appl. Algebra 198 (2005), no. 1-3, 57–65. MR 2132873, DOI 10.1016/j.jpaa.2004.10.008
Matthew G. Brin and Craig C. Squier, Presentations, conjugacy, roots, and centralizers in groups of piecewise linear homeomorphisms of the real line, Comm. Algebra 29 (2001), no. 10, 4557–4596. MR 1855112, DOI 10.1081/AGB-100106774
J. Richard Büchi and Steven Senger, Definability in the existential theory of concatenation and undecidable extensions of this theory, Z. Math. Logik Grundlag. Math. 34 (1988), no. 4, 337–342. MR 950368, DOI 10.1002/malq.19880340410
J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson’s groups, Enseign. Math. (2) 42 (1996), no. 3-4, 215–256. MR 1426438
Laura Ciobanu, Alex Evetts, and Alex Levine, Effective equation solving, constraints, and growth in virtually abelian groups, SIAM J. Appl. Algebra Geom. 9 (2025), no. 1, 235–260. MR 4876546, DOI 10.1137/23M1604679
Laura Ciobanu and Albert Garreta, Group equations with abelian predicates, Int. Math. Res. Not. IMRN 5 (2024), 4119–4159. MR 4714338, DOI 10.1093/imrn/rnad179
Laura Ciobanu, Derek Holt, and Sarah Rees, Equations in groups that are virtually direct products, J. Algebra 545 (2020), 88–99. MR 4044690, DOI 10.1016/j.jalgebra.2018.10.044
François Dahmani and Vincent Guirardel, Foliations for solving equations in groups: free, virtually free, and hyperbolic groups, J. Topol. 3 (2010), no. 2, 343–404. MR 2651364, DOI 10.1112/jtopol/jtq010
Patrick Dehornoy, The structure group for the associativity identity, J. Pure Appl. Algebra 111 (1996), no. 1-3, 59–82. MR 1394345, DOI 10.1016/0022-4049(95)00119-0
Patrick Dehornoy, Geometric presentations for Thompson’s groups, J. Pure Appl. Algebra 203 (2005), no. 1-3, 1–44. MR 2176650, DOI 10.1016/j.jpaa.2005.02.012
Volker Diekert and Markus Lohrey, Existential and positive theories of equations in graph products, STACS 2002, Lecture Notes in Comput. Sci., vol. 2285, Springer, Berlin, 2002, pp. 501–512. MR 2050863, DOI 10.1007/3-540-45841-7_{4}1
Volker Diekert and Anca Muscholl, Solvability of equations in free partially commutative groups is decidable, Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 2076, Springer, Berlin, 2001, pp. 543–554. MR 2066532, DOI 10.1007/3-540-48224-5_{4}5
Ruiwen Dong, Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, Philadelphia, PA, 2025, pp. 1892–1908. MR 4863474, DOI 10.1137/1.9781611978322.59
Moon Duchin, Hao Liang, and Michael Shapiro, Equations in nilpotent groups, Proc. Amer. Math. Soc. 143 (2015), no. 11, 4723–4731. MR 3391031, DOI 10.1090/proc/12630
Światosław R. Gal and Jakub Gismatullin, Uniform simplicity of groups with proximal action, Trans. Amer. Math. Soc. Ser. B 4 (2017), 110–130. With an appendix by Nir Lazarovich. MR 3693109, DOI 10.1090/btran/18
Albert Garreta, Leire Legarreta, Alexei Miasnikov, and Denis Ovchinnikov, Metabelian groups: full-rank presentations, randomness and diophantine problems, J. Group Theory 24 (2021), no. 3, 453–466. MR 4250503, DOI 10.1515/jgth-2020-0091
Albert Garreta, Alexei Miasnikov, and Denis Ovchinnikov, Random nilpotent groups, polycyclic presentations, and Diophantine problems, Groups Complex. Cryptol. 9 (2017), no. 2, 99–115. MR 3717096, DOI 10.1515/gcc-2017-0007
Ross Geoghegan and Marco Varisco, On Thompson’s group $T$ and algebraic $K$-theory, Geometric and cohomological group theory, London Math. Soc. Lecture Note Ser., vol. 444, Cambridge Univ. Press, Cambridge, 2018, pp. 34–45. MR 3822287
Victor Guba and Mark Sapir, Diagram groups, Mem. Amer. Math. Soc. 130 (1997), no. 620, viii+117. MR 1396957, DOI 10.1090/memo/0620
Olga Kharlampovich, Laura Lopez, and Alexei Miasnikov, Diophantine problem in some metabelian groups, arXiv e-prints (2023).
Clément Lasserre, R. J. Thompson’s groups $F$ and $T$ are bi-interpretable with the ring of the integers, J. Symb. Log. 79 (2014), no. 3, 693–711. MR 3248780, DOI 10.1017/jsl.2014.29
Igor Lysenok, Alexei Miasnikov, and Alexander Ushakov, Quadratic equations in the Grigorchuk group, Groups Geom. Dyn. 10 (2016), no. 1, 201–239. MR 3460336, DOI 10.4171/GGD/348
Igor Lysenok and Alexander Ushakov, Orientable quadratic equations in free metabelian groups, J. Algebra 581 (2021), 303–326. MR 4256899, DOI 10.1016/j.jalgebra.2021.04.013
G. S. Makanin, Systems of equations in free groups, Sibirsk. Mat. Ž. 13 (1972), 587–595 (Russian). MR 318314
G. S. Makanin, The problem of the solvability of equations in a free semigroup, Mat. Sb. (N.S.) 103(145) (1977), no. 2, 147–236, 319 (Russian). MR 470107
G. S. Makanin, Equations in a free group, Izv. Akad. Nauk SSSR Ser. Mat. 46 (1982), no. 6, 1199–1273, 1344 (Russian). MR 682490
Ju. V. Matijasevič, The Diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR 191 (1970), 279–282 (Russian). MR 258744
Ju. V. Matijasevič, Diophantine sets, Uspehi Mat. Nauk 27 (1972), no. 5(167), 185–222 (Russian). MR 441711
Francesco Matucci, Algorithms and classification in groups of piecewise-linear homeomorphisms, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)–Cornell University. MR 2712336
Ralph McKenzie and Richard J. Thompson, An elementary construction of unsolvable word problems in group theory, Word problems: decision problems and the Burnside problem in group theory (Conf., Univ. California, Irvine, Calif., 1969; dedicated to Hanna Neumann), Stud. Logic Found. Math., Vol. 71, North-Holland, Amsterdam-London, 1973, pp. 457–478. MR 396769, DOI 10.1016/0003-4916(72)90140-6
E. Rips and Z. Sela, Canonical representatives and equations in hyperbolic groups, Invent. Math. 120 (1995), no. 3, 489–512. MR 1334482, DOI 10.1007/BF01241140
David Matthew Robertson, Conjugacy and centralisers in Thompson’s group T, Ph.D. Thesis, 2019.
V. A. Roman′kov, Equations in free metabelian groups, Sibirsk. Mat. Zh. 20 (1979), no. 3, 671–673, 694 (Russian). MR 537377
V. A. Roman′kov, Universal theory of nilpotent groups, Mat. Zametki 25 (1979), no. 4, 487–495, 635 (Russian). MR 534291
Richard Thompson, Unpublished but widely circulated handwritten notes, 1965.
Alexander Ushakov and Chloe Weiers, Quadratic equations in the lamplighter group, J. Symbolic Comput. 129 (2025), Paper No. 102417, 18. MR 4840449, DOI 10.1016/j.jsc.2024.102417

AMS Website Down

Mathematics of Computation

The Diophantine problem in Thompson’s group $F$
HTML articles powered by AMS MathViewer

Abstract: