View source for Shapiro polynomials

In mathematics, the '''Shapiro polynomials''' are a [[Polynomial sequence|sequence of polynomials]] which were first studied by [[Biography:Harold S. Shapiro|Harold S. Shapiro]] in 1951 when considering the magnitude of specific trigonometric sums.<ref>{{Cite journal|title=Note on the Shapiro polynomials|author=John Brillhart and L. Carlitz|journal= Proceedings of the American Mathematical Society|volume=25|date=May 1970|pages=114–118|doi=10.2307/2036537|issue= 1|publisher=Proceedings of the American Mathematical Society, Vol. 25, No. 1|jstor=2036537|doi-access=free}}</ref> In [[Signal processing|signal processing]], the Shapiro polynomials have good [[Autocorrelation|autocorrelation]] properties and their values on the [[Unit circle|unit circle]] are small.<ref>{{Cite journal|url=https://ieeexplore.ieee.org/document/4236729|title=Binary sequences with good correlation properties|author=Somaini, U.|journal=Electronics Letters|volume=11|issue=13|date=June 26, 1975|pages=278–279|doi=10.1049/el:19750211}}</ref>  The first few members of the sequence are:
:<math>
\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}
</math>

where the second sequence, indicated by ''Q'', is said to be ''complementary'' to the first sequence, indicated by ''P''.

==Construction==
The Shapiro polynomials ''P''<sub>''n''</sub>(''z'') may be constructed from the [[Rudin–Shapiro sequence|Golay–Rudin–Shapiro sequence]] ''a''<sub>''n''</sub>, which  equals 1 if the number of pairs of consecutive ones in the binary expansion of ''n'' is even, and &minus;1 otherwise. Thus ''a''<sub>0</sub>&nbsp;=&nbsp;1,  ''a''<sub>1</sub>&nbsp;=&nbsp;1, ''a''<sub>2</sub>&nbsp;=&nbsp;1, ''a''<sub>3</sub>&nbsp;=&nbsp;&minus;1, etc.

The first Shapiro ''P''<sub>''n''</sub>(''z'') is the partial sum of order 2<sup>''n''</sup>&nbsp;&minus;&nbsp;1  (where ''n''&nbsp;=&nbsp;0,&nbsp;1,&nbsp;2,&nbsp;...) of the [[Power series|power series]]

:''f''(''z'') := ''a''<sub>0</sub>  +  ''a''<sub>1</sub>&thinsp;''z''  +  a<sub>2</sub>&thinsp;''z''<sup>2</sup>  +  ...

The Golay–Rudin–Shapiro sequence {''a''<sub>''n''</sub>} has a fractal-like structure &ndash; for example, ''a''<sub>''n''</sub>&nbsp;=&nbsp;''a''<sub>2''n''</sub> &ndash;  which implies that the subsequence (''a''<sub>0</sub>,&nbsp;''a''<sub>2</sub>,&nbsp;''a''<sub>4</sub>,&nbsp;...) replicates the original sequence {''a''<sub>''n''</sub>}. This in turn leads to remarkable
functional equations satisfied by ''f''(''z'').

The second or complementary Shapiro polynomials ''Q''<sub>''n''</sub>(''z'') may be defined in terms of this sequence, or by the relation ''Q''<sub>''n''</sub>(''z'') = (1-)<sup>''n''</sup>''z''<sup>2<sup>''n''</sup>-1</sup>''P''<sub>''n''</sub>(-1/''z''), or by the recursions

:<math>P_0(z)=1; ~~ Q_0(z) = 1 ; </math>
:<math>P_{n+1}(z) = P_n(z) + z^{2^n} Q_n(z) ; </math>
:<math>Q_{n+1}(z) = P_n(z) - z^{2^n} Q_n(z) . </math>

==Properties==
[[File:Rudin shapiro 8 zeros.svg|thumbnail|right|Zeroes of the polynomial of degree 255]]
The sequence of complementary polynomials ''Q''<sub>''n''</sub> corresponding to the ''P''<sub>''n''</sub> is uniquely characterized by the following properties:
* (i) ''Q''<sub>''n''</sub> is of degree 2<sup>''n''</sup> &minus; 1;
* (ii) the coefficients of ''Q''<sub>''n''</sub> are all 1 or &minus;1, and its constant term equals 1; and
* (iii) the identity  |''P''<sub>''n''</sub>(''z'')|<sup>2</sup>  +  |''Q''<sub>''n''</sub>(''z'')|<sup>2</sup>  =  2<sup>(''n''&thinsp;+&thinsp;1)</sup> holds on the unit circle, where the complex variable ''z'' has absolute value one.

The most interesting property of the {''P''<sub>''n''</sub>} is that the absolute value of ''P''<sub>''n''</sub>(''z'') is bounded on the unit circle by the [[Square root of 2|square root of 2]]<sup>(''n''&thinsp;+&thinsp;1)</sup>, which is on the order
of the L<sup>2</sup> norm of ''P''<sub>''n''</sub>. Polynomials with coefficients from the set {&minus;1,&nbsp;1} whose maximum modulus on the unit circle is close to their mean modulus are useful for various applications in communication theory (e.g., antenna design and [[Data compression|data compression]]).  Property (iii) shows that (''P'',&nbsp;''Q'') form a Golay pair.

These polynomials have further properties:<ref>{{cite journal | author=J. Brillhart |author2=J.S. Lomont |author3=P. Morton | title=Cyclotomic properties of the Rudin–Shapiro polynomials | journal=J. Reine Angew. Math. | volume=288 | year=1976 | pages=37–65 }}</ref>
:<math> P_{n+1}(z) = P_n(z^2) + z P_n(-z^2) ; \, </math>
:<math> Q_{n+1}(z) = Q_n(z^2) + z Q_n(-z^2) ; \, </math>
:<math>P_n(z) P_n(1/z) + Q_n(z) Q_n(1/z) = 2^{n+1} ; \, </math>
:<math>P_{n+k+1}(z) = P_n(z)P_k(z^{2^{n+1}}) + z^{2^n}Q_n(z)P_k(-z^{2^{n+1}}) ; \, </math>
:<math>P_n(1) = 2^{\lfloor (n+1)/2 \rfloor}; {~}{~} P_n(-1) = (1+(-1)^n)2^{\lfloor n/2 \rfloor - 1} . \, </math>

==See also==
* [[Littlewood polynomial]]s

==Notes==
{{reflist}}

==References==
*{{cite book|last = Borwein|first = Peter B|title = Computational Excursions in Analysis and Number Theory|publisher = Springer|year = 2002|isbn = 978-0-387-95444-8|url = https://books.google.com/books?id=A_ITwN13J6YC|accessdate = 2007-03-30}} Chapter 4.
* {{cite book | zbl=0724.11010 | last=Mendès France | first=Michel | chapter=The Rudin-Shapiro sequence, Ising chain, and paperfolding | pages=367–390 | editor1-last=Berndt | editor1-first=Bruce C. | editor1-link=Bruce C. Berndt | editor2-last=Diamond | editor2-first=Harold G. | editor3-last=Halberstam | editor3-first=Heini | editor3-link=Heini Halberstam |display-editors = 3 | editor4-last=Hildebrand | editor4-first=Adolf | title=Analytic number theory. Proceedings of a conference in honor of Paul T. Bateman, held on April 25-27, 1989, at the University of Illinois, Urbana, IL (USA) | series=Progress in Mathematics | volume=85 | location=Boston | publisher=Birkhäuser | year=1990 | isbn=978-0-8176-3481-0 }}

[[Category:Fourier analysis]]
[[Category:Digital signal processing]]
[[Category:Polynomials]]

{{Sourceattribution|Shapiro polynomials}}