Archivi categoria: 2024

Partizioni egizie

L'occhio di Horus e le sue frazioni corrispondenti Gli antichi egizi scrivevano i numeri frazionari come somma di frazioni con numeratore 1 e denominatori tutti diversi tra loro: per esempio 5/14 = 1/3 + 1/42 e 9/11 = 1/2 + 1/4 + 1/15 + 1/660. Per scrivere una frazione come egizia si può usare il metodo “greedy”, togliendo a ogni passo la frazione più grande possibile; non è detto però che esso porti alla somma con il minor numero di addendi. L’occhio di Horus, mostrato qui in figura e che magari vi ricorda l’album dell’Alan Parsons Project Eye in the Sky, contiene appunto alcuni geroglifici corrispondenti a frazioni egizie la cui somma è quasi 1. (Il “quasi” è stato completato da Toth, o Hathor secondo altre tradizioni, per mezzo della magia.)

Ma non è direttamente delle frazioni egizie che voglio parlarvi oggi. Luca Rovelli ha scritto di un tema leggermente diverso, ma correlato. Diciamo che un numero è strettamente egizio se può essere scritto come somma di numeri tutti distinti i cui inversi hanno somma 1. Il più piccolo numero strettamente egizio è 11: infatti 1 = 1/2 + 1/3 + 1/6, e 2 + 3 + 6 = 11. Nel 1963 Ron Graham studiò questi numeri e scoprì che esiste un numero finito di numeri che non sono strettamente egizi: il maggiore di essi è 77, e il loro elenco si trova (ovviamente…) su OEIS.

(immagine di Kompak, Benoît Stella e Ignacio Icke da Wikimedia Commons)

Ultimo aggiornamento: 2024-12-06 12:14

Quando la fisica ha bisogno della matematica

i due premi Nobel 2024 per la fisicaAnche gli Accademici di Stoccolma che assegnano i Nobel scientifici seguono spesso le mode, anche se non a livello di quelli del premio per la letteratura che secondo me ogni tanto si divertono. Così quest’anno il premio per la fisica è andato a John Hopfield e Geoffrey Hinton “per le scoperte e invenzioni di base che hanno permesso il machine learning con le reti neurali artificiali”. Ora che l’AI è tornata di moda, evidentemente, anche il comitato ha deciso di salire sul carro del vincitore.

Da un punto di vista genericamente scientifico l’attribuzione ha senso. Dopo l’Inverno dell’Intelligenza Artifiale arrivato alla fine degli anni ’60 quando Minsky e Papert dimostrarono che il percettrone di Rosenblatt non avrebbe mai potuto funzionare in pratica non essendo neppure in grado di calcolare uno XOR, avere il coraggio di proporre un nuovo modello non era facile, soprattutto considerando che non c’erano potenza di calcolo e basi dati di addestramento che permettessero di mettere in pratica la teoria. Quello che io – ma penso anche altri – mi sono chiesto è cosa tutto questo ha a che fare con la fisica, oltre al fatto che Hopfield è fisico. (Hinton nemmeno questo, tra l’altro: ho scoperto che è psicologo con dottorato in intelligenza artificiale, oltre che avere parentele illustri…) E anche il comitato se lo deve essere chiesto, se nella pagina che spiega a noi comuni mortali le loro ricerche cominciano con lo scrivere “I premiati di quest’anno hanno usato strumenti della fisica per costruire sistemi che hanno aiutato a porre le basi per il machine learning oggi così potente”, seguito dal titolone “They used physics to find patterns in information”. Continuando a leggere, scopriamo che il modello di Hopfield parte da un’analogia con i neuroni biologici più precisa di quella di Rosenblatt e poi usa una formula simile a quella usata nel caso di un reticolo di spin, per trovare lo stato di energia minore che dovrebbe corrispondere all’immagine del dataset più vicina a quella distorta fornitagli in fase di test. Il modello di Hinton, invece, ha introdotto lo strato di neuroni nascosti – il vero valore aggiunto rispetto al percettrone – e usato tecniche di massimizzazione dell’entropia per trovare la configurazione più probabile a cui assegnare la figura presentata nei test e non vista in fase di addestramento: non per niente il suo modello si chiama Boltzmann Machine. Hinton ha anche continuato a lavorare per decenni ai suoi modelli, il che gli ha permesso di farli funzionare anche in pratica e non solo in teoria: troppe connessioni infatti confondono il modello; è stato necessario ridurle, non solo per ridurre la quantità di calcoli necessari ma proprio per non rischiare di fissarsi su caratteristiche non importanti delle immagini.

