Dopo la manipolazione delle serie infinite della scorsa settimana, eccovene un’altra che vi lascerà sicuramente perplessi. Prendiamo la somma infinita 1 + 2 + 4 + 8 + …, dove ogni termine è il doppio del precedente. Qual è la sua somma? Non sembrano esserci dubbi; tutti i termini sono positivi, ciascuno è maggiore del precedente, se ci fermiamo all’n-simo termine la somma parziale è 2ⁿ⁺¹−1… insomma la somma è infinita. Anche se facciamo la somma di Cesaro, quella che ci permette di dire che la somma della serie non assolutamente convergente 1 − 1 + 1 − 1 + 1 − … è 1/2 (non ve ne ho mai parlato?) la somma della nostra serie originale è infinita. Eppure…

Eppure Eulero aveva fatto questo ragionamento. Immaginiamo che questa somma abbia un valore $S$. Avremmo allora per definizione $S = 1 + 2 + 4 + 8 + …$, e quindi $2S = 2 + 4 + 8 + 16 + …$. Se ora sommiamo 1 a entrambi i membri dell’equazione otteniamo $2S + 1 = 1 + 2 + 4 + 8 + 16 + … = S$. Spostando le $S$ a sinistra e i numeri a destra, ricaviamo per l’appunto $S = -1$. E in effetti Eulero (che sapeva benissimo che la serie andava all’infinito…) pensava che i numeri negativi fossero maggiori di tutti i numeri razionali.

Il tutto vi sembra solo uno sporco trucco, come nella “dimostrazione” per cui 1 = 2 ottenuta dividendo a un certo punto entrambi i membri di un’equazione per zero? Non necessariamente, se passiamo dall’aritmetica a qualcosa di più avanzato. Come potete per esempio leggere su Wikipedia, consideriamo la serie di potenze $f(z) = 1 + 2z + 4z^2 + 8z^3 + 16z^4 + …$. (Uso la $z$ e non la $x$ perché lavorerò nel campo dei numeri complessi); intorno al punto 0 il suo raggio di convergenza (cioè il cerchio più grande per cui per tutti tutti i punti al suo interno, esclusi al più quelli sulla circonferenza, la serie converge) è 1/2, perché per z=1/2 la funzione è 1 + 1 + 1 + 1 + … che va all’infinito. Esiste però un teorema dell’analisi complessa che dice che se eliminiamo i punti in cui la funzione assume per l’appunto un valore infinito possiamo associare un unico valore finito per la funzione a tutti gli altri punti del piano complesso; questo valore coincide pertanto con quello della serie di partenza dove essa converge. La serie di potenze equivale alla funzione $f(z) = \tfrac{1}{1-2z}$, e se ora prendiamo $z=1$ otteniamo per l’appunto −1 come risultato. Per completezza, Eulero usò un approccio simile, anche se chiaramente solo sui numeri reali, per arrivare alla sua formula; e lo stesso tipo di calcolo è stato usato anche da Ramanujan, quando disse che $1 + 2 + 3 + 4 + … = \zeta(1) = -\tfrac{1}{12}$. La matematica è pluralistica, anche se sono in molti a credere che non sia così e che ci sia un’unica possibile soluzione per qualunque problema: in realtà quello che importa è avere un ambiente coerente (che non potremo dai dimostrare essere tale, ma quella è un’altra storia) e siamo a posto.

Ultima curiosità: la voce di Wikipedia dice anche che se vediamo la serie come composta di numeri 2-adici $(1_{2p}, 10_{2p}, 100_{2p}, 1000_{2p}, ….)$ allora la somma è comunque $-1$, perché la somma è $…1111111_{2p}$ e se sommiamo 1 tutti gli 1 si annullano e resta appunto zero; ma non ho ancora trovato il tempo per spiegare cosa sono i numeri p-adici, quindi avete il diritto di non capire cosa ho scritto :-)

Prendete due numeri naturali a caso: per esempio 42 e 2025. Come vedete, in questo caso i numeri hanno un fattore in comune, per la precisione 3. Se invece avessimo scelto 42 = 2×3×7 e 2035 = 5×11×37 non ci sarebbe stato nessun fattore in comune, e quindi sono primi tra loro. Se vi piace la matematica, una domanda sorge spontanea: qual è la probabilità che se scegliamo due numeri a caso essi siano primi tra loro?

