🔢 mathematics

Balanced Fibonacci word rectangles, and beyond

This paper demonstrates that the balance properties of rectangular matrices formed from Fibonacci words can be decided by a finite automaton, extends this result to Sturmian words associated with quadratic irrationals, and investigates analogous properties for Tribonacci and Thue-Morse words.

Original authors: Jeffrey Shallit, Ingrid Vukusic

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jeffrey Shallit, Ingrid Vukusic

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have an infinite strip of paper covered in a pattern of black and white dots. This pattern isn't random; it follows a very specific, mathematical rhythm known as the Fibonacci word. It looks something like this: 01001010... (where 0 is white and 1 is black).

Now, imagine you take a pair of scissors and cut out a rectangular window from this strip. You can slide this window along the strip, and every time you move it, you see a slightly different arrangement of dots inside your window.

The Big Question:
If you keep sliding this window, will the number of black dots inside it stay roughly the same? Or will it swing wildly, sometimes having almost all black dots and other times almost all white dots?

In math terms, we call a rectangle "balanced" if the number of black dots in any window of that size never varies by more than a tiny amount (specifically, if the difference between the "most black" window and the "least black" window is at most 1 or 2).

This paper by Jeffrey Shallit and Ingrid Vukusic is like a detective story. They are trying to answer: "For which sizes of windows (say, 4x5 or 7x12) is the pattern perfectly balanced?"

Here is the breakdown of their discovery, explained with everyday analogies:

1. The "Magic Machine" (Finite Automata)

The authors didn't just guess the answer. They built a "magic machine" (in computer science, called a finite automaton).

Think of this machine as a very strict bouncer at a club.

You hand the bouncer two numbers: the width ( $m$ ) and the height ( $n$ ) of your window.
The bouncer checks a secret rulebook (which is actually a complex flowchart of states).
If the window size is "balanced," the bouncer lets you in (says "Yes").
If the window size is "unbalanced," the bouncer kicks you out (says "No").

The amazing part is that for the Fibonacci word, this bouncer is surprisingly simple. It doesn't need to remember the whole infinite strip; it just needs to look at the numbers $m$ and $n$ in a special code (called Zeckendorf representation, which is like counting using only Fibonacci numbers) and make a quick decision.

2. The "Staircase" Analogy (Why it works)

Why is the Fibonacci word special? Imagine the dots are steps on a staircase.

If you take a step up, you go from 0 to 1.
If you take a step down, you go from 1 to 0.
The Fibonacci word is built so that you never take two steps up in a row, and you never take two steps down in a row. It's a very gentle, rhythmic walk.

The authors proved that if you look at the "total height" (the sum of dots) of any rectangular window, the difference between the highest window and the lowest window is tiny. They found a specific rule: If the larger of your two numbers (width or height) is a Fibonacci number (like 2, 3, 5, 8, 13...), the window is guaranteed to be balanced.

But they went further! They found other sizes that are also balanced, like a 4x3 window. They used their "magic machine" to list all the winning sizes.

3. The "Tribonacci" and "Thue-Morse" Cousins

The authors didn't stop at the Fibonacci word. They looked at two other famous patterns:

The Tribonacci Word: This is like the Fibonacci word but with three colors (0, 1, and 2) instead of two. It's more chaotic. They found that for this pattern, if your window is too tall (3 or more rows), it's impossible to be perfectly balanced. It's like trying to stack a wobbly tower; eventually, it tips over.
The Thue-Morse Word: This is a pattern that is famous for never repeating itself. Here, the math is a bit different. The authors found that the "imbalance" (the difference between the most and least dots) is always very small (never more than 4), regardless of the window size. It's like a very well-mixed salad; no matter how big a scoop you take, the ratio of ingredients stays almost the same.

4. The "Computer Brain" (Walnut)

How did they find these rules? They didn't do it with a pencil and paper. They used a free software tool called Walnut.

Think of Walnut as a super-powered calculator that speaks "logic." You can tell it: "Check every possible window size. If you find a window where the dot count swings too wildly, mark it as 'bad'."
The computer then builds the "bouncer" (the automaton) automatically. The authors had to wait for the computer to crunch the numbers for the Thue-Morse word, which took over 3 hours and used a massive amount of memory (100 gigabytes of RAM)—like filling a small warehouse with hard drives just to solve one puzzle!

The Takeaway

This paper is a triumph of automated reasoning. It shows that even for infinite, complex patterns, we can use computers to find simple, finite rules that govern them.

For the Fibonacci word: There is a simple checklist (the automaton) to tell you if any rectangle size is fair and balanced.
For other words: We can use the same tools to see if they are fair, and if not, exactly how unfair they get.

It turns a seemingly endless, chaotic pattern into a solvable puzzle with a clear "Yes" or "No" answer, thanks to the power of logic and computers.

1. Problem Statement

The paper investigates the balance properties of rectangular submatrices (word rectangles) derived from infinite sequences.

Context: Given an infinite sequence $(a_i)_{i \ge 0}$ over $\{0, 1\}$ , an infinite matrix $A$ is defined where $A_{k,\ell} = a_{k+\ell}$ . The $m \times n$ submatrix $A(i, m, n)$ starting at index $i$ represents a "window" of the sequence.
Definition of Balance: A pair of dimensions $(m, n)$ is considered balanced if the sum of entries $T(i, m, n)$ across all possible starting positions $i$ takes on at most two distinct values.
The Core Question: For specific infinite words (Fibonacci, Tribonacci, Thue–Morse), determine exactly which pairs of natural numbers $(m, n)$ result in balanced rectangles.
Background: Previous work by Anselmo et al. established that if $\max(m, n)$ is a Fibonacci number, the $m \times n$ Fibonacci rectangles are balanced. However, this condition is sufficient but not necessary (e.g., $(4,3)$ is balanced). The paper aims to provide a complete characterization.

