View source for Differential equations of addition

In mathematics, the '''Shapiro polynomials''' are a [[polynomial sequence|sequence of polynomials]] which were first studied by [[Harold S. Shapiro]] in 1951 when considering the magnitude of specific [[trigonometric sum]]s.<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|postscript=<!--None-->|jstor=2036537}}</ref> In [[signal processing]], the Shapiro polynomials have good [[autocorrelation]] properties<ref>{{Cite journal|url=http://ieeexplore.ieee.org/Xplore/login.jsp?url=/iel5/2220/4236720/04236729.pdf?arnumber=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|postscript=<!--None-->}}</ref> and their values on the [[unit circle]] are small.  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 [[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

:''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<sup>(''n''&thinsp;+&thinsp;1)</sup>, which is on the order
of the [[L2 norm|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]]).  Property (iii) shows that (''P'',&nbsp;''Q'') form a [[Golay pair]].

These polynomials have further properties:<ref>{{cite journal | author=J. Brillhart | coauthors=J.S. Lomont, 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_k(z)P_n(z^{2k+1}) + z^{2k}Q_k(z)P_n(-z^{2k+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|authorlink=Peter Borwein|title = Computational Excursions in Analysis and Number Theory|publisher = Springer|year = 2002|isbn = 0-387-95444-9|url = http://books.google.com/?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 | 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=0-8176-3481-9 }}

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