On the conjugates of Christoffel words

Basic Information

• Paper ID: 2202.05486
• Title: On the conjugates of Christoffel words
• Authors: Yann Bugeaud (Université de Strasbourg et CNRS, Institut universitaire de France), Christophe Reutenauer (Université du Québec à Montréal)
• Classification: math.CO (Combinatorics)
• Published in: Discrete Mathematics and Theoretical Computer Science, vol. 27:3 #20 (2025)
• Received: October 23, 2025
• Paper Link: https://arxiv.org/abs/2202.05486

Abstract

This paper introduces a parametrization method for conjugacy classes of Christoffel words based on the integer Ostrowski numeration system. Using this parametrization, the authors provide a precise characterization of borders (subwords that are both prefixes and suffixes) of conjugates of Christoffel words and revisit the concept of Sturmian graphs introduced by Epifanio et al.

Research Background and Motivation

Research Problem

This paper investigates the structure and properties of conjugacy classes of Christoffel words. Christoffel words are special word classes over a binary alphabet introduced by Christoffel in 1875, where conjugates are obtained through cyclic permutations.

Significance of the Problem

Christoffel words and their conjugates have important significance in multiple mathematical fields:

1. Free Group Theory: They correspond to positive, cyclically reduced elements that form bases in the two-generator free group
2. Data Compression: They are "perfectly clustering words" over binary alphabets, appearing in Burrows-Wheeler transform theory
3. Sturmian Word Theory: They are finite versions of Sturmian infinite words, related to discretization of plane lines
4. Quadratic Form Theory: They encode Markoff quadratic forms and their minima

Limitations of Existing Methods

Although parametrization of Christoffel words themselves by non-negative rationals is well-known, systematic parametrization of their conjugacy classes was previously incomplete. Specifically:

• Lack of a unified parametrization framework describing all conjugate elements
• Incomplete precise characterization of borders and periods of Christoffel word conjugates
• The relationship between Sturmian graphs and Ostrowski representation requires deeper understanding

Research Motivation

This paper aims to establish a systematic framework based on the Ostrowski numeration system to completely characterize conjugacy classes of Christoffel words and apply this framework to solve border problems and structural questions about Sturmian graphs.

Core Contributions

1. Parametrization Construction: Based on the integer Ostrowski numeration system, introduces a complete parametrization method for conjugacy classes of Christoffel words (Theorem 7.3), generalizing the Rauzy rule and standard word construction
2. Non-commutative Lifting: Proves Frid's result on prefixes of standard words as a corollary (Corollary 7.6), which can be viewed as a non-commutative lifting of the Ostrowski numeration system
3. Border Characterization: Provides precise description of the longest borders of Christoffel word conjugates (Theorem 8.1) and proves that any border is a power of some Christoffel word conjugate (Corollary 8.2)
4. Sturmian Graph Embedding: Proves that compact graphs and Sturmian graphs naturally embed into central word trees and Stern-Brocot trees (Corollary 9.5), utilizing de Luca's iterated palindromization theory
5. Unified Framework: Establishes deep connections between Ostrowski representation, conjugacy classes, borders, and graph-theoretic structures

Detailed Methodology

Task Definition

Given a sequence of positive integers $a_1, \ldots, a_m$, define:

• Associated polynomials: $q_i = K(a_1, \ldots, a_i)$, where $K$ is the continuant polynomial
• Parameters: $b_i = a_i - 1$ (if $i=1$), $b_i = a_i$ (if $i \geq 2$)

Objective: For each integer $N = \sum_{i=1}^m d_i q_{i-1}$ (Ostrowski representation), construct the corresponding Christoffel word conjugate.

Core Construction Method

Recursive Definition (Formula 11)

Define word sequence $V_i = V_i(d_1, \ldots, d_m) \in F(A)$ (free group):

$V_{-1} = b, \quad V_0 = a$

$V_i = V_{i-1}^{b_i - d_i} V_{i-2} V_{i-1}^{d_i}, \quad i = 1, \ldots, m$

where $A = \{a, b\}$ is a binary alphabet.

Key Properties:

• When $0 \leq d_i \leq b_i$, $V_i \in A^*$ (positive word)
• The length of $V_i$ is $q_i = K(a_1, \ldots, a_i)$
• The slope of $V_i$ is $[0, a_1, \ldots, a_i]$ (continued fraction)

