Un paio di dimostrazioni non standard

Quella delle dimostrazioni matematiche è spesso un’arte: non tanto nel senso usuale del termine, quanto perché ci possono essere metodi completamente diversi per arrivare a una dimostrazione, e spesso quello che si sceglie dipende dalle inclinazioni della persona più che da un oggettivo vantaggio. Anzi, a volte il vantaggio non c’è proprio: la dimostrazione fornita è un semplice esercizio di stile. Vediamo due di queste dimostrazioni.

La prima è di un teorema del tutto banale:

Se $n$ è un numero intero e $n^2$ è pari, allora $n$ è pari.

Come la dimostriamo, normalmente? Per assurdo. Supponiamo che $n$ non sia pari, e quindi sia dispari: allora $n^2$ è anch’esso dispari, il che è contro l’ipotesi iniziale. Dunque deve essere pari. Ma immaginiamo che la nostra religione ci vieti di fare dimostrazioni per assurdo, perché rovinano l’equilibrio dell’universo. Come possiamo fare? Come spiegato da Ali Kaya, prendiamo un $n$ per cui sappiamo che $n^2$ è pari, e quindi può essere scritto come $2k$ con $k$ anch’esso intero. Pertanto $n^2 – 2k = 0$, e quindi $n = n + (n^2 – 2k) = n(n+1) – 2nk$. Ma dati due numeri consecutivi ($n$ e $n+1$) uno di essi è pari, e quindi $n(n+1)$ è pari, così come è pari $2nk$. Pertanto, la somma dei due addendi, che ricordo essere $n$, è pari. QED.
Devo aggiungere che i commenti a quel tweet sono generalmente negativi, e dicono che la dimostrazione è solo un modo complicato per dire la stessa cosa che si farebbe con la dimostrazione per assurdo: ma io preferisco vederla come l’applicazione di un vincolo che costringe a fare deviazioni di ogni tipo, un po’ come capita quando si riscrive un testo come lipogramma eliminando per esempio tutte le occorrenze della lettera e.

La seconda dimostrazione è più complicata, sicuramente inutile, ma ha un suo certo fascino.

I numeri primi sono infiniti.

La dimostrazione era già nota ad Euclide, e tra l’altro non è per assurdo, anche se in genere la vediamo esposta in quel modo: Euclide in effetti afferma solo che data una qualunque moltitudine di numeri primi se ne può sempre costruire un altro. La dimostrazione di Sam Northshield, pubblicata sull’ American Mathematical Monthly [Vol. 122, (May 2015), p. 466] è invece per assurdo, e sta su una riga.

