[es] - Računanje Galoaove grupe

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.3gnet.mts.telekom.rs.

+2801 Profil

^{13.05.2013. u 19:32 - pre 145 meseci}

Polje algebarskih brojeva je rekurzivno. To znači da postoji reprezentacija algebarskih brojeva, tako da se može algoritamski računati sa njima (množiti, deliti, sabirati, oduzimati i porediti da li su jednaki), baš kao što racionalni brojevi imaju reprezentaciju (par - brojilac, imenilac) takav da postoje pravila računanja sa time.

Pošto je algebarski broj koren polinoma stepena bar jedan sa racionalnim koeficijentima, može se kao reprezentacija izabrati par - polinom, disk čiji centar ima racionalan realan i imaginaran deo i racionalan poluprečnik takav da željeni koren polinoma pripada unutrašnjosti diska, a ostali ne pripadaju zatvorenju diska.

Pritom se lako može osloboditi najpre višestrukih korena polinoma, jer polinom

ima isti skup korena kao polinom

, ali je svaki jednostruk. Time prelazimo na slučaj kada nam je broj korena polinoma poznat (jednak stepenu polinoma). Dalje, postoje globalno konvergentni algoritmi za numeričko rešavanje algebarskih jednačina. To znači da možemo odrediti onoliko proizvoljno malih disjunktnih diskova koji sadrže po jedan koren, koliki je stepen polinoma. Time se svi koreni polinoma mogu izračunati sa proizvoljnom tačnošću.

Računanjem vrednosti izraza u tački koja je neki od tih korena uzimajući u obzir disk kome koren pripada i grešku odsecanja prilikom računanja može se odrediti disk kome pripada vrednost izraza, pri čemu taj dosk može biti po želji mali s tim da se odredi dovoljno mali disk kome pripada taj koren. Takođe, algoritmima za faktorizaciju, kao što je na primer Kronekerov, može se polinom faktorisati na proste činioce nad poljem

. Ako se svaki od faktora izračuna u tački koja predstavlja željeni koren i dobije disk kome pripada željena vrednost, dobijanjem sve manjih diskova će se dobiti za sve faktore osim jednog da im taj koren polaznog polinoma nije koren, na osnovu čega je taj koren polaznog polinoma koren preostalog faktora. Tako se u reprezentaciji može preći na nesvodljiv polinom nad poljem

.

Problem je kako na osnovu reprezentacija algebarskih brojeva

izračunati reprezentaciju od npr.

i slično za oduzimanje, delenje, množenje i korenovanje proizvoljnog stepena.

Ako je

, pri čemu je

, onda se svaki stepen broja

može prikazati kao linearna kombinacija stepena broja

sa izložiocima manjim od

i sa racionalnim koeficijentima. Naime, ako je

ostatak pri delenju polinoma

polinomom

, onda je

. Slično važi i za stepene broja

.

Uočimo brojeve

, gde je

i numerišimo ih i označimo sa

. Svaki broj oblika

se može prikazati kao linearna kombinacija brojeva

sa racionalnim koeficijentima. Korišćenjem te činjenice i binomne formule se može broj

izraziti kao linearna kombinacija brojeva

sa racionalnim koeficijentima.

Ako je

, formirajmo matricu formata

takvu da se u preseku

-te vrste i

-te kolone nalazi

. Obzirom da je broj vrsta veći od broja kolona, vrste matrice su linearno zavisne, postoje racionalni brojevi

od kojih barem jedan nije nula, takvi da je

za svako

. Stoga je

,

odnosno

. Slično se postupa u slučaju ostalih operacija. Nakon što smo odredili nenula polinom sa racionalnim koeficijentima čiji je jedan od korena

treba odrediti bar jedan disk u čijoj unutrašnjosti leži

i čijem zatvorenju ne pripada nijedan drugi koren polinoma

. To se može učiniti sve tačnijim izračunavanem brojeva

u cilju sve tačnijeg izračunavanja broja

i sve tačnijim računanjem svih korena polinoma

sve dok disk koji sadrži

ne postane disjunktan sa diskovima koji sadrže korene polinoma

osim jednog.

Slično se postupa i sa oduzimanjem i množenjem. Što se inverza u odnosu na množenje tiče, ako je

, onda je

. Takođe, ako je

bilo koji

-ti kompleksni koren broja

, onda je

koren polinoma

. Za određivanje diskova važe slične primedbe kao malopre.

Napokon, kako utvrditi da li su brojevi

dati različitim reprezentacijama jednaki? Izračunajmo reprezentaciju broja

, pa ako se posle svođenja polinoma iz reprezentacije na minimalan dobije polinom

, onda je

, a u suprotnom nije.

_{[Ovu poruku je menjao Nedeljko dana 13.05.2013. u 21:51 GMT+1]}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8704
*.3gnet.mts.telekom.rs.

+2801 Profil

Re: Računanje Galoaove grupe

^{13.05.2013. u 20:45 - pre 145 meseci}

Proverimo koliko su ključne teoreme Galoaove teorije konstruktivne do na rekurzivnost polja algebarskih brojeva. Ispostaviće se da jesu.

Neka je dat polinom

sa racionalnim koeficijentima stepena barem jedan. Polinomi

imaju isti skup korena, pa samim tim i isto korensko polje, pa samim tim i istu Galoaovu grupu, pri čemu drugi nema višestrukih korena. Stoga se možemo ograničiti na slučaj polinoma bez višestrukih korena.

Ako su

svi koreni polinoma

bez višestrukih korena uzeti po jedanput (njihove reprezentacije su izračunljive na osnovu polinoma

), treba naći

koje je primitivni element korenskog polja polinoma

. U tu svrhu koristimo algoritam iz teoreme o primitivnom elementu. Ako su

algebarski brojevi dati reprezentacijama, postoji primitivan element oblika

, gde je

izabrano tako da ne zadovolji nijednu od nekih konačno mnogo linearnih jednačina sa koeficijentima koji su algebarski brojevi kojima možemo naći reprezentacije. Računajući sa reprezentacijama, za jedan po jedan ceo broj proveravamo da li ispunjava uslove dok ne nađemo onaj koji ispunjava. Tako nalazimo reprezentacije brojeva

takvih da je

. U tom slučaju je

traženi primitivni element.

Obzirom da imamo reprezentaciju elementa

, a ona se uvek može svesti na slučaj kada je polinom u reprezentaciji nesvodljiv nad poljem racionalnih brojeva, imamo i minimalni polinom primitivnog elementa. Numeričkim nalaženjem korena tog polinoma nalazimo i reprezentacije svih konjugata od

. Recimo da su svi oni

i da je

.

Automorfizmi korenskog polja (koje je Galoaovo raširenje osnovnog polja) slikaju algebarski broj u neki od njegovih konjugata, mogu ga preslikati u bilo koji od konjugata i jednoznačno su određeni slikom primitivnog elementa. Recimo da je