Последовательность Рудина–Шапиро

В математике последовательность Рудина–Шапиро , также известная как последовательность Голея–Рудина–Шапиро , представляет собой бесконечную 2- автоматную последовательность, названную в честь Марселя Голея , Гарольда С. Шапиро и Уолтера Рудина , которые исследовали ее свойства. ^[1]

Определение

Каждый член последовательности Рудина–Шапиро равен или . Если двоичное разложение задается как ${\displaystyle 1}$ ${\displaystyle -1}$ ${\displaystyle n}$

${\displaystyle n=\sum _{k\geq 0}\epsilon _{k}(n)2^{k},}$

тогда пусть

${\displaystyle u_{n}=\sum _{k\geq 0}\epsilon _{k}(n)\epsilon _{k+1}(n).}$

(Столько же раз блок 11 появляется в двоичном расширении .) ${\displaystyle u_{n}}$ ${\displaystyle n}$

Последовательность Рудина–Шапиро тогда определяется как ${\displaystyle (r_{n})_{n\geq 0}}$

${\displaystyle r_{n}=(-1)^{u_{n}}.}$

Таким образом, если четно, а если нечетно. ^{[2] [3] [4]} ${\displaystyle r_{n}=1}$ ${\displaystyle u_{n}}$ ${\displaystyle r_{n}=-1}$ ${\displaystyle u_{n}}$

Последовательность известна как полная последовательность Рудина–Шапиро, и, начиная с , ее первые несколько членов имеют вид: ${\displaystyle u_{n}}$ ${\displaystyle n=0}$

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, ... (последовательность A014081 в OEIS )

и соответствующие члены последовательности Рудина–Шапиро: ${\displaystyle r_{n}}$

+1, +1, +1, −1, +1, +1, +1, −1, +1, +1, +1, −1, −1, +1, −1, ... (последовательность A020985 в OEIS )

Например, и потому, что двоичное представление числа 6 равно 110, что содержит одно вхождение числа 11; тогда как и потому, что двоичное представление числа 7 равно 111, что содержит два (перекрывающихся) вхождения числа 11. ${\displaystyle u_{6}=1}$ ${\displaystyle r_{6}=-1}$ ${\displaystyle u_{7}=2}$ ${\displaystyle r_{7}=1}$

Историческая мотивация

Последовательность Рудина–Шапиро была введена независимо Голеем, ^{[5] [6]} Рудином, ^[7] и Шапиро. ^[8] Ниже приводится описание мотивации Рудина. В анализе Фурье часто рассматривается норма измеримой функции . Эта норма определяется как ${\displaystyle L^{2}}$ ${\displaystyle f\colon [0,2\pi )\to [0,2\pi )}$

${\displaystyle ||f||_{2}=\left({\frac {1}{2\pi }}\int _{0}^{2\pi }|f(t)|^{2}\,\mathrm {d} t\right)^{1/2}.}$

Можно доказать, что для любой последовательности с каждым из , ${\displaystyle (a_{n})_{n\geq 0}}$ ${\displaystyle a_{n}}$ ${\displaystyle \{1,-1\}}$

${\displaystyle \sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}a_{n}e^{inx}\right|\geq \left|\left|\sum _{0\leq n<N}a_{n}e^{inx}\right|\right|_{2}={\sqrt {N}}.}$

Более того, для почти каждой последовательности, где каждый находится в , ${\displaystyle (a_{n})_{n\geq 0}}$ ${\displaystyle a_{n}}$ ${\displaystyle \{-1,1\}}$

${\displaystyle \sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}a_{n}e^{inx}\right|=O({\sqrt {N\log N}}).}$^[9]

Однако последовательность Рудина–Шапиро удовлетворяет более строгой границе: ^[10] существует константа такая, что ${\displaystyle (r_{n})_{n\geq 0}}$ ${\displaystyle C>0}$

${\displaystyle \sup _{x\in \mathbb {R} }\left|\sum _{0\leq n<N}r_{n}e^{inx}\right|\leq C{\sqrt {N}}.}$

Предполагается, что можно взять , ^[11] но хотя известно, что , ^[12] наилучшая опубликованная верхняя граница в настоящее время . ^[13] Пусть будет n -м полиномом Шапиро . Тогда, когда , указанное выше неравенство дает границу для . Совсем недавно были также даны границы для величины коэффициентов , где . ^[14] ${\displaystyle C={\sqrt {6}}}$ ${\displaystyle C\geq {\sqrt {6}}}$ ${\displaystyle C\leq (2+{\sqrt {2}}){\sqrt {3/5}}}$ ${\displaystyle P_{n}}$ ${\displaystyle N=2^{n}-1}$ ${\displaystyle \sup _{x\in \mathbb {R} }|P_{n}(e^{ix})|}$ ${\displaystyle |P_{n}(z)|^{2}}$ ${\displaystyle |z|=1}$

