Shapiro polynomials $P_n$

edit · history · discussion · files · short url · combinatorics polynomial

Polynomials

$n$

$P_n(x)$

x + 1

-x^3 + x^2 + x + 1

x^7 - x^6 + x^5 + x^4 - x^3 + x^2 + x + 1

-x^15 + x^14 - x^13 - x^12 - x^11 + x^10 + x^9 + x^8 + x^7 - x^6 + x^5 + x^4 - x^3 + x^2 + x + 1

x^31 - x^30 + x^29 + x^28 + x^27 - x^26 - x^25 - x^24 + x^23 - x^22 + x^21 + x^20 - x^19 + x^18 + x^17 + x^16 - x^15 + x^14 - x^13 - x^12 - x^11 + x^10 + x^9 + x^8 + x^7 - x^6 + x^5 + x^4 - x^3 + x^2 + x + 1

-x^63 + x^62 - x^61 - x^60 - x^59 + x^58 + x^57 + x^56 - x^55 + x^54 - x^53 - x^52 + x^51 - x^50 - x^49 - x^48 - x^47 + x^46 - x^45 - x^44 - x^43 + x^42 + x^41 + x^40 + x^39 - x^38 + x^37 + x^36 - x^35 + x^34 + x^33 + x^32 + x^31 - x^30 + x^29 + x^28 + x^27 - x^26 - x^25 - x^24 + x^23 - x^22 + x^21 + x^20 - x^19 + x^18 + x^17 + x^16 - x^15 + x^14 - x^13 - x^12 - x^11 + x^10 + x^9 + x^8 + x^7 - x^6 + x^5 + x^4 - x^3 + x^2 + x + 1

x^127 - x^126 + x^125 + x^124 + x^123 - x^122 - x^121 - x^120 + x^119 - x^118 + x^117 + x^116 - x^115 + x^114 + x^113 + x^112 + x^111 - x^110 + x^109 + x^108 + x^107 - x^106 - x^105 - x^104 - x^103 + x^102 - x^101 - x^100 + x^99 - x^98 - x^97 - x^96 + x^95 - x^94 + x^93 + x^92 + x^91 - x^90 - x^89 - x^88 + x^87 - x^86 + x^85 + x^84 - x^83 + x^82 + x^81 + x^80 - x^79 + x^78 - x^77 - x^76 - x^75 + x^74 + x^73 + x^72 + x^71 - x^70 + x^69 + x^68 - x^67 + x^66 + x^65 + x^64 - x^63 + x^62 - x^61 - x^60 - x^59 + x^58 + x^57 + x^56 - x^55 + x^54 - x^53 - x^52 + x^51 - x^50 - x^49 - x^48 - x^47 + x^46 - x^45 - x^44 - x^43 + x^42 + x^41 + x^40 + x^39 - x^38 + x^37 + x^36 - x^35 + x^34 + x^33 + x^32 + x^31 - x^30 + x^29 + x^28 + x^27 - x^26 - x^25 - x^24 + x^23 - x^22 + x^21 + x^20 - x^19 + x^18 + x^17 + x^16 - x^15 + x^14 - x^13 - x^12 - x^11 + x^10 + x^9 + x^8 + x^7 - x^6 + x^5 + x^4 - x^3 + x^2 + x + 1

Definition

The Shapiro polynomials [1], also called the Rudin-Shapiro polynomials, are the pair of polynomial sequences $P_n,Q_n\in\mathbb Z[x]$ defined by $P_0=Q_0=1$, $P_{n+1}=P_n+x^{2^n}Q_n$, and $Q_{n+1}=P_n-x^{2^n}Q_n$. This table holds $P_n$.

Parameters

$n$

— construction index ($n$ is a nonnegative integer)

Formulas

(1)

Equivalently, $P_n(x)=\sum_{j=0}^{2^n-1}a_jx^j$, where $a_j=1$ if the binary expansion of $j$ has an even number of pairs of consecutive ones, counting overlapping pairs separately, and $a_j=-1$ otherwise.

(2)

The polynomials also satisfy $P_{n+1}(x)=P_n(x^2)+xP_n(-x^2)$.

(3)

$Q_n(x)=(-1)^nx^{2^n-1}P_n(-1/x)$.

(4)

If $d=2^n-1$, then $P_n(x)x^dP_n(1/x)+Q_n(x)x^dQ_n(1/x)=2^{n+1}x^d$. On the unit circle this is $|P_n(z)|^2+|Q_n(z)|^2=2^{n+1}$.

(5)

$P_n(1)=2^{\lfloor(n+1)/2\rfloor}$. Also, $P_n(-1)=0$ for odd $n$ and $P_n(-1)=2^{n/2}$ for even $n$.

Comments

(6)

The table is indexed by the construction parameter $n$, not by the degree: $P_n$ has degree $2^n-1$.

(7)

This table writes the polynomial variable as $x$.

Programs

(P1)

Sage

import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

R = PolynomialRing(ZZ, "x")
x = R.gen()

def shapiro_pair(n):
    P = R.one()
    Q = R.one()
    for k in range(n):
        P, Q = P + x**(2**k)*Q, P - x**(2**k)*Q
    return P, Q

shapiro_pair(8)[0]      # the next polynomial after this table

Links

[1]

Wikipedia: Shapiro polynomials

Similar tables

Fekete polynomials $f_p$ — use a quadratic-residue sign rule for their coefficients, rather than the Rudin-Shapiro rule

Data properties

Entries are of type: integral polynomial

How well the digits are known: exact

Table is complete: no (it holds every construction index $n$ with $0\leq n\leq7$, stopping before the printed polynomials reach about two thousand characters; $P_8$ has 1,932 characters)

How they were obtained:

The generator computes $P_n$ and $Q_n$ by the exact recurrence in $\mathbb Z[x]$.

Before the draft was filled, every entry was checked against the direct Golay-Rudin-Shapiro coefficient construction in (1), against the complementary identity in (4), against the recurrence in (2), against the first three polynomials printed by [1], and against the specialisations in (5).