Shapiro polynomials

In mathematics, the Shapiro polynomials are a sequence of polynomials which were first studied by Harold S. Shapiro in 1951 when considering the magnitude of specific trigonometric sums. [citation|url=http://www.jstor.org/pss/2036537|title=Note on the Shapiro polynomials|author=John Brillhart and L. Carlitz|journal= Proceedings of the American Mathematical Society|volume=25|number= 1|date=May, 1970|pages=114–118|doi=10.2307/2036537] In signal processing, the Shapiro polynomials have good autocorrelation properties [citation|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] and their values on the unit circle are small. The first few members of the sequence are:

:

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

Construction

The Shapiro polynomials "P"_"n"("z") may be constructed from the Golay-Rudin-Shapiro sequence "a"_"n", which equals 1 if the number of pairs of consecutive ones in the binary expansion of "n" is even, and −1 otherwise (OEIS OEIS2C|id=A020985). Thus "a"₀ = 1, "a"₁ = 1, "a"₂ = 1, "a"₃ = −1, etc.

The first Shapiro "P"_"n"("z") is the partial sum of order 2^"n" − 1 (where "n" = 0, 1, 2, ...) of the power series

:"f"("z") := "a"₀ + "a"₁ "z" + a₂ "z"² + ...

The Golay-Rudin-Shapiro sequence {"a"_"n"} has a fractal-like structure – for example, "a"_"n" = "a"_2"n" – which implies that the subsequence ("a"₀, "a"₂, "a"₄, ...) replicates the original sequence {"a"_"n"}. This in turn leads to remarkablefunctional equations satisfied by "f"("z").

The second or complementary Shapiro polynomials "Q"_"n"("z") may be defined in terms of this sequence, or by the relation "Q"_"n"("z") = (1-)^"n""z"^2"n"-1"P"_"n"(-1/"z"), or by the recursions

:$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)\; .$

Properties

The sequence of complementary polynomials "Q"_"n" corresponding to the "P"_"n" is uniquely characterized by the following properties:
* (i) "Q"_"n" is of degree 2^"n" − 1;
* (ii) the coefficients of "Q"_"n" are all 1 or −1 , and its constant term equals 1; and
* (iii) the identity |"P"_"n"("z")|² + |"Q"_"n"("z")|² = 2^{("n" + 1)} holds on the unit circle, where the complex variable "z" has absolute value one.

The most interesting property of the {"P"_"n"} is that the absolute value of "P"_"n"("z") is bounded on the unit circle by the square root of 2^{("n" + 1)}, which is on the orderof the L² norm of "P"_"n". Polynomials with coefficients from the set {−1, 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", "Q") form a Golay pair.

These polynomials have further properties [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 ] ::$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\; floor\};\; \{~\}\{~\}\; P\_n(-1)\; =\; (1+(-1)^n)2^\{lfloor\; n/2\; floor\; -\; 1\}\; .\; ,$

ee also

* Littlewood polynomials

References

*cite book|last = Borwein|first = Peter B|authorlink=Peter Borwein|title = Computational Excursions in Analysis and Number Theory|publisher = Springer|date = 2002|isbn = 0387954449|url = http://books.google.com/books?id=A_ITwN13J6YC|accessdate = 2007-03-30 Chapter 4.