View source for Reciprocal polynomial

In [[algebra]], the '''reciprocal polynomial''', or '''reflected polynomial'''<ref name="concrete">*{{cite book | last = Graham | first = Ronald |last2=Knuth|first2=Donald E.|last3=Patashnik|first3=Oren | title = Concrete mathematics : a foundation for computer science | edition=Second | publisher = Addison-Wesley | location = Reading, Mass | year = 1994 | isbn = 978-0201558029 | page= 340}}</ref><ref name="Aigner">{{cite book | last = Aigner | first = Martin | title = A course in enumeration | publisher = Springer | location = Berlin New York | year = 2007 | isbn = 978-3540390329 | page = 94 }}</ref> {{math|''p''<sup>∗</sup>}} or {{math|''p''<sup>R</sup>}},<ref name="Aigner"/><ref name="concrete"/> of a [[polynomial]] {{math|''p''}} of degree {{math|''n''}} with coefficients from an arbitrary [[Field (mathematics)|field]], such as
:<math>p(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n, \,\!</math>
is the polynomial<ref>{{harvnb|Roman|1995|loc=pg.37}}</ref>

: <math>p^*(x) = a_n + a_{n-1}x + \cdots + a_0x^n = x^n p(x^{-1}).</math>

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]] {{math|''p''}} has [[complex number|complex]] coefficients, that is,

:<math>p(z) = a_0 + a_1z + a_2z^2 + \cdots + a_nz^n, \,\!</math>

the '''conjugate reciprocal polynomial''', {{math|''p''<sup>†</sup>}} given by,

:<math>p^{\dagger}(z) = \overline{a_n} + \overline{a_{n-1}}z + \cdots + \overline{a_0}z^n = z^n\overline{p(\bar{z}^{-1})},</math>

where <math>\overline{a_i}</math> denotes the [[complex conjugate]] of <math>a_i \,\!</math>, is also called the reciprocal polynomial when no confusion can arise.

A polynomial {{math|''p''}} is called '''self-reciprocal''' or '''palindromic''' if {{math|1=''p''(''x'') = ''p''<sup>∗</sup>(''x'')}}.
The coefficients of a self-reciprocal polynomial satisfy {{math|1=''a''<sub>''i''</sub> = ''a''<sub>''n''&minus;''i''</sub>}}. In the conjugate reciprocal case, the coefficients must be [[Real number|real]] to satisfy the condition.

== Properties ==
Reciprocal polynomials have several connections with their original polynomials, including:
# {{math|1=''p''(''x'') = ''x''<sup>''n''</sup>''p''<sup>∗</sup>(''x''<sup>−1</sup>)}}<ref name="Aigner"/>
# {{math|''α''}} is a root of polynomial {{math|''p''}} if and only if {{math|α<sup>−1</sup>}} is a root of {{math|''p''<sup>∗</sup>}}.<ref name="Pless 1990 loc=pg. 57">{{harvnb|Pless|1990|loc=pg. 57}}</ref>
# If {{math|''p''(''x'') ≠ ''x''}} then {{math|''p''}} is [[Irreducible polynomial|irreducible]] if and only if {{math|''p''<sup>∗</sup>}} is irreducible.<ref name="Roman 1995 loc= pg. 37">{{harvnb|Roman|1995|loc= pg. 37}}</ref>
# {{math|''p''}} is [[Primitive polynomial (field theory)|primitive]] if and only if {{math|''p''<sup>∗</sup>}} is primitive.<ref name="Pless 1990 loc=pg. 57"/>

Other properties of reciprocal polynomials may be obtained, for instance:
* If a polynomial is self-reciprocal and irreducible then it must have even degree.<ref name="Roman 1995 loc= pg. 37"/>

=={{anchor|Palindromic polynomial}} Palindromic and antipalindromic polynomials==
A self-reciprocal polynomial is also called palindromic because its coefficients, when the polynomial is written in the order of ascending or descending powers, form a [[palindrome]]. That is, if
:<math> P(x) = \sum_{i=0}^n a_ix^i</math> 
is a polynomial of [[Degree of a polynomial|degree]] {{math|''n''}}, then {{math|''P''}} is ''palindromic'' if {{math|1=''a<sub>i</sub>'' = ''a''<sub>''n'' − ''i''</sub>}} for {{math|1=''i'' = 0, 1, ..., ''n''}}. Some authors use the terms ''palindromic'' and ''reciprocal'' interchangeably.

