The Tribonacci constant and finite automata

Basic Information

• Paper ID: 2510.10834
• Title: The Tribonacci constant and finite automata
• Author: Jeffrey Shallit (University of Waterloo)
• Classification: cs.FL cs.DM math.NT
• Publication Date: October 21, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.10834

Abstract

This paper proves that there does not exist a finite automaton that can simultaneously accept the Tribonacci representations of n and x, where ψ = 1.839··· is the Tribonacci constant and x = ⌊nψ⌋. Similarly, there does not exist a Tribonacci automaton that can generate the Sturmian characteristic word with slope ψ-1.

Research Background and Motivation

Problem Context

1. Success in the Fibonacci case: For the golden ratio φ = (1+√5)/2, the sequence (⌊φn⌋)_{n≥0} is Fibonacci-synchronized, meaning there exists a finite automaton that can simultaneously accept the Zeckendorf representations of n and x if and only if x = ⌊φn⌋.
2. Natural generalization question: Does a similar property exist for generalizations of Fibonacci numbers, such as Tribonacci numbers?
3. Intersection of number theory and automata theory: This problem involves deep connections between properties of irrational numbers in number theory and finite automata theory in theoretical computer science.

Research Motivation

• To explore whether the generalization from second-order recurrences (Fibonacci) to third-order recurrences (Tribonacci) preserves automaton recognizability
• To understand the fundamental differences between higher-order recurrent sequences and finite automata
• To provide theoretical foundations for related logical theories and decidability problems

Core Contributions

1. Main negative result: Proves that the sequence (⌊ψn⌋)_{n≥0} is not Tribonacci-synchronized, where ψ is the Tribonacci constant
2. Non-automaticity of Sturmian sequences: Proves that the corresponding Sturmian characteristic sequence is not Tribonacci-automatic
3. Impact on logical theory: Proves that the mapping n → ⌊ψn⌋ cannot be expressed in the first-order theory ⟨N,+,V'(n)⟩
4. Deep mathematical insight: Reveals that the fundamental difference between second-order and third-order cases lies in the absence of periodicity

Methodology Details

Task Definition

Investigates two classes of automaton problems:

1. Synchronous automata: Accept functions f: N → N by simultaneously inputting n and x (in Tribonacci representation), accepting if and only if x = f(n)
2. Output automata (DFAO): Compute sequences (a_n)_{n≥0} by inputting the Tribonacci representation of n and outputting a_n

Core Mathematical Construction

Properties of Tribonacci Numbers

• Recurrence relation: T_i = T_ + T_ + T_, with initial values T_0 = 0, T_1 = 1, T_2 = 1
• Closed form: T_n = c_1ψ^n + c_2α^n + c_3β^n
• Where ψ ≈ 1.839 is the real root of X³ - X² - X - 1, and α, β are complex conjugate roots

Key Technical Construction

Define:

• a(n) = ⌊ψn⌋
• b(n) = ⌊(ψ-1)(n+2)⌋ - ⌊(ψ-1)(n+1)⌋
• c(n) = ⌊ψ(n+1)⌋ - ⌊ψn⌋

Proof Strategy

Main Proof Approach

1. Reduction argument: Proves that if a(n) is synchronous, then b(n) is automatic
2. State distinction: Constructs infinitely many distinguishable automaton states
3. Application of Myhill-Nerode theorem: Uses state distinction to prove the non-existence of finite automata

Key Mathematical Analysis

Utilizes properties of fractional parts:

{ψT_n} = {2Re c_2(ψ-α)α^n}

Where:

• γ = arg c_2(ψ-α) = 2.536155···
• ζ = arg α = 4.10695···
• The value of c(T_n) depends on v(n) := γ + nζ mod 2π

Experimental Setup

Theoretical Verification Methods

This paper is primarily theoretical, employing verification methods including:

1. Numerical computation: Verifies precise values of complex coefficients and parameters
2. Application of Kronecker's theorem: Proves density properties
3. Linear independence verification: Confirms that ζ and 2π are linearly independent over the rationals

