2012 | OriginalPaper | Buchkapitel
On Two Stronger Versions of Dejean’s Conjecture
verfasst von : Igor N. Tunev, Arseny M. Shur
Erschienen in: Mathematical Foundations of Computer Science 2012
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Repetition threshold is the smallest number
RT
(
n
) such that infinitely many
n
-ary words contain no repetition of order greater than
RT
(
n
). These “extremal” repetition-free words are called threshold words. All values of
RT
(
n
) are now known, since the celebrated Dejean’s conjecture (1972) was finally settled in 2009. We study two questions about threshold words. First, does the number of
n
-ary threshold words grow exponentially with length? This is the case for 3 ≤
n
≤ 10, and a folklore conjecture suggests an affirmative answer for all
n
≥ 3. Second, are there infinitely many
n
-ary threshold words containing only finitely many different repetitions of order
RT
(
n
)? The answer is “yes” for
n
= 3, but nothing was previously known about bigger alphabets.
For odd
n
= 7,9,…,101, we prove the strongest possible result in this direction. Namely, there are
exponentially many
n
-ary threshold words containing
no repetitions of order
RT
(
n
)
except for the repeats of just one letter
.