betaFeedback

WorksMathematics

On a counting conjecture for binary rich words

Abstract

Let R2(n)R_2(n) denote the number of binary rich words of length nn. We prove that lim sup⁡n→∞log⁡R2(n)nlog⁡n=∞\limsup_{n\to\infty}\frac{\log R_2(n)}{\sqrt{n}\log n}=\infty. Consequently, R2(n)R_2(n) is not O(nCn)O(n^{C\sqrt{n}}) for any fixed C>0C>0, disproving the conjectured upper bound O((n/g(n))n)O((n/g(n))^{\sqrt{n}}) with g(n)→∞g(n)\to\infty. The proof combines independent permutation families through an ordered concatenation construction and a binary gap encoding.

The result

Let R2(n)R_2(n) count rich words of length nn over {0,1}\{0,1\}. Guo, Shallit, and Shur [2 Conjecture 1] conjectured the bound

R2(n)=O((ng(n))n)(1)R_2(n)=O\left(\left(\frac{n}{g(n)}\right)^{\sqrt{n}}\right) \tag*{(1)}

for some positive g(n)⟶∞g(n)\longrightarrow\infty.

This formulation also appears in [4 Section 1]. Using run-length constructions, Guo, Shallit, and Shur [3] obtained a lower bound exponential in n\sqrt{n}.

Theorem 1. The binary rich-word counting function satisfies

lim sup⁡n→∞log⁡R2(n)nlog⁡n=∞.\limsup_{n\to\infty}\frac{\log R_2(n)}{\sqrt{n}\log n}=\infty.

Corollary 2. For every C>0C>0, R2(n)≠O(nCn)R_2(n)\ne O(n^{C\sqrt{n}}). In particular, (1) is false.

Proof. An eventual bound R2(n)≤KnCnR_2(n)\le Kn^{C\sqrt{n}} would give a limsup at most CC. Since g(n)≥1g(n)\ge1 eventually, (1) would imply such a bound with C=1C=1.

The construction starts with r!r! rich blocks of length O(r2)O(r^2). 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 O(jrj2)O(jr_j^2) for block jj, suggesting parameters rjr_j proportional to 1/j1/j. We implement this choice dyadically: 2t2^t blocks of parameter 2s2k−t2s2^{k-t} at level tt. Each level has length cost O(s24k)O(s^24^k) and contributes at least s2klog⁡ss2^k\log s to the logarithm of the count. Summing over k+1k+1 levels gives a lower bound of order k+1\sqrt{k+1} for the normalized logarithm, with s→∞s\to\infty first. All logarithms are natural.

Ordered concatenation

We use the standard facts that a word ww has at most ∣w∣+1|w|+1 distinct palindromic factors and that every factor of a rich word is rich [1 Proposition 2.1 and Corollary 2.5]. Write P(w)P(w) for the set of palindromic factors of ww, including ε\varepsilon, and D(w)=∣w∣+1−∣P(w)∣D(w)=|w|+1-|P(w)| for its palindromic defect. For a set SS of letters, let ∣w∣S|w|_S count the positions of ww carrying letters of SS, and put

IS(w)={p∈P(w):apb is a factor of w for some a,b∈S},I_S(w)=\{p\in P(w): apb\text{ is a factor of }w\text{ for some }a,b\in S\},
σS(w)=max⁡{∣w∣S−1,0}−∣IS(w)∣.\sigma_S(w)=\max\{|w|_S-1,0\}-|I_S(w)|.

The two endpoint letters need not coincide. We abbreviate I{b}I_{\{b\}} to IbI_b. If ww is rich and bb occurs in ww, then

∣Ib(w)∣=∣w∣b−1.(2)|I_b(w)| = |w|_b - 1. \tag*{(2)}

Each position carrying bb first introduces exactly one palindrome ending in bb; these are bb and the words bpbbpb with p∈Ib(w)p \in I_b(w) [1 proof of Proposition 2.7].

If all letters are marked and ∣w∣≥2|w| \ge2, then Ialph⁡(w)(w)I_{\operatorname{alph}(w)}(w) is the set of palindromes in ww with its first and last letters deleted. Thus σalph⁡(w)(w)=0\sigma_{\operatorname{alph}(w)}(w) = 0 for rich ww, also when ∣w∣≤1|w| \le1.

For a word d=a1⋯amd = a_1 \cdots a_m of nonnegative integers, define

