6.6. Четно или нечетно число неприводимых делителей f(x) над GF(q)?

Хотя существенное улучшение общего алгоритма разложения разд. 6 1 представляется маловероятным, другие методы позволяют получить некоторую информацию о делителях многочлена с помощью значительно меньших усилий. Рассмотрим, например, школьную

формулу для корней квадратного уравнения с действительными коэффициентами. Если степень нечетного простого числа, не делящего а, то эта формула остается справедливой и над Таким образом, разрешимость квадратного уравнения над в этом поле зависит от того, является или не является дискриминант квадратом в Итак, квадратный многочлен имеет четное число (два) неприводимых делителей над если его дискриминант есть квадрат в и имеет нечетное число (один) неприводимых делителей над в противном случае. Это простейший пример одного общего результата, известного как теорема Штикельбергера. Для доказательства этой теоремы определим сначала дискриминант произвольного многочлена.

6.61. Определение. Дискриминант многочлена а, определяется равенством

Как мы увидим, дискриминант является частным видом одной функции от двух многочленов, называемой результантом и определяемой следующим образом:

6.62. Определение. Результат двух многочленов

задается равенством

Из этого определения сразу вытекают следующие свойства результанта. (Доказательство (6.622) следует непосредственно из

6.623. Если имеют общий делитель положительной степени, то

6.624. Если а и константы, не равные одновременно 0, то

6.625. Если то

6.626. Если то

Свойства позволяют вычислить применяя к алгоритм Евклида. Это означает, что результант может быть выражен через произведения, частные, суммы и разности коэффициентов этих многочленов. В частности, если многочлены над полем то даже если корни лежат не в

Теорема 6.63 дает выражение для дискриминанта нормированного многочлена степени

6.63. Теорема.

Доказательство. Согласно свойству 6.627,

где

Тогда

Используя это соотношение между дискриминантом и результантом, можно вывести формулу для дискриминанта произведения.

6.64. Теорема. Если неприводимые многочлены, то

Доказательство. Пусть степени равны соответственно Тогда

Утверждение теоремы вытекает из равенства

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

6.65. Теорема.

Мы можем теперь вычислить непосредственно дискриминанты некоторых многочленов. Рассмотрим, например, квадратный трехчлен Имеем

Квадратный трехчлен является частным случаем трехчлена общего вида дискриминант которого был вычислен Суоном [1962].

6.66. Лемма Суона. Результант двух биномов определяется равенством

где

Доказательство. Если а — примитивный корень степени из единицы, то

Так как порядок равен то

и

6.67. Теорема Суона. Пусть Пусть Тогда дискриминант трехчлена определяется формулой

Доказательство. Для имеем

где

Утверждение теоремы вытекает непосредственно из леммы 6.66 при

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

6.68. Теорема Штикельбергера (для полей нечетной характеристики). Пусть степень нечетного простого числа. Пусть нормированный многочлен степени над дискриминант которого отличен от нуля, число неприводимых делителей над Сравнение выполняется тогда и только тогда, когда есть квадрат в

Доказательство. Рассмотрим сначала случай т. е. случай, когда неприводим над Если а — некоторый корень то а и остальные корни -сопряжены с а. Следовательно, так как в выполняются равенства

Если нечетно, то так что Если четно, то так что Это доказывает теорему для Предположим теперь, что где неприводимый многочлен степени над Тогда где и Далее,

Так как то так как неприводимый многочлен степени то Таким образом,

Так как

то

и

Следовательно, тогда и только тогда, когда

Если все неприводимые множители различны, то, согласно теореме Штикельбергера, с помощью можно определить, четно или нечетно число этих множителей. В силу теорем 6.63, 6.623 и тогда и только тогда, когда имеет кратные неприводимые делители. Эти свойства дискриминанта многочлена аналогичны свойствам функции Мёбиуса для чисел в теореме 3.41. Если многочлен (число) имеет некоторый кратный неприводимый множитель (простой множитель), то его дискриминант (функция Мёбиуса) равен нулю; если все неприводимые (простые) множители многочлена (числа) различны, то дискриминант (функция Мёбиуса) определяет четность числа неприводимых (простых) множителей.

Теорема Штикельбергера определяет четность числа неприводимых множителей многочленов над полями с нечетной характеристикой при помощи дискриминанта многочлена. Для полей характеристики 2 дискриминанта недостаточно, но четность числа неприводимых делителей многочлена можно определить с помощью другой симметрической функции от его корней, к описанию которой мы сейчас переходим.

6.689. Определение. Для

положим

6.69. Теорема. Если многочлен степени разлагающийся в произведение различных неприводимых множителей над

тогда и только тогда, когда где

Замечание. Мы отложим вычисление по коэффициентам до теоремы 6.695.

Доказательство теоремы 6.69 основано на трех леммах.

6.691. Лемма.

Доказательство. В поле характеристики 2

6.692. Лемма. При справедлива теорема 6.69.

Доказательство. Если то неприводим и так что

Если пололчить то это равенство запишется в виде

Полагая получим

Так как то в поле характеристики 2

Следовательно, при справедлива теорема 6.69.

6.693. Лемма. Если взаимно простые многочлены над то

Доказательство. Пусть корни корни Тогда, используя разбиение

согласно лемме 6.691, получаем

Следовательно, лемма 6.693 эквивалентна утверждению, что

Докажем теперь равенство (6.694), показав, что обе его части совпадают с

Так как полное множество сопряженных элементов, то множество получается путем

перестановки Следовательно, для каждого

Аналогично есть перестановка элементов так что для каждого

Это доказывает равенство (6.694) и лемму 6.693.

Доказательство теоремы 6.69. Пусть где каждый из многочленов неприводим над Тогда в согласно леммам 6.693 и 6.692,

Теорема 6.69 позволяет определить четность числа неприводимых делителей многочлена с помощью Определение 6.689 задает функцию через корни многочлена которые часто бывают неизвестны. Практически воспользоваться теоремой 6.69 можно лишь тогда, когда функция выражена через коэффициенты многочлена Одну из таких возможностей дает теорема 6.695.

6.695. Теорема. Если где дискриминант многочлена многочлены от переменных с целыми рациональными коэффициентами, то в

Пример Дискриминант квадратного трехчлена общего вида равен Полагая согласно теоремам получаем, что квадратный трехчлен над имеет четное число неприводимых делителей над тогда только тогда, когда

Дискриминант кубического многочлена общего вида задается функцией

Согласно теоремам 6.69 и 6.695, этот многочлен над имеет нечетное число неприводимых делителей над тогда и только тогда, когда

Доказательство теоремы 6.695. Не нарушая общности рассуждений, можно считать, что многочлен нормирован. Рассмотрим функцию

Так как симметрическая функция от корней то она может быть также представлена в виде многочлена от как коэффициенты этого представления — целые рациональные числа, то оно имеет место в любом поле. Это следует из хорошо известной теоремы о симметрических многочленах (Ван-дер-Варден [1931, § 26]).

Аналогично функция как симметрический многочлен от корней может быть представлена в виде многочлена от с целыми рациональными коэффициентами. Так как

то

Согласно предположению,

Так как

то

Следовательно, в

и так как , то

В общем случае, если некоторый многочлен над то для определения четности числа неприводимых делителей надо отдельно вычислить и затем найти след Однако если многочлен над то возможно сокращение процедуры счета. Можно рассматривать как многочлен с целыми рациональными коэффициентами и вычислять его дискриминант по модулю Если то [так как если то [так как Если то четно и имеет кратные делители над

Сочетание двоичного варианта теоремы Штикельбергера и теоремы Суона приводит к следующему утверждению.

6.696. Следствие Суона. Пусть Предположим, что точно одно из чисел к нечетно. Многочлен имеет четное число неприводимых делителей над тогда и только тогда, когда

1) четно, к нечетно, или

2) нечетно, к четно, к

3) нечетно, к четно, к

Доказательство. Из теоремы Суона 6.67 вытекает, что

По предположению к и нечетные числа, так что

Поэтому утверждение теоремы следует из рассмотрения вычетов числа в каждом из следующих четырех случаев:

В случае , и этот случай можно дальше не рассматривать.