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

Многочлены Шапиро — последовательность многочленов, впервые изученная Гарольдом Шапиро в 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}.}$

См. также

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