Balanced Fibonacci word rectangles, and beyond

Ingrid Vukusic; Jeffrey Shallit

arxiv: 2509.25994 · v6 · submitted 2025-09-30 · 🧮 math.NT · cs.DM· cs.FL· math.CO

Balanced Fibonacci word rectangles, and beyond

Jeffrey Shallit , Ingrid Vukusic This is my paper

Pith reviewed 2026-05-18 12:39 UTC · model grok-4.3

classification 🧮 math.NT cs.DMcs.FLmath.CO

keywords Fibonacci wordSturmian wordsbalance propertyfinite automatonrectangular matricesTribonacci wordThue-Morse wordquadratic irrationals

0 comments

The pith

Rectangular matrices from the Fibonacci word have balance properties decidable by a finite automaton.

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

The paper shows that for the Fibonacci infinite word, one can decide if an m by n rectangle extracted from it is balanced using a finite automaton that reads m and n. This provides an algorithmic solution to checking the balance property without needing to build the actual matrix each time. The result generalizes to all characteristic Sturmian words generated by quadratic irrationals, and the authors also investigate the same question for the Tribonacci word and the Thue-Morse word. A reader might care because these words are central to the study of aperiodic sequences and low-complexity languages, making their properties more computable.

Core claim

Following a recent paper of Anselmo et al., we consider m × n rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word and the Thue-Morse word.

What carries the argument

Finite automaton that accepts the pairs (m, n) for which the corresponding rectangle is balanced, based on the mechanical properties of Sturmian words.

If this is right

For given m and n one can algorithmically determine if the rectangle is balanced.
The decidability extends to all quadratic Sturmian characteristic words.
Similar decidability questions can be posed and potentially answered for other infinite words like Tribonacci and Thue-Morse.

Where Pith is reading between the lines

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

This could lead to efficient software tools for verifying balance in word-based constructions used in cryptography or tiling.
Since Sturmian words have low complexity, many other geometric or combinatorial properties of their rectangles might also be automaton-recognizable.
Generalizing further to higher-dimensional arrays or other morphic words with similar balance notions would be a natural next step.

Load-bearing premise

The balance property of the rectangles depends in a way that can be captured by a finite-state machine due to the specific structure of these words.

What would settle it

Computing the balance for a large but specific pair m and n where the automaton and the direct definition disagree.

Figures

Figures reproduced from arXiv: 2509.25994 by Ingrid Vukusic, Jeffrey Shallit.

**Figure 1.** Figure 1: 0 [0,0] 1 [1,0] 2 [0,1] 3 [1,1] 4 [0,0] 5 [0,1] [0,0] 6 7 [1,0] 8 [0,0] [1,0] [1,1] 9 [0,0] 10 [0,1] 11 [0,0] [0,1] [1,1] 12 [0,0] 13 [1,0] 14 [0,0] [0,1] [1,0] [0,0] [1,0] [1,1] [0,0] [0,1] [1,0] [0,0] [0,1] [0,0] [0,1] [1,1] [0,0] [1,0] [0,1] [0,0] [1,0] [0,0] [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** Figure 2: Automaton accepting balanced (m, n) pairs for the Fibonacci word with m ≤ n. reg case_a msd_fib msd_fib "([0,0]|[0,1])*|([0,0]|[0,1])*([1,0]|[1,1])": reg case_b msd_fib msd_fib "([0,0]|[0,1])*[0,1][0,0]([0,0][0,0])*[1,0]([0,0]|[0,1])*": # lower part of red reg case_c msd_fib msd_fib "([0,0]|[0,1])*[1,1]([0,0]|[0,1])*": # dark blue, light blue, and the lower part of yellow reg case_d msd_fib msd_fib "([0,0]… view at source ↗

read the original abstract

Following a recent paper of Anselmo et al., we consider $m \times n$ rectangular matrices formed from the Fibonacci word, and we show that their balance properties can be solved with a finite automaton. We also generalize the result to every Sturmian characteristic word corresponding to a quadratic irrational. Finally, we also examine the analogous question for the Tribonacci word and the Thue-Morse word.

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.

Desk Editor's Note private letter to a colleague

Finite automata decide rectangular balance for quadratic Sturmian words, with explicit checks on Tribonacci and Thue-Morse.

read the letter

The main thing to know is that the authors show rectangular balance for m by n arrays from the Fibonacci word is recognizable by a finite automaton, then extend the same approach to every characteristic Sturmian word whose slope is a quadratic irrational. They also run direct checks on the Tribonacci word and the Thue-Morse word using their morphic structure. This is a clean computational advance inside combinatorics on words. The quadratic-irrational condition supplies periodic continued fractions, which keeps the discrepancy states finite and independent of rectangle size. The low subword complexity p(n)=n+1 of Sturmian words supplies the bound on the information the automaton needs to track letter counts and alignments. The extension from the Anselmo et al. Fibonacci case looks straightforward once those properties are in hand, and the extra cases add a bit of breadth without much extra machinery. The soft spots are limited. The central claim rests on the 1D mechanical properties carrying over to the 2D rectangular setting without extra state blow-up; the stress-test note says explicit transition rules close the argument, so the gap appears small. The Tribonacci and Thue-Morse sections read as verification rather than new theory, which is fine but not deep. No circular fitting or invented parameters show up. This paper is for readers who already work with Sturmian words, automata, and balance properties. Someone comfortable with the 1D theory will see the value in the 2D decision procedure right away. It deserves a serious referee because the claims are concrete, the method is reproducible from standard facts, and the result supplies an explicit computational tool rather than an existence statement.

Referee Report

0 major / 2 minor

Summary. The paper considers m×n rectangular matrices formed from the Fibonacci word and shows that their balance properties can be solved with a finite automaton. It generalizes the result to every Sturmian characteristic word corresponding to a quadratic irrational and examines the analogous question for the Tribonacci word and the Thue-Morse word.

Significance. If the central claims hold, the work supplies an explicit finite-automaton construction that decides rectangular balance for the Fibonacci word and extends it to all quadratic-irrational Sturmian words via continued-fraction periodicity and the p(n)=n+1 complexity bound. The direct morphic analysis for Tribonacci and Thue-Morse cases further demonstrates the reach of the finite-state approach. These contributions strengthen the bridge between one-dimensional mechanical words and their two-dimensional rectangular extractions.

minor comments (2)

[Abstract] The abstract states that balance properties 'can be solved with a finite automaton' but does not indicate the precise state space or acceptance condition; a one-sentence description of the tracked discrepancy or alignment states would aid readability.
[Section 3] Section 3 (or the automaton-construction section) would benefit from an explicit small example showing the transition table for a 2×3 rectangle in the Fibonacci word, confirming that the state set remains independent of m and n.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and constructive report, which accurately summarizes the main contributions of our work on balance properties of rectangular extractions from the Fibonacci word and its generalizations. We appreciate the recommendation for minor revision and will address all points raised.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper derives that balance properties of rectangular arrays from the Fibonacci word (and generalizations to Sturmian words with quadratic irrational slopes) are recognizable by a finite automaton. This rests on the externally established facts of subword complexity p(n)=n+1 and mechanical word characterizations from the cited Anselmo et al. work, which has no author overlap. The extension to 2D rectangles is achieved by constructing explicit state-transition rules that track letter counts and alignments using the periodic continued-fraction structure of the slope; these rules are supplied directly in the proofs and do not reduce to any fitted parameters, self-definitions, or load-bearing self-citations from the present authors. The Tribonacci and Thue-Morse cases are handled by direct morphic inspection, preserving independence from the target claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard definitions of Sturmian words, balance, and finite automata from the literature; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Balance of rectangular matrices from Sturmian words is decidable by finite automata when the slope is a quadratic irrational.
This is the load-bearing claim being established; it is invoked as the framework inherited from Anselmo et al. and extended here.

pith-pipeline@v0.9.0 · 5581 in / 1242 out tokens · 57301 ms · 2026-05-18T12:39:29.209910+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Allouche and J

J.-P. Allouche and J. Shallit.Automatic Sequences: Theory, Applications, Generaliza- tions. Cambridge University Press, 2003

work page 2003
[2]

Anselmo, D

M. Anselmo, D. Giammarresi, M. Madonia, and C. Selmi. Fibonacci pictures on a binary alphabet. In A. Malcher and L. Prigioniero, editors,DCFS 2025, volume 15759 ofLecture Notes in Computer Science, pages 1–16. Springer-Verlag, 2025

work page 2025
[3]

J. Berstel. Fibonacci words—a survey. In G. Rozenberg and A. Salomaa, editors,The Book of L, pages 13–27. Springer-Verlag, 1986

work page 1986
[4]

J. Berstel. Recent results on extensions of Sturmian words.Internat. J. Algebra Com- put., 12:371–385, 2002

work page 2002
[5]

Berstel and C

J. Berstel and C. Reutenauer.Noncommutative Rational Series With Applications, volume 137 ofEncyclopedia of Mathematics and Its Applications. Cambridge Univ. Press, 2011

work page 2011
[6]

Berstel and P

J. Berstel and P. S´ e´ ebold. Sturmian words. In M. Lothaire, editor,Algebraic Combina- torics on Words, pages 45–110. Cambridge University Press, 2002

work page 2002
[7]

Berth´ e and R

V. Berth´ e and R. Tijdeman. Balance properties of multi-dimensional words.Theoret. Comput. Sci., 273:197–224, 2002

work page 2002
[8]

T. C. Brown. Descriptions of the characteristic sequence of an irrational.Canad. Math. Bull., 36:15–21, 1993. 16

work page 1993
[9]

Bruy` ere, G

V. Bruy` ere, G. Hansel, C. Michaux, and R. Villemaire. Logic andp-recognizable sets of integers.Bull. Belgian Math. Soc., 1:191–238, 1994. Corrigendum,Bull. Belgian Math. Soc.1(1994), 577

work page 1994
[10]

Carlitz, R

L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr. Fibonacci representations of higher order. Fibonacci Quart., 10:43–69, 94, 1972

work page 1972
[11]

C. G. Lekkerkerker. Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci.Simon Stevin, 29:190–195, 1952

work page 1952
[12]

Markovsky.Low-Rank Approximation: Algorithms, Implementation, Applications

I. Markovsky.Low-Rank Approximation: Algorithms, Implementation, Applications. Springer-Verlag, 2nd edition, 2019

work page 2019
[13]

H. Mousavi. Automatic theorem proving inWalnut. ArXiv preprint arXiv:1603.06017 [cs.FL], 2016. URL:http://arxiv.org/abs/1603.06017

work page arXiv 2016
[14]

Richomme, K

G. Richomme, K. Saari, and L. Q. Zamboni. Balance and abelian complexity of the Tribonacci word.Adv. in Appl. Math., 45:212–231, 2010

work page 2010
[15]

Schaeffer, J

L. Schaeffer, J. Shallit, and S. Zorcic. Beatty sequences for a quadratic irrational: decidability and applications. Arxiv preprint arXiv:2402.08331 [math.NT]. Available at https://arxiv.org/abs/2402.08331, 2024

work page arXiv 2024
[16]

J. Shallit. Synchronized sequences. In T. Lecroq and S. Puzynina, editors,WORDS 2021, volume 12847 ofLecture Notes in Computer Science, pages 1–19. Springer-Verlag, 2021.doi:10.1007/978-3-030-85088-3_1

work page doi:10.1007/978-3-030-85088-3_1 2021
[17]

Shallit.The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words withWalnut, volume 482 ofLondon Mathematical Society Lecture Note Series

J. Shallit.The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words withWalnut, volume 482 ofLondon Mathematical Society Lecture Note Series. Cambridge University Press, 2023

work page 2023
[18]

Shallit, S

J. Shallit, S. L. Shan, and K. H. Yang. Automatic sequences in negative bases and proofs of some conjectures of Shevelev.RAIRO Inform. Th´ eor. App., 57:#4, 2023

work page 2023
[19]

L. Vuillon. Balanced words.Bull. Belgian Math. Soc., 10(5):787–805, 12 2003.doi: 10.36045/bbms/1074791332

work page doi:10.36045/bbms/1074791332 2003
[20]

Zeckendorf

E. Zeckendorf. Repr´ esentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas.Bull. Soc. Roy. Li` ege, 41:179–182, 1972. AWalnutcommands The three principalWalnutcommands used in this paper are •reg: defines a regular expression; 17 •def: defines an automaton for later use; •eval: evaluates a first-order logical stateme...

work page 1972

[1] [1]

Allouche and J

J.-P. Allouche and J. Shallit.Automatic Sequences: Theory, Applications, Generaliza- tions. Cambridge University Press, 2003

work page 2003

[2] [2]

Anselmo, D

M. Anselmo, D. Giammarresi, M. Madonia, and C. Selmi. Fibonacci pictures on a binary alphabet. In A. Malcher and L. Prigioniero, editors,DCFS 2025, volume 15759 ofLecture Notes in Computer Science, pages 1–16. Springer-Verlag, 2025

work page 2025

[3] [3]

J. Berstel. Fibonacci words—a survey. In G. Rozenberg and A. Salomaa, editors,The Book of L, pages 13–27. Springer-Verlag, 1986

work page 1986

[4] [4]

J. Berstel. Recent results on extensions of Sturmian words.Internat. J. Algebra Com- put., 12:371–385, 2002

work page 2002

[5] [5]

Berstel and C

J. Berstel and C. Reutenauer.Noncommutative Rational Series With Applications, volume 137 ofEncyclopedia of Mathematics and Its Applications. Cambridge Univ. Press, 2011

work page 2011

[6] [6]

Berstel and P

J. Berstel and P. S´ e´ ebold. Sturmian words. In M. Lothaire, editor,Algebraic Combina- torics on Words, pages 45–110. Cambridge University Press, 2002

work page 2002

[7] [7]

Berth´ e and R

V. Berth´ e and R. Tijdeman. Balance properties of multi-dimensional words.Theoret. Comput. Sci., 273:197–224, 2002

work page 2002

[8] [8]

T. C. Brown. Descriptions of the characteristic sequence of an irrational.Canad. Math. Bull., 36:15–21, 1993. 16

work page 1993

[9] [9]

Bruy` ere, G

V. Bruy` ere, G. Hansel, C. Michaux, and R. Villemaire. Logic andp-recognizable sets of integers.Bull. Belgian Math. Soc., 1:191–238, 1994. Corrigendum,Bull. Belgian Math. Soc.1(1994), 577

work page 1994

[10] [10]

Carlitz, R

L. Carlitz, R. Scoville, and V. E. Hoggatt, Jr. Fibonacci representations of higher order. Fibonacci Quart., 10:43–69, 94, 1972

work page 1972

[11] [11]

C. G. Lekkerkerker. Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci.Simon Stevin, 29:190–195, 1952

work page 1952

[12] [12]

Markovsky.Low-Rank Approximation: Algorithms, Implementation, Applications

I. Markovsky.Low-Rank Approximation: Algorithms, Implementation, Applications. Springer-Verlag, 2nd edition, 2019

work page 2019

[13] [13]

H. Mousavi. Automatic theorem proving inWalnut. ArXiv preprint arXiv:1603.06017 [cs.FL], 2016. URL:http://arxiv.org/abs/1603.06017

work page arXiv 2016

[14] [14]

Richomme, K

G. Richomme, K. Saari, and L. Q. Zamboni. Balance and abelian complexity of the Tribonacci word.Adv. in Appl. Math., 45:212–231, 2010

work page 2010

[15] [15]

Schaeffer, J

L. Schaeffer, J. Shallit, and S. Zorcic. Beatty sequences for a quadratic irrational: decidability and applications. Arxiv preprint arXiv:2402.08331 [math.NT]. Available at https://arxiv.org/abs/2402.08331, 2024

work page arXiv 2024

[16] [16]

J. Shallit. Synchronized sequences. In T. Lecroq and S. Puzynina, editors,WORDS 2021, volume 12847 ofLecture Notes in Computer Science, pages 1–19. Springer-Verlag, 2021.doi:10.1007/978-3-030-85088-3_1

work page doi:10.1007/978-3-030-85088-3_1 2021

[17] [17]

Shallit.The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words withWalnut, volume 482 ofLondon Mathematical Society Lecture Note Series

J. Shallit.The Logical Approach To Automatic Sequences: Exploring Combinatorics on Words withWalnut, volume 482 ofLondon Mathematical Society Lecture Note Series. Cambridge University Press, 2023

work page 2023

[18] [18]

Shallit, S

J. Shallit, S. L. Shan, and K. H. Yang. Automatic sequences in negative bases and proofs of some conjectures of Shevelev.RAIRO Inform. Th´ eor. App., 57:#4, 2023

work page 2023

[19] [19]

L. Vuillon. Balanced words.Bull. Belgian Math. Soc., 10(5):787–805, 12 2003.doi: 10.36045/bbms/1074791332

work page doi:10.36045/bbms/1074791332 2003

[20] [20]

Zeckendorf

E. Zeckendorf. Repr´ esentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas.Bull. Soc. Roy. Li` ege, 41:179–182, 1972. AWalnutcommands The three principalWalnutcommands used in this paper are •reg: defines a regular expression; 17 •def: defines an automaton for later use; •eval: evaluates a first-order logical stateme...

work page 1972