Лекции по прикладной алгебре. v1.0 (1127110), страница 6
Текст из файла (страница 6)
Òîãäà ïîðÿäîê ëþáîãî ýëåìåíòà G äåëèòm.Òåïåðü ìîæíî âåðíóòüñÿ ê âîïðîñó î ñóùåñòâîâàíèèà)á)êîíå÷íîãî ïîëÿ Fq ðàçìåðà q , ïîêàçàâ, ÷òî âñåãäàq = pn ;íåïðèâîäèìîãî ìíîãî÷ëåíà ñòåïåíè n íàä Fp .(âåçäå p ïðîñòîå, n íàòóðàëüíîå).Ïðèêëàäíàÿ àëãåáðà66 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÏóòè äîêàçàòåëüñòâàÝòî ìîæíî ñäåëàòü äâóìÿ ñïîñîáàìè.à)⇒á)á)⇒à)äîêàçàòü ñóùåñòâîâàíèå ïîëÿ èç pn ýëåìåíòîâ, îòêóäàâûâåñòè ñóùåñòâîâàíèå íåïðèâîäèìîãî ìíîãî÷ëåíàñòåïåíè n íàä Fp ;óñòàíîâèòü ñóùåñòâîâàíèå íåïðèâîäèìîãî ìíîãî÷ëåíàf ñòåïåíè n íàä Fp , îòêóäà óæå ñëåäóåò ñóùåñòâîâàíèåïîëÿ èç pn êàê ôàêòîðêîëüöà ïî èäåàëó (f ).Ìû ïîéä¼ì âòîðûì ïóò¼ì.Ïðèêëàäíàÿ àëãåáðà67 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÑóùåñòâîâàíèå íåïðèâîäèìîãî ìíîãî÷ëåíà ñòåïåíè n íàäïîëåì FpÄëÿ íîðìèðîâàííûõ ìíîãî÷ëåíîâ âûïîëíÿåòñÿ àíàëîã îñíîâíîéòåîðåìû àðèôìåòèêè: êàæäûé íîðìèðîâàííûé ìíîãî÷ëåíîäíîçíà÷íî ðàçëàãàåòñÿ íà ïðîèçâåäåíèå ñòåïåíåéíåïðèâîäèìûõ ìíîãî÷ëåíîâ.Ïðèêëàäíàÿ àëãåáðà67 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÑóùåñòâîâàíèå íåïðèâîäèìîãî ìíîãî÷ëåíà ñòåïåíè n íàäïîëåì FpÄëÿ íîðìèðîâàííûõ ìíîãî÷ëåíîâ âûïîëíÿåòñÿ àíàëîã îñíîâíîéòåîðåìû àðèôìåòèêè: êàæäûé íîðìèðîâàííûé ìíîãî÷ëåíîäíîçíà÷íî ðàçëàãàåòñÿ íà ïðîèçâåäåíèå ñòåïåíåéíåïðèâîäèìûõ ìíîãî÷ëåíîâ.Äåéñòâèòåëüíî:ðàçëîæåíèå â åâêëèäîâîì êîëüöå îäíîçíà÷íî (ñ òî÷íîñòüþäî óìíîæåíèÿ íà îáðàòèìûå ýëåìåíòû äåëèòåëè);â ñëó÷àå êîëüöà ìíîãî÷ëåíîâ íàä ïîëåì îáðàòèìûåýëåìåíòû ýòî êîíñòàíòû (ìíîãî÷ëåíû ñòåïåíè 0);âûáîð ñòàðøåãî êîýôôèöèåíòà óñòðàíÿåò ïðîèçâîë ââûáîðå ñîìíîæèòåëåé.Ïðèêëàäíàÿ àëãåáðà68 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâ×èñëî íåïðèâîäèìûõ íîðìèðîâàííûõ ìíîãî÷ëåíîâ dnËåììà (î ÷èñëå dn )Ïóñòü dn ÷èñëî íåïðèâîäèìûõ íîðìèðîâàííûõ ìíîãî÷ëåíîâñòåïåíè n íàä ïîëåì Fp .
ÒîãäàXm · dm = pn .m|nÄîêàçàòåëüñòâîÇàíóìåðóåì i = 1, . . . , dn âñå íåïðèâîäèìûå íîðìèðîâàííûåìíîãî÷ëåíû ñòåïåíè n è ñîïîñòàâèì èì ôîðìàëüíóþ ïåðåìåííóþfi,n . Òîãäà ïðîèçâîëüíîìó íîðìèðîâàííîìó ìíîãî÷ëåíó ñòåïåíè nîäíîçíà÷íî ñîïîñòàâëåí ìîíîì ïðîèçâåäåíèÿ ýòèõ ïåðåìåííûõfis11,n1 · . . . · fisrr,nr , ïðè÷åìrXj=1nj , sj = n .Ïðèêëàäíàÿ àëãåáðà69 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâ×èñëî íåïðèâîäèìûõ íîðìèðîâàííûõ ìíîãî÷ëåíîâ dn ...ÄîêàçàòåëüñòâîÏîýòîìó âñå íîðìèðîâàííûå ìíîãî÷ëåíû ïåðå÷èñëÿþòñÿôîðìàëüíûì áåñêîíå÷íûì ïðîèçâåäåíèåì!∞Y XXkfi,n=fis11,n1 · . . .
· fisrr,nri,nk=0(ðàñêðûòû ñêîáêè è áåñêîíå÷íîå ïðîèçâåäåíèå çàïèñàíî â âèäåôîðìàëüíîãî ðÿäà; ýòî ðàâåíñòâî ýòî äðóãîé ñïîñîá ñêàçàòü,÷òî êàæäûé íîðìèðîâàííûé ìíîãî÷ëåí îäíîçíà÷íî ðàçëàãàåòñÿâ ïðîèçâåäåíèå íåïðèâîäèìûõ íîðìèðîâàííûõ).Ñäåëàåì çàìåíó ïåðåìåííûõ fi,n = tn , êîòîðàÿ äåëàåòâñå ìíîãî÷ëåíû îäíîé ñòåïåíè íåðàçëè÷èìûìè. Ïðèâåäåíèåïîäîáíûõ â ïðàâîé ÷àñòè ðàâåíñòâà äàñò ðÿä îò ïåðåìåííîé t.Ïðèêëàäíàÿ àëãåáðà70 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâ×èñëî íåïðèâîäèìûõ íîðìèðîâàííûõ ìíîãî÷ëåíîâ dn ...ÄîêàçàòåëüñòâîÊîýôôèöèåíò ïðè tn â ýòîì ðÿäå ðàâåí ÷èñëó íîðìèðîâàííûõìíîãî÷ëåíîâ ñòåïåíè n, êîòîðîå ðàâíî pn .
Äåéñòâèòåëüíî,íîðìèðîâàííûé ìíîãî÷ëåí ñòåïåíè n îäíîçíà÷íî çàäàåòñÿ ñâîèìèêîýôôèöèåíòàìè a0 , . . . , an−1 (ò.ê. ñòàðøèé êîýôôèöèåíò ðàâåí 1). ëåâîé ÷àñòè ðàâåíñòâà âñå íåïðèâîäèìûå ìíîãî÷ëåíû ñòåïåíè näàäóò îäèíàêîâûé ìíîæèòåëü (ñóììó áåñêîíå÷íîé ãåîìåòðè÷åñêîéïðîãðåññèè ñî çíàìåíàòåëåì tn ). Ðàâåíñòâî ïðåâðàùàåòñÿ â∞Y Xn!dnf nk=∞Xpn tn .n=0k=0Ïî ôîðìóëå äëÿ ñóììû áåñêîíå÷íîé ãåîìåòðè÷åñêîé ïðîãðåññèè1Yn(1 −tn )dn=1.1 − ptÏðèêëàäíàÿ àëãåáðà71 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâ×èñëî íåïðèâîäèìûõ íîðìèðîâàííûõ ìíîãî÷ëåíîâ dn ...ÄîêàçàòåëüñòâîÏðîëîãàðèôìèðóåì:Xdn ln(1 − tn ) = ln(1 − pt) .nÏðîäèôôåðåíöèðóåì ïî t:Xndnntn−1p=.n1−t1 − ptÑíîâà âîñïîëüçóåìñÿ ñóììîé ãåîìåòðè÷åñêîé ïðîãðåññèè:XXdn ntn−1 tnk =ps+1 ts .n,ksÏðèêëàäíàÿ àëãåáðà72 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâ×èñëî íåïðèâîäèìûõ íîðìèðîâàííûõ ìíîãî÷ëåíîâ dn ...ÄîêàçàòåëüñòâîÊîñìåòè÷åñêèå ïðåîáðàçîâàíèÿ:XXndn tn(k+1) =ps ts .n,ksÐàâåíñòâî êîýôôèöèåíòîâ ïðè îäèíàêîâûõ ñòåïåíÿõ t â ëåâîé èïðàâîé ÷àñòè è åñòü óòâåðæäåíèå ëåììû.Ïðèêëàäíàÿ àëãåáðà73 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÂàæíûå çàìå÷àíèÿÇàìå÷àíèå (Äîêàçàòåëüñòâîíåïðèâîäèìûõ ïîëèíîìîâ)òåîðåìûîñóùåñòâîâàíèèÈç äàííîé ëåììû ñëåäóåò íåðàâåíñòâî ndn 6 pn .
Ïðîñòàÿ îöåíêàndn =Xk|n, k<nnkdk > p −n−1Xk=0pk = pn −pn − 1>0.p−1äîêàçûâàåò, ÷òî dn >0, à ýòî îçíà÷àåò, ÷òî ñóùåñòâóåò õîòÿ áû îäèííåïðèâîäèìûé ìíîãî÷ëåí ñòåïåíè n.Çàìå÷àíèåÈç äàííîé ëåììû âûòåêàåò, ÷òî ïðè n → ∞ èìååì dn ∼ pn /n.Òàêèì îáðàçîì, ïðèìåðíî, 1/n-ÿ ÷àñòü âñåõ ìíîãî÷ëåíîâ ñòåïåíè níàä ïîëåì èç p ýëåìåíòîâ íåïðèâîäèìà.Ïðèêëàäíàÿ àëãåáðà74 / 225Ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èçpnýëåìåíòîâÂàæíûåÄîêàæåì âòîðóþ ÷àñòü îñíîâíîé òåîðåìû î êîíå÷íûõ ïîëÿõ:ëþáûå äâà ïîëÿ ñ îäèíàêîâûì ÷èñëîì ýëåìåíòîâ èçîìîðôíû.ÒåîðåìàÏóñòü m ìèíèìàëüíàÿ ôóíêöèÿ ýëåìåíòà α ∈ Fnp è d å¼ ñòåïåíü.
Òîãäà ïîëå Fp [x]/(m) èçîìîðôíî ïîäïîëþ Fdp ,ïîðîæäåííîìó ñòåïåíÿìè α.ÄîêàçàòåëüñòâîÑòåïåíè α ïðèíàäëåæàò d-ìåðíîìó ïðîñòðàíñòâó ñ áàçèñîì1, α, α2 , . . . , αd−1 , êîòîðîå ÿâëÿåòñÿ ïîäïîëåì ïîëÿ Fnp ,ïîñêîëüêó çàìêíóòî îòíîñèòåëüíî ñëîæåíèÿ è óìíîæåíèÿ èñîäåðæèò 0 è 1.Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÐàçäåë I1Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IÏîëÿ âû÷åòîâ ïî ìîäóëþ ïðîñòîãî ÷èñëàÏîñòðîåíèå ïîëåé ÃàëóàËèíåéíàÿ àëãåáðà íàä êîíå÷íûì ïîëåìÊîðíè ìíîãî÷ëåíîâ íàä êîíå÷íûì ïîëåì2Êîíå÷íûå ïîëÿ èëè ïîëÿ Ãàëóà - IIÑóùåñòâîâàíèå è åäèíñòâåííîñòü ïîëÿ Ãàëóà èç pnýëåìåíòîâÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÇàäà÷è3Êîäû, èñïðàâëÿþùèå îøèáêèÎñíîâíàÿ çàäà÷à òåîðèè êîäèðîâàíèÿÖèêëè÷åñêèå êîäû75 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÐàçäåë IIÊîäû Á×Õ4Òåîðèÿ ïåðå÷èñëåíèÿ ÏîéàÄåéñòâèå ãðóïïû íà ìíîæåñòâåÏðèìåíåíèå ëåììû Áåðíñàéäà äëÿ ðåøåíèÿêîìáèíàòîðíûõ çàäà÷5×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèËèíåàðèçàöèÿ6Àëãåáðàè÷åñêèå ðåø¼òêèÐåø¼òêè76 / 225Ïðèêëàäíàÿ àëãåáðà77 / 225Ïîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÊîëüöîFp /(f ) ïðèëîæåíèÿõ ÷àñòî èñïîëüçóåòñÿ êîëüöî Fp /(f ) ïî ìîäóëþ ãëàâíîãîèäåàëà íå îáÿçàòåëüíî íåïðèâîäèìîãî ìíîãî÷ëåíà f ∈ Fp [x].Åñëè f íåïðèâîäèì, òîFp /(f ) ïîëå è ýòîò ñëó÷àé óæå ðàññìîòðåí.Ïðèêëàäíàÿ àëãåáðà77 / 225Ïîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÊîëüöîFp /(f ) ïðèëîæåíèÿõ ÷àñòî èñïîëüçóåòñÿ êîëüöî Fp /(f ) ïî ìîäóëþ ãëàâíîãîèäåàëà íå îáÿçàòåëüíî íåïðèâîäèìîãî ìíîãî÷ëåíà f ∈ Fp [x].Åñëè f íåïðèâîäèì, òîFp /(f ) ïîëå è ýòîò ñëó÷àé óæå ðàññìîòðåí. ëþáîì ñëó÷àå âû÷åòû îáðàçóþò âåêòîðíîå ïðîñòðàíñòâî íàäìíîãî÷ëåíîâ ñòåïåíè íå âûøå deg f .Fp [x]= { 0, 1, . .
. , x, x + 1, . . . , f , . . . };(f ) = f = { t · f }, t ∈ Fp [x];Fp /(f )= { f , g, h, . . . }, deg g, deg h, . . . < deg f ;g = { t · f + g };h = { t · f + h };...g + f = g, g · f = f .FpÏðèêëàäíàÿ àëãåáðà78 / 225Ïîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÍîðìèðîâàííûé äåëèòåëü â ïîðîæäàþùåãî ýëåìåíòà èäåàëàÒåîðåìàÏóñòü ϕ íåïðèâîäèìûé íîðìèðîâàííûé ìíîãî÷ëåí, êîòîðûéäåëèò f : ϕ | f . Òîãäà ñîâîêóïíîñòü âñåõ âû÷åòîâ, êðàòíûõ ϕ,îáðàçóåò èäåàë â êîëüöå êëàññîâ âû÷åòîâ ïî ìîäóëþ f è ϕ åäèíñòâåííûé íîðìèðîâàííûé ìíîãî÷ëåí ìèíèìàëüíîé ñòåïåíèâ ýòîì èäåàëå.ÄîêàçàòåëüñòâîÈòàê, (f ) = tf , t, s ∈ Fp [x], deg f > deg ϕ = kϕ = a0 + a1 x + .
. . + ak−1 xk−1 + 1 · xk , f = ϕ∗ ϕ;defIϕ = sϕ ⊆ (f ) = tϕ∗ ϕ ⇔ deg s > deg ϕ.Ïðèêëàäíàÿ àëãåáðà79 / 225Ïîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÍîðìèðîâàííûé äåëèòåëü...Ïðîâåðèì, ÷òî Iϕ èäåàë. g = {sϕ}, h = {rϕ}; s, r ∈ Fp [x].1g ∈ Iϕ ,h 6 g.⇔{sϕ}, deg s > deg ϕ{rϕ}, deg r > deg s.⇒⇒⇒⇒ deg r > deg ϕ ⇒ h ∈ Iϕ2g, h ∈ Iϕ ⇔ deg s, deg r > deg ϕ.g + h = {sϕ} + {rϕ} = {(s + r)ϕ};deg(s + r) > deg ϕ ⇒ g + h ∈ Iϕ .Ïðèêëàäíàÿ àëãåáðà80 / 225Ïîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÍîðìèðîâàííûé äåëèòåëü...Ïîêàæåì, ÷òî â Iϕ íåò äðóãèõ, êðîìåϕ = a0 + a1 x + . . . + ak−1 xk−1 + xkíîðìèðîâàííûõ ìíîãî÷ëåíîâ ñòåïåíè, ìåíüøåé k = deg ϕ.Ïóñòü ψ = b0 + b1 x + . .
. + bm−1 xm−1 + xm ∈ Iϕ , m 6 k . Òîãäà:m > k, ò.å. k = mψ ∈ Iϕ ⇒ ϕ | ψ ⇒⇒ ψ = ϕ.bi = ai , i = 0, 1, . . . , m − 1Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÏîäûäåàë êàê âåêòîðíîå ïðîñòðàíñòâîÒåîðåìàÏóñòü ϕ íåïðèâîäèìûé íîðìèðîâàííûé äåëèòåëü ìíîãî÷ëåíàf ∈ Fp [x] îòëè÷íûé îò f , deg f = n, deg ϕ = k . Òîãäà èäåàë(ϕ) âåêòîðíîå ïðîñòðàíñòâî ðàçìåðíîñòè n − k .Äîêàçàòåëüñòâî81 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÏîäûäåàë êàê âåêòîðíîå ïðîñòðàíñòâîÒåîðåìàÏóñòü ϕ íåïðèâîäèìûé íîðìèðîâàííûé äåëèòåëü ìíîãî÷ëåíàf ∈ Fp [x] îòëè÷íûé îò f , deg f = n, deg ϕ = k . Òîãäà èäåàë(ϕ) âåêòîðíîå ïðîñòðàíñòâî ðàçìåðíîñòè n − k .ÄîêàçàòåëüñòâîÁåç äîêàçàòåëüñòâà.81 / 225Ïðèêëàäíàÿ àëãåáðàÏîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÖèêëè÷åñêîå ïðîñòðàíñòâî: îïðåäåëåíèåÏóñòü 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 ).82 / 225Ïðèêëàäíàÿ àëãåáðà83 / 225Ïîëÿ Ãàëóà - IIÖèêëè÷åñêèå ïîäïðîñòðàíñòâàÊîëüöî êëàññîâ âû÷åòîâ ïî ìîäóëþ ìíîãî÷ëåíà xn − 1 êîëüöå Fp /(xn − 1), ðàññìàòðèâàåìîì êàê âåêòîðíîåïðîñòðàíñòâî íàä ïîëåì Fp , åñòü áàçèñ { 1, x, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
