Полином перестановки - Permutation polynomial

В математика, а перестановочный многочлен (для данного звенеть ) это многочлен что действует как перестановка элементов кольца, т. е. карту ${\displaystyle x\mapsto g(x)}$ это биекция. В случае, если кольцо конечное поле, то Полиномы Диксона, которые тесно связаны с Полиномы Чебышева, приведите примеры. Над конечным полем каждая функция, в частности, каждая перестановка элементов этого поля, может быть записана как полиномиальная функция.

В случае конечных колец Z/пZ, такие полиномы также изучались и применялись в перемежитель компонент обнаружение и исправление ошибок алгоритмы.^[1][2]

Многочлены перестановки одной переменной над конечными полями

Позволять F_q = GF (q) конечное поле характеристика п, то есть поле, имеющее q элементы, где q = п^е для некоторых премьер п. Полином ж с коэффициентами в F_q (символически записывается как ж ∈ F_q[Икс]) это перестановочный многочлен из F_q если функция из F_q себе определяется ${\displaystyle c\mapsto f(c)}$ это перестановка F_q.^[3]

Из-за конечности F_q, это определение можно выразить несколькими эквивалентными способами:^[4]

• функция ${\displaystyle c\mapsto f(c)}$ является на (сюръективный );
• функция ${\displaystyle c\mapsto f(c)}$ является один к одному (инъективный );
• ж(Икс) = а имеет решение в F_q для каждого а в F_q;
• ж(Икс) = а имеет уникальный решение в F_q для каждого а в F_q.

Характеристика того, какие полиномы являются полиномами перестановок, дается формулой

(Эрмит критерий)^[5][6] ж ∈ F_q[Икс] является перестановочным многочленом F_q тогда и только тогда, когда выполняются следующие два условия:

1. ж имеет ровно один корень в F_q;
2. для каждого целого числа т с 1 ≤ т ≤ q − 2 и ${\displaystyle t\not \equiv 0\!{\pmod {p}}}$, сокращение ж(Икс)^т мод (Икс^q − Икс) имеет степень ≤ q − 2.

Если ж(Икс) является перестановочным многочленом, определенным над конечным полем GF (q), то так грамм(Икс) = а ж(Икс + б) + c для всех а ≠ 0, б и c в GF (q). Полином перестановки грамм(Икс) в нормализованная форма если а, б и c выбраны так, чтобы грамм(Икс) является моник, грамм(0) = 0 и (при условии характеристики п не делит степень п полинома) коэффициент при Икс^п-1 равно 0.

Есть много открытых вопросов, касающихся многочленов с перестановками, определенных над конечными полями (см. Лидл и Маллен (1988) и Лидл и Маллен (1993) ).

Малая степень

Критерий Эрмита требует больших вычислительных ресурсов и может быть трудным для использования при теоретических выводах. Тем не мение, Диксон смог использовать его, чтобы найти все полиномы перестановки степени не выше пяти по всем конечным полям. Вот эти результаты:^[7][6]

Нормализованный многочлен перестановки Fq	q
${\displaystyle x}$	любой ${\displaystyle q}$
${\displaystyle x^{2}}$	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{3}}$	${\displaystyle q\not \equiv 1\!{\pmod {3}}}$
${\displaystyle x^{3}-ax}$ (${\displaystyle a}$ не квадрат)	${\displaystyle q\equiv 0\!{\pmod {3}}}$
${\displaystyle x^{4}\pm 3x}$	${\displaystyle q=7}$
${\displaystyle x^{4}+a_{1}x^{2}+a_{2}x}$ (если его единственный корень в Fq равно 0)	${\displaystyle q\equiv 0\!{\pmod {2}}}$
${\displaystyle x^{5}}$	${\displaystyle q\not \equiv 1\!{\pmod {5}}}$
${\displaystyle x^{5}-ax}$ (${\displaystyle a}$ не четвертая степень)	${\displaystyle q\equiv 0\!{\pmod {5}}}$
${\displaystyle x^{5}+ax\,(a^{2}=2)}$	${\displaystyle q=9}$
${\displaystyle x^{5}\pm 2x^{2}}$	${\displaystyle q=7}$
${\displaystyle x^{5}+ax^{3}\pm x^{2}+3a^{2}x}$ (${\displaystyle a}$ не квадрат)	${\displaystyle q=7}$
${\displaystyle x^{5}+ax^{3}+5^{-1}a^{2}x}$ (${\displaystyle a}$ произвольный)	${\displaystyle q\equiv \pm 2\!{\pmod {5}}}$
${\displaystyle x^{5}+ax^{3}+3a^{2}x}$ (${\displaystyle a}$ не квадрат)	${\displaystyle q=13}$
${\displaystyle x^{5}-2ax^{3}+a^{2}x}$ (${\displaystyle a}$ не квадрат)	${\displaystyle q\equiv 0\!{\pmod {5}}}$