La domanda è più insidiosa di quanto possa sembrare a prima vista. Come è possibile scegliere un numero a caso, visto che ce ne sono infiniti? La probabilità di sceglierne uno è zero, come ci insegna Kolmogorov. I matematici però non si lasciano fermare da queste quisquilie, e hanno trovato un modo ragionevole per scegliere un numero a caso: calcolare il limite per $n \to \infty$ di cosa succede se scegliamo due numeri a caso tra 1 e $n$. Questo è un semplice trucco formale: i conti li si fa lo stesso all’infinito…

Vediamo ora i conti effettivi. Preso un numero primo $p$, la probabilità che due numeri casuali abbiano entrambi un fattore $p$ è $1\!/\!p^2$, e quindi quella che non abbiano quel fattore è $1 – 1\!/\!p^2$. Dato che la probabilità è indipendente dal numero primo scelto, la probabilità che due numeri non abbiano fattori primi in comune è

$$ P = (1 – 1\!/\!2^2)(1 – 1\!/\!3^2)(1 – 1\!/\!5^2)(1 – 1\!/\!7^2)(1 – 1\!/\!11^2)\cdots $$

Ma sappiamo che possiamo scrivere $1\!/\!(1-x) = 1 + x + x^2 + x^3 + \cdots$. Sostituendo queste successioni infinite nella formula sopra ricaviamo

$$ P = \left( (1 + 1\!/\!2^2 + 1\!/\!2^4 + \cdots)(1 + 1\!/\!3^3 + 1\!/\!3^4 + \cdots) \cdots \right) ^{-1}. $$

Qui arriva il colpo di genio, che elimina uno dei due livelli di infinito nel prodotto qui sopra. Un qualunque numero è sempre esprimibile in un unico modo come prodotto di numeri primi. Questo significa che tutti e soli i quadrati dei numeri naturali si troveranno una e una sola volta come demoninatore, scegliendo opportunamente i fattori, (Chiaramente non si può ottenere un numero che non è un quadrato perfetto, se moltiplichiamo solo quadrati perfetti). Dunque la somma vale

$$ P = (1 + 1\!/\!2^2 + 1\!/\!3^2 + 1\!/\!4^2 + 1\!/\!5^2 + \cdots )^{-1} $$

Non si direbbe abbiamo fatto un grande passo avanti, vero? Ma qui possiamo farci aiutare da zio Eulero, che nel 1735 risolse il “Problema di Basilea” e dimostrò che la somma degli inversi dei quadrati dei numeri naturali vale $\pi^2\!/\!6$. (Oggi chiamiamo quella somma $\zeta(2)$, usando la zeta di Riemann, ma quella è un’altra storia). Pertanto la probabilità che cerchiamo è il suo inverso, cioè $6/\pi^2$, pari a circa il 61%.

L’avreste mai detto, che pi greco sarebbe spuntato

Non so se avete mai visto il nome scritto in italiano – credo ci fosse nelle traduzioni dei giochi matematici di Martin Gardner – ma se avete un po’ di dimestichezza con l’informatica teorica dovreste sapere che cos’è il Busy Beaver. O meglio non dovreste essere sicuri di saperlo, perché ci sono due diverse definizioni. Quella originale, proposta da Tibor Rado come funzione Sigma, rappresenta il massimo numero di 1 che una macchina di Turing a n stati con due simboli (0 e 1) che termina la sua computazione può stampare. Rapido ripasso: una macchina di Turing è composta da un nastro infinito, una testina che può leggere un simbolo per volta, e un insieme di stati che sono il suo programma, perché dicono cosa può fare (scrivere un simbolo, eventualmente cancellarlo anche se nel nostro caso si suppone che il nastro contenga infiniti 0, spostarsi a sinistra o a destra ed entrare in un nuovo stato). Ci sono macchine di Turing che non terminano mai la computazione: per esempio se partiamo con un nastro pieno di zeri e abbiamo lo stato “se trovi scritto 0, scrivi 1 e vai a destra” avremo un nastro che si riempirà di 1 dal punto di partenza a destra verso l’infinito. Queste macchine non sono così interessanti, quindi per il Busy Beaver si richiede che la macchina termini l’elaborazione. La seconda definizione, indicata come BB(n), non conta gli uni scritti ma il numero massimo di passi che una macchina di Turing con n stati può compiere prima di fermarsi: anche in questo caso si richiede che la macchina effettivamente si fermi.

Possiamo trovare i primi valori di queste funzioni, come al solito, su OEIS. Per quanto riguarda la funzione Sigma, abbiamo

$$\Sigma(1) = 1; \Sigma(2) = 4; \Sigma(3) = 6; \Sigma(4) = 13; \Sigma(5) = 4098.$$

I primi valori di BB() sono invece i seguenti:

$$ BB(1) = 1; BB(2) = 6; BB(3) = 21; BB(4) = 107; BB(5) = 47176870.$$