G(d)=01a101a20⋯1am0,G(ε)=0.G(d) = 0 1^{a_1} 0 1^{a_2} 0 \cdots1^{a_m} 0,\qquad G(\varepsilon) = 0.

For nonempty dd, with M=max⁡iaiM = \max_i a_i and Sh={a:a≥h}S_h = \{a : a \ge h\}, one has

D(G(d))=D(d)+∑h=1MσSh(d).(3)D(G(d)) = D(d) + \sum_{h=1}^{M} \sigma_{S_h}(d). \tag*{(3)}

To see this, the nonempty zero-ended palindromes are exactly G(p)G(p), p∈P(d)p \in\mathcal{P}(d). The one-ended palindromes are 1,…,1M1,\ldots,1^M and 1hG(p)1h1^hG(p)1^h with p∈ISh(d)p \in I_{S_h}(d). Parsing at zeros makes these classes disjoint and exhaustive. Hence

∣P(G(d))∣=1+∣P(d)∣+M+∑h=1M∣ISh(d)∣.|\mathcal{P}(G(d))| = 1 + |\mathcal{P}(d)| + M + \sum_{h=1}^{M} |I_{S_h}(d)|.

Now use ∣G(d)∣=1+m+∑iai|G(d)| = 1 + m + \sum_i a_i and ∑h=1M∣d∣Sh=∑iai\sum_{h=1}^{M}|d|_{S_h} = \sum_i a_i.

Lemma 3. Let q≥1q \ge1 and let z1,…,zqz_1,\ldots,z_q be nonempty binary words ending in 11, with zj1z_j1 rich for every jj. Relabel 0,10,1 in zjz_j as 2j−2,2j−12j-2,2j-1, respectively, obtaining BjB_j. Then G(B1⋯Bq)G(B_1\cdots B_q) is rich.

Proof. Put d=B1⋯Bqd = B_1\cdots B_q. Each block is rich, and their alphabets are pairwise disjoint. No nonempty palindrome crosses a block boundary, so dd is rich. We show that every term in (3) vanishes.

At an even threshold h=2j−2h = 2j-2, the marked positions form the entire rich suffix Bj⋯BqB_j\cdots B_q, so the marked deficit is zero. At an odd threshold h=2j−1h = 2j-1, put U=BjU = B_j, b=2j−1b = 2j-1, and V=Bj+1⋯BqV = B_{j+1}\cdots B_q. Only bb is marked in UU, and all letters are marked in VV. If VV is empty, use (2). Otherwise, writing V−V^{-} for VV with its last letter deleted,

I{b}∪alph⁡(V)(UV)=Ib(Ub)∪P(V−).(4)I_{\{b\}\cup\operatorname{alph}(V)}(UV) = I_b(Ub) \cup\mathcal{P}(V^{-}). \tag*{(4)}

For an interior contained in UU, the first letter of VV can replace the auxiliary final bb in UbUb. For an interior contained in VV, the last letter of UU supplies a left endpoint. No nonempty palindrome crosses the disjoint-alphabet boundary. These observations give (4). Its two sets intersect only in ε\varepsilon, which belongs to both since UbUb ends in bbbb. As UbUb and V−V^{-} are rich, the union has ∣U∣b+∣V∣−1|U|_b + |V| - 1 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 r≥1r \ge1 there are r!r! distinct binary words zz ending in 11 such that z1z1 is rich and

∣z∣=Lr:=5r2+9r+42,∣z∣1=(r+1)2.(5)|z| = L_r := \frac{5r^2 + 9r + 4}{2},\qquad|z|_1 = (r+1)^2. \tag*{(5)}

Proof. For a permutation p=(p1,…,pr)p = (p_1,\ldots,p_r) of 1,…,r1,\ldots,r, put H=r+1H = r+1 and

Wp=01H∏i=1r(011pi011H)0r.W_p = 0 1^H \prod_{i=1}^{r}(0^1 1^{p_i} 0^1 1^H)0^r.

The following nonempty palindromic factors occur in WpW_p:

