Improved Estimates for the Number of Privileged Words

Jeremy Nicholson and Narad Rampersad^{1} Department of Mathematics and Statistics University of Winnipeg 515 Portage Avenue Winnipeg, Manitoba R3B 2E9 Canada

                 jnich998@hotmail.com
               n.rampersad@uwinnipeg.ca

Abstract

In combinatorics on words, a word w of length n over an alphabet of size q is said to be privileged if n ≤ 1, or if n ≥ 2 and w has a privileged border that occurs exactly twice in w. Forsyth, Jayakumar and Shallit proved that there exist at least 2^{n−5}/n^{2} privileged binary words of length n. Using the work of Guibas and Odlyzko, we prove that there are constants c and n_{0} such that for n ≥ n_{0}, there are at least \frac{cq^{n}}{n(log_{q} n)^{2}} privileged words of length n over an alphabet of size q. Thus, for n sufficiently large, we improve the earlier bound determined by Forsyth, Jayakumar and Shallit, and generalize it for all q.

1 Introduction

The class of privileged words was recently introduced by Kellendonk, Lenz, and Savinien [6] and studied further by Peltomäki [7]. This is one of several classes, such as the classes of closed words and rich words, that are defined based on its members having borders satisfying certain properties. Recall that a border of a word w is a non-empty word that is both a prefix and a suffix of w. A word w is privileged if either

• w is a single letter, or

• w has a privileged border that occurs exactly twice in w.

The first few privileged words (up to length 4) over the alphabet {0, 1} are

ϵ, 0, 1, 00, 11, 000, 010, 101, 111, 0000, 0110, 1001, 1111.

Note that 0101 is not privileged because, although it has a border 01 that occurs exactly twice, this border is not itself privileged.

If one removes the condition requiring this border to be privileged from the above definition, one obtains the class of closed words studied by Fici [1]. Similarly, the class of rich words [3] can be obtained by the following definition: a word is rich if each of its closed factors whose longest border is a palindrome is itself a palindrome. For each of these classes of words, it is natural to try to count the number of words of each length in the class for a given alphabet size. For instance, Guo, Shallit, and Shur [5] gave a superpolynomial lower bound on the number of binary rich words, and Rukavicka [8] gave a subexponential upper bound (for any alphabet size).

Forsyth, Jayakumar, Peltomäki, and Shallit [2] looked at the problem of enumerating privileged words over a binary alphabet. The number of such words of length n is given by sequence \underline{A231208} of the Online Encyclopedia of Integer Sequences. This sequence begins

1, 2, 2, 4, 4, 8, 8, 16, 20, 40, 60, 108, …

Forsyth et al. proved that there exist at least 2^{n−5}/n^{2} privileged binary words of length n. In their paper they sketch a method for potentially improving this estimate. In the present paper we apply some results of Guibas and Odlyzko [4] on the size of prefix-synchronized codes to carry out this method. We are thus able to obtain the following asymptotic improvement to the result of Forsyth, Jayakumar, and Shallit, and also generalize the result to arbitrary alphabets; since every privileged word is closed, this also gives a lower bound on the number of closed words of length n.

Theorem 1. Let q ≥ 2. There exist constants c and n_{0} such that for n ≥ n_{0}, there are at least \frac{cq^{n}}{n(log_{q} n)^{2}} privileged words of length n over an alphabet of size q.

The estimates given in this theorem derive from the asymptotic analysis of maximal prefix-synchronized codes carried out by Guibas and Odlyzko [4]. Given an alphabet of size q, a block length N and a prefix P of length p < N, a prefix-synchronized code is a set of length-N codewords with the property that every codeword starts with a fixed prefix P = a_{1}a_{2} ⋯ a_{p}, and furthermore, for any codeword a_{1}a_{2} ⋯ a_{p}b_{1}b_{2} ⋯ b_{N−p}, the prefix P does not appear as a factor of a_{2} ⋯ a_{p}b_{1} ⋯ b_{N−p}a_{1} ⋯ a_{p−1}. In other words, the border a_{1}a_{2} ⋯ a_{p} of a_{1}a_{2} ⋯ a_{p}b_{1} ⋯ b_{N−p}a_{1}a_{2} ⋯ a_{p} occurs exactly twice in this word.