Detto tutto questo, continuo a restare della mia idea: è vero che le idee alla base delle ricerche dei nuovi Nobel arrivano dalla fisica, ma poi di altra fisica non ce n’è molta, e abbiamo più che altro matematica. Ma lasciamo crogiolarsi i fisici al pensiero che sia tutta fisica ;-)

(Ritratti dei Nobel John Hopfield e Geoffrey Hinton di Niklas Elmehed, © Nobel Prize Outreach)

Dal caso all’ellisse

un poligono casuale Quello che vedete qui a sinistra è un poligono (intrecciato) di 100 lati. D’accordo, assomiglia più a uno scarabocchio, ma tecnicamente è un poligono. Supponiamo di costruire un nuovo poligono i cui vertici siano i punti di mezzo dei cento lati, e ripetere l’operazione a piacere. Cosa otterremo come limite? Beh, sempre un poligono di cento lati, mi direte: ma non è esattamente così. Il poligono ottenuto sarà sempre più piccolo, e il limite dei vari poligoni sarà un singolo punto, il baricentro di quelli iniziali.

Questo non è poi così interessante: cambiamo allora leggermente il nostro esperimento. Dopo ciascun passo scaliamo il poligono ottenuto in modo che i due vettori formati dalle coordinate $x$ e dalle coordinate $y$ dei punti abbiano norma 1, e il baricentro del poligono sia l’origine degli assi: ingrandiamo insomma man mano il poligono, e non pensiamo di arrivare all’infinito ma solo a un numero abbastanza alto di iterazioni. Quello che succede è che i vertici dei poligoni man mano ottenuti tenderanno a essere parte di un’ellisse, inclinata di 45 gradi rispetto agli assi cartesiani. Potete vedere all’opera l'”ellissizzazione” in questa pagina di Jason Davies.

Attenzione: i punti non tendono a una posizione fissa. Lo si vede bene se prendete un poligono di 10 lati e vi fate mostrare solo una posizione ogni due, per smussare il disegno: in pratica si nota una lenta rotazione dei punti. Come mai? Adam N. Elmachtoub e Charles F. Van Loan lo spiegano in questo articolo, dove vengono calcolati i semiassi dell’ellisse partendo dai vettori $x$ e $y$. Ma anche senza studiare la matematica, vedere “sbrogliarsi” il poligono e poi aggiustarsi lentamente è piuttosto ipnotico!

Approssimare il perimetro di un’ellisse

un'ellisse Se abbiamo un cerchio di raggio $r$, la sua circonferenza è $2\pi r$. Questo è facile. Se abbiamo un’ellisse di semiassi $a$ e $b$, il suo perimetro è $P(a,b) = 4aE(e^2)$, dove l’eccentricità $e$ è data da $\sqrt{a^2-b^2}/a$ ed $E$ è l’integrale $E(x) = \int_{0}^{\pi/2}(1-x \sin^2\theta)^{1/2}d\theta$. Un po’ meno facile, considerato poi che quell’integrale è un integrale ellittico del secondo tipo (poca fantasia nei nomi, concordo) e non è risolubile se non con metodi numerici.
Che si può fare, allora? Si può provare a cercare un’approssimazione e accontentarsi di quella. Il solito Ramanujan trovò questa formula:

$P = \pi(a+b)\left( 1 + \frac{3 \lambda^2}{10 + \sqrt{4-e\lambda^2}} \right)$

dove $\lambda = (a-b)/(a+b)$. Io non ho idea se questa formula sia davvero venuta a Ramanujan in sogno, ma è di una precisione incredibile. Tenete conto che queste formule in genere sono sempre meno precise man mano che l’eccentricità $e$ aumenta; John D. Cook mostra che se prendiamo l’orbita del pianeta nano Sedna che ha un’eccentricità 0,8549 (Plutone, per confronto, ha 0,2488 e la terra 0,0167) e un semiasse maggiore di 76 miliardi di chilometri, l’errore commesso con questa formula è di 53 chilometri.
La cosa ancora più bella di questa approssimazione è che l’errore relativo è limitato, e resta sempre sotto lo 0,0051% anche con un’eccentricità massima. Direi che ci si può accontentare!

(figura di ZetaZeti, da Wikimedia Commons)

Ultimo aggiornamento: 2024-09-25 19:35

OpenAI o1 saprà davvero “ragionare matematicamente”?

Mi pare che la notizia secondo cui OpenAI ha creato un chatbot che “sa fare ragionamenti matematici e scientifici” non abbia avuto grande eco. Può darsi che ciò sia dovuto al fatto che OpenAI o1 – questo è il nome in codice del nuovo progetto – è disponibile solo per un selezionato gruppo di utenti, oppure perché a nessuno interessa davvero avere un sistema che sappia risolvere problemi matematici.

