Recentemente molti siti di divulgazione scientifica hanno riportato la soluzione di un problema di combinatoria: la stima del limite della lunghezza di una superpermutazione minima di n elementi. Molto probabilmente il problema non avrebbe attratto tanta attenzione se non fosse per la curiosità offerta dall’identità degli scopritori: un anonimo in una lista di discussione e lo scrittore di fantascienza Greg Egan. Ce ne parla Nicola Ciccoli, che riflette sulle nuove forme di comunicazione dei risultati.

Nonostante non si tratti della prima volta che un anonimo e un dilettante (ma vedremo in che misura Egan lo è) abbiano contribuito alla soluzione di un problema matematico, la storia merita sicuramente di essere raccontata. Per spiegare come mai il problema sia stato affrontato in una lista di discussione, e anche per capire come mai la cosa sia stata osservata dalla comunità matematica con vari anni di ritardo, è necessario spiegare qualcosa del problema.

Una superpermutazione di n numeri è una stringa di numeri tra 1 e n, di lunghezza arbitraria, tale che ogni possibile permutazione dei numeri compresi tra 1 e n compaia all’interno della stringa almeno una volta. Essendo \(n!\) le possibili permutazioni di n numeri (\(n!\) si legge “n fattoriale” ed è il prodotto di tutti gli interi tra 1 e n), affiancandole una all’altra è sempre possibile trovare una superpermutazione di n numeri che sia una stringa di lunghezza \(n\times n!\). Ma è possibile fare molto meglio di così, sono possibili superpermutazioni molto più corte. La superpermutazione più corta possibile di 3 numeri è, ad esempio, 123121321. Solo 9 numeri, esattamente la metà della stringa di 18 numeri che otterremmo affiancando le 6 possibili permutazioni di 3 elementi una dopo l’altra.

Per anni si era creduto che la superpermutazione più corta di n elementi avesse un numero di cifre uguale alla somma dei fattoriali dei primi n numeri. Questa congettura, detta fattoriale, funziona fino a n=5, ma si è successivamente dimostrata errata per eccesso nel caso n=6. E’ possibile costruire una superpermutazione di 6 elementi con 872 cifre, una in meno di quelle che vorrebbe la congettura fattoriale. Qualora vi sembri strano che nell’epoca dei computer possa essere difficile calcolare la superpermutazione minima di 6 elementi mi sembra giusto farvi osservare che non si tratta solo di un numero con 872 cifre, ma che va ricercato, in assenza di teoremi generali, tra stringhe numeriche di lunghezza arbitraria (o quantomeno inferiore a 4520).

La ricerca di una formula che ci dica la lunghezza minima di una superpermutazione di n elementi ha improvvisamente ripreso vigore quando John Baez, un fisico matematico noto anche per la sua attività di divulgatore, ha scritto su Twitter un breve messaggio sul problema. Lo scrittore di fantascienza australiano Greg Egan, laureato in matematica e con alcuni lavori scientifici pubblicati all’attivo, tra cui uno proprio con Baez, incuriosito si è dedicato allo studio della questione e solo un mese dopo il tweet di Baez ha prodotto un limite superiore per la lunghezza della superpermutazione minima.

Le tecniche usate da Egan (e da altri prima di lui) sfruttano il collegamento tra il problema delle superpermutazioni e il problema del commesso viaggiatore. Supponete che il vostro commesso viaggiatore debba visitare 20 città per presentare i suoi prodotti. Qual è il cammino di minima lunghezza che gli permette di passare per tutte le città una e una sola volta? Una problema pratico che, con un po’ di riflessione si può scoprire che, oltre al commesso viaggiatore, tiene svegli manager di compagnie di spedizioni, dirigenti di linee aeree, tassisti e postini. E che pure è ben lontano dall’avere una soluzione facilmente calcolabile. Il problema del commesso viaggiatore è un esempio di problema NP-completo, ossia la classe più difficile tra i problemi non deterministici che si possono risolvere in un temo che dipende in modo polinomiale dal numero n dei casi, ed è diventato nel tempo una sorta di banco di prova per ogni algoritmo di ottimizzazione.

