Complementary Shapiro polynomials $Q_n$

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

Polynomials

$n$

$Q_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 complementary Shapiro polynomials [1] are the sequence $Q_n\in\mathbb Z[x]$ defined together with the Shapiro polynomials $P_n$ 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 $Q_n$.

Parameters

$n$

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

Formulas

(1)

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

(2)

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}$.

(3)

Equivalently, for $n\geq1$, $Q_n(x)=\sum_{j=0}^{2^n-1}b_jx^j$. Let $s_j=1$ if the binary expansion of $j$ has an even number of pairs of consecutive ones, counting overlapping pairs separately, and let $s_j=-1$ otherwise. Then $b_j=s_j$ for $j<2^{n-1}$ and $b_j=-s_j$ for $j\geq2^{n-1}$.

(4)

If $f(x)=\sum_{j=0}^{2^n-1}b_jx^j$ has every $b_j=\pm1$, its aperiodic autocorrelations are $c_k(f)=\sum_{j=0}^{2^n-1-k}b_jb_{j+k}$, so $c_0(f)=2^n$. For the Shapiro pair, $c_k(P_n)+c_k(Q_n)=0$ for $1\leq k<2^n$.

(5)

$Q_{n+1}(x)=Q_n(x^2)+xQ_n(-x^2)$ for $n\geq1$.

(6)

$Q_n(1)=0$ for odd $n$ and $Q_n(1)=2^{n/2}$ for even $n$. For $n\geq1$, $Q_n(-1)=(-1)^{n+1}2^{\lfloor(n+1)/2\rfloor}$, while $Q_0(-1)=1$.

Comments

(7)

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

(8)

This table writes the polynomial variable as $x$.

(9)

Each coefficient of $Q_n$ is $1$ or $-1$, and the constant coefficient is $1$. Formula (3) indexes coefficients by increasing degree.

(10)

The other sequence of the pair, $P_n$, is held in Shapiro polynomials $P_n$.

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)[1]      # the next polynomial after this table

Links

[1]

Wikipedia: Shapiro polynomials

Similar tables

Shapiro polynomials $P_n$ — are the first polynomial sequence in the same recursion; together $P_n$ and $Q_n$ satisfy $|P_n(z)|^2+|Q_n(z)|^2=2^{n+1}$ on $|z|=1$

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; $Q_8$ has 1,931 characters)

How they were obtained:

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

Every entry was checked against the direct Golay-Rudin-Shapiro coefficient construction in (3) and the reciprocal relation in (1), against the first three $Q_n$ polynomials printed by [1], against the complementary identity in (2), against the aperiodic autocorrelations in (4), against the recurrence in (5), and against the specialisations in (6).