Рудин-Шапиро реттілігі - Rudin–Shapiro sequence

Жылы математика, Рудин-Шапиро реттілігі, деп те аталады Голай-Рудин-Шапиро тізбегі, шексіз 2-автоматты реттілік атындағы Марсель Голай, Вальтер Рудин, және Гарольд С. Шапиро, оның қасиеттерін тәуелсіз зерттеген.^[1]

Анықтама

Рудин-Шапиро дәйектілігінің әр мерзімі бір-біріне тең ${displaystyle 1}$ немесе ${displaystyle -1}$. Келіңіздер ${displaystyle e_ {2; 11} (n)}$ блоктың (қайталануы мүмкін) пайда болу саны болуы керек ${displaystyle 11}$ екілік кеңеюінде ${displaystyle n}$. Егер екілік кеңею болса ${displaystyle n}$ арқылы беріледі

${displaystyle n = sum _ {kgeq 0} эпсилон _ {k} (n) 2 ^ {k},}$

содан кейін

${displaystyle u_ {n} = sum _ {kgeq 0} эпсилон _ {k} (n) эпсилон _ {k + 1} (n).}$

Рудин-Шапиро тізбегі ${displaystyle (r_ {n}) _ {ngeq 0}}$ содан кейін анықталады

${displaystyle r_ {n} = (- 1) ^ {e_ {2; 11} (n)}.}$

Осылайша ${displaystyle r_ {n} = 1}$ егер ${displaystyle u_ {n}}$ тең және ${displaystyle r_ {n} = - 1}$ егер ${displaystyle u_ {n}}$ тақ.^[2][3][4]

