ON TWO CONJECTURES DUE TO RAUZY

AND TO SHALLIT FOR INFINITE SEQUENCES

Jean-Paul Allouche and Mireille Bousquet-Mélou

Abstract. We show a connection between a recent conjecture of Shallit and an older conjecture of Rauzy. More precisely we correct a misprint in Rauzy’s conjecture and we show that a Rauzy-like conjecture is equivalent to Shallit’s.

In a paper of Shallit and Breitbart (see [8], see also [6]) Shallit proposed a conjecture on the finite factors (subwords) of the non-ultimately periodic infinite sequences on an infinite alphabet: a function S is defined (see below) and the conjecture reads

lim inf_{n→+∞} \frac{S(n)}{n} ≤ C,

where C = \frac{3−\sqrt{5}}{2}. Furthermore the conjecture is proved optimal (if it is true) by considering the Fibonacci sequence

0 1 0 0 1 0 1 0 0 1 ⋯

which is the fixed point of the morphism 0 → 01, 1 → 0.

Looking at this conjecture we remembered a conjecture in a paper of Rauzy [7] on the recurrence function R of a non-ultimately periodic primitive infinite sequence on a finite alphabet (the precise definition of R is given below). Rauzy’s conjecture is that, for such a sequence,

lim sup_{n→+∞} \frac{R(n)}{n} ≥ D,

where D = \frac{3+\sqrt{5}}{2}. This constant is also said optimal if the conjecture is true by considering the Fibonacci word (but there is a misprint, D is not optimal as we shall see below).

Of course the number \sqrt{5} often enters the picture when studying infinite words on a finite alphabet, because the Fibonacci sequence which has many “optimal” properties is related to the golden ratio. But we were intrigued by these two conjectures (note in particular that CD = 1) and we tried to find a link between them.

We first defined a function R′ resembling the recurrence function R of a sequence. In particular we noticed that Rauzy’s conjecture (as stated with the constant D) implies the following Rauzy-like conjecture:

lim sup_{n→+∞} \frac{R′(n)}{n} ≥ D.

Then we proved that this Rauzy-like conjecture is equivalent to Shallit’s. Hence we thought we had a proof that Shallit’s conjecture was a consequence of Rauzy’s.

But checking Rauzy’s paper we asked him about a non-published paper of C. Rauzy proving G. Rauzy’s conjecture for the Sturmian sequences which was quoted there. He answered us that they found the result was already known to Morse and Hedlund [4]. Finally checking this last paper we found there was a misprint in Rauzy’s paper and that the constant D in his conjecture has to be replaced by 1 + D to keep optimality.

Hence our proof that Rauzy’s conjecture implies Shallit’s is no longer correct, but we will give here our Rauzy-like conjecture and we will prove it is equivalent to Shallit’s.

1. The recurrence function of a sequence and the Rauzy conjecture

Definition. Let u be an infinite sequence on a finite alphabet. The recurrence function of the sequence u is the function n → R(n) (which might be infinite), where R(n) is the shortest length such that every factor of u of length R(n) contains at least one copy of every factor of u of length n.

Remark

A sequence for which ∀n ≥ 1, R(n) < +∞ is called primitive. It is not hard to see that a sequence is primitive if and only if each factor of it occurs infinitely often and “with bounded gaps” (i.e. the distance between two consecutive occurrences is bounded). A primitive sequence is sometimes called minimal, as the dynamical system it generates is minimal: the dynamical system generated by a sequence u is defined as (Ω, T) where T is the shift and Ω the closure of the orbit of u under the shift; the system is said minimal if there is no closed subset of Ω stable under the shift except ∅ and Ω. It is easy to see that this means exactly that the sequence u is primitive.

The reader wanting to know more about the recurrence function of infinite sequences can read for instance [3], [4] and also [5].

We can now state the Rauzy conjecture.

Rauzy’s conjecture [7]. Let u be an infinite sequence on a finite alphabet which is primitive and non-ultimately periodic. Then:

lim sup_{n→+∞} \frac{R(n)}{n} ≥ \frac{5 + \sqrt{5}}{2} = 3.61803 ⋯

Remark

As we said in the Introduction, the original text has the constant \frac{3+\sqrt{5}}{2}, but the case of Sturmian sequences shows that the optimal constant in this conjecture should be \frac{5+\sqrt{5}}{2}.

2. The Shallit conjecture

Conjecture ([8] and [6]). Let u = u_{0}u_{1}u_{2} ⋯ be an infinite sequence over a finite alphabet that is not ultimately periodic. Define S(n) to be the length of the longest suffix of u_{0}u_{1} ⋯ u_{n} that is also a factor of u_{0}u_{1} ⋯ u_{n−1}. Then

lim inf_{n→∞} \frac{S(n)}{n} ≤ \frac{3 − \sqrt{5}}{2} = .381966 · · · .

To know more about this conjecture and related topics the reader can read [8],

[9] and [6].

3. A function resembling the recurrence function and a Rauzy-like conjecture

