Gorputz finitu

Matematikan, gorputz finitua edo Galoisen gorputza elementu kopuru finitua duen gorputza da. Gorputz bat multzo bat da zeinetan bi eragiketa definituta ditugun, batuketa eta biderketa deritzegunak. Gorputza izateko eragiketek baldintza batzuk bete behar dituzte. Gorputz finituak, beraz, gorputzen kasu berezi bat dira zeinetan elementu kopurua finitua den.

Gorputz finitu baten ordena bere elementu kopurua da. Hau beti p zenbaki lehen bat edo p zenbaki lehenaren berretura bat da. Gainera, edozein zenbaki lehenetarako eta beraien berreturetarako, beti existitzen da ordena hori duen gorputz finitu bat. Bestalde, ordena bereko bi gorputz finitu beti isomorfoak dira.

Gorputz finituak funtsezkoak dira matematikaren eta informatikaren hainbat arlotan, besteak beste, zenbakien teorian, geometria aljebraikoan, Galoisen teorian, geometria finituan, kriptografian eta kodifikazioaren teorian.

Historia

Évariste Galois, gorputz finituetan aritu zen lehenengoetariko matematikaria

Gorputz finituen teoriaren hastapena XIX. mendearen bigarren erdialdean kokatzen da, Richard Dedekind matematikari alemaniarrak Körper terminoa asmatu zuenean, euskaraz gorputza esaten dena. Hala ere, honen definizioa Heinrich Weber-ek zehaztu zuen, baina gaur egun erabiltzen den definizioa Ernest Steinitz matematikariak idatzi zuen 1910. urtean.

Lehen aldiz gorputz finituak erabili zituen matematikaria Ferdinand George Frobenius izan zen XIX. mende amaieran. Frobenius matematikariak gorputz finituak erabili zituen talde finituen aurkezpenak lortzeko. Horrekin erlazionaturik, Frobenius-en endomorfismoa sortu zuen, Galois-en teoria gorputz finituetan erabiltzea ahalbidetuz.

Gorputz finituen azterketa sistematikoa XX. mendean hasi zen Leonard Dickinson-en azterlanekin. Dickinsonek gorputz finitu abeldarren lehenengo sailkapena egin zuen. Halaber, 1905. urtean argitaraturiko lanean frogatu zuen ez dela existitzen gorputz finitu ez abeldarrik. Bestalde, Wedderburn matematikariarekin lan egin zuenez, teorema honi Wedderburn-en teorema izena eman zitzaion.

Notazioa

Hurrengo notazioak honela ulertu behar dira:

• $n$ zenbaki osoa bada, $na$ $F$-ko elementua honela definitzen da:
  1. $a+\dots +a$ $n>0$ bada.
  2. $0$ $n=0$ bada.
  3. $(-a)+\dots +(-a)$ $n<0$ bada.
• $n$ arrunta edo zero bada, $a^{n}F$-ko elementua honela definitzen da:
  1. $a\dots a$ $n>0$ bada.
  2. $0$ $n=0$ bada.
• $n$ zenbaki osoa negatiboa bada, $a^{n}F$-ko elementua honela definitzen da: $(a^{-1})\dots (a^{-1})$

Propietateak

Propietateak azaldu baino lehen, komenta dezagun zer den gorputz baten karakteristika. Gorputz baten karakteristika $n$ zenbaki arruntik txikiena da zeinetarako $1$ $n$ aldiz batuz $0$ ematen duen. Horrela bada, $char(F)=n$ idazten da. Ohartu definizio hau goian aipatutako notazioarekin azaldu dela.

Unitatearen erroak plano konplexuan irudikaturik

$F$ gorputz finitua bada, existitzen dira $p$ zenbaki lehena eta $n$ zenbaki arrunta non $|F|=p^n$ den. Kasu horretan, froga daiteke $char(F)=p$ dela.

$q=p^n$ bada, $q$ ordenako gorputz guztiak isomorfoak dira. Gainera, gorputz batek ezin ditu ordena bereko bi azpigorputz izan.

