Estimation of the number of aperiodic words

Full Text

Введение*

В 1902 Уильям Бернсайд поставил вопрос о локальной конечности групп, в которых выполнено соотношение xⁿ = 1 [1]. Впоследствии этот вопрос приобрел статус проблемы Бернсайда. Отрицательный ответ на него впервые был получен в 1968 в работах П. С. Новикова – С. И. Адяна [2–4].

Группа B(d, n) с d порождающими и тождественным соотношением xⁿ = 1 называется сейчас свободной бернсайдовской группой ранга d и периода n. Ее конечность установлена в разное время для n = 2 (тривиальный случай), n = 3 (У. Бернсайд [1]), n = 4 (У. Бернсайд [1] для d = 2; И. Н. Санов [5] для произвольного d), n = 6 (М. Холл [6]). Доказательство бесконечности группы B(d, n), d ≥ 2, для нечетных показателей n ≥ 4381 было дано в [2–4], а для нечетных n ≥ 665 – в монографии С. И. Адяна [7].

Более подробно с результатами по проблеме Бернсайда можно познакомиться по работе С. И. Адяна [8].

Определение

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

В монографии А. Ю. Ольшанского [10] доказана теорема о бесконечности множества 6-апериодических слов и получена оценка снизу количества таких слов любой данной длины. Автором в [9] была улучшена оценка из [10] количества 6-апериодических слов в алфавите из двух букв.

В связи с этими результатами рассмотрим множество m-апериодических слов в двухбуквенном алфавите для m ≥ 2.

В статье [11] также получены результаты для 6-апериодических слов над трехбуквенным алфавитом. По этой теме автором опубликованы работы [12–15]. Результаты могут быть применены при кодировании информации в космической связи.

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

В 1906 А. Туэ установил существование неповторяющихся слов в трехбуквенном алфавите и 3-апериодических слов произвольной длины в любом неоднобуквенном алфавите [11] (см. также лемму 1 в [8]). В статье [16] С. Е. Аршон в 1937 доказал существование n-значной асимметричной (повторяющейся) последовательности для n³ 3. В монографии С. И. Адяна [7] представлен метод Аршона для доказательства существования бесконечных 3-апериодических последовательностей в алфавите из двух символов.

В [10] доказана теорема 4.6 о бесконечности множества 6-апериодических слов и получена оценка функции ƒ(n) числа таких слов длины n: в алфавите {a, b} существуют сколь угодно длинные 6-апериодические слова. При этом количество ƒ(n) таких слов длины n больше чем (³/₂)ⁿ.

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

Случай 2-апериодических слов в алфавите {a, b} легко рассматривается и такие слова можно сразу перечислить:    

a, b, ab, ba, aba, bab.

Остальные случаи рассматриваются в теоремах 1–3.

При доказательстве теорем будем использовать метод А. Ю. Ольшанского из [10].

Теорема 1. Алфавит {a, b} содержит сколь угодно длинные m-апериодические слова для m≥5. При этом количество таких слов длины n больше, чем (³/₂)ⁿ.

Доказательство. Сначала докажем неравенство ƒ(n + 1) > ³/₂ƒ(n) по индукции.

База индукции:  ƒ(2) > ³/₂ƒ(1), где ƒ(1) = 2, ƒ(2) = 4.

Каждое m-апериодическое слово длины n + 1 есть результат приписывания справа одной из букв a или b к m-апериодическому слову длины n. Можно получить 2ƒ(n) слов X длины n + 1. Но некоторые из полученных слов могут содержать степени A^m. Нужно оценить число подобных возможностей.

Может получиться лишь равенство вида X ≡ YA^m, поскольку иначе уже начало длины n слова X длины n + 1 содержит A^m. Для слов A длины 1 (всего два таких слова) имеется меньше, чем 2ƒ(n + 1 – m) слов вида X ≡ YA^m, где слово Y m-апериодично и |Y| = n + 1 – m:

($\underset{n+1-m}{\underbrace{\mathrm{........}}} \underset{m-1}{\underbrace{aa\mathrm{...}a}}$ ) a,

($\underset{n+1-m}{\underbrace{\mathrm{........}}} \underset{m-1}{\underbrace{bb\mathrm{...}b}}$) b.

Существует 4 слова A длины 2. Количество соответствующих слов вида X ≡ YA^m  длины n + 1 меньше, чем 4ƒ(n + 1 – 2m) , где слово Y m - апериодично длины n + 1 – 2m.

Аналогично продолжая рассуждения, получаем:

$f(n+1)>2f\left(n\right)-2f(n+1-m)-2^{2}f(n+1-2m)-2^{3}f(n+1-3m)-\mathrm{...}$

Поскольку по предположению индукции ƒ(n) > (³/₂)^k × ƒ(n - k), получается

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

Вынося ƒ(n) за скобки получаем

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

для любых m ≥ 5 (так как ^m√2<³/₂ для любого m ≥ 5, то геометрическая прогрессия в неравенстве является убывающей со знаменателем 2 (³/₂)^-m).

Следовательно, неравенство ƒ(n +1) > ³/₂ƒ(n) верно для любых натуральных n для функции ƒ(n) количества m-апериодических слов длины n при m ³ 5. Теорема доказана.

Из доказательства теоремы 1, в частности, вытекает, что этот способ доказательства не проходит для доказательства оценки ƒ(n) > (³/₂)ⁿ функции ƒ(n)  количества 3- или 4-аперио-дических слов длины n. В следующей теореме показано, что этот способ не подходит длядоказательства оценки ƒ(n) > (x)ⁿ  и для какого значения x из интервала [³Ö2,2] для 3-апериодических слов и из интервала [⁴Ö2,2] для 4-апериодических слов.

Теорема 2. Перенос доказательства теоремы 4.6 о 6-апериодических словах из [10] на случай 3- и 4-апериодических слов не приводит к доказательству соответствующей теоремы, т. е. для любого значения x из интервалов [³√2,2] для 3-апериодических и [⁴√2,2] для 4 - апериодических слов не удается доказать методом из [10], что число f_m(n) m-апериодических слов длины n больше, чем xⁿ при m = 3  или m = 4.

Доказательство. Проведем рассуждения, аналогичные приведенным в [10]. Но теперь мы не фиксируем значение (³/₂)ⁿ для основания показательной функции, а вводим переменную x и ищем оценку в виде ƒ(n) > (x)ⁿ для m = 3 и m = 4.

Сначала докажем неравенство ƒ(n + 1) > x × ƒ(n) по индукции. При этом введем ограничения на x. Чтобы удовлетворить неравенству ƒ(n) = 2 > x для m = 3 и m = 4, подложим x < 2.

База индукции ƒ(2) > x × ƒ(1), где ƒ(1) = 2, ƒ(2) = 4. База индукции справедлива при x < 2.

Каждое 3- или 4-апериодическое слово длины n+1 есть результат приписывания справа одной из букв a или b к 3-апериодическому (соответственно 4-апериодическому) слову длины n. Можно получить 2ƒ(n) слов X длины n + 1 (m = 3 или m = 4). Но некоторые из полученных слов могут содержать степени A³ (соответственно степени A⁴). Нужно оценить число подобных возможностей.

Может получиться лишь равенство вида X ≡ YA³ (соответственно X ≡ YA⁴), поскольку иначе уже начало длины n слова X длины n + 1 содержит A³ (или A⁴). Для слов A длины 1 (всего два таких слова) имеется меньше, чем 2ƒ(n - 2) (соответственно 2ƒ(n - 3) слов вида X ≡ YA³  (соответственно X ≡ YA⁴), где слово Y 3-апериодично (4-апериодично) и |Y| = n – 2 (соответственно |Y| = n – 3):

($\underset{n-2}{\underbrace{\mathrm{........}}}$aa) a,  ($\underset{n-2}{\underbrace{\mathrm{........}}}$bb) b   для случая 3-апериодических слов;

($\underset{n-3}{\underbrace{\mathrm{........}}}$aaa) a, ($\underset{n-3}{\underbrace{\mathrm{........}}}$bbb) b  для случая 4-апериодических слов.

Существует 4 слова A длины 2. Количество соответствующих слов вида X ≡ YA³ (соответственно X ≡ YA⁴) длины n + 1 меньше, чем 4ƒ(n - 5) (соответственно 4ƒ(n - 7)), где слово Y3-апериодично длины n-5 (соответственно 4-апериодично длины n-7).

Аналогично продолжая рассуждения, получаем

$f(n+1)>2f\left(n\right)-2f(n-2)-2^{2}f(n-5)-2^{3}f(n-8)-\mathrm{...}$

для 3-апериодических слов;

$f(n+1)>2f\left(n\right)-2f(n-3)-2^{2}f(n-7)-2^{3}f(n-11)-\mathrm{...}$

для 4-апериодических слов.

$f(n+1)>2f\left(n\right)-2f(n-3)-2^{2}f(n-7)-2^{3}f(n-11)-\mathrm{...}$

Поскольку по предположению индукции ƒ(n) > x^k × ƒ(n - k), получается соответственно

$f(n+1)>2f\left(n\right)-\left(2{\left(x\right)}^{-2}f\right(n)+2^2{\left(x\right)}^{-5}f(n)+2^3{\left(x\right)}^{-8}f(n)+\mathrm{...})$

и

$f(n+1)>2f\left(n\right)-\left(2{\left(x\right)}^{-3}f\right(n)+2^2{\left(x\right)}^{-7}f(n)+2^3{\left(x\right)}^{-11}f(n)+\mathrm{...})$.

Вынося ƒ(n) за скобки получаем

$f(n+1)>f\left(n\right)(2-(2{\left(x\right)}^{-2}+2^2{\left(x\right)}^{-5}+2^3{\left(x\right)}^{-8}+\mathrm{...})$

и соответственно

$f(n+1)>f\left(n\right)(2-(2{\left(x\right)}^{-3}+2^2{\left(x\right)}^{-7}+2^3{\left(x\right)}^{-11}+\mathrm{...})$.

Введем еще ограничения ³√2 < x в первом случае и ⁴√2 < x во втором для того, чтобы геометрические прогрессии в правых частях неравенств были убывающими.

Обозначим вторые сомножители правых частей за S и применим формулу для суммы членов геометрической прогрессии со знаменателем 2x^-3  для 3-апериодических слов и 2x^-4 для 4 -апериодических слов:

$S=2-\frac{2x^{-2}}{1-2x^{-3}} , S=2-\frac{2x^{-3}}{1-2x^{-4}}$.

Неравенство ƒ(n + 1) > x × ƒ(n) будет выполняться при S > x.

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

$S-x=\frac{2-4x^{-3}-2x^{-2}+2x^{-2}-x}{1-2x^{-3}}>0$, при m = 3,

$S-x=\frac{2-4x^{-4}-2x^{-3}+2x^{-3}-x}{1-2x^{-4}}>0$, при m = 4.

После приведения подобных получаем

$\frac{2-4x^{-3}-x}{1-2x^{-3}}>0 , \frac{2-4x^{-4}-x}{1-2x^{-4}}>0$.

Так как 1 – 2x^-3 > 0 в первом случае и 1 – 2x^-4 > 0 во втором, получаем неравенства: 2 – 4x^-3 - x > 0, 2 – 4x^-4 - x > 0.

Нас интересует решения этих неравенств в интервалах (³√2; 2) и (⁴√2; 2) соответственно. Оказывается, что неравенства в данных интервалах решений не имеют. Теорема доказана.

Как показано в теореме 2 доказательство 1 не проходит для случая m = 4. В следующей теореме докажем, что утверждение теоремы 1 тем не менее верно для m = 4. Для случая m = 3 доказательство таким же методом, как в теореме 3, не проходит.

Теорема 3. В алфавите {a, b} существует сколь угодно длинные 4-апериодические слова. Более того, число ƒ(n) таких слов длины n больше, чем (³/₂)ⁿ.

Доказательство. Используем ту же схему, что и в теореме 1, но будем отбрасывать меньше лишних слов.

Заметим, что ƒ(1) = 2 > 3/2.

Докажем неравенство ƒ(n + 1) > 3/2 ƒ(n) по индукции.

База индукции: ƒ(2) > 3/2 ƒ(1), где ƒ(1) = 2, ƒ(2) = 4.

Каждое 4-апериодическое слово длины n + 1 есть результат приписывания справа одной из букв a или b к 4-апериодическому слову длины n. Можно получить 2ƒ(n) слов X длины n + 1. Но некоторые из полученных слов могут содержать степени A⁴. Нужно оценить число подобных возможностей.

Может получиться лишь равенство вида X ≡ YA⁴, поскольку иначе уже начало длины n слова X длины n + 1 содержит A⁴. Для слов A длины 1 (всего два таких слова) имеется меньше, чем 2ƒ(n - 3) слов вида X ≡ YA⁴, где слово Y 4 - апериодично и |Y| = n - 3:

($\underset{n-3}{\underbrace{\mathrm{........}}}$ aaa) a

($\underset{n-3}{\underbrace{\mathrm{........}}}$ bbb) b.

На самом деле среди слов Y первого вида нужно брать только те, которые заканчиваютсяна b, так как иначе уже слово в скобках содержало бы a⁴, что противоречит его 4 - апериодичности. Аналогично среди слов Y второго вида нужно брать только те, которые заканчиваются на a. Таким образом, для слов A длины 1 имеется меньше, чем ƒ(n – 3) слов вида X ≡ YA⁴, где слово Y 4-апериодично и |Y| = n - 2.

Существует 4 слова A длины 2. Количество соответствующих слов вида X ≡ YA⁴ длины n + 1 меньше, чем 4ƒ(n – 7), где слово Y 4-апериодично длины n - 7:

($\underset{n-7}{\underbrace{\mathrm{.......}}}$ aa aa aa a) a

($\underset{n-7}{\underbrace{\mathrm{.......}}}$ ba ba ba b) a

($\underset{n-7}{\underbrace{\mathrm{.......}}}$ ab ab ab a) b

($\underset{n-7}{\underbrace{\mathrm{.......}}}$ bb bb bb b) b.

Но такие слова, как в скобках первого и последнего слов уже не содержатся в множестве 4 -апериодических слов длины n, поэтому их надо убрать из этого списка. Во втором слове подслово Y длины n -7 не может заканчиваться на a, так как иначе уже слово в скобках содержало бы (ba)⁴, что противоречит его 4-апериодичности. Аналогично в третьем слове подслово Y длины n - 7 не может заканчиваться на b, так как иначе уже слово в скобках содержало бы (ba)⁴. Таким образом, слов вида X ≡ YA⁴  длины n + 1 меньше, чем ƒ(n - 7), где Y – 4-апериодическое слово длины .

Аналогично продолжая рассуждения, получаем

$f(n+1)>2f\left(n\right)-f(n-3)-\left(\right(2^2-2)/2)f(n-7)-\left(\right(2^3-2)/2)f(n-11)-\mathrm{...}$

Поскольку по предположению индукции $f\left(n\right)>{(3/2)}^k\cdot f(n-k)$, получается

$f(n+1)>2f\left(n\right)-(2·{\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3}\cdot f(n)+2^2\cdot {\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-7}·f(n)+2^3\cdot {\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-11}·f(n)+\mathrm{...})+$

$+\left({\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3}f\right(n)+ 2·{\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-7}\cdot f(n)+2^2·{\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-11}f(n)+\mathrm{...})+\left({\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-7}f\right(n)+{\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-11}f(n)+\mathrm{...})$

Вынося ƒ(n) за скобки, получаем

$f(n+1)>f\left(n\right)(2-(2\cdot {\left(\raisebox{1ex}{$3$}\!\left/ \!\raisebox{-1ex}{$2$}\right.\right)}^{-3}+2^2\cdot {\left(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.\right)}^{-7}+2^3\cdot {\left(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.\right)}^{-11}+\mathrm{...})+$

$+{\left(\right(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.)}^{-3} + 2·{\left(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.\right)}^{-7} + 2^2\cdot {\left(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.\right)}^{-11}+\mathrm{...})+({\left(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.\right)}^{-7} + {\left(\raisebox{1ex}{${\displaystyle 3}$}\!\left/ \!\raisebox{-1ex}{${\displaystyle 2}$}\right.\right)}^{-11} +.....\left)\right)$

Обозначим второй сомножитель правой части за S и применим формулу для суммы членов геометрической прогрессии со знаменателем 2(³/₂)^-4 для первой и второй прогрессии и со знаменателем (³/₂)^-4 для третьей:

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

Это значение S приближенно равно 1,58, что больше, чем 3/2. Теорема доказана.

Непосредственно из теорем 1 и 3 вытекает следующее.

Следствие. В алфавите {a, b} существует сколь угодно длинные m-апериодические слова при m ³ 4. Более того, число таких слов ƒ(n) длины n больше, чем (³/₂)ⁿ.

Заключение

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

 

_________________________

* Работа выполнена при поддержке Красноярского математического центра и финансировании Министерства науки и высшего образования Российской Федерации в рамках создания и развития региональных научно-образовательных центров математики (Соглашение № 075-02-2021-1388).

This work is supported by the Krasnoyarsk Mathematical Center and financed by the Ministry of Science and Higher Education of the Russian Federation in the framework of the establishment and development of regional Centers for Mathematics Research and Education (Agreement No. 075-02-2021-1388).

About the authors

Vladimir I. Senashov

Institute of Computational Modelling of Siberian Branch of RAS

Author for correspondence.
Email: sen1112home@mail.ru

Dr. Sc., professor, leader researcher, professor of algebra and logic department

Russian Federation, 50/44, Akademgorodok, Krasnoyarsk, 660036

References

Supplementary files