Devo dire che l’articolo del NYT è parco di informazioni. Pare che OpenAI o1 usi l’apprendimento per rinforzo, quindi “premiando” le successioni di passi logici rispetto a un risultato ottenuto di colpo. L’idea degli sviluppatori è che in questo modo ci si avvicinerebbe di più al pensiero umano. Io personalmente non sono molto convinto di questo approccio, che continua a nascondere sotto il tappeto il problema di base degli LLM: non è che avere un approccio passo passo faccia sì che il computer abbia un’idea di quello che sta facendo: per lui continua a trattarsi di un’emissione di simboli secondo una certa logica sintattica e non semantica. Certo, è vero che fare passi più brevi aumenta la probabilità che l’output del singolo passo sia corretta: ma visto che il numero di passi aumenta alla fine la probabilità di un’allucinazione è la stessa.

Il modo migliore per far risolvere problemi di matematica è quello di accorgersi che si parla di matematica e passare a un altro sistema “classico”: se la domanda è “quanto fa 48 per 75?” ci dovrebbe essere un metasistema che si accorge di star facendo un’operazione aritmetica e quindi buttare via tutto l’apprendimento standard, facendo piuttosto partire un sistema classico. Perché è vero che probabilmente ChatGPT ha visto quell’espressione in fase di addestramento e quindi ha la risposta, ma è anche vero che alla domanda “quanto fa 10048 per 13275?” i risultati non possono essere che sbagliati. Eppure il pattern dovrebbe essere chiaro, e quindi passare a un sistema aritmetico dovrebbe essere possibile senza troppe difficoltà: il chatbot continuerebbe a non “pensare”, qualunque significato si dia a questa parola nel caso degli esseri umani, e si troverebbe in difficoltà con un testo del tipo “ci sono 10000 soldati e 48 comandanti, ciascuno dei quali pattuglia una zona rettangolare di lati 59 e 225 metri. Se le zone non si sovrappongono, qual è la superficie totale pattugliata?” (Ho appena provato: ChatGPT 4o si dimentica i 10000 soldati…)

In definitiva, questi chatbot saranno anche più bravi di noi, ma ne hanno ancora di strada da fare.

Ultimo aggiornamento: 2024-09-18 22:19

Il problema di Brocard

4! + 1 = 5²; 5! + 1 = 11²; 7! + 1 = 71²Il fattoriale di 4 è 24; se gli sommiamo 1 otteniamo 25, che è il quadrato di 5. Il fattoriale di 5 è 120; sommandogli 1 otteniamo 121, che è il quadrato di 11. Il fattoriale di 7 è 5040; sommandogli 1 otteniamo 5041, che è il quadrato di 71. E poi? Basta, almeno per quanto ne sappiamo.

Il problema di Brocard è stato posto da Henri Brocard nel 1876, ed è stato riscoperto indipendentemente da altri matematici, tra cui Ramanujan. La congettura è che questi siano gli unici casi in cui il fattoriale di un numero sia un’unità inferiore a un quadrato perfetto: sono stati esclusi altri risultati fino a $10^{12}$, ma non si è nemmeno riusciti a dimostrare che il numero di soluzioni possibili sia finito. (La cosa sarebbe un corollario della congettura abc, ma la “dimostrazione” di Shinichi Mochizuki non è stata accettata dalla comunità matematica).

Del resto Brocard, anche se la sua carriera matematica è stata nel campo della geometria, è noto anche per un’altra sua congettura: se $p$ e $q$ sono due primi dispari consecutivi (nel senso che non ci sono altri primi tra di esso: per esempio 89 e 97 sono primi consecutivi) allora ci sono almeno quattro numeri primi tra $p^2$ e $q^2$. Il mio commento su queste proposizioni ricicla quanto Gauss scrisse a W. M. Olbers: «Confesso che il teorema di Fermat, come proposizione isolata ha davvero scarso interesse per me, poiché potrei facilmente formulare una gran quantità di tali proposizioni, che non si potrebbero né provare né confutare». (Ma secondo me Gauss rosicava…)

Ultimo aggiornamento: 2024-09-11 08:37

Persi in una foresta

Nel 1956 Richard Bellman fece questa domanda, qui da me parafrasata: “Vi trovate in una foresta di cui sapete la forma e vi siete persi. Quanto è lungo il più breve percorso che nel caso peggiore vi porti fuori dalla foresta?” Per la cronaca, Bellman è stato uno dei guru della programmazione dinamica, quindi che abbia proposto un problema di ottimizzazione è normale. È anche chiaro che se fosse vissuto nella pianura padana e non in America il problema sarebbe stato ambientato col nebiun, che è molto meglio di una foresta per non sapere dove ci si trova: ma ormai il problema è noto come Bellman’s lost in a forest problem e ce lo teniamo così.

