PA_full (1127144), страница 8
Текст из файла (страница 8)
Это можно сделатьдвумя способами.а) ) б) доказать существование поля из pn элементов,откуда вывести существование неприводимогомногочлена степени n над p ;б) ) а) установить существование неприводимогомногочлена f степени n над p , откуда ужеследует существование поля из pn какфакторкольца по идеалу (f ).Мы пойдём вторым путём.83 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовСуществование неприводимого многочлена степени n надполем pБудем доказывать существование нормированногонеприводимого многочлена.
Для таких многочленоввыполняется аналог основной теоремы арифметики: каждыйнормированный многочлен однозначно разлагается напроизведение степеней неприводимых многочленов.84 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовСуществование неприводимого многочлена степени n надполем pБудем доказывать существование нормированногонеприводимого многочлена. Для таких многочленоввыполняется аналог основной теоремы арифметики: каждыйнормированный многочлен однозначно разлагается напроизведение степеней неприводимых многочленов.Действительно:разложение в евклидовом кольце однозначно (с точностьюдо умножения на обратимые элементы � делители);в случае кольца многочленов над полем обратимыеэлементы � это константы (многочлены степени 0);выбор старшего коэффициента 1 однозначно определяетсомножители.84 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленов85 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленовЛемма (о числе dn )Если dn � число неприводимых нормированных многочленовPиз np , тоm · d m = pn .m|n85 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов85 / 432Подсчёт неприводимых нормированных многочленовЛемма (о числе dn )Если dn � число неприводимых нормированных многочленовPиз np , тоm · d m = pn .m|nДоказательствоЗанумеруем i = 1, .
. . , dn все неприводимые нормированныемногочлены степени n и сопоставим им формальнуюпеременную fi,n ) произвольному такому многочленуоднозначно сопоставлен моном (многочлен степени nj берётсяв степени sj ):fis11,n1 · . . . · fisrr,nr , причемrPj=1nj sj = n.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов86 / 432Подсчёт неприводимых нормированных многочленов...ДоказательствоПоэтому все нормированные многочлены перечисляютсяформальным бесконечным произведением!1Y XXkfi,n=fis11,n1 · . . . · fisrr,nri,n(⇤)k=0(раскрыты скобки и бесконечное произведение записано в видеформального ряда).Сделаем замену переменных fi,n = tn , которая делает всемногочлены одной степени неразличимыми.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов87 / 432Подсчёт неприводимых нормированных многочленов...1Y Xi,nk=0kfi,n!=Xfis11,n1 · .
. . · fisrr,nrПриведение подобных приведёт к тому, что:в правой части (⇤) будет ряд от переменной t.Коэффициент при tn в этом ряде равен числунормированных многочленов степени n, т.е. pn :1Xn=0p n tn .(⇤)Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов88 / 432Подсчёт неприводимых нормированных многочленов...1Y Xi,nk=0kfi,n!=1Xpn tn(⇤)n=0в левой части все неприводимые многочлены степени nдадут одинаковый множитель (сумму бесконечнойгеометрической прогрессии со знаменателем tn ) и(⇤) превращается в1Y Xnk=0tnk! dn=1Xn=0pn tn .Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов89 / 432Подсчёт неприводимых нормированных многочленов...По формуле суммы бесконечной геометрической прогрессии:Yn1(1tn ) d n=11pt.Прологарифмируем (� � в обеих частях равенствасокращаются, n 7! m):Xdm ln(1 tm ) = ln(1 pt) .mПродифференцируем по t (� � в обеих частях равенствасокращаются):Xmtm 1pdm=.m1 t1 ptmПрикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПодсчёт неприводимых нормированных многочленов...(Pntn 1n dn 1 tn=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 = pnXk|n, k<nkdk > pnnX1k=0pk = pnpnp1> 0.1доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов91 / 432Важные замечанияЗамечание (о существовании неприводимых многочленов)Из данной леммы следует неравенство ndn 6 pn .
Простая оценкаndn = pnXk|n, k<nkdk > pnnX1k=0pk = pnpnp1> 0.1доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.Замечание (о среднем числе неприводимых многочленов)Из данной леммы вытекает, что при n ! 1 имеем dn ⇠ pn /n.Таким образом, примерно, 1/n-я часть всех многочленов степениn над полем из p элементов неприводима.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов92 / 432Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m � минимальный многочлен элемента ↵ 2степень.
Тогда поле p [x]/(m) изоморфно подполюпорожденному степенями ↵.n иpd,pd � еёПрикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов92 / 432Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m � минимальный многочлен элемента ↵ 2степень. Тогда поле p [x]/(m) изоморфно подполюпорожденному степенями ↵.n иpd,pd � еёДоказательствоСтепени ↵ принадлежат d-мерному пространству с базисом1, ↵, ↵2 , . .
. , ↵d 1 , которое является подполем поля np ,поскольку замкнуто относительно сложения и умножения исодержит 0 и 1.Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды93 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств94 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать95 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваКольцоp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = p [x]/(f ) по модулю главного идеала не обязательнонеприводимого многочлена f 2 p [x].Если f неприводим, то K(p, f ) � поле и этот случай уже рассмотрен.96 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваКольцо96 / 432p [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = p [x]/(f ) по модулю главного идеала не обязательнонеприводимого многочлена f 2 p [x].Если f неприводим, то K(p, f ) � поле и этот случай уже рассмотрен.В любом случае K(p, f ) � векторное пространство надсовокупность многочленов степени 6 deg f .p [x]= { 0, 1, .
. . , p(f ) = f = { t · f }, t 2p /(f )p,1, x, x + 1, . . . , f , . . . };p [x];= { f , g, h, . . . }, deg f, deg g, . . . 6 deg fg = { t · f + g };h = { t · f + h };...g + f = g,g · f = f.1;Прикладная алгебраПоля ГалуаЦиклические подпространства97 / 432Нормированный делитель порождающего элемента идеалаТеоремаПусть ' � неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ', образует идеал вкольце классов вычетов по модулю f :def2I' = { t · ' } C p [x]/(f ).' � единственный нормированный многочленминимальной степени в I' .Прикладная алгебраПоля ГалуаЦиклические подпространства97 / 432Нормированный делитель порождающего элемента идеалаТеоремаПусть ' � неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ', образует идеал вкольце классов вычетов по модулю f :def2I' = { t · ' } C p [x]/(f ).' � единственный нормированный многочленминимальной степени в I' .Доказательство(f ) = tf,t, s, ' 2p [x],' = a0 + a1 x + .
. . + ak1xdeg f > deg ' = kk 1+ 1 · xk ,f ='.Прикладная алгебраПоля ГалуаЦиклические подпространства98 / 432Нормированный делитель...Проверим, что I' � идеал.1⇢g 2 I'h✓g,⇢g = u'h = vg = vu'2g, h 2 I' ,⇢g = u'h = v'g + h = (u + v)' 2 I' .) h 2 I' .Прикладная алгебраПоля ГалуаЦиклические подпространства99 / 432Нормированный делитель...Покажем, что в I' нет других, кроме' = a0 + a1 x + .
. . + ak1xk 1+ xkнормированных многочленов степени, меньшей k = deg '.Пусть! = b0 + b1 x + . . . + x m .Тогда:! 2 I' , ! = t' ) deg ! = m > deg '.Прикладная алгебраПоля ГалуаЦиклические подпространстваПодыдеал как векторное пространствоТеоремаПусть ' � неприводимый нормированный делительмногочлена f 2 p [x] отличный от f , deg f = n, deg ' = k.Тогда идеал (') � векторное пространство размерности n k.100 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваПодыдеал как векторное пространствоТеоремаПусть ' � неприводимый нормированный делительмногочлена f 2 p [x] отличный от f , deg f = n, deg ' = k.Тогда идеал (') � векторное пространство размерности n k.ДоказательствоБез доказательства.100 / 432Прикладная алгебраПоля ГалуаЦиклические подпространства101 / 432Циклическое пространство: определениеПусть F � n-мерное векторное пространство наднеоторым полем.Фиксируем некоторый базис F .ТогдаF ⇠= F n = { (a0 , .
. . , an 1 ) | ai 2 F, i = 0, 1, . . . , nкоординатное пространство.1} �ОпределениеПодпространство координатного пространства F n называетсяциклическим, если вместе с набором (a0 , . . . , an 1 ) оносодержит циклический сдвиг этого набора, т.е. набор(an 1 , a0 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