Il valore di BB(5) è stato congetturato nel 1990 e dimostrato nel 2024: per verificarlo si sono dovute studiare 88664064 macchine di Turing e decidere se si fermano oppure no. La macchina “vincente” ha questa definizione:

         0       1
A       1RB 	1LC
B 	1RC 	1RB
C 	1RD 	0LE
D 	1LA 	1LD
E 	--- 	0LA

La tabella si legge in questo modo: la colonna di sinistra indica in che stato si trova la macchina, la colonna centrale cosa succede se c’è scritto 0 sotto la testina e quella di destra cosa succede se c’è scritto 1; le triplette di caratteri dicono cosa scrivere (0 oppure 1), se andare a destra (R) o sinistra (L), e infine in quale stato posizionarsi. Non è mai possibile arrivare nello stato E e vedere uno 0, quindi quella casella è vuota.

E quali sono i valori successivi delle due successioni? Non solo non lo si sa ma non lo si potrà nemmeno sapere. Nel caso di Σ, sappiamo che Σ(6) > 10^^15. La notazione con doppio cappello, indicata a volte con l’esponente a sinistra ( ¹⁵10 ), è la tetrazione, la generalizzazione di moltiplicazione ed elevamento a potenza. Come 3×5 = 3+3+3+3+3 e 3^5 = 3×3×3×3×3×, 3^^5 = 3^(3^(3^(3^3)))). 10^^15 è insomma un numero così grande che è praticamente inconcepibile. Ma BB(6) è molto, molto, molto più grande: Scott Aaronson riporta che BB(6) > 2^^^5, dove il triplo cappelletto indica la pentazione, cioè il passo successivo alla tetrazione. Questo risultato surclassa il vecchio limite che era “solo” 10^^10000000. Quanto è grande quel numero? Aaronson spiega che se avessimo 10^^10000000 granelli di sabbia potremmo riempire 10^^10000000 copie dell’universo osservabile. Sì, lo stesso numero, tanto il valore è così grande che non ci si accorge della differenza. Numeri oltre ogni comprensione umana, insomma!

Ultimo aggiornamento: 2025-07-18 23:02

Il primo giorno in seconda liceo, il nuovo professore di matematica si è presentato dicendo a ciascuno di noi un numero di due cifre e chiedendo di fattorizzarlo (a mente, ovvio). Questo è abbastanza banale: se volete allenarvi potete andare su questo sito, dove in un minuto dovete indicare quanti più numeri primi possibile. (Ci ho provato mentre scrivevo questo post e sono cascato solo in fondo, ma era già un numero di tre cifre).

Tutto questo è però da dilettanti. Nel 2023 Hilarie Orman e Richard Schroeppel hanno preparato un manuale (mai uscito dallo stato di bozza) dal titolo “Numbers for Masochists: A Guide to Mental Factoring” che spiega come fattorizzare a mente numeri fino a 100000 (centomila, ho messo il numero corretto di zeri). Gli autori dicono subito che è una cosa essenziamente inutile, ma non si sa mai cosa uno voglia fare per perdere tempo. Alcune tecniche le conoscevo, altre (quelle per trovare fattori primi grandi, generalmente) mi erano ignote; ma credo che la parte più interessante sia quella dove gli autori raccontano la matematica che sta dietro ad alcune di queste regole mentali, soprattutto quella delle formule quadratiche. Tanto il manuale si può liberamente scaricare: potete poi decidere voi se ne vale o no la pena.

Oggi parlo brevemente di due sviluppi matematici (occhei, il secondo è più legato all’intelligenza artificiale) che hanno dato un risultato che non ci si aspettava. I due sviluppi hanno in comune che il matematico intervistato dallo Scientific American per far capire di più (hahaha) i lettori è sempre lo stesso: Ken Ono, un pezzo grosso nella teoria dei numeri, che ha condotto in prima persona il primo sviluppo e partecipato al secondo.

Il primo sviluppo parla di una definizione dei numeri primi. A scuola ci hanno insegnato che un numero è primo se non ha divisori propri. (Il numero stesso e 1 sono divisori impropri: così ci togliamo una volta per tutte il commento “ma perché 1 non è considerato primo?”). Quello che Ono ha scoperto, insieme a William Craig e Jan-Willem van Ittersum, è una definizione alternativa di numero primo che non parla di divisioni, ma si basa sulle partizioni di un numero. Una partizione di un numero naturale n è semplicemente un modo di suddividerlo in parti (sempre numeri naturali) che una volta sommate tra di loro danno il numero di partenza. Per esempio ci sono 11 partizioni di 6: (1,1,1,1,1,1), (2,1,1,1,1), (2,2,1,1), (2,2,2), (3,1,1,1), (3,2,1), (3,3), (4,1,1), (4,2), (5,1), (6). Ordunque, Ono e i suoi colleghi hanno dimostrato che esistono infinite funzioni legate alle partizioni che permettono di dire se un numero è primo. Se per esempio prendiamo un numero n e calcoliamo