Шапиро пришел к этой последовательности, потому что многочлены

${\displaystyle P_{n}(z)=\sum _{i=0}^{2^{n}-1}r_{i}z^{i}}$

где — последовательность Рудина–Шапиро, имеет абсолютное значение, ограниченное на комплексной единичной окружности значением . Это обсуждается более подробно в статье о полиномах Шапиро . Мотивация Голея была схожей, хотя он был озабочен приложениями к спектроскопии и публиковался в журнале по оптике. ${\displaystyle (r_{i})_{i\geq 0}}$ ${\displaystyle 2^{\frac {n+1}{2}}}$

Характеристики

Последовательность Рудина–Шапиро может быть сгенерирована 4-позиционным автоматом, принимающим двоичные представления неотрицательных целых чисел в качестве входных данных. ^[15] Последовательность, таким образом, является 2-автоматической, поэтому по малой теореме Кобэма существует 2-однородный морфизм с неподвижной точкой и кодированием таким, что , где — последовательность Рудина–Шапиро. Однако последовательность Рудина–Шапиро не может быть выражена как неподвижная точка некоторого однородного морфизма в одиночку. ^[16] ${\displaystyle \varphi }$ ${\displaystyle w}$ ${\displaystyle \tau }$ ${\displaystyle r=\tau (w)}$ ${\displaystyle r}$

Существует рекурсивное определение ^[3]

${\displaystyle {\begin{cases}r_{2n}&=r_{n}\\r_{2n+1}&=(-1)^{n}r_{n}\end{cases}}}$

Значения членов r _n и u _n в последовательности Рудина–Шапиро можно найти рекурсивно следующим образом. Если n = m ·2 ^k , где m нечетно, то

${\displaystyle u_{n}={\begin{cases}u_{(m-1)/4}&{\text{if }}m\equiv 1{\pmod {4}}\\u_{(m-1)/2}+1&{\text{if }}m\equiv 3{\pmod {4}}\end{cases}}}$

${\displaystyle r_{n}={\begin{cases}r_{(m-1)/4}&{\text{if }}m\equiv 1{\pmod {4}}\\-r_{(m-1)/2}&{\text{if }}m\equiv 3{\pmod {4}}\end{cases}}}$

Таким образом, u ₁₀₈ = u ₁₃ + 1 = u ₃ + 1 = u ₁ + 2 = u ₀ + 2 = 2, что можно проверить, заметив, что двоичное представление числа 108, то есть 1101100, содержит две подстроки 11. И поэтому r ₁₀₈ = (−1) ² = +1.

2-однородный морфизм , требующий кодирования для генерации последовательности Рудина-Шапиро, выглядит следующим образом: ${\displaystyle \varphi }$ ${\displaystyle \tau }$ $${\displaystyle {\begin{aligned}\varphi :a&\to ab\\b&\to ac\\c&\to db\\d&\to dc\end{aligned}}}$$ $${\displaystyle {\begin{aligned}\tau :a&\to 1\\b&\to 1\\c&\to -1\\d&\to -1\end{aligned}}}$$

Слово Рудина–Шапиро +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.

Последовательность частичных сумм последовательности Рудина–Шапиро, определяемая формулой

${\displaystyle s_{n}=\sum _{k=0}^{n}r_{k}\,,}$

с ценностями

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, ... (последовательность A020986 в OEIS )

можно показать, что удовлетворяет неравенству

${\displaystyle {\sqrt {{\frac {3}{5}}n}}<s_{n}<{\sqrt {6n}}{\text{ for }}n\geq 1\,.}$^[1]

Пусть обозначает последовательность Рудина–Шапиро на , в этом случае — это число по модулю 2 вхождений (возможно, перекрывающихся) блока в разложении по основанию 2 . Тогда производящая функция ${\displaystyle (s_{n})_{n\geq 0}}$ ${\displaystyle \{0,1\}}$ ${\displaystyle s_{n}}$ ${\displaystyle 11}$ ${\displaystyle n}$

${\displaystyle S(X)=\sum _{n\geq 0}s_{n}X^{n}}$

