backup del Post

La dimostrazione matematica più lunga

Uno dei campi più strani della matematica è la teoria di Ramsey. La sua stranezza non sta certo nella complessità dei suoi teoremi, che possono essere descritti anche a un ragazzino. Il teorema di Ramsey, per esempio, considera i grafi completi di grado n, cioè le configurazioni formate da n punti e da tutti i segmenti che uniscono una coppia qualunque di punti: potremmo insomma dire che abbiamo un n-gono con tutte le diagonali, ma dobbiamo ricordarci che lati e diagonali sono in questo contesto la stessa cosa. Il teorema afferma che se scegliamo un numero qualunque c di colori diversi per colorare i segmenti e un numero naturale k, allora esiste un numero N tale che il grafo completo di N punti conterrà sicuramente un sottografo completo di ordine k i cui segmenti sono di un solo colore. Il guaio è che le dimostrazioni nella teoria di Ramsey sono spesso molto complicate, perché il numero di elementi in gioco cresce più che esponenzialmente; per i risultati di esistenza e si riescono solo a fare stime grossolane. Tanto per dire, è facile dimostrare che se c=2 e k=3 allora il più piccolo N è 6: quindi se si disegna un esagono con tutte le sue diagonali e si colorano lati e diagonali in rosso oppure in blu siamo certi di avere un triangolo tutto rosso oppure tutto blu. Ma già se k=5 nessuno sa qual è il più piccolo valore di N, e per k=6 nessuno sa se sapremo mai la risposta. Roberto Zanasi lo racconta qui e qui.

Bene. Un problema della teoria di Ramsey si chiama “delle terne pitagoriche booleane”, che detto così sembra un’arma impropria, ma non è poi così difficile. Una terna pitagorica è una tripletta di numeri naturali (a, b, c) tali che a²+b²=c². Esempi di terne pitagoriche sono (3,4,5), (5,12,13) e così via. Immaginiamo ora di colorare tutti i numeri naturali di rosso o di blu – ecco il perché del “booleano”, che non significa altro che “una di due possibilità”, e chiediamoci se è possibile farlo in modo tale che non esista una terna pitagorica con tutti i numeri dello stesso colore; o se preferite esprimere la cosa in formato più matematico, che è possibile dividere gli interi in due insiemi tale che nessuno di essi contenga una terna pitagorica. No, non è possibile; più precisamente, lo si può fare con l’insieme {1, …, 7824} ma non con {1, …, 7825} (e quindi con limite massimo maggiore). Il risultato è stato dimostrato (al calcolatore… usando tecniche della cosiddetta soddisfacibilità booleana) nel 2016: la dimostrazione ha richiesto quattro anni di tempo CPU di un supercomputer e occupa 200 terabyte di spazio, che però si possono comprimere per trasportarla in giro in “soli” 68 gigabytes. Non so se la dimostrazione completa sia disponibile in rete, però :-)