m-апериодические слова над трехбуквенным алфавитом

Полный текст

Введение

Работа посвящена изучению множеств апериодических слов над конечным алфавитом. Множество апериодических слов можно рассматривать как словарь некоторого конечного формального языка.

Данные о существовании бесконечного слова в двух- или трехбуквенном алфавите, которое не содержит подслов, являющихся кубами или, соответственно, квадратами, впервые получены А. Туэ в 1906 г. [1]. Пример бесконечной последовательности несократимых слов, каждое из которых является началом следующего и не содержит квадратов слов в алфавите из двух букв, построил С. И. Адян (лемма 1 из [2]). В статье С. Е. Аршона 1937 г. [3] доказано существование n-значной ассиметричной бесповторной последовательности для алфавита не менее чем из трех букв. В монографии С. И. Адяна [4] доказано, что в алфавите из двух символов существуют бесконечные 3-апериодические последовательности. Задача изучения таких последовательностей рассматривается С. И. Адяном в связи с его исследованием проблемы Бернсайда [5–7]. А. М. Шур выяснил, какие свойства обычных слов сохраняются при переходе к бесконечным, а какие видоизменяются, теряются либо заменяются новыми, и изучил множество всех бескубных Z-слов в двухбуквенном алфавите [8–10]. В монографии А. Ю. Ольшанского [11] доказана бесконечность множества 6-апериодических слов в двухбуквенном алфавите и получена оценка количества таких слов любой данной длины.

Нами была улучшена оценка А. Ю. Ольшанского [11] количества 6-апериодических слов в 2-буквенном алфавите [12], а также сделан доклад по теме апериодических слов [13]. Затем исследования по этому вопросу были продолжены.

В работе [14] доказана теорема о бесконечности множества m-апериодических слов для $m\ge 4$ в двухбуквенном алфавите и получена оценка количества таких слов. Случай трехбуквенного алфавита рассмотрен только в одном случае: в работе [15] получена оценка для количества 6-апериодических слов.

В данной статье будет изучено множество m-апериодических слов в трехбуквенном алфавите: доказана бесконечность множества m-апериодических слов для $m\ge 4$ в трехбуквенном алфавите и получена оценка количества таких слов. Результаты могут быть полезны при кодировании информации в сеансах космосвязи.

Обобщения апериодичности, когда исключаются не только степени некоторых подслов, исследовались в [16].

Основной результат

Напомним, что периодическим словом с периодом Н называется любое подслово некоторого слова Н^р, р > 0.

В качестве примера периодического слова с периодом ab можно рассмотреть слово ababa.

l-апериодическим словом называется слово Х, в котором нет нетривиальных подслов вида Y^l.

С. И. Адян [4] доказал, что в алфавите из двух букв существует бесконечно много сколь угодно длинных 3-апериодических слов.

С. Е. Аршон установил существование слов любой длины, свободных от квадратов в трех- буквенном алфавите [3].

