Теорема Дежана - Википедия - 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 к leq 11}$.^[4]Этот анализ был расширен до ${ Displaystyle к leq 14}$ в 2007 году Мохаммад-Нури и Карри.^[5]

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

Слова Дежана

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

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