Reciprocal polynomial

<h2 id="properties">Properties</h2>
Reciprocal polynomials have several connections with their original polynomials, including:

<ol><li>deg p = deg p∗ if 
 
 
 
 
 a
 
 0
 
 
 
 
 {\displaystyle a_{0}}
 
 is not 0.</li>
<li>p(x) = xnp∗(x−1).<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>α is a <a href="/facts/Zero_of_a_function/mlK3dhoT">root</a> of a polynomial p if and only if α−1 is a root of p∗.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li>If x ∤ p(x) then p is <a href="/facts/Irreducible_polynomial/PTeuKm4W">irreducible</a> if and only if p∗ is irreducible.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>p is <a href="/facts/Primitive_polynomial_(field_theory)/8nvXpBUL">primitive</a> if and only if p∗ is primitive.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li></ol>
Other properties of reciprocal polynomials may be obtained, for instance:

<ul><li>A self-reciprocal polynomial of odd degree is divisible by x+1, hence is not irreducible if its degree is > 1.</li></ul>
<h2 id="palindromic-and-antipalindromic-polynomials"> Palindromic and antipalindromic polynomials</h2>
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 <a href="/facts/Palindrome/PHo33zqN">palindrome</a>. That is, if

P
        (
        x
        )
        =
        
          ∑
          
            i
            =
            0
          
          
            n
          
        
        
          a
          
            i
          
        
        
          x
          
            i
          
        
      
    
    {\displaystyle P(x)=\sum _{i=0}^{n}a_{i}x^{i}}

is a polynomial of <a href="/facts/Degree_of_a_polynomial/Bf8vEIhf">degree</a> n, then P is palindromic if ai = an−i for i = 0, 1, ..., n. 
Similarly, a polynomial P of degree n is called antipalindromic if ai = −an−i for i = 0, 1, ..., n. That is, a polynomial P is antipalindromic if P(x) = –P∗(x).

<h3>Examples</h3>
From the properties of the <a href="/facts/Binomial_coefficient/Tsx7eY5h">binomial coefficients</a>, it follows that the polynomials P(x) = (x + 1)n are palindromic for all positive <a href="/facts/Integer/PUwwrawx">integers</a> n, while the polynomials Q(x) = (x – 1)n are palindromic when n is even and antipalindromic when n is <a href="/facts/Parity_(mathematics)/7zq2UM4V">odd</a>.
Other examples of palindromic polynomials include <a href="/facts/Cyclotomic_polynomial/TsWXDHIp">cyclotomic polynomials</a> and <a href="/facts/Eulerian_polynomial/lMWud3wa">Eulerian polynomials</a>.

<h3>Properties</h3>
<ul><li>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 <a href="/facts/Multiplicity_(mathematics)/dndUyetA">multiplicity</a>.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li>
<li>The converse is true: If for each root a of polynomial, the value ⁠1/a⁠ is also a root of the same multiplicity, then the polynomial is either palindromic or antipalindromic.</li>
<li>For any polynomial q, the polynomial q + q∗ is palindromic and the polynomial q − q∗ is antipalindromic.</li>
<li>It follows that any polynomial q can be written as the sum of a palindromic and an antipalindromic polynomial, since q = (q + q∗)/2 + (q − q∗)/2.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>The product of two palindromic or antipalindromic polynomials is palindromic.</li>
<li>The product of a palindromic polynomial and an antipalindromic polynomial is antipalindromic.</li>
<li>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.</li>
<li>An antipalindromic polynomial over a field k with odd <a href="/facts/Characteristic_(algebra)/D2VzcQaG">characteristic</a> is a multiple of x – 1 (it has 1 as a root) and its quotient by x – 1 is palindromic.</li>
<li>An antipalindromic polynomial of even degree is a multiple of x2 – 1 (it has −1 and 1 as roots) and its quotient by x2 – 1 is palindromic.</li>
<li>If p(x) is a palindromic polynomial of even degree 2d, then there is a polynomial q of degree d such that p(x) = xdq(x + ⁠1/x⁠).<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a></li>
<li>If p(x) is a <a href="/facts/Monic_polynomial/4JzuIJ5R">monic</a> antipalindromic polynomial of even degree 2d over a field k of odd <a href="/facts/Characteristic_(algebra)/D2VzcQaG">characteristic</a>, then it can be written uniquely as p(x) = xd(Q(x) − Q(⁠1/x⁠)), where Q is a monic polynomial of degree d with no constant term.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></li>
<li>If an antipalindromic polynomial P has even degree 2n over a field k of odd characteristic, then its "middle" coefficient (of power n) is 0 since an = −a2n – n.</li></ul>
<h3>Real coefficients</h3>
A polynomial with <a href="/facts/Real_number/R02gw5Pb">real</a> coefficients all of whose <a href="/facts/Complex_number/2w7mqI7e">complex</a> roots lie on the unit circle in the <a href="/facts/Complex_plane/vE0QrxJp">complex plane</a> (that is, all the roots have modulus 1) is either palindromic or antipalindromic.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>

