Körper mit 4 elementen konstruieren

15.02.2011, 10:51

hnky

Körper mit 4 elementen konstruieren

hallo,

ich habe zunächst eine allgemeine frage zur konstruktion eines körpers mit n elementen als restklassenring von $\begin{eqnarray*} \mathbb F_p[x] \end{eqnarray*}$ .

habe ich es richtig verstanden, dass ich dazu immer ein polynom vom grad p benötige, das über dem betrachteten körper, also $\begin{eqnarray*} \mathbb F_p[x] \end{eqnarray*}$ , irreduzibel ist?

und um dann die elemente des gesuchten körpers zu finden, nehme ich die reste modulo dem irreduziblen polynom?

ich möchte dazu folgende aufgabe lösen:

Zitat:

Es sei $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ der körper mit 2 elementen.
1) Konstruiere den körper mit 4 elementen als restklassenring von $\begin{eqnarray*} \mathbb F_2[x] \end{eqnarray*}$ .
2) Konstruiere den körper mit 4 elementen als teilmenge von $\begin{eqnarray*} \mathbb F_2^{2 \times 2} \end{eqnarray*}$

den ersten teil der aufgabe habe ich mit meinen obigen vermutungen so angehen wollen:

ich suche mir also zunächst ein polynom vom grad 2, das über $\begin{eqnarray*} \mathbb F_2 \end{eqnarray*}$ irreduzibel ist. bei polynomen von grad 2 ist ein hinreichendes kriterium für die irreduzibilität, dass es keine nullstellen besitzt.
$\begin{eqnarray*} f=x^2+x+1 \end{eqnarray*}$ wäre ein solches polynom.

dann ist $\begin{eqnarray*} \mathbb F_2[x] \slash f \mathbb F_2[x] \end{eqnarray*}$ ein körper und die elemente wären dann die reste modulo f.

das 0 element wäre dann $\begin{eqnarray*} (x^2+x+1)+f \mathbb F_2[x] \end{eqnarray*}$
das 1 element wäre dann $\begin{eqnarray*} (x^2+x)+f \mathbb F_2[x] \end{eqnarray*}$
das x element wäre dann $\begin{eqnarray*} (x^2+1)+f \mathbb F_2[x] \end{eqnarray*}$
das x+1 element wäre dann $\begin{eqnarray*} x^2 + f \mathbb F_2[x] \end{eqnarray*}$

jetzt bin ich mir nicht sicher, ob bei solchen aufgabenstellungen auch immer eine verknüpfungstabelle verlangt ist. ich habe sie mal gemacht:

$\begin{eqnarray*} \begin{pmatrix} + & 0 & 1 & x & x+1 \\ 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1\\ x+1 & x+1 & x & 1 & 0\end{pmatrix} \end{eqnarray*}$

und

$\begin{eqnarray*} \begin{pmatrix} \cdot & 0 & 1 & x & x+1 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1\\ x+1 & 0 & x+1 & 1 & x\end{pmatrix} \end{eqnarray*}$

fehlt noch etwas, ist mein gesuchter körper damit bereits konstruiert?

bei teil 2 der aufgabe weiß ich gar nicht, wie ich anfangen soll.

ich befinde mich im raum der $\begin{eqnarray*} 2 \times 2 \end{eqnarray*}$ matrizen, also matrizen der form $\begin{eqnarray*} \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{eqnarray*}$ mit $\begin{eqnarray*} a,b,c,d \in \mathbb F_2 \end{eqnarray*}$ .

das ist aber leider auch schon alles, was mir dazu einfällt.

kann mir jemand hierbei auf die sprünge helfen?

vielen dank schonmal im voraus.

15.02.2011, 18:19

Leopold

Auf diesen Beitrag antworten »

Die Konstruktion mit den Polynomen modulo $\begin{eqnarray*} f \end{eqnarray*}$ stimmt. Ich verstehe nur nicht, warum du die Elemente am Anfang deines Beitrags so kompliziert schreibst (Nullelement, Einselement usw.), in den Verknüpfungstabelle nimmst du dann ja auch die kanonische Variante.
Und eigentlich brauchst du keine Verknüpfungstafeln, denn es ist ja allgemein gezeigt, daß diese Konstruktion immer den gesuchten Körper liefert. Natürlich ist es nicht von Schaden, wenn man sich in einem einfachen Fall wie hier die Verknüpfungstafeln hinschreibt, um "ein Gefühl für die Sache" zu bekommen.

