# zbMATH — the first resource for mathematics

On the conjectures of Rauzy and Shallit for infinite words. (English) Zbl 0859.11019
Shallit has conjectured the following result: Let $$(u_n)$$ 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 \dots u_n$$ that is also a factor of $$u_0,u_1, \dots, u_{n-1}$$. Then $\lim\inf {S(n) \over n} \leq C, \text{where }C={3-\sqrt 5 \over 2}.$ The authors show a connection between Shallit’s conjecture and a conjecture due to Rauzy on the recurrence function $$R(n)$$ of a non-ultimately periodic primitive sequence $$u$$ $$(R(n)$$ is the smallest integer such that every factor of $$u$$ of length $$R(n)$$ contains at least one occurrence of each factor of $$u$$ of length $$n)$$. Rauzy’s conjecture states that $\limsup_{n\to+ \infty} {R(n) \over n} \geq {5+\sqrt 5\over 2}.$ In fact, Shallit’s conjecture is proved to be equivalent to a Rauzy-like conjecture: if $$R'(n)$$ denotes the length of the shortest prefix of the sequence $$u$$ that contains at least one occurrence of each factor of $$u$$ of length $$n$$, then we have: ${1\over \displaystyle{\lim_{n\to+\infty}} \inf {s(n)\over n}} = \lim_{n \to+\infty} \sup{R'(n) \over n}.$ Very recently, Julien Cassaigne has given a proof of Rauzy’s conjecture and, by studying the Rauzy-like conjecture, has produced a counter-example to Shallit’s conjecture, which seems to indicate that the constant $$C= {3-\sqrt 5 \over 2}$$ has to be replaced by $${29-2 \sqrt{10} \over 9}$$.

##### MSC:
 11B85 Automata sequences 68R15 Combinatorics on words
Full Text: