IMPROVING OF ESTIMATE OF THE NUMBER OF 6-APERIODIC WORDS OF FIXED LENGTH

全文:

Введение. В 1902 г. Уильям Бернсайд поставил вопрос о локальной конечности групп, все элементы которых имеют конечные порядки [1]. Впоследствии этот вопрос приобрел статус проблемы Бернсайда о периодических группах. Отрицательный ответ на него был получен впервые лишь спустя 62 года, в 1964 г. Е. С. Голодом [2]. Позднее С. В. Алешиным (1972) [3], Р. И. Григорчуком (1980) [4], В. И. Сущанским (1979) [5] была предложена целая серия отрицательных примеров. Сам У. Бернсайд в своей статье 1902 г. [1] обратил особое внимание на вопрос о локальной конечности групп с тождественным соотношением хn = 1. Группа B(d,n) = F/Fn, d > 1, которая получается факторизацией свободной группы F = F(d) с d-образующими по нормальной подгруппе Fn, порожденной n-ми степенями всех элементов из F, называется сейчас свободной бернсайдовской группой показателя (или периода) n. Ее конечность установлена в разное время для n = 2 (тривиальный случай), n = 3 (У. Бернсайд), n = 4 (У. Бернсайд для d = 2; И. Н. Санов [6] для произвольного d), n = 6 (М. Холл [7]). Доказательство бесконечности группы B(d,n), d ≥ 2, для нечетных показателей n ≥ 4381 было дано в работе П. С. Новикова - С. И. Адяна [8], а для нечетных n ≥ 665 - в книге С. И. Адяна [9]. Гораздо более доступный и геометрически наглядный вариант доказательства для нечетных n > 1010 был предложен А. Ю. Ольшанским [10], который на основе усовершенствованного им геометрического метода построил для каждого достаточно большого простого числа p бесконечную р-группу, все собственные подгруппы которой имеют порядок р. Это наиболее сильная форма отрицательного ответа на вопрос Бернсайда, означающая существование бесконечного множества конечно порожденных периодических групп с тождеством, сколь угодно далеких по своим свойствам от конечных. В связи с этими результатами рассмотрим множества апериодических слов, которые могут быть как конечными, так и бесконечными. Автором был сделан доклад «Апериодические слова» в 2015 г. на конференции «Решетневские чтения» [11]. Основной результат. Под периодическим словом с периодом Н понимается любое подслово некоторой степени Нр, р > 0. В этом смысле ababa - периодическое слово с периодом ab или ba. Под l-апериодическим словом понимают слово Х, если в нем нет непустых подслов вида Yl. Рассмотрим вопрос, как много 2-апериодических слов в алфавите , и как много 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-апериодических слов и получена оценка снизу функции - количества таких слов длины n: в алфавите {a,b} существует сколь угодно длинные 6-апериодические слова. Более того, число таких слов длины больше, чем (3/2)n. Наша задача получить более точную оценку для функции количества 6-апериодических слов длины . Проведем рассуждения, аналогичные доказательству теоремы 4.6 из [15], заранее не выставляя значение оценки, а будем искать ее в виде . При этом мы изменим доказательство из [15], чтобы получить более точную оценку множества 6-апериодических слов любой заданной длины. Тем самым мы докажем следующую теорему. Теорема. В алфавите {a,b} существует сколь угодно длинные 6-апериодические слова. Более того, число таких слов длины n больше, чем , для любого х из интервала (1,3219635; 1,9221753). Доказательство. Докажем неравенство по индукции. Одновременно будем вводить ограничения на . Сразу отметим очевидное неравенство: . База индукции , где , f(2) = 4. Для того, чтобы выполнялась база индукции , положим . Каждое 6-апериодическое слово длины есть результат приписывания справа одной из букв a или b к 6-апериодическому слову длины . Можно получить 2f(n) слов X длины n + 1. Но некоторые из полученных слов могут содержать степени A6. Нужно оценить число подобных возможностей. Может получиться лишь равенство вида , поскольку иначе уже начало длины слова длины содержит . Для слов A длины 1 (всего два таких слова) имеется меньше чем слов вида , где слово 6-апериодично и : (aaaaa) a, (bbbbb) b. Существует 4 слова A длины 2. Количество соответствующих слов вида длины меньше, чем , где слово 6-апериодично длины : (aa aa aa aa aa a) a, (ba ba ba ba ba b) a, (ab ab ab ab ab a) b, (bb bb bb bb bb b) b. Но такие слова, как начала первого и последнего слов, уже не содержатся в множестве 6-апериодических слов длины , поэтому их надо убрать из этого списка. Таким образом, слов вида длины меньше, чем , где - 6-апериодическое слово длины . Аналогично продолжая рассуждения, получаем: Поскольку по предположению индукции получается Вынося за скобки, получаем: Обозначим второй сомножитель правой части за и применим формулу для суммы членов геометрической прогрессии со знаменателем для первой суммы и со знаменателем - для второй: Неравенство будет выполняться при . Получаем: Преобразуем данное неравенство: Домножим на числитель и знаменатель (напомним, что ): Получаем две системы неравенств: 1) 2) Нас интересует решения этих систем в интервале Решение системы 1 можно приблизить интервалом (1,3219635; 1,9221753), причём этот интервал полностью содержится в решении системы. Решением системы 2 является интервал . Нас интересует максимальное значение , поэтому мы можем брать значения из интервала (1,3219635; 1,9221753). Теорема доказана. Заключение. Рассмотрено множество 6-апериодических слов и получена более точная, чем в работе [15], оценка для функции количества 6-апериодических слов длины .

作者简介

V. Senashov

Institute of Computational Modeling SB RAS; Siberian Federal University

Email: sen1112home@mail.ru
50/44, Akademgorodok, Krasnoyarsk, 660036, Russian Federation; 79, Svobodniy Av., Krasnoyarsk, 660041, Russian Federation

参考

补充文件