Next, we define G(N) = G_{P} (N) as the size of a maximal prefix-synchronized code with these parameters. In other words, G_{P} (N) is the number of q-ary words a_{1} ⋯ a_{N+p} such that a_{k} ⋯ a_{k+p−1} = P for k = 1 and k = N + 1, and for no other k with 1 ≤ k ≤ N + 1. If we take n = N + p where the prefix P of length p is a privileged word, then G_{P} (N) counts all words of length n with a privileged border P that occurs exactly twice in w. All these words are necessarily privileged words. If we sum up G_{P} (N) over all privileged P of length p for some p, then we obtain a lower bound for the number of privileged words of length n.

2 Proof of Theorem 1

To prove Theorem 1 we begin with some lemmas. In all the following lemmas and for the rest of this document, q is the size of the alphabet and it will be a fixed integer ≥ 2, p is the size of the prefix P, and Q = y_{1}y_{2} ⋯ y_{p} is the autocorrelation of P, defined as follows. If P = a_{1} ⋯ a_{p}, then for i = 1, …, p we define

y_{i} = \begin{cases}1, & if a_{i+1} ⋯ a_{p} = a_{1} ⋯ a_{p−i}; \\ 0, & otherwise. \end{cases}

We also define the polynomial

f(z) = f_{Q}(z) = ∑_{i=1}^{p} y_{i}z^{p−i}.

The next series of lemmas are Lemmas 3–6 of [4].

Lemma 2. If p is sufficiently large, then 1 + (z − q)f(z) has exactly one zero ρ that satisfies |ρ| ≥ 1.7.

Since there is only one such root ρ, it follows that this ρ is real. In what follows, the quantity ρ is the ρ specified by the previous lemma.

Lemma 3. If p is sufficiently large, then

ln ρ = ln q − \frac{1}{qf(q)} − \frac{f′(q)}{qf(q)^{3}} − \frac{1}{2q^{2}f(q)^{2}} + O (\frac{p^{2}}{q^{3p}} ) .

Define R_{Q} by

R_{Q}ρ = \frac{(q − ρ)^{2}ρ^{p−1}}{1 − (q − ρ)^{2}f′(ρ)}.

Lemma 4. G(N) = R_{Q}ρ^{N} + O((1.7)^{N})

Lemma 5. If p is sufficiently large, then

ln R_{Q} = (p − 2) ln q − 2 ln(f(q)) + \frac{3f′(q)}{f(q)^{2}} − \frac{p − 2}{qf(q)} + O (\frac{p^{2}}{q^{2p}} ) .

In what follows, c’s, d’s and Greek letters denote positive constants.

Lemma 6. Let p be the unique integer such that

\frac{ln q}{q − 1}q^{p} ≤ N < \frac{ln q}{q − 1}q^{p+1}.

Let P be a prefix of length p and let n = N + p. There exist constants N_{0} and d such that for N > N_{0} we have

G_{P} (N) ≥ dq^{n}/n^{2}.

(The constant d may depend on q but not on N.)

Proof. If p = ⌊log_{q} N +log_{q}(q −1)−log_{q}(ln q)⌋, then G(N) = R_{Q}ρ^{N} +O((1.7)^{N}) by applying Lemma 4. By Lemmas 3 and 5 we have

ln(R_{Q}ρ^{N}) = ln R_{Q} + N ln ρ
= (p − 2) ln q − 2 ln(f(q)) + \frac{3f′(q)}{f(q)^{2}} − \frac{p − 2}{qf(q)} + O (\frac{p^{2}}{q^{2p}} )
+ N ln q − \frac{N}{qf(q)} − \frac{Nf′(q)}{qf(q)^{3}} − \frac{N}{2q^{2}f(q)^{2}} + O (\frac{Np^{2}}{q^{3p}} ) .

Therefore,

G(N) = R_{Q}ρ^{N} + O((1.7)^{N}) = exp(ln(R_{Q}ρ^{N})) + O((1.7)^{N})
= \frac{q^{N+p−2}}{f(q)^{2}} exp (\frac{3f′(q)}{f(q)^{2}} − \frac{p − 2}{qf(q)} − \frac{N}{qf(q)} − \frac{Nf′(q)}{qf(q)^{3}} − \frac{N}{2q^{2}f(q)^{2}} + O (\frac{Np^{2}}{q^{3p}} + \frac{p^{2}}{q^{2p}} ))
+ O((1.7)^{N}).

Since the first digit of Q will always be a 1, f(q) will have the leading term q^{p−1}. Let α, β, γ, δ, and N_{0} be positive constants such that the following inequalities are valid for all N ≥ N_{0}.

0 ≤ \frac{3f′(q)}{f(q)^{2}} ≤ 3\frac{(p − 1)^{2}q^{p−2}}{q^{2p−2}} ≤ \frac{3(p − 1)^{2}}{q^{p}} ≤ 2

\frac{p − 2}{qf(q)} ≤ \frac{p − 2}{q^{p}} ≤ \frac{p}{q^{p}} ≤ 1/q

\frac{N}{qf(q)} ≤ \frac{N}{q^{p}} ≤ \frac{N}{q^{⌊log_{q} N−log_{q}(ln q)⌋}} ≤ α\frac{N}{q^{log_{q} N−log_{q}(ln q)}} ≤ α\frac{N ln q}{N} ≤ β

\frac{Nf′(q)}{qf(q)^{3}} ≤ \frac{N(p − 1)^{2}q^{p−2}}{q^{3p−2}} ≤ \frac{N(p − 1)^{2}}{q^{2p}} ≤ \frac{N}{q^{p}} \frac{(p − 1)^{2}}{q^{p}} ≤ 2β

\frac{N}{2q^{2}f(q)^{2}} ≤ \frac{N}{2q^{2p}} ≤ \frac{N}{2q^{2⌊log_{q} N−log_{q}(ln q)⌋}} ≤ \frac{δN}{q^{2 log_{q} N}} ≤ \frac{δN}{N^{2}} ≤ δ

|O (\frac{Np^{2}}{q^{3p}} + \frac{p^{2}}{q^{2p}} )| = |O (\frac{p^{2}}{q^{2p}} )| ≤ γ.

Thus

G_{P} (N) = \frac{q^{N+p−2}}{f(q)^{2}} exp (\frac{3f′(q)}{f(q)^{2}} − \frac{p − 2}{qf(q)} − \frac{N}{qf(q)} − \frac{Nf′(q)}{qf(q)^{3}} − \frac{N}{2q^{2}f(q)^{2}} + O (\frac{Np^{2}}{q^{3p}} + \frac{p^{2}}{q^{2p}} ))
+ O((1.7)^{N})
≥ \frac{d_{1}q^{N+p−2}}{f(q)^{2}} ≥ \frac{d_{1}q^{N+p−2}}{((1 − q^{p})/(1 − q))^{2}} ≥ \frac{d_{2}q^{N+p−2}}{(1 − q^{p})^{2}} ≥ \frac{d_{2}q^{N+p−2}}{q^{2p} − 2q^{p} + 1}
≥ \frac{d_{2}q^{N+p−2}}{q^{2p} + 1} ≥ \frac{d_{2}q^{N+p−2}}{2q^{2p}} ≥ \frac{d_{3}q^{N}}{q^{p}} ≥ \frac{d_{3}q^{N}}{q^{⌊log_{q} N+log_{q}(q−1)−log_{q}(ln q)⌋}}
≥ \frac{d_{3}q^{N}}{q^{log_{q} N+log_{q}(q−1)−log_{q}(ln q)}} ≥ \frac{d_{3}q^{N} ln q}{N(q − 1)} ≥ \frac{d_{4}q^{N}}{N} ≥ \frac{d_{4}q^{n−p}}{n}
≥ \frac{d_{4}q^{n−(log_{q} N+log_{q}(q−1)−log_{q}(ln q))}}{n} ≥ \frac{d_{4}q^{n} ln q}{nN(q − 1)} ≥ \frac{dq^{n}}{n^{2}} .

We can now complete the proof of Theorem 1.

Proof of Theorem 1. We define the function B(n, q) as the number of privileged words of length n over an alphabet of size q ≥ 2. Let n = N+p where p = ⌊log_{q} N + log_{q}(q − 1) − log_{q}(ln q)⌋. Let n_{0} be a constant such that whenever n ≥ n_{0} we have p ≥ N_{0}, where N_{0} is the constant mentioned in Lemma 6. Then for n ≥ n_{0}, we have

