Reciprocal polynomial

대수학(algebra)에서, 다음과 같은

p(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots +a_{n}x^{n},\,\!

임의의 필드(field)로부터 계수를 갖는 차수 $n$ 의 다항식(polynomial) $p$ 의 상반 다항식(reciprocal polynomial) 또는 반사 다항식(reflected polynomial)^[1]^[2] $p *$ 또는 $p R$ 은^[2]^[1] 다음 다항식입니다:^[3]

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

본질적으로, 계수는 반대 순서으로 쓰입니다. 그것들은 행렬의 역(inverse of a matrix)의 특성 다항식(characteristic polynomial)으로 선형 대수(linear algebra)에서 자연적으로 발생합니다.

다항식(polynomial) $p$ 가 복소(complex) 계수를 갖는 특별한 경우에서, 즉,

p(z)=a_{0}+a_{1}z+a_{2}z^{2}+\cdots +a_{n}z^{n},\,\!

다음에 의해 제공된, 켤레 상반 다항식, $p †$ 은

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

여기서 ${\overline {a_{i}}}$ 는 $a_{i}\,\!$ 의 복소 켤레(complex conjugate)를 나타내며, 혼동이 발생하지 않을 때, 역시 상반 다항식으로 불립니다.

다항식 $p$ 는 만약 $p (x) = p * (x)$ 이면 자기-상반(self-reciprocal) 또는 회문(palindromic)으로 불립니다. 자기-상반 다항식의 계수는 $a i = a n - i$ 를 만족시킵니다. 켤레 상반 경우에서, 계수는 반드시 조건을 만족시키기 위해 실수(real)여야 합니다.

Properties

상반 다항식은 다음을 포함하여 원래 다항식과 여러 연결을 가집니다:

$p (x) = x n p * (x -1)$ ^[2]
$α$ 가 다항식 $p$ 의 근인 것과 $α -1$ 가 $p *$ 의 근인 것은 필요충분 조건입니다.^[4]
만약 $p (x) \neq x$ 이면 $p$ 가 기약(irreducible)인 것과 $p *$ 가 기약인 것은 필요충분 조건입니다.^[5]
$p$ 가 원시(primitive)인 것과 $p *$ 가 원시인 것은 필요충분 조건입니다.^[4]

상반 다항식의 다른 속성은 얻어질 수 있습니다: 예를 들어,

만약 다항식이 자기-상반이고 기약이면 그것은 반드시 짝수 차수를 가져야 합니다.^[5]

Palindromic and antipalindromic polynomials

자기-상반 다항식은 역시 회문으로 불리는데 왜냐하면 그것의 계수는, 다항식이 올라가는 또는 내려가는 거듭제곱의 순서로 쓰일 때, 회문(palindrome)을 형성하기 때문입니다. 즉, 만약 다음이 차수(degree) $n$ 의 다항식이면,

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

$P$ 는 $i = 0, 1, ..., n$ 에 대해 $a i = a n - i$ 이면 회문입니다. 일부 저자는 용어 회문과 상반을 서로 교환-가능하게 사용합니다.

비슷하게, 차수 $n$ 의 다항식, $P$ 는 $i = 0, 1, ... n$ 에 대해 $a i = - a n - i$ 이면 역회문(antipalindromic)이라고 불립니다. 즉, 다항식 $P$ 는 $P (x) = - P * (x)$ 이면 역회문입니다.

Examples

이항 계수(binomial coefficient)의 속성으로부터, 다항식 $P (x) = (x + 1 ) n$ 은 모든 양의 정수 $n$ 에 대해 회문이지만, 다항식 $Q (x) = (x - 1 ) n$ 은 $n$ 이 짝수일 때 회문이고 $n$ 이 홀수일 때 역회문을 따릅니다.

역회문 다항식의 다른 예제는 원분 다항식(cyclotomic polynomial)과 오일러 다항식(Eulerian polynomial)을 포함합니다.

Properties

만약 $a$ 가 회문 또는 역회문인 다항식의 근이면, 1/ $a$ 이 역시 근이고 같은 중복도(multiplicity)를 가집니다.^[6]
그 역도 참입니다: 만약 다항식이 $a$ 가 근이면 1/ $a$ 이 역시 근이고 같은 중복도(multiplicity)를 가짐을 만족하는 것이면, 다항식은 회문 또는 역회문입니다.
임의의 다항식 $q$ 에 대해, 다항식 $q + q *$ 은 회문이고 다항식 $q - q *$ 은 역회문입니다.
임의의 다항식 $q$ 는 회문과 역회문 다항식의 합으로 쓸 수 있습니다.^[7]
두 회문 또는 역회문 다항식의 곱은 회문입니다.
회문 다항식과 역회문 다항식의 곱은 역회문입니다.
홀수 차수의 회문 다항식은 $x + 1$ 의 배수 (근으로 –1을 가짐)이고 $x + 1$ 에 의한 그것은 몫은 역시 회문입니다.
역회문 다항식은 $x - 1$ 의 배수 (근으로 1을 가짐)이고 $x - 1$ 에 의한 몫은 회문입니다.
짝수 차수의 역회문 다항식은 $x 2 - 1$ 의 배수 (근으로 −1과 1을 가짐)이고 $x 2 - 1$ 에 의한 몫은 회문입니다.
만약 $p (x)$ 가 짝수 차수 $2d$ 의 회문 다항식이면, $p (x) = x d q (x + 1 / x)$ 을 만족하는 차수 $d$ 의 다항식 $q$ 가 있습니다 (Durand 1961).
만약 $p (x)$ 가 홀수 특성(characteristic)을 갖는 필드 $k$ 에 걸쳐 짝수 차수 $2d$ 의 일계수 역회문 다항식이면, 그것은 $p (x) = x d (Q (x) - Q (1 / x))$ 로 고유하게 쓸 수 있으며, 여기서 $Q$ 는 상수 항을 갖지 않는 차수 $d$ 의 일계수 다항식입니다.^[8]
만약 역회문 다항식 $P$ 가 짝수 차수 $2 n$ 이면, 그것의 (거듭제곱 $n$ 의) "중앙" 계수는 0인데 왜냐하면 $a n = - a 2n - n$ 이기 때문입니다.

Real coefficients

그것의 모든 복소수(complex) 근이 복소 평면(complex plane)에서 단위 원 위에 놓이는 실수(real) 계수를 갖는 다항식 (모든 근은 단일모듈러입니다)은 회문 또는 역회문입니다. ^[9]

Conjugate reciprocal polynomials

다항식은 단위 원(unit circle) 위의 스케일 인수 $ω$ 에 대해 만약 $p(x)\equiv p^{\dagger }(x)$ 이면 켤레 상반(conjugate reciprocal)이고 만약 $p(x)=\omega p^{\dagger }(x)$ 이면 자기-반전(self-inversive)입니다.^[10]

만약 $p (z)$ 가 $| z 0 | = 1, z 0 \neq 1$ 를 갖는 $z 0$ 의 최소 다항식(minimal polynomial)이고, $p (z)$ 가 실수(real) 계수를 가지면, $p (z)$ 는 자기-상반입니다. 이것은 다음이기 때문에 따릅니다:

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

그래서 $z 0$ 는 차수 $n$ 를 가지는 다항식 $z^{n}{\overline {p({\bar {z}}^{-1})}}$ 의 근입니다. 그러나, 최소 다항식은 고유하며, 일부 상수 $c$ , 즉, $ca_{i}={\overline {a_{n-i}}}=a_{n-i}$ 에 대해, 따라서

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

.

$i = 0$ 에서 $n$ 까지 합하고 1은 $p$ 의 근이 아님에 주목하십시오. 우리는 $c = 1$ 이라고 결론짓습니다.

결과는 원분 다항식(cyclotomic polynomial) $Φ n$ 은 $n > 1$ 에 대해 자기-상반이라는 것입니다. 이것은 형식 $x 11 \pm 1, x 13 \pm 1, x 15 \pm 1$ 및 $x 21 \pm 1$ 의 숫자를, 각각, 5, 6, 4 및 6 차수의 다항식을 사용함으로써 대수적 인수의 이점을 취하는 인수화되는 것을 허용하기 위해 특수 숫자 필드 체(special number field sieve)에서 사용됩니다 – 지수의 $φ$ (오일러의 토션트 함수(Euler's totient function))는 10, 12, 8 및 12입니다.

Application in coding theory

상반 다항식은 순환 오류 수정 코드(cyclic error correcting codes)의 이론에서 사용을 찾습니다. $x n - 1$ 이 두 다항식의 곱, 말하자면 $x n - 1 = g (x) p (x)$ 으로 인수화될 수 있음을 가정합니다. $g (x)$ 가 순환 코드 $C$ 를 생성할 때, 상반 다항식 $p *$ 는 $C ⊥$ , $C$ 의 직교 여(orthogonal complement)를 생성합니다.^[11] 역시, $C$ 가 자기-직교 (즉, $C \subseteq C ⊥)$ 인 것과 $p *$ 가 $g (x)$ 를 나누는 것은 필요충분 조건입니다.^[12]

Notes

^ ^a ^b *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 ^b ^c Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. p. 94. ISBN 978-3540390329.
^ Roman 1995, pg.37
^ ^a ^b Pless 1990, pg. 57
^ ^a ^b Roman 1995, pg. 37
^ Pless 1990, pg. 57 for the palindromic case only
^ Stein, Jonathan Y. (2000), Digital Signal Processing: A Computer Science Perspective, Wiley Interscience, p. 384, ISBN 9780471295464
^ Katz, Nicholas M. (2012), Convolution and Equidistribution : Sato-Tate Theorems for Finite Field Mellin Transformations, Princeton University Press, p. 146, ISBN 9780691153315
^ Markovsky, Ivan; Rao, Shodhan (2008), "Palindromic polynomials, time-reversible systems and conserved quantities" (PDF), Control and Automation: 125–130, doi:10.1109/MED.2008.4602018, ISBN 978-1-4244-2504-4
^ 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.
^ Pless 1990, pg. 75, Theorem 48
^ Pless 1990, pg. 77, Theorem 51

References

Pless, Vera (1990), Introduction to the Theory of Error Correcting Codes (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-61884-5
Roman, Steven (1995), Field Theory, New York: Springer-Verlag, 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. 140-141.

External links

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

[concrete-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.

[Aigner-2] Aigner, Martin (2007). A course in enumeration. Berlin New York: Springer. p. 94. ISBN 978-3540390329.

[3] Roman 1995, pg.37

[Pless_1990_loc=pg._57-4] Pless 1990, pg. 57

[Roman_1995_loc=_pg._37-5] Roman 1995, pg. 37

[6] Pless 1990, pg. 57 for the palindromic case only

[7] Stein, Jonathan Y. (2000), Digital Signal Processing: A Computer Science Perspective, Wiley Interscience, p. 384, ISBN 9780471295464

[8] Katz, Nicholas M. (2012), Convolution and Equidistribution : Sato-Tate Theorems for Finite Field Mellin Transformations, Princeton University Press, p. 146, ISBN 9780691153315

[9] Markovsky, Ivan; Rao, Shodhan (2008), "Palindromic polynomials, time-reversible systems and conserved quantities" (PDF), Control and Automation: 125–130, doi:10.1109/MED.2008.4602018, ISBN 978-1-4244-2504-4

[SV08-10] 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.

[11] Pless 1990, pg. 75, Theorem 48

[12] Pless 1990, pg. 77, Theorem 51

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

Properties

Palindromic and antipalindromic polynomials

Examples

Properties

Real coefficients

Conjugate reciprocal polynomials

Application in coding theory

See also

Notes

References

External links