Так как R£GF{q), то Л«==Л; так как (ж)-неприводимый многочлен степени то !/"£)? = (-1) YDi. Таким образом,

YW = RU{-~yi

Так как

S dim,

г= 1

S №-l) = m--r

Кх>« = л(-1Г-" П Ка = (-1Г-К£>.

Следовательно, YD G С/ (g) тогда и только тогда, когда т = г mod 2.

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

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

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

f{x) = fm П (-«0

положим

р(/)= SS

L(5iqF)2j

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

Утверждение теоремы вытекает непосредственно из леммы 6.66 при jn-k, m = iN- К) Kd, v™ = (n-i к -и Г = {-n-4kf. ш

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

6.68. Теорема Штикельбергера (для полей нечетной характеристики). Пусть q - степень нечетного простого числа. Пусть j [х) - нормированный многочлен степени т над GF (q), дискриминант D {/) которого отличен от нуля, а г ~- число неприводимых делителей f (х) над GF (q). Сравнение г = т mod 2 выполняется тогда и только тогда, когда D {/) есть квадрат в GF (q).

Доказательство. Рассмотрим сначала случай г = 1, т. е. случай, когда / (х) ненриводим над GF (q). Если а - некоторый корень f (х), то а g GF (g™), и остальные корни / (х) д-сопряжены с а. Следовательно, YD 6 GF (q™), так как в GF (q") выполняются равенства

0i<j:Sm-l

= ПП П =

l«i<3i=in-l ft

= (-\)-УЪ.

Если т нечетно, то YD" = VD, так что YDQGF(д). Если т четно, то YD ¥=YD, так что YDGF(q). Это доказывает теорему

дляг=1. Предположим теперь, что / (ж) = Пгде (ж),

1 = 1, ... ,г,- неприводимый многочлен степени dt над GF (q). Тогда DR]\Di, где Di = DiP>) и Л- ПП f)- Далее,

Ydr П YdI,

{YW=-R UVdI

ataj

aj/ai

. .1-.

= 2S S

1 , 1

1 , 1

-1 +

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

Доказательство. Если г=1, то f{x) неприводим и так что

тг(Р)= 2 2 (-[-j+7zJ-

Если положить J = i - i, то это равенство запишется в виде

т-1т-J

6.6. Четно или нечетно число неприводимых делителей? Полагая Р = а и Im - J, получим

m-i m-i

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

Тг(р)= S i=m-l. j=i

Следовательно, при г = 1 справедлива теорема 6.69, щ

6.693. Лемма. Если f (х) и g (х) - взаимно простые многочлены над GF (2"), то

Тг [р ifg)] = Тг [р (/)] Ч- Тг [р (g)].

Доказательство. Пусть а, а, «з, . . ., - корни / (х), а ат+1, «т+г, . . ., а+ь - корни g (х). Тогда, используя разбиение

m m+h

li£t<jm-bft lKJm m+li<j$m+ft i=l ;=m+l

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

Tr[p(/g)] = Tr[p(/)] + Tr[p(g)]4-

m m+ft

+ 2 2 L l-fa/ai +i + (aj/aiK i=l;=m+l

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

т m+ft m m-\-k

i=lj=m--l i=l,-=m+l

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

Так как «щ+ь «„+2, am+h-полное множество сопряженных

элементов, то множество а+и а+2, а+ь получается путем

12-658

GF (2"), то

r = mmod2

тогда и только тогда, когда Тг [р (/)] = О, где

тг(х)="2

1 = 0

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

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

6.691. Лемма.

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

перестановки из ат+и «тп+г» • • •> ат+». Следовательно, для каждого i

14-аЧ/аг l+a/ai* i=m+l i=m--l

Аналогично ai, ag, ..., есть перестановка элементов a?, а, ..., aj,,

так что для каждого /

Я 1 + а?/а? Р.1+а?

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

Доказательство теоремы 6.69, Пусть / (ж) =[]/*().

где каждый из многочленов (ж) неприводим над GF (2"). Тогда в GF{2), согласно леммам 6.693 и 6.692,

Тг[р(/)]= S Тг[р(/<*)] =S(<ieg/<*-l)=deg/-r..

i=l

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

6.695. Теорема. Если D (/) = [т1 (/)]2 - 4 (/) mod 8, где jT) () дискриминант многочлена f (х), и D, ц и 1, - многочлены от переменных /о, Л, • • /т с целыми рациональными коэффициен- . тами, то в GF (2")

Тг[р(/)] = Тг{.}.

Примеры. Дискриминант квадратного трехчлена общего вида /о -Ь + fiX + f2X равен D {/) = Я - fofa- Полагая г\ (/) = /i, I if) = /0/2, согласно теоремам 6.69 и 6.695, получаем, что квадратный трехчлен над GF (2") имеет четное число • неприводимых делителей над GF (2") тогда и только

тогда, когда Тг (/0/2 1) =0. , , , . 2 , з

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

D if) = mi - 27/g/i - 4/о/е - 4/f/3 + 18/0/1/2/3 =

(/1/2 + /о/з) - 4 (/§/! + /о/1 + Wz) mod 8.

Согласно теоремам 6.69 и 6.695, этот многочлен над GF (2") имеет нечетное число неприводимых делителей над GF{2n) тогда и только тогда, когда

/g/i+/o/i+/j/3

L {hf2 + f0f3) J

= 0.

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

fi(/)=. ПП («.-+«)

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

Аналогично функция [б {f)Y р (/) как симметрический многочлен от корней / (ж) может быть представлена в виде многочлена от /о1 /ц • • •> fm-i с целыми рациональными коэффициентами. Так как

{at - ajf = (аг + ajf - Aatccj,

(/)=[«(/)]» ПП L*-

m-1 m

=[6(/)]»-{6(/)i« 2 S

t=ii=i+i

m-1 m m-1 m

(ai + ay)2j

16aia;ajaj

i=ij=i+i/=t j=j+i

-64...=

=i+i

J>j, если I=i

s[S(/)]a 4[6(/)]V(/)mod8. Согласно предположению,

D (/) = [Т1 (Z)] - 4i (/) mod 8.

Так как

In if)? 1(f)

[ti if)? = [6 {f)V mod 4, T] (/) б (/) mod 2,

б (/) -b 2y (/),

[6 (f)] + 46 (/) V (/) + 4 [y (/)l

[6 (/)]= P (/) + б (/) Y (/) -f [y (/)]2 mod 2.

Следовательно, в GF (2")

[n(/)]

. = P(/)

У if)

Y(/)

L б (/).