Morphism Representation (Lemma 7.1)

The word $V_i$ can be represented through morphism composition:

$(V_i, V_{i-1}) = \pi(b_1 - d_1, d_1) \circ \cdots \circ \pi(b_i - d_i, d_i)$

where $\pi(i, j) = (a^i b a^j, a)$ is a specific endomorphism of the alphabet.

Parametrization Theorem (Theorem 7.3)

Main Result:

1. All $V_m(d_1, \ldots, d_m)$ (where $0 \leq d_i \leq b_i$) are conjugate to $M_m = V_m(0, \ldots, 0)$ in the free group
2. The conjugacy class in the word sense consists precisely of all words corresponding to Ostrowski representations satisfying legal conditions
3. Exact formula: $V_m = C^N(M_m)$, where $C$ is the conjugation operator and $N = \sum d_i q_{i-1}$

Proof Strategy:

• Utilize Lemma 5.1 (on conjugacy relations of automorphisms)
• Construct conjugating element $h$ such that $V_m = h^{-1} M_m h$
• Compute that the algebraic length of $h$ is exactly $N$
• Use uniqueness of Ostrowski representation to prove coverage of entire conjugacy class

Technical Innovations

1. Unified Framework: Unifies Rauzy rule, standard word construction, and Ostrowski numeration in recursive definition (11)
2. Algebraic Method: Utilizes conjugacy theory of free groups and abelianization matrices of morphisms to compute lengths
3. Dual Representations:
   • Greedy representation: $\forall i \geq 2, d_i = b_i \Rightarrow d_{i-1} = 0$
   • Lazy representation: $\forall i, 2 \leq i \leq k, d_i = 0 \Rightarrow d_{i-1} = b_{i-1}$
4. Mirror Symmetry (Proposition 7.8): $\widetilde{V_m(d_1, \ldots, d_m)} = V_m(b_1 - d_1, \ldots, b_m - d_m)$
   This establishes a duality between greedy and lazy representations.

Border Theory (Section 8)

Main Theorem (Theorem 8.1)

For $V_m(d_1, \ldots, d_m)$ that is not a Christoffel word (greedy representation), its longest border $B$ is determined by the following cases:

Case Classification:

• (i) If $d_m = b_m$: $B = V_{m-1}$
• (ii) If $1 \leq d_m \leq b_m - 1$ and $1 \leq d_{m-1} \leq b_{m-1} - 1$: $B = V_{m-1}^\ell$, where $\ell = \min\{b_m - d_m, d_m\}$
• (iii)-(vii) Other cases have similar but more complex descriptions

Key Lemma (Lemma 8.14): In $V_m = V_{m-1}^{b_m - d_m} V_{m-2} V_{m-1}^{d_m}$, the word $V_{m-1}$ appears at most $b_m + 2$ times, with additional occurrences only near $V_{m-2}$.

Corollary (Corollary 8.2)

Any border of a Christoffel word conjugate is a power of some Christoffel word conjugate.

Proof Strategy:

• If $u$ is a border of Christoffel word $w$, then $uu$ is a factor of $ww$
• $ww$ is a Sturmian word, hence all conjugates of $u$ are Sturmian words
• Among these exists a power of a Lyndon word, which must be a Christoffel word

Sturmian Graph Theory (Section 9)

Compact Graph Construction

Definition:

• Vertex set $V$: All prefixes of central palindrome $p = L_0^{c_1} L_1^{c_2} \cdots L_{m-1}^{c_m}$ (as words over $L_i$)
• Edges: Two types
  1. Horizontal edges: $U \xrightarrow{L_i} UL_i$
  2. Jump edges: $U \xrightarrow{L_{i+1}} UL_i^k L_{i+1}$ ($k \geq 1$)

Main Result (Corollary 9.2)

Theorem: For each suffix $s$ of central palindrome $p$, there exists a unique path from the origin with label $s$.

Proof Points:

1. Graph determinism: Each vertex has at most two outgoing edges with different initial labels
2. Path labels correspond exactly to lazy Ostrowski representations
3. Utilize Corollary 9.1: $s = L_0^{d_1} L_1^{d_2} \cdots L_{m-1}^{d_m}$