$q$ ordenako gorputz finitua $X^q-X$ polinomioaren erroek osatzen dute. Gainera, gorputz honen unitateek talde bat osatzen dute biderketarekiko. Talde hau ziklikoa da eta bere sortzaileari unitatearen jatorrizko $(q-1)$. erroa deritzo.

$q$ ordenako edozein gorputz finituren elementuak $\{0,1,...,q-1\}$ bezala adieraz daitezke, ${𝔽}_q$ eta $\frac{\mathbb{Z}}{q\mathbb{Z}}$ isomorfoak baitira.

$F$-ren karakteristika $p$ denez, $x$ eta $y$ $F$-ko bi elementu hartzen baditugu, hurrengoa betetzen da:$$(x+y{)}^p=x^p+y^p$$

Existentzia eta bakartasuna

Izan bitez $q=p^n$ non $p$ zenbaki lehena den eta $F$ $X^q-X$ polinomioaren deskonposizio gorputza ${𝔽}_q$ gainean.

1893. urtean E. H. Moore matematikariak lehen aldiz frogatutako teoremaren arabera, edozein $q$ zenbaki lehen baten berreturarako ordena horretako gorputz finitua existitzen da, eta ordena bereko gorputz finitu guztiak isomorfoak dira. Gorputz hauetako edozein elementutarako, beti betetzen da $X^q=X$ berdintza.

Halaber, ${𝔽}_p^n$ gorputzak ${𝔽}_p^m$ erako azpigorputza du baldin eta soilik baldin $m$-k n zatitzen badu. Gainera, azpigorputz hori bakarra da. Bereziki, $X^{p^m}-X$ polinomioak $X^{p^m}-X$ polinomioa zatitzen du.

Gorputz finituen eraikuntza

Dagoeneko azaldu den bezala, $p$ zenbaki lehena denean, ${𝔽}_p$ isomorfoa da $\frac{\mathbb{Z}}{p\mathbb{Z}}$ gorputzarekin. Baina, ohartu, $p$ zenbaki lehena ez den kasuan, isomorfismo hau ez dela egia; izan ere, $\frac{\mathbb{Z}}{p\mathbb{Z}}$ ez da gorputza. Orduan, $p$ zenbaki lehena ez den kasurako, atal honetan ikusiko dugu zein gorputzekiko den isomorfoa.

Demagun $q=p^n$ dela, $n>1$ izanik; kasu honetan, aukeratu $P(X)$ ${𝔽}_q[X]$-ren $n$ mailako polinomio irreduzible bat. Orduan, ${𝔽}_q$ isomorfoa da$\frac{{𝔽}_q[X]}{P(X)}$-rekiko.

Adibideak

1. Adibidea: Kalkula dezagun ${𝔽}_4$ gorputza zein zatidura gorputzekiko den isomorfoa. $4=2^2$ denez,

$\frac{{𝔽}_2[X]}{P(X)}$ eginik eraikiko dugu ${𝔽}_4$ gorputzean, $P(X)$ ${𝔽}_2[X]$ gaineko polinomio bat izanik. Gainera, ${𝔽}_2$-ren gainean, bigarren mailako polinomio irreduzible bakarra $X^2+X+1$ da (hau erraz frogatu daiteke irreduzibilitatearen baldintzak probatuz, soilik bigarren mailakoa baita). Ondorioz, ${𝔽}_4$ sortzeko $\frac{{𝔽}_2[X]}{(X^2+X+1)}$ zatidura-eraztuna egin behar dugu. Honekin, lau elementuko gorputz finitua lortuko dugu. Laburbilduz, isomorfismo hau dugu: ${𝔽}_4\cong$$\frac{{𝔽}_2[X]}{(X^2+X+1)}$.

2. Adibidea: Kalkula dezagun ${𝔽}_8$ gorputza zein zatidura gorputzekiko den isomorfoa. Ohartu $8=2^3$ dela. Hortaz, ${𝔽}_2[X]$ eraztuna eta eraztun honen 3. mailako polinomio irreduzible bat behar dugu. $X^3+3X+3$ polinomio irreduziblea denez ${𝔽}_2[X]$-n, ${𝔽}_8$ isomorfoa da $\frac{{𝔽}_2[X]}{(X^3+3X+3)}$.

