Обратный полином

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

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

с коэффициентами из произвольного поля , его обратным полиномом или отраженным полиномом , ^[1]^[2] обозначается $р *$ или $п Р$ , ^[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 * (х)$ .Коэффициенты обратного многочлена удовлетворяют условиям $a i = a n - i$ для всех $i$ .

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

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

$a_{0}$
$п (Икс) знак равно Икс н п * (х -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 * (х)$ .

Примеры

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

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

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

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

Реальные коэффициенты

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

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

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

Если $p (z)$ — минимальный многочлен от $z 0$ с $| я 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$ является корнем многочлена $z^{n}{\overline {p({\bar {z}}^{-1})}}$ который имеет степень $n$ . Но минимальный многочлен единственен, следовательно,

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

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

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

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

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

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

См. также

Теорема Кона

Примечания

^ Jump up to: ^а ^б * Грэм, Рональд; Кнут, Дональд Э.; Паташник, Орен (1994). Конкретная математика: основа информатики (второе изд.). Ридинг, Массачусетс: Аддисон-Уэсли. п. 340. ИСБН 978-0201558029 .
^ Jump up to: ^а ^б ^с Айгнер, Мартин (2007). Курс счета . Берлин Нью-Йорк: Спрингер. п. 94. ИСБН 978-3540390329 .
^ Роман 1995 , стр.37
^ Jump up to: ^а ^б Плесс 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. дои : 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 .
^ Анкочеа, Герман (1953). «Нули самоинвертирующих полиномов» . Труды Американского математического общества . 4 (6): 900–902. дои : 10.1090/S0002-9939-1953-0058748-8 . ISSN 0002-9939 .
^ Бонсолл, ФФ; Марден, Моррис (1952). «Нули самоинвертирующих полиномов» . Труды Американского математического общества . 3 (3): 471–475. дои : 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 - полиномы, коэффициенты которых симметричны или антисимметричны», Цифровые решения алгебраических уравнений , том. я, стр. 140–141

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

[concrete-1] Jump up to: ^а ^б * Грэм, Рональд; Кнут, Дональд Э.; Паташник, Орен (1994). Конкретная математика: основа информатики (второе изд.). Ридинг, Массачусетс: Аддисон-Уэсли. п. 340. ИСБН 978-0201558029 .

[Aigner-2] Jump up to: ^а ^б ^с Айгнер, Мартин (2007). Курс счета . Берлин Нью-Йорк: Спрингер. п. 94. ИСБН 978-3540390329 .

[3] Роман 1995 , стр.37

[Pless_1990_loc=pg._57-4] Jump up to: ^а ^б Плесс 1990 , с. 57

[Roman_1995_loc=_pg._37-5] Роман 1995 , стр. 37

[6] Плесс 1990 , стр. 57 только для палиндромного случая

[7] Стейн, Джонатан Ю. (2000), Цифровая обработка сигналов: перспектива компьютерных наук , Wiley Interscience, стр. 384, ISBN 9780471295464

[8] Дюран 1961

[9] Кац, Николас М. (2012), Свертка и равнораспределение: теоремы Сато-Тейта для конечных преобразований Меллина , Princeton University Press, стр. 146, ISBN 9780691153315

[10] Марковский, Иван; Рао, Шодхан (2008). «Палиндромные полиномы, обратимые во времени системы и сохраняющиеся величины». 2008 г. 16-я Средиземноморская конференция по управлению и автоматизации (PDF) . стр. 125–130. дои : 10.1109/MED.2008.4602018 . ISBN 978-1-4244-2504-4 . S2CID 14122451 . {{cite book}}: |journal= игнорируется ( помогите )

[SV08-11] Синклер, Кристофер Д.; Ваалер, Джеффри Д. (2008). «Самоинверсивные полиномы со всеми нулями на единичной окружности». В Макки, Джеймс; Смит, СиДжей (ред.). Теория чисел и полиномы. Материалы семинара, Бристоль, Великобритания, 3–7 апреля 2006 г. Серия лекций Лондонского математического общества. Том. 352. Кембридж: Издательство Кембриджского университета . стр. 312–321. ISBN 978-0-521-71467-9 . Збл 1334.11017 .

[12] Анкочеа, Герман (1953). «Нули самоинвертирующих полиномов» . Труды Американского математического общества . 4 (6): 900–902. дои : 10.1090/S0002-9939-1953-0058748-8 . ISSN 0002-9939 .

[13] Бонсолл, ФФ; Марден, Моррис (1952). «Нули самоинвертирующих полиномов» . Труды Американского математического общества . 3 (3): 471–475. дои : 10.1090/S0002-9939-1952-0047828-8 . ISSN 0002-9939 .

[14] Плесс 1990 , стр. 75, Теорема 48

[15] Плесс 1990 , стр. 77, Теорема 51

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]