The Ehrenfeucht-Silberger problem (Q662035): Difference between revisions

A factor of a word \(w\) is a block of consecutive letters of \(w\). A factor \(u\) is said to be unbordered if none of its proper prefixes is also a suffix of \(u\); otherwise, \(u\) is said to be bordered. In 1979, \textit{A. Ehrenfeucht} and \textit{D. M. Silberger} [Discrete Math. 26, 101--109 (1979; Zbl 0416.20051)] raised a difficult problem that relates periodicity and unbordered factors of words (this problem is closely related to the so-called critical factorization theorem). Denoting by \(\tau(w)\) the maximum length of unbordered factors of \(w\) and by \(\pi(w)\) the minimal period of \(w\), they asked for a bound on the length of \(w\), bound depending on \(\tau(w)\), that would guarantee the equality \(\tau(w)=\pi(w)\) to hold. In this beautiful paper, the authors finally settle this longstanding problem showing that if \(w\) is a word of length at least \(\frac{7}{3}\tau(w)\), then \(\tau(w)=\pi(w)\). This turns out to be an asymptotically tight bound due to an earlier example of Assous and Pouzet. Holub and Nowotka prove their result, which is independent of the alphabet size, using their notion of \(\alpha\)-critical prefix of a word. This notion becomes useful when finding long unbordered factors in words with large minimal periods. The authors' arguments can also be modified to exhibit an additive constant, i.e., they can show that if the length of \(w\) is at least \(\frac{7}{3}\tau(w)-\frac{8}{3}\) then \(\tau(w)=\pi(w)\). For sake of clarity, the authors did not try to optimize the additive constant.