3.3. Число неприводимых нормированных О-ичных многочленов заданной степени

Обозначим через А, число двоичных многочленов степени к вида /" {х), где / {х) - неприводимый двоичный многочлен степени т. Так как степень f {х) равна jm, то

f 1, если т\к, \ О, если т \ к.

Если ввести в рассмотрение многочлен /" (х) = 1 нулевой степени, то получим, что = 1. Производящую функцию

ДЛЯ последовательности {А) назовем нумератором множества {Г (х), i = О, 1, 2, . . .}.

Пусть В (z) = -jz--нумератор множества {g {х)), где;

g (х) - произвольный неприводимый многочлен степени п. Запи- j шем множество многочленов Л = {/ (х) g {х)), где i, j =0, 1, 2 . . . . Нумератором этого множества назовем производящую!

оо 1

функцию с (z) = S h- Здесь - число многочленов степени Л

=0 - I

в множестве Л. Ясно, что если произведение f (х) g (х) имеет сте- пень /с, то 7 = /<; - i и поэтому = 2 iB-u а С (z) = 4 (2) В (z)J

В общем случае, если А (z) - нумератор множества многочлене! h () и () • • • 3 (2) - нумератор множества многочлено! fi ()> fa • • причем любые два многочлена (х) и gj (х) взаим но просты, то С (2) = 4 (2) В (2) является нумератором множеств? всех произведений вида U () Sj (а:), причем, как и раньше, Cft

С помощью индукции этот результат может быть распространев на произвольное число множеств:

3.31. Теорема. Пусть 2, . • - множества много

членов, обладающие тем свойством, что любые два многочлена различных множест£ взаимно просты. Пусть 81*82*- - - мноз ство всех многочленов вида fifi, • • •, fin. де многочлены fi - {х) прь надлежит различным St.. Тогда нумератор множества 8*8*. . имеет вид [Jt*) (2), где А> (z) - нумератор множества 8i.

1) /с-й коэффициент нумератора -число многочленов степени к в множе стве fi(x), / (х), ... .-Прим. ред.

Пусть, например, 8 - множество степеней многочлена а:, а .$2 - множество степеней многочлена х -\- i. Тогда 8*82 - множество двоичных многочленов, распадающихся только на линейные неприводимые множители. В соответствии с теоремой 3.31 нумератором этого множества является [1/(1 - 2)]. Далее

(1-Z)2

dz 1-2

(Z):=nZn-={k+i)z\

n=0 n=l ft=0

Следовательно, существует точно к -\- I двоичных многочленов степени к, разлагающихся в произведение линейных множителей. Это согласуется с рассуждениями, предшествующими уравнению (3.11).

Аналогично, нумератором множества двоичных многочленов, неприводимые делители которых содержатся среди многочленов х, X i, х -\- X -\- I, является функция

\ i-Z I 1-Z2*

Более того, нумератор множества двоичных многочленов, среди неприводимых множителей которых содержится 1 неприводимых многочленов степени 1, I, неприводимых многочленов степени 2, /3 неприводимых многочленов степени 3, . . ., равен

П (-т)--

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

Мы получаем, таким образом, двоичный вариант следующей общей

теоремы:

3.32. Теорема. Пусть обозначает число различных неприводимых нормированных многочленов степени т над конечным полем из q элементов. Тогда

i - qz П ( 1-zm ) •

г Множество произведений степеней-» \ = \ неприводимых нормированных

Доказательство, f Множество всех норми--;

{ рованных многочленов } = \ неприводимых нормированных , - <- многочленов

Ясно, что теорема 3.32 является количественным уточнением теоремы о единственности разложения нормированных многочленов над конечным полем из q элементов.

Если приравнять коэффициенты в обоих частях равенства, то мы получим аналог вычислений при грубом методе подсчета чисел /„. Например, в двоичном случае мы знаем, что = 2, 1 = \, 1д = 2. Можно теперь найти 1, приравнивая коэффициенты при

в правой и левой частях равенства

+ 2z + 4z2 + 8z3 + 16z* + . . . =

