Računanje Galoaove grupe

Računanje Galoaove grupe 11.05.2005. u 23:15 · pre 261 mesec #1

Da li neko zna barem jedan algoritam za računanje Galoaove grupe proizvoljnog polinoma sa racionalnim koeficijentima?

Potpis

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

Re: Računanje Galoaove grupe 12.05.2005. u 01:16 · pre 261 mesec #2

Mislim da znam nekog ko zna

Re: Računanje Galoaove grupe 20.05.2005. u 10:55 · pre 261 mesec #3

Dobro, hoće li neko da odgovori, ili moram ja?

Potpis

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

Re: Računanje Galoaove grupe 31.05.2005. u 17:02 · pre 260 meseci #4

Ako nekoga zanima, mogu da postujem jedan algoritam.

Potpis

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

Re: Računanje Galoaove grupe 02.06.2005. u 14:35 · pre 260 meseci #5

Ja se lično ne bavim Galoaovim grupama ali ako te ne mrzi napiši taj algoritam koji znaš, možda će nekome nekad zatrebati.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Računanje Galoaove grupe 12.05.2013. u 17:18 · pre 164 meseca #6

Ja bih voleo da vidim, s tim da necu moci da ga detaljnije analiziram narednih 20-tak dana, jer trenutno radim druge stvari.

Potpis

Leonardo da Vinči

Nema istine u onim naukama u kojima se matematika ne primenjuje.

Milorad Stevanović

Bog postoji zato sto je matematika neprotivurečna.