Кезектілік ${displaystyle e_ {2; 11} (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, -1, .. . (жүйелі A020985 ішінде OEIS )

Мысалға, ${displaystyle u_ {6} = 1}$ және ${displaystyle r_ {6} = - 1}$ өйткені 6-ның екілік көрінісі 110-ға тең, ол 11-дің бір көрінісін қамтиды; ал ${displaystyle u_ {7} = 2}$ және ${displaystyle r_ {7} = 1}$ өйткені 7-нің екілік көрінісі 111-ге тең, ол 11-дің екі (қайталанатын) көрінісін қамтиды.

Тарихи мотивация

Рудин-Шапиро дәйектілігін Голай дербес ашты^[5][6], Рудин^[7], және Шапиро^[8]. Төменде Рудиннің уәждемесінің сипаттамасы берілген. Жылы Фурье анализі, көбінесе ${displaystyle L ^ {2}}$ норма а өлшенетін функция ${displaystyle fcolon [0,2pi) o [0,2pi)}$. Бұл норма анықталады

${displaystyle || f || _ {2} = сол жақ ({frac {1} {2pi}} int _ {0} ^ {2pi} | f (t) | ^ {2}, mathrm {d} тығыз) ^ {1/2}.}$

Мұны кез-келген дәйектілік үшін дәлелдей алады ${displaystyle (a_ {n}) _ {ngeq 0}}$ әрқайсысымен ${displaystyle a_ {n}}$ жылы ${displaystyle {1, -1}}$,

${displaystyle sup _ {xin mathbb {R}} left | sum _ {0leq n$

Сонымен қатар, кез-келген дәйектілік үшін ${displaystyle (a_ {n}) _ {ngeq 0}}$ әрқайсысымен ${displaystyle a_ {n}}$ ішінде ${displaystyle {-1,1}}$,

${displaystyle sup _ {xin mathbb {R}} left | sum _ {0leq n$^[9]

Алайда, Рудин-Шапиро дәйектілігі ${displaystyle (r_ {n}) _ {ngeq 0}}$ неғұрлым тығыз байланыстырады^[10]: тұрақты бар ${displaystyle C> 0}$ осындай

${displaystyle sup _ {xin mathbb {R}} left | sum _ {0leq n$

Болжам бойынша, біреуі алады ${displaystyle C = {sqrt {6}}}$^[11], бірақ бұл белгілі болғанымен ${displaystyle Cgeq {sqrt {6}}}$^[12], қазіргі уақытта ең жақсы жарияланған жоғарғы шегі ${displaystyle Cleq (2+ {sqrt {2}}) {sqrt {3/5}}}$.^[13] Келіңіздер ${displaystyle P_ {n}}$ болуы n-шы Шапиро көпмүшесі. Содан кейін, қашан ${displaystyle N = 2 ^ {n} -1}$, жоғарыдағы теңсіздік шекараны береді ${displaystyle sup _ {xin mathbb {R}} | P_ {n} (e ^ {ix}) |}$. Жақында коэффициенттерінің шамалары үшін де шектер берілді ${displaystyle | P_ {n} (z) | ^ {2}}$ қайда ${displaystyle | z | = 1}$.^[14]

Шапиро қатарға келді, өйткені көпмүшелер

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

қайда ${displaystyle (r_ {i}) _ {igeq 0}}$ - Рудин-Шапиро тізбегі, абсолюттік мәні бойынша күрделі бірлік шеңберімен шектелген ${displaystyle 2 ^ {frac {n + 1} {2}}}$. Бұл туралы мақалада толығырақ талқыланады Шапиро көпмүшелері. Голайдың мотивациясы ұқсас болды, дегенмен ол өтініштермен айналысқан спектроскопия және оптика журналында жарияланған.

Қасиеттері

Рудин-Шапиро тізбегін 4 күй тудыруы мүмкін автомат теріс емес бүтін сандардың екілік көріністерін кіріс ретінде қабылдау.^[15] Осылайша, реттілік 2-автоматты болып табылады, сондықтан Кобхэмнің кішкентай теоремасы бар а 2-біркелкі морфизм ${displaystyle varphi}$ белгіленген нүктемен ${displaystyle w}$ және кодтау ${displaystyle au}$ осындай ${displaystyle r = au (w)}$, қайда ${displaystyle r}$ бұл Рудин-Шапиро тізбегі. Алайда, Рудин-Шапиро дәйектілігі тек біркелкі морфизмнің бекітілген нүктесі ретінде көрсетілуі мүмкін емес.^[16]

Рекурсивті анықтама бар^[3]

${displaystyle {egin {case} b_ {2n} & = b_ {n} b_ {2n + 1} & = (- 1) ^ {n} b_ {n} end {case}}}$

Терминдердің мәндері а_n және б_n Рудин-Шапиро дәйектілігінде рекурсивті келесі түрде табуға болады. Егер n = м·2^к қайда м онда тақ

${displaystyle a_ {n} = {egin {case} a _ {(m-1) / 4} & {ext {if}} mequiv 1 {pmod {4}} a _ {(m-1) / 2} + 1 & {ext {if}} mequiv 3 {pmod {4}} end {case}}}$

${displaystyle b_ {n} = {egin {case} b _ {(m-1) / 4} & {ext {if}} mequiv 1 {pmod {4}} - b _ {(m-1) / 2} & {ext {if}} mequiv 3 {pmod {4}} end {case}}}$

Осылайша а₁₀₈ = а₁₃ + 1 = а₃ + 1 = а₁ + 2 = а₀ + 2 = 2, мұны 1101100 болатын 108 екілік екіленуі екі қосалқы жолдан тұратынын байқау арқылы тексеруге болады. б₁₀₈ = (−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 ...

Морфизм ережелерінен Рудин-Шапиро жолында ең көбі қатарынан + 1 және ең көбі қатарынан төрт −1 болатынын көруге болады.

-Мен анықталған Рудин-Шапиро дәйектілігінің ішінара қосындыларының реттілігі

${displaystyle s_ {n} = sum _ {k = 0} ^ {n} b_ {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}}$^[1]

Егер ${displaystyle (s_ {n}) _ {ngeq 0}}$ Рудин-Шапиро дәйектілігін білдіреді ${displaystyle {0,1}}$арқылы беріледі ${displaystyle s_ {n} equiv e_ {2; 11} (n) {pmod {2}}}$, содан кейін генерациялау функциясы

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

қанағаттандырады

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

оны алгебралық етіп, қуаттың ресми сериясы ретінде қабылдады ${displaystyle mathbb {F} _ {2} (X)}$.^[17] Алгебралығы ${displaystyle S (X)}$ аяқталды ${displaystyle mathbb {F} _ {2} (X)}$ -ның 2-автоматтығынан туындайды ${displaystyle (s_ {n}) _ {ngeq 0}}$ арқылы Кристол теоремасы.

Квадраттар бойындағы Рудин-Шапиро тізбегі ${displaystyle (r_ {n ^ {2}}) _ {ngeq 0}}$ бұл қалыпты жағдай.^[18]

Толық Рудин-Шапиро дәйектілігі келесі біркелкі тарату нәтижесін қанағаттандырады. Егер ${displaystyle xin mathbb {R} setminus mathbb {Z}}$, содан кейін бар ${displaystyle альфа = (0,1) ішіндегі альфа (х)}$ осындай

${displaystyle sum _ {n$

мұны білдіреді ${displaystyle (xu_ {n}) _ {ngeq 0}}$ біркелкі үлестірілген модуль болып табылады ${displaystyle 1}$ барлық қисынсыздар үшін ${displaystyle x}$.^[19]

Бір өлшемді Ising моделімен байланыс

N-дің екілік кеңеюі келесідей болсын

${displaystyle n = sum _ {kgeq 0} эпсилон _ {k} (n) 2 ^ {k}}$

қайда ${displaystyle epsilon _ {k} (n) in {0,1}}$. Еске салайық, Рудин-Шапиро толық тізбегі анықталады

${displaystyle u (n) = sum _ {kgeq 0} эпсилон _ {k} (n) эпсилон _ {k + 1} (n).}$

Келіңіздер

${displaystyle {ilde {epsilon}} _ {k} (n) = {egin {case} epsilon _ {k} (n) & {ext {if}} kleq N-1, epsilon _ {0} (n) & {ext {if}} k = N.end {case}}}$

Содан кейін рұқсат етіңіз

${displaystyle u (n, N) = sum _ {0leq k$

Ақырында, рұқсат етіңіз

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

Еске салайық бір өлшемді Ising моделі келесідей анықтауға болады. Түзету ${displaystyle Ngeq 1}$ сайттардың санын көрсететін және тұрақтыларды бекітетін ${displaystyle J> 0}$ және ${displaystyle H> 0}$ сәйкесінше муфтаның тұрақты және сыртқы өріс кернеулігін бейнелейді. Салмақ тізбегін таңдаңыз ${displaystyle eta = (eta _ {0}, нүктелер, eta _ {N-1})}$ әрқайсысымен ${displaystyle eta _ {i} in {-1,1}}$. Айналудың кез-келген реттілігі үшін ${displaystyle sigma = (sigma _ {0}, нүктелер, sigma _ {N-1})}$ әрқайсысымен ${displaystyle sigma _ {i} in {-1,1}}$, оның Гамильтондықты анықтаңыз

${displaystyle H_ {eta} (sigma) = - Jsum _ {0leq k$

Келіңіздер ${displaystyle T}$ температураны білдіретін тұрақты, болуы керек, ол кездейсоқ нөлге тең емес комплекс сан болады және орнатылады ${displaystyle eta = 1 / (kT)}$ қайда ${displaystyle k}$ болып табылады Больцман тұрақтысы. Бөлімнің функциясы арқылы анықталады

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

Сонда бізде бар

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

мұнда салмақ реттілігі ${displaystyle eta = (eta _ {0}, нүктелер, eta _ {N-1})}$ қанағаттандырады ${displaystyle eta _ {i} = 1}$ барлығына ${displaystyle i}$.^[20]

Сондай-ақ қараңыз

• Шапиро көпмүшелері

Ескертулер

Әдебиеттер тізімі

• Аллуш, Жан-Пол; Шаллит, Джеффри (2003). Автоматты тізбектер: теория, қолдану, жалпылау. Кембридж университетінің баспасы. ISBN  978-0-521-82332-6. Zbl  1086.11015.
• Эверест, Грэм; ван дер Пуортен, Альф; Шпарлинский, Игорь; Уорд, Томас (2003). Қайталану реттілігі. Математикалық зерттеулер және монографиялар. 104. Providence, RI: Американдық математикалық қоғам. ISBN  0-8218-3387-1. Zbl  1033.11006.
• Pytheas Fogg, N. (2002). Берте, Валери; Ференцци, Себастиан; Мод, христиан; Зигель, Анна (ред.) Динамика, арифметика және комбинаторикадағы алмастырулар. Математикадан дәрістер. 1794. Берлин: Шпрингер-Верлаг. ISBN  3-540-44141-7. Zbl  1014.11015.
• Мендес Франция, Мишель (1990). «Рудин-Шапиро дәйектілігі, Исинг тізбегі және қағазды бүктеу». Жылы Берндт, Брюс С.; Даймонд, Гарольд Дж.; Хальберштам, Хейни; т.б. (ред.). Аналитикалық сандар теориясы. Пол Тэтмэннің құрметіне 1989 жылы 25-27 сәуірде Иллинойс Университетінде, Урбана, Иллинойс қаласында өткізілген конференция материалдары (АҚШ). Математикадағы прогресс. 85. Бостон: Биркхаузер. 367-390 бб. ISBN  0-8176-3481-9. Zbl  0724.11010.