Campi finiti e somma di quadrati

Una conseguenza del noto teorema di Fermat è che un numero intero può essere rappresentato come somma di due quadrati se e solo se esso è non negativo e non contiene nella sua fattorizzazione alcun primo congruente a $3$ modulo $4$ elevato ad una potenza dispari [1].

Viene dunque naturale chiedersi cosa accade su altri anelli commutativi: ad esempio, su $\mathbb{R}$ un elemento è somma di quadrati se e solo se è non negativo.

Un caso particolarmente interessante è quello dei campi finiti $\mathbb{F}_q$, dove $q$ è la potenza di un primo. In tal caso si ha infatti a disposizione il seguente importante risultato, vedi [2, Chapter I, Corollary 2]:

Teorema 1 (Chevalley). Ogni forma quadratica in tre variabili su un campo finito $\mathbb{F}_q$ ha almeno uno zero non banale. 

In termini geometrici, ciò può esprimersi dicendo che ogni conica proiettiva su $\mathbb{F}_q$ ha un punto razionale (cioè, un punto a coordinate nel campo di definizione) e quindi, tramite proiezione stereografica da tale punto, essa è isomorfa alla retta proiettiva su $\mathbb{F}_q$.

Si noti che vi sono campi infiniti in cui esistono coniche proiettive senza alcun punto razionale; ad esempio la conica $X^2+Y^2 -3Z^2=0$ non ha punti definiti su $\mathbb{Q}$: ciò segue dal fatto che l’equazione diofantea deomogeneizzata $x^2+y^2-3=0$ non ha soluzioni in numeri razionali, vedi ad esempio [3].

Come corollario del Teorema di Chevalley, otteniamo un sorprendente risultato sulla rappresentabilità di ogni elemento di $\mathbb{F}_q$ come somma di quadrati. Nel seguito, diremo che una forma quadratica $Q$ su un $\mathbb{F}_q$-spazio vettoriale $V$ “rappresenta $a \in \mathbb{F}_q$” se esiste un vettore non nullo $v \in V$ tale che $Q(v)=a$.

Teorema 2. Ogni elemento del campo finito $\mathbb{F}_q$ si esprime come somma di due quadrati in $\mathbb{F}_q$.

Dimostrazione. Fissato $a \in \mathbb{F}_q$, si consideri la forma quadratica $X^2+Y^2-aZ^2$. Per il Teorema di Chevalley, essa ha uno zero non banale $(X_0, \, Y_0, \, Z_0)$.

Se $Z_0=0$, allora $Q(X, \, Y)=X^2+Y^2$ ha uno zero non banale $(X_0, \, Y_0)$ e, per risultati generali sulle forme quadratiche che ammettono vettori isotropi non nulli, segue che $Q$ rappresenta ogni elemento di $\mathbb{F}_q$, vedi [2, Chapter IV, Corollary to Proposition 3]. In particolare, essa rappresenta $a$ e  abbiamo finito. Se invece $Z_0 \neq 0$ allora, posto $u=X_0/Z_0$ e $v=Y_0/Z_0$, otteniamo $u^2+v^2=a$ e possiamo di nuovo concludere.

                                                                                                                                                 $\Box$

È interessante notare che è possibile dare una semplice dimostrazione del Teorema 2 che non dipende dal Teorema 1, e che sfrutta invece il seguente argomento combinatorio. 

Se $\mathrm{char}(\mathbb{F}_q)=2$, allora $x^2+y^2=(x+y)^2$, dunque $a$ è somma di quadrati in $\mathbb{F}_2$ se e solo se è esso stesso un quadrato, e ciò è sempre vero dato che in caratteristica $2$ la mappa $x \mapsto x^2$ è l’endomorfismo di Frobenius, che è suriettivo.

Supponiamo allora $\mathrm{char}(\mathbb{F}_q)$ dispari, nel qual caso i quadrati non-nulli di $\mathbb{F}_q$ formano un sottogruppo di indice $2$ del gruppo moltiplicativo $(\mathbb{F}_q)^*$, più precisamente essi sono il nucleo dell'omomorfismo $x \mapsto x^{(q-1)/2}$, che assume valori in $\{1, \, -1\}$, vedi [2, Chapter I, Thm. 4].