We will introduce a function resembling the recurrence function. Instead of looking for a length R(n) such that every window having this length contains all factors of the sequence of length n, we just look for a length R′(n) such that the window of length R′(n) at the beginning of the sequence contains all factors of length n.

Definition. Let u be an infinite sequence on a finite alphabet. We define the function R′ by: R′(n) is the length of the shortest prefix of the sequence u that contains at least one occurrence of each factor of u of length n.

Remark

For any n ≥ 1, one has R′(n) < +∞ as the sequence takes only finitely many values. Furthermore the following inequality is clear:

∀n ≥ 1, R′(n) ≤ R(n).

Indeed any window of length R(n) contains all the factors of length n, this is the case in particular for the prefix of u of length R(n).

A Rauzy-like conjecture. Let u be an infinite sequence on a finite alphabet which is non-ultimately periodic. Then:

lim sup_{n→+∞} \frac{R′(n)}{n} ≥ \frac{3 + \sqrt{5}}{2} = 2.61803 ⋯

3. The Rauzy-like conjecture and the Shallit conjecture are equivalent

The aim of this paragraph is to prove the following theorem.

Theorem. For any sequence u with values in a finite alphabet, one has:

\frac{1}{lim inf_{n→+∞} \frac{S(n)}{n}} = lim sup_{n→+∞} \frac{R′(n)}{n}.

Hence the Rauzy-like conjecture is equivalent to Shallit’s.

Before we prove the theorem, we recall the inequality R′(n) ≤ R(n), which explains why, before having found the misprint in Rauzy’s paper, we thought we had a proof that Rauzy’s conjecture implies Shallit’s. We will prove this theorem in six steps:

(i) R′(S(n) + 1) ≥ n + 1,

(ii) S(R′(n)) < n + 1,

(iii) S(R′(n)) ≥ n,

(iv) S(R′(n)) = n,

(v) lim inf_{n→+∞} \frac{S(n)}{n} ≤ _{\frac{1}{lim sup_{n→+∞} \frac{R′(n)}{n}}},

(vi) _{\frac{1}{lim inf_{n→+∞} \frac{S(n)}{n}}} ≤ lim sup_{n→+∞} \frac{R′(n)}{n}.

∗ Step (i)

Consider the word u_{0} ⋯ u_{n} and its suffix u_{n−S(n)}u_{n−S(n)+1} ⋯ u_{n} of length S(n) + 1. This suffix is not a factor of u_{0} ⋯ u_{n−1} by definition of S(n). Hence the length of the prefix of the sequence u with minimal length that contains all the factors of u of length S(n) + 1 is certainly larger than or equal to the length of u_{0} ⋯ u_{n}, i.e. n + 1.

∗ Step (ii)

Consider the word u_{0} ⋯ u_{R′(n)} and its suffix u_{R′(n)−n}u_{R′(n)−n+1} ⋯ u_{R′(n)} of length n+1. The factor u_{R′(n)−n}u_{R′(n)−n+1} ⋯ u_{R′(n)−1}, of length n, is not a factor of u_{0} ⋯ u_{R′(n)−2} from the definition of R′, (if it were, the word u_{0} ⋯ u_{R′(n)−2} would then contain all factors of length n of the sequence u, although it has length R′(n) − 1). This implies in turn that the word u_{R′(n)−n}u_{R′(n)−n+1} ⋯ u_{R′(n)} is not a factor of u_{0} ⋯ u_{R′(n)−1}, hence S(R′(n)) < n + 1.

∗ Step (iii)

Consider the word u_{0} ⋯ u_{R′(n)} and its suffix u_{R′(n)−n+1}u_{R′(n)−n+2} ⋯ u_{R′(n)} of length n. By definition of R′(n) this last word is a factor of u_{0} ⋯ u_{R′(n)−1}, hence S(R′(n)) ≥ n.

∗ Step (iv)

This step results from Steps (ii) and (iii).

∗ Step (v)

Define a = lim inf_{n→+∞} \frac{S(n)}{n} and b = lim sup_{n→+∞} \frac{R′(n)}{n}.

We first notice that the sequence R′ is strictly increasing: indeed it results from the proof of Step (ii) that the word u_{R′(n)−n}u_{R′(n)−n+1} ⋯ u_{R′(n)} which has length n + 1 is not a factor of u_{0} ⋯ u_{R′(n)−1}. This implies R′(n + 1) > R′(n).

Now, replacing the sequence of integers n by the sequence R′(n), we can write:

a = lim inf_{n→+∞} \frac{S(n)}{n} ≤ lim inf_{n→+∞} \frac{S(R′(n))}{R′(n)}.

But using Step (iv) we have:

lim inf_{n→+∞} \frac{S(R′(n))}{R′(n)} = lim inf_{n→+∞} \frac{n}{R′(n)} = \frac{1}{lim sup_{n→+∞} \frac{R′(n)}{n}} .

Hence

a ≤ \frac{1}{b}.

Let us take now a strictly increasing sequence of integers n_{k} such that

lim_{k→+∞} \frac{S(n_{k})}{n_{k}} = a.

