Diskussion:Lemma von Zolotareff

Widerspruch zu Quartls Revert

Hallo Quartl!

(A): Mit dieser pauschalen Zurücksetzung meiner Überarbeitung hast Du (abgesehen von der Frage um die 0, siehe dazu weiter unten) einiges Falsches in den Artikel eingefügt und einige Verbesserungen aus ihm entfernt. Korrigiere das bitte selbst wieder, mit Deinem Kommentar in der Zusammenfassungszeile wendest Du Dich ja nur gegen mein Weglassen der 0.

(B): Du meinst dort, daß man die 0 mitnehmen solle, weil

1. sonst die Matrixdarstellung unten nicht klappe und
2. das außerdem auch in der Literatur so gehandhabt werde.

Zu 1.: Ich sehe (Nachtrag: in dieser alten Version) keinen Zusammenhang zwischen den Permutationen $\pi _{a,p}$ im Lemma (einschließlich seines Beweises und der Beispiele) einerseits und den Permutationen $\alpha _{p,q},\tau _{p,q}$ (im Beweis des Reziprozitätsgesetzes) andererseits, der eine Vereinheitlichung in der Frage der 0 nötig machen würde. Wenn man aber eine solche Vereinheitlichung unbedingt anstrebte, so ließe sie sich auch leicht durch das Weglassen der 0 in allen Fällen erzwingen (was auch Zolotarev selbst in seiner Originalarbeit getan hat, wo nur die Zahlen von 1 bis pq–1 permutiert werden); man könnte dann in den von Dir erwähnten Matrizen die erste Zeile und die erste Spalte weglassen.

Ich kann mich übrigens mit dem ganzen Abschnitt Quadratisches Reziprozitätsgesetz in seiner jetzigen Form nicht besonders anfreunden, weil ich dem dortigen Beweis nicht lückenlos zu folgen imstande bin. Das kann natürlich nur an meiner mangelnden Auffassungsgabe liegen, aber vielleicht auch an irgendwelchen Ungenauigkeiten, die beim Übertragen (und Umformulieren und/oder Kürzen?) passiert sein könnten. Vorläufig will ich es aber bei diesem kurzen Hinweis belassen, damit wir uns erst einmal auf das von Dir Zurückgesetzte konzentrieren können. Mehr dazu dann also bei Bedarf erst später.

Zu 2.: Hier siehst Du mich noch verwunderter: Mein Vorschlag hatte seinen Ursprung zunächst nur in einer Art ästhetischer Irritation (die natürlich auch ihre sachliche Rechtfertigung hat). Nach Deiner Behauptung habe ich nun aber auch alle vier von Dir in den Artikel gestellten Links inspiziert:

• Weblink 1: PlanetMath (PDF)
• Weblink 2: Matt Baker
• Weblink 3: nLab
• Die Originalarbeit: Zolotareff

Auf allen vier Seiten ist mein Vorschlag (also ohne 0) realisiert. Deine Behauptung, in der Literatur werde es anders (also mit 0) gehandhabt, läßt sich also zumindest mit keinem einzigen der von Dir selbst geposteten Links verifizieren. Vielleicht vermag das ja (auch wenn es sicherlich auch Literatur mit 0 geben wird) Deine Sicht der Dinge ein wenig zu relativieren, sodaß Du Deine Entscheidung in dieser Frage (mit/ohne 0) noch einmal überdenken willst.

Liebe Grüße, Franz 13:18, 11. Aug. 2015 (CEST)

Hallo Franz, als allererstes vielen Dank für deine Durchsicht und deine Verbesserungen am Artikel. Ich hatte deinen gestrigen Edit als Vorschlag angesehen, den ich akzeptieren aber auch ablehen darf. Dass du nebenbei auch noch ein paar andere Verbesserungen eingebracht hast, habe ich nachts um drei schlichtweg übersehen (es hätte aber auch geholfen, wenn du dies in der Zusammenfassungszeile erwähnt hättest).

Unter Literatur verstehe ich primär das, was im Abschnitt "Literatur" zu finden ist. Im Buch von Diekert, Kufleitner und Rosenberger [1] wird die Permutation explizit auf der Menge $\{0,\ldots ,n-1\}$ konstruiert, daher hatte ich das auch im Artikel so übernommen. Ich muss aber zugeben, dass ich mir (auch aufgrund mangelnder Französischkenntnisse) die Originalarbeit von Zolotareff nicht genauer angeschaut habe. In der Tat nimmt er dort die Null aus. Ich glaube aber nicht, dass die Matrixdarstellung dadurch gerettet werden kann, dass einfach nur die erste Zeile und Spalte gestrichen werden, vielmehr wird wohl nur das linke obere Element gestrichen. Die Weblinks kann man formal nicht als Quellen verwenden, ich möchte aber darauf hinweisen, dass Matt Baker in seinem Claim 1 bei der Definition von $\left[{\tfrac {n}{m}}\right]$ die Null sehr wohl miteinbezieht.

Inhaltlich ist es wohl ziemlich egal, ob man die Null mitnimmt oder nicht. Die Frage ist letztendlich, was theoretisch oder didaktisch besser wäre. Ich persönlich finde es beim Umgang mit Restklassen natürlicher die Null mit einzuschließen und die Matrizen sind einfach rechteckiger, wenn die Null dabei ist. Es mag aber tieferliegende gruppentheoretische Gründe geben, die Null besser auszuschließen. Du scheinst dich sehr gut in dem Bereich auszukennen, vermutlich besser als ich, deswegen werde ich deinem Rat folgen und den Vorschlag nun dennoch annehmen.

Zu dem Beweis: ja, der ist verkürzt, möglicherweise zu stark, denn ich wollte nicht zu ausufernd werden. Stattdessen habe ich die involvierten Permutationen explizit angegeben. Den Beweis für die Darstellung von $\operatorname {sgn} (\tau _{p,q})$ durch Aufzählung der Fehlstände wollte ich gegebenenfalls in einen eigenen Artikel Transpositionspermutation auslagern. Den Beweis für die Darstellung von $\operatorname {sgn} (\alpha _{p,q})$ werde ich noch etwas ausführlicher schreiben (da fehlt noch ein Term, der sich aber rauskürzt). Der Rest sollte nachvollziehbar sein.

Nochmal vielen Dank für deine Hilfe und entschuldige meinen zu pauschalen Revert. Viele Grüße, --Quartl (Diskussion) 18:39, 11. Aug. 2015 (CEST)

Noch eine Rückfrage: warum stört es dich, die Restklassen zu permutieren, also $\pi _{a,p}\colon \mathbb {Z} _{p}^{\times }\to \mathbb {Z} _{p}^{\times }$ statt $\pi _{a,p}\colon \{1,\ldots ,p-1\}\to \{1,\ldots ,p-1\}$ zu definieren? Viele Grüße, --Quartl (Diskussion) 18:54, 11. Aug. 2015 (CEST)

Hallo Quartl!

• Zur Zusammenfassungszeile: Ja, da hast Du Recht. Noch besser wäre es wohl gewesen, meine Bearbeitung auf mehrere Edits zu verteilen. Vielen Dank jedenfalls für Deine rasche Rückmeldung und die freundliche Erledigung!
• Zu Matt Baker (und allgemein zur Frage „mit/ohne 0“): Ja, aber im Beweis des Lemmas (und hauptsächlich darauf bezog sich ja mein ursprünglicher Vorschlag „ohne 0“) bleibt er ganz innerhalb der multiplikativen Gruppe. Daß er dabei den durch den Index definierten Isomorphismus mit der (zyklischen) additiven Restklassengruppe modulo p−1 verwendet, widerspricht dem natürlich nicht, sondern bekräftigt nur meine Meinung, daß ein Permutieren der additiven Restklassengruppe modulo p der ganzen Problemstellung nicht angemessen wäre: Der „Umgang mit Restklassen“, den Du erwähnst, besteht ja im Wesentlichen darin, sie zu multiplizieren. Und die multiplikativen Eigenschaften der Restklassen manifestieren sich eben am reinsten innerhalb der multiplikativen Gruppe, während sie verwaschen werden, wenn man die 0 dazunimmt (was bei Matt Baker steht, ist aber nicht weiter wichtig, sodaß wir diesen Punkt wohl nicht zu vertiefen brauchen). Das soeben Gesagte gilt übrigens nicht im selben Umfang für die Permutationen, die im Beweis des Reziprozitätsgesetzes verwendet werden. Dort hat das Permutieren aller Ringelemente eine gewisse Berechtigung, weil beide Ringoperationen im Spiel sind (was beim Lemma und seinem Beweis nicht der Fall ist).
• Zum neuen Beweis: Ich werde auch ihn bei Gelegenheit prüfen, es kann aber ein paar Tage dauern. In Kürze werde ich mich nämlich der zermürbenden Großstadthitze durch die Flucht in einen kühlen Wald entziehen, wo ich vermutlich bis nach dem kommenden Wochenende nicht online sein kann.
• Zur letzten Rückfrage: Es stört mich gar nicht (eher im Gegenteil), denn für beide Varianten gibt es gute Gründe. Ich hatte damals die Gruppen nur deshalb wieder durch ihre Trägermengen ersetzt, weil mir Deine vorangegangene entgegengesetzte Änderung als nur auf einem Mißverständnis beruhend erschienen war. Ich dachte also einfach, Du hättest lieber Deine alte Version mit den Mengen, wogegen ich auch nichts Schwerwiegendes einzuwenden hätte. Du kannst aber gerne wieder zu den Gruppen übergehen: Solange wir hier „ohne 0“ arbeiten, handelt es sich bei den Permutationen ja um Gruppenisomorphismen. Hier leuchtet ein wenig der Satz von Cayley durch und bei der Tatsache, daß die Elemente einer Gruppe durch Multiplikation mit einem festen Element untereinander permutiert werden, handelt es sich um den wohl elementarsten Satz der ganzen Gruppentheorie, der über Triviales hinausgeht, sodaß man kaum übertreibt, wenn man sagt, daß gerade mit ihm die eigentliche Gruppentheorie beginnt. All dem könnte man durch die Variante mit den Gruppen Rechnung tragen. Für die Variante mit den Mengen würde zum Beispiel sprechen, daß man dem Problem der Verwechslung der Restklassen mit ihren Repräsentanten aus dem Wege geht. Ich sehe dieses Problem aber keineswegs als schwerwiegendes an.

