Archivi categoria: 2025

post di argomento matematico del 2025

1/4 + 1/16 + 1/64 + 1/256 + ⋯

la somma 1/4 + 1/16 + 1/64 + 1/256 + ⋯ mostrata graficamente La successione infinita mostrata qui sopra è stata probabilmente la prima ad essere sommata. Naturalmente l’artefice di questo risultato è stato Archimede, l’unico matematico dell’antichità che non aveva paura di trattare con quantità infinite. Questo risultato gli serviva per quadrare la parabola; chiaramente la dimostrazione formale che fece per la quadratura sfruttò il metodo di esaustione di Eudosso, ma per quanto riguarda la somma il siracusano mostrò la figura qui raffigurata. Il quadrato grande di lato 1 è diviso in quattro parti uguali: una è colorata (e quindi ha area 1/4), due sono bianche, la quarta è divisa a sua volta allo stesso modo, con un quadrato colorato di area 1/16, due quadrati bianchi della stessa area e un quarto quadrato da dividere a sua volta. In definitiva, alla parte colorata corrispondono due parti identiche non colorate, e tutte assieme riempiono il quadrato: pertanto l’area complessiva delle parti colorate è 1/3.

Ok, in realtà non è proprio così: come spiega la voce di Wikipedia, Archimede dimostrò che la somma 3/4 + 3/16 + 3/64 + 3/256 + ⋯ si avvicina quanto si vuole a 1. (Sempre esaustione, claro). Nella sua dimostrazione il quadrato colorato e i due non colorati formano uno gnomone, cioè una figura a L; l’insieme di tutti gli gnomoni riempiono il quadrato.

un altro modo per sommare la serie infinita 1/4 + 1/16 + 1/64 + ..., stavolta con i triangoli

Immagine di Kilom69, da Wikimedia Commons

Ma la cosa forse più bella è che non è necessario usare i quadrati per mostrare che la somma in questione vale 1/3. Come potete vedere nella figura qui a fianco, è possibile prendere un triangolo equilatero e scomporlo in modo tale da avere la stessa suddivisione. Quale delle due scomposizioni è la migliore? Per quanto mi riguarda, la risposta è “entrambe”; ciascuna costruzione è infatti interessante, e visualmente chiara. Il bello di queste dimostrazioni senza parole è proprio questo: capire un risultato senza dover fare conti (in questo caso bisogna saper contare fino a tre, ma direi che ce la possiamo fare…)

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?

RSA non è più quello di una volta (II)

La scorsa settimana ho scritto che anche se la struttura logica dell’algoritmo RSA ha cinque parametri, la chiave di cifratura e è quasi sempre settata a 65537, per ragioni di efficienza computazionale e perché non dovrebbe dare problemi di sicurezza (almeno nei casi normali). Ma c’è anche un’altra modifica che è stata fatta negli anni, sempre per ridurre il costo computazionale (che nel caso della crittografia a chiave pubblica è molto più alto che nei sistemi di crittografia simmetrici).

Ricordo che nell’algoritmo RSA viene calcolato φ(n) = (p−1)(q−1), dove p e q sono i numeri primi di partenza, il cui prodotto è n, e φ(n) è la funzione φ di Eulero, cioè quanti sono i numeri minori di n e che non hanno fattori primi in comune con n. Nel nostro caso è facile calcolare il “toziente” (altro nome con cui è nota la funzione φ di Eulero), proprio perché p e q sono primi.