$$0 < \prod_p \sin\frac{\pi}{p} = \prod_p \sin\left(\frac{\pi(1+2\prod_{p'}p')}{p}\right) = 0$$ Vediamo pezzo per pezzo il significato di questa formula. La prima disuguaglianza è semplice: abbiamo un prodotto finito (perché supponiamo che i numeri primi siano finiti) di termini tutti diversi da zero (perché sono il seno di valori strettamente maggiori di 0 e minori o uguali a 90 gradi). Sia ora $N$ il prodotto di tutti i (finiti per ipotesi d'assurdo) numeri primi, cioè $\prod_{p'}p'$ nella prima uguaglianza. Riscriviamo dunque quel pezzo della catena di uguaglianze come $\prod_p \sin\left(\frac{\pi(1+2N)}{p}\right)$ che è un po' più leggibile. Perché è uguale a quello precedente? Semplice: per ogni $p$ si ha che $\frac{1+2N}{p} = \frac{1}{p} + 2\frac{N}{p}$, e il secondo addendo è un numero pari perché $N$ è per definizione multiplo di $p$; pertanto quando moltiplichiamo per $\pi$ questo fattore vale 0. Riprendiamo ora $\prod_p \sin\left(\frac{\pi(1+2N)}{p}\right)$. Abbiamo che $1+2N$ è un numero dispari, quindi deve avere un fattore primo $q$. Tra tutti i primi $p$ di cui facciamo il prodotto c'è anche $q$; quel fattore vale pertanto $\sin\pi$ = 0 e rende nullo tutto il prodotto. QED. A nessuno chiaramente verrebbe in mente di usare una dimostrazione del genere per far vedere che i numeri primi sono infiniti. Però credo che essa abbia una sua bellezza: usare una parte della matematica (apparentemente) del tutto scorrelata come la trigonometria fa capire come la matematica sia fondamentalmente un qualcosa di unitario. Qui insomma, più di un vincolo, c'è proprio l'idea di scegliere strade diverse per scoprire cose nuove. Voi che ne pensate?

I compartimenti stagni di IBS

Giovedì scorso ho ordinato online un libro (cartaceo) da IBS, sfruttando lo sconto di un’Happy Card che avevo. Premetto che non avevo fretta di averlo: ne ho sempre troppi da leggere. C’era comunque l’opzione “Consegna gratuita veloce presso una libreria Feltrinelli”: l’ho selezionata, scegliendo la libreria in Centrale. Risultato: lunedì a pranzo mi è arrivata la mail con la disponibilità del libro.
Possiamo discutere se la consegna è stata veloce o no: evidentemente le consegne alle librerie del gruppo non sono effettuate ogni giorno. Quello che però mi lascia perplesso è che quel libro era fisicamente disponibile in quel punto vendita e avrei potuto fermarlo e acquistarlo (non so se potevo anche usare l’Happy Card, ammetto di non aver verificato). Io sono un ingenuone e pensavo che sarebbe stato semplice darmi la copia già in libreria e mandarne una di rimpiazzo, considerato che è tutto lo stesso gruppo: ma evidentemente avrei complicato troppo la gestione interna…

AlphaEvolve

Rewire ha pubblicato un articolo su un risultato ottenuto da Google DeepMind’s AlphaEvolve. Nel 1969 Volker Strassen scoprì come moltiplicare due matrici 4×4 usando solo 49 moltiplicazioni anziché le 64 del metodo canonico riga-per-colonna, e da allora nessuno riuscì a migliorare il risultato: ora AlphaEvolve ha trovato un metodo che ne richiede solo 48. Il preprint relativo è interessante per due motivi: il primo è che non parla solo di questo risultato ma di un corpus di problemi in cui ci sono stati altri casi di risultati migliorati rispetto a quanto noto in letteratura (ma anche di casi in cui non ci è proprio arrivato…), il secondo è che oltre ai due dipendenti di Google i coautori sono Javier Gómez-Serrano, matematico catalano ora alla Brown University che è stato uno dei primi a studiare la possibilità di usare l’IA per migliorare risultati matematici noti ma non dimostrati ottimali, e l’altro è Terry Tao, di cui non serve spiegare nulla. Detto in altri termini, la parte matematica è sicuramente stata controllata bene.

Quello che ho trovato molto interessante è l’approccio usato per questi problemi. Tenete conto che siamo generalmente parlando di problemi combinatori, per cui il numero di possibili combinazioni da testare è oltre la possibilità di un calcolatore per quanto potente; questa è una delle ragioni per cui trovare nuovi e migliori risultati è un compito praticamente impossibile. Personalmente già l’algoritmo originale di Strassen è stato qualcosa di incredibile. Per la precisione Strassen ha dimostrato che bastavano sette moltiplicazioni anziché 8 per moltiplicare due matrici 2times;2; il risultato indicato all’inizio è una banale conseguenza ottenuta considerando la matrice 4times;4 come formata da quattro matricette 2times;2. Però con la matrice più piccola ci sono relativamente poche possibilità di giocare con i parametri e quindi con costanza e fortuna si può trovare qualcosa. Raddoppiando le dimensioni questo tipo di approccio non funziona. Che fa allora AlphaEvolve? Innanzitutto non cerca un risultato nello spazio delle soluzioni, ma lavora nello spazio degli algoritmi, cioè cerca di scrivere un programma che dia il risultato cercato. Ma anche così il compito sarebbe impervio, visto che il numero di algoritmi possibili è dell’ordine di 1033. Quello che invece fa è far evolvere gli algoritmi, usando gli LLM come generatori di mutazioni. Ci sono cinque componenti:

  • La specificazione del problema, data dagli umani: non solo il prompt iniziale (un algoritmo non necessariamente ottimale) ma anche una funzione di valutazione che deve essere semplice da verificare e dare un punteggio. In questo specifico caso la funzione era data dalla correttezza formale dell’algoritmo e dal numero di moltiplicazioni necessarie.
  • La base dati degli algoritmi trovati man mano, da cui si pesca quello statisticamente più promettente.
  • Il selezionatore, che prende dalla base dati un algoritmo promettente e lo trasforma in un prompt “ricco” per un LLM;
  • La mutazione semantica ottenuta con gli LLM, che essendo addestrati sul codice riescono spesso a fornire ottimizzazioni… che magari danno però la soluzione a un altro problema: l’equivalente algoritmico delle allucinazioni di un chatbot standard.
  • Il valutatore-selettore, che controlla che l’LLM non sia andato per farfalle e sceglie i candidati più promettenti.

La parte di mutazione semantica può – anzi vi dovrebbe – fare venire in mente gli algoritmi genetici che erano di moda alcuni decenni fa, dove si facevano modifiche casuali a un algoritmo per vedere se migliorava o no. La differenza fondamentale in questo caso è che gli LLM possono partire per la tangente, ma lo fanno in un modo formalmente corretto, semplificando la vita. Per fare un esempio, la chiave per eliminare la quarantanovesima moltiplicazione è stata il passare alle operazioni con i numeri complessi, che apparentemente complicano la situazione – moltiplicare due numeri complessi significa fare quattro moltiplicazioni rispetto a quella singola nel caso di due numeri reali – ma in un caso particolare permettono un allineamento cosmico per cui moltissime moltiplicazioni si ripetono identiche in più punti, riducendo il numero totale necessario. Tao ha commentato, in maniera un po’ più formale della mia parafrasi, che si sfrutta il fatto stesso che gli LLM sparino parole a caso.

Ho già detto in passato che non bisogna aspettarsi chissà che cosa dall’attuale stato dell’arte delle IA. A dirla tutta, ho il sospetto che passare da 49 a 48 moltiplicazioni (un 2% di guadagno…) non sia chissà cosa. Ma devo riconoscere che per tutta una serie di problemi prettamente combinatori dove lo spazio delle soluzioni è sterminato sono già un grande aiuto.

Meloni e le operazioni aritmetiche

La pressione fiscale in Italia è aumentata ancora, toccando il 42,8% del Pil. Non lo dico io, ma il Documento programmatico di finanza pubblica (tabella a pagina 57). Dire questa cosa però fa piangere il PresConsMin: così ELLA ci tiene a far sapere che “I dati aumentano perché c’è più gente che lavora, perché questo governo ha portato al record storico di proventi dalla lotta all’evasione”. È proprio così? Facciamo un po’ di conti: nulla più che le quattro operazioni, non temete.

Partiamo dalla seconda parte della frase, i proventi dalla lotta all’evasione. Da gennaio a settembre si sono incassati 1,137 miliardi in più. (Non fermatevi al titolo dell’articolo, che non si sa se per compiacere ELLA oppure per comune carenza di comprensione dei concetti matematici confonde il gettito con la differenza di gettito.) Questo denaro equivale a circa lo 0,1% del PIL, ma la pressione è aumentata dello 0,3%: manca ancora molto. Vediamo che si può dire della prima parte dell’affermazione di ELLA. Ricordo che la pressione fiscale è il rapporto tra quanti soldi arrivano allo Stato (numeratore) e quant’è il prodotto nazionale lordo (denominatore). Cosa succede se c’è più gente che lavora? Che il numeratore cresce, perché se guadagni paghi tasse e hai soldi per comprare oggetti su cui paghi l’IVA. Ma cresce anche il denominatore, perché hai prodotto ricchezza… a meno che non ti paghino per fare la guardia ai bidoni di benzina. E si spera che il denominatore cresca più del doppio del numeratore, perché in caso contrario è vero che il rapporto aumenta (per esempio, se partiamo da 4/10, cioè il 40%, e sommiamo 5 sopra e sotto otteniamo 9/15, cioè il 60%) ma questo significa che stai creando lavoro che vale poco. In definitiva, consiglierei ad ELLA di fare meglio il proprio compitino e scegliere almeno i numeri giusti da mostrare…

Archimede : Un grande scienziato antico (libro)

In questo testo Russo racconta tutto quello che sappiamo su Archimede (relativamente poco: i manoscritti che ci sono pervenuti sono una piccola parte di quello che ha presumbilmente scritto, e scoprire il palinsesto del Metodo è stato un colpo di fortuna), quello che possiamo provare a inferire da fonti che generalmente non vengono considerate, come per esempio quelle umanistiche che fanno pensare che al tempo fossero note più opere, ma soprattutto quello che pensiamo di sapere ma è errato. Che la storia dell'”Eureka!” fosse falsa potevamo immaginarlo, ma Russo mostra anche come Archimede avesse ben altre formule per il calcolo del volume di un solido. Inoltre spiace dirlo, ma anche tutta la storia dell’assedio di Siracusa è con ogni probabilità falsa, e molte delle invenzioni che la leggenda vuole create da Archimede erano in realtà fatte da altri, nel fiorire della cultura ellenistica che secondo Russo è stata obliterata dai romani; romani che hanno reso sovrumana la figura del grande matematico per nascondere la loro inferiorità tecnica. Mi viene in mente l’episodio di Asterix quando una centuria ritorna distrutta al campo, affermando che era stata sconfitta da avversari preponderanti, e quando viene chiesto loro quanti erano rispondono “due”. Questo non significa sminuire le capacità di Archimede, ma semplicemente metterle nel loro giusto contesto. E in tutto questo possiamo anche sorridere pensando a un Archimede che prendeva in giro i colleghi alessandrini, come con il problema dei buoi…

Lucio Russo, Archimede : Un grande scienziato antico, Carocci 2019, pag. 184, € 18, ISBN 9788843098262 – come Affiliato Amazon, se acquistate il libro dal link qualche centesimo va a me

Toh, la manovra Irpef favorisce i ricchi

Non riesco a capire gli alti lai odierni alla scoperta che con la manovra Irpef che abbassa dal 35% al 33% l’aliquota sui redditi tra i 28000 e i 50000 euro «il beneficio medio è pari a 408 euro per i dirigenti, 123 per gli impiegati e 23 euro per gli operai; per i lavoratori autonomi è di 124 euro e per i pensionati di 55 euro».
È un mese che la proposta è nota. L’IRPEF è entrata in vigore nel 1974 ed è sempre stata a scaglioni progressivi, il che significa che nel nostro caso il risparmio è nullo per i redditi fino a 28000 euro, cresce linearmente fino a 50000 euro e poi si stabilizza. (Per amor di precisione, sopra i 200000 euro vengono tolte lacune detrazioni e quindi il risparmio scende.) Non entro nel merito della scelta fatta, che è prettamente politica: mi limito a notare che se bisogna aspettare l’Ufficio parlamentare di bilancio perché qualcuno espliciti quanto era già perfettamente chiaro a chiunque sappia un po’ di aritmetica siamo messi male…