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

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

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

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

Пусть F _q = GF( q ) будет конечным полем характеристики p , то есть полем, имеющим q элементов, где q = p ^и для некоторого простого p . Многочлен f с коэффициентами из F _q (символически записанный как f ∈ F _q [ x ] ) является перестановки многочленом F _q, если функция из F _q в себя определяется формулой $c\mapsto f(c)$ является перестановкой F _q .

Ввиду конечности F _q это определение можно выразить несколькими эквивалентными способами:

• функция $c\mapsto f(c)$ находится на ( сюръективном );
• функция $c\mapsto f(c)$ является взаимно однозначным ( инъективным );
• f ( x ) = a имеет решение в F _q для каждого a из F _q ;
• f ( x ) = a имеет единственное решение в F _q для каждого a из F _q .

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

( Эрмита критерий ) f ∈ F _q [ x ] является полиномом перестановки F _q тогда и только тогда, когда выполняются следующие два условия:

1. f имеет ровно один корень в F _q ;
2. для каждого целого числа t с 1 ≤ t ≤ q − 2 и $t\not \equiv 0\!{\pmod {p}}$, уменьшение f ( x ) ^т против ( х ^д - x ) имеет степень ≤ q - 2 .

Если f ( x ) является полиномом перестановки, определенным над конечным полем GF( q ) , то так же и g ( x ) = a f ( x + b ) + c для всех a ≠ 0, b и c в GF( q ) . Полином перестановки g ( x ) находится в нормализованной форме , если a , b и c выбраны так, что g ( x ) является моническим , g (0) = 0 и (при условии, что характеристика p не делит степень n полинома) коэффициент при х ^{п -1} равен 0.

Существует много открытых вопросов, касающихся полиномов перестановок, определенных над конечными полями.

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

Критерий Эрмита требует больших вычислительных ресурсов, и его может быть сложно использовать для теоретических выводов. Однако Диксон смог использовать его, чтобы найти все полиномы перестановок степени не выше пяти во всех конечных полях. Эти результаты:

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

Список всех монических перестановочных полиномов шестой степени в нормализованной форме можно найти в Shallue & Wanless (2013) .

Некоторые классы полиномов перестановки

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

• х ^н переставляет GF( q ) тогда и только тогда, когда n и q − 1 ( взаимно просты условно, ( n , q − 1) = 1 ).
• Если a находится в GF( q ) и n ≥ 1 , то полином Диксона (первого рода) D _n ( x , a ) определяется формулой $$D_{n}(x,a)=\sum _{j=0}^{\lfloor n/2\rfloor }{\frac {n}{n-j}}{\binom {n-j}{j}}(-a)^{j}x^{n-2j}.$$

Их также можно получить из рекурсии $$D_{n}(x,a)=xD_{n-1}(x,a)-aD_{n-2}(x,a),$$с начальными условиями $D_{0}(x,a)=2$ и $D_{1}(x,a)=x$.Первые несколько полиномов Диксона:

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

Если a ≠ 0 и n > 1 , то D _n ( x , a ) переставляет GF( q ) тогда и только тогда, когда ( n , q ² − 1) = 1 . Если a = 0 , то D _n ( x , 0) = x ^н и предыдущий результат имеет место.

• Если GF( q ^р ) является расширением GF ( q ) степени r , то линеаризованный полином $$L(x)=\sum _{s=0}^{r-1}\alpha _{s}x^{q^{s}},$$ с α _s в GF( q ^р ) , является линейным оператором на GF( q ^р ) над GF( q ) . Линеаризованный полином L ( x ) переставляет GF( q ^р ) тогда и только тогда, когда 0 является единственным корнем L ( x ) в GF( q ^р ) . Это условие можно выразить алгебраически как $$\det \left(\alpha _{i-j}^{q^{j}}\right)\neq 0\quad (i,j=0,1,\ldots ,r-1).$$

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

• Если g ( x ) находится в кольце многочленов F _q [ x ] и g ( x ^с ) не имеет ненулевого корня в GF( q ), когда s делит q − 1 и r > 1 относительно просто (взаимопросто) с q − 1 , тогда x ^р ( г ( х ^с )) ^{( q - 1)/ с} переставляет GF( q ) .
• лишь несколько других конкретных классов полиномов перестановок над GF( q ) Охарактеризовано . Например, два из них: $$x^{(q+m-1)/m}+ax$$ где m делит q − 1 и $$x^{r}\left(x^{d}-a\right)^{\left(p^{n}-1\right)/d}$$ где d делит p ^н − 1 .

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

над Исключительный многочлен GF ( q ) — это многочлен из F _q [ x ] , который является полиномом перестановки над GF( q ^м ) для бесконечно многих m .

Полином перестановки над GF( q ) степени не выше q ^1/4 является исключительным над GF( q ) .

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

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

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

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

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

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

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

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

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

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

Для конечного кольца Z / n Z можно построить квадратичные полиномы перестановок. На самом деле это возможно тогда и только тогда, когда n делится на p. ² для некоторого простого числа p . Конструкция удивительно проста, тем не менее, она может создавать перестановки с некоторыми хорошими свойствами. Именно поэтому он использовался в перемежителя компоненте турбокодов в 3GPP Long Term Evolution (см. техническую спецификацию 3GPP 36.212). стандарте мобильной связи например, страница 14 в версии 8.8.0).

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

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

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

Кольца З/ п ^к С

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

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

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

Кольца З/ н З

Учитывать $n=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{l}^{k_{l}}$, где p _t — простые числа.

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

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

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

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

Например, рассмотрим Z /12 Z и полином $6x^{2}+x$.Он определяет перестановку ${\begin{pmatrix}0&1&2&3&4&5&6&7&8&\cdots \\0&7&2&9&4&11&6&1&8&\cdots \end{pmatrix}}.$

Полиномы более высокой степени над конечными кольцами

Полином g ( x ) для кольца Z / p ^к Z является полиномом перестановки тогда и только тогда, когда он переставляет конечное поле Z / p Z и $g'(x)\neq 0{\bmod {p}}$ для всех х в Z / p ^к Z , где g ′( ) — формальная производная g x ( x ).

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

Пусть K — поле алгебраических чисел , а R — кольцо целых чисел . Термин «гипотеза Шура» относится к утверждению, что, если многочлен f, определенный над K, является многочленом перестановки на R / P для бесконечного числа простых идеалов P , то f является композицией полиномов Диксона, многочленов первой степени и многочленов. формы х ^к . На самом деле Шур не выдвигал никаких предположений в этом направлении. Идея, что он это сделал, принадлежит Фриду, который дал ошибочное доказательство ложной версии результата. Правильные доказательства дал Турнвальд. и Мюллер.

Ссылки

• Диксон, Л.Е. (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 . Збл   0866.11069 . Глава 7.
• Маллен, Гэри Л.; Панарио, Дэниел (2013). Справочник по конечным полям . ЦРК Пресс. ISBN  978-1-4398-7378-6 . Глава 8.
• Шаллу, CJ; Ванлесс, IM (март 2013 г.). «Полиномы перестановок и полиномы ортоморфизма шестой степени» . Конечные поля и их приложения . 20 : 84–92. дои : 10.1016/j.ffa.2012.12.003 .