Quest’estate ha avuto molto risalto la notizia che il numero 42 si può scrivere come somma di tre cubi. Alessandro Zaccagnini ci spiega perché questo problema era difficile (e qual è il prossimo da risolvere) e ci accompagna in un piccolo giro tra i problemi chiamati “additivi”.

I fan di Douglas Adams e quelli di Lewis Carroll non hanno bisogno di spiegazioni: è chiaro che 42 è un numero decisamente interessante, e basta. Rimando alle pagine di Wikipedia per un elenco dettagliato di proprietà di 42, non solo matematiche, che lo rendono molto popolare. Io aggiungo l’osservazione, a quanto pare tanto originale quanto futile, che \(10!\) secondi sono esattamente 42 giorni; Alberto Saracco, che i lettori di MaddMaths! conoscono bene e ha letto una prima bozza di questo articolo, ha immediatamente replicato che \(5!\) secondi sono solo 2 minuti, e questo dà un’idea della rapida crescita del fattoriale.

Ma veniamo subito al motivo per cui 42 è salito alla ribalta quest’estate, quando A. Booker (Bristol) & A. Sutherland (MIT) hanno annunciato di aver risolto l’equazione \[42 = x^3 + y^3 + z^3\] in numeri interi \(x\), \(y\), \(z\), uno dei quali negativo. La soluzione che hanno trovato è \(x = -80538738812075974\), \(y = 80435758145817515\), \(z = 12602123297335631\). I lettori che vogliono verificare la correttezza di questo risultato sono invitati a fare molta attenzione allo strumento che usano, supponendo che non abbiano voglia di fare queste operazioni con carta e matita: è necessario servirsi di un “pacchetto” di aritmetica a precisione arbitraria; in caso contrario, si può trovare un risultato quasi casuale, perché le calcolatrici abitualmente disponibili sui computer arrotondano i numeri interi cosí grandi e passano dalla rappresentazione in virgola fissa a quella in virgola mobile, con dei “piccoli” errori di calcolo. Questi errori sono piccoli rispetto alla grandezza di \(x^3\), \(y^3\) e \(z^3\) ma non rispetto alla grandezza di \(x^3 + y^3 + z^3\), che vale per l’appunto 42 ed è molto piú piccolo del valore assoluto di ciascun addendo.

Fino a questo momento, ma solo per pochi mesi, 42 era il piú piccolo intero positivo \(n\) per cui non si sapeva se l’equazione \[n = x^3 + y^3 + z^3\] ha soluzione in numeri interi, non necessariamente positivi. Ora il primato spetta a 114.

Osserviamo subito una cosa importante che riprenderemo piú avanti negli altri casi che discuteremo. Ci sono alcuni interi, un’infinità in effetti, per cui possiamo dire a priori, e quasi senza fare calcoli, che questa equazione non ha soluzione, per quanto grandi possano essere scelti \(x\), \(y\) o \(z\). Il piú piccolo intero positivo per cui questa equazione non ha soluzione è 4, e il successivo è 5; poi ci sono 13 e 14, 22 e 23, 31 e 32, 40 e 41, …In generale, se \(n\) è della forma \(\pm 4 + 9 k\), dove \(k\) è un numero intero, l’equazione qui sopra non può avere soluzione perché c’è un ostacolo, un’ostruzione di natura aritmetica; la spiegazione è questa: se consideriamo i possibili valori di \(x^3\) modulo 9, troviamo solo 0, 1, 8, o, piú brevemente, 0, \(\pm 1\). Lo stesso vale, evidentemente, per i valori di \(y^3\) e \(z^3\); provando tutte le 27 combinazioni possibili, si scopre che il valore di \(x^3 + y^3 + z^3\) modulo 9 non è mai \(\pm 4\). Il matematico britannico Roger Heath-Brown, che ha dato importantissimi contributi alla Teoria dei Numeri, ha congetturato che per ogni intero positivo \(n\), escludendo i valori appena indicati, l’equazione qui sopra ha infinite soluzioni. Notiamo incidentalmente che per \(n = 0\) l’equazione diventa quella di Fermat, e sappiamo che non ha soluzione, anche se la dimostrazione, dovuta a Eulero e Legendre, è piuttosto sofisticata; la si può trovare nel paragrafo 13.4 del famoso libro di Hardy & Wright ^{[1 ]}G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, sixth ed., Oxford University Press, Oxford, 2008.