= (1 + z + z2 + z3 + z* + . . .)2 (1 + z«

(1 + z3 + z« + . .

+ г* + . . .)

У (1 + z* +

Вычисление коэффициента при z* в правой части этого соотношения требует такой же вычислительной работы, как и грубый метод, описанный в разд. 3.1. В этом смысле переход к языку производяш;их функций не дает нам ничего нового, кроме корректных обозначений для сложных выкладок грубого метода.

Однако в другом направлении производяш;ие функции дают нам нечто новое, поскольку над ними можно производить алгебраические операции. Например, обраш;ая равенство (3.32), получаем

(3.33)

i-qz= П (1-Z"

Уравнение (3.33) имеет интересную интерпретацию. Так

нумератор множества многочленов, разлагающих-

П (1 + г"

ся в произведение различных неприводимых множителей, то

[] (1 - zy есть разность между нумератором множества много-

771=1

членов, являющихся произведениями четного числа различных неприводимых множителей и нумератором множества многочленов, являющихся произведением нечетного числа различных неприводи-! мых множителей. Нормированный многочлен степени О не является произведением неприводимых множителей, а каждый нормирован-; ный неприводимый д-многочлен степени 1 имеет один неприводимый множитель. Таким образом, уравнение (3.33) эквивалентно следую-; щей теореме:

3.34. Теорема. Если пг>2, то число нормированных много-членов степени т, являющихся произведением четного числа различных I

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

Теорема 3.34 справедлива для любого конечного поля.

Для выяснения других свойств чисел 1т произведем дальнейшие преобразования уравнения (3.33). Применяя следствие 3.22, получаем, что

mTmZ"- l-zm

771=1

Умножение на -z дает равенства

qz К} гт 2

2771

fe=l m=l ft, ft=l 771,

771 I ft 771 ft

Таким образом, имеет место 3.35. Теорема

2 mim-

771, 77lft

Сумма берется по всем т, делящим к, включая 1 и А;. Некоторые свойства величин могут быть выведены непосредственно из этого уравнения. Прежде всего видно, что 1 = q. Далее, так как О для всех т, то 1 {( - q)lk, причем равенство достигается тогда и только тогда, когда к простое. В частности, 1 = {q - q)l2 > 0; 3 = (?* - 9)/3 > 0. Можно также получить грубую нижнюю границу для /ft, замечая, что

ft/2

так что

III,

Отсюда следует, что > О для всех А; > 2. Так как мы видели, что /i > О и /2 > О, то, следовательно, над каждым конечным полем существуют неприводимые многочлены произвольной степени. Если / (х) - неприводимый многочлен степени т над полем классов вычетов mod р, то множество р*" классов вычетов по модулю многочлена f (х) образует конечное поле из р элементов. Это доказывает теорему 3.36. "

3.36. Теорема. Если р - простое число и т - произвольное натуральное число, то существует конечное поле, содержащее р элементов.

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

(3.37)

l(l 5-ft/2+l)<A <(l g-+l).

Для вывода выражения для необходимо воспользоваться формулой обращения Мёбиуса.

* 3.4. Формула обращения Мёбиуса Формула

является частным случаем формулы

nn)=g{d),

d I n

где g (d) - произвольная функция. Нашей задачей является отыскание формулы, явно выражающейчерез/. Если эта формула (см. 3.41) известна, то ее доказательство можно сделать значительно более коротким по сравнению с рассуждениями, связанными с ее выводом. Мы, однако, получим эту формулу, не предполагая ее заранее известной. Если

где -простые числа, то d делит п тогда и только тогда, когда

где 0<;/cj<;ej. Тогда формула

/(и)= ligid)

d, din

может быть записана в виде

/([Ь:о= S S ... S ип/-о-

г=1 fti=0ft2=0 ft ,-=0 г=1

Так как эта формула справедлива для всех значений п, то ее можно использовать для

в этом случае получаем, что

г=2 Й1=0Й2=0 kj=0 i=l

Вычитание дает равенство

S (-i)-V(pM1K0= S ••• SHpM1p-0.

ftl=n-l i=2 ft2=0 ft=0 * t=2

Таким образом, мы заменили одну из сумм для g суммой для /. Продолжая этот процесс, получим, что

ftl=ei-l Й2=е2-1 i=3

= S ••• S sipyUpb)

кз=0 kj=0 J=3

и, окончательно.

ftl==ei-l Й2=е2-1 hj=ej-l г=1 {=1.

Подстановка т, -- ej - ki дает

1 1

1=1 mi=0 т2=0 т~0

Эта формула выражает функцию g через функцию /. Она может быть также переписана в виде

и.1Ь:о= S S ••• S Allрт)f(йрг""),

4=1 mi=0m2=0 mj=0 i=i

j 2 "г

(П/ГO=(-l) ,