3. Adibidea: Kalkula dezagun ${𝔽}_{16}$ gorputza zein zatidura gorputzekiko den isomorfoa. $16=2^4$ denez ${𝔽}_2[X]$ eraztuna eta eraztun honen 4. mailako polinomio irreduzible bat behar dugu. Kasu honetan, $X^4+X+1$ polinomioa ${𝔽}_2[X]$-n irreduziblea denez, ${𝔽}_{16}$ isomorfoa da $\frac{{𝔽}_2[X]}{(X^4+X+1)}$ zatidura gorputzarekiko.

Egitura biderkakorra

Izan bedi $F$ $q$ elementudun edozein gorputz. Gorputz guztiekin gertatzen den bezala, bertako elementu guztiak $0$ izan ezik unitateak dira. Beraz, izan bedi $𝒰(F)$ $F$-ren unitateen multzoa. Esan bezala, bertan $F$-ko elementu guztiak daude $0$ izan ezik. Hori dela eta, $𝒰(F)$-n $q-1$ elementu daude. Gorputzen izateko baldintzak aztertuz gero, berehala ikusten da $𝒰(F)$-k gorputz egitura duela (eta $F$ finitua denez, bereziki $𝒰(F)$ ere finitua izango da).

Baldintza hauen artean, $𝒰(F)$-k talde abeldar egitura izateko bete behar diren baldintzak daude. Hori dela eta, esaten da $𝒰(F)$-k talde abeldar egitura duela biderketarekiko. Hori dela eta, askotan $𝒰(F)$-k talde biderkakor egitura duela esaten da. Talde teorian ezaguna den Lagrange-ren teorema erabiliz, existitzen da $k$ $q-1$ zenbakiaren zatitzaile bat zeinak $x^{k-1}=1$ betetzen duen, edozein $x\in 𝒰(F)$-rentzat. Nabaria den bezala, ekuazio horrek asko jota $k$ soluzio ezberdin ditu edozein gorputzen gainean (bereziki $𝒰(F)$ gainean). Gainera, esan dugu  zenbakiak $q-1$ zatitu behar duela. Hori dela eta, $k$-k hartu ahal duen baliorik txikiena $q-1$ izango da.

Talde abeldar finituen oinarrizko teoremagatik, $𝒰(F)$ taldeak talde zikliko egitura duela ondorioztatu daiteke. Ondorioz, talde hori modu honetan idatzi daiteke:

$$𝒰(F)=⟨a⟩=\{1,a,a^2,\dots ,a^{q-2}|a\in 𝒰(F)\}$$

Kasu horretan, $a$ $𝒰(F)$-ren jatorrizko elementua dela esaten da.

Teorema garrantzitsuenak

Gorputz finituei buruzko ondoko teorema hauek ezagutu behar dira, haien funtsezko propietateak baitira.

Teorema: Edozein gorputz finituren karakteristika zenbaki lehen bat da.

Froga: $F$-k gorputz egitura badu, bereziki talde abeldar egitura izango du. Gainera, $F$ finitua denez, taldea ere finitua izango da. Ondorioz, esan genezake $(F,+)$ talde abeldar finitua izango dela. Edozein taldetan eragiketarekiko identitatea dago. Gure kasuan identitate hori $1$ denez, $1\in F$ idatzi daiteke. Lagrangeren teorema aplikatuz, elementu horren ordenak taldearen ordena zatitzen du: $o(1)=1$-ek $|F|$ zaitzen du. Beraz, taldearen karakteristika ezin da $0$ izan (bestela, taldea infinitua izango zen eta hori absurdua litzateke). Ezaguna den bezala, gorputzen karakteristika $0$ edo zenbaki lehen bat da. Lehenengoa ezin denez bete, nahitaez $F$-ren karakteristika lehena izan behar da.