Non è però necessario usare φ(n) per scegliere un d tale che ed = 1 (mod φ(n)). È infatti sufficiente usare la funzione di Carmichael λ(n), definita come il più piccolo intero positivo m tale che am ≡ 1 (mod n) per ogni a coprimo con n. Si può dimostrare che λ(n) è un divisore di φ(n), e quindi è un numero più piccolo e pertanto le operazioni di computazione sono più brevi. Ma di quanto lo sono? Di un fattore MCD(p−1, q−1). Chiaramente entrambi i numeri sono pari e quindi c’è un fattore 2, ma si potrebbe sperare che ci sia qualcosa in più. John Cook ha fatto qualche prova, e ha trovato che su 100 coppie di numeri generati casualmente, la mediana del MCM è 2 (quindi in almeno metà dei casi il fattore è effettivamente 2); c’è stato un caso in cui si è arrivati a 2370, mentre il valore medio (poco utile in questo caso, perché a noi serve una sola coppia) è stato 35,44. In pratica, insomma, abbiamo quasi sempre 2 o 4 come fattore comune, In altri termini, se dobbiamo usare spesso una chiave può valer la pena di cercare una coppia di primi per cui λ(n) è effettivamente molto minore di φ(n), altrimenti possiamo far finta di niente.

Ultimo aggiornamento: 2025-11-05 15:33

RSA non è più quello di una volta (I)

Come probabilmente sapete, l’algoritmo RSA è uno dei più famosi algoritmi di crittografia a chiave pubblica: questo significa che chiunque può mandarci un messaggio cifrato, usando appunto la chiave pubblica, ma solo noi possiamo decodificarlo. L’algoritmo è tendenzialmente questo:

(a) Scegliamo due numeri primi molto grandi p e q.
(b) Calcoliamo n = pq e φ(n) = (p−1)(q−1).
(c) Scegliamo una chiave di crittazione e che sia un numero relativamente primo rispetto a φ(n). (La lettera “e” sta per “encryption”, se ve lo foste chiesti.)
(d) Calcoliamo la chiave di decrittazione d tale che ed = 1 (mod φ(n)).
(e) Pubblichiamo e e n, mantenendo segreti d, p e q.

La logica della crittografia RSA è che se conosciamo p e q possiamo calcolare “facilmente” n, φ(n) e d, ma non è possibile trovare d senza fattorizzare n, e almeno per il momento la fattorizzazione non è facile da fare, checché si dica delle meraviglie dei computer quantistici.

La cosa buffa è che di solito (pare nel 99,5% dei casi in un sondaggio compiuto da due ricercatori) i punti (b) e (c) si invertono: si sceglie prima e e poi si prendono i due primi, verificando che φ(n) sia primo rispetto a e. E soprattutto non si sceglie e a caso, ma si usa 65537. Come mai? John D. Cook lo spiega esaurientemente: è abbastanza grande perché φ(n) sia relativamente primo (se non lo è, bisogna trovare altri p e q) ed essendo uno più una potenza di 2 si risparmia sui calcoli. C’è addirittura chi ha usato e = 3, ma li si esagera. In realtà, continua Cook, usare un e troppo piccolo può far correre il rischio che qualcuno che ha accesso al computer dove sono stati fatti i conti riesce a trovare alcuni dei bit del numero, e in questo caso ci sono algoritmi più rapidi per decrittare a forza bruta. E scegliere un altro primo? Il punto è che e non è semplicemente una potenza di due più uno, ma un numero primo di Fermat: ne conosciamo solo 5 (3, 7, 17, 257, 65537), e anche se ce ne fosse un altro sarebbe così grande da risultare impraticabile…

Insomma, all’atto pratico abbiamo una semplificazione dell’algoritmo, visto che non scegliamo più e; ma la prossima volta vedremo che ce n’è un’altra.

Un trucchetto con le percentuali

Scrivendo il post di stamattina mi è venuto in mente un trucchetto che può permettervi di fare bella figura con poca fatica. Riuscite a calcolare a mente quant’è il 60% di 25?

Il calcolo è molto più semplice di quanto sembri a prima vista. Per definizione, una percentuale si calcola moltiplicando i due numeri presenti e dividento per 100, cioè 60×25/100 nel nostro caso. Questo equivale a 25×60/100, che è il 25% di 60. Ma il 25% è un quarto, quindi basta dimezzare due volte 60 e trovare il risultato che è 15. Semplice, no?

Il metodo d’Hondt… o dovrei dire Jefferson?

