6.4. ПОЛЯ И МНОГОЧЛЕНЫ

Значительная часть алгебраической теории кодирования основана на теории конечных полей. Грубо говоря, поле — это множество элементов, в котором сложение, вычитание, умножение и деление могут трактоваться как обычные правила арифметики. Более точной является следующая формулировка: поле — это множество по меньшей мере двух элементов, замкнутоё по двум операциям, называемым сложением и умножением и удовлетворяющее следующим аксиомам

1. Множество элементов образует абелеву группу по операции сложения.

2. Множество ненулевых элементов (где 0 является нейтральным элементом группы по операции сложения) образует абелеву группу по операции умножения.

3. Выполняется дистрибутивный закон

Легко непосредственно убедиться, что множество действительных чисел с обычными операциями сложения и умножения удовлетворяет этим аксиомам. Множество двоичных элементов 0 и 1 с операцией сложения по модулю 2 и обычным умножением также удовлетворяет этим аксиомам. Однако множество целых чисел не удовлетворяет этим аксиомам, поскольку любое целое число, большее 1, не имеет об; ратного по операции умножения элемента, который являлся бы целым числом.

Условимся всюду обозначать нейтральный по операции сложения элемент символом 0, а нейтральный по операции умножения элемент символом 1. Будем всюду обозначать обратные элементы по операциям сложения и умножения как соответственно.

Следующие соотношения выражают некоторые элементарные свойства полей:

Чтобы проверить справедливость (6.4.2), допустим, что произвольны и заметим, что Отсюда следует, что а является нейтральным элементом в группе по сложению [см. Соотношение (6.4.3) утверждает, что множество ненулевых элементов замкнуто по умножению; это следует из аксиомы 2. Чтобы проверить (6.4.4), запишем следующее соотношение

Поэтому является обратным элементом по операции сложения для а Вторая часть равенства (6.4.4) доказывается аналогично. Из (6.4.4) следует, что, не вызывая недоразумений, знак минус может использоваться без скобок; в дальнейшем мы так и будем поступать. Чтобы доказать математическое правило сокращения (6.4.5), заметим, что из следует Так как то отсюда следует, что

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

Теорема 6.4.1. Аксиома 2 в данном выше определении поля для случая конечного множества элементов может быть заменена более

слабым условием (2): операция умножения является коммутативной и ассоциативной и выполняется (6.4.3).

Доказательство. Легко видеть, что (6.4.2), (6.4.4.) и (6.4.5) по-прежнему верны, поскольку их доказательства не опирались на аксиому 2. Пусть а — ненулевой элемент множества; рассмотрим последовательность где и т. д. Так как рассматриваемое множество конечно, то должны существовать два целых числа для которых

Покажем, что является нейтральным элементом по операции умножения. Умножая обе части (6.4.6) на произвольный элемент и сокращая на (который является ненулевым элементом), получаем

Отсюда следует, что является нейтральным элементом по операции умножения. Наконец, обратный по операции умножения элемент для а равен (иди а, если Так как а — произвольный элемент, то любой ненулевой элемент имеет обратный и аксиома 2 справедлива.

Чтобы пояснить на примере использование этой теоремы, выберем простое число и рассмотрим множество целых чисел где Введем операции сложения и умножения по модулю [это означает, что элемент поля задается остатком от деления обычной суммы на Обратный по сложению элемент для элемента это элемент, соответствующий Существование обратного по умножению элемента не совсем очевидно, но следует из теоремы 6.4.1. Поэтому для любого простого неотрицательные целые числа, меньшие чем образуют поле в арифметике по модулю Если не простое, эти элементы не могут образовывать поле в арифметике по модулю поскольку существуют два ненулевых элемента, обычное произведение которых равно отсюда следует, что их произведение по модулю равно нулю. Ниже мы покажем, то существуют поля с элементами, где простое, большее 1 целое число, однако правила сложения и умножения в этих полях не являются сложением и умножением по модулю Как и в теории групп, порядок поля Галуа равен числу элементов в поле; в дальнейшем будем обозначать любое поле с элементами через

Многочлены

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

над как способ представления бесконечной последовательности элементов поля когда лишь конечное число членов последовательности отлично от нуля. Степенью многочлена в этом случае является наибольшее число для которого В частном случае 0-многочлена, для всех условимся считать, что -многочлен имеет степень 0.

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

Назовем два многочлена равными, если каждый из них соответствует одной и той же последовательности коэффициентов. Например, пусть два многочлена над полем по модулю 2 (условимся при записи многочленов опускать слагаемые, коэффициенты при которых равны 0, и записывать В силу нашего определения, эти многочлены не равны. Вместе с тем, если подставить вместо элементы поля 0 и 1, то получим, что Поэтому, если рассматривать как функции переменной, определенной в поле по модулю 2, то они будут равны, хотя при рассмотрении их в виде многочленов они не равны.

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

Степень равна максимальному для которого следовательно, не превосходит наибольшей среди степеней Например, над полем по модулю 2

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

Непосредственно используя (6.4.8), можно показать, что для

Кроме того,

Чтобы убедиться в этом, предположим, имеет степень имеет степень Тогда из (6.4.8) следует, что

имеет степень и первое слагаемое этого многочлена равно

Умножение многочлена над некоторым полем на элемент а этого поля определяется соотношением

Аналогично, отрицательный многочлен для данного многочлена определяется как

Легко убедиться, что множество многочленов над полем образует абелеву группу по сложению. Также можно показать, что для умножения многочленов выполняются и ассоциативный и коммутативный законы и что справедлив дистрибутивный закон

Однако множество многочленов над полем не образует поле из-за отсутствия обратных по умножению элементов. Последнее служит примером того, что теорема 6.4.1 становится неверной без ограничения конечными множествами.

Сформулируем некоторые элементарные свойства многочленов, которые будут полезны в дальнейшем:

Доказательства (6.4.11) и (6.4.12) аналогичны доказательствам (6.4.4) и (6.4.5).

Хотя, вообще говоря, нельзя делить один многочлен на другой и получить многочлен — частное, деление все же может производиться, если при этом допускается остаток.

Теорема 6.4.2. (Алгоритм Евклида деления многочленов.) Пусть многочлены над и пусть имеет степень, не меньшую 1. Тогда существуют единственные многочлены над для которых

где степень меньше, чем степень

Доказательство. Покажем сначала, как найти удовлетворяющие (6.4.13), а затем докажем, что это решение единственное. Пусть имеет степень и пусть имеет степень Если то положим Если и произведем деление на по тому же правилу, по которому производится деление многочленов в обычном поле действительных чисел, а затем положим равным частному от деления, остатку. Это означает, что первое слагаемое равно Это первое слагаемое, умноженное на вычитается из и следующее слагаемое находится путем деления на этого остатка. Когда остаток

будет иметь степень, меньшую, чем степень он выбирается в качестве В качестве примера рассмотрим случай, когда являются многочленами над полем по модулю 2:

В этом примере

Теперь предположим, что существуют два решения (6.4.13), задаваемые Тогда

Теперь заметим, что имеет степень, меньшую, чем степень и поэтому Но отсюда следует, что что завершает доказательство единственности решения.

В дальнейшем при операциях над конечными полями нас часто будет интересовать не столько частное сколько остаток в (6.4.13). По аналогии с арифметическими действиями по модулю простого числа назовем вычетом многочлена по модулю многочлена остаток от деления на будем обозначать его через

Алгоритм Евклида деления многочленов можно использовать для исследования существования делителей и корней многочлена над Многочлен является множителем (или делителем) другого многочлена если существует многочлен над рассматриваемым полем, удовлетворяющий соотношению

Другими словами, делится на если при использовании алгоритма Евклида (6.4.13) получим Многочлен называется приводимым, если существуют два многочлена над рассматриваемым полем, каждый из которых имеет степень, не меньшую 1, удовлетворяющие (6.4.17). Многочлен называется неприводимым, если он не является приводимым.

Часто бывает полезно разлагать многочлен на неприводимые множители. При этом всегда существует некоторая доля неопределенности, поскольку при разложении всегда можно умножить один из сомножителей на произвольный элемент поля, а другой сомножитель — на обратный ему элемент поля, не изменяя при этом произведение.

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

Теорема 6.4.3. (Единственность разложения.) Многочлен над заданным полем единственным образом представляется в виде произведения элемента поля и нормированных неприводимых многочленов над данным полем, каждый из которых имеет степень, не меньшую 1.

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

где многочлены нормированные и неприводимые.

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

где имеет степень, меньшую, чем степень и меньшую, чем Подставляя (6.4.19) в (6.4.18), получаем

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

Элемент а из поля называется корнем многочлена над этим полем, если

Теорема 6.4.4. Элемент а, принадлежащий полю, является корнем ненулевого многочлена над этим полем тогда и только тогда, когда а) является делителем Кроме того, если имеет степень то число элементов поля, являющихся корнями не превосходит

Доказательство. Согласно алгоритму Евклида имеем

Так как степень равна 1, то степень равна 0 и потому является просто элементом поля Подставляя а вместо получаем Поэтому, если то является делителем Обратно, если является делителем то имеем

Теперь представим в виде произведения элемента поля и неприводимых множителей степени не меньше 1. Так как степень равна сумме степеней множителей, то существует не более сомножителей. Это разложение единственно и, следовательно, имеет не более корней в рассматриваемом поле.

Рис. 6.4.1. Поле многочленов в по модулю

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

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

Теперь покажем, что множество многочленов над степени которых не превышают образует поле с операциями обычного сложения многочленов и умножения (неопределенная будет обозначаться в этом случае через для напоминания о том, что рассматривается частное множество многочленов, степени которых не превышают и со специальной операцией умножения, в отличие от обычной операции умножения многочленов). Чтобы доказать, что получается поле, заметим, что аксиомы 1 и 3 непосредственно следуют из свойств сложения многочленов и умножения. Далее отметим, что при имеем

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

может быть любым из элементов первоначального поля, то вновь полученное поле содержит элементов. Назовем это новое поле полем многочленов над по модулю В рассматриваемом случае необходимо, чтобы многочлен был неприводимым, так как в противном случае для некоторых ненулевых следовательно, что противоречит (6.4.3).

Например, пусть является многочленом над Тогда элементами поля по модулю служат многочлены На рис. 6.4.1 приведены таблицы сложения и умножения. Например, чтобы найти воспользуемся алгоритмом Евклида; получим Отсюда