Il lavoro di Egan ha, come si diceva, ravvivato l’interesse sulla questione. E’ stato a questo punto che Robin Houston, il matematico che aveva verificato che la congettura fattoriale era errata per n=6, si è reso conto che una stima inferiore molto efficace (e molto vicina a quella superiore di Egan) era già presente. Non nella letteratura matematica, però. In una lista di discussione sugli anime giapponesi del 2011 ci si chiedeva quale fosse il modo più efficiente per vedere i 14 episodi della serie di Haruhi, una serie famosa per i suoi paradossi temporali, in tutti gli ordini possibili. Una superpermutazione per n=14, appunto. All’interno della discussione, condita di fraintendimenti, insulti, inviti a lasciar perdere ma anche link al lavoro di matematici e discussioni pertinenti, un anonimo proponeva il suo limite inferiore e un cenno di dimostrazione. Cenno di dimostrazione sufficiente a Houston per ricostruire una dimostrazione corretta rispetto agli attuali standard e proporre un limite inferiore alla lunghezza delle superpermutazioni che va certamente ascritto all’anonimo fan di Haruhi.

Non sappiamo ancora quale sia (se esiste) una formula per la lunghezza di una superpermutazione minima. Abbiamo un limite superiore fornito da un famoso scrittore di fantascienza e un limite inferiore fornito da un appassionato di anime giapponesi a oggi ancora anonimo. Una situazione alquanto bizzarra per la comunità dei matematici.

Non che Egan e il misterioso anonimo siano i primi matematici amatoriali ad aver ottenuto un risultato significativo. Senza uscire dagli ultimi cent’anni (prima il confine tra scienziato professionista e amatoriale era assai più labile) abbiamo la storia di Kevin Parko, un avvocato newyorkese che corresse un errore ripetuto da anni nella classificazione dei nodi e Kurt Heegner un ingegnere elettrico di Berlino che dimostrò una congettura di Gauss sulla teoria dei numeri. Ci sono il misterioso impiegato delle poste Robert Amann e la casalinga Marjorie Rice che ebbero entrambi un ruolo importante nella teoria delle tassellazioni del piano. Andrew Beal, banchiere e giocatore di poker professionista (ancora oggi detentore della vincita più grande in una singola mano: 11.7 milioni di dollari) ed esperto di teoria dei numeri. Leon Bankoff trasformato da dentista in esperto di prim’ordine di geometria. Lu Jiaxi che da sconosciuto professore di fisica in un liceo della Mongolia Interna dimostrò teoremi di combinatoria studiati da generazioni di professionisti. La lista potrebbe continuare con lo scrittore francese Raymond Queneau, autore di un articolo di combinatoria pubblicato su una rivista scientifica, e molti altri.

Forse è l’anonimo autore che ha dimostrato un teorema come esercizio in una mailing list di appassionati di cartoni animati giapponesi, dunque, a attirare di più la nostra attenzione. Certo la storia non manca di matematici che hanno lavorato coperti da pseudonimi, nom de plume collettivi, false identità né, tantomeno, di tardivi riconoscimenti. Eppure questo teorema rimasto sepolto nel rumore del web per più di 7 anni ci interroga sul futuro del concetto di autore di un teorema. Se è evidente a tutti che la natura della ricerca matematica si va facendo sempre più collaborativa, quanto manca perché l’autore si ritrovi a essere marginale, quanto perché i contributi anonimi possano diventare determinanti? È questa la nuova frontiera del citizen science in un settore che ne sembrava refrattario? Il problema non è in che forma citare il risultato originario o a chi attribuire la dimostrazione, come ha titolato qualche articolo di giornale. Sembra piuttosto aprire un fronte più ampio che mette in questione i luoghi della ricerca matematica e le sue procedure di validazione, oltre che il problema rappresentato dalla volatilità di certi supporti. Forse, un giorno, una frase espressa per caso da uno sconosciuto, su di un social network, diventerà la nuova nota a margine a cui non basta lo spazio; frase che attirerà centinaia di novelli de Fermat.

Nicola Ciccoli