Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
С перестановочными многочленами связан ряд естественных вопросов. Во-
первых, само выяснение того, является данный многочлен перестановочным
или нет, представляет собой нетривиальную задачу. Критерии, полученные в
§ 1, могут эту задачу упростить. Однако общие условия для того, чтобы
многочлен был перестановочным, оказываются достаточно сложными. Поэтому
большой интерес представляют полученные в § 2 результаты о некоторых
типах перестановочных многочленов.
Перестановочные многочлены индуцируют перестановки элементов конечного
поля Fg и, следовательно, соответствуют элементам симметрической группы
Sq - группы всех подстановок на множестве из q элементов. Таким образом1,
если нам дан класс перестановочных многочленов поля Fg, замкнутый
относительно операции композиции (или композиции с последующим
приведением по модулю х? - х), то мы можем поставить вопрос, какая
подгруппа группы Sq представлена этим классом. § 3 посвящен исследованию
такого рода задач.
Связь между перестановочными и исключительными многочленами исследуется в
§ 4. При этом существенно применяется теория уравнений над конечными
полями.
Понятие перестановочного многочлена обобщается в § 5 путем перехода к
рассмотрению многочленов от нескольких переменных. Так как отдельные
многочлены от п> 2 переменных не могут
индуцировать отображения векторного пространства (F? в себя, то здесь
теряется связь многочленов с перестановками. Чтобы восстановить эту
связь, необходимо рассматривать системы многочленов. Это приводит к
понятию ортогональной системы многочленов. Далее в этом параграфе
изучаются основные свойства перестановочных многочленов от нескольких
переменных, а также ортогональных систем.
43В
Гл, 7. Перестановочные многочлены
§ 1. Критерии перестановочности многочленов
Многочлен f ? fg [х ] называется трестановочным многочленом поля fg, если
соответствующая ему полиномиальная функция f: Fg -> Fgi отображающая
элемент с б Fg в элемент f (с) ? Fg, является перестановкой элементов
поля F,r Очевидно, что если / является перестановочным многочленом поля
Fg, то для каждого а ? Fq уравнение / (х) = а имеет ровно одно решение в
поле Fg-Ввиду конечности поля Fq перестановочные многочлены над ним могут
быть определены и другими способами.
7.1. Лемма. Многочлен j ? Fg lx ] является перестановочным многочленом
поля Fq тогда и только тогда, когда выполняется одно из следующих
условий:
(i) функция f: с *-> f (с), с ? Fg, является отображением так
(ii) функция [: с i-> f (с), с ? fg, является взаимно однозначным
отображением;
(iii) для любого а ? fg уравнение f (х) = а имеет решение в пом Fg;
(iv) для любого а ? Fg уравнение f (х) = а имеет ровно одно решение в пом
Fg.
Если <p: Fg -+• Fg - произвольная функция, отображающая Fg в Fq, то
существует единственный многочлен g ? FgUl, deg (g) < q, являющийся
представлением отображения ф в том смысле, что g (с) - Ф (с) для всех с ?
Fq- Многочлен g можно найти, вычислив соответствующий интерполяционный
многочлен Лагранжа (см. теорему 1.71), или с помощью формулы
?(*}=-- Е ф(с)(1 (х~ су-1). (7.1)
Если отображение ф задано в виде полиномиальной функции, например ф: с*-
>/(с), с ? Fg, для некоторого /?Fg[xj, то искомый многочлен g может быть
получен из многочлена [ приведением последнего по модулю у? - х 1)
согласно следующему-результату:
7.2. Лемма. Если f, g^Fqlxj, то f (с) = g (с) для всех с ? Fg в том и
только том случае, когда f (х) = g (х) (mod (х? - - х)).
Доказательство. Согласно алгоритму деления многочленов, мы можем записать
f (х) g (х) = h (х) (х? - х) г (х), где К rGFgfx] и deg (г) < ц. Тогда f
(с) = g (с) для всех с ? Fg в том и только том случае, если г (с) = 0 для
всех с ? fq\ последнее эквивалентно тому, что г - 0. ?
*) Результат приведения многочлена / по модулю xq - х (см. определение на
стр. 40) обозначается через f (mod (xq - я)). - Прим. перев.
§ 1. Критерии нерестановочностн многочленов
439
Установим теперь один полезный критерий того, что данный многочлен
является перестановочным. Нам потребуется следующая лемма.
7.3. Лемма. Пусть а&, alt ... , адЛ - элементы поля fg. Тогда следующие
два условия эквивалентны:
(i) аь, аи ..., ач_г все различны;
"-1 ( j 0 для t~ 0f 1, ..., q - 2,
оо sx = .; .
v /гг0 { - 1 для t - q - 1.
Доказательство. Для фиксированного i, такого, что 0</< ./ I, рассмотрим
многочлен
(*) -= 1 - Ё
/=0
*
Тогда, полагая 0° = I, получаем, что & (^} = I и ^ (6) - 0 для всех b ?
fg, Следовательно, многочлен
f -0 \ i=Q /
отображает каждый элемент поля fg в I тогда н только тогда, когда {аа,
ах, aq_t\ = Fg. Так как deg (g) < q, из леммы 7.2 следует, что многочлен
g отображает каждый элемент поля fg в I тогда и только тогда, когда g (х)
- I, что эквивалентно усло-вню (ii). ?
7.4. Теорема (критерий Эр ми та). Пусть р - характеристика тля fq. Тогда
многочлен / ? Fg U! является перестановочным многочленом поля Тд в том и
только том случае, если выполняются следующие два условия;
