pith. sign in

arxiv: 2602.22123 · v2 · submitted 2026-02-25 · 🧮 math.GR

Quadratic Equations in Graph Products of Groups and the Exponent of Periodicity

Volker Diekert , Silas Natterer , Alexander Thumm This is my paper

Pith reviewed 2026-05-15 19:12 UTC · model grok-4.3

classification 🧮 math.GR
keywords quadratic equationsgraph productsexponent of periodicityright-angled Artin groupsnormal formsgroup equationsBaumslag-Solitar groups
0
0 comments X

The pith

Structural conditions on groups and normal forms ensure quadratic systems with infinitely many solutions have solutions with arbitrarily large exponents of periodicity, preserved under graph products.

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

The paper investigates quadratic equations over finitely generated groups by defining the exponent of periodicity via normal forms. It isolates structural conditions on a group and its normal form that force any quadratic system with an infinite solution set to also admit solutions whose exponents of periodicity are unbounded. These conditions are shown to be closed under graph products, so the property holds for all finitely generated right-angled Artin groups as well as for torsion-free nilpotent groups, hyperbolic groups, and certain Baumslag-Solitar groups.

Core claim

If a group together with a chosen normal form satisfies the identified structural conditions, then every quadratic equation system over the group that possesses infinitely many solutions must possess solutions with unbounded exponent of periodicity. The conditions are preserved when groups are combined via graph products, yielding the property for right-angled Artin groups and the other listed classes.

What carries the argument

The exponent of periodicity extracted from normal forms, together with the structural conditions on groups and normal forms that are preserved under graph products.

If this is right

  • All finitely generated right-angled Artin groups satisfy the unbounded-exponent property for quadratic systems.
  • The property holds for finitely generated torsion-free nilpotent groups and for hyperbolic groups.
  • Graph products of groups satisfying the conditions continue to satisfy them.
  • Baumslag-Solitar groups that meet the conditions are precisely characterized.

Where Pith is reading between the lines

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

  • The result supplies a route toward decidability or finiteness criteria for solution sets in these groups.
  • The same normal-form conditions may be testable for other families such as hyperbolic groups with additional structure.
  • One could ask whether analogous conditions suffice for higher-degree equations or for monoids rather than groups.

Load-bearing premise

The structural conditions on a group and its normal form are sufficient to guarantee that infinite solution sets of quadratic systems have unbounded exponent of periodicity.

What would settle it

A quadratic system over a right-angled Artin group that has infinitely many solutions but only solutions with bounded exponent of periodicity.

read the original abstract

In 1977, Makanin established the decidability of equations in free monoids. A key ingredient in his proof is the exponent of periodicity: for a word $w$, it is the largest exponent $e$ such that $w$ contains a nonempty factor of the form $p^e$. Makanin showed the following for a system of equations in free monoids: if the system has a solution with a sufficiently large exponent of periodicity, then it has infinitely many solutions. However, the converse -- whether the existence of infinitely many solutions implies the existence of solutions with arbitrarily large exponent of periodicity -- remains open. In this paper, we investigate the analogous problem for quadratic equations in finitely generated groups. We use normal forms to define the exponent of periodicity. We then identify structural conditions on groups and their normal forms that guarantee that infinite solution sets of quadratic systems have an unbounded exponent of periodicity. We prove that these conditions are preserved under graph products and, in particular, hold for all finitely generated right-angled Artin groups. In addition, we show that they also hold for finitely generated (graph products of) torsion-free nilpotent and hyperbolic groups, and we characterize the Baumslag-Solitar groups satisfying them.

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

0 major / 3 minor

Summary. The paper extends Makanin's 1977 result on the exponent of periodicity from free monoids to quadratic equations over finitely generated groups. Using normal forms, it identifies structural conditions on groups and normal forms that guarantee that any quadratic system with infinitely many solutions admits solutions with arbitrarily large exponent of periodicity. The authors prove these conditions are preserved under graph products and verify that they hold for all finitely generated right-angled Artin groups; they further establish the conditions for graph products of torsion-free nilpotent and hyperbolic groups and characterize the Baumslag-Solitar groups that satisfy them.

Significance. If the structural conditions and preservation results hold, the work supplies a useful criterion for detecting unbounded periodicity in solution sets of quadratic equations in groups. The graph-product preservation theorem is a clear strength, directly yielding the result for RAAGs and several other classes without additional case analysis. The characterization of Baumslag-Solitar groups adds precision to the boundary of the result. These contributions are relevant to algorithmic questions in geometric group theory.

