Somme di quadrati
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).
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).
Risposte
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.
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.
Ok, buona dimostrazione, anche se hai omesso qualche passaggio delicato.
Rimane ora la dimostrazione della 2), che è più astratta, ma sempre elementare.
Rimane ora la dimostrazione della 2), che è più astratta, ma sempre elementare.
"fields":
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$.
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,+)$.
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,+)$.
EDIT: Avevo postato una soluzione del secondo con lo stesso metodo, ma lascio a qualcun altro.
"Crook":
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? 
. 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?
"Crook":
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.
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?
"Crook":
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?
No, no, è giusto! Ma chi lo sapeva che stavi argomentando con i polinomi, non ho mica la sfera di cristallo!
Avevi scritto: "tra i $p^m+1$ operandi delle $(p^m+1)/2$ somme e' presente ogni intero di $[0,p^m-2]$" quindi credevo che stessi parlando di naturali...
Questa è la mia soluzione che estende la prima prova di Crook.
Sia $G$ un gruppo finito abeliano di ordine dispari e sia $a\in G$. Allora il numero di sottinsiemi ${x,y}$ di $G$ tali che $a=xy$ e' esattamente $(|G|+1)/2$ e inoltre tali sottinsiemi sono uguali o disgiunti e $y!=x$ per tutti i sottinsiemi in questione all'infuori di uno.
Osserviamo che, per ogni $x,y\in G$, $a=xy$ sse $y=ax^(-1)$. Dunque per ogni $x\in G$ esiste un solo $y$ in $G$ tale che $a=xy$. Pertanto ci sono esattamente $|G|$ coppie ordinate $(x,y)$ tali che $a=xy$: sia $S$ l'insieme di tali coppie ordinate.
Le coppie di $S$, viste come insiemi, sono uguali o disgiunte, perche' se $y!=z$, allora $xy!=xz$, e dunque non puo' essere che $xy=a=xz$.
Poiche' inoltre $G$ e' di ordine dispari ci puo' essere al massimo un $x$ tale che $x^2=a$: sia infatti $y^2=a$. Abbiamo allora $x^2=y^2$ e dunque $(xy^(-1))^2=1$, e dunque, dato che l'ordine di un elemento divide l'ordine del gruppo, deve essere $xy^(-1)=1$ e dunque $x=y$. D'altra parte poiche' $G$ e' abeliano, $(x,y)\in S$ sse $(y,x)$ in $S$. Ma $|S|$ e' dispari. Quindi deve esserci esattamente un $x$ tale che $(x,x)\in S$.
In conclusione, ci sono, viste come insiemi, $(|G|-1)/2+1=(|G|+1)/2$ coppie distinte in $S$, che e' la tesi.
Poi la prova si conclude come Crook.
Sia $G$ un gruppo finito abeliano di ordine dispari e sia $a\in G$. Allora il numero di sottinsiemi ${x,y}$ di $G$ tali che $a=xy$ e' esattamente $(|G|+1)/2$ e inoltre tali sottinsiemi sono uguali o disgiunti e $y!=x$ per tutti i sottinsiemi in questione all'infuori di uno.
Osserviamo che, per ogni $x,y\in G$, $a=xy$ sse $y=ax^(-1)$. Dunque per ogni $x\in G$ esiste un solo $y$ in $G$ tale che $a=xy$. Pertanto ci sono esattamente $|G|$ coppie ordinate $(x,y)$ tali che $a=xy$: sia $S$ l'insieme di tali coppie ordinate.
Le coppie di $S$, viste come insiemi, sono uguali o disgiunte, perche' se $y!=z$, allora $xy!=xz$, e dunque non puo' essere che $xy=a=xz$.
Poiche' inoltre $G$ e' di ordine dispari ci puo' essere al massimo un $x$ tale che $x^2=a$: sia infatti $y^2=a$. Abbiamo allora $x^2=y^2$ e dunque $(xy^(-1))^2=1$, e dunque, dato che l'ordine di un elemento divide l'ordine del gruppo, deve essere $xy^(-1)=1$ e dunque $x=y$. D'altra parte poiche' $G$ e' abeliano, $(x,y)\in S$ sse $(y,x)$ in $S$. Ma $|S|$ e' dispari. Quindi deve esserci esattamente un $x$ tale che $(x,x)\in S$.
In conclusione, ci sono, viste come insiemi, $(|G|-1)/2+1=(|G|+1)/2$ coppie distinte in $S$, che e' la tesi.
Poi la prova si conclude come Crook.
Questa e' la mia soluzione.
Sia $F$ campo finito di ordine dispari $n$, $F^x$ il gruppo moltiplicativo di $F$ (ovvero $(F-{0},*))$, $S$ l'insieme delle somme di due quadrati privato di $0$
e $Q$ l'insieme dei quadrati di $F^x$. Naturalmente $Q$ e' un sottogruppo di $F^x$ e $Q\sube S$. Anche $S$, tuttavia, e' un sottogruppo di $F^x$, in base alla nota identita', $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ab+cd)^2$.
Poiche' inoltre $F^x={g^0,g,g^2,....,g^(n-2)}$, per qualche $g\in F^x$, ${g^0,g^2,g^4,....,g^(n-3)}\sube Q$ e dunque $|Q|>=|F^x|/2$.
Caso 1) $S!=Q$. In questo caso $|S|>|F^x|/2$. Essendo pero' $S$ un sottogruppo di $F^x$, $|S|$ divide $|F^x|$ e dunque deve essere $S=F^x$, e dunque $S=F$.
Caso 2) $S=Q$. In questo caso $S uu {0}$ e' un sottogruppo di $(F,+)$. Infatti se $a^2+b^2\in Suu{0}$ e $c^2+d^2\in Suu{0}$, allora $a^2+b^2=x^2$ e $c^2+d^2=y^2$ per qualche $x,y\in F$. Dunque $a^2+b^2+c^2+d^2=x^2+y^2\in Suu{0}$.
Ma $0\notin Q$, dunque $|Suu{0}|>=|F^x|/2+1=(|F^x|+2)/2>|F|/2$, e ancora una volta, dovendo $|Suu0|$ dividere $|F|$, dev'essere $Suu{0}=F$.
Sia $F$ campo finito di ordine dispari $n$, $F^x$ il gruppo moltiplicativo di $F$ (ovvero $(F-{0},*))$, $S$ l'insieme delle somme di due quadrati privato di $0$
e $Q$ l'insieme dei quadrati di $F^x$. Naturalmente $Q$ e' un sottogruppo di $F^x$ e $Q\sube S$. Anche $S$, tuttavia, e' un sottogruppo di $F^x$, in base alla nota identita', $(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ab+cd)^2$.
Poiche' inoltre $F^x={g^0,g,g^2,....,g^(n-2)}$, per qualche $g\in F^x$, ${g^0,g^2,g^4,....,g^(n-3)}\sube Q$ e dunque $|Q|>=|F^x|/2$.
Caso 1) $S!=Q$. In questo caso $|S|>|F^x|/2$. Essendo pero' $S$ un sottogruppo di $F^x$, $|S|$ divide $|F^x|$ e dunque deve essere $S=F^x$, e dunque $S=F$.
Caso 2) $S=Q$. In questo caso $S uu {0}$ e' un sottogruppo di $(F,+)$. Infatti se $a^2+b^2\in Suu{0}$ e $c^2+d^2\in Suu{0}$, allora $a^2+b^2=x^2$ e $c^2+d^2=y^2$ per qualche $x,y\in F$. Dunque $a^2+b^2+c^2+d^2=x^2+y^2\in Suu{0}$.
Ma $0\notin Q$, dunque $|Suu{0}|>=|F^x|/2+1=(|F^x|+2)/2>|F|/2$, e ancora una volta, dovendo $|Suu0|$ dividere $|F|$, dev'essere $Suu{0}=F$.
"fields":
[quote="Crook"]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?
No, no, è giusto! Ma chi lo sapeva che stavi argomentando con i polinomi, non ho mica la sfera di cristallo!
Avevi scritto: "tra i $p^m+1$ operandi delle $(p^m+1)/2$ somme e' presente ogni intero di $[0,p^m-2]$" quindi credevo che stessi parlando di naturali...[/quote]Sì, come uno stupido, pensavo in termini di polinomi e ho scritto di interi.
Non possiedo il rigore formale e le conoscenze, per argomentare soluzioni come le tue. Me le studio per bene. Saluti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo