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

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

Если ввести в рассмотрение многочлен нулевой степени, то получил, что

Производящую функцию

для последовательности назовем нумератором множества

Пусть - нумератор множества где произвольный неприводимый многочлен степени Запишем множество многочленов где Нумератором этого множества назовем производящую функцию Здесь число многочленов степени к в множестве Ясно, что если произведение имеет степень k, то поэтому .

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

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

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

Пусть, например, — множество степеней многочлена множество степеней многочлена Тогда множество двоичных многочленов, распадающихся только на линейные неприводимые множители. В соответствии с теоремой 3.31 нумератором этого множества является Далее

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

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

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

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

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

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

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

(см. скан)

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

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

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

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

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

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

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

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

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

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

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

3.35. Теорема

Сумма берется по всем делящим к, включая 1 и к. Некоторые свойства величин могут быть выведены непосредственно из этого уравнения. Прежде всего видно, что Далее, так как для всех то причем равенство достигается тогда и только тогда, когда к простое. В частности, Можно также получить грубую нижнюю ницу для замечая, что

так что

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

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

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

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