Stern-Brocot Tree Embedding (Corollary 9.5)

Proposition 9.4: The directive word of central word $p$ is $v = a^{c_1} b^{c_2} a^{c_3} \cdots$

Embedding Result:

• Compact graphs and Sturmian graphs naturally embed into central word trees
• Through correspondence with Stern-Brocot trees, also embed into that tree
• Utilizes de Luca's iterated palindromization operator $\text{Pal}$

Experiments and Verification

Example Computation (End of Section 9)

Parameters: $m = 3, a_1 = 2, a_2 = 1, a_3 = 3$

Computational Results:

• $M_0 = a, M_1 = ab, M_2 = aba, M_3 = abaabaabaab$
• $M_3 = pab$, central word $p = aba^2ba^2ba$
• Palindromic prefixes: $1, a, aba, abaaba, p$
• Directive word: $v = abaa$
• $L_0 = a, L_1 = ba, L_2 = aba$

Verification:

• $p = L_0 L_1^2 L_2 = a \cdot (ba)^2 \cdot aba = aba^2ba^2ba$ ✓
• Compact graph paths consistent with lazy representation ✓

Theoretical Verification

The paper provides complete proofs of uniqueness of Ostrowski representation in the appendix (Section 10):

Lemma 10.1: Alternating sequences correspond to $q_k - 1$

Lemma 10.2:

• Greedy representation: $N \leq q_k - 1$
• Lazy representation: $N \leq q_k + q_{k-1} - 2$

These results guarantee completeness of the parametrization.

Related Work

Historical Background

1. Christoffel (1875) and Smith (1876): Independently introduced Christoffel words
2. Markoff (1879, 1880): Used for constructing quadratic forms, unaware of connection to Christoffel
3. Frobenius (1913): Explicitly established the connection, proposed the famous Markoff number conjecture

Modern Theory

1. Rauzy (1985): "Rauzy rule," foundation of standard word construction
2. de Luca & Mignosi (1994, 1997): Standard word theory and iterated palindromization
3. Ostrowski (1922): Ostrowski numeration system
4. Epifanio et al. (2007, 2012): Sturmian graphs and lazy representation

Innovations of This Paper

1. vs Rauzy/de Luca: The recursive construction (11) is a more general framework, with standard words as special cases
2. vs Frid (2018): Corollary 7.6 generalizes Frid's result to entire conjugacy classes
3. vs Lapointe (2017): Reproves periodicity results using completely different methods (Ostrowski parametrization)
4. vs Epifanio et al.: Provides new perspective on Sturmian graph embedding into tree structures

Conclusions and Discussion

Main Conclusions

1. Complete Parametrization: Establishes bijection between conjugacy classes of Christoffel words and Ostrowski representations
2. Complete Border Characterization: All borders are powers of Christoffel word conjugates, with explicit formulas for longest borders
3. Graph-Theoretic Unification: Sturmian and compact graphs naturally embed into classical tree structures
4. Theory Deepening: Unifies combinatorial word theory, number theory (continued fractions), free group theory, and graph theory in one framework

Limitations

1. Computational Complexity: Paper does not discuss computational complexity of parametrization construction
2. Generalizability: Methods limited to binary alphabet; generalization to larger alphabets not obvious
3. Applications: While theory is elegant, discussion of practical application scenarios is limited
4. Algorithm Implementation: Lacks concrete algorithm pseudocode and implementation details

Future Directions

1. Algorithmization: Develop efficient algorithms for computing conjugates and borders
2. Generalization: Study analogous theory for larger alphabets or infinite words
3. Applications: Explore applications in data compression and pattern matching
4. Connections: Further investigate deep connections with Markoff theory and quadratic forms

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Establishes profound connections across multiple mathematical fields (combinatorics, number theory, algebra)
   • Rigorous and complete proofs with clear logic
2. Methodological Innovation:
   • Ostrowski parametrization provides entirely new perspective
   • Recursive construction (11) is elegant and unified
   • Mirror symmetry (Proposition 7.8) reveals deep structure
3. Result Completeness:
   • Provides not just existence but also uniqueness and explicit construction
   • Border theorem covers all cases
   • Generalizes and unifies multiple known results