2. Methodology

The authors employ automata theory and logical decidability as their primary methodology, utilizing the software tool Walnut.

Finite Automata Construction:
- For the Fibonacci word (a Sturmian word corresponding to the quadratic irrational $\gamma = (3-\sqrt{5})/2$ ), the authors utilize the Ostrowski $\alpha$ -numeration system (specifically the Zeckendorf representation).
- They establish a criterion (Lemma 1) stating that rectangles are balanced if and only if the sequence of differences $\Delta(i, m, n) = T(i+1, m, n) - T(i, m, n)$ does not contain specific patterns (blocks of $1, 0, \dots, 0, 1$ or $-1, 0, \dots, 0, -1$ ).
- Since the condition $x = \lfloor n\alpha \rfloor$ is expressible in first-order logic for quadratic irrationals, the balance criterion can be translated into a first-order formula.
- Using Walnut, this formula is converted into a finite automaton that accepts pairs $(m, n)$ (represented in Zeckendorf form) if and only if they are balanced.
Generalization to Other Words:
- Tribonacci Word: The authors adapt the approach using the Tribonacci numeration system. They construct automata to count occurrences of symbols $0, 1, 2$ in sub-rectangles and verify the 2-balance condition.
- Thue–Morse Word: Due to the specific symmetry of the Thue–Morse sequence ( $t_{2k} + t_{2k+1} = 1$ ), the authors use a pairing argument to bound the sums. They implement this using base-(-2) representation in Walnut to handle negative differences naturally, eventually converting the result to a standard base-2 automaton.
Linear Representations: For proving density and diversity results (Theorem 8), the authors use linear representations (triples of matrices/vectors) to compute exact values of $T(i, m, n)$ for specific sequences of $m$ and $n$ , verifying identities via Maple.

3. Key Contributions and Results

A. The Fibonacci Word

Complete Characterization: The authors construct a 15-state finite automaton (Figure 1) that accepts exactly the balanced pairs $(m, n)$ for the Fibonacci word. This proves that the set of balanced pairs is a regular language in the Zeckendorf numeration system.
Human-Readable Criteria: They derive Theorem 7, a non-automaton-based characterization of balanced pairs based on the Zeckendorf expansions of $m$ and $n$ (involving parity of indices and relative sizes of Fibonacci components).
Recovery of Previous Results: The automaton automatically verifies the theorem of Anselmo et al. (that if $\max(m, n)$ is a Fibonacci number, the pair is balanced).
Density and Diversity:
- Proposition 5: Establishes periodicity and symmetry properties of balanced pairs within Fibonacci intervals.
- Proposition 6: Proves that for any $m$ , there exists a $j \le F_{i+1}$ such that $(m, n+j)$ is balanced, establishing a lower bound on the density of balanced $n$ .
- Theorem 8 & Corollary 9: Proves that for $m=n=F_{3k/2}$ , the number of distinct values of $T(i, m, n)$ grows linearly with $k$ (specifically $\Theta(k)$ ), showing that the number of distinct sums is not bounded by a constant for all $m, n$ .

B. The Tribonacci Word

Theorem 10: Characterizes 2-balanced rectangles for the Tribonacci word (which uses symbols $\{0, 1, 2\}$ ${0, 1, 2}$ ):
- If $m=1$ , all $n$ are balanced.
- If $m=2$ , there exists a 77-state automaton accepting specific $n$ .
- If $m \ge 3$ , no $n$ exists such that the rectangles are 2-balanced.
The proof for $m \ge 3$ involves constructing specific counter-examples where the count of the symbol '2' differs by at least 3 between two rectangles.

C. The Thue–Morse Word

Theorem 11: Establishes that for any $m \times n$ rectangle, the balance (deviation from the mean sum $mn/2$) is bounded by 4. Specifically, $|2|A(i, m, n)|_1 - mn| \le 4$ .
Theorem 12: Constructs a 92-state automaton (in base 2) that determines the exact balance value (1, 2, 3, or 4) for any input $(m, n)$ $(m, n)$ .
- Note: This computation was massive, requiring 12834 CPU seconds and 100GB of RAM, with an intermediate automaton reaching over 32 million states.
Theorem 14: Proves that for $m, n \ge 3$ , the balance is exactly 3 if and only if both $m$ and $n$ are odd.

4. Significance

Algorithmic Number Theory: The paper demonstrates the power of automata-based decision procedures (specifically using Walnut) to solve complex combinatorial problems on infinite words. It shows that properties of Sturmian and other morphic words can be reduced to the existence of paths in finite automata.
Generalization: It moves beyond the specific case of Fibonacci numbers to a general framework applicable to any Sturmian word corresponding to a quadratic irrational, and extends the concept to non-binary words (Tribonacci) and different balance definitions (Thue–Morse).
Refutation of Intuition: The results show that while certain "nice" conditions (like Fibonacci dimensions) guarantee balance, the full set of balanced pairs is complex and requires automata for precise description. Furthermore, the number of distinct sums can grow linearly with the dimension, contradicting the idea that these sums are always tightly clustered.
Open Source Verification: All proofs are constructive and verified via code (Walnut and Maple), which is made publicly available, ensuring reproducibility and allowing for further exploration of similar problems.

In summary, the paper provides a definitive, algorithmic solution to the "balanced rectangle" problem for several fundamental infinite words, leveraging the deep connection between logical definability, numeration systems, and finite automata.