Ciało skończone

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Ciało skończone lub ciało Galoisciało skończonego rzędu, tj. o skończonej liczbie elementów; druga z nazw pochodzi od nazwiska francuskiego matematyka Évariste'a Galois, który znacząco przyczynił się do rozwoju badań nad ciałami skończonymi oraz wskazał ich zastosowanie w tzw. teorii Galois dającej m.in. definitywną odpowiedź na pytania o rozstrzygnięcie możliwości wykonania klasycznych konstrukcji w geometrii euklidesowej, czy też zgrabnie uzasadniającej brak ogólnych wzorów na pierwiastki wielomianów wyższych stopni.

W artykule za naturalne uważa się dodatnie liczby całkowite, ciało proste o elementach (tzn. rzędu gdzie jest liczbą pierwszą) oznaczane będzie zamiennie jednym z symboli oraz inną stosowaną notacją jest (od ang. Galois field, ciało Galois).

Konstrukcja i własności[edytuj]

Niech będzie liczbą pierwszą, a będzie unormowanym (monicznym) wielomianem nierozkładalnym stopnia należącym do (tj. zmiennej o współczynnikach z ciała ). Pierścień jest wtedy ciałem rzędu [1]. Każde ciało skończone ma rząd wyrażający się naturalną potęgą liczby pierwszej[2], a ponadto jest izomorficzne z dla pewnej liczby pierwszej i unormowanego wielomianu nierozkładalnego należącego do (grupa multiplikatywna ciał skończonych jest cykliczna[3])[4][5].

Dowolne ciało skończone można opisać jako ciało rozkładu wielomianu wyłącznie w zależności od rzędu ciała: ciało skończone o rzędzie będącym potęgą liczby pierwszej jest ciałem rozkładu wielomianu nad ciałem [6]; wynika stąd, że ciała skończone tego samego rzędu są izomorficzne[7][8]. Wychodząc stąd można dowieść istnienia ciał skończonych dowolnego rzędu będącego potęgą liczby pierwszej[9]. Dla dowolnej liczby pierwszej i naturalnej liczby istnieje unormowany wielomian nierozkładalny stopnia należący do [10]. Podciała są rzędu gdzie przy czym istnieje jedno i tylko jedno takie ciało dla każdego [11].

Zbiór pierwiastków wielomianu zawiera wszystkie elementy zatem ciało to jest ciałem rozkładu tego wielomianu rozdzielczego nad ciałem Stąd ciało jest rozszerzeniem Galois – zasadniczą cechą ciał skończonych jest to, iż grupa Galois jest cykliczna i ma kanoniczny generator w postaci endomorfizmu Frobeniusa [12]. Jeśli jest wielomianem nierozkładalnym stopnia i ma pierwiastek w pewnym rozszerzeniu ciała to jego pierwiastki tworzą zbiór złożony z elementów [13].

Powyższe twierdzenia można uogólnić zastępując ciało rzędu wyrażającego się pewną liczbą pierwszą ogólnym ciałem rzędu wykorzystując obserwację, iż dla każdego zachodzi zatem rolę endomorfizmu Frobeniusa dla skończonych rozszerzeń przejmuje odwzorowanie dla skończonych rozszerzeń [14].

Ciała skończone nie są algebraicznie domknięte[15] (dla każdego jednak ciała istnieje ciało algebraicznie domknięte je zawierające). Twierdzenie Wedderburna mówi, że każdy skończony pierścień całkowity (w szczególności: pierścień z dzieleniem) jest przemienny, a więc jest ciałem (skończonym); teza zachodzi również dla pierścieni alternatywnych, czyli przy zrezygnowaniu z założenia łączności pierścienia na rzecz jego alternatywności, o czym mówi twierdzenie Artina-Zorna.

Przykłady[edytuj]

Pierścień tworzy ciało -elementowe; jego elementami są ideały z naturalnie określonymi działaniami (zob. pierścień ilorazowy). Innym ciałem -elementowym jest pierścień o elementach z działaniami arytmetyki modularnej; ciało to ma tę postać, co W gruncie rzeczy wszystkie ciała o elementach mają tę samą strukturę. Pierścień nie jest ciałem, ponieważ ma on (właściwy) dzielnik zera skoro to jest niezerowym elementem nieodwracalnym[16] (a więc przeczy definicji ciała, w którym każdy niezerowy element jest odwracalny). Tabliczki działań dodawania i mnożenia w jedynym (z dokładnością do izomorfizmu) -elementowym ciele (wielomian jest jedynym nierozkładalnym wielomianem drugiego stopnia nad ) przedstawiono niżej:

Odpowiednio - i -elementowe pierścienie i nie są poprawnymi konstrukcjami ciał – pierścień jest ciałem wyłącznie wtedy, gdy jest liczbą pierwszą – niemniej ciała skończone tych rzędów istnieją: ciałami rzędu są np. oraz a przykładami ciał rzędu są np. bądź albo – są to wszystkie ciała postaci dla unormowanego wielomianu dla i czyli rzędu innym ciałem rzędu jest które jest izomorficzne z a nawet wszystkimi innymi ciałami rzędu Wielomian jest nierozkładalny w zatem jest ciałem rzędu

Zbiór niezerowych elementów ciała tworzy grupę (cykliczną) rzędu element nie generuje tej grupy – jego kolejnymi potęgami są jednakże element jest jej generatorem – jego kolejne potęgi to (w pozostałych ciałach rzędu w „modelu wielomianowym”, generatorem grupy multiplikatywnej jest ).

Wielomian jest nierozkładalny w jednym z jego pierwiastków w ciele jest element dwoma pozostałymi są Ponieważ w to (gdyż ), zatem skąd wynika, że pierwiastki w można zapisać jako Element jest jednym z pierwiastków w dwoma pozostałymi są oraz

Element ciała ma wielomian minimalny nad Pozostałymi dwoma pierwiastkami tego wielomianu są nad oraz potęgi tych elementów można zredukować korzystając z tożsamości mianowicie: oraz

Rys historyczny[edytuj]

Ciała o rzędzie wyrażającym się liczbą pierwszą, były przedmiotem badań wielu pionierów teorii liczb, m.in. Pierre'a de Fermata, Leonharda Eulera, Josepha Louisa Lagrange'a, Adriena-Marie Legendre'a, czy Carla Friedricha Gaussa. Pierwszym matematykiem piszącym o innych ciałach skończonych był Évariste Galois, który przedstawił o nich pracę w 1830 roku (ciałami o rzędach niewyrażających się liczbami pierwszymi zajmował się wcześniej Gauss, co odkryto jednak dopiero po jego śmierci w 1855 roku wydając jego prace na ten temat w 1863 roku, lecz przeszły one bez większego echa).

Galois konstruował ciała skończone jako rozszerzenia pojedyncze gdzie jest pierwiastkiem wielomianu nierozkładalnego zmiennej nad ciałem (tzn. należącego do ); jest to równoważne rozpatrywaniu Galois nie pokazał, że w istnieje wielomian nierozkładalny dowolnego stopnia.

W 1893 roku na Międzynarodowym Kongresie Matematycznym w Chicago Eliakim Hastings Moore dowiódł, że każde ciało skończone jest izomorficzne z ciałem postaci twierdzenie opatrzył komentarzem „To interesujący wynik, którego sformułowania nie widziałem nigdzie indziej”[17]. Moore był pierwszą osobą, która użyła angielskiego słowa field (dosł. „pole”) w sensie algebraicznym, choć traktował je jako synonim niemieckiego endlicher Körper (dosł. „ciało skończone”)[18]. Każde skonstruowane ciało postaci nazywał on ciałem Galois, były więc one dla niego konkretnymi modelami wszystkich ciał skończonych. W informatyce wyrażenie Moore'a „ciało Galois” jest synonimem ciała skończonego, a stosowana przez niego notacja (od ang. Galois field) stosowana jest często zamiast

Przypisy

  1. Warstwy modulo są reprezentowane za pomocą reszt gdzie przy czym jest ich Ponieważ jest nierozkładalny, to korzystając z tego samego argumentu, co przy dowodzie, iż jest ciałem dla będącego liczbą pierwszą, pierścień jest ciałem.
  2. Charakterystyka ciała skończonego jest liczbą pierwszą, gdyż jądro homomorfizmu jest niepuste (z uwagi na nieskończony rząd i skończony ) i jest postaci dla pewnej liczby całkowitej zatem zanurza się w jako podpierścień; każdy podpierścień ciała jest dziedziną, zatem musi być liczbą pierwszą, oznaczaną dalej Skoro jest zanurzeniem, to można traktować jako przestrzeń liniową nad skończonego wymiaru (gdyż jest zbiorem skończonym). Każdy element można wtedy zapisać jednoznacznie w bazie nad jako kombinację liniową dla liczba tych kombinacji wynosi
  3. Lemat: Jeśli ciało jest skończone, to jego grupa multiplikatywna jest cykliczna.
    Dowód lematu: Niech oznacza największy rząd elementu w grupie z teorii skończonych grup abelowych wynika, że rząd dowolnego jej elementu dzieli rząd maksymalny, zatem dla dowolnego zachodzi Stąd wszystkie liczby w są pierwiastkami
    Niech liczba pierwiastków wielomianu jest równa co najwyżej stopniowi wielomianu, a ponieważ ma pierwiastków w to Skoro jest rzędem elementu w będącej grupą rzędu to a więc skąd wynika, że w istnieją elementy rzędu co oznacza, iż jest cykliczna.
  4. Niech będzie ciałem skończonym o elementów (z twierdzenia wyżej) i dane będzie zanurzenie ciał Niech będzie generatorem grupy cyklicznej (z powyższego lematu). Ewaluacja wielomianu dla elementu dana wzorem jest homomorfizmem pierścieni. Ponieważ każdy element jest zerem lub potęgą (tzn. oraz dla dowolnego ), to jest epimorfizmem („na”), zatem Skoro jądro jest ideałem maksymalnym w to musi być ono równe dla pewnego unormowanego wielomianu nierozkładalnego należącego do
  5. Twierdzenie to nie zapewnia o istnieniu ciał rzędów wyrażających się za pomocą wszystkich potęg liczb pierwszych; mówi jedynie, iż jeśli istnieje ciało rzędu to jest ono izomorficzne z odpowiedni dowód istnienia przedstawiono dalej.
  6. Niech będzie ciałem rzędu z dowodu twierdzenia o rzędzie ciała skończonego wynika, że zawiera podciało rzędu izomorficzne z jest nim podpierścień generowany przez Dla każdego zachodzi otóż jeśli to gdyż jest grupą multiplikatywną rzędu i wtedy tożsamość wynika z obustronnego pomnożenia równania przez co jest również prawdą w przypadku, gdy Każdy element jest pierwiastkiem zatem jest ciałem rozkładu tego wielomianu nad ciałem
  7. Wynika to wprost z izomorficzności ciał rozkładu ustalonego wielomianu nad
  8. Analogiczne twierdzenie dla skończonych grup lub pierścieni jest fałszywe: tak jak i są rzędu lecz są nieizomorficzne jako grupy addytywne (odpowiednio grupa cykliczna i grupa czwórkowa Kleina) i pierścienie przemienne.
  9. Twierdzenie: Dla dowolnych liczb pierwszej i naturalnej istnieje ciało rzędu
    Dowód: Niech będzie rozszerzeniem ciała nad którym wielomian rozkłada się na czynniki liniowe (tzn. pewnym rozszerzeniem ciała rozkładu tego wielomianu; istnienie tego rodzaju rozszerzenia wynika z ogólnej teorii ciał). Pierwiastki wspomnianego wielomianu tworzą zbiór o elementach, gdyż wielomian jest rozdzielczy: gdyż w zatem i jego pochodna nie mają wspólnych pierwiastków; wielomian ten rozkłada się na czynniki liniowe nad i jest stopnia zatem ma pierwiastków w
    Zbiór tworzy ciało – wynika to wprost z własności endomorfizmu Frobeniusa Mianowicie: zamkniętość ze względu na mnożenie i odwracanie (niezerowych rozwiązań) jest trywialna, z kolei zamkniętość ze względu na dodawanie i branie elementów przeciwnych wynika stąd, iż jest grupą addytywną: skoro w to dla dowolnych elementów zachodzi równość (wyrazy mieszane rozwinięcia dwumianu Newtona mają współczynniki będące wielokrotnościami zatem są równe zeru), co dowodzi addytywności endomorfizmu Frobeniusa, skąd wynika także addytywność jego -tej iteracji Zbiór jest grupą ze względu na dodawanie jako zbiór punktów stałych tej właśnie funkcji addytywnej.
  10. Z powyższego twierdzenia wynika istnienie abstrakcyjnego ciała rzędu a z twierdzenia wyżej musi być ono izomorficzne z ciałem dla pewnego
  11. Niech będzie ciałem spełniającym i niech tak, iż a dzieli Opisanie wyłącznie w zależności od zagwarantuje jedyność podciała tego rzędu w Skoro jest rzędu to dla każdego zachodzi zatem również dla Wielomian ma co najwyżej pierwiastków w a ponieważ jest zbiorem różnych pierwiastków, jest (zależna tylko od liczby elementów) postać tego zbioru dowodzi jego jednoznaczności. Przechodząc do dowodu, iż dla każdego istnieje podciało ciała rzędu zbiór jest ciałem na mocy tego samego argumentu, co dla zbioru w dowodzie twierdzenia o istnieniu; wykazanie, iż ma on elementów polega na wskazaniu niezerowych elementów w spełniających Otóż niech będzie generatorem czyli ma rząd ponieważ tj. dzieli to jest rzędu Wszystkie potęgi dla spełniają
  12. Dla dowolnego zachodzi zatem jest zbiorem punktów stałych funkcji funkcja ta jest homomorfizmem ciał i jest różnowartościowa (wszystkie homomorfizmy ciał są monomorfizmami), a także „na”, jako że jest skończone (innymi słowy endomorfizm Frobeniusa jest automorfizmem). Stąd Rząd tej grupy Galois wynosi wystarczy wykazać, że jest rzędu co oznaczać będzie, iż jest generatorem tej grupy. Niech dla będzie Wówczas jeśli jest elementem neutralnym tej grupy, to dla wszystkich Wielomian ma co najwyżej pierwiastków, zatem czyli Wynika stąd, iż ma w rząd równy co najmniej z drugiej strony grupa ta ma rząd co najwyżej zatem musi być tamże rzędu
  13. Każde skończone ciało rzędu wyrażającego się potęgą liczby pierwszej jest rozszerzeniem Galois nad W szczególności dotyczy to ciała a pozostałe pierwiastki można otrzymać z działając na ten element grupą Ponieważ grupa ta jest generowana przez endomorfizm Frobeniusa, to pierwiastki należą do zbioru Zbiór ten jest skończony, gdyż co wynika stąd, iż jest rzędu Wielomian jest rozdzielczy, ponieważ jego pierwiastki należą do rozszerzenia Galois ciała a skoro ma on stopień to parami różne elementy tworzą zbiór jego pierwiastków.
  14. Twierdzenie: Dla dowolnej liczby naturalnej istnieje unormowany wielomian nierozkładalny stopnia należący do
    Twierdzenie: Między a istnieje jedno i tylko jedno ciało rzędu dla każdego jest ono postaci
    Twierdzenie: Dla dowolnej liczby naturalnej ciało jest rozszerzeniem Galois, a jego grupa Galois jest cykliczna, przy czym jej generatorem jest przekształcenie
    Twierdzenie: Jeśli jest wielomianem nierozkładalnym stopnia i ma pierwiastek w pewnym rozszerzeniu ciała to zbiór elementów zawiera wszystkie jego pierwiastki.
  15. Jeśli jest ciałem skończonym, to wartość wielomianu dla dowolnego elementu jest równa (jego funkcja wielomianowa jest stale równa ), skąd wielomian ten nie ma pierwiastków w
  16. Jeśli (w ciele ) element byłby elementem odwrotnym do to (z definicji) jednakże wtedy czyli nie może mieć elementu odwrotnego.
  17. (Moore, s. 211)
  18. (Moore, s. 208)

Bibliografia[edytuj]

  • J. Browkin: Teoria ciał. Wyd. 1. T. 49. Warszawa: PWN, 1977, seria: Biblioteka Matematyczna.
  • Rudolf Lidl, Harald Niederreiter, „Finite Fields”, Addison-Wesley 1983.
  • E. H. Moore: A Doubly-Infnite System of Simple Groups, ss. 208–242 w „Mathematical papers read at the International Mathematical Congress held in connection with the World's Columbian Exposition, Chicago, 1893”; Macmillan & Co., Nowy Jork, 1896.
  • Andrzej Chmielowiec, Ciała charakterystyki 2 – aspekty implementacyjne, 2007