В математике последовательность Рудина – Шапиро , также известная как последовательность Голея – Рудина – Шапиро , представляет собой бесконечную 2- автоматную последовательность, названную в честь Марселя Голея , Вальтера Рудина и Гарольда С. Шапиро , которые независимо исследовали ее свойства. [1]
Определение
Каждый член последовательности Рудина – Шапиро либо или же . Позволять быть количеством (возможно перекрывающихся) вхождений блока в двоичном разложении . Если двоичное разложение дан кем-то
тогда
Последовательность Рудина – Шапиро. тогда определяется как
Таким образом если даже и если странно. [2] [3] [4]
Последовательность известна как полная последовательность Рудина – Шапиро, и начиная с , его первые несколько терминов:
и соответствующие условия последовательности Рудина – Шапиро:
- +1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, .. . (последовательность A020985 в OEIS )
Например, а также потому что двоичное представление 6 - 110, что содержит одно вхождение 11; тогда как а также потому что двоичное представление 7 - 111, которое содержит два (перекрывающихся) вхождения 11.
Историческая мотивация
Последовательность Рудина – Шапиро была открыта независимо Голеем, [5] [6] Рудиным [7] и Шапиро. [8] Ниже приводится описание мотивации Рудина. В анализе Фурье часто обращают внимание нанорма о измеримой функции . Эта норма определяется
Можно доказать, что для любой последовательности с каждым в ,
Более того, почти для каждой последовательности с каждым в ,
Однако последовательность Рудина – Шапиро удовлетворяет более жесткой оценке: [10] существует постоянная такой, что
Предполагается, что можно взять , [11] но пока известно, что, [12] лучшая опубликованная верхняя граница в настоящее время. [13] Пустьбыть п -м Шапиро полинома . Потом, когда, указанное выше неравенство дает оценку . Совсем недавно были даны оценки величины коэффициентов при где . [14]
Шапиро пришел к последовательности, потому что многочлены
где - последовательность Рудина – Шапиро, имеют модуль, ограниченный на комплексной единичной окружности соотношением . Более подробно это обсуждается в статье о полиномах Шапиро . Мотивация Голея была аналогичной, хотя его интересовали приложения к спектроскопии и он публиковался в журнале по оптике.
Характеристики
Последовательность Рудина – Шапиро может быть сгенерирована автоматом с 4 состояниями, принимающим двоичные представления неотрицательных целых чисел в качестве входных данных. [15] Следовательно, последовательность является 2-автоматической, поэтому по малой теореме Кобхэма существует 2-равномерный морфизм с фиксированной точкой и кодирование такой, что , где - последовательность Рудина – Шапиро. Однако последовательность Рудина – Шапиро не может быть выражена только как неподвижная точка некоторого однородного морфизма. [16]
Есть рекурсивное определение [3]
Значения членов a n и b n в последовательности Рудина – Шапиро могут быть найдены рекурсивно следующим образом. Если n = m · 2 k, где m нечетно, то
Таким образом, a 108 = a 13 + 1 = a 3 + 1 = a 1 + 2 = a 0 + 2 = 2, что можно проверить, наблюдая, что двоичное представление 108, то есть 1101100, содержит две подстроки 11. Итак, b 108 = (−1) 2 = +1.
2-однородный морфизм это требует кодирования для генерации последовательности Рудина-Шапиро следующая:
Слово Рудина – Шапиро +1 +1 +1 −1 +1 +1 −1 +1 +1 +1 +1 −1 −1 −1 +1 −1 ..., которое создается путем конкатенации членов Последовательность Рудина – Шапиро, является фиксированной точкой правил морфизма или подстановки строк.
- +1 +1 → +1 +1 +1 -1
- +1 -1 → +1 +1 -1 +1
- −1 +1 → −1 −1 +1 −1
- −1 −1 → −1 −1 −1 +1
следующим образом:
- +1 +1 → +1 +1 +1 −1 → +1 +1 +1 −1 +1 +1 −1 +1 → +1 +1 +1 −1 +1 +1 −1 +1 +1 + 1 +1 -1 -1 -1 +1 -1 ...
Из правил морфизма видно, что строка Рудина – Шапиро содержит не более четырех последовательных +1 и не более четырех последовательных −1.
Последовательность частичных сумм последовательности Рудина – Шапиро, определяемая формулой
с ценностями
можно показать, что удовлетворяет неравенству
Если обозначает последовательность Рудина – Шапиро на , который задается , то производящая функция
удовлетворяет
делая его алгебраическим как формальный степенной ряд над . [17] Алгебраичность над следует из 2-автоматности по теореме Кристола .
Последовательность Рудина – Шапиро по квадратам. нормально. [18]
Полная последовательность Рудина – Шапиро удовлетворяет следующему результату о равномерном распределении. Если, то существует такой, что
откуда следует, что равномерно распределена по модулю для всех иррациональных . [19]
Связь с одномерной моделью Изинга
Пусть двоичное разложение n задается формулой
где . Напомним, что полная последовательность Рудина – Шапиро определяется формулой
Позволять
Тогда пусть
Наконец, пусть
Напомним, что статистическая сумма одномерной модели Изинга может быть определена следующим образом. Исправить представляющий количество сайтов, и фиксируем константы а также представляющие константу связи и напряженность внешнего поля соответственно. Выберите последовательность весов с каждым . Для любой последовательности вращений с каждым , определим его гамильтониан как
Позволять быть константой, представляющей температуру, которая может быть произвольным ненулевым комплексным числом, и установить где - постоянная Больцмана . Статистическая сумма определяется как
Тогда у нас есть
где весовая последовательность удовлетворяет для всех . [20]
Смотрите также
Заметки
- ^ a b Джон Бриллхарт и Патрик Мортон, победители Премии Лестера Р. Форда 1997 года (1996). «Пример математического исследования: последовательность Голая – Рудина – Шапиро» . Амер. Математика. Ежемесячно . 103 : 854–869. DOI : 10.2307 / 2974610 .
- ^ Вайсштейн, Эрик В. "Последовательность Рудина – Шапиро" . MathWorld .
- ^ a b Пифей Фогг (2002) с.42
- ^ Эверест и др. (2003) стр.234
- ^ Голай, MJE (1949). «Многощелевая спектрометрия». J. Optical Soc. Амер . 39 (437–444).
- ^ Голай, MJE (1951). «Статическая многощелевая спектрометрия и ее применение для панорамного отображения инфракрасных спектров». J. Optical Soc. Амер . 41 : 468–472.
- ^ Рудин, В. (1959). «Некоторые теоремы о коэффициентах Фурье». Proc. Амер. Математика. Soc. 10 : 855–859.
- ^ Шапиро, HS (1952). «Экстремальные задачи для многочленов и степенных рядов». Магистерская работа, Массачусетский технологический институт .
- ^ Салем, Р.; Зигмунд, А. (1954). «Некоторые свойства тригонометрических рядов, члены которых имеют случайные знаки». Acta Mathematica . 91 : 245–301.
- ^ Allouche и Shallit (2003) стр. 78–79
- ^ Allouche и Shallit (2003) стр. 122
- ^ Brillhart, J .; Мортон, П. (1978). "Über Summen von Rudin – Shapiroschen Koeffizienten". Иллинойс J. Math. 22 : 126–148.
- ^ Саффари, Б. (1986). "Единая функция вне пределов сюиты Рудена-Шапиро". CR Acad. Sci. Париж . 303 : 97–100.
- ^ Allouche, J.-P .; Choi, S .; Дениз, А .; Erdélyi, T .; Саффари, Б. (2019). "Границы коэффициентов автокорреляции многочленов Рудина-Шапиро". Математический анализ . 45 : 705–726.
- ^ Конечные автоматы и арифметика , Жан-Поль Аллуш
- ^ Allouche и Shallit (2003) стр. 192
- ^ Allouche и Shallit (2003) стр. 352
- ^ Мюлльнер К. «Последовательность Рудина – Шапиро и подобные последовательности нормальны вдоль квадратов». Канадский математический журнал . 70 (5): 1096–1129.
- ^ Аллуш и Шаллит стр. 462–464
- ^ Allouche и Shallit (2003) стр. 457–461
Рекомендации
- Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета . ISBN 978-0-521-82332-6. Zbl 1086.11015 .
- Эверест, Грэм; ван дер Поортен, Альф; Шпарлинский, Игорь; Уорд, Томас (2003). Повторяющиеся последовательности . Математические обзоры и монографии. 104 . Провиденс, Род-Айленд : Американское математическое общество . ISBN 0-8218-3387-1. Zbl 1033.11006 .
- Пифей Фогг, Н. (2002). Берте, Валери ; Ференци, Себастьен; Mauduit, Christian; Сигель, Энн (ред.). Подстановки в динамике, арифметике и комбинаторике . Конспект лекций по математике. 1794 . Берлин: Springer-Verlag . ISBN 3-540-44141-7. Zbl 1014.11015 .
- Мендес Франция, Мишель (1990). «Последовательность Рудина-Шапиро, цепь Изинга и раскладывание бумаги». У Берндта, Брюса К .; Даймонд, Гарольд Дж .; Хальберштам, Хейни ; и другие. (ред.). Аналитическая теория чисел. Материалы конференции в честь Пола Т. Бейтмана, состоявшейся 25–27 апреля 1989 г. в Университете Иллинойса, Урбана, Иллинойс (США) . Успехи в математике. 85 . Бостон: Биркхойзер. С. 367–390. ISBN 0-8176-3481-9. Zbl 0724.11010 .