Key Parameter Calculations

• |c_2(ψ-α)| = 0.608085···
• |α| = 0.73735···
• Verified that |2Re c_2(ψ-α)α^n| < 2-ψ holds for n ≥ 5

Experimental Results

Main Theoretical Results

Completion of Theorem 1's Proof

Proves that:

1. The sequence (a(n))_{n≥0} is not Tribonacci-synchronized
2. The sequence (b(n))_{n≥0} is not Tribonacci-automatic

Constructive Proof of State Distinction

• For all i < j, there exists k such that c(T_{i+k}) ≠ c(T_{j+k})
• Kronecker's theorem ensures the existence of infinitely many such k
• Successfully constructs infinitely many distinguishable states

Logical Theory Results

Theorem 2

Proves that the mapping n → ⌊ψn⌋ cannot be expressed in the first-order theory ⟨N,+,V'(n)⟩, where V'(n) is the smallest Tribonacci number in the Tribonacci representation of n.

Related Work

Known Results in the Fibonacci Case

• Mousavi et al. and Hieronymi independently proved that n → ⌊φn⌋ is expressible in the corresponding structure
• Khani and Zarei obtained similar results using different methods
• Similar properties hold for arbitrary quadratic irrationals

Numeral System Theory

• Zeckendorf representation theory
• Representation theory of generalized Fibonacci sequences
• Pisano number-related numeral systems

Conclusions and Discussion

Main Conclusions

1. Fundamental difference: There exists an essential distinction between the Fibonacci and Tribonacci cases
2. Absence of periodicity: The sign of F_{n+1} - φF_n is periodic, but the sign of T_{n+1} - ψT_n is not periodic
3. Approximate results exist: Although exact results are unattainable, there exist automata approximations with errors within ±1

Limitations

1. Negative results: Primarily negative results without providing alternative constructive methods
2. Specific to Tribonacci: Results are specific to third-order recurrences; higher-order cases require separate analysis
3. Precision of approximation: The error bounds of approximate automata may not be sufficiently precise

Future Directions

1. Other Pisano numbers: Investigate numeral systems based on other cubic Pisano numbers
2. Higher-order generalizations: Consider cases of k-th order recurrent sequences
3. Approximate algorithms: Improve the precision and efficiency of approximate automata

In-Depth Evaluation

Strengths

1. Theoretical depth: Reveals the fundamental impact of recurrence order on automaton recognizability
2. Proof techniques: Skillfully combines complex analysis, number theory, and automata theory
3. Completeness: Not only proves the main results but also analyzes implications for logical theory
4. Mathematical rigor: The proof is rigorous and computations are precise

Weaknesses

1. Lack of constructivity: Primarily negative existence results lacking positive constructions
2. Limited applicability: Results are mainly theoretical with limited practical application value
3. Generalizability: The generalizability of methods to other similar problems requires further verification

Impact

1. Theoretical contribution: Provides important insights for interdisciplinary research between automata theory and number theory
2. Methodological value: Proof techniques serve as reference for related problems
3. Boundary determination: Clarifies the applicable boundaries of automata methods

Applicable Scenarios

1. Theoretical research: Number theory, automata theory, formal language theory
2. Algorithm design: Design of numerical algorithms that must account for automata constraints
3. Complexity theory: Research on related decidability problems

References

The paper cites 17 important references, covering:

• Classical automata theory textbooks (Hopcroft & Ullman)
• Pioneering work on Fibonacci automata (Bruyère et al.)
• Number theory foundations (Hardy & Wright)
• Related recent research (Mousavi et al., Hieronymi et al.)

Overall Assessment: This is a high-quality theoretical paper that rigorously proves the fundamental difference between Fibonacci and Tribonacci cases in automaton recognizability. Although primarily negative results, it makes important theoretical contributions to the field, particularly in understanding the relationship between recurrent sequences and finite automata, with far-reaching significance.