uscire da un quadrato

Il problema sembra semplice, ma non lo è affatto. Prendiamo per esempio un quadrato, per comodità [0,1]×[0,1]. Se sapessimo le coordinate dove ci troviamo e avessimo una bussola, potremmo uscire dalla foresta percorrendo un tratto di lunghezza al massimo 0,5 parallelo a un lato, come a sinistra nella figura. Se non conoscessimo le nostre coordinate ma avessimo la bussola, potremmo uscire percorrendo un tratto di lunghezza al massimo 1, come a metà in figura; magari andremmo nella direzione opposta a quella più vicina ma comunque usciremo. Se non sappiamo proprio nulla? Sicuramente la distanza minima nel caso peggiore è al massimo $\sqrt{2}$, come a destra in figura, ma magari c’è un modo più furbo… E invece no, si dimostra che per tutti i poligoni “grassi” (come spiegato qui) la soluzione ottimale è il diametro della figura. Questo vale tra l’altro per tutti i poligoni regolari dal quadrato in su (e per il cerchio, cosa che però si era già dimostrata in altro modo). E per il triangolo equilatero? Il testo che ho appena citato afferma che A. S. Besicovitch ha congetturato e Patrick Coulton e Yevgenya Movshovich hanno dimostrato che un certo percorso a zig zag in un triangolo equilatero di lato 1 ha lunghezza inferiore a 1: per la precisione, $3 \sqrt{21}/14 ≈ 0.981981$. Esistono altre figure per cui si è calcolata la “lunghezza di fuga” minima, ma il problema non è ancora completamente risolto.

Il tutto serve a qualcosa? Secondo il matematico Scott W. Williams, è “un problema milionario”, nel senso che le tecniche che presumibilmente porterebbero alla risoluzione potrebbero essere riciclate per ottimizzare le soluzioni di problemi nella vita reale…

Ultimo aggiornamento: 2024-09-04 15:48

I dadi di Lake Wobegon

facce del dado D: un 5 e cinque 3; facce del dado E e del dado F: due 1 e quattro 4bLa scorsa settimana abbiamo visto che è possibile costruire tre dadi non standard A, B, C tali che in media il dado C sia “migliore” di A, nel senso che lanciandoli è più facile che abbia il valore più alto; B sia “migliore” di A; C sia “migliore” di B. Ma si può fare di meglio, come Donald Knuth ha scritto nel Volume 4, Fascicolo 5 di The Art of Computer Programming.
Una premessa. Lake Wobegon è il paesino fittizio narrato da Garrison Keillor per radio e nei suoi libri: uno dei tormentoni radiofonici fa “Queste le notizie da Lake Wobegon, dove tutte le donne sono forti, tutti gli uomini sono belli, e tutti i bambini sono al di sopra della media.” Chiaramente le due prime affermazioni prendono in giro i romanzetti dove tutti gli uomini sono forti e le donne belle, e la terza prende in giro la matematica perché non è possibile che tutti stiano sopra la media… o no?
Considerate i tre dadi (sempre non standard) nella figura a fianco. Il primo ha un 5 e cinque 3, e gli altri due due 1 e quattro 4. Ora lanciamoli tutti insieme, e vediamo quando uno dei dadi ha un punteggio maggiore della media dei tre dadi (compreso sé stesso, quindi). Indico con (l,m,n} il risultato rispettivamente dei dadi D, E, F.

Per il dado D, il suo punteggio è maggiore della media nei casi (3,1,1), (3,1,4), (3,4,1), (5,*,*) (l’asterisco indica che qualunque valore va bene). Le probabilità rispettive sono 5/54, 10/54, 10/54 e 1/6; la loro somma è 17/27 che è maggiore di 1/2.

Per il dado E (ma lo stesso vale per il dado F), il suo punteggio è maggiore della media nei casi (3,4,*) e (5,4,1); le rispettive probabilità sono 5/9 e 1/27, che sommate danno 16/27 che è ancora maggiore di 1/2. In pratica, ogni dado se lanciato da solo ha un punteggio che statisticamente è maggiore della media della somma degli altri due!

John D. Cook spiega che l’apparente paradosso per cui A > (A+B+C)/3, B > (A+B+C)/3, C > (A+B+C)/3 si risolve notando che i tre eventi non sono disgiunti, e quindi quando uno è vero può anche esserne vero un altro.