Теорема Дежана - Dejeans theorem

Теорема Дежана (ранее Гипотеза Дежана) - это утверждение о повторениях в бесконечном строки символов. Это относится к области комбинаторика слов; это было предположено в 1972 году Франсуазой Дежан и доказано в 2009 году Карри и Рамперсад и, независимо, Рао.^[1]

Контекст

При изучении струн конкатенация рассматривается как аналог умножения чисел. Так, например, если ${\displaystyle s}$ любая строка, то объединение ${\displaystyle ss}$ двух экземпляров ${\displaystyle s}$ называется квадратом ${\displaystyle s}$, и обозначил ${\displaystyle s^{2}}$. Эту экспоненциальную запись можно также распространить на дробные степени: если ${\displaystyle s}$ имеет длину ${\displaystyle \ell }$, и ${\displaystyle e}$ неотрицательное рациональное число вида ${\displaystyle n/\ell }$, тогда ${\displaystyle s^{e}}$ обозначает строку, образованную первым ${\displaystyle n}$ персонажи бесконечного повторения ${\displaystyle sssss\dots }$.^[1]

А слово без квадратов - это строка, не содержащая квадратов в качестве подстроки. В частности, он избегает последовательного повторения одного и того же символа, повторения одной и той же пары символов и т. Д. Аксель Туэ показал, что существует бесконечное слово без квадратов, использующее трехсимвольный алфавит, последовательность разностей между последовательными элементами Последовательность Туэ – Морса. Однако бесконечное двухсимвольное слово (или даже двухсимвольное слово длиной больше трех) не может быть бесквадратным.^[1]

Однако для алфавитов из двух символов существуют бесконечные слова без кубов, слова без подстроки формы ${\displaystyle sss}$. Одним из таких примеров является Последовательность Туэ – Морса сам; другой - это Последовательность Колакоски. Более того, последовательность Туэ – Морса не содержит подстроки, степень которой строго больше двух.^[1]

В 1972 году Дежан исследовал проблему определения для каждого возможного размера алфавита порога между показателями степени. ${\displaystyle e}$ для которого существует бесконечное ${\displaystyle e}$-сильное слово и показатели степени, для которых такого слова не существует. Проблема была решена для двухсимвольных алфавитов с помощью последовательности Туэ – Морса, и Дежан решила ее также для трехсимвольных алфавитов. Она выдвинула гипотезу о точной формуле для порогового показателя для каждого большего размера алфавита;^[2] эта формула - гипотеза Дежана, теперь теорема.^[1]

Заявление

Позволять ${\displaystyle k}$ - количество символов в алфавите. Для каждого ${\displaystyle k}$, определять ${\displaystyle \operatorname {RT} (k)}$, то порог повторения, чтобы быть инфимум экспонентов ${\displaystyle e}$ такой, что существует бесконечное ${\displaystyle e}$-беспроводное слово на ${\displaystyle k}$-символ алфавита. Так, например, последовательность Туэ – Морса показывает, что ${\displaystyle \operatorname {RT} (2)=2}$, и аргумент, основанный на Локальная лемма Ловаса можно использовать, чтобы показать, что ${\displaystyle \operatorname {RT} (k)}$ конечно для всех ${\displaystyle k}$.^[1]

Тогда гипотеза Дежана состоит в том, что порог повторения может быть вычислен по простой формуле^[1][2]

${\displaystyle \operatorname {RT} (k)={\frac {k}{k-1}}}$

кроме двух исключительных случаев:

${\displaystyle \operatorname {RT} (3)={\frac {7}{4}}}$

и

${\displaystyle \operatorname {RT} (4)={\frac {7}{5}}.}$

Прогресс и доказательство

Сама Дежан доказала гипотезу о ${\displaystyle k=3}$.^[2]Дело ${\displaystyle k=4}$ было доказано Жан-Жаком Пансио в 1984 году.^[3]Следующим шагом вперед был Мулен Олланье в 1992 году, который доказал гипотезу для всех размеров алфавита до ${\displaystyle k\leq 11}$.^[4]Этот анализ был расширен до ${\displaystyle k\leq 14}$ в 2007 году Мохаммад-Нури и Карри.^[5]

В другом направлении, также в 2007 году, Артуро Карпи показал, что гипотеза верна для больших алфавитов. ${\displaystyle k\geq 33}$.^[6] Это сократило проблему до конечного числа оставшихся случаев, которые были решены в 2009 году и опубликованы в 2011 году Карри и Рамперсад.^[7] и независимо от Рао.^[8]

Слова Дежана

Бесконечная строка, удовлетворяющая формуле Дежана (не имеющая повторений экспоненты выше порога повторения), называется Слово Dejean.Так, например, последовательность Туэ – Морса является словом Дежана.

Рекомендации

1. Рамперсад, Нарад; Шаллит, Джеффри (2016), «Повторы словами», Комбинаторика, слова и символическая динамика, Энциклопедия математики. Appl., 159, Cambridge Univ. Press, Cambridge, pp. 101–150, МИСТЕР  3525483
2. Дежан, Франсуаза (1972), "Sur un théorème de Thue", Журнал комбинаторной теории, Серия А, 13: 90–99, Дои:10.1016/0097-3165(72)90011-8, МИСТЕР  0300959
3. Пансиот, Жан-Жак (1984), "À Propos d'une conjecture de F. Dejean sur les repétitions dans les mots", Дискретная прикладная математика, 7 (3): 297–311, Дои:10.1016 / 0166-218x (84) 90006-4, МИСТЕР  0736893
4. Мулен Олланье, Жан (1992), «Доказательство гипотезы Дежана для алфавитов с 5, 6, 7, 8, 9, 10 и 11 буквами», Теоретическая информатика, 95 (2): 187–205, Дои:10.1016 / 0304-3975 (92) 90264-Г, МИСТЕР  1156042
5. Mohammad-Noori, M .; Карри, Джеймс Д. (2007), "Гипотеза Дежана и слова Штурма", Европейский журнал комбинаторики, 28 (3): 876–890, Дои:10.1016 / j.ejc.2005.11.005, МИСТЕР  2300768
6. Карпи, Артуро (2007), "О гипотезе Дежана о больших алфавитах", Теоретическая информатика, 385 (1–3): 137–151, Дои:10.1016 / j.tcs.2007.06.001, МИСТЕР  2356248
7. Карри, Джеймс; Рамперсад, Нарад (2011), «Доказательство гипотезы Дежана», Математика вычислений, 80 (274): 1063–1070, arXiv:0905.1129, Дои:10.1090 / S0025-5718-2010-02407-X, МИСТЕР  2772111
8. Рао, Микаэль (2011), «Последние случаи гипотезы Дежана», Теоретическая информатика, 412 (27): 3010–3018, Дои:10.1016 / j.tcs.2010.06.020, МИСТЕР  2830264