backup del Post

Una dimostrazione più grande di tutta Wikipedia

Da Liverpool non sono solo arrivati i Beatles. È notizia di questi giorni che Alexei Lisitsa e Boris Konev dell’Università di Liverpool hanno pubblicato un preprint in cui fanno un passo avanti verso la risoluzione del problema delle discrepanze di Erdős… o meglio lo fanno fare al computer, visto che la dimostrazione occupa più spazio dell’intera base dati di Wikipedia. Beh, meglio raccontare la storia dall’inizio.

Ho già parlato un paio di volte (qui e qui) del matematico Paul Erdős e delle sue eccentricità. Una sua caratteristica – decidete voi se è eccentrica o no – era quella di sparare congetture a raffica e vedere se lui o qualcun altro riusciva a risolverle. Il problema delle discrepanze (c’è un qualche accenno su Wikipedia) è appunto una di queste congetture: come molti problemi in teoria dei numeri è relativamente facile da esporre, molto meno da dimostrare.

Erdős partiva considerando le successioni infinite di +1 e -1, se si chiedeva se potesse essercene qualcuna abbastanza “equilibrata”, oppure – come lui credeva – no. La definizione di “successione equilibrata” consisteva nel partire dalla successione, prendere una sottosuccessione qualunque – dove per sottosuccessione si intendono gli elementi di posto d, 2d, 3d, …, kd – fare la somma dei valori e non trovarsi mai troppo lontano da zero. Detto in altri termini, la somma (algebrica) dei primi k numeri, o la somma dei primi k numeri in posizione pari, o quella dei primi k numeri in posizione multipla di 42 doveva essere sempre minore in valore assoluto di un certo C. Però, secondo Erdős, questo non era possibile: in qualunque modo si mettessero i +1 e i -1 si poteva sempre trovare una sottosuccessione la cui somma abbia valore assoluto (la discrepanza, appunto) grande a piacere. La congettura appare in un articolo del 1957, ma Erdős scrisse che ci pensava dagli anni 1930, tanto che offrì 500$ per chi l’avesse risolta. Quella di mettere una taglia su un problema era un’altra peculiarità di Erdős; quella era una delle cifre più alte che avesse mai offerto, il che la dice lunga su quanto ritenesse complicato il problema.

Qualche esempio potrà forse far capire meglio cosa succede. Se immaginiamo una successione di tutti +1, naturalmente la discrepanza è infinita. Quindi dobbiamo cercare per quanto possibile di avere un numero simile di +1 e di -1. Ma la successione +1 -1 +1 -1 +1 -1 ... non funziona mica; se prendiamo la sottosuccessione delle posizioni pari abbiamo -1 -1 -1 -1... che di nuovo va all’infinito ancorché negativo. Possiamo pensare allora a scrivere qualcosa di più complicato, come +--+-++--++-+--+... dove per comodità ho scritto + invece che +1 e – anziché -1; questa successione è costruita per ricorsione, aggiungendo ogni volta l’opposto di quanto già presente. Non ho avuto voglia di fare i conti completi, ma già così i primi multipli di 3 sono -+---, il che significa che la discrepanza di questa successione è almeno 3.

Però è chiaro che non possiamo andare avanti in questo modo, facendo ipotesi e testandole una a una: occorre un approccio un po’ più scientifico. In pratica quello che vorremmo dimostrare è che, data una successione infinita di +1 e -1, troviamo sempre delle sottosuccessioni di discrepanza grande a piacere. Ma iniziamo in piccolo: se Erdős ha ragione, dato un qualunque valore C possiamo trovare una successione finita abbastanza lunga la cui discrepanza è maggiore di C. Visto che una successione infinita ha comunque una parte iniziale finita, saremmo a posto. Proviamo allora a sporcarci un po’ le mani: costruirò esplicitamente una successione di 11 elementi di discrepanza 1, cioè per cui la somma di qualunque sottosuccessione è -1, 0 oppure 1.