Teorema: Izan bedi $F$ gorputz finitua non $|F|=p^n$. Orduan $F$-ko elementuak $X^{p^n}-X$ polinomioaren erroak dira. Gainera, mota horretako polinomioen deskonposizio gorputzak isomorfoak direnez beraien artean, askotan $F={𝔽}_{p^n}$ izendatzen da.

Froga: Frogatu behar da edozein $u\in F$ hartuz $u^q=u$ dela. Bi kasu daude: $u=0$ bada, nabaria da esandakoa betetzen dela.

Beste kasua frogatzeko, demagun $u\ne 0$ dela. Orduan $u$ alderanzgarria da, hau da, $u\in 𝒰(F)$ da. $(𝒰(F),*)$ taldea finitua da eta $|𝒰(F)|=q-1$ betetzen da. Ondorioz $u^{q-1}=1$ beteko da eta hortik $u^q=u$ dela ondorioztatzen da. Beraz, oraingoz $F\subseteq${$X^q-X$-ren erroak} dela frogatu dugu. Beste noranzkoa frogatzeko, ohartu $|F|=q$ dela eta $X^q-X$-ren erro kopuru ezberdin kopurua $q$ edo txikiagoa dela. Hori dela eta, nahi genuen partekotasuna betetzen da,  $F=${$X^q-X$-ren erroak}.

Polinomioen faktorizazioa

Gorputz finituetan, finituak ez diren gorputzetan ez bezala, polinomio monikoen irreduzibilitatearen azterketa errazagoa da. Demagun $F$ gorputz finituaren gaineko $f(X)$ polinomio monikoa dugula. Orduan $f(X)$ polinomioa irreduziblea izango da $F$-n baldin eta soilik baldin ez badira existitzen beste bi polinomio ez-konstante, $g(X)$ eta $h(X)$, non $f(X)$ polinomioa horrela idatzi ahal den: $f(X)=g(X)h(X)$. Propietate hori hurrengo moduan berridatzi daiteke: $F$ gaineko edozein $f(X)$ polinomio irreduziblea izango da $f(X)=g(X)h(X)$ idatzi ahal bada, $g(X)$ eta $h(X)$ $F$ gaineko beste bi polinomio izanik, orduan $g(X)$ edo $h(X)$ (gutxienez bietako bat) $F$-ko unitatea bada. Ohartu elementu bat unitatea izateko $F$-n, bere alderantzizkoa izan behar duela. $F$-ko elementuak polinomioak ez direnez, alderantzizkoa duten polinomio bakarrak polinomio konstanteak izango dira.

Gorputz orokorretan gertatzen den bezala, gorputz finituak ere faktorizazio bakarreko domeinuak dira. Hori dela eta, aurreko atalean idatzitako $f(X)$-ren deskonposizioa bakarra izango da, gaien ordena salbu.

Gainera, lehen mailako polinomioen bidez polinomio berezi bat lortu daiteke: izan bedi $F$ $q$ elementudun gorputza. Izan bedi $\{f_1(X),\dots ,f_n(X)\}$ $F$-n koefizienteak dituzten lehen mailako polinomio ezberdin guztiak, $n$ zenbaki arrunta izanik. Ohartu printzipioz ez dagoela erlaziorik $q$ eta $n$ zenbakien artean. Orduan, polinomio horien biderketa eginez, beti hurrengo polinomioa lortzen da:

$$f_1(X)\dots f_n(X)=X^q-X$$Propietate hori erabiliz, frogatu daiteke gorputz finituen gaineko edozein mailatako polinomio irreduzibleen kopurua zehaztu daitekeela. Demagun $F$ $q$ elementudun gorputza dela eta $n$ ordenako polinomio irreduzible monikoen kopurua lortu nahi dugula. Orduan, zenbaki hori (deitu $N(q,n)$) hurrengoa da:$$N(q,n)=\frac{1}{n}\sum _{d|n}\mu (d)q^{\frac{n}{d}}$$Formula horretan $\mu$ Möbius-en funtzioa da eta $d|n$ notazioaren bidez $n$ zatitzen dituzten $d$ zenbakiak adierazi nahi dira. Formula horren frogapena aipaturiko $X^q-X$-ren deskonposizioaren eta Möbius-en inbertsio formularen bidez egiten da.