L’idea di base dell’algoritmo scoperto da Booker per risolvere il caso \(n = 33\) è quella di scrivere l’equazione qui sopra nella forma alternativa \[n – z^3 = x^3 + y^3 = (x + y) (x^2 – x y + y^2)\] e usare il fatto che \(x + y\) divide \(n – z^3\). Questo porta ad una drastica riduzione dei tentativi che il computer deve fare nella ricerca di una soluzione. I fan di Douglas Adams apprezzeranno senz’altro il fatto che il calcolo è stato “distribuito” su una rete di centinaia di migliaia di computer dislocati su tutto il pianeta. Decisiva, a questo scopo, è stata l’esperienza di Sutherland nel cosiddetto calcolo parallelo, in cui molti processori, quasi mezzo milione in questo caso, lavorano simultaneamente su frammenti del problema.

Per inciso, notiamo l’enorme differenza che intercorre tra la dimostrazione o scoperta di un fatto matematico e la sua, pur doverosa, verifica. In questo caso, la ricerca ha richiesto molti milioni di ore, mentre per la verifica basta una frazione di secondo, anche su un portatile commerciale, purché dotato di software adatto al calcolo esatto.

Problemi additivi

Prendiamo lo spunto da questa recentissima scoperta per parlare in generale di problemi additivi in Teoria dei Numeri. Passeremo subito a descrivere esempi concreti, ma cominciamo enunciando in astratto il nostro obiettivo. Abbiamo a disposizione un certo numero di insiemi di numeri interi (positivi o negativi) \(A_1\), \(A_2\), …, \(A_k\) e vogliamo sapere per quali interi \(n\) l’equazione \[n = a_1 + a_2 + \cdots + a_k\] è risolubile, con il vincolo che \(a_1 \in A_1\), …, \(a_k \in A_k\). In quasi tutti i casi interessanti, compresi quelli di cui parleremo qui sotto, prenderemo tutti gli insiemi \(A\) uguali fra loro; nel problema da cui siamo partiti, abbiamo 3 addendi, e quindi \(k = 3\), e prendiamo sempre l’insieme di tutti i cubi perfetti, positivi o negativi. Per brevità, considereremo solo problemi in cui questi insiemi hanno una natura moltiplicativa semplice (numeri primi, quadrati perfetti, cubi o altre potenze perfette): l’interesse e la difficoltà dei problemi additivi nascono in un certo senso dal “conflitto” fra le due operazioni aritmetiche di base, perché ci ostiniamo a sommare numeri che dovremmo invece combinare moltiplicandoli. Il prodotto di due quadrati perfetti è ancora un quadrato perfetto, i numeri primi sono definiti moltiplicativamente.

Passiamo senz’altro a qualche esempio concreto, non prima di un’ultima osservazione: se tutti gli insiemi \(A\) che consideriamo sono sottoinsiemi di \(\mathbf{N}\), in un certo senso il nostro è un problema di conteggio, perché l’equazione che vogliamo risolvere ha certamente un numero finito di soluzioni; è il caso del problema di Goldbach, per esempio. Invece, se qualcuno degli insiemi contiene infiniti interi positivi e un altro contiene infiniti interi negativi, l’equazione potrebbe avere infinite soluzioni e si pone il problema di “contarle” adeguatamente; rimanendo ai casi famosi, il problema dei primi “gemelli” rientra in questo tipo.

Problemi additivi con potenze perfette

Somme di due quadrati