А. Ю. Ольшанский в работе [11] рассматривал множество 6-апериодических слов. Он доказал, что существуют такие слова любой длины, и получил оценку функции f (n) – количества 6-апериодических слов длины n . Их оказалось больше, чем ${\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^n$. В работе [12] нами улучшена оценка А. Ю. Ольшанского количества 6-апериодических слов над 2-буквенным алфавитом.

В работе [15] нами доказана теорема о бесконечности множества m-апериодических слов при ограничении на период $m\ge 4$ в двухбуквенном алфавите и получена оценка снизу количества таких слов.

Для нас представляет интерес оценить количество m-апериодических слов в алфавите из трех букв.

При доказательстве теоремы мы будем применять метод, используемый А. Ю. Ольшанским [11].

Теорема. В трехбуквенном алфавите существуют сколь угодно длинные m-апериодические слова для $m\ge 4$ и число f (n) таких слов длины n больше, чем ${\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^n$.

Доказательство. Рассмотрим трехбуквенный алфавит {a, b, c}. В этом алфавите будем изучать m-апериодические слова для $m\ge 4$. Будем исследовать функцию f (n) количества m-апериодических слов длины n.

Сначала докажем неравенство f (n + 1) > (5 / 2) f (n) при помощи метода математической индукции.

Заметим, что имеется ровно три m-апериодическиx слова a, b, c длины один и девять m-апериодических слов aa, ab, ac, ba, bb, bc, ca, cb, cc длины 2 в трехбуквенном алфавите для $m\ge 4$. Таким образом, в этом случае имеем f (1) = 3, f (2) = 9 .

Тогда при n = 1 справедливо нервенство $f \left(2\right) >\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right. · f \left(1\right)$ и полученная оценка выступает в качестве базы индукции.

Теперь нужно сделать шаг индукции. Предположим, что неравенство f (n) > (5 / 2) f (n - 1) верно для всех значений, не превышающих n, и установим его справедливость в случае f (n + 1) > (5 / 2) f (n).

Любое m-апериодическое слово длины n + 1 можно получить приписыванием справа букв a, b или c к m-апериодическому слову длины n . Так получается 3 f (n) слов X длины n + 1 .

Некоторые из таких слов содержат степени A^m . Попробуем отбросить такие слова, содержащие подслова периода m.

При приписывании новой буквы справа может получиться только слово вида $X \equiv Y{A}^m$, содержащее слово периода m, так как иначе начало длины n слова X длины n + 1 содержит периодическое подслово периода m: A^m .

Для слов A длины 1 (существует всего три таких слова) имеется не больше, чем 3 f (n - m + 1) слов вида $X \equiv Y{A}^m$ , где слово Y m-апериодично и $\left|Y\right| = n - m + 1$ , A – одно из слов a, b, c.

Как показали выше, существует всего девять слов A длины 2. Тогда количество слов вида $X \equiv Y{A}^m$ длины n + 1 не больше, чем 9 f (n - 2m + 1) , где слово Y m-апериодично и имеет длину n - 2m + 1 .

Рассуждаем далее таким же образом, получаем оценку количества слов длины n+1 (строгое неравенство, так как легко указать слова, которые при получении оценки количества слов вида $X \equiv Y{A}^m$ уже при длине 1 слова A мы отбросили с избытком для получения оценки):

f (n + 1) > 3 f (n) - 3 f (n - m + 1) - 3² f (n - 2m + 1) - 3³ f (n - 3m + 1) - ...

Так как по индуктивному предположению справедлива оценка $f \left(n\right) > {\left(\raisebox{1ex}{$5 $}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^k · f (n - k )$, то применяя ее, видим:

$f\left(n+1\right)>3f\left(n\right)-\left(3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}f\left(n\right)+3^2{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-2m+1}f\left(n\right)+3^3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3m+1}f\left(n\right)+...\right)$.

Преобразуем полученное неравенство:

$f(n+1)>f\left(n\right)(3-\left(3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}+3^2{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-2m+1}+3^3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3m+1}+...\right)$.

Очевидно, $\sqrt[m]{3}<\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$ , поэтому геометрическая прогрессия в скобках является убывающей со знаменателем $3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}$ при ограничении $m\ge 4$.

Для выражения S в скобках правой части применим формулу суммы убывающей геометрической прогрессии

$S=3-\frac{3{\left({\displaystyle \raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}\right)}^{-m+1}}{1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}}$.

Для доказательства утверждения теоремы нам требуется оценка выражения в скобках правой части неравенства $S >\raisebox{1ex}{$ 5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.$.

Подставим в неравенство полученное выше выражение для S и выполним элементарные преобразования:

$\frac{3-9{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}+3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m+1}-\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}}>0$

Упростим полученное неравенство:

$\frac{3-9{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}-\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.}{1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}}>0$

Так как неравенство $1-3{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}>0$ выполняется при $m\ge 4$, то остается проверить справедливость неравенства:

$3-9{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}-\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.>0$

Справедливость этого неравенства устанавливается непосредственным вычислением при m = 4 , а при $m\ge 4$ оно тем более верно, поскольку ${\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-m}<{\left(\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3}$ при таких m. Следовательно, доказано, что неравенство $f(n+1)>\raisebox{1ex}{$5$}\!\left/ \!\raisebox{-1ex}{$2$}\right.f\left(n\right)$ выполняется для любых натуральных значений числа n при условии $m\ge 4$.

Утверждение теоремы доказано.

Заключение

Продолжается изучение вопроса об оценке количества апериодических слов при различных условиях. Рассмотрено множество m-апериодических слов при $m\ge 4$ в трехбуквенном алфавите и получена оценка для функции количества таких слов любой данной длины.

Благодарности. Работа выполнена в рамках госзадания ИВМ СО РАН (базовый проект № 0287-2021-0002). Работа поддержана Красноярским математическим центром, финансируемым Минобрнауки РФ (Соглашение 075-02-2024-1429).

Acknowledgment. The work was performed in the framework of the state assignment of ICM SB RAS, project no. 0287-2021-0002. This work is supported by the Krasnoyarsk Mathematical Center and financed by the Ministry of Science and Higher Education of the Russian Federation (Agreement No. 075-02-2024-1429).

Об авторах

Владимир Иванович Сенашов

Автор, ответственный за переписку.
Email: sen1112home@mail.ru

доктор физико-математических наук, профессор, ведущий научный сотрудник

Список литературы

Дополнительные файлы