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}\).


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