We claim that the sequence S(n_{k}) is unbounded: indeed, if S(n_{k}) were bounded, then R′(S(n_{k}) + 1) would be bounded as R′ is strictly increasing, but one has R′(S(n_{k}) + 1) ≥ n_{k} + 1 from Step (i). Then, after replacing if necessary the sequence n_{k} by a subsequence, one can assume that the sequence S(n_{k}) is strictly increasing. Of course the sequence S(n_{k})+1 will be also strictly increasing. Hence

b = lim sup_{n→+∞} \frac{R′(n)}{n} ≥ lim sup_{k→+∞} \frac{R′(S(n_{k}) + 1)}{S(n_{k}) + 1} ≥ lim sup_{k→+∞} \frac{n_{k} + 1}{S(n_{k}) + 1},

the last inequality coming from Step (i). By the definition of the sequence n_{k} one has

lim sup_{k→+∞} \frac{n_{k} + 1}{S(n_{k}) + 1} = lim_{k→+∞} \frac{n_{k} + 1}{S(n_{k}) + 1} = \frac{1}{a},

hence

\frac{1}{a} ≤ b,

hence finally

\frac{1}{a} = b.

4. Miscellanea

We will make here some remarks on the questions discussed above.

• For any sequence one has the inequality R′(n) ≥ p(n) + n − 1, where p(n) is the number of blocks of length n that occur in the sequence, (the function n → p(n) is called the complexity of the sequence, see [1] for a survey). Indeed, in the “worst” case, the p(n) blocks of length n that occur in the sequence are respectively the blocks u_{0} ⋯ u_{n−1}, u_{1} ⋯ u_{n}, · · ·. Note that the lower bound R(n) ≥ p(n) + n − 1 is well known. It is implied by this remark. For more precise results see [3] and [4].

• From the above remark we can deduce a simpler way than in [8] and [6] of obtaining the bound \frac{1}{2} = .5 instead of .381966 ⋯ in Shallit’s conjecture, or the bound 2 instead of 2.61803 ⋯ in our Rauzy-like conjecture. Indeed for a non-ultimately periodic sequence, one has (see [3] for instance, see also [2]): p(n) ≥ n + 1, hence R′(n) ≥ 2n.

• Almost all sequences on the finite alphabet A are “normal”, i.e. every possible block of length k occurs with frequency (Card A)^{−k}. In particular the complexity of almost all sequences is given by: p(n) = (Card A)^{n}, hence

R′(n) ≥ (Card A)^{n} + n − 1

and lim sup_{n→+∞} \frac{R′(n)}{n} = +∞. Of course the normal sequences are not primitive,

hence this says nothing for Rauzy’s conjecture.

• Using again our first remark, one sees that

lim sup_{n→+∞} \frac{R′(n)}{n} ≥ 1 + lim sup_{n→+∞} \frac{p(n)}{n},

hence it “suffices” to show the Shallit conjecture or the Rauzy-like conjecture for sequences such that lim sup_{n→+∞} \frac{p(n)}{n} ≤ \frac{1+\sqrt{5}}{2}. Among them the case of the

Sturmian sequences (for which p(n) = n + 1) can certainly be addressed by adapting the arguments of [4] for the computation of lim sup_{n→+∞} \frac{R(n)}{n}, but we

have not written the details. Furthermore the fact that the conjecture is true both for the “high” complexities and for the “minimal” complexity (i.e. the Sturmian case) is a strong indication it may be true for all sequences.

References

[1] J.-P. Allouche, Sur la complexité des suites infinies, Bull. Belg. Math. Soc. 1 (1994), 133– 143.

[2] E. M. Coven, G. A. Hedlund, Sequences with minimal block growth, Math. Systems Theory 7 (1973), 138–153.

[3] M. Morse, G. A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), 815–866.

[4] M. Morse, G. A. Hedlund, Symbolic dynamics II, Sturmian trajectories, Amer. J. Math. 62 (1940), 1–42.

[5] J. Mouline, Contribution à l’étude de la complexité des suites substitutives, Thèse, Université de Provence (1989).

[6] C. Pomerance, J. M. Robson, J. Shallit, Automaticity II: descriptional complexity in the unitary case, Preprint (1994).

[7] G. Rauzy, Suites à termes dans un alphabet fini, Sém. de Théorie des Nombres de Bordeaux (1982-1983), 25-01–25-16.

[8] J. Shallit, Y. Breitbart, Automaticity I: properties of a measure of decriptional complexity, In: P. Enjalbert, E. W. Mayr, K. W. Wagner editors, STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science (Springer-Verlag) 775 (1994), 619–630.

[9] J. Shallit, Y. Breitbart, Automaticity I: properties of a measure of decriptional complexity, Preprint (1994).

Jean-Paul Allouche CNRS, LMD Luminy, Case 930 F-13288 Marseille Cedex 9 France

Mireille Bousquet-Mélou CNRS, LaBRI 351 cours de la Libération F-33405 Talence Cedex France

e-mail: allouche@lmd.univ-mrs.fr, bousquet@labri.labri.u-bordeaux.fr