Il matematico tedesco Richard Dedekind è soprattutto noto per la sua definizione dell’insieme dei numeri reali (i “tagli di Dedekind”), e per la sua corrispondenza con Georg Cantor sulla teoria dei numeri transfiniti. Come molti matematici, però, ha anche fatto altre scoperte: tra le altre cose, nel 1897 studiò una successione di numeri che in suo onore sono detti numeri di Dedekind. (Al momento in cui scrivo non c’è la voce di Wikipedia in lingua italiana, ma potete sempre scriverla voi :-) )

I numeri di Dedekind contano quanti sistemi di un certo tipo si possono costruire con 0, 1, 2, … elementi. Che tipo di sistemi? Beh, ce n’è più di uno, il che fa capire che il concetto ha un certo qual interesse teorico, visto che rappresentazioni apparentemente diverse si scoprono essere equivalenti: qui ne mostro tre. Il primo sistema è quello delle funzioni booleane monotone di n variabili. Una funzione booleana ha come ingresso n variabili che possono assumere solo due valori (Vero e Falso, V/F), ed essendo una funzione ha un solo valore di uscita, sempre V o F. In informatica si usano spesso funzioni a due variabili, come AND, OR, XOR, ma nulla ci vieta di aumentare il numero di variabili. Una siffatta funzione si dice monotona se quando cambiamo un qualsiasi valore di input da F a V si possono dare solo due casi: l’output resta lo stesso oppure passa anch’esso da F a V. La funzione AND è per esempio monotona, mentre XOR non lo è perché XOR(V,F) = V ma XOR(V,V) = F. Il secondo sistema è quello delle anticatene. Dato un insieme parzialmente ordinato, un’anticatena è un sottoinsieme di questo insieme in cui nessun elemento è contenuto in un altro elemento. Per esempio, se prendiamo come insieme parzialmente ordinato quello dei divisori di 30, {2, 3, 5} e {6, 10, 15} sono delle anticatene, poiché nessun elemento dell’insieme ne divide un altro, mentre {2, 5, 15} non lo è perché 5 è un divisore di 15. Se prendiamo un insieme di n elementi e consideriamo il suo insieme delle parti, cioè tutti i suoi sottoinsiemi possibili, abbiamo un certo numero di possibili anticatene. Per n=2, cioè con i soli elementi 0 e 1, le anticatene possibili sono {{0,1}}, {{0},{1}}, {{0}}, {{1}}, {{∅}} e {∅} (notate la differenza tra le ultime due anticatene; la seconda è quella vuota, la prima contiene l’insieme vuoto). Il terzo modo consiste infine nel prendere un ipercubo a n dimensioni, metterlo in modo che si poggi su un vertice e abbia il vertice opposto perpendicolare all’iperpiano passante da quel vertice; in due dimensioni abbiamo un quadrato ruotato di 45 gradi, come vedete nel disegno qui sotto. Se la regola è “non possiamo colorare di blu un vertice dell’ipercubo se ce ne sono di bianchi più in alto”, otteniamo di nuovo sei possibili colorazioni.

Insomma, il numero di Dedekind D(n) corrisponde al numero di combinazioni possibili. Quanti sono? Dedekind trovò che i valori da D(0) a D(4) sono rispettivamente 2, 3, 6, 20, 168. Nel 1940 Randolph Church calcolò (immagino con una calcolatrice elettrica) D(5) = 7581; nel 1946 Morgan Ward calcolò D(6) = 7.828.354; nel 1965 di nuovo Church calcolò D(7) = 2.414.682.040.998; nel 1991 Doug Wiedemann calcolò D(8) = 56.130.437.228.687.557.907.88. La successione OEIS corrispondente si fermò lì fino a questa primavera, quando due diversi articoli mostrarono indipendentemente che D(9) = 286.386.577.668.298.411.128.469.151.667.598.498.812.366. Come racconta Quanta, il problema era che D(9) non può essere calcolato direttamente per la banale ragione che non esisterebbe sufficiente potenza di calcolo in tutto il pianeta, e dunque occorre trovare delle scorciatoie. Ottenere lo stesso risultato calcolandolo in due modi differenti ci permette di essere più che ragionevolmente certi che esso sia quello giusto: anche in matematica ogni tanto bisogna fidarsi dell’output dei computer!

Si potrà mai conoscere D(10)? Secondo Patrick De Causmaecker, coautore di uno degli articoli, tra qualche decennio potremmo farcela. Ma Christian Jäkel, che ha scritto l’altro articolo, è scettico. La cosa buffa è che però esiste una stima analitica che sbaglia di pochi punti percentuali il valore di D(n). In altre parole, abbiamo un’idea abbastanza precisa di quante sono queste funzioni, ma il diavolo si nasconde nei dettagli…

Immagine di Watchduck, da Wikimedia Commons.