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

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

${\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.

Построение

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

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

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

См. также

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

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

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