minor comments (3)
  1. [§2.2] §2.2, Definition 2.4: the definition of the exponent of periodicity via normal forms would benefit from a short concrete example (e.g., a word in a RAAG with a visible high-power factor) to clarify how the normal-form length interacts with the exponent.
  2. [Theorem 5.1] Theorem 5.1: the statement that the conditions are preserved under graph products is clear, but the proof sketch in §5.3 could explicitly flag which of the four structural conditions is used at each inductive step.
  3. [§6.2] §6.2, Table 1: the row for the Baumslag-Solitar group BS(2,3) lists the exponent bound as finite; a brief parenthetical remark explaining why the normal-form condition fails would help readers trace the characterization.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The referee's description correctly captures the paper's focus on structural conditions for unbounded exponent of periodicity in quadratic equations over groups, the preservation under graph products, and the applications to RAAGs, nilpotent groups, hyperbolic groups, and Baumslag-Solitar groups.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on Makanin's 1977 decidability result for free monoids (external prior work) together with independently stated structural conditions on groups and normal forms. These conditions are shown to be preserved under graph products by direct proof; the central claim for RAAGs and other classes follows from that preservation without any reduction of a 'prediction' to a fitted input, self-definition, or load-bearing self-citation chain. No equation or theorem in the paper equates a derived quantity to its own defining assumption by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the existence of suitable normal forms for the groups considered and on the definition of structural conditions that are shown to be preserved; these are domain assumptions rather than new free parameters or invented entities.

axioms (2)
  • domain assumption Finitely generated groups admit normal forms suitable for defining exponent of periodicity
    Invoked to extend the monoid notion to groups; appears in the setup of the exponent definition.
  • ad hoc to paper Graph products preserve the identified structural conditions on normal forms
    The paper proves this preservation, but the base groups must satisfy the conditions for the result to apply.