Список всех монических перестановочных многочленов шестой степени в нормализованной форме можно найти в Шаллу и Ванлесс (2013).^[8]

Некоторые классы перестановочных многочленов

Помимо приведенных выше примеров, следующий список, хотя и не исчерпывающий, содержит почти все известные основные классы многочленов с перестановками над конечными полями.^[9]

• Икс^п переставляет GF (q) если и только если п и q − 1 находятся совмещать (условно, (п, q − 1) = 1).^[10]
• Если а в GF (q) и п ≥ 1 затем Многочлен Диксона (первого вида) D_п(Икс,а) определяется

${\displaystyle D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.}$

Их также можно получить из рекурсия

${\displaystyle D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),}$

с начальными условиями ${\displaystyle D_{0}(x,a)=2}$ и ${\displaystyle D_{1}(x,a)=x}$Первые несколько многочленов Диксона:

${\displaystyle D_{2}(x,a)=x^{2}-2a}$

${\displaystyle D_{3}(x,a)=x^{3}-3ax}$

${\displaystyle D_{4}(x,a)=x^{4}-4ax^{2}+2a^{2}}$

${\displaystyle D_{5}(x,a)=x^{5}-5ax^{3}+5a^{2}x.}$

Если а ≠ 0 и п > 1 тогда D_п(Икс, а) переставляет GF (q) если и только если (п, q² − 1) = 1.^[11] Если а = 0 тогда D_п(Икс, 0) = Икс^п и предыдущий результат остается в силе.

• Если GF (q^р) является расширение из GF (q) степени р, то линеаризованный полином

${\displaystyle L(x)=\Sigma _{s=0}^{r-1}\alpha _{s}x^{q^{s}},}$

с α_s в GF (q^р), это линейный оператор на GF (q^р) над GF (q). Линеаризованный многочлен L(Икс) переставляет GF (q^р) тогда и только тогда, когда 0 - единственный корень L(Икс) в GF (q^р).^[10] Это условие можно алгебраически выразить как^[12]

${\displaystyle {\rm {{det}\left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).}}}$

Линеаризованные многочлены, которые являются многочленами перестановки над GF (q^р) сформировать группа под действием композиции по модулю ${\displaystyle x^{q^{r}}-x}$, которая известна как группа Бетти-Матье, изоморфная группе общая линейная группа GL (р, F_q).^[12]

• Если грамм(Икс) находится в кольце многочленов F_q[Икс] и грамм(Икс^s) не имеет ненулевого корня в GF (q) когда s разделяет q − 1, и р > 1 относительно просто (взаимно просто) с q − 1, тогда Икс^р(грамм(Икс^s))^{(q - 1)/s} переставляет GF (q).^[6]
• Лишь несколько других конкретных классов полиномов перестановок над GF (q) были охарактеризованы. Например, два из них:

${\displaystyle x^{(q+m-1)/m}+ax}$

куда м разделяет q − 1, и

${\displaystyle x^{r}(x^{d}-a)^{(p^{n}-1)/d}}$

куда d разделяет п^п − 1.

Исключительные полиномы

An исключительный многочлен над GF (q) является многочленом от F_q[Икс] который является перестановочным многочленом на GF (q^м) бесконечно много м.^[13]

Подстановочный многочлен над GF (q) степени не более q^1/4 является исключительным по GF (q).^[14]

Каждая перестановка GF (q) индуцирован исключительным многочленом.^[14]

Если многочлен с целыми коэффициентами (т.е. ℤ [Икс]) - перестановочный многочлен над GF (п) для бесконечно большого числа простых чисел п, то это композиция линейных многочленов и многочленов Диксона.^[15] (См. Гипотезу Шура ниже).

Геометрические примеры

Основная статья: Овал (проективная плоскость)

В конечная геометрия координатные описания определенных наборов точек могут предоставить примеры перестановочных многочленов более высокой степени. В частности, точки, образующие овал в конечном проективная плоскость, PG (2,q) с q степень двойки, может быть скоординирована таким образом, что связь между координатами задается о-полином, который является специальным типом перестановочного полинома над конечным полем GF (q).

Вычислительная сложность

Проблема проверки того, является ли данный многочлен над конечным полем перестановочным многочленом, может быть решена в полиномиальное время.^[16]

Подстановочные многочлены от нескольких переменных над конечными полями

