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

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

$\begin{array}{cc}{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{array}$,

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

Построение

Полиномы Шапиро $P_n(z)$ могут быть получены из последовательности Рудина-Шапиро $a_n$ ($a_n=1$, если число подстрок 11 в двоичной записи числа n четно, и $a_n=-1$ иначе (OEIS Шаблон:OEIS2C)). Так, $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 ℂ,|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)+z{P}_n(-z^2);$

$Q_{n+1}(z)=Q_n(z^2)+z{Q}_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}.$

См. также

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

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

• Шаблон:Книга Chapter 4.