Перестановки, задаваемые многочленом.

[Профессор Снэйп]

Пусть $\mathbb{F}$ --- конечное поле. Легко заметить, что для любой функции $s : \mathbb{F} \to \mathbb{F}$ существует многочлен $p_s(x) \in \mathbb{F}[x]$, такой что $s(x) = p_s(x)$ для всех $x \in \mathbb{F}$. Вопрос такой: при каких (необходимых и достаточных) условиях на $p_s$ отображение $s$ является перестановкой $\mathbb{F}$.

Ничего лучше, чем существование многочлена $q \in \mathbb{F}[x]$ со свойством $p_s(q(x)) = q(p_s(x)) = x$ пока не придумал. Хотелось бы найти условие на коэффициенты многочлена. Больше всего интересует случай, когда $\mathbb{F}$ имеет характеристику $2$.

[Xaositect]

Ну как вариант, многочлен не является перестановкой тогда и только тогда, когда какие-то его значения совпадают, т.е. $p(x) = c + (x-a)(x-b)q(x), a\neq b$. Может, что нибудь полезное вылезет.

-- Вт янв 25, 2011 19:36:30 --

Или даже лучше наоборот: если не перестановка, то какое-то значение не принимается, т.е. $p-c$ неприводим для какого-то $c$. Отсюда мне кажется, что каких-то хороших условий на коэффициенты не предвидится.

[Профессор Снэйп]

Ну это понятно: отображение конечного множества в себя является перестановкой тогда и только тогда, когда оно инъективно, а также тогда и только тогда, когда оно сюрьективно. Что с этим дальше делать?

Пока дошёл вот до чего. Пусть $\mathbb{F}$ содержит $k = 2^l$ элементов. Тогда $x^{k-1}+1$ равно $1$ в нуле и нулю на остальных элементах, так что

$$ p_s(x) = \sum_{b \in \mathbb{F}} s(b)((x+b)^{k-1}+1) $$

Если $s$ перестановка, то сумма $\sum_{b \in \mathbb{F}} s(b)$ уходит в ноль и остаётся

$$ p_s(x) = \sum_{i \in A} \left(\sum_{b \in \mathbb{F}} b^is(b)\right) x^{k-1-i} + s(0), $$

где $A$ --- множество чисел из диапазона $[1,k-2]$, для которых число $C_{k-1}^i$ нечётно. Если для каждого $b \in \mathbb{F}$ составить вектор $(1,b,b^2,\ldots,b^{k-1})$, то все эти вектора линейно независимы, потому что соответствующая матрица --- матрица Вандермонда. И вот из этой матрицы берутся линейные комбинации строк с коэффициентами $s(b)$ и ставятся коэффициентами в $p_s$.

И что? Да похоже, ничего, по крайней мере я дальше ни асилил Единственное что ещё прослеживается --- если $s$ перестановка, то вектора-строки $(1, s(b), (s(b))^2, \ldots, (s(b))^{k-1})$ образуют ту же самую матрицу, только с переставленными строками. Матрица, увы, не ортогональна...

Можно ещё попробовать поитерировать $s$, что-нибудь посопрягать в группе перестановок и посмотреть, как всё это будет влиять на коэффициенты многочленов... Кропотливо всё очень, а будет ли какой-нибудь хороший результат --- не факт!

[Xaositect]

Ну вот и я говорю: раз для неприводимых многочленов хороших критериев на коэффициенты нет, то и у наших не будет.

[Профессор Снэйп]

P. S. Производные считать бесполезно, потому что характеристика $2$ --- очень подлая. Например, $p(x) = x^2$ задаёт перестановку (даже автоморфизм поля $\mathbb{F}$), а производная $p'(x)$ тождественно равна нулю

-- Вт янв 25, 2011 23:10:01 --

Xaositect в сообщении #404478 писал(а):

Ну вот и я говорю: раз для неприводимых многочленов хороших критериев на коэффициенты нет, то и у наших не будет.

Не, ну тута всё же несколько другой вопрос...

[Xaositect]

Ну с этим-то понятно - надо просто брать по модулю $x^{\sharp \mathbb{F}} - x$

[Профессор Снэйп]

Смущает несоизмеримость численных характеристик: всего $k!$ перестановок и $k^k$ многочленов степени $\leqslant k-1$.

Ладно, наложим ещё дополнительное условие:коэффициенты многочлена принадлежат множеству $\{ 0, 1 \}$, то есть многочлен принадлежит $\mathbb{F}_2[x]$. Что-нибудь легче становится?

-- Вт янв 25, 2011 23:21:57 --

Короче, это была очередная попытка почёсыванием левого уха через правое колено решить вот эту задачу. Когда-нибудь я её добью, собаку?! Сколько ночей убил за последние 4 года, а воз где был, там и остаётся

Самое обидное, что когда начинаешь искать все эти перестановки численным перебором, их там сотни тысяч вылазят. Правда, перебрать удаётся немного: порядки групп растут крайне стремительно и brute force быстро затыкается

[Xaositect]

Хмм.
Ну оно будет тогда перестановкой на $\{0,1\}$ :). Вообще надо посмотреть, какая цикловая структура у этой перестановки может быть

[Профессор Снэйп]

Xaositect в сообщении #404449 писал(а):

Ну как вариант, многочлен не является перестановкой тогда и только тогда, когда какие-то его значения совпадают, т.е. $p(x) = c + (x-a)(x-b)q(x), a\neq b$. Может, что нибудь полезное вылезет.

Я рассматривал $q_{a,b}(x) = p(ax) + p(bx)$. Если единица --- корень $q_{a,b}$ при $a \neq b$, то инъективность отсутствует.

При рассмотрении $p(ax) + p(bx)$ начинается задница с нечётными степенями

[Null]

$F(P(x))$не делиться на $x^k-x$ При $deg(F)<k,F\neq 0$

[Leox]

Лидл, Нидеррайтер, том 2. Глава 7. Перестановочные многочлены.