Улучшение оценки количества 6-апериодических слов фиксированной длины

Введение. В 1902 г. Уильям Бернсайд поставил вопрос о локальной конечности групп, все элементы которых имеют конечные порядки [1]. Впоследствии этот вопрос приобрел статус проблемы Бернсайда о периодических группах. Отрицательный ответ на него был получен впервые лишь спустя 62 года, в 1964 г. Е. С. Голодом [2]. Позднее С. В. Алешиным (1972) [3], Р. И. Григорчуком (1980) [4], В. И. Сущанским (1979) [5] была предложена целая серия отрицательных примеров. Сам У. Бернсайд в своей статье 1902 г. [1] обратил особое внимание на вопрос о локальной конечности групп с тождественным соотношением х" = 1.

Группа B ( d,n ) = F / F , d > 1, которая получается факторизацией свободной группы F = F ( d ) с d -образующими по нормальной подгруппе F " , порожденной n -ми степенями всех элементов из F , называется сейчас свободной бернсайдовской группой показателя ( или периода ) n . Ее конечность установлена в разное время для n = 2 (тривиальный случай), n = 3 (У. Бернсайд), "  = 4 (У. Бернсайд для d = 2; И. Н. Санов [6] для произвольного d ), n = 6 (М. Холл [7]).

Доказательство бесконечности группы B ( d , n ), d > 2, для нечетных показателей n > 4381 было дано в работе П. С. Новикова - С. И. Адяна [8], а для нечетных n > 665 - в книге С. И. Адяна [9]. Гораздо более доступный и геометрически наглядный вариант доказательства для нечетных n > 10 ¹⁰ был предложен А. Ю. Ольшанским [10], который на основе усовершенствованного им геометрического метода построил для каждого достаточно большого простого числа p бесконечную р -группу, все собственные подгруппы которой имеют порядок р . Это наиболее сильная форма отрицательного ответа на вопрос Бернсайда, означающая существование бесконечного множества конечно порожденных периодических групп с тождеством, сколь угодно далеких по своим свойствам от конечных.

В связи с этими результатами рассмотрим множества апериодических слов, которые могут быть как конечными, так и бесконечными. Автором был сделан доклад «Апериодические слова» в 2015 г. на конференции «Решетневские чтения» [11].

Основной результат. Под периодическим словом с периодом Н понимается любое подслово некоторой степени Н , р > 0 . В этом смысле ababa - периодическое слово с периодом ab или ba.

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

Рассмотрим вопрос, как много 2-апериодических слов в алфавите a , b и как много 3-апериодических слов в этом алфавите.

Выпишем в лексикографическом порядке все слова в алфавите a , b с условием, что любое подслово в таких словах не содержит подслов, являющихся вторыми степенями других слов.

Таких 2-апериодических слов всего шесть:

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

Теперь начнем выписывать в таком же порядке различные слова в алфавите a, b , в которых не встречается подслов, являющихся третьими степенями других слов:

• a , aa , aab , aaba , aabaa , aabaab , aabaaba , aabaabaa , aabaabab , aabaababa , aabaababaa , aabaababaab , aabaababaaba , aabaababaabaa , aabaababaabaab , aabaababaababb ...

По мере составления списка становится понятным, что таких 3-апериодических слов бесконечно много. В монографии С. И. Адяна [9] приведено доказательство С. Е. Аршона 1937 г. [12] того, что в алфавите из двух букв существует бесконечное множество сколь угодно длинных 3-апериодических слов. Тем самым подтверждается гипотеза о бесконечности множества слов в алфавите a , b , в которых не встречается подслов, являющихся третьей степенью других слов.

В 1906 г. А. Туэ установил существование 3-апериодических слов произвольной длины в любом неоднобуквенном алфавите [13]. В работе [14] рассмотрена задача, являющаяся обобщением задачи о существовании сколь угодно длинных бесквадрат-ных слов над алфавитом из трех букв.

В работе [15] была доказана теорема (доказательство близко к [16]) о бесконечности множества 6-апериодических слов и получена оценка снизу функции f ( n ) - количества таких слов длины n : в алфавите { a , b } существует сколь угодно длинные 6-апериодические слова. Более того, число f ( n ) таких слов длины n больше, чем (3/2) ⁿ .

Наша задача получить более точную оценку для функции f ( n ) количества 6-апериодических слов длины n . Проведем рассуждения, аналогичные доказательству теоремы 4.6 из [15], заранее не выставляя значение оценки, а будем искать ее в виде xⁿ . При этом мы изменим доказательство из [15], чтобы получить более точную оценку множества 6-апериоди-ческих слов любой заданной длины. Тем самым мы докажем следующую теорему.

Теорема. В алфавите { a , b } существует сколь угодно длинные 6-апериодические слова. Более того, число f ( n ) таких слов длины n больше, чем ( x ) ⁿ , для любого х из интервала (1,3219635; 1,9221753).

Доказательство. Докажем неравенство f ( n + 1) > >  x • f ( n ) по индукции. Одновременно будем вводить ограничения на x. Сразу отметим очевидное неравенство: x >  1 .

База индукции f (2) >  x • f (1), где f (1) = 2, f (2) = 4. Для того, чтобы выполнялась база индукции 4 >  x • 2, положим x <  2 .

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

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

(........ aaaaa ) a ,

.—j

n — 5

Домножим на x ¹⁷ числитель и знаменатель (напомним, что 1 <  x <  2 ):

n — 5

Существует 4 слова A длины 2. Количество соответствующих слов вида X = YA ⁶ длины n + 1 меньше, чем 4 f ( n — 11), где слово Y 6-апериодично длины n — 11:

4 >  0.

(

(

(

....... aa aa aa aa aa a ) a ,

1,

n — 11

....... ba ba ba ba ba b ) a ,

1———1                        7 ’

n — 11

....... ab ab ab ab ab a ) b ,

1———1                        7 ’

n — 11

2 x ¹⁷ — x ¹⁸ + x ¹² — 6 x ¹¹ + 2 x ⁶ + 4 x ⁵ — ( x ⁶ — 2)( x ⁶ — 1)

Получаем две системы неравенств:

11 •	2 x 17 . ( x 6 "	— x 18 + x 12 — 6 x 11 2)( x 6 — 1) >  0;	+ 2 x 6	+ 4 x 5	— 4 >  0,
2) '	2 x 17 6 Д x -	18     12       11 — x + x — 6 x 2)( x 6 — 1) <  0.	+ 2 x 6	+ 4 x 5	— 4 <  0,

(„..... bb bb bb bb bb b ) b. n — 11

Но такие слова, как начала первого и последнего слов, уже не содержатся в множестве 6-апериоди-ческих слов длины n , поэтому их надо убрать из этого списка. Таким образом, слов вида X = YA ⁶ длины n + 1 меньше, чем 2 f ( n — 11), где Y - 6-апериодичес-кое слово длины n — 11.

Аналогично продолжая рассуждения, получаем: f ( n + 1) >  2 f ( n ) — 2 f ( n — 5) —

— (4 — 2) f ( n — 11) — (8 — 2) f ( n — 17)...

Поскольку по предположению индукции f (n +1) > x • f (n), получается f (n +1) > 2 f (n) — (2(x)—5 f (n) + 22 (x)—11 f (n) + +23 (x)—17 f (n) +...) + (2( x)—11 f (n) + 2( x)—17 f (n) +...).

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

Нас интересует решения этих систем в интервале ( 1; 2 ) . Решение системы 1 можно приблизить интервалом (1,3219635; 1,9221753), причём этот интервал полностью содержится в решении системы. Решением системы 2 является интервал (1; 6/2) . Нас интересует максимальное значение x , поэтому мы можем брать значения x из интервала (1,3219635; 1,9221753). Теорема доказана.

Заключение. Рассмотрено множество 6-апериоди-ческих слов и получена более точная, чем в работе [15], оценка для функции f ( n ) количества 6-апериодичес-ких слов длины n .

Acknowledgment. This work was supported by the grant of the Siberian Federal University (Project “Algebra-logical structures and complex analysis”).