$$(3n^3−13n^2+18n−8)M_1(n)+(12n^2−120n+212)M_2(n)−960M_3(n)$$

dove le $M_i$ sono le funzioni di partizione di MacMahon, che sono abbastanza note a chi lavora sulle partizioni, otterremo zero se e solo se n è un numero primo. A che serve tutto questo? Da un punto di vista pratico, a nulla. Calcolare le $M_i$ è molto più complicato di fattorizzare un numero, che è già un compito non banale. Insomma, se vi stavate preoccupando che gli algoritmi di crittografia basati sulla difficoltà di fattorizzazione fossero da buttare via potete dormire sonni tranquilli. Quello che è importante, però, è avere trovato una correlazione tra due campi della matematica apparentemente slegati tra di loro: e si sa che in questi casi da cosa nasce cosa.

Il secondo sviluppo vede invece una versione di o4-mini (il modello più recente di OpenAI) addestrato esplicitamente su problemi di teoria dei numeri. Un gruppo di matematici, ancora una volta guidato da Ono, ha preparato un insieme di domande “difficili” e su cui non dovevano esserci esempi risolti in letteratura, tanto che i matematici non solo hanno firmato un NDA ma è stato loro imposto di usare Signal per comunicare tra di loro, in modo che non potessero esserci fuoriuscite di dadi. Secondo Ono, anche se alla fine i trenta matematici hanno trovato dieci domande a cui il modello non ha saputo rispondere, i progressi dell’IA sono stati incredibili. Ono racconta di un problema aperto di teoria dei numeri che è stato risolto in una decina di minuti, con il modello che termina l’esposizione con “Non è necessaria la citazione perché il numero misterioso è stato calcolato da me!” Come ha commentato Yang Hui He, “C’è la dimostrazione per induzione, la dimostrazione per contraddizione e la dimostrazione per intimidazione. Se dici qualcosa con sufficiente autorità, la gente s’intimorisce. Penso che o4-mini abbia imparato la dimostrazione per intimidazione: afferma tutto con grande sicurezza”. Non ho visto le domande, e anche se le avessi viste non penso che le avrei capite, o se per questo avrei capito l’output del modello – no, non lo chiamo “ragionamento”. La mia idea è che in un certo senso il risultato sia combinatorio: è vero che non esiste un testo specifico da copiare per trovare la risposta, ma le tecniche sono comunque standard e quindi gli esempi trovati in letteratura sono utilizzabili da un sistema automatico per costruire la risposta. Un livello superiore e una velocità molto maggiore rispetto a quello che facevo io all’università nel risolvere gli esercizi di algebra, ma la logica è ancora la stessa.

Ultimo aggiornamento: 2025-07-02 11:39

La scorsa settimana avevo presentato il problema di Langford: mettere in fila $2n$ coppie di numeri da $1$ a $n$ in modo che tra i due numeri $i$ ci siano esattamente $i$ altri numeri. Per $n=3$ e $n=4$ le soluzioni (essenzialmente uniche) sono rispettivamente 3-1-2-1-3-2 e 4-1-3-1-2-4-3-2. Ho anche detto che una soluzione era possibile solo se il numero di coppie era della forma $4k$ oppure $4k+3$, come è stato dimostrato da Roy O. Davies. La dimostrazione è molto semplice: eccola qua.

