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

Многочлены Шапиро — последовательность многочленов, впервые изученная Гарольдом Шапиро в 1951 году при рассмотрении величин некоторых специальных тригонометрических сумм[1]. С точки зрения обработки сигналов, полиномы Шапиро обладают хорошими автокорреляционными свойствами[2], и их значения в единичном круге малы. Первые члены последовательности:

${\displaystyle {\begin{aligned}P_{1}(x)&{}=1+x\\P_{2}(x)&{}=1+x+x^{2}-x^{3}\\P_{3}(x)&{}=1+x+x^{2}-x^{3}+x^{4}+x^{5}-x^{6}+x^{7}\\...\\Q_{1}(x)&{}=1-x\\Q_{2}(x)&{}=1+x-x^{2}+x^{3}\\Q_{3}(x)&{}=1+x+x^{2}-x^{3}-x^{4}-x^{5}+x^{6}-x^{7}\\...\\\end{aligned}}}$,

где вторая последовательность, Q, называется дополнительной к первой последовательности, P.

Построение

Полиномы Шапиро ${\displaystyle P_{n}(z)}$ могут быть получены из последовательности Рудина-Шапиро ${\displaystyle a_{n}}$ (${\displaystyle a_{n}=1}$, если число подстрок 11 в двоичной записи числа n четно, и ${\displaystyle a_{n}=-1}$ иначе (OEIS A020985)). Так, ${\displaystyle a_{0}=1,a_{1}=1,a_{2}=1,a_{3}=-1}$ и т. д.

${\displaystyle P_{n}}$ есть частичная сумма порядка ${\displaystyle 2^{n}-1}$ степенного ряда ${\displaystyle f(z)=a_{0}+a_{1}z+a_{2}z^{2}+...}$

Последовательность Рудина-Шапиро ${\displaystyle a_{n}}$ имеет структуру, схожую с фрактальной — например, ${\displaystyle a_{n}=a_{2n}}$, то есть подпоследовательность ${\displaystyle a_{0},a_{2},a_{4},...}$ совпадает с исходной ${\displaystyle \{a_{n}\}}$. Это свойство приводит к примечательным функциональным уравнениям, которым удовлетворяет ${\displaystyle f(z)}$.

Дополнительные полиномы Шапиро, ${\displaystyle Q_{n}(z)}$, могут быть определены через эту же последовательность, через отношение ${\displaystyle Q_{n}(z)=(-1)^{n}z^{2n}P_{n}({\frac {-1}{z}})}$, или же через рекуррентные формулы:

${\displaystyle P_{0}(z)=1;~~Q_{0}(z)=1;}$

${\displaystyle P_{n+1}(z)=P_{n}(z)+z^{2^{n}}Q_{n}(z);}$

${\displaystyle Q_{n+1}(z)=P_{n}(z)-z^{2^{n}}Q_{n}(z).}$

Свойства

Дополнительная последовательность, ${\displaystyle Q_{n}}$, соответствующая ${\displaystyle P_{n}}$, однозначно определяется следующими свойствами:

1. Степень ${\displaystyle Q_{n}}$ равна ${\displaystyle 2^{n}-1}$.
2. Коэффициенты ${\displaystyle Q_{n}}$ равны ${\displaystyle \pm 1}$, коэффициент при нулевой степени равен 1.
3. Равенство ${\displaystyle |P_{n}(z)|^{2}+|Q_{n}(z)|^{2}=2^{n+1}}$ выполнено на всей единичной окружности ${\displaystyle z\in \mathbb {C} ,|z|=1}$.

Наиболее интересным свойством последовательности ${\displaystyle P_{n}}$ является то, что модуль значения ${\displaystyle P_{n}(z)}$ на единичной окружности ограничен ${\displaystyle {\sqrt {2^{n+1}}}}$, что по порядку равно ${\displaystyle L_{2}}$-норме ${\displaystyle P_{n}}$. Многочлены с коэффициентами ${\displaystyle \pm 1}$, максимум модуля которых на единичной окружности близок к среднему значению модуля, полезны в различных приложениях теории коммуникаций (например, форма антенны и сжатие данных). Свойство (3) показывает, что (P, Q) образуют пару Голея.

Другие свойства этих многочленов[3]:

${\displaystyle P_{n+1}(z)=P_{n}(z^{2})+zP_{n}(-z^{2});}$

${\displaystyle Q_{n+1}(z)=Q_{n}(z^{2})+zQ_{n}(-z^{2});}$

${\displaystyle P_{n}(z)P_{n}(1/z)+Q_{n}(z)Q_{n}(1/z)=2^{n+1};}$

${\displaystyle P_{n+k+1}(z)=P_{k}(z)P_{n}(z^{2k+1})+z^{2k}Q_{k}(z)P_{n}(-z^{2k+1});}$

${\displaystyle P_{n}(1)=2^{\lfloor (n+1)/2\rfloor };{~}{~}P_{n}(-1)=(1+(-1)^{n})2^{\lfloor n/2\rfloor -1}.}$

См. также

• Многочлены Литлвуда

Примечания

1. John Brillhart and L. Carlitz. Note on the Shapiro polynomials (англ.) // Proceedings of the American Mathematical Society : journal. — Proceedings of the American Mathematical Society, Vol. 25, No. 1, 1970. — May (vol. 25, no. 1). — P. 114—118. — doi:10.2307/2036537.
2. Somaini, U. Binary sequences with good correlation properties (англ.) // Electronics Letters^[англ.] : journal. — 1975. — 26 June (vol. 11, no. 13). — P. 278—279. — doi:10.1049/el:19750211.
3. J. Brillhart; J.S. Lomont, P. Morton. Cyclotomic properties of the Rudin–Shapiro polynomials (англ.) // J. Reine Angew. Math. : journal. — 1976. — Vol. 288. — P. 37—65.

Список литературы

• Borwein, Peter B^[англ.]. Computational Excursions in Analysis and Number Theory (англ.). — Springer, 2002. — ISBN 0387954449. Chapter 4.