La bellezza di un calcio in faccia

[Troleito br00tal]

Determinare il numero di coppie $(x;y)$, dove $x$ e $y$ sono classi di resto modulo $p$ tali che:
\begin{equation}
x^2=y^2+1
\end{equation}

E, tanto per traviare le menti, usare questo fatto per dimostrare che $2$ è residuo quadratico modulo $p$ se e solo se $16|p^2-1$.

[<enigma>]

Un commento su questo problema. Il numero che cerchiamo è uguale al valore atteso del numero di coppie di residui quadratici consecutivi, se per ogni numero modulo $p$ decidessimo casualmente con probabilità $1/2$ se renderlo o no residuo quadratico. Lo stesso dovrebbe valere se richiediamo che i residui distino $k$ invece di $1$. Questo mi portò a chiedermi "ma allora i residui quadratici si comportano davvero casualmente?". In sostanza sì, ed è quello che asserisce la fantastica disuguaglianza di Pólya–Vinogradov!

[Gulliver]

Dobbiamo risolvere $x^2-y^2=1$ ossia $(x-y)(x+y)=1$, col cambio di variabile $x-y=w,x+y=z$ dobbiamo risolvere $wz=1$ che ha p-1 coppie di soluzioni.
Nella seconda richiesta ci deve essere qualche typo perchè $8|p^2-1$ per ogni p dispari.
Però pensando alla tua richiesta mi è venuta in mente una cosa analoga(forse era quella che volevi proporre): tutte le soluzioni in cui non c'è lo 0 si presentano 4 a 4(posso mettere segno + o - a entrambe le coordinate). Quindi modulo 4, il numero di soluzioni in cui c'è lo 0 è proprio p-1(per quanto calcolato). Ma allora poichè (1,0),(-1,0) c'è sempre, stiamo a 2 mod 4: stiamo a 0 se e solo se ci sta $(0,i),(0,-i)$, cioè questo ridimostra che -1 è quadratico se e solo se $p \equiv 1 \pmod 4$.

[Troleito br00tal]

Dobbiamo risolvere $x^2-y^2=1$ ossia $(x-y)(x+y)=1$, col cambio di variabile $x-y=w,x+y=z$ dobbiamo risolvere $wz=1$ che ha p-1 coppie di soluzioni.

Ok, però risolvila (te lo dico perché non è così scontato che se $(w_1;z_1)$ e $(w_2;z_2)$ sono soluzioni allora $(x_1;y_1)$ e $(x_2;y_2)$ sono una coppia di soluzioni $distinte$).

Nella seconda richiesta ci deve essere qualche typo perchè $8|p^2-1$ per ogni p dispari.
Però pensando alla tua richiesta mi è venuta in mente una cosa analoga(forse era quella che volevi proporre): tutte le soluzioni in cui non c'è lo 0 si presentano 4 a 4(posso mettere segno + o - a entrambe le coordinate). Quindi modulo 4, il numero di soluzioni in cui c'è lo 0 è proprio p-1(per quanto calcolato). Ma allora poichè (1,0),(-1,0) c'è sempre, stiamo a 2 mod 4: stiamo a 0 se e solo se ci sta $(0,i),(0,-i)$, cioè questo ridimostra che -1 è quadratico se e solo se $p \equiv 1 \pmod 4$.

Hai ragione, intendevo 16! Ora edito. Comunque il resto è corretto.

[Gulliver]

