УЛУЧШЕНИЕ ОЦЕНКИ КОЛИЧЕСТВА 6-АПЕРИОДИЧЕСКИХ СЛОВ ФИКСИРОВАННОЙ ДЛИНЫ

Описание

Перевод названия: IMPROVING OF ESTIMATE OF THE NUMBER OF 6-APERIODIC WORDS OF FIXED LENGTH

Тип публикации: статья из журнала

Год издания: 2016

Ключевые слова: группа, периодическое слово, апериодическое слово, алфавит, локальная конечность, group, Periodic word, aperiodic word, alphabet, local finiteness

Аннотация: У. Бернсайд поставил вопрос о локальной конечности групп, все элементы которых имеют конечные порядки. Отрицательный ответ был получен лишь в 1964 году Е. С. Голодом. Позднее С. В. Алешиным, Р. И. Григорчуком, В. И. Сущанским была предложена целая серия отрицательных примеров. Конечность свободной бернсайдовской группы периода n усПоказать полностьютановлена в разное время для n = 2, n = 3 (У. Бернсайд), n = 4 (У. Бернсайд, И. Н. Санов), n = 6 (М. Холл). Доказательство бесконечности этой группы для нечетных показателей n ? 4381 было дано в работе П. С. Новикова - С. И. Адяна (1967), а для нечетных n ? 665 - в книге С. И. Адяна (1975). Более наглядный вариант доказательства для нечетных n 1010 был предложен А. Ю. Ольшанским (1989). В связи с этими результатами рассматриваются множества апериодических слов. Под l-апериодическим словом понимают слово Х, если в нем нет непустых подслов вида Yl. Рассматривается вопрос о количестве 2-апериодических слов в двухбуквенном алфавите и как много 3-апериодических слов в этом алфавите. В монографии С. И. Адяна (1975) приведено доказательство С. Е. Аршона (1937) того, что в алфавите из двух букв существует бесконечное множество сколь угодно длинных 3-апериодических слов. В монографии А. Ю. Ольшанского (1989) доказана теорема о бесконечности множества 6-апериодических слов и получена оценка снизу количества таких слов любой данной длины. Наша задача получить более точную оценку для функции f(n) количества 6-апериодических слов длины n. Результаты могут найти применение при кодировании информации, иcпользующейся в сеансах космической связи. W. Burnside raised the issue of locally finiteness of groups, all elements of which have finite order. A negative answer was received only in 1964 by E. S. Golod. Later S. V. Aleshin, R. I. Hryhorczuk, V. I. Sushchanskii proposed series of negative examples. Finiteness of the free Burnside group of period n installed at different times for n = 2, n = 3 (W. Burnside), n = 4 (W. Burnside, I. N. Sanov), n = 6 (M. Hall). Proof of infinity of this group for odd n ? 4381 was given by P. S. Novikov and S. I. Adian (1967), and for odd n ? 665 in the book of S. I. Adian (1975). More intuitive version of the proof for odd n 1010 was proposed by A. Yu. Olshansky (1989). In connection with these results we consider sets of aperiodic words. Under the l-aperiodic word understand the word X if in it there is no non-empty subwords of the form Yl. We consider the question about the number of 2-aperiodic words in a two-letter alphabet and how many 3-aperiodic words in this alphabet. In the monograph of S. I. Adian (1975) shows a 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 of A. Yu. Olshansky (1989) a theorem on the infinity of the set of 6-aperiodic words and obtained a lower bound function for the number of words of a given length was proved. Our aim is to get more accurate estimate for the function of the number of 6-aperiodic words of given length. The results can be applied when encoding information is used in space communications.

Ссылки на полный текст

Издание

Журнал: Вестник Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева

Выпуск журнала: Т. 17, 2

Номера страниц: 368-371

ISSN журнала: 18169724

Место издания: Красноярск

Издатель: Сибирский государственный аэрокосмический университет имени академика М.Ф. Решетнева

Авторы

Вхождение в базы данных