Similarly, {{math|''P''}}, a polynomial of degree {{math|''n''}}, is called '''antipalindromic''' if {{math|1=''a<sub>i</sub>'' = −''a''<sub>''n'' − ''i''</sub>}} for {{math|1=''i'' = 0, 1, ... ''n''}}. That is, a polynomial {{math|''P''}} is ''antipalindromic'' if {{math|1=''P''(''x'') = – ''P''<sup>∗</sup>(''x'')}}.

===Examples===
From the properties of the [[binomial coefficient]]s, it follows that the polynomials {{math|1=''P''(''x'') = (''x'' + 1 )<sup>''n''</sup>}} are palindromic for all positive integers {{math|''n''}}, while the polynomials {{math|1=''Q''(''x'') = (''x'' – 1 )<sup>''n''</sup>}} are palindromic when {{math|''n''}} is even and antipalindromic when {{math|''n''}} is odd.

Other examples of palindromic polynomials include [[cyclotomic polynomial]]s and [[Eulerian polynomial]]s.

===Properties===
* If {{math|''a''}} is a root of a polynomial that is either palindromic or antipalindromic, then {{sfrac|{{math|''a''}}}} is also a root and has the same [[multiplicity (mathematics)|multiplicity]].<ref>{{harvnb|Pless|1990|loc=pg. 57}} for the palindromic case only</ref>
* The converse is true: If a polynomial is such that if {{math|''a''}} is a root then {{sfrac|{{math|''a''}}}} is also a root of the same multiplicity, then the polynomial is either palindromic or antipalindromic.
* For any polynomial {{math|''q''}}, the polynomial {{math|''q'' + ''q''<sup>∗</sup>}} is palindromic and the polynomial {{math|''q'' − ''q''<sup>∗</sup>}} is antipalindromic.
* Any polynomial {{math|''q''}} can be written as the sum of a palindromic and an antipalindromic polynomial.<ref>{{citation|first=Jonathan Y.|last=Stein|title=Digital Signal Processing: A Computer Science Perspective|publisher=Wiley Interscience|year=2000|page=384|isbn=9780471295464}}</ref>
* The product of two palindromic or antipalindromic polynomials is palindromic.
* The product of a palindromic polynomial and an antipalindromic polynomial is antipalindromic.
* A palindromic polynomial of odd degree is a multiple of {{math|''x'' + 1}} (it has –1 as a root) and its quotient by {{math|''x'' + 1}} is also palindromic.
* An antipalindromic polynomial is a multiple of {{math|''x'' – 1}} (it has 1 as a root) and its quotient by {{math|''x'' – 1}} is palindromic.
* An antipalindromic polynomial of even degree is a multiple of {{math|''x''<sup>2</sup> – 1}} (it has -1 and 1 as a roots) and its quotient by {{math|''x''<sup>2</sup> – 1}} is palindromic. 
* If {{math|''p''(''x'')}} is a palindromic polynomial of even degree {{mvar|2d}}, then there is a polynomial {{math|''q''}} of degree {{math|''d''}} such that {{math|1=''p''(''x'') = ''x''<sup>''d''</sup>''q''(''x'' + {{sfrac|1|''x''}})}} (Durand 1961).
* If {{math|''p''(''x'')}} is a monic antipalindromic polynomial of even degree {{mvar|2d}} over a field {{mvar|k}} with odd [[Characteristic (field)|characteristic]], then it can be written uniquely as {{math|1=''p''(''x'') = ''x''<sup>''d''</sup> (''Q''(''x'') − ''Q''({{sfrac|''x''}}))}}, where {{mvar|Q}} is a monic polynomial of degree {{mvar|d}} with no constant term.<ref>{{citation|first=Nicholas M.|last=Katz|title=Convolution and Equidistribution : Sato-Tate Theorems for Finite Field Mellin Transformations|publisher=Princeton University Press|year=2012|isbn=9780691153315|page=146}}</ref>
* If an antipalindromic polynomial {{math|''P''}} has even degree {{math|2''n''}}, then its "middle" coefficient (of power {{math|''n''}}) is 0 since {{math|1=''a<sub>n</sub>'' = −''a<sub>2n – n</sub>''}}.

