В математике последовательность Баума – Свита представляет собой бесконечную автоматическую последовательность нулей и единиц, определяемую правилом:
- b n = 1, если двоичное представление n не содержит блока последовательных нулей нечетной длины;
- b n = 0 в противном случае;
для n ≥ 0. [1]
Например, b 4 = 1, потому что двоичное представление 4 равно 100, которое содержит только один блок последовательных нулей длины 2; тогда как b 5 = 0, потому что двоичное представление 5 - это 101, которое содержит блок последовательных нулей длины 1.
Начиная с n = 0, первые несколько членов последовательности Баума – Свита:
Историческая мотивация
Свойства последовательности были впервые изучены Леонардом Э. Баумом и Мелвином М. Свитом в 1976 году. [2] В 1949 году Хинчин предположил, что не существует неквадратичного алгебраического действительного числа с ограниченными частными частными в его разложении в непрерывную дробь. . Контрпример к этой гипотезе до сих пор не известен. [3] [4] Статья Баума и Свита показала, что такое же ожидание не выполняется для алгебраических степенных рядов. Они привели пример кубического степенного ряда вчастные частные которых ограничены. (Степень степенного ряда в результате Баума и Свита аналогична степени расширения поля, связанного с алгебраическим вещественным числом в гипотезе Хинчина.)
Одна из серий, рассмотренных в статье Баума и Свита, является корнем
Авторы показывают, что по лемме Гензеля существует единственный такой корень в потому что сокращение определяющего уравнения по модулю дает , которая учитывается как
Они продолжают доказывать, что этот единственный корень имеет частные частные степени . Перед тем как это сделать, они заявляют (в примечании к теореме 2, стр. 598) [2], что корень можно записать в виде
где а также для тогда и только тогда, когда двоичное разложение содержит только блоки четной длины с. Это источник последовательности Баума – Свита.
Мкауар [6] и Яо [7] доказали, что частные частные непрерывной дроби длявыше не образуют автоматической последовательности. [8] Однако последовательность частных частных может быть порождена неоднородным морфизмом. [9]
Характеристики
Последовательность Баума – Свита может быть сгенерирована автоматом с 3 состояниями . [9]
Значение члена b n в последовательности Баума – Свита можно найти рекурсивно следующим образом. Если n = m · 4 k , где m не делится на 4 (или равно 0), то
Таким образом, b 76 = b 9 = b 4 = b 0 = 1, что можно проверить, наблюдая, что двоичное представление числа 76, равное 100 1100, не содержит последовательных блоков нулей нечетной длины.
Слово Баума – Свита 1101100101001001 ..., которое создается путем конкатенации терминов последовательности Баума – Свита, является фиксированной точкой правил морфизма или подстановки строк.
- 00 → 0000
- 01 → 1001
- 10 → 0100
- 11 → 1101
следующим образом:
- 11 → 1101 → 11011001 → 1101100101001001 → 11011001010010011001000001001001 ...
Из правил морфизма видно, что слово Баума – Свита содержит блоки последовательных нулей любой длины ( b n = 0 для всех 2 k целых чисел в диапазоне 5,2 k ≤ n <6,2 k ), но оно не содержит блоков три последовательных единицы.
Если говорить более кратко, то по небольшой теореме Кобхэма слово Баума – Свита может быть выражено как кодирование применяется к неподвижной точке равномерного морфизма . Действительно, морфизм
и кодирование
генерировать слово таким образом. [10]
Заметки
- ^ Weisstein, Эрик В. «Баум – Сладкая последовательность» . MathWorld .
- ^ а б в Баум, Леонард Э .; Сладкий, Мелвин М. (1976). «Непрерывные дроби алгебраических степенных рядов в характеристике 2». Анналы математики . 103 (3): 593–610. DOI : 10.2307 / 1970953 . JSTOR 1970953 .
- ^ Вальдшмидт, М. (2009). «Слова и трансцендентность». В WWL Чен; WT Gowers; Х. Хальбертштам; В. М. Шмидт; RC Vaughan (ред.). Аналитическая теория чисел: Очерки в честь Клауса Рота (PDF) . Издательство Кембриджского университета. Раздел 31, с. 449–470.
- ^ Хинчин А.И. (1964). Непрерывные дроби . Издательство Чикагского университета.
- ^ Graham Эверест, Альф ван дер Poorten, Игорь Шпарлинский, Томас Уорд рекуррентные последовательности AMS 2003, стр 236.
- ^ Мкауар, М. (1995). "Sur le développement en Fraction continue de la série de Baum et Sweet" . Бык. Soc. Математика. Франция . 123 (3): 361–374. DOI : 10,24033 / bsmf.2264 .
- ^ Яо, Ж.-Й. (1997). «Критерии неавтоматических и других приложений» . Acta Arith . 80 (3): 237–248. DOI : 10,4064 / аа-80-3-237-248 .
- ^ Allouche и Shallit (2003) стр 210.
- ^ а б Allouche, J.-P. (1993). «Конечные автоматы и арифметика». Séminaire Lotharingien de Combinatoire : 23.
- ^ Allouche и Shallit (2003) стр 176.
Рекомендации
- Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl 1086.11015 .