Vi siete mai chiesti come si suddividono i seggi in un sistema proporzionale? Un metodo abbastanza comune è quello dei resti. Se hanno votato 10000 persone e ci sono 15 seggi, si comincia a fare la divisione, ottenendo un quoziente di 666 e 2/3. Si dividono ora i voti presi dai partiti per quel quoziente, e si comincia ad attribuire un seggio per ogni quoziente. Tipicamente a ciascun partito avanzeranno dei voti, i “resti”; e parallelamente ci saranno dei seggi non assegnati: questi seggi verranno distribuiti ai partiti che hanno i resti più alti. Il metodo è a prima vista equo, ma non è proprio così: potrebbe darsi che assegnando un seggio in più in totale ci sia un partito che ne prenda uno in meno. Questo è il cosiddetto paradosso dell’Alabama: ne avevo parlato tanti anni fa sul Post, e qui trovate una copia di quel post. Vi svelo subito che non c’è un metodo perfetto per suddividere i seggi, ed è per questo che sono stati proposti vari sistemi.

Uno di questi, che ha avuto molta fortuna in Europa – in Italia lo si usava per le elezioni al Senato fino al 1992, e ancora adesso i seggi di minoranza nei consigli comunali si assegnano in quel modo – è il metodo d’Hondt, che prende il nome dallo studioso belga che l’ha formalizzato. In questo caso si prendono i voti ottenuti dai vari partiti e li si divide per 1, 2, 3, 4, … fino al numero n di seggi da assegnare (in genere non serve andare così avanti). Si prendono quindi gli n valori più alti, a cui sarà assegnato un seggio. Facciamo un esempio pratico. Abbiamo quattro partiti (A, B, C, D) che si contendono otto seggi. I voti totali sono stati 23000, e i singoli partiti hanno ricevuto rispettivamente 10000, 8000, 3000 e 2000 voti. La tabella che si costruisce è la seguente, dove per semplicità ho saltato le ultime colonne inutili:

$$
\begin{matrix}
\textrm{partito} & 1 & 2 & 3 & 4 & 5 & \textrm{seggi} \\
A & \bf{10000} & \bf{5000}& \bf{3333.3} & \bf{2500} & 2000 & 4 \\
B & \bf{8000} & \bf{4000} & \bf{2666.6} & 2000 & 1600 & 3 \\
C & \bf{3000} & 1500 & 1000 & 750 & 600 & 1 \\
D & 2000 & 1000 & 666.6 & 500 & 400 & 0 \\
\end{matrix}
$$

Il metodo d’Hondt non soffre del problema del paradosso dell’Alabama, ma in compenso indebolisce i partiti minori. Con i resti, infatti, il quoziente sarebbe stato 23000/8 = 2875 e avremmo avuto il seguente risultato: un seggio è stato spostato dal partito A al D.

$$
\begin{matrix}
\textrm{partito} & \textrm{voti} & \textrm{quoziente} & \textrm{resto} & \textrm{seggi} \\
A & 10000 & 3 & 1375 & \bf{3} \\
B & 8000 & 2 & \bf{2250} & \bf{3} \\
C & 3000 & 1 & 125 & \bf{1} \\
D & 2000 & 0 & \bf{2000} & \bf{1} \\
\end{matrix}
$$

Quello che non sapevo, e ho scoperto da questo articolo – ma Wikipedia lo diceva già… – è che un sistema equivalente era stato ideato da Thomas Jefferson e proposto a George Washington quando il presidente degli Stati Uniti d’America era quest’ultimo e non il primo. Jefferson divideva i voti ottenuti dai vari partiti per un numero, che chiamava “quota”, e prendeva i quozienti. Come nella fiaba di Riccioli d’oro, c’erano le quote troppo grandi, che non permettevano di assegnare tutti i seggi: nel nostro esempio, una quota di 3000 dà come risultato (3, 2, 1, 0) per un totale di 6 seggi assegnati. C’erano poi le quote troppo piccole: una quota di 2000 dà come risultato (5, 4, 1, 1) per un totale di 11 seggi. E infine c’erano le quote proprio giuste, come 2500 che dà come risultato (4, 3, 1, 0). Ecco dunque la ripartizione dei seggi: si prende la più grande quota che dia una suddivisione esatta dei seggi a disposizione.

Ma perché i due metodi sono esattamente gli stessi? Ci ho dovuto pensare un attimo, ma la cosa è davvero banale: se facciamo scendere man mano la quota, il valore finale di Jefferson è per definizione il primo per cui viene allocato l’ultimo seggio a disposizione. (nel nostro esempio al partito A, ma potrebbe essere uno qualunque). Ma dire con Jefferson che 10000/2500 = 4 è la stessa cosa che dire come d’Hondt che 10000/4 = 2500, no? E a questo punto tutti gli altri valori si ottengono automaticamente, perché aumentare o diminuire il numero di seggi agli altri partiti cambierebbe automaticamente il valore della quota.

Dobbiamo insomma cambiare nome al metodo d’Hondt? Secondo me no. Esso è sicuramente molto più facile da implementare di quello di Jefferson, e soprattutto quando i conti si dovevano fare a mano era fattibile. Insomma, teniamocelo così!

Ultimo aggiornamento: 2025-10-22 12:32

Solo una coincidenza? (II)

Non so se avete avuto voglia di provare a dare una spiegazione per la notevole coincidenza che ho presentato mercoledì scorso. Qui ci sono le mie pensate, che mi hanno portato lentamente a trovare una soluzione.

La prima cosa che mi è venuta in mente è stata la legge di Benford, che si vede bene nei valori delle potenze di 10. Quella è però una falsa pista: beh, a dire il vero nemmeno troppo falsa, ma solo nel senso che il procedimento che porta alla legge di Benford è simile a quello che ci interessa. La seconda cosa che mi è venuta in mente è che $2^{10} \approx 10^3$, e che questo poteva forse spiegare la somiglianza dei valori. Però anche $2^{20} \approx 10^6$; d’accordo, l’errore è circa il doppio, ma la successione delle potenze “scalate tra 1 e 10” non assomiglia affatto a quella delle potenze frazionarie di 10. Però è anche vero che in certi casi la concordanza è ottima: abbiamo che $6^9 = 10077696$, e costruendo la tabella con le prime nove potenze (e quelle di 10 da $10^{1/9}$ in su) otteniamo (sempre approssimando)

$$
\begin{matrix}
n & \textrm{potenza} & \textrm{seietto} & \textrm{differenza} \\
0 & 1 & 1 & 0.00\% \\
1 & 1.2915 & 1.296 & 0.34\% \\
2 & 1.6681 & 1.6796 & 0.69\% \\
3 & 2.1544 & 2.16 & 0.26\% \\
4 & 2.7826 & 2.7993 & 0.60\% \\
5 & 3.5938 & 3.6 & 0.17\% \\
6 & 4.6416 & 4.6656 & 0.52\% \\
7 & 5.9948 & 6 & 0.09\% \\
8 & 7.7426 & 7.776 & 0.43\% \\
\end{matrix}
$$

Insomma, a volte l’essere arrivati molto vicino a una potenza di 10 funziona e a volte no. A questo punto sono tornato sui miei passi, e ho ripreso l’idea della legge di Benford, o meglio mi sono ricordato di come Simon Newcomb avesse notato la legge qualche decennio prima di Benford: le prime pagine delle tavole dei logaritmi erano più sporche delle ultime, il che significava che quelle pagine venivano usate di più. Prendiamo dunque i logaritmi in base 10 delle potenze di 10 usate nella tabella: per costruzione saranno tutti equidistanti tra 0 e 1 (più precisamente saranno 0/10, 1/10, …, 9/10, visto che ci siamo fermati prima di $10^1$). Cosa abbiamo invece nelle prime dieci potenze di 2? Sappiamo che $2^{10} \approx 10^3$, e quindi i loro logaritmi saranno equidistanti, con un passo di circa 3/10 (e infatti $\log_{10} 2 \approx 0.30103$). Trasformare le potenze di due mettendo il punto decimale dopo la prima cifra corrisponde a considerare solo la parte decimale (la mantissa) dei logaritmi; quindi abbiamo (quasi) la parte decimale dei multipli di 0.3; la cifra decimale di questi multipli varia da 0 a 9. Ora è chiaro perché considerare le prime venti potenze di 2 non funziona: abbiamo i valori della prima cifra decimale a coppie. Nel caso dei seietti, le parti decimali sono nove e quindi i logaritmi saranno distanziati circa di 1/9 uno dall’altro, mentre quelli delle potenze di 10 sono distanziati esattamente di 1/9.

