92 Гл. 3. Число неприводимых q-ичных многочленов ааданной степени. причем irii - Q или 1 для всех i. Если положить

i(ПГO = o

ДЛЯ любого jUi > 2, то верхний предел суммирования можно увеличить до любого желаемого предела. В частности, мы можем записать

f(.[I.AO= 1... З+С.П.аО/ЩрГ-О.

i=l mi=0 m2=0

Это эквивалентно теореме 3.41.

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

где \i(d) -функция Мёбиуса,

1, если d=i, j,(d)= ( - 1), если d -произведение к различных простых чисел,

, О, если d делится на квадрат.

Формула обращения Мёбиуса может быть переписана также в другом виде. Если положить c-n/d, то получим

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

1, если га = 1, О, если п> 1.

S х id) =

Это эквивалентно свойству

/ m \ /1. если d-m,

d\n\m

если - собственный делитель.

Другими словами, как заметил Рота [1964], функция Мёбиуса является обращением дельта-функции в области целых чисел, в которой частичный порядок определяется отношением делимости. Если это установлено, то не составляет труда доказать, что если

/Н= S gid),

d, d\n]

gim)= 2 /Ht() •

n, nm

Доказательство проводится в одну строку:

п, d,

п\т d\n

d\m d{n\m

Аналогично можно доказать и другую форму теоремы.

3.42. Мультипликативная теорема обращения Мёбиуса. Если

f(n)==Uiid),

d, d\n

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

(m/n)

