Reciprocal polynomial

In algebra, the reciprocal polynomial p^∗ of a polynomial p of degree n with coefficients from an arbitrary field, such as

$p(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n, \,\!$

is the polynomial

$p^*(x) = a_n + a_{n-1}x + \cdots + a_0x^n = x^n p(x^{-1}).$

Essentially, the coefficients are written in reverse order. They arise naturally in linear algebra as the characteristic polynomial of the inverse of a matrix.

In the special case that the polynomial p has complex coefficients, that is,

$p(z) = a_0 + a_1z + a_2z^2 + \cdots + a_nz^n, \,\!$

the conjugate reciprocal polynomial, p^† given by,

$p^{\dagger}(z) = \overline{a_n} + \overline{a_{n-1}}z + \cdots + \overline{a_0}z^n = z^n\overline{p(\bar{z}^{-1})},$

where $\overline{a_i}$ denotes the complex conjugate of $a_i \,\!$, is also called the reciprocal polynomial when no confusion can arise.

A polynomial p is called self-reciprocal if p(x) = p^∗(x).

The coefficients of a self-reciprocal polynomial satisfy a_i = a_n−i, and in this case p is also called a palindromic polynomial. In the conjugate reciprocal case, the coefficients must be real to satisfy the condition.

Properties

Reciprocal polynomials have several connections with their original polynomials, including:

1. α is a root of polynomial p if and only if α⁻¹ is a root of p^∗.
2. If p(x) ≠ x then p is irreducible if and only if p^∗ is irreducible.
3. p is primitive if and only if p^∗ is primitive.

Other properties of reciprocal polynomials may be obtained, for instance:

• If a polynomial is self-reciprocal and irreducible then it must have even degree.

Palindromic and antipalindromic polynomials

A self-reciprocal polynomial is called palindromic because its coefficients, when the polynomial is written in ascending or descending order, form a palindrome. That is, if

$P(x) = \sum_{i=0}^n a_ix^i$

is a polynomial of degree n, then P is palindromic if a_i = a_{n − i} for i = 0, 1, ..., n. Some authors use the terms "palindromic" and "reciprocal" interchangeably.

Similarly, P, a polynomial of degree n, is called antipalindromic if a_i = −a_{n − i} for i = 0, 1, ... n. That is, a polynomial P is antipalindromic if P(x) = – P^∗(x).

Due to the properties of the binomial coefficients the polynomials P(x) = (x + 1 )ⁿ are palindromic for all positive integers n, while the polynomials Q(x) = (x – 1 )ⁿ are palindromic when n is even and antipalindromic when n is odd. Also, cyclotomic polynomials are palindromic.

General properties

1. If a is a root of a polynomial that is either palindromic or antipalindromic, then 1/a is also a root and has the same multiplicity.
2. The converse is true: If a polynomial is such that if a is a root then 1/a is also a root of the same multiplicity, then the polynomial is either palindromic or antipalindromic.
3. For any polynomial q, the polynomial q + q^∗ is palindromic and the polynomial q − q^∗ is antipalindromic.
4. Any polynomial q can be written as the sum of a palindromic and an antipalindromic polynomial.
5. The product of two palindromic or antipalindromic polynomials is palindromic.
6. The product of a palindromic polynomial and an antipalindromic polynomial is antipalindromic.
7. A palindromic polynomial of odd degree is a multiple of x + 1 (it has -1 as a root) and its quotient by x + 1 is also palindromic.
8. An antipalindromic polynomial is a multiple of x – 1 (it has 1 as a root) and its quotient by x – 1 is palindromic.
9. An antipalindromic polynomial of even degree is a multiple of x² – 1 (it has -1 and 1 as a roots) and its quotient by x² – 1 is palindromic.
10. If p(x) is a palindromic polynomial of even degree 2d, then there is a polynomial q of degree d such that p(x) = x^dq(x + 1/x).
11. If p(x) is a monic antipalindromic polynomial of even degree 2d over a field k with odd characteristic, then it can be written uniquely as p(x) = x^d (Q(x) − Q(1/x)), where Q is a monic polynomial of degree d with no constant term.

It follows from the definition that if P is of even degree n (so it has an odd number of terms), then it can only be antipalindromic when the "middle" term is 0, i.e., a_m = −a_{n – m}, where n = 2m.

Real coefficients

A polynomial with real coefficients all of whose complex roots lie on the unit circle in the complex plane (all the roots are unimodular) is either palindromic or antipalindromic.

Conjugate reciprocal polynomials

A polynomial is conjugate reciprocal if $p(x) \equiv p^{\dagger}(x)$ and self-inversive if $p(x) = \omega p^{\dagger}(x)$ for a scale factor ω on the unit circle.

If p(z) is the minimal polynomial of z₀ with | z₀ | = 1, z₀ ≠ 1, and p(z) has real coefficients, then p(z) is self-reciprocal. This follows because

$z_0^n\overline{p(1/\bar{z_0})} = z_0^n\overline{p(z_0)} = z_0^n\bar{0} = 0.$

So z₀ is a root of the polynomial $z^n\overline{p(\bar{z}^{-1})}$ which has degree n. But, the minimal polynomial is unique, hence

$cp(z) = z^n\overline{p(\bar{z}^{-1})}$

for some constant c, i.e. $ca_i=\overline{a_{n-i}}=a_{n-i}$. Sum from i = 0 to n and note that 1 is not a root of p. We conclude that c = 1.

A consequence is that the cyclotomic polynomials Φ_n are self-reciprocal for n > 1. This is used in the special number field sieve to allow numbers of the form x¹¹ ± 1, x¹³ ± 1, x¹⁵ ± 1 and x²¹ ± 1 to be factored taking advantage of the algebraic factors by using polynomials of degree 5, 6, 4 and 6 respectively – note that φ (Euler's totient function) of the exponents are 10, 12, 8 and 12.

Application in coding theory

The reciprocal polynomial finds a use in the theory of cyclic error correcting codes. Suppose xⁿ − 1 can be factored into the product of two polynomials, say xⁿ − 1 = g(x)p(x). When g(x) generates a cyclic code C, then the reciprocal polynomial p^∗ generates C^⊥, the orthogonal complement of C. Also, C is self-orthogonal (that is, C ⊆ C^⊥), if and only if p^∗ divides g(x).

External links

• "The Fundamental Theorem for Palindromic Polynomials" at MathPages.com.
• Reciprocal Polynomial (on MathWorld)