Estimation of the number of aperiodic words
- Авторлар: Senashov V.I.1
-
Мекемелер:
- Institute of Computational Modelling of Siberian Branch of RAS
- Шығарылым: Том 23, № 3 (2022)
- Беттер: 409-416
- Бөлім: Section 1. Computer Science, Computer Engineering and Management
- URL: https://journals.eco-vector.com/2712-8970/article/view/553500
- ID: 553500
Дәйексөз келтіру
Толық мәтін
Аннотация
In 1902 W. Burnside raised the issue of local finiteness of groups, all elements of which are of finite order. The first negative answer was obtained in 1968 in the article by by P.S. Novikov and S.I. Adian. Finiteness of the free Burnside group of period n was established for n = 2, n = 3 (W. Burnside), n = 4 (W. Burnside, I. N. Sanov), n = 6 (M. Hall). The proof of infinity of this group for odd n ≥ 4381 was given in the article by P. S. Novikov and S. I. Adian (1967), and for odd n ≥ 665 in the book by S. I. Adian (1975). In relation with these results we consider the set of m-aperiodic words. Word is called l-aperiodic if there are no non-empty subwords of the form Yl in it. In the monograph by S. I. Adian (1975) it was showen the proof of S. E. Arshon (1937) of the fact that in the two-letters alphabet there is an infinite set of arbitrarily long 3-aperiodic words. In the book by A. Yu. Olshansky (1989) the theorem on the infinity of the set of 6-aperiodic words was proved, and a lower bound function for the number of words of a given length was obtained. Our aim is to get an estimate for the function f(n) of the number of -m - aperiodic words of the length in the two-letters alphabet. The results can be applied when encoding information in space communications.
Негізгі сөздер
Толық мәтін
Введение*
В 1902 Уильям Бернсайд поставил вопрос о локальной конечности групп, в которых выполнено соотношение xn = 1 [1]. Впоследствии этот вопрос приобрел статус проблемы Бернсайда. Отрицательный ответ на него впервые был получен в 1968 в работах П. С. Новикова – С. И. Адяна [2–4].
Группа B(d, n) с d порождающими и тождественным соотношением xn = 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, если оно не содержит непустых подслов вида Yl.
В монографии А. Ю. Ольшанского [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 больше чем (³/₂)n.
В связи с этими результатами представляет интерес оценка числа m-апериодических слов в двухбуквенном алфавите.
Случай 2-апериодических слов в алфавите {a, b} легко рассматривается и такие слова можно сразу перечислить:
a, b, ab, ba, aba, bab.
Остальные случаи рассматриваются в теоремах 1–3.
При доказательстве теорем будем использовать метод А. Ю. Ольшанского из [10].
Теорема 1. Алфавит {a, b} содержит сколь угодно длинные m-апериодические слова для m≥5. При этом количество таких слов длины n больше, чем (³/₂)n.
Доказательство. Сначала докажем неравенство ƒ(n + 1) > ³/₂ƒ(n) по индукции.
База индукции: ƒ(2) > ³/₂ƒ(1), где ƒ(1) = 2, ƒ(2) = 4.
Каждое m-апериодическое слово длины n + 1 есть результат приписывания справа одной из букв a или b к m-апериодическому слову длины n. Можно получить 2ƒ(n) слов X длины n + 1. Но некоторые из полученных слов могут содержать степени Am. Нужно оценить число подобных возможностей.
Может получиться лишь равенство вида X ≡ YAm, поскольку иначе уже начало длины n слова X длины n + 1 содержит Am. Для слов A длины 1 (всего два таких слова) имеется меньше, чем 2ƒ(n + 1 – m) слов вида X ≡ YAm, где слово Y m-апериодично и |Y| = n + 1 – m:
( ) a,
() b.
Существует 4 слова A длины 2. Количество соответствующих слов вида X ≡ YAm длины n + 1 меньше, чем 4ƒ(n + 1 – 2m) , где слово Y m - апериодично длины n + 1 – 2m.
Аналогично продолжая рассуждения, получаем:
Поскольку по предположению индукции ƒ(n) > (³/₂)k × ƒ(n - k), получается
.
Вынося ƒ(n) за скобки получаем
для любых m ≥ 5 (так как m√2<³/₂ для любого m ≥ 5, то геометрическая прогрессия в неравенстве является убывающей со знаменателем 2 (³/₂)-m).
Следовательно, неравенство ƒ(n +1) > ³/₂ƒ(n) верно для любых натуральных n для функции ƒ(n) количества m-апериодических слов длины n при m ³ 5. Теорема доказана.
Из доказательства теоремы 1, в частности, вытекает, что этот способ доказательства не проходит для доказательства оценки ƒ(n) > (³/₂)n функции ƒ(n) количества 3- или 4-аперио-дических слов длины n. В следующей теореме показано, что этот способ не подходит длядоказательства оценки ƒ(n) > (x)n и для какого значения x из интервала [3Ö2,2] для 3-апериодических слов и из интервала [4Ö2,2] для 4-апериодических слов.
Теорема 2. Перенос доказательства теоремы 4.6 о 6-апериодических словах из [10] на случай 3- и 4-апериодических слов не приводит к доказательству соответствующей теоремы, т. е. для любого значения x из интервалов [3√2,2] для 3-апериодических и [4√2,2] для 4 - апериодических слов не удается доказать методом из [10], что число f_m(n) m-апериодических слов длины n больше, чем xn при m = 3 или m = 4.
Доказательство. Проведем рассуждения, аналогичные приведенным в [10]. Но теперь мы не фиксируем значение (³/₂)n для основания показательной функции, а вводим переменную x и ищем оценку в виде ƒ(n) > (x)n для 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). Но некоторые из полученных слов могут содержать степени A3 (соответственно степени A4). Нужно оценить число подобных возможностей.
Может получиться лишь равенство вида X ≡ YA3 (соответственно X ≡ YA4), поскольку иначе уже начало длины n слова X длины n + 1 содержит A3 (или A4). Для слов A длины 1 (всего два таких слова) имеется меньше, чем 2ƒ(n - 2) (соответственно 2ƒ(n - 3) слов вида X ≡ YA3 (соответственно X ≡ YA4), где слово Y 3-апериодично (4-апериодично) и |Y| = n – 2 (соответственно |Y| = n – 3):
(aa) a, (bb) b для случая 3-апериодических слов;
(aaa) a, (bbb) b для случая 4-апериодических слов.
Существует 4 слова A длины 2. Количество соответствующих слов вида X ≡ YA3 (соответственно X ≡ YA4) длины n + 1 меньше, чем 4ƒ(n - 5) (соответственно 4ƒ(n - 7)), где слово Y3-апериодично длины n-5 (соответственно 4-апериодично длины n-7).
Аналогично продолжая рассуждения, получаем
для 3-апериодических слов;
для 4-апериодических слов.
Поскольку по предположению индукции ƒ(n) > xk × ƒ(n - k), получается соответственно
и
.
Вынося ƒ(n) за скобки получаем
и соответственно
.
Введем еще ограничения 3√2 < x в первом случае и 4√2 < x во втором для того, чтобы геометрические прогрессии в правых частях неравенств были убывающими.
Обозначим вторые сомножители правых частей за S и применим формулу для суммы членов геометрической прогрессии со знаменателем 2x-3 для 3-апериодических слов и 2x-4 для 4 -апериодических слов:
.
Неравенство ƒ(n + 1) > x × ƒ(n) будет выполняться при S > x.
Преобразуем последние неравенства для обоих случаев:
, при m = 3,
, при m = 4.
После приведения подобных получаем
.
Так как 1 – 2x-3 > 0 в первом случае и 1 – 2x-4 > 0 во втором, получаем неравенства: 2 – 4x-3 - x > 0, 2 – 4x-4 - x > 0.
Нас интересует решения этих неравенств в интервалах (3√2; 2) и (4√2; 2) соответственно. Оказывается, что неравенства в данных интервалах решений не имеют. Теорема доказана.
Как показано в теореме 2 доказательство 1 не проходит для случая m = 4. В следующей теореме докажем, что утверждение теоремы 1 тем не менее верно для m = 4. Для случая m = 3 доказательство таким же методом, как в теореме 3, не проходит.
Теорема 3. В алфавите {a, b} существует сколь угодно длинные 4-апериодические слова. Более того, число ƒ(n) таких слов длины 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. Но некоторые из полученных слов могут содержать степени A4. Нужно оценить число подобных возможностей.
Может получиться лишь равенство вида X ≡ YA4, поскольку иначе уже начало длины n слова X длины n + 1 содержит A4. Для слов A длины 1 (всего два таких слова) имеется меньше, чем 2ƒ(n - 3) слов вида X ≡ YA4, где слово Y 4 - апериодично и |Y| = n - 3:
( aaa) a
( bbb) b.
На самом деле среди слов Y первого вида нужно брать только те, которые заканчиваютсяна b, так как иначе уже слово в скобках содержало бы a4, что противоречит его 4 - апериодичности. Аналогично среди слов Y второго вида нужно брать только те, которые заканчиваются на a. Таким образом, для слов A длины 1 имеется меньше, чем ƒ(n – 3) слов вида X ≡ YA4, где слово Y 4-апериодично и |Y| = n - 2.
Существует 4 слова A длины 2. Количество соответствующих слов вида X ≡ YA4 длины n + 1 меньше, чем 4ƒ(n – 7), где слово Y 4-апериодично длины n - 7:
( aa aa aa a) a
( ba ba ba b) a
( ab ab ab a) b
( bb bb bb b) b.
Но такие слова, как в скобках первого и последнего слов уже не содержатся в множестве 4 -апериодических слов длины n, поэтому их надо убрать из этого списка. Во втором слове подслово Y длины n -7 не может заканчиваться на a, так как иначе уже слово в скобках содержало бы (ba)4, что противоречит его 4-апериодичности. Аналогично в третьем слове подслово Y длины n - 7 не может заканчиваться на b, так как иначе уже слово в скобках содержало бы (ba)4. Таким образом, слов вида X ≡ YA4 длины n + 1 меньше, чем ƒ(n - 7), где Y – 4-апериодическое слово длины .
Аналогично продолжая рассуждения, получаем
Поскольку по предположению индукции , получается
Вынося ƒ(n) за скобки, получаем
Обозначим второй сомножитель правой части за S и применим формулу для суммы членов геометрической прогрессии со знаменателем 2(³/₂)-4 для первой и второй прогрессии и со знаменателем (³/₂)-4 для третьей:
.
Это значение S приближенно равно 1,58, что больше, чем 3/2. Теорема доказана.
Непосредственно из теорем 1 и 3 вытекает следующее.
Следствие. В алфавите {a, b} существует сколь угодно длинные m-апериодические слова при m ³ 4. Более того, число таких слов ƒ(n) длины 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).
Авторлар туралы
Vladimir Senashov
Institute of Computational Modelling of Siberian Branch of RAS
Хат алмасуға жауапты Автор.
Email: sen1112home@mail.ru
Dr. Sc., professor, leader researcher, professor of algebra and logic department
Ресей, 50/44, Akademgorodok, Krasnoyarsk, 660036Әдебиет тізімі
- Burnside W. On an unsettled question in the theory of discontinuous groups. Quart. J. Pure. Appl. Math. 1902, Vol. 33, P. 230–238.
- Novikov P. S., Adyan S. I. [On infinite periodic groups]. Izv. AN SSSR, Ser. mat. 1968, No. 1 (32), P. 212–244 (In Russ.).
- Novikov P. S., Adyan S. I. [On infinite periodic groups. II]. Izv. AN SSSR, Ser. mat. 1968, No. 2 (32), P. 251–524 (In Russ.).
- Novikov P. S., Adyan S. I. [On infinite periodic groups. III]. Izv. AN SSSR, Ser. mat. 1968,No. 3 (32), P. 709–731 (In Russ.).
- Sanov I. N. [Solving the Burnside problem for exponent 4]. Uch. Zap. LGU. 1940, Vol. 55, P. 166–170 (In Russ.).
- Hall M. Teoriya grupp [Group Theory]. Moscow, IL Publ., 1962, 468 p.
- Adyan S. I. Problema Bernsayda i tozhdestva v gruppakh [Bernside Problem and Identities in Groups]. Moscow, Nauka Publ., 1975, 336 p.
- Adyan S. I. [Burnside's problem and related questions]. Uspekhi Mat. sciences. 2010, Vol. 65, Iss. 5 (395), P. 5–60 (In Russ.).
- Senashov V. I. [Improved estimates of the number 6-aperiodic words of fixed length]. Vestnik SibGAU. 2016, No. 2 (17), P. 168–172 (In Russ.).
- Olshansky A. Yu. Geometriya opredelyayushchikh sootnosheniy v gruppakh [Geometry of defining relations in groups]. Moscow, Nauka Publ., 1989, 448 p.
- Senashov V. I. [6-aperiodic words over the three-letter alphabet]. Siberian Journal of Science and Technology. 2020, No. 3 (21), P. 333–336.
- Senashov V. I. [Aperiodic words]. Reshetnevskiye chteniya: materialy XIX Mezhdunar. nauch.-prakt. konf., posvyashch. 55-letiyu Sib. gos. aerokosmich. un-ta im. akad. M. F. Reshetneva [Reshetnev Readings: materials of XIX Intern. scientific and practical. conf. for 55th anniversary of Sib. State. Aerokosmich. Univ. Acad. M. F. Reshetnev]. (10–14 Nov. 2015, Krasnoyarsk): 2 parts. Under total. Ed. of Y. Y. Loginov; Sib. State. Aerokosmich. Univ, Krasnoyarsk, 2015, Part 2, P. 132–133 (In Russ.)
- Senashov V. I. Estimation of the number of 5-aperiodic words. Bulletin of Tuva State University. Technical and physical and mathematical sciences. 2017, No. 3, P. 132–138 (In Russ.).
- Senashov V. I. [Estimation of the number of 12-aperiodic words of fixed length]. Vestnik SibGAU. 2017, No. 1 (18), P. 93–96 (In Russ.).
- Thue A. Uber unendliche Zeichenreih. Norcke Vid. Selsk. skr., I Mat. Nat. Kl. Christiania. 1906, Bd. 7, P. 1–22.
- Arshon S. E. [Proof of existence of n-unit infinite asymmetric sequences]. Mat. sb. 1937, No. 4 (2 (44)), P. 769–779 (In Russ.).
Қосымша файлдар
![](/img/style/loading.gif)