4. Writing Quality:
   • Clear structure, progressing from basic definitions to advanced results
   • Well-organized lemmas and theorems
   • Provides concrete examples (Section 9)

Weaknesses

1. Readability Challenges:
   • Requires strong background in combinatorial word theory and free groups
   • Complex symbol system ($V_i, M_i, L_i, q_i, b_i$, etc.)
   • Theorem 8.1's seven cases are overly intricate
2. Experimental Verification:
   • Only one small-scale example
   • Lacks large-scale numerical verification
   • No code or computational tools provided
3. Application-Oriented Perspective:
   • Strong theory but limited application discussion
   • Does not clearly explain how to apply to practical problems
   • Computational efficiency not analyzed
4. Technical Details:
   • Some proofs (e.g., Theorem 8.1) are lengthy and highly technical
   • Appendix proof of Ostrowski representation, while complete, has poor readability

Impact

1. Academic Contribution:
   • Provides new unified framework for Christoffel word theory
   • Solves important border characterization problem
   • Connects Ostrowski numeration with word combinatorics
2. Potential Applications:
   • Data compression algorithms (Burrows-Wheeler transform)
   • Symbolic dynamical systems
   • Diophantine approximation in number theory
3. Reproducibility:
   • Strong reproducibility of theoretical results
   • Lack of software implementation limits practical applications
   • Example computations can be manually verified
4. Subsequent Research:
   • Provides theoretical foundation for algorithmic research
   • May inspire research on larger alphabets
   • Connection with Markoff theory deserves deeper exploration

Applicable Scenarios

1. Theoretical Research:
   • Further research in combinatorial word theory
   • Exploration of Sturmian and Christoffel word properties
   • Free group and free monoid theory
2. Algorithm Development:
   • String matching and pattern recognition
   • Period detection algorithms
   • Data compression optimization
3. Teaching:
   • Advanced courses in combinatorial mathematics and word combinatorics
   • Application examples of continued fraction theory
   • Concrete instances of free group theory
4. Interdisciplinary Applications:
   • Continued fraction expansion in number theory
   • Line discretization in discrete geometry
   • Quadratic form theory

Summary of Technical Highlights

Core Mathematical Tools

1. Continuant Polynomial: $K(n_1, \ldots, n_k) = K_{k-1}(n_1, \ldots, n_{k-1})n_k + K_{k-2}(n_1, \ldots, n_{k-2})$ Connects recursive definition and continued fractions
2. Morphism Composition: $M(\pi(i,j)) = P(i+j) = \begin{pmatrix} i+j & 1 \\ 1 & 0 \end{pmatrix}$ Computes lengths through abelianization
3. Conjugation Operator: $C(au) = ua, \quad C^n(w) = \text{cyclic shift}$ Connects algebraic length with word conjugacy

Key Inequalities

Greedy Representation (Lemma 10.2(i)): $q_{k-1} - 1 < N \leq q_k - 1$

Lazy Representation (Lemma 10.2(ii)): $q_{k-1} + q_{k-2} - 2 < N \leq q_k + q_{k-1} - 2$

These inequalities guarantee uniqueness of representation and completeness of parametrization.

Key References

1. Christoffel, E. B. (1875): Observatio arithmetica - Original definition
2. Rauzy, G. (1985): Mots infinis en arithmétique - Rauzy rule
3. de Luca, A. (1997): Sturmian words: structure, combinatorics - Standard word theory
4. Epifanio et al. (2007, 2012): On Sturmian graphs - Sturmian graphs
5. Frid, A. E. (2018): Sturmian numeration systems - Results generalized in this paper
6. Lapointe, M. (2017): Study of Christoffel classes - Period and normal form
7. Bugeaud & Laurent (2023): Combinatorial structure of Sturmian words - Infinite word version

Overall Assessment: This is a theoretically profound pure mathematics paper making important contributions to Christoffel word theory. By introducing Ostrowski parametrization, the authors establish an elegant unified framework solving conjugacy class characterization and border problems. The paper's main value lies in theoretical innovation and interdisciplinary connections, though there remains room for expansion in algorithmic implementation and practical applications. For researchers in combinatorial word theory and related fields, this is an essential reference.