Взаимный многочлен

В алгебре дан многочлен

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

с коэффициентами из произвольного поля , его обратный многочлен или отраженный многочлен , ^[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}).

То есть коэффициенты $p *$ являются коэффициентами $p$ в обратном порядке. Взаимные многочлены естественным образом возникают в линейной алгебре как характеристический многочлен обратной матрицы .

В частном случае, когда поле представляет собой комплексные числа , когда

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

Многочлен $p$ называется самообратным или палиндромным , если $p (x) = p * (x)$ . Коэффициенты самообратного многочлена удовлетворяют соотношению $a i = a n - i$ для всех $i$ .

Характеристики

Взаимные многочлены имеют несколько связей со своими исходными многочленами, в том числе:

$a_{0}$
$p (x) = x n p * (x -1)$ .^[2]
$α$ является корнем многочлена $p$ тогда и только тогда, когда $α -1$ является корнем $p *$ .^[4]
Если $p (x) \neq x$ , то $p$ неприводимо тогда и только тогда, когда $p$ $*$ неприводимо. ^[5]
$p$ примитивентогда и только тогда, когда p $* примитивен$ .^[4]

Могут быть получены и другие свойства обратных многочленов, например:

Самообратный многочлен нечетной степени делится на x+1, следовательно, не является неприводимым, если его степень > 1.

Палиндромные и антипалиндромные многочлены

Самообратный многочлен также называется палиндромным, потому что его коэффициенты, когда многочлен записан в порядке возрастания или убывания степеней, образуют палиндром . То есть, если

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

— многочлен степени $n$ , то $P$ является палиндромным, если $a i = a n - i$ для $i = 0, 1, ..., n$ .

Аналогично, многочлен $P$ степени $n$ называется антипалиндромным , если $a i = - a n - i$ для $i = 0, 1, ..., n$ . То есть многочлен $P$ является антипалиндромным , если $P (x) = - P * (x)$ .

Примеры

Из свойств биномиальных коэффициентов следует, что многочлены $P (x) = (x + 1) n$ являются палиндромными для всех положительных целых чисел $n$ , тогда как многочлены $Q (x) = (x - 1) n$ являются палиндромными, когда $n$ четное, и антипалиндромными, когда $n$ нечетное .

Другие примеры палиндромных многочленов включают циклотомические многочлены и многочлены Эйлера .

Характеристики

Если $a$ является корнем многочлена, который является либо палиндромным, либо антипалиндромным, то ⁠1/ $а$ ⁠ также является корнем и имеет ту же кратность . ^[6]
Обратное верно: если для каждого корня $a$ многочлена значение ⁠1/ $а$ ⁠ также является корнем той же кратности, то многочлен является либо палиндромным, либо антипалиндромным.
Для любого многочлена $q$ многочлен $q + q *$ является палиндромным, а многочлен $q - q *$ является антипалиндромным.
Отсюда следует, что любой многочлен $q$ можно записать в виде суммы палиндромного и антипалиндромного многочленов, поскольку $q = (q + q *)/2 + (q - q *)/2$ . ^[7]
Произведение двух палиндромных или антипалиндромных многочленов является палиндромным.
Произведение палиндромного многочлена и антипалиндромного многочлена является антипалиндромным.
Палиндромный многочлен нечетной степени кратен $x + 1$ (он имеет корень –1), и его частное по $x + 1$ также является палиндромным.
Антипалиндромный многочлен над полем $k$ с нечетной характеристикой кратен $x - 1$ (имеет 1 в качестве корня), а его частное по $x - 1$ является палиндромным.
Антипалиндромный многочлен четной степени кратен $x 2 - 1$ (имеет корни −1 и 1), а его частное по $x 2 - 1$ является палиндромным.
Если $p (x)$ — палиндромный многочлен четной степени 2 $d$ , то существует многочлен $q$ степени $d$ такой, что $p (x) = x d q (x + ⁠ 1 / х ⁠)$ .^[8]
Если $p (x)$ — монический антипалиндромный многочлен четной степени 2 $d$ над полем $k$ нечетной характеристики , то его можно однозначно записать как $p (x) = x d (Q (x) - Q (⁠ 1 / х ⁠))$ , где $Q$ — мономический многочлен степени $d$ без постоянного члена.^[9]
Если антипалиндромный многочлен $P$ имеет четную степень $2n$ над полем $k$ нечетной характеристики, то его «средний» коэффициент (степени $n ) равен$ $0$ , поскольку $a n = - a 2 n - n$ .

Действительные коэффициенты

Многочлен с действительными коэффициентами, все комплексные корни которого лежат на единичной окружности в комплексной плоскости (то есть все корни имеют модуль 1), является либо палиндромным, либо антипалиндромным. ^[10]

Сопряженные обратные многочлены

Полином является сопряженно-обратным, если и самообратимым , если для масштабного коэффициента $ω$ на единичной окружности . ^[11] $p(x)\equiv p^{\dagger }(x)$ $p(x)=\omega p^{\dagger }(x)$