Полином ${\displaystyle f\in \mathbb {F} _{q}[x_{1},\ldots ,x_{n}]}$ это многочлен перестановки в п переменные над ${\displaystyle \mathbb {F} _{q}}$ если уравнение ${\displaystyle f(x_{1},\ldots ,x_{n})=\alpha }$ точно ${\displaystyle q^{n-1}}$ решения в ${\displaystyle \mathbb {F} _{q}^{n}}$ для каждого ${\displaystyle \alpha \in \mathbb {F} _{q}}$.^[17]

Квадратичные перестановочные многочлены (QPP) над конечными кольцами

Для конечное кольцо Z/пZ можно построить квадратичные многочлены подстановки. На самом деле это возможно тогда и только тогда, когда п делится на п² для какого-то простого числа п. Конструкция на удивление проста, тем не менее, она может производить перестановки с некоторыми хорошими свойствами. Вот почему он был использован в перемежитель компонент турбокоды в Долгосрочное развитие 3GPP стандарт мобильной связи (см. техническую спецификацию 3GPP 36.212 ^[18] например стр.14 в версии 8.8.0).

Простые примеры

Учитывать ${\displaystyle g(x)=2x^{2}+x}$ для кольца Z/4Z.Один видит: ${\displaystyle g(0)=0;~g(1)=3;~g(2)=2;~g(3)=1}$, поэтому многочлен определяет перестановку

${\displaystyle {\begin{pmatrix}0&1&2&3\\0&3&2&1\end{pmatrix}}}$.

Рассмотрим тот же многочлен ${\displaystyle g(x)=2x^{2}+x}$ для другого кольца Z/8Z.Один видит: ${\displaystyle g(0)=0;~g(1)=3;~g(2)=2;~g(3)=5;~g(4)=4;~g(5)=7;~g(6)=6;~g(7)=1;}$, поэтому многочлен определяет перестановку

${\displaystyle {\begin{pmatrix}0&1&2&3&4&5&6&7\\0&3&2&5&4&7&6&1\end{pmatrix}}}$.

Кольца Z /п^kZ

Учитывать ${\displaystyle g(x)=ax^{2}+bx+c}$ для кольца Z/п^kZ.

Лемма: за k = 1 (т.е. Z/пZ) такой многочлен определяет перестановку только в случае а = 0 и б не равно нулю. Значит, многочлен не квадратичный, а линейный.

Лемма: за k> 1, p> 2 (Z/п^kZ) такой многочлен определяет перестановку тогда и только тогда, когда ${\displaystyle a\equiv 0{\pmod {p}}}$ и ${\displaystyle b\not \equiv 0{\pmod {p}}}$.

Кольца Z /пZ

Учитывать ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$, куда п_т простые числа.

Лемма: любой многочлен ${\displaystyle g(x)=a_{0}+\sum _{0<i\leq M}a_{i}x^{i}}$определяет перестановку для кольца Z/пZ тогда и только тогда, когда все многочлены ${\displaystyle g_{p_{t}}(x)=a_{0,p_{t}}+\sum _{0<i\leq M}a_{i,p_{t}}x^{i}}$ определяет перестановки для всех колец ${\displaystyle Z/p_{t}^{k_{t}}Z}$, куда ${\displaystyle a_{j,p_{t}}}$ остатки ${\displaystyle a_{j}}$по модулю ${\displaystyle p_{t}^{k_{t}}}$.

Как следствие, можно построить множество квадратичных многочленов с перестановками, используя следующую простую конструкцию. Учитывать ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$, предположить, что k₁ >1.