Formula hori egokitu daiteke monikoak ez diren polinomio kopurua zehazteko. Aurretik esandako egoeran, deitu diezaiogun $M(q,n)$ $F$ gaineko $n$ ordenako polinomio irreduzibleen kopuruari (monikoak eta ez monikoak). Orduan betetzen da:$$M(q,n)=(q-1)N(q,n)$$Horren frogapenean hurrengo formulara iristen gara:$$N(q,n)\ge \frac{1}{n}(q^n-\sum _{p|nplehena}{q}^{\frac{n}{p}})$$Gainera, formula hori hertsia da baldin eta soilik baldin  zenbaki lehen baten berredura gisa idatzi ahal bada (hau da, $n=u^r$ idatzi ahal bada, $u$ zenbaki lehena izanik eta $n$ zenbaki arrunt bat izanik). Eskuineko zenbakia beti positiboa denez, zuzenean ondoriozta daiteke gutxienez maila bakoitzeko polinomio irreduzible bana dagoela $F$ gainean.

Aplikazioak

${ℝ}^2$-ko kurba eliptiko bat.

Kriptografian, logaritmo diskretuaren problema, bai gorputz finituetan bai kurba eliptikoetan, hainbat metodoren oinarria da, haien artean Diffie-Hellman metodoa. Kode teorian, kode asko gorputz finituen gaineko espazio bektorialen azpiespazio gisa eraikitzen dira.

Errore-zuzenketa kode askok gorputz finituak erabiltzen dituzte, hala nola Reed-Solomon errore-zuzenketa kodeak edo BCH kodeak. Praktikan, gorputz finituen karakteristika 2 izan ohi da; izan ere, ordenagailuetan informazioa sistema bitarrean gordetzen da. Adibidez, informazioko “byte” bat GF($2^8$)-ko elementutzat ikus har daiteke. Salbuespen bat PDF417 kode-barra da, GF(929)-ko elementuak erabiltzen dituelako. CPU batzuek 2 karakteristika duten gorputz finituentzat erabilgarriak izan daitezkeen agindu bereziak dituzte, oro har “carry-less”  biderkadura aldaketak.

Gorputz finituak oso erabiliak dira zenbaki-teorian, zenbaki osoen gaineko problema asko ebatz baitaitezke 1 moduluarekin edo zenbaki lehen baten moduluarekin. Esate baterako, polinomioak faktorizatzeko algoritmo azkarrenek metodo hau erabiltzen dute eta, honen ondoren, soluzioa berreraikitzeko hondarraren metodo txinatarra, Hensel lifting edo “LLL” algoritmoa erabiltzen.

Halaber, problema teoriko asko zenbaki-teoriaren bidez ebatz daitezke zenbaki lehen batzuen moduluarekin edo zenbaki lehen guztien moduluarekin sinplifikatuz, haien artean Hasse printzipioa. Metodo hauen indarra handitzeko beharrari esker, aljebra geometrikoko hainbat aurkikuntza sustatu ziren. Fermat-en azken teoremaren Wiles-en froga gorputz finituak erabiltzen dituen emaitza sakon baten adibidea da.

Weil-en aieruek gorputz finituen gaineko barietate aljebraikoen puntu kopuruei buruz hitz egiten dute. Teoriak aplikazio asko ditu esponentzialen eta karaktere batuketen estimazioetan.

Gorputz finituek aplikazio oso zabala dute matematika konbinatorioan; bi adibide oso ezagun ditugu: Paley grafoen definizioak eta Hadamard matrizeen eraiketa. Aritmetikan, gorputz finitu konbinatorioak eta gorputz finituen ereduak oso erabiliak dira, hala nola Szemerédi-ren teorema progresio aritmetikoetan.