Zolotarev's Magical Proof of Quadratic Reciprocity

De Magie van Kaarten en Getallen: Zolotarevs Bewijs

Stel je voor dat wiskunde niet alleen uit saaie formules bestaat, maar ook uit een groot magisch toneelstuk. De auteur, Matthew Baker, neemt je mee door een bewijs van een van de beroemdste regels in de getaltheorie: de Wet van de Kwadratische Reciprociteit.

Hij deelt dit verhaal op in drie acts, net als in de film The Prestige:

1. De Pledge (De Belofte): Het tonen van iets alledaags.
2. De Turn (De Toer): Het maken van iets onmogelijks.
3. De Prestige (De Prestatie): Het verrassende einde dat alles verklaart.

Laten we de kaarten erbij pakken.

---

Act 1: De Pledge (Het Kaartspel)

Stel je een stapel kaarten voor, genummerd van 0 tot $mn - 1$. We hebben een stapel van $m \times n$ kaarten. Nu gaan we deze kaarten op twee verschillende manieren in een rechthoekig raster (een grid) leggen.

• Manier A (Rijen): Je legt de kaarten rij voor rij. Eerst de bovenste rij van links naar rechts, dan de volgende rij, enzovoort.
• Manier B (Kolommen): Je legt de kaarten kolom voor kolom. Eerst de eerste kolom van boven naar beneden, dan de tweede kolom, enzovoort.

Het Raadsel:
Als je de kaarten eerst volgens Manier A hebt gelegd en ze vervolgens overneemt naar Manier B, zijn de kaarten verplaatst. De kaart die eerst op positie 1 lag, ligt nu ergens anders. Dit is een permutatie (een herschikking).

De vraag is: Is deze herschikking "even" of "onaan"?

• Denk aan een danspaar. Als je twee mensen van plek wisselt, is dat één beweging (onaan). Als je drie mensen in een cirkel laat draaien, is dat twee bewegingen (even).
• Wiskundigen noemen dit het teken van de permutatie: $+1$ (even) of $-1$ (onaan).

Het Magische Resultaat:
Het paper toont aan dat het teken van deze herschikking afhangt van de grootte van $m$ en $n$. Als je de kaarten van rijen naar kolommen schuift, is het teken precies gelijk aan:
$$(-1)^{\text{aantal paren rijen} \times \text{aantal paren kolommen}}$$

Klinkt ingewikkeld? Het betekent simpelweg: als zowel $m$ als $n$ een getal zijn dat 3 overlaat bij delen door 4 (zoals 3, 7, 11), dan is het teken -1. In alle andere gevallen is het +1.

---

Act 2: De Turn (De Diagonale Toer)

Nu wordt het gekker. Stel dat $m$ en $n$ geen gemeenschappelijke delers hebben (ze zijn "onderling ondeelbaar"). Nu introduceren we een derde manier om de kaarten te leggen: Diagonaal.

• Manier C (Diagonaal): Je begint linksboven en legt kaarten diagonaal naar rechtsbeneden. Als je aan de rand komt, "wrap" je (zoals in een Pac-Man spel) naar de andere kant.

Nu hebben we drie manieren: Rij (R), Kolom (C) en Diagonaal (D).
We kunnen kijken naar de herschikkingen tussen deze manieren:

1. Van Rij naar Diagonaal ($\alpha$).
2. Van Diagonaal naar Kolom ($\beta$).
3. Van Rij naar Kolom ($\gamma$).

De Grote Onthulling:
Het paper ontdekt iets verbazingwekkends:

• De herschikking van Rij naar Diagonaal ($\alpha$) is precies hetzelfde als het vermenigvuldigen van getallen met $n$ in een wereld van $m$ getallen.
• De herschikking van Diagonaal naar Kolom ($\beta$) is hetzelfde als vermenigvuldigen met $m$ in een wereld van $n$ getallen.

En omdat we weten dat "Rij naar Kolom" gelijk is aan "Rij naar Diagonaal" gevolgd door "Diagonaal naar Kolom", kunnen we de tekens vermenigvuldigen:
$$\text{Teken}(\alpha) \times \text{Teken}(\beta) = \text{Teken}(\gamma)$$

Als we de formules invullen, krijgen we een formule die eruitziet als de beroemde Wet van de Kwadratische Reciprociteit, maar dan nog zonder te weten wat "kwadraten" zijn. Het is alsof we een code hebben gekraakt zonder de sleutel te kennen.

---

Act 3: De Prestige (De Sleutel)

Nu komen we bij het echte magische moment. Wat heeft dit met kwadraten (getallen die je kunt schrijven als $x^2$) te maken?

Stel je voor dat je kijkt naar een priemgetal $p$ (een getal dat alleen deelbaar is door 1 en zichzelf, zoals 3, 5, 7, 11).
Er is een beroemd symbool, het Legendre-symbool $\left(\frac{a}{p}\right)$, dat vertelt of een getal $a$ een "kwadraat" is modulo $p$.

• Is $a$ een kwadraat? Dan is het symbool $+1$.
• Is het geen kwadraat? Dan is het symbool $-1$.

Zolotarevs Lemma (De Magische Link):
Het paper toont aan dat het teken van de herschikking die we in Act 2 hebben beschreven (het vermenigvuldigen met $a$ in een wereld van $p$ getallen) exact hetzelfde is als het Legendre-symbool!

Dit betekent:

• Als het vermenigvuldigen met $a$ een "onaan" herschikking is, dan is $a$ géén kwadraat.
• Als het een "even" herschikking is, dan is $a$ wél een kwadraat.

Het Eindresultaat:
Als we dit lemma combineren met de formule uit Act 2, krijgen we direct de Wet van de Kwadratische Reciprociteit:

Als $p$ en $q$ twee verschillende priemgetallen zijn, dan hangt het antwoord op de vraag "Is $p$ een kwadraat modulo $q$?" en "Is $q$ een kwadraat modulo $p$?" samen.

Ze zijn ofwel beide kwadraten, of beide geen kwadraten, tenzij beide getallen 3 overlaten bij delen door 4. In dat geval is het antwoord omgekeerd.

De formule is:
$$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{(p-1)(q-1)}{4}}$$

---

Waarom is dit zo speciaal?

Normaal gesproken wordt dit bewijs gedaan met zware algebra en ingewikkelde formules. Zolotarev (de wiskundige uit 1872) en Matthew Baker (de auteur van dit paper) hebben het bewijs "ontdaan" van al die zware wiskunde.

Ze hebben het vertaald naar iets tastbaars: het herschikken van een kaartspel.

• Ze tonen dat de diepe, abstracte relatie tussen priemgetallen en kwadraten eigenlijk gewoon een gevolg is van hoe je kaarten in een raster kunt leggen.
• Het is alsof je ontdekt dat de wetten van de zwaartekracht (die heel complex lijken) eigenlijk gewoon te verklaren zijn door te kijken hoe een balletje rolt op een helling.

Bonus:
In de "Director's Cut" (aan het einde van het paper) laten ze zien dat je met dezelfde kaarttrucs ook kunt bewijzen of $-1$ of $2$ kwadraten zijn. Het is alsof je met één set kaarten de gehele wetenschap van kwadratische resten kunt uitleggen.

Samenvatting in één zin

Dit paper toont aan dat de mysterieuze relatie tussen priemgetallen en kwadraten (de Wet van de Kwadratische Reciprociteit) eigenlijk gewoon een slimme kaarttruc is: als je een stapel kaarten op een specifieke manier herschikt, vertelt de manier waarop ze bewegen je precies of een getal een kwadraat is of niet.