Mitternachtsformel über endlichen Körpern

Neue Frage »

25.03.2020, 13:50	Fabiano	Auf diesen Beitrag antworten »
Mitternachtsformel über endlichen Körpern Meine Frage: Hallo, gilt die Mitternachtsformel auch über endlichen Körpern? Meine Ideen: D.h. wenn x keine reelle Zahl, sondern zum Beispiel ein Element des Körpers F_p ist. Gilt dann immer noch die Mitternachtsformel?
25.03.2020, 14:21	Elvis	Auf diesen Beitrag antworten »
Nein, $\begin{eqnarray} x^2=2 \end{eqnarray}$ hat keine Nullstelle in $\begin{eqnarray} \mathbb F_3 \end{eqnarray}$ .
25.03.2020, 15:52	Iorek	Auf diesen Beitrag antworten »
@Elvis, das würde ich zu einem "Jein" entschärfen bzw. erweitern. Solange im betrachteten Körper $\begin{eqnarray} 2\neq 0 \end{eqnarray}$ gilt, hindert einen ja niemand daran die Diskriminante $\begin{eqnarray} D=\frac{p}{2}-q=p\cdot 2^{-1}-q \end{eqnarray}$ zu bilden (ich gehe dreisterweise von der $\begin{eqnarray} pq \end{eqnarray}$ -Formel, also einem normierten Polynom zweiten Grades aus). Ist nun wie in deinem Fall $\begin{eqnarray} D \end{eqnarray}$ kein Quadrat in $\begin{eqnarray} K \end{eqnarray}$ , so gibt es keine Nullstelle. Im anderen Fall lassen sich die Lösungen mit Hilfe der $\begin{eqnarray} pq \end{eqnarray}$ -Formel ja berechnen mittels $\begin{eqnarray} x=-\frac{p}{2}\pm r \end{eqnarray}$ wobei $\begin{eqnarray} r^2=D \end{eqnarray}$ ist. Es fällt halt die "einfache Aussage" zur Existenz über das Vorzeichen von $\begin{eqnarray} D \end{eqnarray}$ weg und auch die Berechnung des $\begin{eqnarray} r \end{eqnarray}$ lässt sich nicht "wie gewohnt" durch Wurzelziehen bestimmen, anwenden kann man die Formel aber schon.
25.03.2020, 17:52	Elvis	Auf diesen Beitrag antworten »
Die Ideen von Fabiano scheinen nicht ganz ausgereift, deshalb fällt mir eine Antwort nicht leicht. $\begin{eqnarray} x^2+1=0 \end{eqnarray}$ hat ja schon in rationalen und in reellen Zahlen keine Lösung. Da hilft die Mitternachtsformel auch nichts. Vielleicht kann Fabiano die Frage umformulieren oder präzisieren oder ein Beispiel geben oder einen Sachzusammenhang, in dem die Frage steht. Dann können wir bestimmt ganz viele gute Antworten suchen und vielleicht sogar finden.
25.03.2020, 22:17	Fabiano	Auf diesen Beitrag antworten »
Ok, ich sehe ein, dass es Probleme geben kann. Nehmen wir den folgenden Fall: $\begin{eqnarray} x^2-2ax+1=0 \end{eqnarray}$ . Wenn x bzw. a jetzt aus $\begin{eqnarray} \mathbb F_{p} \end{eqnarray}$ sind (mit p>2), gilt dann die Mitternachtsformel? Wie ist es, wenn x und a z.B. in $\begin{eqnarray} \mathbb F_{p^2} \end{eqnarray}$ sind?
26.03.2020, 08:41	Leopold	Auf diesen Beitrag antworten »
In einem Körper der Charakteristik $\begin{align} p>2 \end{align}$ gilt die Mitternachtsformel immer, in dem Sinn, daß die in der Formel auftretende Wurzel existiert, oder sagen wir es so: daß die Diskriminante ein Quadrat ist. In diesem Sinn gilt die Formel überhaupt in jedem Körper, in dem man durch 2 dividieren kann, zum Beispiel ja auch in $\begin{align} \mathbb{Q} \end{align}$ . Ich mache ein Beispiel. Sei $\begin{align} \mathbb{Z}_5 \end{align}$ der Körper der ganzen Zahlen modulo 5. Dessen Elemente schreibe ich wie ganze Zahlen, indem ich Vertreter derselben Restklasse identifiziere. Das Polynom $\begin{align} x^2 + 2 \end{align}$ ist über $\begin{align} \mathbb{Z}_5 \end{align}$ nullstellenfrei, also irreduzibel. Wir adjungieren eine symbolische Wurzel $\begin{align} \vartheta \end{align}$ dieses Polynoms und bekommen einen Körper $\begin{align} K = \mathbb{Z}_5( \vartheta ) \end{align}$ mit $\begin{align} 5^2 = 25 \end{align}$ Elementen. Die Elemente von $\begin{align} K \end{align}$ sind von der Form $\begin{align} c + d \vartheta \end{align}$ mit $\begin{align} c,d \in \mathbb{Z}_5 \end{align}$ . Man rechnet mit ihnen wie gewohnt unter Beachtung von $\begin{align} \vartheta^2 = -2 \end{align}$ . Jetzt nehme ich über $\begin{align} K \end{align}$ einmal die quadratische Gleichung $\begin{align} 2x^2 + \vartheta x + 2 - 2 \vartheta = 0 \end{align}$ Die Diskriminante der abc-Formel ist $\begin{align} D = \vartheta^2 - 4 \cdot 2 \cdot \left( 2 - 2 \vartheta \right) = -2 - 4 \cdot 2 \cdot 2 \cdot \left( 1 - \vartheta \right) = -2 - \left( 1 - \vartheta \right) = 2 + \vartheta \end{align}$ $\begin{align} D \end{align}$ ist ein Quadrat, wie $\begin{align} \left( 2 - \vartheta \right)^2 = 4 - 4 \vartheta + \vartheta^2 = 4 + \vartheta - 2 = 2 + \vartheta \end{align}$ zeigt. Nach der Lösungsformel gilt daher $\begin{align} x = \frac{-b \pm \sqrt{D}}{2a} = \frac{- \vartheta \pm \left( 2 - \vartheta \right)}{2 \cdot 2} = - \left( - \vartheta \pm \left( 2 - \vartheta \right) \right) = \vartheta \mp \left( 2 - \vartheta \right) \end{align}$ Man erhält die beiden Lösungen $\begin{align} x = \vartheta + \left( 2 - \vartheta \right) = 2 \end{align}$ oder $\begin{align} x = \vartheta - \left( 2 - \vartheta \right) = -2 + 2 \vartheta \end{align}$ Und die Probe zeigt, daß das tatsächlich Lösungen sind.
Anzeige