Если $p (z)$ — минимальный многочлен z $0$ с $| z 0 | = 1, z 0 \neq 1$ $и$ p $(z) имеет$ действительные коэффициенты , то $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})}}$

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

для некоторой константы $c$ , т.е. Суммируем от $i$ $= 0$ до $n$ и заметим, что 1 не является корнем $p$ . Приходим к выводу, что $c$ $= 1$ . $ca_{i}={\overline {a_{n-i}}}=a_{n-i}$

Следствием этого является то, что циклотомические многочлены $Φ n$ являются самообратными для $n > 1.$ Это используется в специальном числовом поле решета , чтобы позволить числам вида $x 11 \pm 1, x 13 \pm 1, x 15 \pm 1$ и $x 21 \pm 1$ быть факторизованными, используя преимущества алгебраических множителей с использованием многочленов степени 5, 6, 4 и 6 соответственно – обратите внимание, что $φ$ ( функция тотиента Эйлера ) показателей степени равна 10, 12, 8 и 12. ^{[ требуется ссылка ]}

Согласно теореме Кона , самообратимый многочлен имеет столько же корней в единичном круге, сколько и обратный многочлен его производной . ^[12]^[13] $\{z\in \mathbb {C} :|z|<1\}$

Применение в теории кодирования

Обратный многочлен находит применение в теории циклических кодов, исправляющих ошибки . Предположим, что $x n - 1$ можно разложить на множители в произведении двух многочленов, скажем, $x n - 1 = g (x) p (x)$ . Когда $g (x)$ генерирует циклический код $C$ , то обратный многочлен $p *$ генерирует $C ⊥$ , ортогональное дополнение C $.$ [ ^14] Кроме того, $C$ является самоортогональным (то есть $C \subseteq C ⊥)$ тогда и только тогда, когда $p *$ делит $g (x)$ . ^[15]

Смотрите также

Теорема Кона

Примечания

^ ab * Грэм, Рональд; Кнут, Дональд Э.; Паташник, Орен (1994). Конкретная математика: основа компьютерной науки (Второе изд.). Reading, Mass: Addison-Wesley. стр. 340. ISBN 978-0201558029.
^ abc Aigner, Martin (2007). Курс перечисления . Berlin New York: Springer. стр. 94. ISBN 978-3540390329.
^ Роман 1995, стр.37
^ ab Pless 1990, стр. 57
↑ Роман 1995, стр. 37
^ Плесс 1990, стр. 57 только для палиндромного случая
^ Стайн, Джонатан Ю. (2000), Цифровая обработка сигналов: перспектива компьютерной науки , Wiley Interscience, стр. 384, ISBN 9780471295464
^ Дюран 1961
^ Кац, Николас М. (2012), Свертка и равнораспределение: теоремы Сато-Тейта для преобразований Меллина в конечных полях , Princeton University Press, стр. 146, ISBN 9780691153315
^ Марковский, Иван; Рао, Шодхан (2008). «Палиндромные многочлены, обратимые во времени системы и сохраняющиеся величины». 2008 16-я Средиземноморская конференция по управлению и автоматизации (PDF) . стр. 125–130. doi :10.1109/MED.2008.4602018. ISBN 978-1-4244-2504-4. S2CID 14122451. {{cite book}}: |journal=проигнорировано ( помощь )
^ Синклер, Кристофер Д.; Ваалер, Джеффри Д. (2008). «Самоинверсивные многочлены со всеми нулями на единичной окружности». В Макки, Джеймс; Смит, К.Дж. (ред.). Теория чисел и многочлены. Труды семинара, Бристоль, Великобритания, 3–7 апреля 2006 г. Серия заметок к лекциям Лондонского математического общества. Том 352. Кембридж: Издательство Кембриджского университета . С. 312–321. ISBN 978-0-521-71467-9. Збл 1334.11017.
^ Ancochea, German (1953). «Нули самообратимых многочленов». Труды Американского математического общества . 4 (6): 900–902. doi : 10.1090/S0002-9939-1953-0058748-8 . ISSN 0002-9939.
^ Бонсалл, ФФ; Марден, Моррис (1952). «Нули самообратимых многочленов». Труды Американского математического общества . 3 (3): 471–475. doi : 10.1090/S0002-9939-1952-0047828-8 . ISSN 0002-9939.
^ Плесс 1990, стр. 75, Теорема 48
^ Плесс 1990, стр. 77, Теорема 51

Ссылки

Плесс, Вера (1990), Введение в теорию кодов, исправляющих ошибки (2-е изд.), Нью-Йорк: Wiley-Interscience, ISBN 0-471-61884-5
Роман, Стивен (1995), Теория поля , Нью-Йорк: Springer-Verlag, ISBN 0-387-94408-7
Дюран, Эмиль (1961), «Masson et Cie: XV - многочлены без коэффициентов, симметричных или антисимметричных», Solutions numériques des équations algrébriques , vol. Я, стр. 140–141.

Внешние ссылки

«Основная теорема для палиндромных многочленов». MathPages.com .
Вайсштейн, Эрик В. "Взаимный многочлен". MathWorld .