Cominciamo da uno dei problemi piú eleganti e basilari di questa sezione: quali interi \(n\) si possono rappresentare come somma di due quadrati perfetti? Per quali interi positivi \(n\) l’equazione \[n = x^2 + y^2\] ha soluzione? Qui e nei problemi futuri, è sempre sottinteso che le variabili, \(x\) ed \(y\) in questo caso, siano a loro volta numeri interi, eventualmente nulli o negativi. Invito i lettori a fermarsi a questo punto e a compilare una lista dei valori di \(n\) compresi fra 1 e 40 o 50, diciamo, selezionando quelli per cui l’equazione ha soluzione. Emerge qualche tipo di regolarità?

Una cosa semplice che si può notare subito è che tra i numeri \(n\) per cui l’equazione è risolubile, non ce n’è neppure uno per cui \(n \equiv 3 \bmod 4\). La spiegazione è la stessa vista sopra, anche se questo caso è decisamente piú semplice: \(x^2\) assume solo i valori \(0\) ed \(1\) modulo \(4\), e quindi \(x^2 + y^2\) assume solo i valori \(0\), \(1\) o \(2\) modulo 4, cioè \(x^2 + y^2\) “evita” la classe \(3 \bmod 4\). In particolare, nessuno fra i numeri primi \(p \equiv 3 \bmod 4\) è nella lista degli \(n\) per cui c’è una soluzione. Viceversa, Fermat ha osservato che tutti i numeri primi \(p \equiv 1 \bmod 4\) sono nella lista degli \(n\) per cui c’è una soluzione, dando anche una dimostrazione che usa il suo metodo della discesa, una specie di induzione al contrario. Ma perché ci interessano tanto i numeri primi per cui questa equazione è o non è risolubile? Una proprietà estremamente interessante delle somme di quadrati è la formula di “composizione”: partiamo dall’identità tra numeri complessi \[(a + i b) (c + i d)
=
(a c – b d) + i (a d + b c).\] Prendendo le norme dei numeri complessi qui sopra, cioè moltiplicando ambo i membri per i propri coniugati, troviamo la relazione \[(a^2 + b^2) (c^2 + d^2)
=
(a c – b d)^2 + (a d + b c)^2.\] Questa identità è vera anche se \(a\), \(b\), \(c\), \(d\) non sono interi e può essere verificata direttamente senza usare i numeri complessi, ma è utile procedere in questo modo anche solo per motivi mnemonici. Dunque, se \(n\) ed \(m\) sono somme di quadrati, anche \(n m\) lo è! Per esempio, \(13 = 2^2 + 3^2\), \(17 = 1^2 + 4^2\) e \(221 = 13 \cdot 17 = (2 \cdot 1 – 3 \cdot 4)^2 + (2 \cdot 4 + 3 \cdot 1)^2
= 10^2 + 11^2\).

Questo spiega l’interesse per i numeri primi “rappresentabili.” Abbiamo osservato sopra che se \(p \equiv 3 \bmod 4\) allora non è rappresentabile come somma di quadrati, ma \(p^2 = 0^2 + p^2\) lo è. Aggiungiamo anche il fatto banale che \(2 = 1^2+ 1^2\). Usando tante volte la formula di composizione, se ne conclude che una condizione sufficiente affinché un intero \(n\) sia rappresentabile come somma di quadrati, cioè che l’equazione \(n = x^2 + y^2\) abbia soluzioni intere \(x\), \(y\), è che nella scomposizione in fattori primi di \(n\), eventuali fattori primi \(p \equiv 3 \bmod 4\) compaiano con esponente pari. Non è molto difficile dimostrare che la condizione è anche necessaria, utilizzando il Piccolo Teorema di Fermat per vedere che la congruenza \(x^2 \equiv -1 \bmod p\) non ha soluzione se \(p \equiv 3 \bmod 4\).