Учитывать ${\displaystyle ax^{2}+bx}$, так что ${\displaystyle a=0~mod~p_{1}}$, но ${\displaystyle a\neq 0~mod~p_{1}^{k_{1}}}$; предположить, что ${\displaystyle a=0~mod~p_{i}^{k_{i}}}$,я> 1. И предположим, что ${\displaystyle b\neq 0~mod~p_{i}}$ для всех я=1...л. (Например, можно взять ${\displaystyle a=p_{1}p_{2}^{k_{2}}...p_{l}^{k_{l}}}$и ${\displaystyle b=1}$Тогда такой многочлен определяет перестановку.

Чтобы убедиться в этом, заметим, что для всех простых чисел п_я,я> 1, редукция этого квадратичного многочлена по модулю п_я на самом деле является линейным полиномом и, следовательно, является перестановкой по тривиальной причине. Для первого простого числа мы должны использовать лемму, обсужденную ранее, чтобы увидеть, что она определяет перестановку.

Например, рассмотрим Z/12Z и полином ${\displaystyle 6x^{2}+x}$.Он определяет перестановку

${\displaystyle {\begin{pmatrix}0&1&2&3&4&5&6&7&8&...\\0&7&2&9&4&11&6&1&8&...\end{pmatrix}}}$.

Многочлены высшей степени над конечными кольцами

Полином грамм(Икс) для кольца Z/п^kZ является перестановочным полиномом тогда и только тогда, когда он переставляет конечное поле Z/пZ и ${\displaystyle g'(x)\neq 0~mod~p}$ для всех Икс в Z/п^kZ, куда грамм′(Икс) это формальная производная из грамм(Икс).^[19]

Гипотеза Шура

Позволять K быть поле алгебраических чисел с р в кольцо целых чисел. Термин «гипотеза Шура» относится к утверждению, что если многочлен ж определяется по K является перестановочным многочленом на р/п бесконечно много главные идеалы п, тогда ж - композиция многочленов Диксона, многочленов степени один и многочленов вида Икс^k. Фактически, Schur не делал никаких предположений в этом направлении. То, что он сделал, принадлежит Фриду,^[20] который дал ошибочное доказательство ложной версии результата. Верные доказательства были даны Тернвальдом ^[21]и Мюллер.^[22]

Примечания

1. Такешита, Оскар (2006). "Перемежители полиномов с перестановками: алгебро-геометрическая перспектива". IEEE Transactions по теории информации. 53: 2116–2132. arXiv:cs / 0601048. Дои:10.1109 / TIT.2007.896870.
2. Такешита, Оскар (2005). «Новое строительство для Коды LDPC с использованием полиномов перестановки над целыми кольцами ". arXiv:cs / 0506091.
3. Mullen & Panario 2013, п. 215
4. Lidl & Niederreiter 1997, п. 348
5. Lidl & Niederreiter 1997, п. 349
6. Mullen & Panario 2013, п. 216
7. Диксон 1958, стр. 63
8. Mullen & Panario 2013, п. 217
9. Лидл и Маллен 1988, п. 244
10. Lidl & Niederreiter 1997, п. 351
11. Lidl & Niederreiter 1997, п. 356
12. Lidl & Niederreiter 1997, п. 362
13. Mullen & Panario 2013, п. 236
14. Mullen & Panario 2013, п. 238
15. Mullen & Panario 2013, п. 239
16. Каял, Нирадж (2005). «Распознавание функций перестановки за полиномиальное время». ECCC  TR05-008. Отсутствует или пусто | url = (помощь) Более ранние исследования этой проблемы см .: Ма, Кеджу; фон цур Гатен, Иоахим (1995). «Вычислительная сложность распознавания функций перестановки». Вычислительная сложность. 5 (1): 76–97. Дои:10.1007 / BF01277957. МИСТЕР  1319494. Шпарлинский, И. Э. (1992). «Детерминированный тест для перестановки многочленов». Вычислительная сложность. 2 (2): 129–132. Дои:10.1007 / BF01202000. МИСТЕР  1190826..
17. Mullen & Panario 2013, п. 230
18. 3GPP TS 36.212
19. Солнце, Цзин; Такешита, Оскар (2005). «Перемежитель для турбокодов, использующий полиномы перестановки над целыми кольцами». IEEE Transactions по теории информации. 51 (1): 102.
20. Фрид М. (1970). «По догадке Шура». Michigan Math. Дж.: 41–55.
21. Турнвальд, Г. (1995). «По догадке Шура». J. Austral. Математика. Soc.: 312–357.
22. Мюллер, П. (1997). «Свободное доказательство гипотезы Шура с ограничением Вейля». Конечные поля и их приложения: 25–32.

Рекомендации

• Диксон, Л. Э. (1958) [1901]. Линейные группы с изложением теории поля Галуа. Нью-Йорк: Дувр.
• Лидл, Рудольф; Маллен, Гэри Л. (март 1988 г.). «Когда многочлен над конечным полем переставляет элементы поля?». Американский математический ежемесячник. 95 (3): 243–246. Дои:10.2307/2323626.
• Лидл, Рудольф; Маллен, Гэри Л. (январь 1993 г.). «Когда многочлен над конечным полем переставляет элементы поля? II». Американский математический ежемесячник. 100 (1): 71–74. Дои:10.2307/2324822.
• Лидл, Рудольф; Нидеррайтер, Харальд (1997). Конечные поля. Энциклопедия математики и ее приложений. 20 (2-е изд.). Издательство Кембриджского университета. ISBN  0-521-39231-4. Zbl  0866.11069. Глава 7.
• Mullen, Gary L .; Панарио, Даниэль (2013). Справочник конечных полей. CRC Press. ISBN  978-1-4398-7378-6. Глава 8.
• Shallue, C.J .; Ванлесс И.М. (март 2013 г.). «Подстановочные многочлены и многочлены ортоморфизма шестой степени». Конечные поля и их приложения. 20: 84–92. Дои:10.1016 / j.ffa.2012.12.003.