Ю.И. Журавлёв, Ю.А. Флёров, М.Н. Вялый - Дискретный анализ. Основы высшей алгебры (1127101), страница 27
Текст из файла (страница 27)
множителей вида (x − a)r , r > 1.Чтобы исключить такую возможность, нам потребуется использовать понятие производной многочлена над полем F .Производная константы равна 0 по определению, производнаяxn определяется как nxn−1 (здесь n означает элемент поля коэффициентов F , который равен сумме n единиц поля). Крометого, потребуем линейности производной: для любых α, β ∈ F ,f, g ∈ F [x] это означает выполнение равенства(αf + βg)′ = αf ′ + βg ′ ,где штрихом обозначена производная. По линейности можноопределить производную для любого многочлена, зная производные одночленов и констант.Утверждение 3.46 (формула Лейбница).многочленов f, g выполнено (f g)′ = f ′ g + f g ′ .Для любыхДоказательство. Если один из сомножителей равен 1, то(f · 1)′ = f ′ = f ′ · 1 + f · 1′ (производная константы — нуль).156Глава 3.Конечные поля или поля ГалуаДля мономов xn , xk имеем(xn · xk )′ = (n + k) · xn+k−1 = nxn−1 xk + kxn xk−1 == (xn )′ xk + xn (xk )′ .В остальных случаях формула выполняется в силу линейностипроизводной.Утверждение 3.47.
Пусть f и f ′ взаимно просты. Тогда fне имеет кратных корней.Доказательство. Предположим противное: f = g 2 h. Тогдапо формуле Лейбница f ′ = 2g ′ gh + g 2 h′ . Значит, g являетсяобщим делителем f и f ′ . Пришли к противоречию.Вычислим производную нашего многочлена xq − x:(xq − x)′ = qxq−1 − 1 = −1.В последнем равенстве мы учли, что q = pn = 0 в поле характеристики p. Теперь из утверждения 3.47 получаем, чтоу многочлена xq − x над полем Fm кратных корней нет. Значит, построенное нами поле корней этого многочлена содержитровно q = pn элементов.Первое доказательство теоремы 3.16. Чтобы доказать существование неприводимого многочлена степени n над полемGF (p), рассмотрим поле GF (pn ) из pn элементов. Мультипликативная группа этого поля циклическая по теореме 3.44,значит, есть такой элемент α ∈ GF (pn ), степени которого совпадают со всеми ненулевыми элементами поля.По утверждению 3.31 минимальная функция m(α) — неприводимый многочлен.
Докажем, что ее степень равна n. Обозначим d = deg m(α). Все степени α (т. е. все элементы поля)принадлежат d-мерному подпространству с базисом 1, α, α2 ,α3 , . . . , αd−1 , в котором pd элементов. Значит, d = n.Как обещано в начале этого раздела, докажем теперь существование неприводимого многочлена степени n над полемGF (p), не опираясь на существование поля из pn элементов.Это рассуждение дает независимый способ доказательства существования поля из pn элементов.3.7.Существование поля из pn элементов157Будем доказывать существование нормированного (старший коэффициент 1) неприводимого многочлена.
Для нормированных многочленов выполняется аналог основной теоремыарифметики: каждый нормированный многочлен однозначноразлагается на произведение степеней неприводимых многочленов. Действительно, разложение в евклидовом кольце однозначно с точностью до умножения на делители единицы (обратимые элементы). В случае кольца многочленов над полемобратимые элементы — это константы (многочлены степени 0).Выбор старшего коэффициента устраняет произвол в выборесомножителей.Мы выведем существование неприводимых нормированныхмногочленов степени n над полем GF (p) из рекуррентной формулы для числа dn неприводимых нормированных многочленов степени n.XЛемма 3.48.mdm = pn .m|nДоказательство.
Каждому неприводимому нормированномумногочлену сопоставим формальную переменную fin , где n —степень многочлена, i = 1, . . . , dn . Поскольку всякий нормированный многочлен однозначно раскладывается в произведениестепеней неприводимых нормированных, то произвольномунормированному многочлену степени n однозначно сопоставлен мономrXnr sr = n.fis11n1 . . . fisrrnr , причемj=1Поэтому все нормированные многочлены перечисляются формальным бесконечным произведением∞ XYXk(3.9)fin=fis11n1 . . . fisrrnr .i,nk=0В последнем выражении мы раскрыли скобки и переписалибесконечное произведение в виде формального ряда.
Равенство (3.9) — это другой способ сказать, что каждый нормированный многочлен однозначно разлагается в произведениенеприводимых нормированных.158Глава 3.Конечные поля или поля ГалуаТеперь сделаем замену переменных fin = tn , которая делает все многочлены одной степени «одинаковыми». Приведениеподобных в правой части равенства (3.9) даст ряд от переменной t. Коэффициент при tn в этом ряде равен числу нормированных многочленов степени n, которое равно pn . Действительно, нормированный многочлен степени n однозначнозадается своими коэффициентами a0 , . . . , an−1 (так как старший коэффициент равен 1).Что произойдет с левой частью равенства (3.9) после замены переменных? Все неприводимые многочлены степени n дадут одинаковый множитель (сумму бесконечной геометрической прогрессии со знаменателем tn ).
Поэтому равенство (3.9)превращается в∞∞dn XYXtnk=p n tn .(3.10)nn=0k=0Применим формулу для суммы бесконечной геометрической прогрессии к левой и правой частям равенства (3.10).Получим равенствоY11=,(3.11)n )dn(1−t1−ptnкоторое и означает, в сущности, искомое рекуррентное соотношение. Чтобы это увидеть, прологарифмируем его, потомпродифференцируем по t, после чего снова воспользуемся суммой геометрической прогрессии. Более подробно:Xdn ln(1 − tn ) = ln(1 − pt),npntn−1=,n1−t1 − ptnXXdn ntn−1 tnk =ps+1 ts ,Xdnsn,kXn,kndn tn(k+1)=Xp s ts .(3.12)sРавенство коэффициентов при одинаковых степенях t в левойи правой части (3.12) и есть утверждение леммы.3.8.159Единственность поля из pn элементовЗамечание 3.49.
Единственное, что нужно от поля коэффициентов в этом доказательстве — это число элементов. Такчто утверждение леммы справедливо и при p, равном степенипростого.Второе доказательство теоремы 3.16. Заметим, что излеммы 3.48 следует неравенство ndn 6 pn . Теперь осталосьсделать простую оценку:ndn = pn −Xk|n,k<nkdk > pn −n−1Xk=0pk = pn −pn − 1> 0.p−1Мы доказали, что dn > 0. Но это означает, что существуетхотя бы один неприводимый многочлен степени n.Замечание 3.50.
Из леммы 3.48 вытекает, что при n → ∞ величина dn эквивалентна pn /n. Таким образом, примерно, 1/nчасть всех многочленов степени n над полем из p элементовнеприводима.3.8. Единственность поля изpn элементовВ этом разделе мы докажем вторую часть теоремы 3.15:любые два поля с одинаковым числом элементов изоморфны. Доказательство будет использовать теорему 3.38, утверждающую, что все неприводимые многочлены степени n надnполем GF (p) являются делителями многочлена xp − x и следствие 3.36, которое утверждает по сути, что над полем из pnnэлементов многочлен xp − x разлагается на линейные множители.Из первого доказательства теоремы 3.16, приведенного впредыдущем разделе, можно понять, что любое конечное полеявляется кольцом вычетов кольца многочленов GF (p)[x] помодулю некоторого неприводимого многочлена. Сформулируем это утверждение явно.Теорема 3.51.
Пусть m — минимальная функция элемента α ∈ GF (pn ) и d — ее степень. Тогда поле GF (p)[x]/(m)изоморфно подполю GF (pd ), порожденному степенями α.160Глава 3.Конечные поля или поля ГалуаДоказательство. Степени α принадлежат d-мерному пространству с базисом 1, α, α2 , . . .
, αd−1 , которое является подполем поля GF (pn ), поскольку замкнуто относительно сложенияи умножения и содержит 0 и 1.Искомый изоморфизм ϕ отображает вычет {xk } в αk :ϕ : {xk } 7→ αk ,(3.13)на остальных элементах GF (p)[x]/(m) его можно доопределить по линейности: d−1d−1XXkϕ:ak {x } 7→ak αk .(3.14)k=0k=0Из (3.14) ясно, что отображение ϕ взаимно однозначно и является гомоморфизмом аддитивных групп рассматриваемыхполей. Осталось проверить, что ϕ({f }{g}) = ϕ({f })ϕ({g}).Разделим f g на m с остатком: f g = qm + r. Тогдаϕ({f })ϕ({g}) = f (α)g(α) = q(α)m(α) + r(α) = r(α) = ϕ({r}),а в GF (p)[x]/(m) мы имеем равенство {f }{g} = {r}.
Итак,построенное отображение — изоморфизм полей.Рассмотрим теперь два поля с одинаковым количествомэлементов F = GF (p)/(f ) и G = GF (p)/(g), которые по предыдущей теореме можно считать кольцами вычетов по модулю неприводимых многочленов f и g соответственно. Степеньэтих многочленов одинакова, обозначим ее n.nПоскольку в поле G многочлен xp − x разлагается на линейные множители, его множитель f имеет в этом поле кореньα. Из неприводимости f следует, что он является минимальнойфункцией α.
По теореме 3.51 убеждаемся, что наши два поляизоморфны.3.9. Циклические подпространстваВ приложениях к теории кодирования мы будем использовать кольцо многочленов над GF (p) по модулю главного идеала, порожденного некоторым (не обязательно неприводимым)многочленом f . Приведем некоторые свойства этого кольца.3.9.Циклические подпространства161Сначала докажем две теоремы о том, как устроены идеалыв кольце классов вычетов кольца многочленов над GF (p) помодулю главного идеала, порожденного некоторым многочленом f .
Если f неприводим, то кольцо вычетов является полем,этот случай мы уже рассмотрели в предыдущем разделе.Заметим, что, как и раньше, вычеты образуют векторноепространство над GF (p) многочленов степени не выше deg f .Теорема 3.52. Пусть ϕ — неприводимый нормированныймногочлен, который делит f . Тогда совокупность всех вычетов, кратных ϕ, образует идеал в кольце классов вычетовпо модулю f и ϕ — единственный нормированный многочленминимальной степени в этом идеале.Доказательство. Проверим, что это идеал:{v} · {ϕ} + {u} · {ϕ} = {v + u} · {ϕ},{u} · {v} · {ϕ} = {uv} · {ϕ}.Поскольку разность элементов идеала принадлежит идеалу, а старшие коэффициенты нормированных многочленовравны 1, осталось доказать, что в этом идеале нет многочленовстепени меньше deg ϕ. Докажем, что любой ненулевой многочлен степени меньше deg ϕ не сравним по модулю f ни с какимкратным ϕ.
Поскольку f = wϕ, то многочлен, сравнимый скратным ϕ по модулю f имеет вид uϕ−vf = (u−vw)ϕ, степеньтакого многочлена не меньше, чем степень ϕ.Теорема 3.53. Рассмотрим идеал (ϕ), порожденный ϕ — неприводимым нормированным делителем f . Пусть степень fравна n, а степень ϕ равна k. Тогда идеал (ϕ) — векторноепространство размерности n − k.Доказательство. Утверждение теоремы будет следовать изтого, что любой элемент идеала (ϕ) можно представить в виде{(a0 + a1 x + · · · + an−k−1 xn−k−1 )ϕ},(3.15)где a0 , . . . , an−k−1 — произвольные элементы GF (p).Степень многочлена (a0 + a1 x + · · · + an−k−1 xn−k−1 )ϕ небольше n − 1, поэтому все вычеты в (3.15) различны. Пусть{u} = {v}{ϕ}, а vϕ делится на f с остатком r. Тогдаvϕ = uf + r = uwϕ + r,162Глава 3.Конечные поля или поля Галуат. е.
r = (v−uw)ϕ. Поэтому {u} = {r} и мы доказали, что (3.15)описывает все элементы идеала (ϕ).Теперь изучим кольцо вычетов по модулю многочленаxn − 1.Введем понятие циклического подпространства. Пусть вn-мерном векторном пространстве над полем F фиксированнекоторый базис. Тогда это пространство можно отождествитьс координатным пространством F n , точки которого — упорядоченные наборы (a0 , . . . , an−1 ) элементов F длины n. Подпространство координатного пространства F n называется циклическим, если вместе с набором (a0 , . . . , an−1 ) оно содержитциклический сдвиг этого набора, т.
е. (an−1 , a0 , . . . , an−2 ).В кольце классов вычетов по модулю многочлена xn − 1,рассматриваемом как векторное пространство над полемGF (p), есть базис {1}, {x}, . . . , {xn−1 }. Циклический сдвигкоординат в этом базисе равносилен умножению на x. Действительно,{a0 +a1 x+· · ·+an−1 xn−1 }·{x} = {a0 x+a1 x2 +· · ·+an−1 xn } == {an−1 + a0 x + a1 x2 + · · · + an−2 xn−1 }.Теорема 3.54. В кольце классов вычетов по модулю многочлена xn − 1 подпространство является циклическим тогдаи только тогда, когда оно идеал.Доказательство. Если подпространство — идеал, то оно замкнуто относительно умножения на {x}, а умножение на {x}и есть циклический сдвиг.В другую сторону, пусть элемент v принадлежит циклическому подпространству I.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