<h2 id="conjugate-reciprocal-polynomials">Conjugate reciprocal polynomials</h2>
A polynomial is conjugate reciprocal if 
 
 
 
 p
 (
 x
 )
 ≡
 
 p
 
 †
 
 
 (
 x
 )
 
 
 {\displaystyle p(x)\equiv p^{\dagger }(x)}
 
 and self-inversive if 
 
 
 
 p
 (
 x
 )
 =
 ω
 
 p
 
 †
 
 
 (
 x
 )
 
 
 {\displaystyle p(x)=\omega p^{\dagger }(x)}
 
 for a scale factor ω on the <a href="/facts/Unit_circle/VsTffjPK">unit circle</a>.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
If p(z) is the <a href="/facts/Minimal_polynomial_(field_theory)/dJv9Q0Kh">minimal polynomial</a> of z0 with |z0| = 1, z0 ≠ 1, and p(z) has <a href="/facts/Real_number/R02gw5Pb">real</a> coefficients, then p(z) is self-reciprocal. This follows because

z
          
            0
          
          
            n
          
        
        
          
            
              p
              (
              1
              
                /
              
              
                
                  
                    
                      z
                      
                        0
                      
                    
                    ¯
                  
                
              
              )
            
            ¯
          
        
        =
        
          z
          
            0
          
          
            n
          
        
        
          
            
              p
              (
              
                z
                
                  0
                
              
              )
            
            ¯
          
        
        =
        
          z
          
            0
          
          
            n
          
        
        
          
            
              0
              ¯
            
          
        
        =
        0.
      
    
    {\displaystyle z_{0}^{n}{\overline {p(1/{\bar {z_{0}}})}}=z_{0}^{n}{\overline {p(z_{0})}}=z_{0}^{n}{\bar {0}}=0.}

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

c
        p
        (
        z
        )
        =
        
          z
          
            n
          
        
        
          
            
              p
              (
              
                
                  
                    
                      z
                      ¯
                    
                  
                
                
                  −
                  1
                
              
              )
            
            ¯
          
        
      
    
    {\displaystyle cp(z)=z^{n}{\overline {p({\bar {z}}^{-1})}}}