B(n, q) ≥ ∑_{P privileged ; |P |=p} G_{P} (N)

≥ (\frac{dq^{n}}{n^{2}} ) B(⌊log_{q} N + log_{q}(q − 1) − log_{q}(ln q)⌋, q)
≥ (\frac{dq^{n}}{n^{2}} ) (\frac{c_{1}q^{⌊log_{q} N+log_{q}(q−1)−log_{q}(ln q)⌋}}{(⌊log_{q} N + log_{q}(q − 1) − log_{q}(ln q)⌋)^{2}} )
≥ (\frac{c_{2}q^{n}}{n^{2}} ) (\frac{q^{log_{q} N+log_{q}(q−1)−log_{q}(ln q)}}{(log_{q} N + log_{q}(q − 1) − log_{q}(ln q))^{2}} )
≥ (\frac{c_{2}q^{n}}{n^{2}} ) (\frac{N(q − 1)}{(ln q)(1 + log_{q} N)^{2}} )
≥ (\frac{c_{3}q^{n}}{n^{2}} ) (\frac{N}{(log_{q} q + log_{q} N)^{2}} )

≥ (\frac{c_{3}q^{n}}{n^{2}} ) (\frac{N}{(log_{q} qN)^{2}} )
≥ (\frac{c_{3}q^{n}}{n^{2}} ) (\frac{n}{(log_{q} qn)^{2}} − \frac{p}{(log_{q} qn)^{2}} )
≥ (\frac{c_{3}q^{n}}{n^{2}} ) (\frac{n}{(log_{q} qn)^{2}} − \frac{log_{q} n}{(log_{q} qn)^{2}} − \frac{1}{(log_{q} qn)^{2}} )
≥ (\frac{c_{3}q^{n}}{n(log_{q} n)^{2}} ) (\frac{(log_{q} n)^{2}}{(log_{q} qn)^{2}} − \frac{(log_{q} n)^{3}}{n(log_{q} qn)^{2}} − \frac{(log_{q} n)^{2}}{n(log_{q} qn)^{2}} )
≥ \frac{cq^{n}}{n(log_{q} n)^{2}} ,

since

\frac{(log_{q} n)^{2}}{(log_{q} qn)^{2}} − \frac{(log_{q} n)^{3}}{n(log_{q} qn)^{2}} − \frac{(log_{q} n)^{2}}{n(log_{q} qn)^{2}}

is positive and increases for n > 2. This completes the proof.

References

[1] G. Fici, Open and closed words, Bull. Europ. Assoc. Theoret. Comput. Sci. 123 (2017).

   Available at http://bulletin.eatcs.org/index.php/beatcs/article/view/508 .

[2] M. Forsyth, A. Jayakumar, J. Peltomäki, and J. Shallit, Remarks on privileged words, Int. J. Found. Comput. Sci. 27 (2016), 431–442.

[3] A. Glen, J. Justin, S. Widmer, and L. Zamboni, Palindromic richness, European J. Combin. 30 (2009), 510–531.

[4] L. Guibas and A. Odlyzko, Maximal prefix-synchronized codes, SIAM J. Appl. Math. 35 (1978), 401–418.

[5] C. Guo, J. Shallit, and A. M. Shur, Palindromic rich words and run-length encodings, Inform. Process. Lett. 116 (2016), 735–738.

[6] J. Kellendonk, D. Lenz, and J. Savinien, A characterization of subshifts with bounded powers, Discrete Math. 313 (2013), 2881–2894.

[7] J. Peltomäki, Introducing privileged words: Privileged complexity of Sturmian words, Theoret. Comput. Sci. 500 (2013), 57–67.

[8] J. Rukavicka, On the number of rich words, in Developments in Language Theory: Proc. DLT 2017, Lect. Notes in Comp. Sci., Vol. 10396, Springer, 2017, pp. 345–352.

2010 Mathematics Subject Classification: Primary 68R15. Keywords: privileged word, rich word, closed word, border, enumeration.

(Concerned with sequence \underline{A231208}.)

Received January 23 2018; revised version received May 2 2018. Published in Journal of Integer Sequences, May 7 2018.

Return to Journal of Integer Sequences home page.