Лекции по прикладной алгебре. v1.1 (1127111), страница 7
Текст из файла (страница 7)
Для любогоx ∈ G выполняется xM = e, т.е. порядок x делит M .Но произведение всех выбранных циклических групп имеетпорядок M . Поэтому m = M .74 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp .(везде p — простое, n — натуральное).75 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp .(везде p — простое, n — натуральное).
Это можно сделатьдвумя способами.а) ⇒ б) доказать существование поля из pn элементов,откуда вывести существование неприводимогомногочлена степени n над Fp ;б) ⇒ а) установить существование неприводимогомногочлена f степени n над Fp , откуда ужеследует существование поля из pn какфакторкольца по идеалу (f ).Мы пойдём вторым путём.75 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовСуществование неприводимого многочлена степени n надполем FpБудем доказывать существование нормированногонеприводимого многочлена.
Для таких многочленоввыполняется аналог основной теоремы арифметики: каждыйнормированный многочлен однозначно разлагается напроизведение степеней неприводимых многочленов.76 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовСуществование неприводимого многочлена степени n надполем FpБудем доказывать существование нормированногонеприводимого многочлена. Для таких многочленоввыполняется аналог основной теоремы арифметики: каждыйнормированный многочлен однозначно разлагается напроизведение степеней неприводимых многочленов.Действительно:разложение в евклидовом кольце однозначно (с точностьюдо умножения на обратимые элементы — делители);в случае кольца многочленов над полем обратимыеэлементы — это константы (многочлены степени 0);выбор старшего коэффициента 1 однозначно определяетсомножители.76 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленов77 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленовЛемма (о числе dn )Если dn — число неприводимых нормированных многочленовPиз Fnp , тоm · dm = pn .m|n77 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов77 / 160Подсчёт неприводимых нормированных многочленовЛемма (о числе 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 элементов78 / 160Подсчёт неприводимых нормированных многочленов...ДоказательствоПоэтому все нормированные многочлены перечисляютсяформальным бесконечным произведением!∞Y XXkfi,n=fis11,n1 · .
. . · fisrr,nri,n(∗)k=0(раскрыты скобки и бесконечное произведение записано в видеформального ряда).Сделаем замену переменных fi,n = tn , которая делает всемногочлены одной степени неразличимыми.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов79 / 160Подсчёт неприводимых нормированных многочленов...∞Y Xi,n!kfi,n=Xfis11,n1 · . . . · fisrr,nrk=0Приведение подобных приведёт к тому, что:в правой части (∗) будет ряд от переменной t.Коэффициент при tn в этом ряде равен числунормированных многочленов степени n, т.е. pn :∞Xn=0pn tn .(∗)Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов80 / 160Подсчёт неприводимых нормированных многочленов...∞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 − ptm81 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из 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|n82 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов83 / 160Важные замечанияЗамечание (о существовании неприводимых многочленов)Из данной леммы следует неравенство ndn 6 pn .
Простая оценкаndn = pn −Xk|n, k<nkdk > pn −n−1Xk=0pk = pn −pn − 1> 0.p−1доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов83 / 160Важные замечанияЗамечание (о существовании неприводимых многочленов)Из данной леммы следует неравенство 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 элементов84 / 160Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальная функция элемента α ∈ Fnp и d — еёстепень.
Тогда поле Fp [x]/(m) изоморфно подполю Fdp ,порожденному степенями α.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов84 / 160Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальная функция элемента α ∈ Fnp и d — еёстепень.
Тогда поле Fp [x]/(m) изоморфно подполю Fdp ,порожденному степенями α.ДоказательствоСтепени α принадлежат d-мерному пространству с базисом1, α, α2 , . . . , αd−1 , которое является подполем поля Fnp ,поскольку замкнуто относительно сложения и умножения исодержит 0 и 1.Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды85 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел IIКоды БЧХЧто надо знать86 / 160Прикладная алгебраПоля ГалуаЦиклические подпространстваКольцо87 / 160Fp /(f )В приложениях часто используется кольцо многочленовGF (p) = Fp [x]/(f ) по модулю главного идеала не обязательнонеприводимого многочлена f ∈ Fp [x].Если f неприводим, тоFp /(f ) — поле и этот случай уже рассмотрен.Прикладная алгебраПоля ГалуаЦиклические подпространстваКольцо87 / 160Fp /(f )В приложениях часто используется кольцо многочленовGF (p) = Fp [x]/(f ) по модулю главного идеала не обязательнонеприводимого многочлена f ∈ Fp [x].Если f неприводим, тоFp /(f ) — поле и этот случай уже рассмотрен.В любом случае GF (p) — векторное пространство надстепени 6 deg f .Fp [x]Fp многочленов= { 0, 1, .
. . , p − 1, x, x + 1, . . . , f , . . . };(f ) = f = { t · f }, t ∈ Fp [x];Fp /(f )= { f , g, h, . . . }, deg f, deg g, . . . 6 deg f − 1;g = { t · f + g };h = { t · f + h };...g + f = g,g · f = f.Прикладная алгебраПоля ГалуаЦиклические подпространства88 / 160Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).ϕ — единственный нормированный многочленминимальной степени в Iϕ .def2Прикладная алгебраПоля ГалуаЦиклические подпространства88 / 160Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