Numeriamo da $1$ a $2n$ i numeri dell’elenco, e per ciascun numero $k \in {1, … n}$ consideriamo le due posizioni $P_k < Q_k$ dei due numeri nell'elenco. Nel caso $n=3$ abbiamo per esempio $P_1 = 2, Q_1 = 4, P_2 = 3, Q_2 = 6, P_3 = 1, Q_3 = 5.$ Chiaramente abbiamo $Q_k = P_k + k + 1$ per definizione di coppia $k$. La somma di tutti questi valori è $\sum_{k=1}^{n} (2P_k + k + 1) = 2\sum_{k=1}^{n} P_k + n + n(n+1)\!/\!2$, ma visto che sono i valori da $i$ a $2n$ sappiamo che la somma è anche $n(2n+1).$ Poiché la somma dei $P_k$ è evidentemente un numero intero, ci accorgiamo subito che se $n = 4q + 1$ oppure $n = 4q +2$ abbiamo che gli altri termini danno una somma frazionaria e quindi non ci sono soluzioni. □ Questo è un risultato negativo, nel senso che ci dice quando non si può risolvere il problema ma non quando lo si può fare. Però le soluzioni negli altri casi sono tantissime, a parte quella unica nei casi visti sopra. Davies pensava che per $n=7$ ci fossero 25 soluzioni, e Martin Gardner nel 1967 riportò quel valore: in realtà ce ne sono 26. John Miller, come scrive nel suo sito, programmò un computer nel 1968 e trovò le 26 soluzioni per $n=7$ e le 150 per $n=8$. (Due persone riuscirono a trovare tutte le soluzioni nel primo caso a mano…). E.J. Groth ottenne anche il numero di soluzioni per $n=11$ (17792) e $n=12$ (108144). Altri valori si possono trovare come sempre su OEIS: quelli per 15 e 16 sono stati computati negli anni ’80; il 19 nel 1999, il 20 nel 2002, il 23 nel 2004, il 24 nel 2005, il 27 e il 28 nel 2015… e poi non si sa più. Del resto, le soluzioni per $n=28$ sono 1607383260609382393152, diciamo parecchie!

Si può anche decidere di accettare solo le soluzioni “planari” al problema, nel senso che i numeri uguali si possono connettere tra loro e ottenere un grafo planare. La soluzione generale per $n=3$ è planare, quella per $n=4$ e quelle per $n=7$ non lo sono, ci sono quattro soluzioni planari per $n=8$ e così via. Come al solito, OEIS ha la successione. C’è poi la “variante Tanton”, da James Tanton: in questo caso ci sono $n$ studenti seduti in circolo, e si chiede che si può dare un numero da 1 a $n$ agli studenti in modo tale che se lo studente $k$ si sposta di $k$ posti in senso orario (quindi quello $n$ non si sposta…) alla fine non ci sia nessuno seduto sulle ginocchia di un altro. In questo caso si può dimostrare con semplici sistemi di parità che il numero di studenti deve essere dispari: stranamente la successione dei possibili valori (0, 0, 1, 0, 3, 0, 19, 0, 225, 0, 3441, 0, 79259, 0, 2424195…) non si trova su OEIS!

Ultimo aggiornamento: 2025-06-25 20:07

Nel 1958 il matematico scozzese C. Dudley Langford stava guardando suo figlio piccolo che giocava con dei cubi colorati: ne aveva presi sei e li aveva messi in fila. I matematici, si sa, sono brutte persone: invece che giocare con suo figlio, notò che c’erano tre coppie di cubi di colori diversi, rosso, azzurro e giallo. Inoltre i due cubi rossi avevano un altro cubo in mezzo, quelli azzurri due e quelli gialli tre, come nella parte in alto della figura.

Spero dopo aver mandato a dormire il bimbo, Langford da buon matematico provò a vedere se la configurazione era generalizzabile: ci riuscì con quattro coppie, e addirittura con quindici: ma alcuni casi proprio non volevano saperne di avere soluzione, e così congetturò che una soluzione era possibile solo se il numero di coppie fosse della forma $4k$ oppure $4k+3$, come è in effetti il caso: Roy O. Davies lo dimostrò l’anno successivo.

La formulazione matematica del problema di Langford chiede di trovare una successione di $n$ coppie di oggetti, denominati $a_1, a_2, … a_n, b_1, b_2, … b_n$, tali che $b_i − a_i = i + 1 \forall i = 1, …, n$. Il numero di soluzioni, quando ovviamente ci sono, cresce in maniera molto rapida, come si vede nella successione su OEIS: c’è solo una soluzione per 3 o 4 coppie di blocchi, ma per venti coppie ci sono più di 2600 miliardi di possibili soluzioni!

Quasi contemporaneamente da Langford ma in modo indipendente, Thoralf Skolem propose un problema simile, dove però le distanze tra i blocchi $b_i$ e $a_i$ non sono $ i+1$ ma semplicemente $i$. R. S. Nickerson riscoprì il problema una decina d’anni dopo, e così la versione si chiama di Skolem-Nickerson. Come si può vedere nella voce di Wikipedia, per questa versione del problema ci sono successioni solo se il numero di coppie è della forma $4k$ oppure $4k+1$. Anche in questo caso le soluzioni crescono molto rapidamente al crescere del numero di coppie.

Ci sono ancora altre curiosità su questo problema, ma ve le racconto la prossima volta…

(Immagine di RiccardoFila, da Wikimedia Commons, CC-BY-SA 4.0)