Bei der Matrizenkonstruktion kenne ich keine allgemeine Lösung. Im Konkreten kannst du aber so vorgehen:

Für die multiplikative Gruppe $\begin{eqnarray*} K^{*} \end{eqnarray*}$ des Körpers $\begin{eqnarray*} K \end{eqnarray*}$ brauchst du drei Matrizen. Jetzt ist aber jede Gruppe der Ordnung 3 zyklisch. Neben der Einheitsmatrix $\begin{eqnarray*} e \end{eqnarray*}$ für das Einselement brauchst du also eine weitere Matrix $\begin{eqnarray*} \vartheta \end{eqnarray*}$ der Ordnung 3. Die allgemeine lineare Gruppe hat $\begin{eqnarray*} (4-1) \cdot (4-2) = 6 \end{eqnarray*}$ Elemente (siehe etwa hier), also muß es solch ein Element $\begin{eqnarray*} \vartheta \end{eqnarray*}$ geben. Einfach die sechs möglichen Matrizen mit Determinante 1 durchprobieren. Somit hast du den Ansatz

$\begin{eqnarray*} K^{*} = \left\{ e , \vartheta , \vartheta^2 \right\} \end{eqnarray*}$

Jetzt nimmst du noch die Nullmatrix $\begin{eqnarray*} 0 \end{eqnarray*}$ dazu, also

$\begin{eqnarray*} K = \left\{ 0 , e , \vartheta , \vartheta^2 \right\} \end{eqnarray*}$

Die Sache mit der Multiplikation ist nach Konstruktion klar. Daß aber diese Matrizen unter der Addition eine Gruppe bilden, ist nicht selbstverständlich. Hier mußt du also tatsächlich die Verknüpfungstafel aufstellen und hoffen, daß du beim Addieren nicht aus $\begin{eqnarray*} K \end{eqnarray*}$ herausfällst.

Möglicherweise gibt es auch eine allgemeine Konstruktion, wie man gewisse Körper in Matrizenringen findet. Vielleicht weiß jemand anders mehr darüber.

15.02.2011, 18:49

Manus

Auf diesen Beitrag antworten »

Zur allgemeinen Konstruktion über dem Matrixring:

Wenn man das Polynom (aus dem ersten Aufgabenteil) gegeben hat und man das ganze über einem endlichen Körper konstruieren möchte, so kann man einfach die Begleitmatrix zu diesem Polynom nehmen. Die davon erzeugte Teilalgebra des Matrixrings ist per Konstruktion automatisch isomorph zum gesuchten Körper.

15.02.2011, 20:31

hnky

Auf diesen Beitrag antworten »

danke euch beiden für die tollen tips smile

teil 1 der aufgabe ist mir dann klar.

die begleitmatrix zu $\begin{eqnarray*} x^2+x+1 \end{eqnarray*}$ ist $\begin{eqnarray*} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} \end{eqnarray*}$ .

wenn die von dieser begleitmatrix erzeugte teilalgebra per konstruktion automatisch schon isomorph zu $\begin{eqnarray*} \mathbb F_2^{2 \times 2} \end{eqnarray*}$ ist, dann wäre die aufgabe doch direkt schon gelöst, oder?

zu Leopold:

danke für die tolle erklärung, jetzt wird mir das ganze deutlich klarer.

ich habe es mal nach deiner anleitung versucht, und bin tatsächlich bei der addition nicht aus dem körper herausgeflogen.

15.02.2011, 23:23

Manus

Auf diesen Beitrag antworten »

Falls dir der Homomorphiesatz was sagt, hier vielleicht eine kurze Begründung, wieso das mit der Begleitmatrix funktioniert.

Wir müssen nur zeigen, dass die von der Begleitmatrix $\begin{eqnarray*} A \end{eqnarray*}$ erzeugte Teilalgebra isomorph ist zu unserem Faktorring. Dazu betrachten wir die Abbildung:

$\begin{eqnarray*} \phi: K[X] \rightarrow K[A], p(X) \mapsto p(A) \end{eqnarray*}$ (also ich nehme ein Polynom und setze einfach nur A ein). Dann ist $\begin{eqnarray*} \phi \end{eqnarray*}$ offensichtlich surjektiv (ich treffe ja den Erzeuger mit $\begin{eqnarray*} \phi(X) \end{eqnarray*}$ ) und der Kern besteht aus allen Polynomen, die A annullieren. Wenn aber nun $\begin{eqnarray*} \mu \end{eqnarray*}$ das Minimalpolynom von A ist und $\begin{eqnarray*} p \end{eqnarray*}$ ein weiteres Element des Kerns, so wissen wir bereits, dass $\begin{eqnarray*} \mu \end{eqnarray*}$ p teilt. Insbesondere entspricht der Kern von $\begin{eqnarray*} \phi \end{eqnarray*}$ gerade dem von $\begin{eqnarray*} \mu \end{eqnarray*}$ erzeugten Hauptideal.

Dann gilt aber mit dem Homomorphiesatz: $\begin{eqnarray*} Bild(\phi)=K[A] \simeq K[X]/(\mu) \end{eqnarray*}$

Und da das Minimalpolynom gerade das Polynom war, welches wir ohnehin herausfaktorisieren wollten, folgt die Behauptung.

Was wir also letztlich in beiden Fällen tun, ist ein einzelnes Element zum Körper hinzuzufügen, dass gewisse Relationen erfüllt (nämlich genau sein Minimalpolynom zu erfüllen) und dann den neuen Körper zu betrachten der erzeugt wird. Die Aufgabe zeigt also vor allem, dass es letztlich wurscht ist, in welcher Art und Weise man das Element repräsentiert.

16.02.2011, 13:00

hnky

Auf diesen Beitrag antworten »

ich habe mir den homomorphiesatz mal angeschaut, und verstehe jetzt auch deine erklärung.

vielen dank dafür smile

Ich denke, ich habe es nun auch verstanden, und somit ist die aufgabe auch gelöst smile

16.02.2011, 16:02

Leopold

Auf diesen Beitrag antworten »

Wobei jetzt noch der Nachweis fehlt, daß die Begleitmatrix gerade ihr Polynom als Minimalpolynom besitzt. Das ist wohl eine hübsche Determinantenrechnung.

16.02.2011, 16:14

Manus

Auf diesen Beitrag antworten »

Nicht wirklich. Es gibt einen hübschen Algorithmus für das Minimalpolynom, in welchem man nicht die Matrix selbst potenziert, sondern sie einfach wiederholt auf einen beliebigen Ausgangsvektor anwendet (wir nutzen also aus, dass eine lineare Abhänigigkeit der Matrizenpotenzen eine lineare Abhängigkeit dieser Vektoren mit gleicher Relation impliziert).

Wählt man hier den ersten Einheitsvektor, so erhält man nach n-maligem Anwenden (wenn wir die Dimension mal n nennen) genau die letzte Spalte und damit genau die durch das Minimalpolynom beschriebene Relation (so wird die letzte Spalte ja gerade gewählt).

16.02.2011, 17:24

Leopold

Auf diesen Beitrag antworten »

Interessant, was du da bringst. Freude

Ich habe in der Matrix $\begin{eqnarray*} B-xE \end{eqnarray*}$ (wo $\begin{eqnarray*} B \end{eqnarray*}$ die Begleitmatrix und $\begin{eqnarray*} E \end{eqnarray*}$ die Einheitsmatrix bezeichnen mögen) durch Nachbarvertauschungen von Zeilen die erste Zeile zur letzten gemacht, womit man schon fast eine obere Dreiecksmatrix bekommt. Jetzt muß man nur noch das $\begin{eqnarray*} x \end{eqnarray*}$ -fache der ersten Zeile, das $\begin{eqnarray*} x^2 \end{eqnarray*}$ -fache der zweiten Zeile usw. zur letzten Zeile addieren.

16.02.2011, 18:26

Manus

Auf diesen Beitrag antworten »

Das Problem bei der Methode ist, dass sie einem die Behauptung nur für den Fall liefert, dass das Polynom irreduzibel ist, da man sich ja sonst nicht sicher sein kann, dass char. und Mininmalpolynom übereinstimmen.

Ist hier natürlich herzlich egal.

Neue Frage »

Antworten »

Körper mit 4 elementen konstruieren

Verwandte Themen