A Proof of Rauzy's Conjecture on Abelian Complexity
Pith reviewed 2026-05-09 14:00 UTC · model grok-4.3
The pith
There are no infinite ternary words with rationally independent letter frequencies and constant abelian complexity equal to 3.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We prove that there do not exist infinite ternary words with rationally independent letter frequencies and constant abelian complexity equal to 3.
What carries the argument
The abelian complexity function, which assigns to each length n the number of distinct abelian equivalence classes (Parikh vectors) among the factors of length n.
If this is right
- Constant abelian complexity equal to 3 is impossible for any aperiodic ternary word whose frequencies are rationally independent.
- The only infinite words with rationally independent frequencies and constant abelian complexity 2 remain the Sturmian words.
- Any attempt to build a ternary word with constant low abelian complexity must force linear dependence among the frequencies.
Where Pith is reading between the lines
- The same non-existence statement may hold for alphabets with four or more letters under analogous independence conditions.
- Proof methods developed here could be tested on other fixed-complexity functions such as factor complexity or abelian complexity with different constants.
- Words whose frequencies satisfy a linear relation over the rationals might still admit constant abelian complexity 3 and should be classified separately.
Load-bearing premise
That the standard definitions of abelian complexity via Parikh vectors and of rational independence of frequencies are fixed and cannot be relaxed without changing the statement.
What would settle it
An explicit construction of an infinite ternary word whose three letter frequencies are linearly independent over the rationals yet whose set of Parikh vectors has size exactly 3 for every length n would falsify the claim.
read the original abstract
A celebrated theorem by Coven and Hedlund (1973) states that Sturmian words are characterized by their abelian complexity: they are precisely the infinite words with rationally independent letter frequencies and constant abelian complexity equal to 2. In this article, we prove a conjecture of Rauzy (1983), showing that there do not exist infinite ternary words with rationally independent letter frequencies and constant abelian complexity equal to 3.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves Rauzy's 1983 conjecture: there do not exist infinite words over a ternary alphabet with rationally independent letter frequencies and constant abelian complexity p_ab(n) = 3 for all n. The argument extends the Coven-Hedlund theorem (characterizing Sturmian words via p_ab(n)=2) by case analysis on Parikh vectors of factors of each length and the admissible transitions between abelian equivalence classes, deriving a contradiction with the assumption of rational independence of the three letter frequencies.
Significance. If the proof holds, the result completes the picture for small constant abelian complexities in the ternary case, showing that p_ab(n)=3 is incompatible with frequency independence (in contrast to the Sturmian p_ab(n)=2 case). The direct combinatorial approach via Parikh vectors and class transitions supplies a non-circular, parameter-free derivation and supplies a falsifiable combinatorial obstruction.
minor comments (3)
- §2, Definition of abelian complexity: the notation p_ab(n) is introduced without an explicit reminder that it counts distinct Parikh vectors (abelian classes) rather than distinct factors; a one-sentence clarification would aid readers unfamiliar with the Coven-Hedlund literature.
- The case analysis in the main proof section would benefit from an explicit enumeration or diagram of the admissible transition graph between the three abelian classes for length n, making the contradiction with frequency independence easier to verify at a glance.
- A short remark comparing the obtained obstruction with the known examples of ternary words that achieve p_ab(n)=3 but necessarily have dependent frequencies (e.g., periodic or Sturmian-like substitutions) would strengthen the contextual framing.
Simulated Author's Rebuttal
We thank the referee for the careful reading of the manuscript and for the positive recommendation to accept. The referee's summary accurately captures the main result and its relation to the Coven-Hedlund theorem.
Circularity Check
No significant circularity; direct non-existence proof
full rationale
The manuscript establishes a non-existence result for infinite ternary words satisfying two independent conditions (rationally independent frequencies and p_ab(n)=3 for all n) by extending the Coven-Hedlund characterization through exhaustive case analysis on Parikh vectors and abelian-class transitions. All steps rest on standard combinatorial definitions and an external 1973 theorem; no parameter fitting, self-referential normalization, or reduction of the central claim to prior self-citations occurs. The derivation is self-contained against the stated assumptions.
Axiom & Free-Parameter Ledger
axioms (2)
- standard math Abelian complexity of an infinite word is the function p_ab(n) equal to the number of distinct Parikh vectors realized by its factors of length n.
- standard math Letter frequencies are rationally independent when the vector of frequencies lies outside any rational hyperplane.
Reference graph
Works this paper leans on
-
[1]
Cassaigne, J. and Ferenczi, S. and Zamboni, L. Q. , title =. Annales de l'institut Fourier , volume =. 2000 , publisher =
work page 2000
-
[2]
Fici, G. and Langiu, A. and Lecroq, T. and Lefebvre, A. and Mignosi, F. and Peltom. Abelian powers and repetitions in Sturmian words , journal =
-
[3]
Fici, G. and Puzynina, S. , title =. Computer Science Review , volume =. 2023 , issn =
work page 2023
- [4]
- [5]
- [6]
-
[7]
Currie, J. and Rampersad, N. , title =. Advances in Applied Mathematics , volume =
- [8]
-
[9]
Arnoux, P. and Rauzy, G. , title =. Bulletin de la Soci. 1991 , publisher =
work page 1991
- [10]
-
[11]
Billiard complexity in the hypercube , journal =
B. Billiard complexity in the hypercube , journal =. 2007 , publisher =
work page 2007
- [12]
- [13]
-
[14]
Cassaigne, J. and Hubert, P. and Troubetzkoy, S. , title =. Annales de l'Institut Fourier , volume =. 2002 , pages =
work page 2002
- [15]
-
[16]
Beyond substitutive dynamical systems :
Berth. Beyond substitutive dynamical systems :. RIMS Kokyuroku Bessatu , volume =. 2014 , pages =
work page 2014
- [17]
-
[18]
Glen, A. and Justin, J. , title =. RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications , volume =. 2009 , pages =
work page 2009
-
[19]
Justin, J. and Pirillo, G. , title =. Theoretical Computer Science , volume =. 2002 , pages =
work page 2002
- [20]
- [21]
-
[22]
Morse, M. and Hedlund, G.A. , title=. American Journal of Mathematics , volume=
- [23]
- [24]
-
[25]
Directional complexity of the hypercubic billiard , journal =
B. Directional complexity of the hypercubic billiard , journal =
- [26]
- [27]
-
[28]
Andrieu, M. and Vivion, L. , editor=. Minimal complexities for infinite words written with d letters , booktitle =
-
[29]
Morse, M. and Hedlund, G.A. , title=. American Journal of Mathematics , publisher =
-
[30]
Coven, E.M. and Hedlund, G.A. , title=. Mathematical systems theory , volume=
- [31]
-
[32]
Cassaigne, J. and Ferenczi, S. and Zamboni, L.Q. , title =. Annales de l'Institut Fourier , volume =
-
[33]
Delecroix, V. and Hejda, T. and Steiner, W. , editor =. Balancedness of. Combinatorics on Words , publisher =
- [34]
- [35]
- [36]
-
[37]
Richomme, G. and Saari, K. and Zamboni, L.Q. , title =. Advances in Applied Mathematics , volume =
- [38]
- [39]
- [40]
- [41]
- [42]
-
[43]
Richomme, G. and Saari, K. and Zamboni, L.Q. , title =. Journal of the London Mathematical Society , volume =
- [44]
-
[45]
2-balanced sequences coding rectangle exchange transformation , journal =
Dvo. 2-balanced sequences coding rectangle exchange transformation , journal =
- [46]
- [47]
- [48]
-
[49]
On balance properties of hypercubic billiard words , journal =
B. On balance properties of hypercubic billiard words , journal =
-
[50]
Grepstad, S. and Lev, N. , title =. Geometric and Functional Analysis , Volume =
- [51]
-
[52]
On a generalization of Abelian equivalence and complexity of infinite words , journal =
Karhum. On a generalization of Abelian equivalence and complexity of infinite words , journal =
-
[53]
Rigo, M. and Salimov, P. , title =. Theoretical Computer Science , volume =
- [54]
-
[55]
Lejeune, M. and Rigo, M. and Rosenfeld, M. , title =. Advances in Applied Mathematics , volume =
-
[56]
Arnoux, P. and Mauduit, C. and Shiokawa, I. and Tamura, J.I. , title=. Bulletin de la Soci
- [57]
-
[58]
Arnoux, P. and Mauduit, C. and Shiokawa, I. and Tamura, J.I. , title=. Tokyo Journal of Mathematics , volume=
- [59]
- [60]
-
[61]
Puzynina, S. and Zamboni, L.Q. , title =. Journal of Combinatorial Theory, Series A , volume =
-
[62]
Borel, J.P. and Reutenauer, C. , title =. Theoretical Computer Science , volume =
-
[63]
Classification of rotations on the torus
B. Classification of rotations on the torus. Theoretical Computer Science , volume =
- [64]
- [65]
- [66]
- [67]
- [68]
- [69]
-
[70]
Exceptional trajectories in the symbolic dynamics of multidimensional continued fraction algorithms , author =. 2021 , month =
work page 2021
-
[71]
Dynnikov, I. and Hubert, P. and Skripchenko, A. , title =. International Mathematics Research Notices , volume =
-
[72]
Barro, M. and Kabor\'e, I. and Tapsoba, T. , title =. International Journal of Applied Mathematics , volume =
-
[73]
Kabor\'e, I. and Tapsoba, T. , title =. RAIRO--Theoretical Informatics and Applications , volume =
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.