Usando questa condizione necessaria e sufficiente, è possibile dimostrare il Teorema di Landau-Ramanujan: la “maggior parte” degli interi positivi non sono rappresentabili come somma di due quadrati. In una versione leggermente indebolita, \[\lim_{N \to \infty}
\frac{\vert \{ n \le N \colon
\text{ l’equazione $n = x^2 + y^2$ \`e risolubile } \} \vert}N
=
0.\] Per correttezza storica, dobbiamo dire che Edmund Landau è stato il primo a dare una dimostrazione rigorosa del teorema vero e proprio, ma Srinivasa Ramanujan ha scoperto questo risultato e ha anche trovato un’argomentazione euristica in sostegno ma, come era suo solito, non si è preoccupato oltre. Piú o meno, il motivo per cui questo limite vale \(0\) è che un “tipico” intero grande \(n\) conterrà, nella sua fattorizzazione, qualche fattore primo \(p \equiv 3 \bmod 4\) con esponente dispari e quindi, per quanto spiegato sopra, l’equazione \(n = x^2 + y^2\) non ha soluzioni intere. Concludiamo lo studio di questo problema con un paio di osservazioni. Quello che sembra un problema “additivo” rivela un’insospettata struttura “moltiplicativa” data dalla formula di composizione. Una cosa analoga succede quando si dimostra che ogni intero positivo è somma di quattro quadrati (Teorema di Lagrange), cioè qualunque sia \(n \ge 0\) si possono trovare quattro interi \(x\), \(y\), \(z\) e \(t\) tali che \(n = x^2 + y^2 + z^2 + t^2\): un passo fondamentale è la dimostrazione di un’appropriata formula di composizione che ha la sua origine nella formula che dà il prodotto di due quaternioni.

La seconda osservazione è che per capire bene la formula di composizione nel caso della somma di due quadrati passiamo attraverso i numeri complessi, che apparentemente nulla hanno a che fare con gli interi. Ricordiamo però che per dimostrare che l’equazione di Fermat \(x^3 + y^3 + z^3 = 0\) non ha soluzioni in interi positivi o negativi, tranne quelle in cui una variabile vale 0, è necessario considerare numeri complessi della forma \(x + \omega y\) dove \(\omega = (1 + i \sqrt{3}) / 2\) ed \(x\), \(y\) sono numeri interi. Dunque, queste contaminazioni fra parti apparentemente diverse della matematica si rivelano spesso molto feconde. Notiamo per esempio che, per capire a fondo come sono distribuiti i numeri primi, è necessario passare attraverso l’analisi complessa.

Differenze di due quadrati

Facciamo un piccolo cambio nell’equazione precedente: ora ci chiediamo per quali \(n\) è possibile risolvere l’equazione \(n = x^2 – y^2\). Vedremo fra un istante che questa particolare equazione ha un numero finito di soluzioni, ma il fatto di aver cambiato un segno \(+\) in un segno \(-\) cambia la natura stessa del problema …

Invito di nuovo i lettori a fare una pausa e ad elencare gli interi fra 1 e 50 per cui l’equazione data ha soluzione. Il risultato è molto piú trasparente rispetto al caso della somma di due quadrati: si vede subito, infatti, che non sono rappresentabili come differenza di due quadrati tutti e soli gli interi \(n \equiv 2 \bmod 4\). La spiegazione è del tutto simile alla precedente: i quadrati perfetti occupano solo le classi 0 e 1 modulo 4, ed esaminando tutti i casi possibili si vede che i numeri della forma \(x^2 – y^2\) “evitano” la classe \(2 \bmod 4\).

Ricordiamo la scomposizione in fattori \(x^2 – y^2 = (x – y)(x + y)\). Ci concentriamo ora sui numeri interi dispari: in questo caso l’equazione \(n = x^2 – y^2\) ha la soluzione “banale” in cui \(x – y = 1\) ed \(x + y = n\), cioè \(x = (n + 1) / 2\), \(y = (n – 1) / 2\). Di per sé, questa non sarebbe una cosa interessante, se non fosse per un’osservazione di Fermat, e cioè che ogni altra soluzione spezza \(n\) in due fattori non banali \(d\) ed \(n / d\) prendendo semplicemente \(d = x – y\). Per esempio, \(8051 = 90^2 – 7^2\) e quindi \(8051 = (90 – 7) \cdot (90 + 7)\), cioè \(d = 83\).

Questa è l’idea alla base dell’algoritmo di fattorizzazione alla Fermat: in termini moderni, la versione originale di questo algoritmo ha una complessità computazionale troppo elevata, ma inserendo alcune semplici e brillanti idee su uno schema dovuto al matematico belga Maurice Kraitchik, Carl Pomerance ha inventato negli anni ’80 il crivello quadratico, uno dei migliori algoritmi di fattorizzazione oggi noti. Il migliore in assoluto è il crivello con i campi di numeri dovuto ai fratelli Arjen ed Hendrik Lenstra e Mark Manasse; anche questo usa come punto di partenza l’idea di Fermat e lo schema di Kraitchik, andando però in una direzione diversa da quella di Pomerance, usando anche idee di altri matematici come John Pollard. Consiglio il delizioso articolo di Carl Pomerance ^{[2 ]}C. Pomerance, A tale of two sieves, Notices American Mathematical Society 43 (1996), 1473–1485, nel quale racconta di essere stato sfidato a scomporre in fattori primi il numero 8051, quando era al liceo negli anni ’60, in meno di 5 minuti e senza usare una calcolatrice tascabile (per il buon motivo che nemmeno esistevano, all’epoca della sfida!). Per la cronaca ha perso la sfida e 20 anni dopo ha inventato il crivello quadratico.

Ma perché ci dovrebbero interessare tanto gli algoritmi di fattorizzazione? Perché i crittosistemi che usiamo, spesso inconsapevolmente, ogni volta che ci autentichiamo alla rete (social networks, bancomat, telefono cellulare) si basano sulla difficoltà di scomporre in fattori primi numeri di 200 o 300 cifre decimali: dunque, l’esistenza di “buoni” algoritmi è rilevante per la sicurezza dei nostri dati e la riservatezza delle nostre comunicazioni.

Forme quadratiche

Concludiamo questo lungo paragrafo con una discussione leggermente piú generale: ci interessano le forme quadratiche, cioè espressioni del tipo \(\phi(x, y) = a x^2 + b x y + c y^2\), dove \(a\), \(b\) e \(c\) sono numeri interi fissati; in particolare, vogliamo sapere per quali interi \(n\) l’equazione \(n = \phi(x, y)\) ha soluzioni in numeri interi \(x\), \(y\). Le forme quadratiche sono suddivise in classi a seconda del discriminante \(d = b^2 – 4 a c\). Il caso della somma di quadrati corrisponde a \(d = -4\), quello della differenza a \(d = 4\). In generale, conta il segno di \(d\); quando \(d \ge 0\) è un quadrato perfetto, il problema di risolvere \(n = \phi(x, y)\) si riduce a determinare i divisori di \(n\), eventualmente con qualche vincolo aritmetico modulo \(d\), perché \(\phi\) si spezza nel prodotto di fattori lineari, come abbiamo visto sopra.

Un caso particolarmente interessante riguarda la forma quadratica \(\phi(x, y) = x^2 – 2 y^2\), che ho trattato in dettaglio nell’articolo ^{[3 ]}A. Zaccagnini, Formato A4, L’Educazione Matematica, Anno XXIV, Serie VII 1 (2003), 47–54. Qui il discriminante è positivo ma non è un quadrato perfetto, e l’equazione \(\phi(x, y) = 1\) ha infinite soluzioni! Sapete trovarne qualcuna? Sapete dimostrare che, invece, l’equazione \(\phi(x, y) = 0\) ha solo la soluzione \((0, 0)\)? Usando un linguaggio piú geometrico, sull’iperbole di equazione \(x^2 – 2 y^2 = 1\) ci sono infinite coppie di punti a coordinate intere, mentre sull’iperbole degenere di equazione \(x^2 – 2 y^2 = 0\) c’è solo il punto \((0, 0)\). Quando \(d < 0\) la conica \(n = \phi(x, y)\) è un’ellisse, e i suoi punti a coordinate entrambe intere sono comunque un numero finito perché la curva è limitata.

Il problema di Waring

Concludiamo questa sezione ricordando che il matematico britannico Edward Waring, nelle sue Meditationes Algebraicae del 1770, ha posto in generale il problema della risolubilità dell’equazione \[n = x_1^k + x_2^k + \cdots + x_s^k,\] dove \(k \ge 2\) è un intero fissato, \(n\) è un qualsiasi intero positivo dato, \(x_1\), …, \(x_s\) sono interi non negativi, ed \(s\) può dipendere solo da \(k\). Sopra abbiamo ricordato il Teorema di Lagrange, che corrisponde al caso \(k = 2\), dove si può prendere \(s = 4\). Il problema di Waring è stato risolto da David Hilbert solo nel 1909, ma vi sono alcuni aspetti non ancora non completamente compresi, e oggetto di ricerche in corso.

Problemi additivi con numeri primi

Non possiamo terminare senza fare almeno un breve cenno ai piú famosi problemi additivi che coinvolgono numeri primi: il problema di Goldbach (binario e ternario) e quello dei primi gemelli. Nel problema di Goldbach binario ci chiediamo se sia vero che l’equazione \[n = p_1 + p_2\] sia risolubile in numeri primi \(p_1\) e \(p_2\) per ogni intero pari \(n \ge 4\). Si tratta di un’osservazione empirica di Christian Goldbach, comunicata in una lettera a Leonhard Euler nel 1742. Goldbach ha verificato qualche centinaio di casi; oggi il limite è stato spostato ad alcuni miliardi di miliardi e questa congettura ha trovato tutte le verifiche numeriche che si possano desiderare. Non vi sono motivi di dubitare della sua correttezza, ma i matematici preferiscono avere una dimostrazione rigorosa.

La congettura “coniugata” di questa è la congettura dei primi gemelli: ci chiediamo se sia vero che l’equazione \[n = p_1 – p_2\] abbia infinite soluzioni in numeri primi \(p_1\) e \(p_2\) per ogni intero pari \(n \ge 2\). Anche questa congettura è stata verificata numericamente, ma manca ancora la dimostrazione formale; un deciso passo avanti è stato fatto qualche anno fa. Ho parlato di questi problemi nel mio primo articolo divulgativo ^{[4 ]}A. Zaccagnini, Variazioni Goldbach: problemi con numeri primi, L’Educazione Matematica, Anno XXI, Serie VI 2 (2000), 47–57, quasi 20 anni fa, e qui su MaddMaths! in ^{[5 ]}A. Zaccagnini, Il cerchio si stringe intorno ai primi “gemelli, Sito web MaddMaths! (2013).

Conclusioni

Nei problemi additivi in cui tutti gli addendi sono numeri positivi c’è una “interazione” fra due aspetti: la densità degli insiemi che consideriamo (che è un problema di competenza dell’analisi matematica), e la presenza delle cosiddette “ostruzioni locali” (di competenza dell’aritmetica), cioè la necessità che gli interi \(n\) di sopra soddisfino opportune congruenze. In questo articolo abbiamo privilegiato gli aspetti aritmetici, legati alle congruenze, e quindi vogliamo terminare con un controesempio di natura opposta: non è vero che ogni intero si scrive come somma di al massimo 100 di potenze di 2. Lasciamo ai lettori il compito di trovare il piú piccolo intero \(n\) per cui l’equazione \[n = 2^{x_1} + \cdots + 2^{x_{100}}\] non ha soluzione in interi \(x_1\), …, \(x_{100}\). Il motivo per cui questo succede è che l’insieme delle potenze di 2 è troppo “sottile,” troppo poco denso. Gli insiemi considerati sopra, quadrati o cubi perfetti, o numeri primi, invece, sono ben piú densi e quindi ha senso porsi i problemi di cui abbiamo parlato.

Alessandro Zaccagnini