A questo punto possiamo anche capire il motivo per cui gli errori variano: nei logaritmi abbiamo un residuo (0.00103 nel caso delle potenze di 2) che man mano si accumula. Gli errori maggiori si hanno pertanto in corrispondenza delle potenze più grandi di 2. In definitiva: no, non era una coincidenza, ma accorgersi del motivo non è immediato.

Solo una coincidenza? (I)

Colin Wright ha recentemente postato sul suo sito questa curiosità, segnalatagli da un suo amico.

Passo 1: Scriviamo le potenze di 2 da 0 a 9: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.
Passo 2: Mettiamo questi numeri in ordine lessicografico: 1, 128, 16, 2, 256, 32, 4, 512, 64, 8.
Passo 3: Mettiamo un punto decimale (o una virgola, se preferite) dopo la prima cifra di ciascun numero: 1.0, 1.28, 1.6, 2.0, 2.56, 3.2, 4.0, 5.12, 6.4, 8.0.

A questo punto abbiamo dieci numeri in ordine crescente, compresi tra 1 e 8. Chiamiamoli “duetti” e lasciamoli un attimo da parte.

Passo 4: Calcoliamo le potenze di $10$ da $10^{0.0}$ a $10^{0.9}$ con gli esponenti che crescono man mano di 0.1. Otteniamo (arrotondando)

$10^{0.0} = 1.000$; $10^{0.1} \approx 1.259$; $10^{0.2} \approx 1.585$; $10^{0.3} \approx 1.995$; $10^{0.4} \approx 2.512$; $10^{0.5} \approx 3.162$; $10^{0.6} \approx 3.981$; $10^{0.7} \approx 5.012$; $10^{0.8} \approx 6.310$; $10^{0.9} \approx 7.943$

Chiamiamo questi dieci valori (che evidentemente sono già in ordine crescente) “potenze”.

Passo 5: Prendiamo i duetti e le potenze, mettiamoli a fianco e vediamo la differenza in percentuale tra i valori corrispondenti:

$$
\begin{matrix}
n & \textrm{potenza} & \textrm{duetto} & \textrm{differenza} \\
0 & 1.000 & 1.0 & 0\% \\
1 & 1.259 & 1.28 & 2\% \\
2 & 1.585 & 1.6 & 1\% \\
3 & 1.995 & 2.0 & 0\% \\
4 & 2.512 & 2.56 & 2\% \\
5 & 3.162 & 3.2 & 1\% \\
6 & 3.981 & 4.0 & 0\% \\
7 & 5.012 & 5.12 & 2\% \\
8 & 6.310 & 6.4 & 1\% \\
9 & 7.943 & 8.0 & 1\% \\
\end{matrix}
$$

Una coincidenza notevole, vero? Ma sarà davvero una coincidenza o c’è qualcosa sotto? Vi lascio un paio di giorni per provare a trovare una spiegazione comprensibile di questa coincidenza. Sono buono e vi voglio aiutare: se provate con le prime venti potenze di 2 (e naturalmente fate crescere le potenze di 10 di un ventesimo anziché un decimo) la coincidenza non c’è. In compenso se provate le prime nove potenze di 6 e fate crescere di un nono le potenze di 10 la coincidenza è ancora maggiore, con un errore massimo dello 0.69%.