Liebe Grüße, Franz 13:41, 12. Aug. 2015 (CEST)

Hallo Franz, ich werde jetzt am Artikel nichts weiter ändern, bis du wieder zurück bist und dir den Beweis zum quadratischen Reziprozitätsgesetz (egal in welcher der verlinkten Varianten) genauer angesehen hast. Alle Beweise verwenden in irgendeiner Form die kanonische Isomorphie $\mathbb {Z} _{pq}\cong \mathbb {Z} _{p}\times \mathbb {Z} _{q}$. Wenn nun das Lemma auf $\mathbb {Z} _{p}^{\times }$ formuliert wird, sind die Beweise an zentraler Stelle inkonsistent, eben weil die Null fehlt. Möglicherweise kann man den Beweis auch über die (nicht ganz so kanonische) Isomorphie $\mathbb {Z} _{pq}^{\times }\cong \mathbb {Z} _{p}^{\times }\times \mathbb {Z} _{q}^{\times }$ führen (das würde in der Matrixdarstellung von $\alpha _{p,q}$ einem Streichen der ersten Zeile und Spalte entsprechen). Vielleicht hat Zolotareff genau das sogar gemacht, aber leider kann ich seinen Originalbeweis aufgrund der Sprachproblematik nicht nachvollziehen. Mich würde deine Einschätzung dazu interessieren. Ich gehe jetzt zur Abkühlung ins Schwimmbad :-). Viele Grüße, --Quartl (Diskussion) 17:02, 12. Aug. 2015 (CEST)

Hallo Quartl!

Ich habe mir jetzt Deinen neuen Beweis des Reziprozitätsgesetzes genauer angeschaut und möchte noch einige Anmerkungen dazu machen:

• Der Beweis ist (um den Rahmen des Artikels nicht zu sprengen) an einigen Stellen stark gekürzt. Der Leser merkt aber erst relativ spät, daß er dem Beweis irgendwann einmal nicht mehr „im Kopf“ zu folgen vermag, weil wesentliche/umfangreiche Teilschritte unbegründet bleiben. Das liegt zum Teil auch daran, daß der Aufbau des ganzen Beweises nicht gerade einfach zu erfassen ist.
  Es wäre daher zu überlegen, ob man den Beweis nicht besser gleich durch eine (dann natürlich auch ausdrücklich als solche gekennzeichnete) reine Beweisskizze ersetzen sollte. Das bedeutete einen (weitgehenden) Verzicht auf Begründungen der einzelnen Teilschritte, während der Schwerpunkt auf einer möglichst durchsichtigen Darstellung der logischen Struktur des Beweisganges läge.
  Dieser Vorschlag gilt natürlich nicht nur für den vorliegenden Artikel, sondern grundsätzlich für alle hinreichend komplexen Beweise, die nicht in einer auch nur halbwegs vollständig ausgearbeitete Fassung dargestellt werden können.
• Die Permutationen $\tau$ und $\alpha$ würde ich auf ganz $\mathbb {Z} _{pq}$ definiert lassen.
• Auf die Permutation $\pi$ wird in der neuen Fassung anders (hinsichtlich der von Dir erwähnten Inkonsistenz: wesentlicher) Bezug genommen als in der alten, was jetzt auch die Wahl der Variante „mit 0“ mehr rechtfertigen würde als vorher. Alternativ dazu wäre auch eine einfache Umbenennung denkbar, sodaß dann im RG-Beweis etwa von einer Permutation $\beta _{p,q}$ auf $\mathbb {Z} _{q}$ die Rede wäre, deren Einschränkung auf $\mathbb {Z} _{q}^{\times }$ gleich der im Lemma definierten Permutation $\pi _{p,q}$ ist. Ob so eine „gekünstelte“ Konstruktion gerechtfertigt oder übertrieben ist, beibt allerdings fraglich. Immerhin wird ja auch in den angegebenen Weblinks auf diese Feinheit verzichtet, weil dort wohl angenommen wird, daß dem Leser ohnehin klar ist, daß mit der 0 nur ein Fixpunkt hinzukommt, der nichts Wesentliches verändert. Ob wir – als Enzyklopädie – hier strengere Maßstäbe anlegen müssen, vermag ich nicht abschließend zu beurteilen.