0t,0t1H0t1≤t≤r,0t1pi0t1≤i≤r,1≤t≤i,0t1H0i1pi0i1H0t1≤i≤r,1≤t≤max⁡{1,i−1},1t1≤t≤H,1t0i1t1≤i≤r,1≤t≤pi,1t0i1pi0i1t1≤i≤r,1≤t≤H.\begin{aligned} &0^t,\quad0^t1^H0^t && 1 \le t \le r,\\ &0^t1p_i0^t && 1 \le i \le r,\quad1 \le t \le i,\\ &0^t1^H0^i1p_i0^i1^H0^t && 1 \le i \le r,\quad1 \le t \le\max\{1,i-1\},\\ &1^t && 1 \le t \le H,\\ &1^t0^i1^t && 1 \le i \le r,\quad1 \le t \le p_i,\\ &1^t0^i1p_i0^i1^t && 1 \le i \le r,\quad1 \le t \le H. \end{aligned}

In the third row, the zero-run before the left 1H1^H has length 1 when i=1i=1 and i−1i-1 otherwise; the zero-run on the right is at least as long. This gives the stated range of tt. The run patterns, pi<Hp_i < H, and the distinct values pip_i distinguish all the listed words. Their total number is Lr=∣Wp∣L_r = |W_p|, so WpW_p is rich. Its longest zero-run has length rr; appending one zero adds the new palindrome 0r+10^{r+1}. Thus Wp0W_p0 is rich. The permutation is recoverable from the successive short one-runs, and ∣Wp∣0=(r+1)2|W_p|_0 = (r+1)^2. Taking zz to be the bitwise complement of WpW_p gives the assertion.

Proposition 5. For q≥1q \ge1 and positive integers r1,…,rqr_1,\ldots,r_q, define

N=1+∑j=1q((2j−1)Lrj+(rj+1)2).N = 1 + \sum_{j=1}^{q}\left((2j-1)L_{r_j}+(r_j+1)^2\right).

Then R2(N)≥∏j=1qrj!R_2(N) \ge\prod_{j=1}^{q} r_j!.

Proof. Choose the words in Lemma 4 independently and apply Lemma 3. A zero of block jj contributes 2j−12j-1 letters to the gap encoding, and a one contributes 2j2j, giving the stated common length. Parsing at zeros recovers the integer word; the value ⌊a/2⌋\lfloor a/2\rfloor identifies the block containing each integer aa. Thus every permutation is recoverable, and all outputs are distinct.

Proof of Theorem 1. Fix k≥0k \ge0. For integers s≥2s \ge2, take q=2k+1−1q = 2^{k+1}-1 and

rj=2s2k−t(2t≤j<2t+1,0≤t≤k),r_j = 2s2^{k-t}\qquad(2^t \le j < 2^{t+1},\quad0 \le t \le k),

and denote the length in Proposition 5 by Ns,kN_{s,k}. Since (2u)!≥su(2u)! \ge s^u for u≥su \ge s, that proposition gives

log⁡R2(Ns,k)≥(k+1)s2klog⁡s.(6)\log R_2(N_{s,k}) \ge(k+1)s2^k\log s. \tag*{(6)}

Also Lr≤9r2L_r \le9r^2 and (r+1)2≤4r2(r+1)^2 \le4r^2 for r≥1r \ge1. The 2t2^t blocks at level tt have total length contribution at most

2t(9⋅2t+2+4)(2s2k−t)2≤160s24k.2^t(9\cdot2^{t+2}+4)(2s2^{k-t})^2 \le160s^2 4^k.

The first block also gives Ns,k≥sN_{s,k} \ge s. Thus

s≤Ns,k≤200(k+1)s24k+1.(7)s \le N_{s,k} \le200(k+1)s^2 4^k+1. \tag*{(7)}

Letting s→∞s \to\infty at fixed kk in (6)--(7) gives

lim inf⁡s→∞log⁡R2(Ns,k)Ns,klog⁡Ns,k≥k+12200.\liminf_{s\to\infty}\frac{\log R_2(N_{s,k})}{\sqrt{N_{s,k}}\log N_{s,k}} \ge\frac{\sqrt{k+1}}{2\sqrt{200}}.

Since Ns,k→∞N_{s,k} \to\infty and kk 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. [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. [2]C. Guo, J. Shallit, and A. M. Shur, On the combinatorics of palindromes and antipalindromes, arXiv preprint arXiv:1503.09112v1 (2015).DOI
  3. [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. [4]J. Rukavicka, Subexponential upper bound on the number of rich words, arXiv preprint arXiv:2511.11069v3 (2026).arxiv.org/abs/2511.11069

Paper details

vlnc:W_ev9vncpx
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 23

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

GPT-6 Astra

View statement
Looking for related papers…
Contents