pith-pipeline@v0.9.0 · 5522 in / 1249 out tokens · 32124 ms · 2026-05-15T19:12:15.797618+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages

  1. [1]

    Adams.Mostly Harmless

    D. Adams.Mostly Harmless. Pan Books, London, 1992. The fifth book in the trilogy namedThe Hitch Hiker’s Guide to the Galaxy

    work page 1992

  2. [2]

    P. R. Asveld. Controlled iteration grammars and full hyper-AFL’s.Inform. and Control, 34(3):248 – 269, 1977

    work page 1977

  3. [3]

    R. V. Book and F. Otto.String-Rewriting Systems. Springer-Verlag, 1993

    work page 1993

  4. [4]

    M. R. Bridson and A. Haefliger.Metric Spaces of Non-Positive Curvature. Grundlehren der Mathematis- chen Wissenschaften. Springer Berlin, Heidelberg, 1999

    work page 1999

  5. [5]

    Cartier and D

    P. Cartier and D. Foata.Probl` emes combinatoires de commutation et r´ earrangements. Number 85 in Lecture Notes in Math. Springer-Verlag, Heidelberg, 1969

    work page 1969

  6. [6]

    Carvalho and P

    A. Carvalho and P. V. Silva. Geodesic languages for rational subsets and conjugates in virtually free groups.Journal of Algebra, 694:263–286, 2026

    work page 2026

  7. [7]

    Ciobanu, V

    L. Ciobanu, V. Diekert, and M. Elder. Solution sets for equations over free groups are EDT0L languages. Int. J. Algebra Comp., 26:843–886, 2016. Conference version in Proc. ICALP 2015, LNCS 9135

    work page 2016

  8. [8]

    Ciobanu and M

    L. Ciobanu and M. Elder. The complexity of solution sets to equations in hyperbolic groups.Israel J. Math., 245(2):869–920, 2021

    work page 2021

  9. [9]

    De Mol, Y

    L. De Mol, Y. V. Matiyasevich, E. G. Omodeo, A. Policriti, W. Sieg, and E. J. Weyuker. Martin Davis: An overview of his work in logic, computer science, and philosophy.Philosophia Mathematica, 33:425–450, 2025

    work page 2025

  10. [10]

    Diekert.Combinatorics on Traces, volume 454 ofLecture Notes in Comput

    V. Diekert.Combinatorics on Traces, volume 454 ofLecture Notes in Comput. Sci.Springer-Verlag, Heidelberg, 1990

    work page 1990

  11. [11]

    V. Diekert. Makanin’s Algorithm. In M. Lothaire, editor,Algebraic Combinatorics on Words, volume 90 ofEncyclopedia of Mathematics and Its Applications, chapter 12, pages 387–442. Cambridge University Press, 2002

    work page 2002

  12. [12]

    V. Diekert. More than 1700 years of word equations. InAlgebraic Informatics, pages 22–28, Cham, 2015. Springer International Publishing

    work page 2015

  13. [13]

    Diekert and M

    V. Diekert and M. Elder. Solutions to twisted word equations and equations in virtually free groups.Internat. J. Algebra Comput., 30:731–819, 2020. Conference version in ICALP 2017, see in LIPIcs.ICALP.2017.96:1–96:14

    work page 2020

  14. [14]

    Diekert, A

    V. Diekert, A. Je˙ z, and M. Kufleitner. Solutions of word equations over partially commutative structures. In Y. R. Ioannis Chatzigiannakis, Michael Mitzenmacher and D. Sangiorgi, editors,43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 127:1–1...

    work page 2016

  15. [15]

    Diekert, M

    V. Diekert, M. Kufleitner, G. Rosenberger, and U. Hertrampf.Discrete Algebraic Methods. Arithmetic, Cryptography, Automata and Groups. De Gruyter, 2016

    work page 2016

  16. [16]

    Diekert and M

    V. Diekert and M. Lohrey. Word equations over graph products.Internat. J. Algebra Comput., 18:493–533,

    work page

  17. [17]

    Conference version in FSTTCS 2003

    work page 2003

  18. [18]

    Diekert, Yu

    V. Diekert, Yu. Matiyasevich, and A. Muscholl. Solving word equations modulo partial commutations. Theoretical Computer Science, 224:215–235, 1999. Special issue of LFCS’97. Vol. 18:1 QUADRATIC EQUATIONS, GRAPH PRODUCTS, AND THE EXPONENT OF PERIODICITY 3:31

    work page 1999

  19. [19]

    Diekert and A

    V. Diekert and A. Muscholl. Solvability of equations in free partially commutative groups is decid- able.International Journal of Algebra and Computation, 16:1047–1070, 2006. Conference version in Proc. ICALP 2001, 543–554, LNCS 2076

    work page 2006

  20. [20]

    Diekert, S

    V. Diekert, S. Natterer, and A. Thumm. Word equations and the exponent of periodicity.ArXiv e-prints, 2025

    work page 2025

  21. [21]

    Diekert and G

    V. Diekert and G. Rozenberg, editors.The Book of Traces. World Scientific, Singapore, 1995

    work page 1995

  22. [22]

    C. Droms. Graph groups, coherence and three-manifolds.Journal of Algebra, 106(2):484–489, 1985

    work page 1985

  23. [23]

    Ch. Duboc. Commutations dans les mono¨ ıdes libres: un cadre th´ eorique pour l’´ etude du parallelisme. Th` ese, Facult´ e des Sciences de l’Universit´ e de Rouen, 1986

    work page 1986

  24. [24]

    Ch. Duboc. On some equations in free partially commutative monoids.Theoretical Computer Science, 46:159–174, 1986

    work page 1986

  25. [25]

    Duncan, A

    A. Duncan, A. Evetts, D. F. Holt, and S. Rees. Using EDT0L systems to solve some equations in the solvable Baumslag-Solitar groups.J. Algebra, 630:434–456, 2023

    work page 2023

  26. [26]

    Eilenberg.Automata, Languages, and Machines, volume A

    S. Eilenberg.Automata, Languages, and Machines, volume A. Academic Press, New York and London, 1974

    work page 1974

  27. [27]

    Ende.The Neverending Story

    M. Ende.The Neverending Story. Penguin Random House Children’s UK, 2009

    work page 2009

  28. [28]

    D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson, and W. P. Thurston.Word processing in groups. Jones and Bartlett Publishers, 1992

    work page 1992

  29. [29]

    E. R. Green.Graph products of groups. PhD thesis, University of Leeds, 1990

    work page 1990

  30. [30]

    M. Gromov. Hyperbolic groups. In S. M. Gersten, editor,Essays in Group Theory, number 8 in MSRI Publ., pages 75–263. Springer-Verlag, 1987

    work page 1987

  31. [31]

    Ju. I. Hmelevski˘ ı.Equations in Free Semigroups. Number 107 in Proc. Steklov Institute of Mathematics. American Mathematical Society, 1976. Translated from the Russian original: Trudy Mat. Inst. Steklov. 107, 1971

    work page 1976

  32. [32]

    D. F. Holt and S. Rees. Regularity of quasigeodesics in a hyperbolic group.International Journal of Algebra and Computation, 13:585–596, 2003

    work page 2003

  33. [33]

    J. E. Hopcroft and J. D. Ullman.Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979

    work page 1979

  34. [34]

    A. Je˙ z. Recompression: a simple and powerful technique for word equations. In N. Portier and T. Wilke, editors,STACS, volume 20 ofLIPIcs, pages 233–244, Dagstuhl, Germany, 2013. Schloss Dagstuhl–Leibniz- Zentrum f¨ ur Informatik. Journal version in J. ACM 2016 with DOI http://dx.doi.org/10.1145/2743014

    work page doi:10.1145/2743014 2013

  35. [35]

    A. Je˙ z. Word equations in non-deterministic linear space.J. Comput. Syst. Sci., 123:122–142, 2022

    work page 2022

  36. [36]

    R. M. Keller. Parallel program schemata and maximal parallelism I. Fundamental results.Journal of the ACM, 20(3):514–537, 1973

    work page 1973

  37. [37]

    Kharlampovich, I

    O. Kharlampovich, I. Lys¨ enok, A. Myasnikov, and N. Touikan. The solvability problem for quadratic equations over free groups is NP-complete.Theory of Computing Systems, 47:250–258, 2010

    work page 2010

  38. [38]

    Kharlampovich and A

    O. Kharlampovich and A. Myasnikov. Elementary theory of free non-abelian groups.J. of Algebra, 302:451–552, 2006

    work page 2006

  39. [39]

    S. C. Kleene. Representation of events in nerve nets and finite automata. In C. E. Shannon and J. McCarthy, editors,Automata Studies, number 34 in Annals of Mathematics Studies, pages 3–40. Princeton University Press, 1956

    work page 1956

  40. [40]

    J. C. Lennox and D. J. S. Robinson.The Theory of Infinite Soluble Groups. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, Oxford, 2004

    work page 2004

  41. [41]

    A. Levine. EDT0L solutions to equations in group extensions.J. Algebra, 619:860–899, 2023

    work page 2023

  42. [42]

    Lothaire.Algebraic Combinatorics on Words, volume 90 ofEncyclopedia of Mathematics and Its Applications

    M. Lothaire.Algebraic Combinatorics on Words, volume 90 ofEncyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge, 2002

    work page 2002

  43. [43]

    G. S. Makanin. The problem of solvability of equations in a free semigroup.Math. Sbornik, 103:147–236,

    work page

  44. [44]

    English transl. in Math. USSR Sbornik 32 (1977)

    work page 1977

  45. [45]

    G. S. Makanin. The problem of solvability of equations in free semigroups.Math. USSR Izvestiya, 21:483–546, 1983

    work page 1983

  46. [46]

    G. S. Makanin. Decidability of the universal and positive theories of a free group.Izv. Akad. Nauk SSSR, Ser. Mat. 48:735–749, 1984. In Russian; English translation in:Math. USSR Izvestija, 25, 75–88, 1985

    work page 1984

  47. [47]

    Y. V. Matijasevic. Enumerable sets are diophantine.Soviet Math. Dokl., 11:354–358, 1970

    work page 1970

  48. [48]

    Matiyasevich

    Yu. Matiyasevich. Some decision problems for traces. In S. Adian and A. Nerode, editors,Proceedings of the 4th International Symposium on Logical Foundations of Computer Science (LFCS’97), Yaroslavl, 3:32V. Diekert, S. Natterer, and A. ThummVol. 18:1 Russia, July 6–12, 1997, volume 1234 ofLecture Notes in Comput. Sci., pages 248–257, Heidelberg, 1997. Spr...

    work page 1997

  49. [49]

    Mazurkiewicz

    A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977

    work page 1977

  50. [50]

    Ochma´ nski.Regular trace languages (in Polish)

    E. Ochma´ nski.Regular trace languages (in Polish). PhD thesis, University of Warzaw, 1984

    work page 1984

  51. [51]

    Ochma´ nski

    E. Ochma´ nski. Regular behaviour of concurrent systems.Bulletin of the European Association for Theoretical Computer Science (EATCS), 27:56–67, Oct. 1985

    work page 1985

  52. [52]

    A. Y. Ol’shanskii. Almost every group is hyperbolic.International Journal of Algebra and Computation, 2:1–17, 1992

    work page 1992

  53. [53]

    Plandowski and W

    W. Plandowski and W. Rytter. Application of Lempel-Ziv encodings to the solution of word equations. In K. G. Larsen et al., editors,Proc. 25th International Colloquium Automata, Languages and Programming (ICALP’98), Aalborg (Denmark), 1998, volume 1443 ofLecture Notes in Comput. Sci., pages 731–742, Heidelberg, 1998. Springer-Verlag

    work page 1998

  54. [54]

    Plandowski and A

    W. Plandowski and A. Schubert. On the complexity of computation maximal exponent of periodicity of word equations and expressible relations (note).Theor. Comput. Sci., 792:62–68, 2019

    work page 2019

  55. [55]

    V. A. Roman’kov. Diophantine questions in the class of finitely generated nilpotent groups.J. Group Theory, 19:497–514, 2016

    work page 2016

  56. [56]

    Rozenberg and A

    G. Rozenberg and A. Salomaa.The Book of L. Springer-Verlag, 1986

    work page 1986

  57. [57]

    Z. Sela. Diophantine geometry over groups VIII: Stability.Ann. of Math., 177:787–868, 2013. This work is licensed under the Creative Commons Attribution License. T o view a copy of this license, visithttps://creativecommons.org/licenses/by/4.0/or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Stras...

    work page 2013