удовлетворяет

${\displaystyle (1+X)^{5}S(X)^{2}+(1+X)^{4}S(X)+X^{3}=0,}$

что делает его алгебраическим как формальный степенной ряд над . ^[17] Алгебраичность над следует из 2-автоматичности по теореме Кристола . ${\displaystyle \mathbb {F} _{2}(X)}$ ${\displaystyle S(X)}$ ${\displaystyle \mathbb {F} _{2}(X)}$ ${\displaystyle (s_{n})_{n\geq 0}}$

Последовательность Рудина–Шапиро вдоль квадратов является нормальной. ^[18] ${\displaystyle (r_{n^{2}})_{n\geq 0}}$

Полная последовательность Рудина–Шапиро удовлетворяет следующему результату равномерного распределения. Если , то существует такое, что ${\displaystyle x\in \mathbb {R} \setminus \mathbb {Z} }$ ${\displaystyle \alpha =\alpha (x)\in (0,1)}$

${\displaystyle \sum _{n<N}\exp(2\pi ixu_{n})=O(N^{\alpha })}$

что подразумевает, что равномерно распределено по модулю для всех иррациональных чисел . ^[19] ${\displaystyle (xu_{n})_{n\geq 0}}$ ${\displaystyle 1}$ ${\displaystyle x}$

Связь с одномерной моделью Изинга

Пусть двоичное разложение n будет задано как

${\displaystyle n=\sum _{k\geq 0}\epsilon _{k}(n)2^{k}}$

где . Напомним, что полная последовательность Рудина–Шапиро определяется как ${\displaystyle \epsilon _{k}(n)\in \{0,1\}}$

${\displaystyle u(n)=\sum _{k\geq 0}\epsilon _{k}(n)\epsilon _{k+1}(n).}$

Позволять

${\displaystyle {\tilde {\epsilon }}_{k}(n)={\begin{cases}\epsilon _{k}(n)&{\text{if }}k\leq N-1,\\\epsilon _{0}(n)&{\text{if }}k=N.\end{cases}}}$

Тогда пусть

${\displaystyle u(n,N)=\sum _{0\leq k<N}{\tilde {\epsilon }}_{k}(n){\tilde {\epsilon }}_{k+1}(n).}$

Наконец, позвольте

${\displaystyle S(N,x)=\sum _{0\leq n<2^{N}}\exp(2\pi ixu(n,N)).}$

Напомним, что функция распределения одномерной модели Изинга может быть определена следующим образом. Зафиксируем представляющее число узлов, и зафиксируем константы и представляющие константу связи и напряженность внешнего поля соответственно. Выберем последовательность весов с каждым . Для любой последовательности спинов с каждым , определим ее гамильтониан как ${\displaystyle N\geq 1}$ ${\displaystyle J>0}$ ${\displaystyle H>0}$ ${\displaystyle \eta =(\eta _{0},\dots ,\eta _{N-1})}$ ${\displaystyle \eta _{i}\in \{-1,1\}}$ ${\displaystyle \sigma =(\sigma _{0},\dots ,\sigma _{N-1})}$ ${\displaystyle \sigma _{i}\in \{-1,1\}}$

${\displaystyle H_{\eta }(\sigma )=-J\sum _{0\leq k<N}\eta _{k}\sigma _{k}\sigma _{k+1}-H\sum _{0\leq k<N}\sigma _{k}.}$

Пусть будет константой, представляющей температуру, которая может быть произвольным ненулевым комплексным числом, и задайте где - постоянная Больцмана . Функция распределения определяется как ${\displaystyle T}$ ${\displaystyle \beta =1/(kT)}$ ${\displaystyle k}$

${\displaystyle Z_{N}(\eta ,J,H,\beta )=\sum _{\sigma \in \{-1,1\}^{N}}\exp(-\beta H_{\eta }(\sigma )).}$

Тогда у нас есть

${\displaystyle S(N,x)=\exp \left({\frac {\pi iNx}{2}}\right)Z_{N}\left(1,{\frac {1}{2}},-1,\pi ix\right)}$

где последовательность весов удовлетворяет для всех . ^[20] ${\displaystyle \eta =(\eta _{0},\dots ,\eta _{N-1})}$ ${\displaystyle \eta _{i}=1}$ ${\displaystyle i}$

Смотрите также

• Многочлены Шапиро

Примечания

