WorksMathematics
On a counting conjecture for binary rich words
Abstract
Let denote the number of binary rich words of length . We prove that . Consequently, is not for any fixed , disproving the conjectured upper bound with . The proof combines independent permutation families through an ordered concatenation construction and a binary gap encoding.
The result
Let count rich words of length over . Guo, Shallit, and Shur [2 Conjecture 1] conjectured the bound
for some positive .
This formulation also appears in [4 Section 1]. Using run-length constructions, Guo, Shallit, and Shur [3] obtained a lower bound exponential in .
Theorem 1. The binary rich-word counting function satisfies
Corollary 2. For every , . In particular, (1) is false.
Proof. An eventual bound would give a limsup at most . Since eventually, (1) would imply such a bound with .
The construction starts with rich blocks of length . To multiply the choices, we place successive blocks on disjoint ordered pairs of letters and then encode the resulting word by binary gaps. The encoding charges for block , suggesting parameters proportional to . We implement this choice dyadically: blocks of parameter at level . Each level has length cost and contributes at least to the logarithm of the count. Summing over levels gives a lower bound of order for the normalized logarithm, with first. All logarithms are natural.
Ordered concatenation
We use the standard facts that a word has at most distinct palindromic factors and that every factor of a rich word is rich [1 Proposition 2.1 and Corollary 2.5]. Write for the set of palindromic factors of , including , and for its palindromic defect. For a set of letters, let count the positions of carrying letters of , and put
The two endpoint letters need not coincide. We abbreviate to . If is rich and occurs in , then
Each position carrying first introduces exactly one palindrome ending in ; these are and the words with [1 proof of Proposition 2.7].
If all letters are marked and , then is the set of palindromes in with its first and last letters deleted. Thus for rich , also when .
For a word of nonnegative integers, define
For nonempty , with and , one has
To see this, the nonempty zero-ended palindromes are exactly , . The one-ended palindromes are and with . Parsing at zeros makes these classes disjoint and exhaustive. Hence
Now use and .
Lemma 3. Let and let be nonempty binary words ending in , with rich for every . Relabel in as , respectively, obtaining . Then is rich.
Proof. Put . Each block is rich, and their alphabets are pairwise disjoint. No nonempty palindrome crosses a block boundary, so is rich. We show that every term in (3) vanishes.
At an even threshold , the marked positions form the entire rich suffix , so the marked deficit is zero. At an odd threshold , put , , and . Only is marked in , and all letters are marked in . If is empty, use (2). Otherwise, writing for with its last letter deleted,
For an interior contained in , the first letter of can replace the auxiliary final in . For an interior contained in , the last letter of supplies a left endpoint. No nonempty palindrome crosses the disjoint-alphabet boundary. These observations give (4). Its two sets intersect only in , which belongs to both since ends in . As and are rich, the union has elements. The marked deficit is therefore zero. Earlier blocks contain no marked positions and do not affect these interiors. (3) completes the proof.
A product lower bound
Lemma 4. For each there are distinct binary words ending in such that is rich and
Proof. For a permutation of , put and
The following nonempty palindromic factors occur in :
In the third row, the zero-run before the left has length 1 when and otherwise; the zero-run on the right is at least as long. This gives the stated range of . The run patterns, , and the distinct values distinguish all the listed words. Their total number is , so is rich. Its longest zero-run has length ; appending one zero adds the new palindrome . Thus is rich. The permutation is recoverable from the successive short one-runs, and . Taking to be the bitwise complement of gives the assertion.
Proposition 5. For and positive integers , define
Then .
Proof. Choose the words in Lemma 4 independently and apply Lemma 3. A zero of block contributes letters to the gap encoding, and a one contributes , giving the stated common length. Parsing at zeros recovers the integer word; the value identifies the block containing each integer . Thus every permutation is recoverable, and all outputs are distinct.
Proof of Theorem 1. Fix . For integers , take and
and denote the length in Proposition 5 by . Since for , that proposition gives
Also and for . The blocks at level have total length contribution at most
The first block also gives . Thus
Letting at fixed in (6)--(7) gives
Since and is arbitrary, the theorem follows.
Formal verification. Theorem 1 and the negation of (1) have also been formalized in Lean 4 using Mathlib. The formal proof uses the product construction and explicit integer bounds for the scaled profiles above. The formalization and paper source are available at https://github.com/glasss13/rich-word-counting.
Acknowledgment. GPT-6 Astra (OpenAI) was used for the main proof construction and drafting of this paper.
References
- [1]A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni, Palindromic richness, European Journal of Combinatorics 30(2) (2009), 510–531. doi:10.1016/j.ejc.2008.04.006.DOI
- [2]C. Guo, J. Shallit, and A. M. Shur, On the combinatorics of palindromes and antipalindromes, arXiv preprint arXiv:1503.09112v1 (2015).DOI
- [3]C. Guo, J. Shallit, and A. M. Shur, Palindromic rich words and run-length encodings, Information Processing Letters 116(12) (2016), 735–738. doi:10.1016/j.ipl.2016.07.001.DOI
- [4]J. Rukavicka, Subexponential upper bound on the number of rich words, arXiv preprint arXiv:2511.11069v3 (2026).arxiv.org/abs/2511.11069