Лекции по прикладной алгебре. v2.0 (1127112), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Тогда поле Fp [x]/(m) изоморфно подполю Fdp ,порожденному степенями α.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов92 / 432Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальный многочлен элемента α ∈ Fnp и d — еёстепень. Тогда поле Fp [x]/(m) изоморфно подполю Fdp ,порожденному степенями α.ДоказательствоСтепени α принадлежат d-мерному пространству с базисом1, α, α2 , .

. . , αd−1 , которое является подполем поля Fnp ,поскольку замкнуто относительно сложения и умножения исодержит 0 и 1.Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды93 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств94 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваРаздел IIIОсновные понятия теории ч.у.

множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать95 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваКольцоFp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = Fp [x]/(f ) по модулю главного идеала не обязательнонеприводимого многочлена f ∈ Fp [x].Если f неприводим, то K(p, f ) — поле и этот случай уже рассмотрен.96 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваКольцо96 / 432Fp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = Fp [x]/(f ) по модулю главного идеала не обязательнонеприводимого многочлена f ∈ Fp [x].Если f неприводим, то K(p, f ) — поле и этот случай уже рассмотрен.В любом случае K(p, f ) — векторное пространство надсовокупность многочленов степени 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.Прикладная алгебраПоля ГалуаЦиклические подпространства97 / 432Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).ϕ — единственный нормированный многочленминимальной степени в Iϕ .def2Прикладная алгебраПоля ГалуаЦиклические подпространства97 / 432Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f .

Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).ϕ — единственный нормированный многочленминимальной степени в Iϕ .def2Доказательство(f ) = tf,t, s, ϕ ∈ Fp [x],ϕ = a0 + a1 x + . . . + ak−1 xdeg f > deg ϕ = kk−1+ 1 · xk ,f = ψϕ.Прикладная алгебраПоля ГалуаЦиклические подпространства98 / 432Нормированный делитель...Проверим, что Iϕ — идеал.1g ∈ Iϕh⊆g⇔g = uϕh = vg = vuϕ2g, h ∈ Iϕ ⇔g = uϕh = vϕg + h = (u + v)ϕ ∈ Iϕ .⇒ h ∈ Iϕ .Прикладная алгебраПоля ГалуаЦиклические подпространстваНормированный делитель...Покажем, что в Iϕ нет других, кромеϕ = a0 + a1 x + .

. . + ak−1 xk−1 + xkнормированных многочленов степени, меньшей k = deg ϕ.Пустьω = b0 + b1 x + . . . + xm .Тогда:ω ∈ Iϕ ⇔ ω = tϕ ⇒ deg ω = m > deg ϕ.99 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваПодыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.100 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваПодыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.ДоказательствоБез доказательства.100 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваЦиклическое пространство: определениеПусть F — n-мерное векторное пространство наднеоторым полем.Фиксируем некоторый базис F .ТогдаF ∼= F n = { (a0 , .

. . , an−1 ) | ai ∈ F, i = 0, 1, . . . , n − 1 } —координатное пространство.ОпределениеПодпространство координатного пространства F n называетсяциклическим, если вместе с набором (a0 , . . . , an−1 ) оносодержит циклический сдвиг этого набора, т.е. набор(an−1 , a0 , . . . , an−2 ).101 / 432Прикладная алгебраПоля ГалуаЦиклические подпространства102 / 432Кольцо классов вычетов по модулю многочлена xn − 1В кольце Fp /(xn − 1), рассматриваемом как векторноепространство над полем Fp в базисе { 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 ).Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вFp /(xn − 1) — циклическое пространствоТеоремаПусть I ⊆ Fp /(xn − 1).Тогда I — циклическое пространство ⇔ I C Fp /(xn − 1).103 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вFp /(xn − 1) — циклическое пространствоТеоремаПусть I ⊆ Fp /(xn − 1).Тогда I — циклическое пространство ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг.103 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваИдеал вFp /(xn − 1) — циклическое пространствоТеоремаПусть I ⊆ Fp /(xn − 1).Тогда I — циклическое пространство ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг.Пусть I — циклическое подпространство I и g ∈ I.Тогда g · x, g · x2 , .

. . — циклические сдвиги, т.е. такжепринадлежат I.Значит, g · f ∈ I для любого многочлена f ,поэтому I — идеал.103 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваПримитивные корниПоказано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором поле Fqхарактеристики p.Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.104 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваПримитивные корниПоказано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором поле Fqхарактеристики p.Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.

Справедливо:В Fq выполняется равенство xkp − 1 = (xk − 1)p , поэтомуинтересен случай, когда n взаимно просто с p: тогда умногочлена xn − 1 кратных корней нет (он взаимно простсо своей производной nxn−1 ).Равенство xn = 1 означает, что порядок элемента xв мультипликативной циклической группе F∗q делит n.Вывод: корни уравнения xn − 1 = 0 образуют группу корнейстепени n из единицы — подгруппу в F∗q .Эта подгруппа также циклическая; её порождающие элементыназываются примитивными корнями степени n.104 / 432Прикладная алгебраПоля ГалуаЦиклические подпространстваКоличество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒105 / 432Прикладная алгебраПоля ГалуаЦиклические подпространства105 / 432Количество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒ поле Fq содержит группукорней из единицы степени n iff n | q − 1.Разложение xn − 1 над12Fp :в поле Fq на линейные множители (корни степени n изединицы);в поле Fp на неприводимые множители.Какие корни из единицы будут неприводимыми делителямиxn − 1 в Fp ?2Если β — корень f (x), то β p , β p и т.д.

Характеристики

Список файлов лекций