Лекции по прикладной алгебре. v2.0 (1127112), страница 7
Текст из файла (страница 7)
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать78 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа расширения поляПример (полеF42 )Поле F42 можно строить с помощью любого из трехнеприводимых многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Удобнее всего это сделать, если взять многочленf (x) = x4 + x + 1 (почему?).79 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа расширения поляПример (полеF42 )Поле F42 можно строить с помощью любого из трехнеприводимых многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Удобнее всего это сделать, если взять многочленf (x) = x4 + x + 1 (почему?).Будем задавать элементы F42 наборами коэффициентовмногочлена-остатка при делении на f , записывая их в порядкевозрастания степеней.Порождающим является элемент α = x, который записываетсякак (0, 1, 0, 0).Вычислим степени α, сведя результаты в таблицу.79 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа поляα4 = α + 180 / 432F42 ∼= F2 [x]/(x4 + x + 1)степень αα=α2 =α3 =1 + α = α4 =α + α2 = α5 =α2 + α3 = α6 =3α + α + 1 = α3 + α4 = α7 =1 + α2 = α + 1 + α2 + α = α8 =α + α3 = α9 =22α + 1 + α = α + α4 = α10 =α + α2 + α3 = α11 =231 + α + α + α = α2 + α3 + α4 = α12 =1 + α2 + α3 = α + α2 + α3 + α4 = α13 =1 + α3 = α + α3 + α4 = α14 =1 = α + α4 = α15 =1(0,(0,(0,(1,(0,(0,(1,(1,(0,(1,(0,(1,(1,(1,(1,x1,0,0,1,1,01,0,1,1,1,1,0,0,0,x20,1,0,0,1,1,01,0,1,1,1,1,0,0,x30)0)1)0)0)1)1)0)1)0)1)1)1)1)0)Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов81 / 432Имея такую таблицу, очень просто производить умножение(x3 + x + 1) · (x2 + x + 1) = ?Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов81 / 432Имея такую таблицу, очень просто производить умножение(x3 + x + 1) · (x2 + x + 1) = ?1перемножить, учитывая x4 = x + 1 — можно, но сложно...Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов81 / 432Имея такую таблицу, очень просто производить умножение(x3 + x + 1) · (x2 + x + 1) = ?1перемножить, учитывая x4 = x + 1 — можно, но сложно...2с помощью таблицы:представляем многочлены в векторной форме и по ней — ввиде степеней α = x:x3 + x + 1 ↔ (1, 1, 0, 1) ↔ α7 ,x2 + x + 1 ↔ (1, 1, 1, 0) ↔ α10перемножаем, получаем: α7 α10 = α17 = α2 = x2 .Получаем: (x3 + x + 1) · (x2 + x + 1) = x2 .Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m — максимальный порядок элемента в конечнойабелевой группе G.Тогда порядок любого элемента x ∈ G = h G, ◦, e i делит m.82 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m — максимальный порядок элемента в конечнойабелевой группе G.Тогда порядок любого элемента x ∈ G = h G, ◦, e i делит m.ДоказательствоГруппа G однозначно разлагается в прямую сумму циклическихгрупп, порядки которых являются степенями простых чисел.Для каждого простого делителя pi порядка группы найдемциклическую группу максимального порядка pki .Обозначим произведение чисел pki через M .
Для любогоx ∈ G выполняется xM = e, т.е. порядок x делит M .Но произведение всех выбранных циклических групп имеетпорядок M . Поэтому m = M .82 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp .(везде p — простое, n — натуральное).83 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp .(везде p — простое, n — натуральное). Это можно сделатьдвумя способами.а) ⇒ б) доказать существование поля из pn элементов,откуда вывести существование неприводимогомногочлена степени n над Fp ;б) ⇒ а) установить существование неприводимогомногочлена f степени n над Fp , откуда ужеследует существование поля из pn какфакторкольца по идеалу (f ).Мы пойдём вторым путём.83 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовСуществование неприводимого многочлена степени n надполем FpБудем доказывать существование нормированногонеприводимого многочлена.
Для таких многочленоввыполняется аналог основной теоремы арифметики: каждыйнормированный многочлен однозначно разлагается напроизведение степеней неприводимых многочленов.84 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовСуществование неприводимого многочлена степени n надполем FpБудем доказывать существование нормированногонеприводимого многочлена. Для таких многочленоввыполняется аналог основной теоремы арифметики: каждыйнормированный многочлен однозначно разлагается напроизведение степеней неприводимых многочленов.Действительно:разложение в евклидовом кольце однозначно (с точностьюдо умножения на обратимые элементы — делители);в случае кольца многочленов над полем обратимыеэлементы — это константы (многочлены степени 0);выбор старшего коэффициента 1 однозначно определяетсомножители.84 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленов85 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленовЛемма (о числе dn )Если dn — число неприводимых нормированных многочленовPиз Fnp , тоm · dm = pn .m|n85 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов85 / 432Подсчёт неприводимых нормированных многочленовЛемма (о числе dn )Если dn — число неприводимых нормированных многочленовPиз Fnp , тоm · dm = pn .m|nДоказательствоЗанумеруем i = 1, .
. . , dn все неприводимые нормированныемногочлены степени n и сопоставим им формальнуюпеременную fi,n ⇒ произвольному такому многочленуоднозначно сопоставлен моном (многочлен степени nj берётсяв степени sj ):fis11,n1 · . . . · fisrr,nr , причемrPj=1nj sj = n.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов86 / 432Подсчёт неприводимых нормированных многочленов...ДоказательствоПоэтому все нормированные многочлены перечисляютсяформальным бесконечным произведением!∞Y XXkfi,n=fis11,n1 · . .
. · fisrr,nri,n(∗)k=0(раскрыты скобки и бесконечное произведение записано в видеформального ряда).Сделаем замену переменных fi,n = tn , которая делает всемногочлены одной степени неразличимыми.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов87 / 432Подсчёт неприводимых нормированных многочленов...∞Y Xi,n!kfi,n=Xfis11,n1 · . . . · fisrr,nrk=0Приведение подобных приведёт к тому, что:в правой части (∗) будет ряд от переменной t.Коэффициент при tn в этом ряде равен числунормированных многочленов степени n, т.е. pn :∞Xn=0pn tn .(∗)Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов88 / 432Подсчёт неприводимых нормированных многочленов...∞Y Xi,n!kfi,n=∞Xpn tn(∗)n=0k=0в левой части все неприводимые многочлены степени nдадут одинаковый множитель (сумму бесконечнойгеометрической прогрессии со знаменателем tn ) и(∗) превращается в∞Y Xnk=0!dnnkt=∞Xn=0pn tn .Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленов...По формуле суммы бесконечной геометрической прогрессии:1Yn(1 −tn )dn=1.1 − ptПрологарифмируем («−» в обеих частях равенствасокращаются, n 7→ m):Xdm ln(1 − tm ) = ln(1 − pt) .mПродифференцируем по t («−» в обеих частях равенствасокращаются):Xmtm−1pdm=.m1−t1 − ptm89 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленов...(ntn−1n dn 1−tnP=p1−pt)Снова воспользуемся формулой суммой геометрическойпрогрессии:XXdm mtm−1 tmk =pn+1 tn .nm,kУмножаем на t обе части равенства:XXmdm tm(k+1) =pn tn .nm,kРавенство коэффициентовстепенях t и естьP при одинаковыхnутверждение леммы (m · dm = p ).m|n90 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов91 / 432Важные замечанияЗамечание (о существовании неприводимых многочленов)Из данной леммы следует неравенство ndn 6 pn .
Простая оценкаndn = pn −Xk|n, k<nkdk > pn −n−1Xk=0pk = pn −pn − 1> 0.p−1доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов91 / 432Важные замечанияЗамечание (о существовании неприводимых многочленов)Из данной леммы следует неравенство ndn 6 pn . Простая оценкаndn = pn −Xk|n, k<nkdk > pn −n−1Xk=0pk = pn −pn − 1> 0.p−1доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.Замечание (о среднем числе неприводимых многочленов)Из данной леммы вытекает, что при n → ∞ имеем dn ∼ pn /n.Таким образом, примерно, 1/n-я часть всех многочленов степениn над полем из p элементов неприводима.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов92 / 432Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальный многочлен элемента α ∈ Fnp и d — еёстепень.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
