Somme di quadrati

[fields]

1) Dimostrare che, se $p$ e' primo, ogni naturale $n$ è somma di due quadrati modulo $p$. Ovvero, $n=x^2+y^2 (mod p)$ per qualche $x,y\in NN$.

2) Generalizzare 1) ad ogni campo finito $F$. Ovvero, dimostrare che, se $F$ e' un campo finito, ogni elemento di $F$ e' somma di due quadrati.

Chiaramente 2) implica 1).

[TomSawyer]

1) Se $n \in F$, con $F$ campo finito di ordine $p$, primo naturalmente, allora possiamo esprimere $n$ come somma di due elementi di $F$ in $(p+1)/2$ modi.
Ora, poiché ogni campo finito è ciclico, abbiamo che per ogni elemento $a \in F$, esistono $m \in F$ unico e $g \in F$ tali che $0\le m \le p-2$ e $a=g^m$.
Sapendo che ci sono $(p+1)/2$ modi per esprimere $n$ come somma di due potenze di $g$ o come somma di una potenza di $g$ e lo zero, negli $(p+1)/2$ modi è presente come operando di una somma almeno una volta ogni intero $\in [0,p-2]$. Quindi, per il pigeonhole principle, si avrà almeno una volta che $n=g^k+g^j$, con $k, j$ pari, o altrimenti si avrà $n=0+g^k$, con $k$ pari.

[fields]

Ok, buona dimostrazione, anche se hai omesso qualche passaggio delicato.

Rimane ora la dimostrazione della 2), che è più astratta, ma sempre elementare.

[TomSawyer]

Ok, buona dimostrazione, anche se hai omesso qualche passaggio delicato.

Immagino tu ti riferisca alla parte finale. Vedo di rimediare, se intendi questi passaggi.
Poiché $g$ è un elemento primitivo, si ha per definizione che $F={0,g^0, g^1,\ldots,g^{p-2}}$. I modi di esprimere un $n \in F$ come somma di due elementi di $F$ sono $(p+1)/2$, come detto, e le varie somme sono del tipo $n=0+n=1+(n-1)=2+(n-2)=\ldots$, dove le somme si estendono anche a $n+p$, se $n \ne p-1$; quindi tra tutti i $p+1$ operandi c'è un solo elemento ripetuto. Perciò anche gli indici (gli esponenti) si comportano allo stesso modo, facendo in modo che almeno in una di queste somme ci siano due esponenti pari ($n=g^k+g^j$, con $k,j$ pari) o che $n$ sia la somma tra $0$ e una potenza pari di $g$.

[fields]

Ok, Crook. Da quanto hai scritto ho notato che il tuo metodo si generalizza facilmente ai campi finiti di ordine dispari. I campi di ordine pari possiamo tralasciarli perché cedono subito, riguardo al nostro problema.

Ecco la struttura della soluzione, per chi vuole risolvere il 2).

Sia $G$ un gruppo abeliano finito di ordine dispari e sia $a\in G$. Calcolare il numero di coppie (non ordinate) ${x,y}$ di elementi di $G$ tali che $a=xy$.

Fatto questo il metodo di Crook si applica come nel caso $F=ZZ_p$. Naturalmente il calcolo delle coppie si riferisce a $(F,+)$.

[TomSawyer]

EDIT: Avevo postato una soluzione del secondo con lo stesso metodo, ma lascio a qualcun altro.

[fields]

EDIT: Avevo postato una soluzione del secondo con lo stesso metodo, ma lascio a qualcun altro.

Non credo che ci sia un nugolo di aspiranti solutori che si vogliono gettare sul problema... Quindi, perché sprecare ciò che hai scritto?

[TomSawyer]

. E' che e' talmente identico. Vabbe', basta considerare che i modi per esprimere un $n \in F$ come somma di due elementi di $F$ sono $(p^m+1)/2$, dove $p^m$ e' l'ordine del campo, e che tra i $p^m+1$ operandi delle $(p^m+1)/2$ somme e' presente ogni intero di $[0,p^m-2]$. Ora basta osservare come prima che succedera' almeno una volta che $n=g^k+g^j$ o che $n=g^k+0$, con $j,k$ pari e $g$ tale che $F={0,g^0,g^1,\ldots,g^{p^m-2}}$.

Che metodo hai usato tu?

[fields]

Vabbe', basta considerare che i modi per esprimere un $n \in F$ come somma di due elementi di $F$ sono $(p^m+1)/2$, dove $p^m$ e' l'ordine del campo

Be' è questo il punto che si differenzia dal primo caso... Attenzione che non tutti gli elementi di $F$ sono necessariamente esprimibili come $1+1+1....+1$, ad esempio quando il campo ha caratteristica $p$ e $|F|>p$. Quindi il calcolo delle coppie e' diverso.

[TomSawyer]

Allora spiegami dove sbaglio: una rappresentazione isomorfa di $F(p^m)$ è fatta con polinomi di grado al massimo $m-1$ e coefficienti in $ZZ_p$. E per rappresentare un polinomio in $F(p^m)$ come somma di due polinomi sempre di $F(p^m)$, ci sono $(p^m+1)/2$ modi. E' sbagliato il numero di modi?