26.03.2020, 19:07	Elvis	Auf diesen Beitrag antworten »
Das ist ein sehr schönes und anregendes Beispiel, quasi direkt aus dem Leben gegriffen. Deshalb habe ich einen halben Tag lang gerechnet und mir überlegt, welche Diskriminanten $\begin{eqnarray} a^2-4b\equiv a^2+b\mod 5 \end{eqnarray}$ der Polynome $\begin{eqnarray} x^2+ax+b\in\mathbb F_5[x] \end{eqnarray}$ Quadrate sind und welche nicht und welche dieser 625 Polynome dazu gehören. Für die quadratischen Diskriminanten liefert die Mitternachtsformel die Nullstellen in diesem $\begin{eqnarray} \mathbb F_5(\theta)\cong \mathbb F_{25} \end{eqnarray}$ mit $\begin{eqnarray} \theta^2=-2\equiv 3\mod 5 \end{eqnarray}$ (Beispiel $\begin{eqnarray} x^2+3\theta x+4+2\theta \end{eqnarray}$ ). Für die nichtquadratischen Diskriminanten adjungieren wir die Wurzel aus der Diskriminante und finden mit der Mitternachtsformel die Nullstellen in $\begin{eqnarray} \mathbb F_5(\theta,\sqrt D)\cong \mathbb F_{25^2}\cong \mathbb F_{625} \end{eqnarray}$ (Beispiel $\begin{eqnarray} x^2+3\theta x+2+3\theta \end{eqnarray}$ ). Nun frage ich mich (und euch), ob diese Zerlegung der Menge quadratischer Polynome in solche mit und solche ohne quadratische Diskriminante davon abhängt, wie man den $\begin{eqnarray} \mathbb F_{25} \end{eqnarray}$ konstruiert. Man könnte ja statt $\begin{eqnarray} \theta ^2=3 \end{eqnarray}$ auch ein anderes quadratisches Element zu $\begin{eqnarray} \mathbb F_5 \end{eqnarray}$ adjungieren. Alle $\begin{eqnarray} \mathbb F_{25} \end{eqnarray}$ sind isomorph, beantwortet das schon meine Frage, oder muss ich noch 3 Tage lang weiter rechnen ?
26.03.2020, 21:18	Leopold	Auf diesen Beitrag antworten »
Ehrlich gesagt, verstehe ich nicht so richtig, was du sagen willst. Auch wird mir nicht klar, in welchem Körper du gerade arbeitest. Gleich am Anfang sprichst du von $\begin{align} \mathbb{F}_5[x] \end{align}$ , aber von 625 Polynomen $\begin{align} x^2 + ax + b \in \mathbb{F}_5[x] \end{align}$ . Das sind meiner Ansicht nach nur 25 Stück. Meinst du da $\begin{align} \mathbb{F}_{25}[x] \end{align}$ ? Auch später kann ich nicht folgen. Du sagst, $\begin{align} x^2 + 3 \vartheta x + 4 + 2 \vartheta \end{align}$ habe eine quadratische Diskriminante. Einverstanden (Nullstellen sind $\begin{align} 1 \end{align}$ und $\begin{align} -1 + 2 \vartheta \end{align}$ ). Dann sagst du, $\begin{align} x^2 + 3 \vartheta x + 2 + 3 \vartheta \end{align}$ habe eine nichtquadratische Diskriminante. Ich habe hier $\begin{align} D = -1 - 2 \vartheta = \left( 1 - \vartheta \right)^2 \end{align}$ und komme auf die Nullstellen $\begin{align} -2 - 2 \vartheta \end{align}$ und $\begin{align} 2 - \vartheta \end{align}$ . Ich hab's mehrmals nachgerechnet. Sollte ich immer denselben Fehler gemacht haben?
26.03.2020, 22:30	Fabiano	Auf diesen Beitrag antworten »
Danke erstmal Leopold für das Beispiel, das ich gut nachvollziehen konnte. Also das Beispiel von Elvis $\begin{eqnarray} x^2+3\theta x+2+3 \theta \end{eqnarray}$ habe ich auch nachgerechnet, und ich komme auch auf die Diskriminante $\begin{eqnarray} 4-2 \theta \end{eqnarray}$ . Ich hätte es jetzt so verstanden, dass, wenn die Diskriminante ein Quadrat in $\begin{eqnarray} \mathbb F_5 \end{eqnarray}$ ist, man mit der Mitternachtsformel auch die Nullstellen in $\begin{eqnarray} \mathbb F_5 \end{eqnarray}$ bekommt. Und andernfalls liegen die Nullstellen in $\begin{eqnarray} \mathbb F_{25} \end{eqnarray}$ . Liege ich da richtig? Denn bei dem was Elvis geschrieben hat kann ich leider nicht ganz folgen.
26.03.2020, 23:52	Leopold	Auf diesen Beitrag antworten »
Das hat nichts mit dem speziellen Körper zu tun. Wenn $\begin{align} K \end{align}$ ein Körper einer Charakteristik $\begin{align} \neq 2 \end{align}$ ist, gilt immer: Ist die Diskriminante einer quadratischen Gleichung über $\begin{align} K \end{align}$ ein Quadrat $\begin{align} \neq 0 \end{align}$ , so hat die quadratische Gleichung zwei Lösungen, ist die Diskriminante 0, eine Lösung, und ist die Diskriminante kein Quadrat, keine Lösung, jeweils in $\begin{align} K \end{align}$ . Daß unlösbare algebraische Gleichungen durch Adjunktionen in Oberkörpern Lösungen besitzen, ist ein anderes Thema. Ein paar Beispiele mit der abc-Formel. Beispiel 1 $\begin{align} x^2 - \frac{1}{2} x - \frac{7}{144} = 0 \ \ \text{über} \ \mathbb{Q} \end{align}$ $\begin{align} D = \frac{4}{9} = \left( \frac{2}{3} \right)^2 \end{align}$ Diese quadratische Gleichunge besitzt zwei rationale Lösungen. Beispiel 2 $\begin{align} 2x^2 + x - \frac{1}{2} = 0 \ \ \text{über} \ \mathbb{Q} \end{align}$ $\begin{align} D = 5 \end{align}$ 5 ist kein Quadrat in $\begin{align} \mathbb{Q} \end{align}$ . Diese Gleichung ist über $\begin{align} \mathbb{Q} \end{align}$ unlösbar. Beispiel 3 $\begin{align} 2x^2 + x - \frac{1}{2} = 0 \ \ \text{über} \ \mathbb{R} \end{align}$ $\begin{align} D = 5 = \left( \sqrt{5} \right)^2 \end{align}$ Diese Gleichung besitzt zwei reelle Lösungen. Beispiel 4 $\begin{align} 2x^2 + x + \frac{1}{2} = 0 \ \ \text{über} \ \mathbb{R} \end{align}$ $\begin{align} D = -3 \end{align}$ -3 ist kein Quadrat in $\begin{align} \mathbb{R} \end{align}$ . Diese Gleichung ist über $\begin{align} \mathbb{R} \end{align}$ unlösbar. Beispiel 5 $\begin{align} x^2 + x + 75 = 0 \ \ \text{über} \ \mathbb{Z}_{101} \end{align}$ $\begin{align} D = 4 = 2^2 \end{align}$ Diese Gleichung besitzt zwei Lösungen in $\begin{align} \mathbb{Z}_{101} \end{align}$ . Beispiel 6 $\begin{align} x^2 + 2 = 0 \ \ \text{über} \ \mathbb{Z}_5 \end{align}$ $\begin{align} D = 2 \end{align}$ 2 ist kein Quadrat in $\begin{align} \mathbb{Z}_5 \end{align}$ , also ist die Gleichung über $\begin{align} \mathbb{Z}_5 \end{align}$ unlösbar. Beispiel 7 $\begin{align} x^2 + 2 = 0 \ \ \text{über} \ \mathbb{Z}_5(\vartheta) \end{align}$ mit $\begin{align} \vartheta^2 = -2 \end{align}$ $\begin{align} D = 2 = \left( 2 \vartheta \right)^2 \end{align}$ Diese Gleichung besitzt zwei Lösungen in $\begin{align} \mathbb{Z}_5(\vartheta) \end{align}$ , nämlich $\begin{align} x = \pm \vartheta \end{align}$ .
27.03.2020, 11:44	Elvis	Auf diesen Beitrag antworten »
Leider habe ich mich verrechnet und vor lauter Begeisterung habe ich mich auch fehlerhaft ausgedrückt. Was ich eigentlich untersuchen wollte ist das Verhalten von quadratischen Polynomen über $\begin{eqnarray} \mathbb F_5 \end{eqnarray}$ , und dabei gibt es 10 irreduzible normierte Polynome. Dies gibt Anlass zu 10 unterschiedlichen, wenn auch isomorphen endlichen Körpern mit 25 Elementen. Wenn ich über diesen Körpern wieder die Mitternachtsformel auf alle normierten quadratischen Polynome anwenden möchte, gibt es ja auch wieder die beiden Möglichkeiten, dass die Diskriminante quadratisch oder nichtquadratisch ist. Im ersten Falle liegen dann 2 Nullstellen in dem jeweiligen $\begin{eqnarray} \mathbb F_{25} \end{eqnarray}$ , im zweiten Falle muss ich dann noch einmal die Wurzel aus der Diskriminante adjungieren. Ich komme da sehr schnell an die Grenzen meiner Rechenfähigkeiten (was euch ja schon aufgefallen ist), und ich frage mich, ob die Theorie der endlichen Körper die unterschiedlichen Körpertürme so zusammenführt, dass man unabhängig vom Erzeugungsprozess der Körpererweiterungen noch Aussagen über die Gesamtheit der Polynome und ihre Nullstellen machen kann. Vielleicht hilft es, wenn ich mir die Situation zunächst in einem algebraischen Abschluß von $\begin{eqnarray} \mathbb F_5 \end{eqnarray}$ ansehe, das ist aber wohl auch nicht sehr konkret, weil der auch nur bis auf Isomorphie festliegt. Es tut mir leid, wenn ich mehr verwirrt als geklärt habe, und ich werde mich ins stille Kämmerlein zurückziehen und so lange rechnen, bis ich etwas weiß oder keine Lust mehr dazu habe.
28.03.2020, 18:16	Elvis	Auf diesen Beitrag antworten »
Heureka, ich hab's ! Alle endlichen Körper mit $\begin{eqnarray} q=p^n \end{eqnarray}$ Elementen, $\begin{eqnarray} p \end{eqnarray}$ Primzahl, $\begin{eqnarray} n \end{eqnarray}$ natürliche Zahl, sind isomorph. Das heißt, man kann sie algebraisch nicht unterscheiden. Wenn man ein irreduzibles Polynom $\begin{eqnarray} f(x)\in \mathbb F_q[x] \end{eqnarray}$ mit Grad $\begin{eqnarray} d \end{eqnarray}$ hat, so kann man eine Nullstelle $\begin{eqnarray} \alpha \end{eqnarray}$ mit $\begin{eqnarray} f(\alpha)=0 \end{eqnarray}$ adjungieren, d.h. $\begin{eqnarray} \mathbb F_q(\alpha)=\mathbb F_q[x]/(f(x))=\mathbb F_{q^d} \end{eqnarray}$ . Für jedes irreduzible Polynom $\begin{eqnarray} g(x)\in \mathbb F_q[x] \end{eqnarray}$ mit Grad $\begin{eqnarray} d \end{eqnarray}$ ist $\begin{eqnarray} \mathbb F_q[x]/(g(x))=\mathbb F_{q^d} \end{eqnarray}$ . Also ist es völlig egal, welches irreduzible Polynom vom Grad $\begin{eqnarray} d \end{eqnarray}$ benutzt wird, um die Körpererweiterung zu erzeugen. Folgerung: Die Körpererweiterung $\begin{eqnarray} \mathbb F_{q^d}/\mathbb F_q \end{eqnarray}$ enthält alle Nullstellen aller Polynome aus $\begin{eqnarray} \mathbb F_q[x] \end{eqnarray}$ vom Grad $\begin{eqnarray} d \end{eqnarray}$ . Speziell für quadratische Polynome über endlichen Körpern enthält jede quadratische Erweiterung alle Quadratwurzeln aller Elemente des Grundkörpers. Das ist ganz anders als im Fall der quadratischen Zahlkörper, wo jede quadratische Erweiterung die Form $\begin{eqnarray} \mathbb Q(\sqrt D)/\mathbb Q \end{eqnarray}$ mit quadratfreiem $\begin{eqnarray} D\in\mathbb Z\backslash \{0,1\} \end{eqnarray}$ hat. Diese Körper sind für verschiedene $\begin{eqnarray} D \end{eqnarray}$ nicht isomorph.
28.03.2020, 20:43	Leopold	Auf diesen Beitrag antworten »
Ich habe das mal konkret bei meinem Beispiel angeschaut. Die Tabelle zeigt alle über $\begin{align} K= \mathbb{Z}_5 \end{align}$ irreduziblen quadratischen Polynome mit ihren Nullstellen in $\begin{align} L = \mathbb{Z}_5(\vartheta) \end{align}$ , wobei $\begin{align} \vartheta^2 = 3 \end{align}$ gilt. [attach]50870[/attach] Es gibt $\begin{align} k=10 \end{align}$ normierte irreduzible Polynome mit je 2 Nullstellen, das sind $\begin{align} 2k = 20 \end{align}$ Elemente von $\begin{align} L \end{align}$ (keine Doppelzählungen). Dazu kommen noch die Elemente von $\begin{align} K = \mathbb{Z}_p \end{align}$ mit $\begin{align} p=5 \end{align}$ . Und das geht auf: $\begin{align} 2k+p = p^2 \end{align}$ Nach $\begin{align} k \end{align}$ aufgelöst: $\begin{align} k = \frac{1}{2} p(p-1) \end{align}$ Das müßte ja auch für andere $\begin{align} p \end{align}$ gelten (Doppelzählungen möglich? Idee: Satz von Vieta) und hieße zum Beispiel: In $\begin{align} \mathbb{Z}_{101} \end{align}$ gibt es $\begin{align} k = \frac{1}{2} \cdot 100 \cdot 101 = 5050 \end{align}$ (Carl Friedrich läßt grüßen!) normierte irreduzible quadratische Polynome, womit 5151 normierte quadratische Polynome reduzibel wären. Ich habe mir noch nie überlegt, wie viele normierte irreduzible Polynome zweiten Grades es modulo $\begin{align} p \end{align}$ eigentlich gibt. Kann man diese Formel irgendwie anders herleiten? Und stimmt sie überhaupt? Gerade will ich das abschicken - da fällt mir ein: Da oben schreibe ich noch Vieta, und der macht es doch! Ich betrachte nur normierte quadratische Polynome über $\begin{align} \mathbb{Z}_p \end{align}$ und gehe einmal von der andern Seite heran. Reduzible kann man faktorisieren: $\begin{align} (x-a)(x-b) \end{align}$ . Wegen des Kommutativgesetzes kommt es auf die Reihenfolge nicht an. Betrachten wir zuerst den Fall $\begin{align} a=b \end{align}$ . Davon gibt es $\begin{align} {p \choose 1} \end{align}$ Stück. Dann den Fall $\begin{align} a \neq b \end{align}$ . Davon gibt es $\begin{align} {p \choose 2} \end{align}$ Stück. Zusammen sind das $\begin{align} {p \choose 1} + {p \choose 2} = {{p+1} \choose 2} \end{align}$ Stück. Oder gleich "mit Wiederholung, ohne Reihenfolge": $\begin{align} {{p+1} \choose 2} \end{align}$ . Wenn die Formel für Anzahl der irreduziblen oben stimmt, müßte sich in der Summe $\begin{align} p^2 \end{align}$ ergeben: $\begin{align} {{p+1} \choose 2} + {p \choose 2} = p^2 \end{align}$ Und das stimmt.
28.03.2020, 22:06	Elvis	Auf diesen Beitrag antworten »
Das gefällt mir. Mit einigen Berechnungen und ein paar Überlegungen haben wir Probleme gelöst, die es bisher noch nicht gab und Fragen beantwortet, die niemand gestellt hat. Ich habe etwas dazugelernt, was ich bisher so explizit noch nicht verstanden hatte. Die endlichen Körper überraschen mich immer wieder, und wenn ich die Zeit finde, werde ich mich eines Tages mehr mit algebraischen Funktionenkoerpern über endlichen Körpern beschäftigen. Hat jemand Literatur zum Thema (abgesehen von algebraischer Zahlentheorie)? Hier habe ich etwas auf dem passenden Niveau (https://www.amazon.de/Arithmetic-Functio...s=books&sr=1-10) aber ich suche eher Monographien, Handbücher oder Lehrbücher. Angesichts der Wunder, die uns immer wieder in der Mathematik begegnen, ist es ein Wunder, dass immer wieder Spinner auftauchen, die wider besseres Wissen behaupten, etwas besser zu wissen (namentlich P. und q.).

Neue Frage »

Antworten »

Mitternachtsformel über endlichen Körpern

Verwandte Themen