Re: Računanje Galoaove grupe 13.05.2013. u 20:32 · pre 163 meseca #7

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 $p/NZD(p,p')$ ima isti skup korena kao polinom $p$ , 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 $Q$ . 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 $Q$ .

Problem je kako na osnovu reprezentacija algebarskih brojeva $a$ i $b$ izračunati reprezentaciju od npr. $a+b$ i slično za oduzimanje, delenje, množenje i korenovanje proizvoljnog stepena.

Ako je $p(a)=q(b)=0$ , pri čemu je $deg(p)=m$ i $deg(q)=n$ , onda se svaki stepen broja $a$ može prikazati kao linearna kombinacija stepena broja $a$ sa izložiocima manjim od $n$ i sa racionalnim koeficijentima. Naime, ako je $r_k(x)$ ostatak pri delenju polinoma $x^k$ polinomom $p(x)$ , onda je $a^k=r_k(a)$ . Slično važi i za stepene broja $b$ .

Uočimo brojeve $a^ib^j$ , gde je $i<m$ i $j<n$ i numerišimo ih i označimo sa $v_1,\dots,v_{mn}$ . Svaki broj oblika $a^kb^l$ se može prikazati kao linearna kombinacija brojeva $c_1,\dots,c_{mn}$ sa racionalnim koeficijentima. Korišćenjem te činjenice i binomne formule se može broj $(a+b)^k$ izraziti kao linearna kombinacija brojeva $c_1,\dots,c_{mn}$ sa racionalnim koeficijentima.

Ako je $(a+b)^k=\sum_{i=1}^{mn}\lambda_{k,i}c_i$ uz $\lambda_{k,i}\in Q$ , formirajmo matricu formata $(mn+1)\times mn$ takvu da se u preseku $k$ -te vrste i $i$ -te kolone nalazi $\lambda_{k-1,i}$ . Obzirom da je broj vrsta veći od broja kolona, vrste matrice su linearno zavisne, postoje racionalni brojevi $\alpha_0,\dots,\alpha_{mn}$ od kojih barem jedan nije nula, takvi da je $\sum_{k=0}^{mn}\alpha_k\lambda_{k,i}=0$ za svako $i\in\{1,\dots,mn\}$ . Stoga je

$\sum_{k=0}^{mn}\alpha_k(a+b)^k=\sum_{k=0}^{mn}\alpha_k\sum_{i=1}^{mn}\lambda_{k,i}c_i=\sum_{i=1}^{mn}c_i\sum_{k=0}^{mn}\alpha_k\lambda_{k,i}=\sum_{i=1}^{mn}0\cdot c_i=0$ ,

odnosno $s(a+b)=0$ za $s(x)=\alpha_0+\cdots+\alpha_{mn}x^{mn}$ . Slično se postupa u slučaju ostalih operacija. Nakon što smo odredili nenula polinom sa racionalnim koeficijentima čiji je jedan od korena $a+b$ treba odrediti bar jedan disk u čijoj unutrašnjosti leži $a+b$ i čijem zatvorenju ne pripada nijedan drugi koren polinoma $s(x)$ . To se može učiniti sve tačnijim izračunavanem brojeva $a$ i $b$ u cilju sve tačnijeg izračunavanja broja $a+b$ i sve tačnijim računanjem svih korena polinoma $s$ sve dok disk koji sadrži $a+b$ ne postane disjunktan sa diskovima koji sadrže korene polinoma $s$ osim jednog.

Slično se postupa i sa oduzimanjem i množenjem. Što se inverza u odnosu na množenje tiče, ako je $p(a)=0$ za $a\neq 0$ i $p(x)=c_0+\cdots c_nx^n$ , onda je $q(a^{-1})=0$ za $q(x)=c_n+\cdots+c_0x^n$ . Takođe, ako je $b$ bilo koji $n$ -ti kompleksni koren broja $a$ i $p(a)=0$ , onda je $b$ koren polinoma $p(x^n)$ . Za određivanje diskova važe slične primedbe kao malopre.

Napokon, kako utvrditi da li su brojevi $a$ i $b$ dati različitim reprezentacijama jednaki? Izračunajmo reprezentaciju broja $a-b$ , pa ako se posle svođenja polinoma iz reprezentacije na minimalan dobije polinom $p(x)=x$ , onda je $a-b=0$ , a u suprotnom nije.

Potpis

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

Re: Računanje Galoaove grupe 13.05.2013. u 21:45 · pre 163 meseca #8

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

Neka je dat polinom $p$ sa racionalnim koeficijentima stepena barem jedan. Polinomi $p$ i $p/NZD(p,p')$ 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 $a_1,\dots,a_n$ svi koreni polinoma $p$ bez višestrukih korena uzeti po jedanput (njihove reprezentacije su izračunljive na osnovu polinoma $p$ ), treba naći $a$ koje je primitivni element korenskog polja polinoma $p$ . U tu svrhu koristimo algoritam iz teoreme o primitivnom elementu. Ako su $\alpha$ i $\beta$ algebarski brojevi dati reprezentacijama, postoji primitivan element oblika $\alpha+n\beta$ , gde je $n\in Z$ 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 $\beta_2,\dots,\beta_n$ takvih da je $Q[a_1,a_2]=Q[\beta_2]$ i $Q[\beta_i,a_{i+1}]=Q[\beta_{i+1}]$ za $i\in{2,\dots,n-1}$ . U tom slučaju je $a=\beta_n$ traženi primitivni element.

Obzirom da imamo reprezentaciju elementa $a$ , 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 $a$ . Recimo da su svi oni $c_1,\dots,c_m$ i da je $a=c_1$ .

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 $f_i$ automorfizam za koji je $f(c_1)=c_i$ . Pitanje je šta je $f_i(c_j)$ . Svakako mora biti u pitanju jedan od brojeva $c_1,\dots,c_m$ . Ako je $q_j$ polinom sa racionalnim koeficijentima takav da je $c_j=q_j(c_1)$ , onda je $f_i(c_j)=f_i(q_j(c_1))=q_j(f_i(c_1))=q_j(c_i)$ . Obzirom da ova vrednost mora pripadati konačnom skupu $\{c_1,\dots,c_m\}$ , numeričkim računanjem možemo poodbacivati sve mogućnosti osim jedne i zaključiti koliko je $f_i(c_j)$ .

Ostaje da se odredi polinom $q_j$ . On se može odrediti tako što se nabrajaju svi polinomi $r_i$ sa racionalnim koeficijentima stepena nižeg od $m$ dok se ne nađe onaj čija je vrednost u tački $c_1$ jednaka $c_j$ . Naravno, ima i efikasnijih načina, ali i ovo je dovoljno za konstrukciju algoritma, koliko god on bio neefikasan.

Potpis

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

Re: Računanje Galoaove grupe 15.05.2013. u 20:49 · pre 163 meseca #9

Postoji još nešto - ako se ispostavi da je Galoaova grupa rešiva, postoji algoritam koji ispisuje radikalska rešenja. Pristup je opet u tome da se slede ključne teoreme Galoaove teorije, čiji su standardni dokazi konstruktivni do na rekurzivnost polja algebarskih brojeva, ali je priča kudikamo duža i zaista me mrzi da pišem. U svakom slučaju bih voleo da čujem druge šta misle o ovome.

Potpis

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

Re: Računanje Galoaove grupe 17.05.2013. u 09:29 · pre 163 meseca #10

Ispravka:

Citat:

Nedeljko: Uočimo brojeve $a^ib^j$ , gde je $i<m$ i $j<n$ i numerišimo ih i označimo sa $v_1,\dots,v_{mn}$ .

Umesto $v_1,\dots,v_{mn}$ treba $c_1,\dots,c_{mn}$ .

Potpis

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

Forum kao aplikacija na telefonu

Srodne teme