On Number of Rich Words
Josef Rukavicka

On Lattice Calculation of Electric Dipole Moments and Form Factors of the Nucleon
    [
    18 november 2016
=================================================================================





Any finite word w of length n contains at most n+1 distinct palindromic factors. If the bound  n+1 is reached, the word w is called rich. 
The number of rich words of length n over an alphabet of cardinality q is denoted R_n(q).   For binary alphabet,  Rubinchik and Shur deduced  that  R_n(2)≤ c 1.605^n for some constant c. 
We prove that lim_n→∞√(R_n(q))=1 for any q, i.e. R_n(q) has  a subexponential
growth on any alphabet. 







§ INTRODUCTION

The study of palindromes is a frequent topic and many diverse results may be found.
In recent years, some of the papers deal with so-called rich words, or also words having palindromic defect 0.
They are words that have the maximum number of palindromic factors.
As noted by <cit.>, a finite word w can contains at most |w|+1 distinct palindromic factors with |w| being the length of w.
The rich words are exactly those that attain this bound. It is known that on binary alphabet the set of rich words contains factors of Sturmian words, factors of complementary symmetric Rote words, factors of the period-doubling word, etc., see <cit.>. On multiliteral alphabet, the set of rich words contains for example factors of Arnoux–Rauzy words and factors of words coding symmetric interval exchange.   


Rich words can be characterized using various properties, see for instance <cit.>.
The concept of rich words can also be generalized to respect so-called pseudopalindromes, see <cit.>.
In this paper we focus on an unsolved question of computing the number of rich words of length n over an alphabet with q>1 letters. This number is denoted  R_n(q). 

This question is investigated in <cit.>, where J. Vesti gives a recursive lower bound on the number of rich words of length n, and an upper bound on the number of binary rich words.
Both these estimates seem to be very rough.
In <cit.>,  C. Guo, J. Shallit and A.M. Shur  constructed for each n  a large set of rich words of length n. Their construction gives,  currently,  the best lower bound on the number of binary rich words, namely 
R_n(2)≥C^√(n)/p(n), 
 where p(n) is a polynomial and the constant C ≈ 37. On the other hand, the best known upper bound is exponential.  As mentioned in <cit.>,  calculation performed recently by M. Rubinchik provides the upper bound  R_n(2)≤ c 1.605^n for some constant c, see <cit.>.

Our main result stated as Theorem  <ref> shows that R_n(q) has  a subexponential
growth on any alphabet.  More precisely,   we prove  

    lim_n→∞√(R_n(q))=1 .

In <cit.>, Shur calls languages with the above property small.
Our result  is   an argument in favor of a conjecture formulated in <cit.>  saying that  for some infinitely growing function g(n) the following holds true  R_n(2) = 𝒪(n/g(n))^√(n) . 


To derive our result we consider a specific factorization of  a rich word into distinct rich palindromes, here called UPS-factorization (Unioccurrent Palindromic Suffix factorization),  see Definition  <ref>.  
Let us mention that  another palindromic factorizations have already been studied, see <cit.>: Minimal (minimal number of palindromes), maximal (every palindrome cannot be extended on the given position) and diverse (all palindromes are distinct). Note that only the minimal palindromic factorization has to exist for every word.

The article is organized as follows: Section <ref> recalls notation and known results. In Section <ref> we study a relevant property of  UPS-factorization. The last section is devoted to the proof of our main result. 





§ PRELIMINARIES

Let us start with a couple of definitions:
Let A be an alphabet of q letters, where q>1 and q∈ℕ (ℕ denotes the set of nonnegative integers).
A finite sequence u_1u_2⋯ u_n with u_i ∈ A is a finite word.
Its length is n and is denoted |u_1u_2⋯ u_n| = n.
Let A^n denote the set of words of length n. We define that A^0 contains just the empty word.
It is clear that the size of A^n is equal to q^n. 

Given u=u_1u_2⋯ u_n ∈ A^n and v=v_1v_2⋯ v_k ∈ A^k with 0≤ k ≤ n, we say that v is a factor of u if there exists i such that 0<i, i+k ≤ n and u_i=v_1, u_i+1=v_2, …, u_i+k-1=v_k.
 

A word u=u_1u_2⋯ u_n is called a palindrome if u_1u_2⋯ u_n=u_nu_n-1⋯ u_1. The empty word is considered to be a palindrome and a factor of any word.

A word u of length n  is called rich if u has n+1 distinct  palindromic factors. Clearly,  u=u_1u_2⋯ u_n  is rich if and only if its reversal u_nu_n-1⋯ u_1 is rich as well. 


Any factor of a rich word is rich as well, see <cit.>. In other words,  the language of rich words is factorial. In particular it means that 
R_n(q)R_m(q)≤ R_n+m(q) for any m, n, q ∈ℕ. Therefore,  the Fekete's lemma  implies existence of the limit of  √(R_n(q)) and moreover 

    lim_n→∞√(R_n(q))= inf{√(R_n(q)) n ∈ℕ}.

For a fixed n_0,   one can find the number of all rich words of length n_0 and obtain an upper bound on the limit. 
Using computer Rubinchik counted R_n(2) for n≤ 60, (see the sequence A216264 in OEIS). As  √(R_60(2)) < 1.605, he obtained the  upper bound given in Introduction. 



As shown in <cit.>,  any rich word u over alphabet A is richly prolongable, i.e., there exist  letters a, b ∈ A such that aub is also rich. Thus a rich word is a factor of an arbitrarily long rich word.  But the question whether two  rich words  can appear simultaneously as factors of a longer rich word may have  negative answer. It means that  the language of rich words is not recurrent.  This fact makes enumeration  of rich words hard. 








§ FACTORIZATION OF RICH WORDS INTO RICH PALINDROMES

Let us recall one important property of rich words <cit.>: the longest palindromic suffix of a rich word w has exactly one occurrence in w (we say that the longest palindromic suffix of w is unioccurrent in w).
It implies that w=w^(1)w_1, where w_1 is a palindrome which is not a factor of w^(1). Since every factor of a rich word is a rich word as well, it follows that  w^(1) is a rich word and thus w^(1)=w^(2)w_2, where w_2 is a palindrome which is not a factor of w^(2).  Obviously w_1≠w_2.  We can repeat the process until w^(p) is the empty word for some p∈ℕ, p≥ 1. We express these ideas by the following lemma:



Let w be a rich word. There exist distinct non-empty palindromes w_1,w_2,…,w_p such that

    w=w_pw_p-1⋯ w_2w_1
     w_i 
     w_pw_p-1⋯ w_i i=1,2,… ,p.



We define UPS-factorization (Unioccurrent Palindromic Suffix factorization) to be the factorization of a rich word w into the form (<ref>).

Since w_i in the factorization (<ref>) are non-empty, it is clear that p≤ n=| w|. From the fact that the palindromes w_i in  the factorization (<ref>) are distinct we can derive a better upper bound for p. The aim of this section is to prove the following theorem:



There is a constant c>1 such that for any rich word w of length n the number of palindromes in the UPS-factorization of w=w_pw_p-1⋯ w_2w_1 satisfies 

    p≤ cn/lnn


Before proving the theorem, we show two auxiliary lemmas:


Let q,n,t∈ℕ such that

    ∑_i=1^tiq^⌈i/2⌉≥ n
 The number p of palindromes in the UPS-factorization w=w_pw_p-1… w_2w_1 of any rich word w with n=| w| satisfies

    p≤∑_i=1^tq^⌈i/2⌉



Let f_1,f_2,f_3,… be an infinite sequence of all non-empty palindromes over an alphabet A with q=| A| letters, where the palindromes are ordered in such a way that i<j implies that | f_i|≤| f_j|.
In consequence f_1,…,f_q are palindromes of length 1, f_q+1, …,f_2q are palindromes of length 2, etc.

Since w_1,…,w_p are distinct non-empty palindromes we have ∑_i=1^p| f_i|≤∑_i=1^p| w_i|=n.
The number of palindromes of length i over the alphabet A with q letters is equal to q^⌈i/2⌉ (just consider that that the “first half” of a palindrome determines the second half).
The number ∑_i=1^tiq^⌈i/2⌉ equals the length of a word concatenated from all palindromes of length less than or equal to t.
Since ∑_i=1^p | f_i|≤ n ≤∑_i=1^tiq^⌈i/2⌉, it follows that the number of palindromes p is less than or equal to the number of all palindromes of length at most t; this explains the inequality (<ref>).



Let N∈ℕ, x∈ℝ, x>1 such that N(x-1)≥ 2. We have

    N x^N/2(x-1)≤∑_i=1^Nix^i-1≤N x^N/(x-1)



The sum of the first N terms of a geometric series with the quotient x is equal to ∑_i=1^Nx^i=x^N+1-x/x-1. Taking the derivative of this formula with respect to x with x>1 we obtain:
∑_i=1^Nix^i-1=x^N(N(x-1)-1)+1/(x-1)^2=N x^N/x-1+1-x^N/(x-1)^2.
It follows that the right inequality of (<ref>) holds for all N∈ℕ and x>1. The condition N(x-1)≥ 2 implies that 1/2N(x-1)≤ N(x-1)-1, which explains the left inequality of (<ref>).

We can start the proof of Theorem <ref>:

Let t∈ℕ be a minimal nonnegative integer such that the inequality (<ref>) in Lemma <ref> holds. It means that:

    n>∑_i=1^t-1iq^⌈i/2⌉≥∑_i=1^t-1iq^i/2=q^1/2∑_i=1^t-1iq^i-1/2≥(t-1)q^t/2/2(q^1/2-1)

where for the last inequality we exploited (<ref>) with N=t-1 and x=q^1/2. If q≥ 9, then the condition N(x-1)=(t-1)(q^1/2-1)≥ 2 is fulfilled (it is the condition from Lemma <ref>) for any t≥ 2. Hence let us suppose that q≥ 9 and t≥ 2. From (<ref>) we obtain:

    q^t/2/q^1/2-1≤2n/t-1≤4n/t

Since t is such that the inequality (<ref>) holds and i≤ q^i+1/2 for any i∈ℕ and q≥ 2, we can write:

    n≤∑_i=1^t iq^i+1/2≤∑_i=1^t q^i+1=q^2q^t-1/q-1≤q^2/q-1q^t≤ q^2t

We apply a logarithm on the previous inequality:

    lnn≤ 2tlnq

An upper bound for the number of palindromes p in UPS-factorization follows from (<ref>), (<ref>), and (<ref>):

    p≤∑_i=1^tq^⌈i/2⌉≤∑_i=1^tq^i+1/2≤ q^3/2q^t/2/q^1/2-1≤ q^3/24n/t≤ q^3/28lnqn/lnn

The previous inequality supposes that q≥ 9 and t≥ 2. If t=1 then we can easily derive from (<ref>) that n≤ q and consequently p≤ n≤ q. Thus the inequality p≤ q^3/28lnqn/lnn holds as well for this case.
Since every rich word over an alphabet with the cardinality q<9 is also a rich word over the alphabet with the cardinality 9, the estimate (<ref>) in Theorem <ref> holds if we set the constant c as follows: c=max{8q^3/2lnq, 8 · 9^3/2ln9}.



Theorem <ref> implies that average length of a palindrome of UPS-factorization of a rich word of length n is 𝒪(ln(n)).
Note that in <cit.> it is shown that most of palindromic factors of a random word of length n are of length close to ln(n).




§ RICH WORDS FORM A SMALL LANGUAGE

The aim of this section is to show that the set of rich words forms a small language, see Theorem <ref>. 


We present a recurrent inequality for R_n(q). To ease our notation we omit the specification of the cardinality of alphabet and write 
R_n instead of R_n(q).

Denote κ_n= ⌈ cn/lnn⌉, where c is the constant from Theorem <ref> and n≥ 2.



Let n≥ 2, then

    R_n≤∑_p=1^κ_n∑_n_1+n_2+… +n_p=n 
     n_1,n_2,…, n_p≥ 1R_⌈n_1/2⌉R_⌈n_2/2⌉… R_⌈n_p/2⌉



Given p,n_1,n_2,…,n_p, let R(n_1,n_2,…, n_p) denote the number of rich words with UPS-factorization w=w_pw_p-1… w_1, where | w_i|=n_i for i=1,2,…,p.
Note that any palindrome w_i is uniquely determined by its prefix of length ⌈n_i/2⌉; obviously this prefix is rich. Hence the number of words that appears in UPS-factorization as w_i cannot be larger than R_⌈n_i/2⌉. It follows that R(n_p,n_p-1,…, n_1)≤ R_⌈n_1/2⌉R_⌈n_2/2⌉… R_⌈n_p/2⌉. The sum of this result over all possible p (see Theorem <ref>) and n_1,n_2,…,n_p completes the proof.




If h>1,K≥ 1 such that R_n≤ Kh^n for all n, then lim_n→∞√(R_n)≤√(h).


For any integers p,n_1,…,n_p≥ 1, the assumption implies  that

R_⌈n_1/2⌉R_⌈n_2/2⌉… R_⌈n_p/2⌉≤ K^ph^n_1+1/2h^n_2+1/2… h^n_p+1/2≤ K^ph^n+p/2.
Exploiting (<ref>) we obtain:

    R_n≤ K^κ_nh^n+κ_n/2∑_p=1^κ_n∑_n_1+n_2+… +n_p=n 
     n_1,n_2,…, n_p≥ 1 1

The sum 
    S_n=∑_n_1+n_2+… +n_p=n 
     n_1,n_2,…, n_p≥ 11
 can be interpreted as the number of ways how to distribute n coins between p people in such a way that everyone has at least one coin. That is why S_n=n-1p-1.

It is known (see Appendix for the proof) that

    ∑_i=0^LNi≤(eN/L)^LL,N∈ℕ L≤ N

From (<ref>) we can write:
R_n≤ K^κ_nh^n+κ_n/2enκ_n^κ_n. To evaluate √(R_n), just recall that lim_n→∞(const)^κ_n/n=lim_n→∞(const)^c/lnn=1 for any constant const and moreover lim_n→∞(n/κ_n)^κ_n/n=lim_n→∞(clnn)^1/clnn=1.


The main theorem of this paper is a simple consequence of the previous proposition.


Let R_n denote the number of rich words of length n over an alphabet with q letters.
We have lim_n→∞√(R_n)=1.


Let us suppose that lim_n→∞√(R_n)=λ>1. We are going to find ϵ>0 such that λ+ϵ<λ^2. The definition of a limit implies that there is n_0 such that √(R_n)<λ+ϵ for any n>n_0, i.e. R_n<(λ+ϵ)^n. Let K=max{R_1,R_2,…,R_n_0}. It holds for any n∈ℕ that R_n≤ K(λ+ϵ)^n. Using Proposition <ref> we obtain lim_n→∞√(R_n)≤√(λ+ϵ)<λ, and this is a contradiction to our assumption that lim_n→∞√(R_n)=λ>1.





§ APPENDIX

For the reader's convenience, we provide a proof of the well-known inequality we used the proof of Proposition <ref>.

∑_k=0^LNk≤(eN/L)^L, where L≤ N and L,N∈ℕ.


Consider x∈ (0,1]. The binomial theorem states that 
    (1+x)^N=∑_k=0^NNkx^k≥∑_k=0^LNkx^k

By dividing by the factor x^L we obtain

    ∑_k=0^LNkx^k-L≤(1+x)^N/x^L

Since x∈ (0,1] and k-L≤ 0, then x^k-L≥ 1, it follows that

    ∑_k=0^LNk≤(1+x)^N/x^L

Let us substitute x=L/N∈ (0,1] and let us exploit the inequality 1+x<e^x, that holds for all x>0:

    (1+x)^N/x^L≤e^xN/x^L=e^L/NN/(L/N)^L=(eN/L)^L






§ ACKNOWLEDGMENTS


The author wishes to thank Edita Pelantová and Štěpán Starosta for their useful comments. 
The authors acknowledges support by the Czech Science
Foundation grant GAČR 13-03538S and by the Grant Agency of the Czech Technical University in Prague, grant No. SGS14/205/OHK4/3T/14.


siam
biblio.bib