===Real coefficients===
A polynomial with [[Real number|real]] coefficients all of whose [[Complex number|complex]] roots lie on the unit circle in the [[complex plane]] (all the roots are unimodular) is either palindromic or antipalindromic.<ref>{{citation|first1=Ivan|last1=Markovsky|first2=Shodhan|last2=Rao|title=Palindromic polynomials, time-reversible systems and conserved quantities|journal=Control and Automation|pages=125–130|year=2008|doi=10.1109/MED.2008.4602018|isbn=978-1-4244-2504-4|url=https://eprints.soton.ac.uk/266592/1/Med08.pdf}}</ref>

==Conjugate reciprocal polynomials==

A polynomial is '''conjugate reciprocal''' if <math>p(x) \equiv p^{\dagger}(x)</math> and '''self-inversive''' if <math>p(x) = \omega p^{\dagger}(x)</math> for a scale factor {{math|''ω''}} on the [[unit circle]].<ref name=SV08>{{cite book | last1=Sinclair | first1=Christopher D. | last2=Vaaler | first2=Jeffrey D. | chapter=Self-inversive polynomials with all zeros on the unit circle | zbl=1334.11017 | editor1-last=McKee | editor1-first=James | editor2-last=Smyth | editor2-first=C. J. | title=Number theory and polynomials. Proceedings of the workshop, Bristol, UK, April 3–7, 2006 | location=Cambridge | publisher=[[Cambridge University Press]] | isbn=978-0-521-71467-9 | series=London Mathematical Society Lecture Note Series | volume=352 | pages=312–321 | year=2008 }}</ref>

If {{math|''p''(''z'')}} is the [[Minimal polynomial (field theory)|minimal polynomial]] of {{math|''z''<sub>0</sub>}} with {{math|1={{abs|''z''<sub>0</sub>}} = 1, ''z''<sub>0</sub> ≠ 1}}, and {{math|''p''(''z'')}} has [[real number|real]] coefficients, then {{math|''p''(''z'')}} is self-reciprocal.  This follows because

:<math>z_0^n\overline{p(1/\bar{z_0})} = z_0^n\overline{p(z_0)} = z_0^n\bar{0} = 0.</math>

So {{math|''z''<sub>0</sub>}} is a root of the polynomial <math>z^n\overline{p(\bar{z}^{-1})}</math> which has degree {{math|''n''}}.  But, the minimal polynomial is unique, hence 
:<math>cp(z) = z^n\overline{p(\bar{z}^{-1})}</math>
for some constant {{math|''c''}}, i.e. <math>ca_i=\overline{a_{n-i}}=a_{n-i}</math>. Sum from {{math|1=''i'' = 0}} to {{math|''n''}} and note that 1 is not a root of {{math|''p''}}. We conclude that {{math|1=''c'' = 1}}.

A consequence is that the [[cyclotomic polynomial]]s {{math|Φ<sub>''n''</sub>}} are self-reciprocal for {{math|''n'' > 1}}. This is used in the [[special number field sieve]] to allow numbers of the form {{math|''x''<sup>11</sup> ± 1, ''x''<sup>13</sup> ± 1, ''x''<sup>15</sup> ± 1}} and {{math|''x''<sup>21</sup> ± 1}} to be factored taking advantage of the algebraic factors by using polynomials of degree 5, 6, 4 and 6 respectively – note that {{math|''φ''}} ([[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 code|cyclic error correcting codes]]. Suppose {{math|''x''<sup>''n''</sup> &minus; 1}} can be factored into the product of two polynomials, say {{math|1=''x''<sup>''n''</sup> &minus; 1 = ''g''(''x'')''p''(''x'')}}. When {{math|''g''(''x'')}} generates a cyclic code {{math|''C''}}, then the reciprocal polynomial {{math|''p''<sup>∗</sup>}} generates {{math|''C''<sup>⊥</sup>}}, the [[orthogonal complement]] of {{math|''C''}}.<ref>{{harvnb|Pless|1990|loc = pg. 75, Theorem 48}}</ref>
Also, {{math|''C''}} is ''self-orthogonal'' (that is, {{math|''C'' ⊆ ''C''<sup>⊥</sup>)}}, if and only if  {{math|''p''<sup>∗</sup>}} divides {{math|''g''(''x'')}}.<ref>{{harvnb|Pless|1990|loc = pg. 77, Theorem 51}}</ref>

== Notes ==
{{reflist}}

==References==
{{More citations needed|date=June 2008}}
* {{citation|first=Vera|last=Pless|title=Introduction to the Theory of Error Correcting Codes|edition=2nd|publisher=Wiley-Interscience|place=New York|year=1990|isbn=0-471-61884-5}}
* {{citation|first=Steven|last=Roman|title=Field Theory|publisher=Springer-Verlag|place=New York|year=1995|isbn=0-387-94408-7}}
* Émile Durand (1961) Solutions numériques des équations algrébriques I, Masson et Cie: XV - polynômes dont les coefficients sont symétriques ou antisymétriques, p.&nbsp;140-141.

== External links ==
* {{MathPages|id=home/kmath294/kmath294|title=The Fundamental Theorem for Palindromic Polynomials}}
* [http://mathworld.wolfram.com/ReciprocalPolynomial.html Reciprocal Polynomial] (on [[MathWorld]])

[[Category:Polynomials]]