Конечные поля (часть 2) (1127161), страница 2
Текст из файла (страница 2)
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов16 / 86Количество неприводимых нормированных многочленов...Доказательство (продолжение)По формуле суммы бесконечной геометрической прогрессии:1Yn(1 −tn )dn=1.1 − ptПрологарифмируем («−» в обеих частях равенствасокращаются, n 7→ m):Xdm ln(1 − tm ) = ln(1 − pt) .mПродифференцируем по t («−» в обеих частях равенствасокращаются):Xmtm−1pdm=.m1−t1−ptmПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов17 / 86Количество неприводимых нормированных многочленов...Доказательство (Xndnntn−1p=)1 − tn1 − ptСнова воспользуемся формулой суммой геометрическойпрогрессии:XXdm mtm−1 tmk =pn+1 tn .nm,kУмножаем на t обе части равенства:XXpn tn .mdm tm(k+1) =nm,kРавенство коэффициентов при одинаковых! степенях t и естьPутверждение леммыm · dm = pn .m|nПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов18 / 86Следствия из леммы1. Существование неприводимых многочленовСправедливо неравенство ndn 6 pn : простая оценкаn−1XXpn − 1> 0.ndn = pn −kdk > pn −pk = pn −p−1k|n, k<nk=0доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый (и нормированный) многочлен степени npn(более точная оценка — 2n6 dn ).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов18 / 86Следствия из леммы1. Существование неприводимых многочленовСправедливо неравенство ndn 6 pn : простая оценкаn−1XXpn − 1> 0.ndn = pn −kdk > pn −pk = pn −p−1k|n, k<nk=0доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый (и нормированный) многочлен степени npn(более точная оценка — 2n6 dn ).2. Среднее число неприводимых нормированных многочленовПри n → ∞ имеем dn ∼ pn /n, т.е.
неприводимыенормированные многочлены составляют приблизительно1/n-ю часть всех многочленов степени n над полем Fp .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов19 / 86Ещё одна формула для dnФункция Мёбиуса µ(n) определена для всех n ∈ N:µ(n) = 1, если примарное разложение n состоит из чётногочисла различных сомножителей;µ(n) = −1, если примарное разложение n состоит изнечётного числа различных сомножителей;µ(n) = 0, иначе (примарное разложение не свободно отквадратов).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов19 / 86Ещё одна формула для dnФункция Мёбиуса µ(n) определена для всех n ∈ N:µ(n) = 1, если примарное разложение n состоит из чётногочисла различных сомножителей;µ(n) = −1, если примарное разложение n состоит изнечётного числа различных сомножителей;µ(n) = 0, иначе (примарное разложение не свободно отквадратов).Например:µ(1) = 1 (по определению),µ(6) = 1,µ(2) = −1,µ(7) = −1,µ(3) = −1,µ(8) = 0,µ(4) = 0,µ(9) = 0,µ(5) = −1,µ(10) = 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовЕщё одна формула для dn ...Основное свойство функции Мёбиуса:(X1, n = 1,µ(d) =0, n > 1.d|n20 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовЕщё одна формула для dn ...Основное свойство функции Мёбиуса:(X1, n = 1,µ(d) =0, n > 1.d|nТеорема (о числе dn неприводимых нормированныхмногочленах степени n над Fp )n1 Xdn =µ(d) p d .nd|nНапример:p = 2, d4 =14p = 2, d5 =1516p = 3, d6 =µ(1)24 + µ(2)22 + µ(4)2 = = 41 24 − 22 + 0 = 3;µ(1)25 + µ(5)2 = 15 [32 − 2] = 6;µ(1)36 + µ(2)33 + µ(3)32 + µ(6)3 = 116.20 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов21 / 86Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальный многочлен элемента α ∈ Fnp и d — еёстепень.Тогда поле Fp [x]/(m) изоморфно подполю Fdp , порожденномустепенями α.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов21 / 86Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальный многочлен элемента α ∈ Fnp и d — еёстепень.Тогда поле Fp [x]/(m) изоморфно подполю Fdp , порожденномустепенями α.ДоказательствоСтепени α принадлежат d-мерному пространству с базисом1, α, α2 , . . .
, αd−1 , которое является подполем поля Fnp ,поскольку замкнуто относительно сложения и умножения исодержит 0 и 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями22 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваКольцоFp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = Fp [x]/(f ) по модулю главного идеала (f ) возможноприводимого многочлена f ∈ Fp [x].Если f неприводим, то K(p, f ) — поле и этот случай ужерассмотрен.23 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваКольцо23 / 86Fp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = Fp [x]/(f ) по модулю главного идеала (f ) возможноприводимого многочлена f ∈ Fp [x].Если f неприводим, то K(p, f ) — поле и этот случай ужерассмотрен.В любом случае K(p, f ) — векторное пространство надсовокупность многочленов степени меньшей deg f .Fp т.е.Fp [x] = { 0, 1, .
. . , p − 1, x, x + 1, . . . , f , . . . };(f ) = f = { t · f } , t ∈ Fp [x];Fp [x]/(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.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства24 / 86Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).def2ϕ — единственный в Iϕ нормированный многочленминимальной степени.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства24 / 86Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).def2ϕ — единственный в Iϕ нормированный многочленминимальной степени.Доказательствоu, v, ϕ ∈ Fp [x],k = deg ϕ 6 deg fϕ = a0 + a1 x + .
. . + ak−1 xk−1 + xk ,f = ψϕ.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства25 / 86Нормированный делитель...1. Проверим, что Iϕ — идеал в кольцеFp [x]/(f ).1g ∈ Iϕh ∈ Fp [x]/(f ), h ⊆ g⇔g = uϕh = vg = vuϕ⇒ h ∈ Iϕ .2g, h ∈ Iϕ ⇔g = uϕh = vϕ⇒ g + h = (u + v)ϕ ∈ Iϕ .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваНормированный делитель...2. Покажем, что в Iϕ нет других, кромеϕ = a0 + a1 x + . . .
+ ak−1 xk−1 + xkнормированных многочленов степени, меньшей k = deg ϕ.Пустьg = b0 + b1 x + . . . + xm .Тогда:g ∈ Iϕ ⇔ g = uϕ ⇒ deg g = m > deg ϕ = k.26 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства27 / 86Подыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства27 / 86Подыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.ДоказательствоБез доказательства.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства28 / 86Циклическое пространство: определениеПусть V — n-мерное векторное пространство наднекоторым полем F .Фиксируем некоторый базис V .Тогда V ∼= Fn == { ( a0 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