for some constant c, i.e. 
 
 
 
 c
 
 a
 
 i
 
 
 =
 
 
 
 a
 
 n
 −
 i
 
 
 ¯
 
 
 =
 
 a
 
 n
 −
 i
 
 
 
 
 {\displaystyle 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 <a href="/facts/Cyclotomic_polynomial/TsWXDHIp">cyclotomic polynomials</a> Φn are self-reciprocal for n > 1. This is used in the <a href="/facts/Special_number_field_sieve/vnlM5Tb7">special number field sieve</a> to allow numbers of the form x11 ± 1, x13 ± 1, x15 ± 1 and x21 ± 1 to be factored taking advantage of the algebraic factors by using polynomials of degree 5, 6, 4 and 6 respectively – note that φ (<a href="/facts/Euler%27s_totient_function/mIQwXYzj">Euler's totient function</a>) of the exponents are 10, 12, 8 and 12.
Per <a href="/facts/Cohn%27s_theorem/KVJDCNon">Cohn's theorem</a>, a self-inversive polynomial has as many roots in the <a href="/facts/Unit_disk/phrUu7yC">unit disk</a> 
 
 
 
 {
 z
 ∈
 
 C
 
 :
 
 |
 
 z
 
 |
 
 <
 1
 }
 
 
 {\displaystyle \{z\in \mathbb {C} :|z|<1\}}
 
 as the reciprocal polynomial of its <a href="/facts/Derivative/7Ito70Dh">derivative</a>.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>

<h2 id="application-in-coding-theory">Application in coding theory</h2>
The reciprocal polynomial finds a use in the theory of <a href="/facts/Cyclic_code/LmhezpnR">cyclic error correcting codes</a>. Suppose xn − 1 can be factored into the product of two polynomials, say xn − 1 = g(x)p(x). When g(x) generates a cyclic code C, then the reciprocal polynomial p∗ generates C⊥, the <a href="/facts/Orthogonal_complement/a13oQBsz">orthogonal complement</a> of C.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
Also, C is self-orthogonal (that is, C ⊆ C⊥), if and only if p∗ divides g(x).<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Cohn%27s_theorem/KVJDCNon">Cohn's theorem </a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Pless, Vera (1990), <a href="/facts/Introduction_to_the_Theory_of_Error-Correcting_Codes/VKWbax0T">Introduction to the Theory of Error Correcting Codes</a> (2nd ed.), New York: Wiley-Interscience, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-471-61884-5</li>
<li>Roman, Steven (1995), Field Theory, New York: Springer-Verlag, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-387-94408-7</li>
<li>Durand, Émile (1961), "Masson et Cie: XV - polynômes dont les coefficients sont symétriques ou antisymétriques", Solutions numériques des équations algrébriques, vol. I, pp. 140–141</li></ul>
<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.mathpages.com/home/kmath294/kmath294.htm">"The fundamental theorem for palindromic polynomials"</a>. MathPages.com.</li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/ReciprocalPolynomial.html">"Reciprocal polynomial"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">*Graham, Ronald; Knuth, Donald E.; Patashnik, Oren (1994). Concrete mathematics : a foundation for computer science (Second ed.). Reading, Mass: Addison-Wesley. p. 340. ISBN 978-0201558029. <a href="978-0201558029" target="_blank">978-0201558029</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. p. 94. ISBN 978-3540390329. <a href="978-3540390329" target="_blank">978-3540390329</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. p. 94. ISBN 978-3540390329. <a href="978-3540390329" target="_blank">978-3540390329</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">*Graham, Ronald; Knuth, Donald E.; Patashnik, Oren (1994). Concrete mathematics : a foundation for computer science (Second ed.). Reading, Mass: Addison-Wesley. p. 340. ISBN 978-0201558029. <a href="978-0201558029" target="_blank">978-0201558029</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Roman 1995, pg.37 - Roman, Steven (1995), Field Theory, New York: Springer-Verlag, ISBN 0-387-94408-7 <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. p. 94. ISBN 978-3540390329. <a href="978-3540390329" target="_blank">978-3540390329</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Pless 1990, pg. 57 - Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5 <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Roman 1995, pg. 37 - Roman, Steven (1995), Field Theory, New York: Springer-Verlag, ISBN 0-387-94408-7 <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Pless 1990, pg. 57 - Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5 <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Pless 1990, pg. 57 for the palindromic case only - Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5 <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Stein, Jonathan Y. (2000), Digital Signal Processing: A Computer Science Perspective, Wiley Interscience, p. 384, ISBN 9780471295464 <a href="9780471295464" target="_blank">9780471295464</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Durand 1961 - Durand, Émile (1961), "Masson et Cie: XV - polynômes dont les coefficients sont symétriques ou antisymétriques", Solutions numériques des équations algrébriques, vol. I, pp. 140–141 <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Katz, Nicholas M. (2012), Convolution and Equidistribution : Sato-Tate Theorems for Finite Field Mellin Transformations, Princeton University Press, p. 146, ISBN 9780691153315 <a href="9780691153315" target="_blank">9780691153315</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Markovsky, Ivan; Rao, Shodhan (2008). "Palindromic polynomials, time-reversible systems, and conserved quantities". 2008 16th Mediterranean Conference on Control and Automation (PDF). IEEE. pp. 125–130. doi:10.1109/MED.2008.4602018. ISBN 978-1-4244-2504-4. S2CID 14122451. <a href="978-1-4244-2504-4" target="_blank">978-1-4244-2504-4</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Sinclair, Christopher D.; Vaaler, Jeffrey D. (2008). "Self-inversive polynomials with all zeros on the unit circle". In McKee, James; Smyth, C. J. (eds.). Number theory and polynomials. Proceedings of the workshop, Bristol, UK, April 3–7, 2006. London Mathematical Society Lecture Note Series. Vol. 352. Cambridge: Cambridge University Press. pp. 312–321. ISBN 978-0-521-71467-9. Zbl 1334.11017. <a href="978-0-521-71467-9" target="_blank">978-0-521-71467-9</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Ancochea, Germán (1953). "Zeros of self-inversive polynomials". Proceedings of the American Mathematical Society. 4 (6): 900–902. doi:10.1090/S0002-9939-1953-0058748-8. ISSN 0002-9939. <a href="https://www.ams.org/proc/1953-004-06/S0002-9939-1953-0058748-8/" target="_blank">https://www.ams.org/proc/1953-004-06/S0002-9939-1953-0058748-8/</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Bonsall, F. F.; Marden, Morris (1952). "Zeros of self-inversive polynomials". Proceedings of the American Mathematical Society. 3 (3): 471–475. doi:10.1090/S0002-9939-1952-0047828-8. ISSN 0002-9939. <a href="https://www.ams.org/proc/1952-003-03/S0002-9939-1952-0047828-8/" target="_blank">https://www.ams.org/proc/1952-003-03/S0002-9939-1952-0047828-8/</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Pless 1990, pg. 75, Theorem 48 - Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5 <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Pless 1990, pg. 77, Theorem 51 - Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5 <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
</ol>

Reciprocal polynomial open-in-new

Reciprocal polynomial