1. Джон Бриллхарт и Патрик Мортон, победители премии Лестера Р. Форда 1997 года (1996). "Исследование случая в математических исследованиях: последовательность Голея–Рудина–Шапиро". Amer. Math. Monthly . 103 (10): 854–869. doi :10.2307/2974610. JSTOR  2974610.{{cite journal}}: CS1 maint: numeric names: authors list (link)
2. Вайсштейн, Эрик В. «Последовательность Рудина–Шапиро». MathWorld .
3. Pytheas Fogg (2002) стр.42
4. Эверест и др. (2003) стр.234
5. Golay, MJE (1949). «Многощелевая спектрометрия». Журнал оптического общества Америки . 39 (437–444): 437–444. doi :10.1364/JOSA.39.000437. PMID  18152021.
6. Golay, MJE (1951). «Статическая многощелевая спектрометрия и ее применение для панорамного отображения инфракрасных спектров». Журнал оптического общества Америки . 41 (7): 468–472. doi :10.1364/JOSA.41.000468. PMID  14851129.
7. Рудин, В. (1959). «Некоторые теоремы о коэффициентах Фурье». Труды Американского математического общества . 10 (6): 855–859. doi : 10.1090/S0002-9939-1959-0116184-5 .
8. Шапиро, Х.С. (1952). «Экстремальные задачи для полиномов и степенных рядов». Магистерская диссертация, Массачусетский технологический институт .
9. Салем, Р.; Зигмунд, А. (1954). «Некоторые свойства тригонометрических рядов, члены которых имеют случайные знаки». Acta Mathematica . 91 : 245–301. doi : 10.1007/BF02393433 . S2CID  122999383.
10. Аллуш и Шаллит (2003) стр. 78–79
11. Аллуш и Шаллит (2003) стр. 122
12. Бриллхарт, Дж.; Мортон, П. (1978). «Über Summen von Rudin – Shapiroschen Koeffizienten». Иллинойский математический журнал . 22 : 126–148. дои : 10.1215/ijm/1256048841 .
13. Саффари, Б. (1986). «Чрезвычайная функция лежит в сюите Рудина-Шапиро». ЧР акад. наук. Париж . 303 : 97–100.
14. Allouche, J.-P.; Choi, S.; Denise, A.; Erdélyi, T.; Saffari, B. (2019). «Границы коэффициентов автокорреляции полиномов Рудина-Шапиро». Analysis Mathematica . 45 (4): 705–726. arXiv : 1901.06832 . doi : 10.1007/s10476-019-0003-4. S2CID  119168430.
15. Конечные автоматы и арифметика, Жан-Поль Аллуш
16. Аллуш и Шаллит (2003) стр. 192
17. Аллуш и Шаллит (2003) стр. 352
18. Мюлльнер, К. (2018). «Последовательность Рудина–Шапиро и подобные последовательности нормальны вдоль квадратов». Канадский журнал математики . 70 (5): 1096–1129. arXiv : 1704.06472 . doi : 10.4153/CJM-2017-053-1. S2CID  125493369.
19. Аллуш и Шаллит, стр. 462–464.
20. Аллуш и Шаллит (2003) стр. 457–461

Ссылки

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Автоматические последовательности: теория, приложения, обобщения . Cambridge University Press . ISBN 978-0-521-82332-6. Збл  1086.11015.
• Эверест, Грэм; ван дер Поортен, Альф; Шпарлинский, Игорь; Уорд, Томас (2003). Рекуррентные последовательности . Математические обзоры и монографии. Том 104. Провиденс, Род-Айленд : Американское математическое общество . ISBN 0-8218-3387-1. Збл  1033.11006.
• Пифей Фогг, Н. (2002). Берта, Валери ; Ференци, Себастьян; Модуит, Кристиан; Сигел, Энн (ред.). Замены в динамике, арифметике и комбинаторике . Конспект лекций по математике. Том. 1794. Берлин: Springer-Verlag . ISBN 3-540-44141-7. Збл  1014.11015.
• Мендес Франс, Мишель (1990). "Последовательность Рудина-Шапиро, цепь Изинга и складывание бумаги". В Берндт, Брюс К .; Даймонд, Гарольд Г.; Халберстам, Хайни ; и др. (ред.). Аналитическая теория чисел. Труды конференции в честь Пола Т. Бейтмана, состоявшейся 25–27 апреля 1989 г. в Иллинойсском университете, Урбана, Иллинойс (США) . Прогресс в математике. Т. 85. Бостон: Birkhäuser. С. 367–390. ISBN 0-8176-3481-9. Збл  0724.11010.