Ok esplicito quel passaggio.
Considero la trasformazione $G(x,y)=(x-y,x+y)$ e $F(x,y)=((x+y)/2,(y-x)/2)$(ha senso invertire per 2 perchè p è dispari). Ora si trova che $F(G(x,y))=(x,y)$(e quindi anche il contrario perchè l'insieme è finito, ad ogni modo si può verificare) e che abbiamo argomentato che G manda l'insieme di equazione $x^2-y^2=1$ in quello di equazione $wz=1$. D'altronde è vero anche che F manda il secondo nel primo:$wz=1$ implica $(w+z)^2/4-(w-z)^2/4=w^2/4+z^2/4+2wz/4-w^2/4+2wz/4-z^2/4=4wz/4=wz=1$. Quindi F e G mettono in biezione i due insiemi. Il secondo ha chiaramente p-1 punti: $(t,1/t), t \neq 0$ ne è una parametrizzazione(stiamo usando l'esistenza dell'inverso di ogni elemento nonnullo mod p).

[Troleito br00tal]

Ok bene! Ora prova la seconda parte vera!

[Gulliver]

Allora ispirandomi al ragionamento di prima che mi determinava quando -1 era quadratico, ho fatto così:
Prima osservo che se $p \equiv 1 \pmod 4 $, allora il cambio di variabile x'=x,y'=iy, mi trasforma l'equazione $x^2-y^2=1$ in $x'^2+y'^2=1$(come prima e più facilmente si vede che crea una biezione). Pertanto dal conto di prima abbiamo che il numero di soluzioni di $x^2+y^2=1$ è p-1 (oppure si può fare lo stesso ragionamento di prima con $(x+iy)(x-iy)=1$). Ora 2 è non quadratico se e solo se non ci sono soluzioni a due coordinate uguali, ma allora abbiamo cambiando di segno e scambiando le posizioni che a parte (-1,0),(1,0),(0,1),(0,-1) tutte le altre soluzioni si raggruppano a gruppi di 8 alla volta. Pertanto $p-1 \equiv 4 \pmod 8$ che è $p^2-1$ non divisibile per 16. Mentre se 2 è quadratico vi è una soluzione con 2 coordinate uguali, (x,x) che entra in un gruppo di 4 soluzioni(si cambia al più il segno, scambiare non aggiunge niente), pertanto abbiamo $p-1 \equiv 0 \pmod 8$ ossia $p^2-1 \equiv 0 \pmod {16}$.
Analogamente se $p\equiv 3 \pmod 4$, osservo che in $x^2=y^2+1$ x è sempre nonnulla quindi il cambio $(x',y')=(y/x,1/x)$ mi dà una biezione con le soluzioni di $x'^2+y'^2=1$ con $y' \neq 0$. Poi vi sono altre 2 soluzioni con y'=0, (1,0),(-1,0). Pertanto abbiamo p+1 soluzioni all'equazione $x^2+y^2=1$.
Rifacendo esattamente lo stesso ragionamento di prima abbiamo che 2 è quadratico se e solo se $p+1 \equiv 0 \pmod 8$ ossia $p^2-1 \equiv 0 \pmod {16}$.

Penso di avere una soluzione analoga, ma leggermente migliore perchè in qualche modo fa i conteggi modulo 16 direttamente su un insieme di $p^2-1$ elementi(le coppie non entrambe nulle, su cui si scambia e si cambia di segno, solo che ora ci sono gli altri valori da considerare), a patto però di trovare alcuni fatti in più. Poi magari la metto.

[Troleito br00tal]

Ottimo! Postala, mi interessa!

[Gulliver]

Ecco qui:
Consideriamo $f(x,y)=x^2+y^2$. Si può dimostrare facilmente che f è suriettiva. Consideriamo il seguente generico cambio di variabile $x'=ax+by,y='-bx+ay$. Si trova che questo cambio è invertibile se e solo se $a^2+b^2\neq 0$ e che l'inversa è $x=\frac{ax'-by'}{a^2+b^2},y=\frac{ax'+by'}{a^2+b^2}$. Inoltra risulta, chiamando $A_{(a,b)}(x,y)=(x',y')$ il cambio di variabile associato ad a,b, come prima, $f(A_{(a,b)}(x,y))=(a^2+b^2)(x^2+y^2)$(questa cosa riformula in altro modo, la solita nozione di moltiplicatività delle norme dei numeri complessi). Ora il fatto abbiamo che se $a^2+b^2 \neq 0$, allora $A_{(a,b)}$ crea una biezione tra $(f^{-1}(1))$ e $f^{-1}(a^2+b^2)$. Essendo f suriettiva, e quindi $a^2+b^2$ prende tutti i resti nonnnulli, abbiamo che $|f^{-1}(c)|=|f^{-1}(d)|, \forall c,d \neq 0$.

Per inciso questo ci permette di ricalcolare le quantità che abbiamo ottenuto nella soluzione precedente: se $p \equiv 3 \pmod 4$ allora, abbiamo $f^{-1}(0)=(0,0)$ pertanto, per quanto spiegato su, $|f^{-1}(1)|(p-1)=p^2-1$ quindi $|f^{-1}(1)|=p+1$, mentre se $p \equiv 1 \pmod 4$ abbiamo che $(x+iy)(x-iy)=0$ ha $2(p-1)+1=2p-1$ soluzioni, pertanto abbiamo $|f^{-1}(0)|=2p-1$, da cui $|f^{-1}(1)|(p-1)=p^2-2p+1=(p-1)^2$ quindi $|f^{-1}(1)|=p-1$.

Ora distinguiamo i due casi:
$p \equiv 3 \pmod 4$, allora i $p^2-1$ punti a coordinate non entrambe nulle, non soddisfano mai $x^2+y^2=0$. Ma allora se 2 non è quadratico significa che $f^{-1}(r)$ non ha mai punti a coordinate uguali, quando $(\frac{r}{p})=1$. Quindi essendo $|f^{-1}(c)|=|f^{-1}(d)|, \forall c,d \neq 0$, otteniamo che su metà dei punti,non compaiono mai coordinate uguali. Inoltre su di essi agisce il cambio di segno e lo scambio di posto, gli unici casi in cui si hanno soli 4 elementi raggruppati proviene da $(a,0)$: questo dà luogo a $(p-1)/2$ blocchi di 4. Quindi abbiamo in totale $\frac{p^2-1}{2}=4(p-1)/2+8k$ cioè $p^2-1=4(p-1)+16k$ ed essendo $p-1 \equiv 2 \pmod 4$ otteniamo $p^2-1 \equiv 8 \pmod {16}$. Se 2 è quadratico si fa lo stesso ragionamento e si giunge al fatto che vi sono p-1 gruppetti di 4, della forma $(a,a)$. Pertanto $\frac{p^2-1}{2}=4(p-1)/2+4(p-1)/2+8k=4(p-1)+8k$ ossia $p^2-1=8(p-1)+16k$ ma $p-1$ è pari.

L'altro caso, $p \equiv 1 \pmod 4$ mi viene un pò più artificialmente perchè tolto $f^{-1}(0)$ non abbiamo $p^2-1$ punti ma $(p-1)^2$. E quindi finisco per ripassare per il conteggio già fatto, in un certo senso. Se poi trovo un modo naturale(cioè che non sia sostanzialmente un riallacciarsi al secondo paragrafo di qui e quindi alla prima soluzione, ma qualcosa che interpreta direttamente la quantità $p^2-1$ come il numero di certi punti su cui facciamo certe manovre, come il terzo paragrafo qui) di fare anche qui il conteggio, lo piazzo.

[Troleito br00tal]

Direi che è giusta, non ho controllato i conti di $p \equiv 1 \pmod{4}$ ma mi ben fido comunque bene!