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

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

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

где вторая последовательность, 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 \C, |z| = 1$.

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

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

$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} . \,$

См. также

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

Примечания

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

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

• Borwein Peter B Computational Excursions in Analysis and Number Theory. — Springer. — ISBN 0387954449 Chapter 4.