Possiamo scegliere senza perdita di generalità +1 come primo elemento: con -1 si farebbe infatti lo stesso ragionamento a segni invertiti. Questo ci obbliga però ad avere come secondo elemento -1, perché altrimenti la sottosuccessione (1,2) avrebbe somma 2. Ma allora l’elemento 4 deve essere +1, perché altrimenti la sottosuccessione (2,4) avrebbe somma -2, e l’elemento 8 deve essere -1. Abbiamo così ottenuto la prima riga nella tabella qui a destra. A questo punto l’elemento 3 non può essere +1, perché altrimenti la sottosuccessione (1,2,3,4) avrebbe somma 2; dunque è -1, e l’elemento 6 è +1. Siamo arrivati alla seonda riga della tabella. Il prossimo passo è avere -1 in posizione 5 e +1 in posizione 10, poi +1 in posizione 7 e -1 in posizione 9; per la posizione 11 si può infine scegliere a piacere +1 o -1. Queste due (e le due ottenute sostituendo +1 a -1 e viceversa) sono le uniche disposizioni possibili con discrepanza 1.

Proviamo ora a inserire un dodicesimo elemento. Visto che quello in posizione 6 è un +1, dovrebbe essere un -1; ma visto che le posizioni 3 e 9 hanno un -1, la sottosuccessione (3,6,9,12) avrebbe somma -2. Senza provare tutte le 4096 possibilità di assegnare +1 e -1, abbiamo così dimostrato che una successione di almeno 12 elementi ha discrepanza maggiore o uguale a 2. E poi? Ecco, qui iniziano i Veri Problemi. Mentre con la discrepanza 1 i vincoli erano così stretti che ho potuto fare i conti a mano, già con la discrepanza 2 le possibilità aumentano in maniera esponenziale. Non ci sono così stati molti progressi in questo mezzo secolo; anche quando i pazzi di Polymath – un gruppone di matematici che si mettono tutti insieme ad attaccare un problema, ne ho parlato qui a proposito della congettura dei primi gemelli – hanno provato a mettersi all’opera, il massimo che avevano ottenuto era trovare una successione di lunghezza 1124 e discrepanza 2.

Lisitsa e Konev hanno invece pensato di usare SAT Solver, un programma che implementa le tecniche di Soddisfacibilità booleana; in altre parole hanno tradotto l’enunciato del problema in modo tale che fosse possibile definire se la risposta era “vero o falso” (per una successione finita questo è sempre possibile, perché il numero di combinazioni è finito) e hanno fatto girare il programma perché scrivesse i passaggi logici necessari per arrivare alla soluzione. Il risultato è stato che hanno esplicitamente trovato una successione di lunghezza 1160 e di discrepanza 2; verificare questo fatto è relativamente semplice. Ma soprattutto hanno fatto dimostrare al SAT Solver che non esistono successioni di lunghezza 1161 e discrepanza 2. Il piccolo guaio è che appunto i passi formali della dimostrazione occupano 13 GB, e per fare un confronto la base dati di Wikipedia (d’accordo, questa è compressa…) si limita ad occupare 10 GB.

Questo non è certo il primo caso di dimostrazione tendenzialmente impossibile da verificare per un essere umano; sono già passati quarant’anni dalla dimostrazione del teorema dei quattro colori, che anch’essa richiede un computer per verificare tutti i casi. Questo non è un grande problema; per verificare il risultato basta scrivere una nuova implementazione di un SAT Solver e riscrivere da capo in maniera booleana il risultato da provare. Il vero problema è che siamo passati dall’aver dimostrato che il minimo valore è 2 all’aver dimostrato che il minimo valore è 3: considerando che la congettura afferma che non c’è minimo valore, o se preferite dirlo in maniera naïf questo valore è infinito, capirete che non si è fatto chissà quale passo. D’altra parte questo approccio non potrebbe nemmeno dimostrare mai la congettura, o se preferite confutarla, ma solo trovare valori sempre maggiori di C. E probabilmente non riuscirà nemmeno a fare questo: per dire, al momento gli autori hanno scoperto una successione di lunghezza 13000 e discrepanza 3, ma non sono ancora riusciti a testare successioni più lunghe perché il SAT Solver non ce la fa… Insomma, se qualcuno vuole mettere le mani sul problema può ancora farcela!