Zu Zolotarevs Originalarbeit kann ich leider auch nicht mehr beitragen, als den reinen „Formeln“ zu entnehmen ist, weil ich kein Wort Französisch kann.

Liebe Grüße, Franz 23:23, 18. Aug. 2015 (CEST)

Hallo Franz, danke für die Durchsicht und deine Kommentare. Vermutlich fällt es mir leichter, den Beweis nachzuvollziehen, weil ich mich ganz gut mit Permutationen auskenne. Ich werde mir überlegen, ob ich gegebenenfalls noch fehlende Informationen ergänze, oder den Beweis zu einer Beweisskizze kürze. Reizvoll fände ich es auch, sofern das möglich ist, den Beweis auf $\mathbb {Z} _{p}^{\times }\times \mathbb {Z} _{q}^{\times }$ zu führen. Vermutlich wäre das aber zu sehr Theoriefindung, wenn Zolotareff selbst das nicht schon so gemacht hat. Allerdings bin ich die kommenden Tage ziemlich eingespannt, deswegen wird das wohl etwas dauern. Viele Grüße, --Quartl (Diskussion) 11:06, 19. Aug. 2015 (CEST)

So, jetzt habe ich noch folgende Änderungen vorgenommen:

• Die Permutation $\pi _{a,p}$ operiert jetzt auf den primen Restklassen modulo $p$.
• Im Beweis des quadratischen Reziprozitätsgesetzes habe ich die 0 als zusätzlichen Fixpunkt erwähnt.
• Zur Berechnung des Vorzeichens von $\alpha _{p,q}$ habe ich Spalten- statt Zeilenvertauschungen verwendet. Dadurch wird die Berechnung etwas leichter. Zur Illustration habe ich auch noch die Matrixdarstellung nach Spaltenvertauschung ergänzt.

Von der Struktur her ist der Beweis eigentlich klar:

• Der wesentliche Trick ist die Permutation $\alpha _{p,q}$, denn die enthält die inverse Permutation von $\pi _{p,q}$ als Zeilen und die inverse Permutation von $\pi _{q,p}$ als Spalten und damit auch beide Legendre-Symbole.
• Man berechnet nun die Vorzeichen von $\alpha _{p,q}$, $\tau _{p,q}$ und $\alpha _{p,q}\circ \tau _{q,p}$.
• Aus dem Signum-Homomorphismus folgt dann direkt das quadratische Reziprozitätsgesetz.

Viele Grüße, --Quartl (Diskussion) 11:09, 21. Aug. 2015 (CEST)

Seltsame Notation / falsche Definition

Die Definition von π_a,p ist m.E. nicht korrekt. Der Autor verwechselt die Elemente von Z_p (Restklassen, ${\bar {k}}=[k]=\{k+mp;~m\in \mathbb {Z} \}=\{k,k\pm p,k\pm 2p,...\}$) mit den einfachen Zahlen k ∈ Z. In Z_p gibt es keine Kongruenzrelation, wie das derzeit da steht. Die Funktion ist einfacher und korrekter der Multiplikations-Operator π_a,p([k]) := a·[k] = [a·k], wenn man wie der Autor a ∈ Z wählt. — MFH 02:01, 18. Nov. 2020 (CET)

EDIT: Habe jetzt eine korrigierte Version vorgeschlagen. In der Hoffnung, "Verschlimmbesserungen" zu vermeiden, möchte ich erklären warum ich es für besser halte, keinen Punkt "·" zu verwenden: der sollte zur Eindeutigkeit für die Gruppenoperation (abgeleitet von der Ring-Multiplikation in Z_p) reserviert werden. Für eine positive ganze Zahl a > 0 haben wir hingegen die "skalare Multiplikation" a [k]  := [k] + [k] +...+ [k] (a Mal [k]) (welche in multiplikativer Gruppennotation einer Potenz entsprechen würde). Das ist nicht dasselbe wie mengentheoretische Multiplikation a·[k] = { a x ; x ∈ [k] } oder [a]·[k] = { b x ; b ∈ [a], x ∈ [k] }, welche nur Untermengen sind von [a]•[k] := [a k], wie die Multiplikation im Ring Z_p, und das daraus abgeleitete Produkt der multiplikativen Gruppe Z_p^x, definiert werden müssen! — MFH 02:22, 18. Nov. 2020 (CET)