ПП Я(rf)<""> = П П =Ili{d) """" = И-1

п, d, d, п, d,

n\md\n d\m d\n\m d\m

Для перечисления неприводимых многочленов более полезна исходная форма обращения Мёбиуса. Из теорем 3.41 и 3.35 непосредственно следует

3.43. Теорема.

Vid)qWd),

d. dh

Если 5 = 2, то /i = 2, /2 = 1/2(2-2) = 1, /3 = 7з(23-2)=2, /,= V4(2*-22) =3, /5 = V5(2-2) = 6, ....

Гл. 3. Число неприводимых д~ичных многочленов заданной степени

Задачи

Даже для больших значений к эта формула легко поддается обработке. Например,

ho = Veo (2" - 220 212 + 2" + 2» + 2* - 2*) = = 19 215 358 392 200 893. В обп];ем случае формула обращения Мёбиуса позволяет выразить

/ft как сумму 2 лей к.

членов, где j - число различных простых делите-

Задачи

3.1. Пусть задана производящая функция

f(z)={n\znf.

Найдя df/dz двумя разными способами, доказать, что для всех п

п п+1

2 (к+ 1)2 к\ (п - к)\ = (га + 1) 2 Я (га + 1 - у)!. Расходимость ряда / (z)

ft=o 3=0

не должна смущать читателя. Проверьте тождество для ге = 3, показав, что обе его части равны 256.

3.2. (а) Классы вычетов двоичных многочленов по модулю + -\- i образуют конечное поле из 32 элементов. Сколько нормированных неприводимых многочленов второй степени существует над этим полем?

(Ь) Двоичный БЧХ-код с исправлением двойных ошибок, описанный в разд. 1.4, имеет блоковую длину п = 31, 10 проверочных позиций и 21 информационных позиций. Ему сцответствуют 2" возможных синдромов. Сколько и» них соответствуют смежным классам, лидеры которых соответственно имеют веса О, 1, 2, >3? (Четыре вопроса.) Какова процедура декодирования, когда полученный вектор лежит в смежном классе с лидером веса ЗГ

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

(a) Многочлены, представимые в виде квадрата.

Ответ: -.--.

1 - gz

(b) Произведения различных неприводимых множителей.

1 - qz

Ответ:

i - qz

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

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

1 - дг + (1 - d - Я)

Отвот:

Ответ:

Указание. См. уравнение (3.33).

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

- 1 + (1 - gz)/(l - gz) 2

Ответ:

(е) Произведения нелинейных неприводимых множителей. (1-г)9

i - qz II \\ - zm)

(f) Произведения различных нелинейных неприводимых множителей.

Ответ:

1 -gz2

{\~gz) (1 + г)? •

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

Ответ:

(1 -gz2)/(l ~gz)(l + z)g + (1 -gz)/(l -z)g 2

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

Ответ:

(l-gz2)/(l-gz) (14-z)9-(l-gz)/(l-z)g 2

3.4. Выразить каждую из полученных в задаче 3.3 производящих функций в виде явного степенного ряда от г. Можно положить q = 2.

Указание. Использовать разложение на простые дроби.

3.5. Сколько различных ожерелий длины т можно составить из бусинок д заданных цветов? Два ожерелья считаются одинаковыми тогда и только тогда, когда они могут быть получены друг из друга вращением. Например, 001101 совпадает с 101001, но отлично от 001011. Ожерелье 001011 может быть получено из 001101 с помощью замены нулей и единиц, но не может быть получено из него вращением.

3.6. Доказать, что ожидаемое число неприводимых делителей случайно пыбранного многочлена достаточно большой степени п над конечным полем порядка q приблизительно равно In п.

Указание. Пусть F (у, г) = [] (1 - yz™)™. Рассматривая F (у, z) как

производящую функцию от двух переменных, вычислить дР/ду при у = И

4.2. Мультипликативная структура конечных полей

Глава 4 Структура конечных полей

4.1. Определения

Возможны различные эквивалентные определения поля. Мы пред-лочтем несколько избыточное, но менее формальное определение.

4.11. Определение поля. Полем называется множество, в котором однозначно определен результат сложения и умножения {обозначения + и * соответственно) любых двух элементов. Поле содержит О и 1. Сложение и умножение ассоциативны и коммутативны, а умножение, как обычно, дистрибутивно относительно сложения: и* (v -\-w) = u*v -\- u*w. Каждый элемент и имеет единственный противоположный элемент -и, такой, что и -f- {-и) = 0. Каждый ненулевой элемент и имеет единственный обратный элемент 1/и,, такой, что и * (1/ы) = 1. Для каждого элемента и выполняются равен-; ства 0 + u = u = u = 1*uhO*u = 0.

Эти свойства поля не все независимы; некоторые из них могут быть выведены из других. Читатель, интересующийся минимизацией числа аксиом, определяющих поле, может найти дальнейшее обсуж- дение этого вопроса в книгах Биркгофа и Маклейна [1965] или ВаН: дер-Вардена [1931]. Для наших целей более удобно постулироват! все перечисленные выше свойства.

Порядком поля называется число его элементов. Если порядо! поля бесконечен, то оно называется бесконечным; если порядок noEii конечен,, то оно называется конечным. Множества рациональш чисел, действительных чисел и комплексных чисел дают пример* бесконечных полей. Если р - простое число, то классы вычето] по модулю р образуют конечное поле порядка р. Если / (х) - nenpi водимый многочлен степени т с коэффициентами из поля классе вычетов по модулю р, то классы вычетов ) по модулю / (х) образув конечное поле порядка р"". В разд. 4.4 мы покажем, что все конечнь поля по существу являются полями этого типа.

1) Читатель, не знакомый с этой терминологией, должен понимать поЯ классами вычетов по модулю / (х) все многочлены, степени которых не превосх(г дят степень / (х), с арифметическими операциями, определенными по модул

4.2. Мультипликативная структура конечных полей

Если поле содержит элемент а, то оно должно содержать и все степени а, а, а, . . . . Так как поле содержит мультипликативный обратный каждого ненулевого элемента, то ему принадлежат также сб"1, а~, а-, .... Если не все степени а различны, то существуют такие два числа тип, что /га > п и а"* = а", или а™"" = 1. Наименьшее из положительных чисел п, для которых а" = 1, называется порядком элемента а. Если порядок а равен п, то элементы 1, а, а, . . ., а"-1 различны. Действительно, если а" = а, где О т <: к <. п, то а*-™ = 1, хотя О < А: - яг < ге, что противоречит определению порядка. Таким образом, порядок элемента равен числу различных степеней этого элемента. Если элемент имеет бесконечное число различных степеней, то мы говорим, что его порядок бесконечен. Порядок элемента О не определен. Поле одновременно может содержать элементы конечного и бесконечного порядка, например, поле действительных чисел содержит два элемента конечного порядка: +1 (порядка 1) и -1 (порядка 2). Все остальные ненулевые действительные числа имеют бесконечный порядок. В поле комплексных чисел элементы конечного порядка исчерпываются числами efti/n кип - целые числа, а i = = К - 1. Таким образом, в некоторых полях только особые элементы имеют конечный порядок. В конечном поле, однако, каждый элемент имеет только конечное число различных степеней. Следовательно, каждый ненулевой элемент конечного поля имеет конечный порядок.

Если а - элемент порядка п, то легко найти порядок а". Согласно алгоритму деления, т = jn + к, где О А; < п. Тогда =

= а"а = 1 а = а. Следовательно,

а"* = а тогда и

только тогда, когда т = к mod п. Это доказывает теорему .4.21.

4.21. Теорема. Если а - элемент порядка -п, то а" = 1 тогда и только тогда, когда т кратно п.

Покажем далее, что если два элемента поля имеют взаимно про-<Ti,ie порядки, то порядок их произведения равен произведению порядков сомножителей.

4.22. Теорема. Если порядог элемента а равен п, а порядок элемента Р равен т и (т, п) - \, то порядок af> равен тп.

Доказательство. Если {aY = 1, то а = В", а" = = р-"" = 1 и р-" = а"" = 1.

Так как а"" = 1 и (т, и) = 1, то А; кратно п; так как р-" = 1 и (щ, п) = 1, то А; кратно т. Следовательно, («Р) = 1 тогда и только тогда, когда к кратно тп. С другой стороны, если к кратно тп, то (ар) = «"р = 1. I

"-658