Многочлены Шапиро
Многочлены Шапиро — последовательность многочленов, впервые изученная Гарольдом Шапиро в 1951 году при рассмотрении величин некоторых специальных тригонометрических сумм. С точки зрения обработки сигналов, полиномы Шапиро обладают хорошими автокорреляционными свойствами, и их значения в единичном круге малы. Первые члены последовательности:
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 . . . {displaystyle {egin{aligned}P_{1}(x)&{}=1+xP_{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-xQ_{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 ) {displaystyle P_{n}(z)} могут быть получены из последовательности Рудина-Шапиро a n {displaystyle a_{n}} ( a n = 1 {displaystyle a_{n}=1} , если число подстрок 11 в двоичной записи числа n четно, и a n = − 1 {displaystyle a_{n}=-1} иначе (OEIS A020985)). Так, a 0 = 1 , a 1 = 1 , a 2 = 1 , a 3 = − 1 {displaystyle a_{0}=1,a_{1}=1,a_{2}=1,a_{3}=-1} и т. д.
P n {displaystyle P_{n}} есть частичная сумма порядка 2 n − 1 {displaystyle 2^{n}-1} степенного ряда f ( z ) = a 0 + a 1 z + a 2 z 2 + . . . {displaystyle f(z)=a_{0}+a_{1}z+a_{2}z^{2}+...}
Последовательность Рудина-Шапиро a n {displaystyle a_{n}} имеет структуру, схожую с фрактальной — например, a n = a 2 n {displaystyle a_{n}=a_{2n}} , то есть подпоследовательность a 0 , a 2 , a 4 , . . . {displaystyle a_{0},a_{2},a_{4},...} совпадает с исходной { a n } {displaystyle {a_{n}}} . Это свойство приводит к примечательным функциональным уравнениям, которым удовлетворяет f ( z ) {displaystyle f(z)} .
Дополнительные полиномы Шапиро, Q n ( z ) {displaystyle Q_{n}(z)} , могут быть определены через эту же последовательность, через отношение Q n ( z ) = ( − 1 ) n z 2 n P n ( − 1 z ) {displaystyle Q_{n}(z)=(-1)^{n}z^{2n}P_{n}({frac {-1}{z}})} , или же через рекуррентные формулы:
P 0 ( z ) = 1 ; Q 0 ( z ) = 1 ; {displaystyle P_{0}(z)=1;~~Q_{0}(z)=1;} P n + 1 ( z ) = P n ( z ) + z 2 n Q n ( z ) ; {displaystyle 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 ) . {displaystyle Q_{n+1}(z)=P_{n}(z)-z^{2^{n}}Q_{n}(z).}Свойства
Дополнительная последовательность, Q n {displaystyle Q_{n}} , соответствующая P n {displaystyle P_{n}} , однозначно определяется следующими свойствами:
Наиболее интересным свойством последовательности P n {displaystyle P_{n}} является то, что модуль значения P n ( z ) {displaystyle P_{n}(z)} на единичной окружности ограничен 2 n + 1 {displaystyle {sqrt {2^{n+1}}}} , что по порядку равно L 2 {displaystyle L_{2}} норме P n {displaystyle P_{n}} . Многочлены с коэффициентами ± 1 {displaystyle pm 1} , чей максимум модуля на единичной окружности близок к среднему значению модуля, полезны в различных приложениях теории коммуникаций (например, форма антенны и сжатие данных). Свойство (3) показывает, что (P, Q) образуют пару Голея.
Другие свойства этих многочленов:
P n + 1 ( z ) = P n ( z 2 ) + z P n ( − z 2 ) ; {displaystyle P_{n+1}(z)=P_{n}(z^{2})+zP_{n}(-z^{2});} Q n + 1 ( z ) = Q n ( z 2 ) + z Q n ( − z 2 ) ; {displaystyle 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 ; {displaystyle 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 2 k + 1 ) + z 2 k Q k ( z ) P n ( − z 2 k + 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});} P n ( 1 ) = 2 ⌊ ( n + 1 ) / 2 ⌋ ; P n ( − 1 ) = ( 1 + ( − 1 ) n ) 2 ⌊ n / 2 ⌋ − 1 . {displaystyle P_{n}(1)=2^{lfloor (n+1)/2 floor };{~}{~}P_{n}(-1)=(1+(-1)^{n})2^{lfloor n/2 floor -1}.}