Pertanto, il sottoinsieme $S$ di tutti i quadrati di $\mathbb{F}_q$ consiste di $(q+1)/2$ elementi e, quindi, lo stesso vale per il suo traslato $a-S$. Siccome $\mathbb{F}_q$ possiede $q$ elementi, per il principio dei cassetti deve esistere uno di essi contenuto nell’intersezione $S \cap (a-S)$, cioè esistono $x, \, y \in \mathbb{F}_q$ tali che $x^2=a-y^2$, come volevamo.

Il riferimento bibliografico [2] è un grande classico, una lettura obbligata per chiunque sia interessato alla Teoria dei Numeri. Lo stile di J. P. Serre è, come sempre, preciso, conciso, dritto al punto: niente fronzoli, solo splendida Matematica. 

Il titolo originale "Cours d'Arithmétique" viene dal fatto che, in francese, "Arithmétique" vuol dire sia "Aritmetica Elementare" che "Teoria dei Numeri", il che a volte è fonte di equivoci.  Parecchi anni fa ero in metropolitana a Parigi e per qualche motivo lo stavo consultando, quando, ad un certo punto, una vecchina seduta di fianco a me indicò la copertina e, guardandomi fisso, mi disse "C'est très bien que, meme à votre âge, vous souhaitiez apprendre les choses de base!".

Riferimenti.

[1] https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem
[2] J. P. Serre: A course in Arithmetic, GTM 7, Springer 1973
[3] https://math.stackexchange.com/questions/2483195/proof-that-x2-y2-3-has-no-rational-solutions

Terne pitagoriche monocromatiche e meccanizzazione della Matematica

Un famoso problema, posto da R. Graham, chiedeva se sia possibile colorare gli interi positivi con due colori (ad esempio, rosso e blu), in modo tale che non esista alcuna terna pitagorica monocromatica, cioè, nessuna tripla $a, \,b, \, c$ di interi dello stesso colore e tali che $a^2+b^2=c^2$.

Nel 2016, la questione venne risolta in senso negativo da tre informatici, M. Heule, O. Pullman e V. Marek, i quali dimostrarono il seguente risultato [HPM16]:

Teorema. Esiste una bi-colorazione di $\{1, \ldots, 7824\}$ che non contiene nessuna terna pitagorica monocromatica. Invece, non esiste nessuna tale bi-colorazione per $\{1, \ldots, 7825\}$.

La dimostrazione di questo enunciato è stata ottenuta utilizzando in modo essenziale il calcolatore. Più precisamente, i tre autori hanno costruito, per ogni $n$, una formula preposizionale che descrive una bi-colorazione di $\{1, \ldots, n\}$ senza terne pitagoriche monocromatiche. Successivamente, hanno implementato questa formula in un software specificamente progettato per la Logica Matematica (‘’SAT solver’’), cercando soluzioni per specifici valori di $n$.

Per $n=7824$ la ricerca è stata coronata da successo, e il software ha fornito una bi-colorazione esplicita che risolve il problema. Per $n=7825$, invece, nessuna tale colorazione è stata trovata.

Ovviamente, nel caso “negativo”, è rischioso accettare il responso del computer come una dimostrazione rigorosa della non-esistenza di una soluzione. Infatti, bisogna innanzitutto essere sicuri che l’algoritmo sia corretto ed esaustivo e che la macchina funzioni perfettamente; inoltre, molti matematici non sono pronti a considerare come soddisfacente una dimostrazione di impossibilità che non possa essere verificata “a mano’’ (si ricordi il famoso caso del Teorema dei Quattro Colori).

Heule, Pullman e Marek hanno dunque deciso di codificare la dimostrazione per mezzo di un procedimento di “validazione formale del risultato”, che ha prodotto un certificato di 68 gigabyte, che che è stato reso pubblicamente disponibile e contiene abbastanza informazioni per permettere a chiunque (almeno in linea di principio) di riprodurre la dimostrazione.

Questo esempio mostra che siamo arrivati ad un punto nel quale le dimostrazioni “computer assisted” cominciano a diventare essenziali in Matematica, facendoci riconsiderare (almeno in alcuni casi) il nostro concetto di “dimostrazione rigorosa”. Tutto ciò apre scenari affascinanti, e per certi versi inquietanti, sulla “meccanizzazione della Matematica”, che sarebbe troppo lungo considerare qui; il lettore interessato può leggere ad esempio [Av18].

Riferimenti.

[HPM16] M. Heule, O. Pullman e V. Marek: Solving and verifying the Boolean Pythagorean Triples via Cube-an-Conquerer, arXiv:1605.00723.

[AV18] J. Avigad: The Mechanization of Mathematics, Notices AMS 65, number 6 (2018).