• In questa pagina trovate:
• Radici quadrate e Fattorizzazione
• Da Ramanujan a Mahlburg: partizioni e congruenze
• Non smettono di stupire i primi di Mersenne!
• Matematici premiati all'ICM di Madrid 2006
• Partizioni e numeri pentagonali
• Matematica e votazioni

6 Febbraio 2007

1  Potenza veloce

Se n è dell'ordine di 10²⁰ e il nostro supercomputer esegue 10 miliardi di operazioni al secondo, occorreranno [(10²⁰)/(10¹⁰)] = 10¹⁰ secondi, pari a più di trecento anni per calcolare la potenza. Il tempo cresce in modo esponenziale all'aumentare del numero delle cifre. Proviamo a passare da 20 a 40 cifre. Se n è dell'ordine di 10⁴⁰, ci vogliono [(10⁴⁰)/(10¹⁰)] = 10³⁰ secondi, pari a più di 3 ×10²² anni, ovvero 3 ×10⁴ ×10⁹ ×10⁹ anni: trentamila miliardi di miliardi di anni.

2  Congruenze quadratiche e Criterio di Eulero

Poichè ci sono soltanto n resti possibili quando si divide per n (ovvero gli interi 0, 1, 2, ..., n-1), ci si muove in un ambiente finito (tecnicamente: l'anello delle classi di resto modulo n, Z_n. Per una introduzione minima all'aritmetica modulare si vedano l' Aritmetica dell'orologio o l'Introduzione alla Crittografia Moderna).

L'equazione 4 si può dunque risolvere con una ricerca esaustiva. Per esempio se cerchiamo la radice quadrata di 2 modulo 23, possiamo calcolare la successione dei quadrati modulo 23:

1 4 9 16 2 ...

fermandoci non appena troviamo 2. A questo punto sappiamo che una soluzione di x² º 2 (mod 23) è 5.
Ovviamente le soluzioni vengono in coppie, se x² º a (mod n), anche (-x)² º a (mod n). Diciamo ±x soluzioni associate. Nel caso appena visto la soluzione associata a 5 è -5 ovvero 18 (-5 diviso per 23 dà resto 18).

E' chiaro che non sempre ci sono soluzioni. Osserviamo la sequenza dei quadrati modulo 11:

1 4 9 5 3 3 5 9 4 1

il numero 2 non compare, quindi la x² º 2 (mod 11) non ha soluzioni.

3  Soluzione della congruenza quadratica modulo p

Le successioni di Lucas V_n(P,Q) sono definite ricorsivamente (P e Q sono due interi dati):

4  Confronto con il metodo di Michele Cipolla

5  La fattorizzazione di N e le radici quadrate di 1 modulo N

Teorema

(Con MCD abbiamo denotato il Massimo Comun Divisore, che è computabile in modo efficace, con un metodo che viene da Euclide).

MCD(N, v - 1) = MCD(657530257, 195417582) = 17389

MCD(N, v + 1) = MCD(657530257, 195417584) = 37813

e trovare così velocemente la fattorizzazione di N.

Io penso che questo problema: trovare radici quadrate non banali di 1 modulo N, sia particolarmente interessante per coloro che vogliono avere un riconoscimento dalla comunità matematica. Se qualcuno (specialmente se non è un professionista della matematica) dice di avere risolto la congettura di Goldbach, o di avere dimostrato che esistono infiniti primi gemelli, si mette in una situazione difficile, piena di controlli e a volte di diffidenza e incredulità, o addirittura indifferenza. Questo è dovuto al fatto che da secoli i matematici più brillanti lavorano su questi problemi, cercando una risposta che non hanno ancora trovato. E al fatto che le dimostrazioni complesse presentano molto spesso lacune ed errori quasi invisibili (specialmente a chi le ha ideate). Ora, se vi dicono che la dimostrazione è sbagliata, potete non crederci, ma al tempo stesso, non potete convincere gli altri. E' frustrante. Se invece dite: i numeri si fattorizzano così e così, e non vi credono, avete una risposta definitiva: "datemi N e io ve lo fattorizzo!".

Se sapete trovare un numero maggiore di 1 il cui quadrato dia 1 modulo questo intero di appena 212 cifre:

74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359

A questo punto non solo avete guadagnato più di mezzo milione di dollari, ma tutti saranno certi che voi avete qualcosa di grande in mano (e soprattutto nella testa) e vi imploreranno di spiegare loro come fate!

Possibile che sia poi tanto difficile estrarre una radice quadrata? E di 1 poi!

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

24 Novembre 2006

Karl Mahlburg

Srinivasa Ramanujan

Il Professor Vittorino Andreoli, psichiatra di fama internazionale e autore di molti libri di successo, sta scrivendo un'opera monumentale, dal titolo "Principia", che attualmente esce a puntate nella sezione culturale (Agorà) della edizione domenicale di Avvenire. Nella parte iniziale dell'opera Andreoli si è occupato della "crisi della scienza", anzi - come lui stesso precisa - della crisi delle singole discipline. Dopo "Grandezza e miseria della Fisica" (Avvenire, 19 Febbraio 2006) è arrivato il turno della Matematica, con il titolo "Matematica, la crisi di una grande signora" (Avvenire, 12 Marzo 2006). Consiglio a tutti di leggere questo testo, affinché ognuno possa trarre le sue personali conclusioni. Non intendo in questa sede entrare nel merito delle affermazioni di Andreoli. Desidero soltanto riportare due frasi tratte dalla parte finale dell'articolo.

"Insomma, il teorema di Gödel stabilisce l'impossibilità di garantire la non contradditorietà della matematica restando all'interno della matematica stessa. Sembra un paradosso, ma la forza della matematica che doveva consistere nella sua capacità di dimostrare ogni affermazione logicamente, giunge ora a dimostrare semplicemente la propria incapacità a dimostrare. Un'atmosfera da tragedia, con Gödel nel ruolo di Euripide."

"La crisi della matematica ha il senso del crollo di quelle colonne che annunciano "muoia Sansone e tutti i filistei". Una sensazione che dovrebbe metterci come attorno al fuoco di un caminetto acceso, la sera, per riposarsi dal viaggio e meditare sul bisogno di sapere e sulla impressione, dopo aver visto tante cose, di non aver trovato ciò che si cerca. Io mi sento come chi ha visitato una vasta area archeologica, ha immaginato una grandezza passata ridotta adesso a sole macerie."

"Io direi questo: i matematici sono come uomini che costruiscono case. Non è soltanto piacevole vivere nelle case, esse consentono ai loro inquilini di fare molte cose che un abitante delle caverne non potrebbe mai realizzare. I matematici sono come uomini che costruiscono, sebbene non possano essere certi che un terremoto non distruggerà i loro edifici. Se un terremoto dovesse distruggere il loro lavoro, nuove costruzioni saranno edificate, e possibilmente più resistenti. Ma gli uomini non decideranno mai di smettere di costruire case, anche perché nemmeno vivere nelle caverne può dare una garanzia di assoluta salvaguardia dagli effetti di un terremoto. I matematici mi sembrano essere nella stessa situazione. La matematica non è soltanto un piacere in se stessa, ma è utile in molteplici importanti applicazioni. I suoi diversi edifici non sono al sicuro dal terremoto della contraddizione. Ma gli uomini non cesseranno per questo di migliorarli e di innalzarne di nuovi."

Altro che macerie!

Vorrei ora dare un'idea dell'ottima salute di cui gode la matematica, parlando del tema indicato nel titolo del Blog. Vedremo velocemente gli sviluppi del problema della divisibilità del numero delle partizioni di un intero dalle prime intuizioni, quasi visionarie, di Ramanujan, all'incredibile esito dei lavori di Ono e del giovanissimo Mahlburg. Sulle partizioni si veda il mio Blog precedente Partizioni e numeri pentagonali dal quale, per comodità del lettore, riporto qui sotto la definizione iniziale:

(1) Definizione

Il numero delle partizioni di n, denotato con p(n), è il numero dei modi di scrivere l'intero positivo n come somma di interi positivi, senza considerare l'ordine.

Esempio

p(5) = 7 perché 5 si può scrivere in 7 modi così:
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

p(6) = 11 perché 6 si può scrivre in 11 modi così:
6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1

Questi sono i primi valori di p(n) per n che va da 0 (si pone p(0) = 1) a 45:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134 (A000041)

Abbiamo già incontrato la funzione p(n) nel Blog "Sul numero dei gruppi finiti di un certo ordine": p(n) è il numero dei gruppi abeliani finiti di ordine qⁿ, con q primo.

Ramanujan scoprì che se si parte da p(4) = 5, e si procede con passi di lunghezza 5, p(n) è sempre divisibile per 5. Formalmente:

(2)

5 divide p(4 + 5k) per ogni k intero non negativo
Questa è la lista {p(4 + 5k)} = {p(4), p(9), p(14), p(19), ... }, con k da 0 a 10:

{5, 30, 135, 490, 1575, 4565, 12310, 31185, 75175, 173525, 386155}

p(28) = 3718 = 2 x 11 x 132

Le proprietà di divisibilità, sopra ricordate, trovate da Ramanujan nel 1919:

(5)

Teorema di Ramanujan

5 divide p(5 n + 4)
7 divide p(7 n + 5)
11 divide p(11 n + 6)

Fu il giovanissimo Freeman Dyson, studente a Cambridge nel 1944, ad avere una idea assolutamente innovativa.

Freeman Dyson

Dyson, che è un grande fisico e ha - tra l'altro - vinto il premio Templeton nel 2000, introdusse il concetto di rank di una partizione di n.

Diciamo rank(s), (o rango di s) dove s è una partizione di n, la differenza tra la parte più grande della partizione e il numero delle parti.

Esempi

Consideriamo la partizione di 24 s = {10,7,2,2,1,1,1}.
rank(s) = rank({10,7,2,2,1,1,1}) = 10 - 7 = 3, perché {10,7,2,2,1,1,1} è una partizione di 24, 24 = 10+7+2+2+1+1+1, la parte più grande è 10, e 24 è stato espresso come somma di 7 parti.

Poniamo ora s = {4,2,2,2,2,2,2,2,2,2,1,1}, un'altra partizione di 24.
Si ha ora rank(s) = rank({4,2,2,2,2,2,2,2,2,2,1,1}) = 4 - 12 = -8 perché {4,2,2,2,2,2,2,2,2,2,1,1} è una partizione di 24, 24 = 4+2+2+2+2+2+2+2+2+2+1+1, la parte più grande è 4, e 24 è stato espresso come somma di 12 parti.

Il rank di una partizione di n ha il massimo in n-1, corrispondente alla partizione {n}, ovvero n = n
e il minimo in 1-n, corrispondente alla partizione {1,1,1,1,....,1}, ovvero n = 1+1+1+...+1.

Dyson definì poi il numero N(t, m, n):

(6)

N(t, m, n) = numero delle partizioni di n il cui rango è congruo a t modulo m.

Equivalentemente:
N(t, m, n) = numero delle partizioni s di n, tali che il resto della divisione di rank(s) per m è uguale a t.

(7)

p(n) = N(0, m, n) + N(1, m, n) + N(2, m, n) + .... + N(m-1, m, n)

poiché i possibili resti della divisione per m sono 0, 1, 2, ... , m-1

(8)

Esempio

Vediamo il caso n=20 e m=13. Sotto si vede la distribuzione delle 627 partizioni di 20 in funzione del loro rango modulo 13:

{53, 54, 51, 49, 46, 44, 43, 43, 44, 46, 49, 51, 54}

Questo significa che ci sono 53 partizioni s di 20 tali che rank(s) è divisibile per 13 (resto 0), 54 tali che rank(s) è congruo a 1 modulo 13, 51 tali che rank(s) è congruo a 2 modulo 13, ... , 54 tali che rank(s) è congruo a 12 modulo 13.

E' interessante anche guardare all'interno delle singole classi. Prendiamo le 53 partizioni il cui rango è divisibile per 13. Di esse 4 hanno rango 13 (esempio {17,1,1,1}), 45 hanno rango 0 (esempio {10,2,1,1,1,1,1,1,1,1}), 4 hanno rango -13 (esempio {4,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}).

Vediamo ancora un caso, quello del resto 7. Ci sono 43 partizioni il cui rango diviso per 13 dà resto 7. Di queste 20 hanno rango 7 (esempio {14,1,1,1,1,1,1}), 22 hanno rango -6 (esempio {7,2,1,1,1,1,1,1,1,1,1,1,1}) e una ({1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}) ha rango -19.

per n = 4 + 5k e m = 5:

k = 0, n = 4, p(4) = 5, distribuzione del rango nelle classi di resto 0, 1, 2, 3, 4 = {1, 1, 1, 1, 1}
k = 1, n = 9, p(9) = 30, distribuzione del rango nelle classi di resto 0, 1, 2, 3, 4 = {6, 6, 6, 6, 6}
k = 2, n = 14, p(14) = 135, distribuzione del rango nelle classi di resto 0, 1, 2, 3, 4 = {27, 27, 27, 27, 27}
...

per n = 5 + 7k e m = 7:

k = 0, n = 5, p(5) = 7, distribuzione del rango nelle classi di resto 0, 1, 2, 3, 4, 5, 6 = {1, 1, 1, 1, 1, 1, 1}
k = 1, n = 12, p(12) = 77, distribuzione del rango nelle classi di resto 0, 1, 2, 3, 4, 5, 6 = {11, 11, 11, 11, 11, 11, 11}
k = 2, n = 19, p(19) = 490, distribuzione del rango nelle classi di resto 0, 1, 2, 3, 4, 5, 6 = {70, 70, 70, 70, 70, 70, 70}
...

(9) Congettura di Dyson

Per ogni intero naturale k, N(t, 5, 4 + 5k) = 1/5 p(4 + 5k) per ogni intero t compreso tra 0 e 4

Per ogni intero naturale k, N(t, 7, 5 + 7k) = 1/7 p(5 + 7k) per ogni intero t compreso tra 0 e 7

Si noti che la terza relazione provata da Ramanujan: 11 divide p(6 + 11k), non verifica la ovvia congettura, analoga alle (9).

Non è vero che per ogni intero naturale k, N(t, 11, 6 + 11k) = 1/11 p(6 + 11k) per ogni intero t compreso tra 0 e 4

Infatti per k = 0 abbiamo che p(6) = 11, ma i ranghi delle 11 partizioni non si ripartiscono equamente nelle 11 classi di resto.

Questa è la situazione:

rank({3, 2, 1}) = 0 = 0 mod 11
rank({4, 1, 1}) = 1 = 1 mod 11
rank({3, 3}) = 1 = 1 mod 11
rank({4, 2}) = 2 = 2 mod 11
rank({5,1}) = 3 = 3 mod 11
rank({6}) = 5 = 5 mod 11
rank({1, 1, 1, 1, 1, 1}) = -5 = 6 mod 11
rank({2, 1, 1, 1, 1}) = -3 = 8 mod 11
rank({2, 2, 1, 1}) = -2 = 9 mod 11
rank({2,2,2}) = -1 = 10 mod 11
rank({3, 1, 1, 1}) = -1 = 10 mod 11

Vi sono due partizioni il cui rango è congruo a 1, e due il cui rango è congruo a 10 (modulo 11), mentre le classi di resto 4 e 7 rimangono vuote.

In realtà, il mistero del crank era celato in un blocco di appunti scritti da Ramanujan nel 1919. Questi appunti furono trovati nel 1976 nella biblioteca del Trinity College, a Cambridge. All'inizio degli anni '80, Frank Garavan fece la sua tesi di Ph.D precisamente su un insieme di formule che gravitavano intorno alla formula del crank. Furono poi G. Andrews e lo stesso Garvan, nel 1988 a trovare la tanto ricercata funzione:

(10) Definizione di crank

Diciamo crank(s) (o c-rango di s) l'intero così definito:

detto r il numero degli 1 che appaiono in s:

se r = 0, poniamo crank(s) = parte più grande di s,

altrimenti diciamo t il numero delle parti di s strettamente più grandi di r, e poniamo crank(s) = t - r.

(11) Esempi

Riprendiamo il caso n = 6 + 11k, con k = 0, appena visto, sostituendo crank a rank.

Nella spiegazione si utilizzano r e t nel senso specifico assegnato loro dalla definizione (10).

crank({3, 2, 1}) = 1 = 1 mod 11, perché r = 1 e t = 2
crank({4, 1, 1}) = -1 = 10 mod 11, perché r = 2 e t = 1
crank({3, 3}) = 3 = 3 mod 11, perché r = 0 e la parte più grande è 3
crank({4, 2}) = 4 = 4 mod 11, perché r = 0 e la parte più grande è 4
crank({5,1}) = 0 = 0 mod 11, perché r = 1 e t = 1
crank({6}) = 6 = 6 mod 11, perché r = 0 e la parte più grande è 6
crank({1, 1, 1, 1, 1, 1}) = -6 = 5 mod 11, perché r = 6 e t = 0
crank({2, 1, 1, 1, 1}) = -4 = 7 mod 11, perché r = 4 e t = 0
crank({2, 2, 1, 1}) = -2 = 9 mod 11, perché r = 2 e t = 0
crank({2,2,2}) = 2 = 2 mod 11, perché r = 0 e la parte più grande è 2
crank({3, 1, 1, 1}) = -3 = 8 mod 11, perché r = 3 e t = 0

Come si vede ora i c-ranghi si ripartiscono equamente nelle 11 classi di congruenza (uno per classe).

Per k = 1 abbiamo n = 17. La distribuzione dei ranghi delle 297 partizioni di 17 nelle 11 classi modulo 11 è:

{29, 29, 28, 26, 26, 25, 25, 26, 26, 28, 29}

Come si vede i numeri variano da 25 a 29,

Se facciamo lo stesso con crank troviamo:

{27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27}

I c-ranghi si equi-ripartiscono nelle 11 classi (27 per classe).

Rimanevano tuttavia insoluti problemi fondamentali, tra i quali la congettura di Erdös:

Per ogni primo q esiste almeno un n tale che q divide p(n).

Sembra una congettura molto debole, ma è rimasta senza risposta fino a pochi anni fa!

Ken Ono, tra il 1998 e il 2000, dimostrò che:

(12) Teorema di Ken Ono

Per ogni primo q ³ 5 esistono infinite sequenze a + bk tali che

q divide p(a + bk) per ogni k.

(Le sequenze sono essenzialmente diverse, cioè non sono contenute una nell'altra.)

Per q = 13 i più piccoli a e b sono rispettivamente 237 e 13x11⁴ = 17203. Ovvero:

Per q = 17 la congruenza più semplice è la seguente:

Per q = 19, 23, 29, 31 abbiamo:

Davanti a questa infinità di congruenze trovate da Ono, ci si chiedeva, ovviamente, se la funzione crank potesse spiegare anche queste, oltre alle classiche tre di Ramanujan. A questo punto entra nella storia il giovanissimo Karl Mahlburg, allievo di Ken Ono, il quale - sebbene fortemente sconsigliato - si impegnò, nella sua tesi di Dottorato, a cercare la connessione perduta. Karl lottò per un anno con migliaia di formule apparentemente scorrelate e inespicabili, fino a quando vide la soluzione. Per i numeri primi q più grandi di 11, i valori di crank(s) non si equiripartiscono nelle classi modulo q, ma si suddividono in gruppi, ognuno dei quali ha ordine divisibile per q.

Per esempio, si può provare che 651 è divisibile per 31, suddividendolo in 31 gruppi ognuno formato da 21 elementi, ma anche ripartendolo in tre sottoinsiemi disgiunti che contengano rispettivamente 124, 341 e 186 elementi, perché 124, 341 e 186 sono tutti divisibili per 31.

Per potere esprimere uno dei risultati più importanti di Mahlburg, introduciamo la funzione M, del tutto analoga alla N definita da Dyson.

(13) Definizione

M(t, m, n) = numero delle partizioni di n il cui c-rango è congruo a t modulo m.

(14) Teorema di Karl Mahlburg

Siano dati un primo q maggiore di 3, e due interi positivi v e j. Allora esistono infinite sequenze a + bk, non contenute una nell'altra, tali che

q^v divide M(t, q^j, a + bk)

per ogni t compreso tra 0 e q^j-1.

p(a + bk) = å M(t, q^j, a + bk), con t che varia da 0 a q^j-1. (è la medesima situazione già osservata in (7))

Dunque q^v divide p(a + bk) perché, per il Teorema 14, q^v divide ogni termine della sommatoria.

Concludiamo con un pensiero di Dyson, che ha seguito tutta la vicenda, da quando aveva 22 anni:

" In questa storia ogni passo è un'opera d'arte, e la storia nel suo complesso è una serie di episodi di rara bellezza, un dramma edificato su null'altro che numeri e immaginazione. "

Congettura

Esistono infiniti interi n per i quali p(n) è un multiplo di 3.

{3, 7, 9, 10, 14, 16, 17, 20, 21, 22, 24, 26, 30, 32, 33, 35, 39, 40, 41, 43, 46, 48, 51, 52, 53, 57, 61, 63, 68, 70, 71, 75, 80, 88, 97, 102, 104, 106, 107, 111, 115, 124, 125, 129, 133, 138, 142, 147, 151, 160, 162, 163, 164, 169, 173, 178, 180, 181, 189, 191, 193, 195, 196, 198, 199, 200, 202, 207, 208, 209, 211, 214, 220, 221, 222, 223, 225, 226, 231, 232, 238, 239, 240, 249, 250, 257, 259, 266, 267, 268, 270, 277, 278, 281, 284, 286, 288, 289, 290, 296, 297, 298, 301, 304, 307, 314, 316, 319, 322, 330, 336, 339, 340, 341, 342, 347, 348, 350, 351, 353, 354, 357, 358, 361, 363, 365, 369, 372, 373, 374, 381, 382, 392, 394, 396, 398, 399, 402, 405, 411, 412, 415, 422, 424, 427, 429, 432, 434, 446, 449, 451, 460, 463, 465, 466, 468, 470, 472, 477, 480, 494, 496, 497, 499, 500, 501, 507, 508, 512, 521, 522, 524, 527, 531, 535, 536, 540, 542, 548, 550, 552, 553, 559, 562, 565, 566, 568, 570, 572, 573, 575, 579, 580, 587, 598}

George E. Andrews and Ken Ono, Ramanujan’s congruences and Dyson’s crank, Proceedings of the National Academy of Sciences, 102 (2005), 15277

A. O. L. Atkin and P. Swinnerton-Dyer, Some properties of partitions, Proc. London Math. Soc., 4 (1954), 84-106

Freeman Dyson, Some guesses in the theory of partitions, Eureka (Cambridge, U.K.) 8 (1944), 10-15

Frank Garvan, New combinatorial interpretations of Ramanujan’s partition congruences mod 5, 7 and 11, Trans. Amer. Math. Soc. 305 (1988), 47-77

Karl Mahlburg, Partition congruences and the Andrews-Garvan-Dyson crank, Proceedings of the National Academy of Sciences, 102 (2005), 15373-15376

Ken Ono, The partition function in arithmetic progressions, Mathematische Annalen, 312 (1998), 251-260

Ken Ono, Distribution of the partition function modulo m, Annals of Mathematics, 151 (2000), 293-307

Srinivasan Ramanujan, Congruences properties of partitions, Proceedings of the London Mathematical Society, 19 (1919), 207-210

29 Settembre 2006

Steven Boone, left, interim dean of the College of Arts and Sciences,
and Curtis Cooper, professor of computer science,
lead the team of researchers at Central Missouri State University
who discovered the largest prime number.
They are participants in the Great Internet Mersenne Prime Search,
which involves researchers from around the globe.
(Photo courtesy of CMSU)

Il 4 Settembre 2006 è stato scoperto il 44° numero primo di Mersenne!

Coloro che non conoscono i primi di Mersenne (ed i numeri perfetti pari ad essi collegati), possono cosultare il blog Il più grande numero primo noto, che contiene anche i collegamenti alle precedenti scoperte, nonché a diverse fonti di utili informazioni.

Qui di seguito riporto il numero delle cifre degli ultimi tredici primi di Mersenne scoperti, dal 32° al 44°, in un arco di quattordici anni, dal 1992 al 2006 (vedi l'elenco completo).

32°   --  227832  cifre
33°   --  258716  cifre
34°   --  378632  cifre
35°   --  420921  cifre
36°   --  895932  cifre
37°   --  909526  cifre
38°   --  2098960 cifre
39°   --  4053946 cifre
40°   --  6320430 cifre
41°   --  7235733 cifre
42°   --  7816230 cifre
43°   --  9152052 cifre
44°   --  9808358 cifre

Il 37° primo di Mersenne ha più di 900000 cifre, ed è stato scoperto nel 1998. Allora il "muro" da sfondare era quello del milione di cifre. Però la zona del milione di cifre si sarebbe rivelata vuota, il 38° primo di Mersenne ha più di due milioni di cifre! Come si vede dal grafico, la crescita del numero delle cifre ha una impennata tra il 37° e il 40°. Le zone dei tre e dei cinque milioni di cifre sono vuote! Sembra poi che la pendenza tenda a diminuire. Ora siamo, con il 44°, appena sotto ai dieci milioni di cifre. Ma quanto sarà grande il 45° campione? Nessuno lo sa. Tutti però scommettono che supererà la fatidica soglia dei dieci milioni, aggiudicandosi così il premio di 100000 $ offerto dalla Electronic Frontier Foundation.

Quanto è accaduto il 4 Settembre ha comunque dell'incredibile! Il 44° Mersenne è stato scoperto dallo stesso team che, il 15 Dicembre 2005, aveva trovato il 43°! Gli stessi Boone e Cooper (vedi la foto all'inizio) sono estremamente sorpresi. Cooper ci scherza sopra, dicendo che ci sono più probabilità di essere colpiti due volte da un fulmine che non di trovare due primi di Mersenne di queste dimensioni...
Presso la Central Missouri State University il software PrimeNet (dedicato a questa ricerca) gira su 850 computer. Alla GIMPS partecipano più di 46000 individui, o gruppi, con un fronte di fuoco di ben 71000 computer. Nel loro insieme - osserva Cooper - fanno ogni giorno il lavoro che un Pentium a 90Mh eseguirebbe in più di 1800 anni.

Queste ricerche ai limiti del possibile hanno molte ricadute nel quotidiano: si va dalle tecniche matematiche di calcolo veloce, all'hardware dei computer, al calcolo parallelo, alla comprensione sempre più profonda, e di illimitate potenzialità, dell'utilizzo di una rete mondiale di macchine e di intelligenze.

E la sfida continua!

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

29 Agosto 2006

Alhambra

Il 22 Agosto, nel corso della cerimonia di apertura dell' International Congress of Mathematicians che si tiene quest'anno a Madrid (22 - 30 Agosto), sono stati assegnati sei premi ad altrettanti matematici. Quattro medaglie Fields, un premio Nevanlinna ed un premio Gauss (assegnato per la prima volta).

La medaglia Fields è considerata l'equivalente del premio Nobel (che non esiste per la Matematica), e viene assegnata ogni quattro anni.
Vediamo chi sono i quattro vincitori, in ordine alfabetico.

Andrei Okounkov

Andrei Okounkov è nato a Mosca nel 1969 e ha conseguito il Dottorato in Matematica dalla Università di Stato di Mosca nel 1995. E' professore di Matematica presso l'Università di Princeton.

Nei suoi lavori Okounkov ha scoperto nuove e profonde connessioni tra diverse aree della Matematica: teoria della probabilità, teoria delle rappresentazioni e geometria algebrica.

Okounkov ha trovato che esiste una stretta (e del tutto inattesa) relazione tra la lunghezza massima di una sottosuccessione ordinata di una permutazione casuale di lunghezza n e il massimo autovalore di una matrice casuale di ordine n. Ha ottenuto questo risultato descrivendo in due modi diversi certe superfici casuali. Le tecniche che ha sviluppato hanno molte applicazioni.

Per esempio, durante il processo di liquefazione di un cristallo, si formano superfici casuali la cui proiezione su di un piano, ha provato Okounkov in collaborazione con Richard Kenyon, ha una forma assai particolare: è sempre circoscritta da una curva di equazione polinomiale.

Nella figura sottostante la curva che segna il confine tra la zona disciolta del cristallo e quella solida è una cardioide.

Ecco quello che pensa delle dimostrazioni matematiche:

"Ogni dimostrazione matematica dovrebbe contenere un ingrediente nuovo, qualcosa che non figura esplicitamente nell'enunciato del problema. Altrimenti la dimostrazione sarebbe in un certo senso ovvia o di routine. Il più delle volte non si deve cercare molto lontano, ma occasionalmente è effettivamente necessaria un'idea che proviene da una parte totalmente diversa della Matematica, come una spezia esotica. Sono sempre molto felice quando questo accade, perché rende la dimostrazione più soddisfacente sul piano estetico."

Grigory Perelman

Grigory Perelman è nato nel 1966 nell'ex Unione Sovietica. Ha ottenuto il Dottorato in Matematica dalla Università di Stato di San Pietroburgo, e durante gli anni '90 ha passato parecchio tempo negli USA, in particolare a Berkeley come Miller Fellow. Nel 1994 è stato 'invited speaker' all'ICM che si tenne a Zurigo.

La medaglia Fields è stata assegnata a Perelman per gli straordinari risultati che ha ottenuto nello studio della struttura analitica e geometrica del flusso di Ricci. I teoremi che Perelman ha dimostrato hanno un forte impatto in diversi campi, in particolare in topologia. Infatti i suoi lavori del 2002-2003 risolvono anche - sembra - la famosissima Congettura di Poincaré (chi è interessato può leggere questo articolo di Federico Peiretti: Poincaré e le n-sfere).

Da tre anni i massimi esperti del campo vagliano gli articoli di Perelman, e non sono stati trovati errori.

Per molti aspetti la vicenda di Perelman è alquanto strana, e su di essa sono stati scritti fiumi di inchiostro, forse anche perché per la soluzione della Congettura di Poincaré il Clay Mathematics Institute offre un milione di dollari di premio.

Nel corso di otto mesi, dal Dicembre 2002, Perelman pubblicò in rete tre articoli che hanno cambiato la storia della Matematica. La prima stranezza è che essi non sono stati inviati, come ci si aspetterebbe, ad una prestigiosa rivista professionale, ma messi a disposizione di tutti. Gli articoli, rispetto alla vastità degli argomenti affrontati e alla profondità dei risultati, sono assai scarni, quasi segni che indicano una strada ben precisa ma difficilmente percorribile se non si è più che esperti. E gli esperti sono intervenuti, hanno tentato di esplicare, di aprire la strada agli altri, con il risultato di circa un migliaio di pagine di teoremi.

Seconda stranezza: da Dicembre del 2005 Perelman ha lasciato l'Istituto Steklov, dove lavorava, e vive di risparmi con l'anziana madre nella periferia di San Pietroburgo. Immagino che si sia allontanato volontariamente: quale centro di ricerca licenzierebbe un ricercatore di tale levatura? L'attuale Presidente della Commissione per l'assegnazione delle medaglie Fields, Sir John Ball, lo ha raggiunto nel suo eremo e lo ha intervistato. Perelman ha rifiutato (è la prima volta che accade) la medaglia. Ha detto, pare, che non si sente di diventare un leader di una comunità dalla quale si sente isolato. Dicono che rifiuterà anche il premio Clay, se gli verrà assegnato.

Chi fosse interessato a conoscere (con un approccio giornalistico) la storia di Perelman, della congettura di Poincaré e dei personaggi coinvolti (per esempio il matematico Richard Hamilton) può leggere alcuni articoli che ho messo nelle Math News, per esempio:
Elusive Proof, Elusive Prover: A New Mathematical Mystery, The New York Times, 15 Agosto 2006
Ask Science: Poincaré's Conjecture, The New York Times, 18 Agosto 2006
MANIFOLD DESTINY, The New Yorker, 21 Agosto 2006
The Math Was Complex, the Intentions, Strikingly Simple, The New York Times, 27 Agosto 2006

Terence Tao

Riporto qui sotto alcune informazioni su Terence Tao e una sua considerazione sui problemi matematici, che traggo da un Blog precedente, nel quale si parlava di un suo lavoro sui gap tra i primi (fatto in collaborazione con Ben Green) che ha avuto un peso notevole nella assegnazione della medaglia Fields:
Il Teorema di Green - Tao: Esistono progressioni aritmetiche di primi di qualsiasi lunghezza!

Terence Tao (nato a Adelaide nel 1975) ottenne il PhD dalla Università di Princeton a soli 21 anni. Dall'età di 24 anni è "full professor" di Matematica presso l'università della California (UCLA). Viene considerato un "Mozart" della Matematica. Essa fluisce da lui apparentemente senza sforzo. Tao somiglia ai grandi del passato, perché i suoi interessi non sono limitati ad un solo settore della Matematica; egli si muove agilmente in campi assai diversi, dalla Geometria Algebrica, alla Combinatoria, Teoria Ergodica, Teoria dei Numeri e Analisi Armonica.

Penso che la descrizione che Terence Tao fa del suo lavoro sia molto interessante, e dovrebbe essere meditata dai tanti che credono che problemi rimasti insoluti da secoli si possano risolvere con un "lampo di genio". Ecco le sue parole:

"La maggior parte dei matematici che affrontano un problema, cercheranno di risolverlo direttamente. Anche quando ci riescono, non è detto che abbiano ottenuto una piena comprensione di quanto hanno fatto. Prima io esamino tutti i dettagli e elaboro una stategia. Una volta che ho una strategia, un problema molto complicato si può spezzare in un insieme di molti mini-problemi. ( ... ) Non è tanto una questione di essere abili o veloci. E' piuttosto come scalare una parete. Certamente è utile essere molto forti e agili, e avere tanta corda. Ma l'importante è individuare un percorso che consenta di arrivare fin lassù. Fare i calcoli in fretta e sapere tante cose è come scalare una roccia essendo forti, agili e muniti di buoni attrezzi. Però quello che ancora manca è un piano - è questa la parte difficile - e per averlo occorre una visione d'insieme."

Wendelin Werner

Wendelin Werner è nato in Germania nel 1968, ma è di nazionalità Francese. Ha conseguito il Dottorato in Matematica presso l'Università di Parigi VI nel 1993. E' professore a Orsay dal 1997 e dal 2005 insegna anche presso la Scuola Normale Superiore di Parigi.
Alcuni dei premi che ha vinto:
Rollo Davidson Prize (1998)
European Mathematical Society Prize (2000)
Fermat Prize (2001)
Jacques Herbrand Prize (2003)
Loève Prize (2005)
Pólya Prize (2006).

Werner ha ottenuto, nell'ambito della teoria delle probabilità, risultati la cui dimostrazione era ritenuta, fino ad allora, praticamente impossibile. Per esempio ha dimostrato una congettura di Mandelbrot del 1982: la dimensione frattale dell'inviluppo di un movimento browniano nel piano è 4/3.

movimento browniano nel piano

La cosa più sorprendente è che Werner ha utilizzato metodi che provengono dalla analisi complessa classica!

Gli è stata posta questa domanda:

"Lei è il primo probabilista a ricevere una medaglia Fields. Come si sente, a questo riguardo?"

Ecco la risposta di Werner:

"Certo sono molto contento che la teoria della probabilità abbia ottenuto questo riconoscimento. Può essere che questo sia un sintomo di un mutamento nella percezione della influenza della teoria della probabilità nella matematica in generale. Ovviamente mi sembra molto strano che io sia il primo probabilista a ricevere questo premio, vista la storia e tutto quello che si è realizzato in questo campo.
Vorrei però anche aggiungere che questa classificazione e divisione della matematica in sotto-settori non dovrebbe essere presa troppo sul serio. Spesso si hanno intuizioni nuove proprio quando si combinano idee provenienti da campi diversi.
In una certa misura questo è quanto è accaduto nell'ambito dei problemi sui quali ho lavorato, dove si è rivelata di importanza fondamentale l'analisi complessa."

Kiyoshi Ito

Kiyoshi Ito è nato nel 1915 in Giappone, ed è stato professore presso l'Università di Kyoto fino al suo ritiro, avvenuto nel 1979.

Dopo la laurea presso la Imperial University di Tokio, Ito lavorò per alcuni anni nel'ufficio nazionale di statistica. All'inizio degli anni '40 pubblicò alcuni lavori fondamentali che posero le fondamenta della teoria della analisi stocastica e delle equazioni differenziali stocastiche.

Le teorie di Ito sono state in seguito grandemente sviluppate, e oggi vengono utilizzate nei settori più diversi: analisi di mercato e dei rischi, filtraggio, dinamica delle popolazioni ...

Grazie a queste tecniche, per esempio, i biologi possono calcolare la probabilità di sopravvivenza di una specie, o quella che ha un gene di diventare dominante.

Per motivi di salute Ito non era presente alla cerimonia e il premio è stato ritirato dalla figlia più giovane, Junko, che ha una cattedra di linguistica a Santa Cruz.

Sir John Ball ha dichiarato che si recherà presto a rendere personalmente omaggio al grande Ito, anche per controbilanciare l'eccessiva attenzione che dalla stampa è stata data al caso Perelman, caso che in un certo senso ha rischiato di oscurare l'intero ICM 2006.

Il premio Nevanlinna viene assegnato ogni quattro anni in occasione dell'ICM per contributi rilevanti che riguardino gli aspetti matematici dell'informatica, includendo:

1. Teoria della complessità, logica dei linguaggi di programmazione, analisi degli algoritmi, crittografia, computer vision, pattern recognition, intelligenza artificiale etc.
2. Calcolo scientifico e analisi numerica. Aspetti computazionali della teoria della ottimizzazione e del controllo. Computer algebra.

Ha vinto il premio Jon Kleinberg.

Jon Kleinberg

Jon Kleinberg è nato nel 1971 a Boston (USA). Ha conseguito il Dottorato nel 1996 presso il MIT. E' professore di computer science alla Cornell University. Ha ottenuto molti riconoscimenti importanti, tra i quali, nel 2005, una MacArthur "genius" Fellowship dalla John D. and Catherine T. MacArthur Foundation.

Kleinberg è uno dei massimi esperti della teoria dei networks, in particolate del World Wide Web, della rete insomma.

Mentre le pagine di un singolo sito, come quelle che state leggendo, sono progettate con cura, la rete, ovvero Internet, nel suo insieme, non segue alcuna regola. Ogni giorno decine di migliaia di pagine - il cui contenuto è del tutto imprevedibile - vengono aggiunte o scompaiono. La quantità di informazione disponibile è, per un essere umano, talmente grande e disordinata da risultare del tutto inutilizzabile, a meno che non si presenti all'utente una particolare, e assai ristretta, selezione dei documenti che potrebbero interessarlo, in quanto riguardano l'argomento da lui scelto.

E' stato Kleinberg, nel 1966, a introdurre i concetti di "authorities" e "hubs", e abbiamo già incontrato questo brillante giovane nel Blog La matematica di Google , ove lo si citava per un suo illuminante articolo: Authoritative Sources in a Hyperlinked Environment.

Kleinberg ha ottenuto risultati sorprendenti sugli algoritmi che cercano il cammino più breve tra due nodi in un network, dove la conoscenza del network è soltanto locale, cioè ogni nodo conosce solo i suoi vicini. La probabilità che due nodi siano connessi nel network diminuisce con la loro distanza. Kleinberg a dimostrato che se la probabilità di connessione tra due nodi nel network diminuisce con il quadrato della distanza tra i nodi, allora esiste un algoritmo efficace per trovare il cammino più corto. Incredibilmente, Kleinberg ha provato che se questa probabilità decresce più velocemente, o più lentamente, del quadrato, allora non esistono algoritmi efficaci.

Le problematiche che riguardano il trattamento dei dati e la ricerca efficace di informazioni sono tra le più importanti al giorno d'oggi. In questo campo Kleinberg si distingue perché unisce intuito matematico e profonde conoscenze teoriche ad una costante attenzione all'uso effettivo che viene fatto della informatica.

La matematica però è molto, molto più grande. Ci sono altre congetture, altri problemi, altre immense zone sconosciute!

Insomma, c'è tanto da fare!

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

10 Giugno 2006

1 - Il numero delle partizioni

Il numero delle partizioni di un intero n p(n), interviene in infiniti problemi che si pongono in modo naturale in campi diversi, dalla combinatoria alla meccanica statistica.

1.1 Definizione

p(n) è il numero dei modi di scrivere l'intero positivo n come somma di interi positivi, senza considerare l'ordine.

Esempio

p(5) = 7 perché 5 si può scrivere in 7 modi così:
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1

p(6) = 11 perché 6 si può scrivre in 11 modi così:
6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1, 1+1+1+1+1+1

Questi sono i primi valori di p(n) per n che va da 0 (si pone p(0) = 1) a 45:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175, 89134 (A000041)

Abbiamo già incontrato la funzione p(n) nel Blog "Sul numero dei gruppi finiti di un certo ordine": p(n) è il numero dei gruppi abeliani finiti di ordine qⁿ, con q primo.

In pratica dobbiamo moltiplicare

(1.7)
1.	1 + 1 + 1 + 1
2.	1 + 1 + 2
3.	1 + 3
4.	2 + 2
5.	4

(1.8)
1.	x4 1  1 1
2.	x2 x2 1 1
3.	x 1 x3 1
4.	1 x4 1 1
5.	1 1 1 x4

(1.9)
1. 1 è stato preso 4 volte
2. 1 è stato preso 2 volte e 2 è stato preso 1 volta
3. 1 è stato preso 1 volta e 3 è stato preso 1 volta
4. 2 è stato preso 2 volte
5. 4 è stato preso 1 volta

Tecnicamente:

Il coefficiente di xⁿ nel prodotto (1.5) è il numero delle espressioni della forma:

k₁ + 2k₂ + 3k₃ .... = n.

In questa espressione k_j è il numero delle volte che si prende j.
Per esempio alla partizione di 14:
1 + 1 + 1 + 3 + 4 + 4
corrisponde l'espressione k₁ + 2k₂ + 3k₃ .... = 14, con k₁ = 3, k₃ = 1, k₄ = 2, e k_j = 0 per ogni j diverso da 1, 3 e 4.

Esempio

Per n = 7 si ha p_d(7) = 5.
Infatti, come somma di interi dispari, 7 si può scrivere così: 7, 1+1+5 ,1+3+3, 1+1+1+1+3, 1+1+1+1+1+1+1+1

Con il metodo di "traduzione" visto sopra queste partizioni corrispondono ai prodotti:

x⁷, nella quarta parentesi
x²x⁵, nella prima e terza parentesi
x x⁶, nella prima e seconda parentesi
x⁴x³, nella prima e seconda parentesi
x⁷, nella prima parentesi.

Seguono i primi 55 termini della succesione p_d(n) (si ricordi che inizia con n = 0):

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, 2304, 2590, 2910, 3264, 3658, 4097, 4582, 5120, 5718 A000009

Dunque il numero di modi di scrivere n come somma di interi dispari è sempre uguale al numero di modi di scrivere n come somma di interi diversi! E questo risultato si è ottenuto senza fatica alcuna, mediante una semplice osservazione!

Esempio

Sappiamo che p_d(7) = 5, Quindi si dovrà avere p_div(7) = 5.

Infatti:

7 = 7
7 = 1 + 6
7 = 2 + 5
7 = 3 + 4
7 = 1 + 2 + 4

(1.15)
p(100) = 190569292
p(200) = 3972999029388
p(300) = 9253082936723602
p(400) = 6727090051741041926
p(500) = 2300165032574323995027

C'è una sorpresa: la successione p(n) è ricorrente! Non si tratta però di una ricorrenza banale, come vedremo nel paragrafo seguente...

2 - Il Teorema Pentagonale di Eulero

In un articolo del 1751 Eulero pubblicò la funzione generatrice di p(n) (vista in 1.2):

(2.1)        ¥ Õ n=1  1 1-xn = 1 + x + 2x2 + 3x3 + 5x4 +7x5 + 11x6 + 15x7 + 22x8 + ¼+ p(n)xn + ¼

Al tempo stesso Eulero desiderava studiare il prodotto Õ(1-xⁿ), con n che va da 1 a infinito, e cominciò a calcolare qualche prodotto finito, come (1-x)(1-x²)(1-x³) ¼(1-x¹⁰⁰). I primi addendi di quest'ultimo sono:

(2.2)        1 - x - x2 + x5 + x7 - x12 - x15 + x22 + x26 - x35 - x40 + x51 + x57 - x70 - x77 + x92 + x100 - ¼

Chiunque nota che, dopo l'uno iniziale, si alternano due segni negativi e due positivi. E probabilmente anche occhi assai meno acuti di quelli di Eulero avrebbero notato che gli esponenti ...

Abbiamo già incontrato questi numeri, sono i numeri pentagonali, una particolare specie di numeri poligonali. Veramente la successione dei numeri pentagonali di solito viene fatta iniziare così:

(I) i numeri pentagonali P(n) si calcolano con la formula

(2.3)    P(n) = n + 3n(n-1)/2 = n(3n-1)/2

(II) la (2.3) si estende anche ai valori negativi di n

(2.11) - Prodotto di serie

Dato il prodotto di due serie:

(2.11.1)     ¥ å n=0  an xn   ¥ å n=0  bn xn = ¥ å n=0  cn xn

i coefficienti c_n della serie prodotto sono questi:

(2.11.2)    cn = n å k=0  ak bn-k

Ecco i primi c_n, calcolati utilizzando la (2.11.2):

(2.11.3)
c0 = a0b0
c1 = a0b1 + a1b0
c2 = a0b2 + a1b1 + a2b0
c3 = a0b3 + a1b2 + a2b1 + a3b0
c4 = a0b4 + a1b3 + a2b2 + a3b1 + a4b0
......

(2.12)
1 = c0 = 1p(0)                                                         
0 = c1 = 1p(1) + (-1)p(0)                                                    
0 = c2 = 1p(2) + (-1)p(1) + (-1)p(0)                                     
0 = c3 = 1p(3) + (-1)p(2) + (-1)p(1) + 0p(0)                         
0 = c4 = 1p(4) + (-1)p(3) + (-1)p(2) + 0p(1) + 0p(0)             
0 = c5 = 1p(5) + (-1)p(4) + (-1)p(3) + 0p(2) + 0p(1) + 1p(0) 
0 = c6 = 1p(6) + (-1)p(5) + (-1)p(4) + 0p(3) + 0p(2) + 1p(1) + 0p(6)
0 = c7 = 1p(7) + (-1)p(6) + (-1)p(5) + 0p(4) + 0p(3) + 1p(2) + 0p(1) +1p(0)
....

Dalle (2.12) si ottiene direttamente:

(2.13)
p(0) = 1
p(1) = p(0)
p(2) = p(1) + p(0)
p(3) = p(2) + p(1)
p(4) = p(3) + p(2)
p(5) = p(4) + p(3) - p(0)
p(6) = p(5) + p(4) - p(1)
p(7) = p(6) + p(5) - p(2) - p(0)

(2.14)

p(n) = p(n-1) + p(n-2) - p(n-5) - p(n-7) + p(n-12) + p(n-15) - p(n-22) - p(n-26) + ...

dove si pone p(k) = 0 se k è negativo (p(-1) = p(-2) = p(-3) = ... = 0).

(2.15)

p(n) = p(n-P(1)) + p(n-P(-1)) - p(n-P(2)) - p(n-P(-2)) + p(n-P(3)) + p(n-P(-3)) - p(n-P(4)) - p(n-P(-4)) + ...

dove, come prima, si pone p(k) = 0 se k è negativo

Proviamo ad utilizzare la formula di ricorrenza per estendere la lista dei primi 45 p(n), che segue immediatamente la definizione 1.1.

p(46) = p(46-1) + p(46-2) - p(46-5) - p(46-7) + p(46-12) + p(46-15) - p(46-22) - p(46-26) + p(46-35) + p(46-40) - p(46-51) - ... =

p(45) + p(44) - p(41) - p(39) + p(34) + p(31) - p(24) - p(20) + p(11) + p(6) + 0 = 105558

Si provi a calcolare s(45) + s(44) - s(41) - s(39) + s(34) + s(31) - s(24) - s(20) + s(11) + s(6). Si ottiene 72.

I divisori di 46 sono 1, 2, 23, 46. La loro somma è 72. Dunque:

s(46) = s(45) + s(44) - s(41) - s(39) + s(34) + s(31) - s(24) - s(20) + s(11) + s(6).

Ramanujan scoprì che se si parte da p(4) = 5, e si procede con passi di lunghezza 5, p(n) è sempre divisibile per 5. Formalmente:

(2.17)

5 divide p(4 + 5k) per ogni k intero non negativo
Questa è la lista {p(4 + 5k)} = {p(4), p(9), p(14), p(19), ... }, con k da 0 a 10:

{5, 30, 135, 490, 1575, 4565, 12310, 31185, 75175, 173525, 386155}

(2.18.1)

7 divide p(5 + 7k) per ogni k intero non negativo
Questa è la lista {p(5 + 7k)} = {p(5), p(12), p(19), p(26), ... }, con k da 0 a 10:

{7, 77, 490, 2436, 10143, 37338, 124754, 386155, 1121505, 3087735, 8118264}
(2.18.2)

11 divide p(6 + 11k) per ogni k intero non negativo
Questa è la lista {p(6 + 11k)} = {p(6), p(17), p(28), p(39), ... }, con k da 0 a 10:

{11, 297, 3718, 31185, 204226, 1121505, 5392783, 23338469, 92669720, 342325709, 1188908248}

p(28) = 3718 = 2 x 11 x 132

{28, 62, 84, 94, 129, 136, 173, 180, 197, 213, 219, 226, 227, 237, 240, 264, 294, 311, 318, 326, 335, 338, 357, 358, 389, 418, 453, 458, 473, 482, 484, 486, 508, 529, 538, 542, 562, 600, 635, 644, 668, 670, 684, 697, 699, 713, 714, 727, 742, 747, 751, 778, 783, 791, 794, 801, 804, 818, 831, 848, 859, 870, 890, 903, 918, 968, 970, 979, 999}

Comunicate problemi, soluzioni, novità, url interessanti, critiche, suggerimenti, domande, correzioni inviandomi una lettera!. Nel soggetto inserite 'mathblog'.

24 Aprile 2006

Valerio Marini, uno studente del 5° anno del liceo scientifico tecnologico, mi ha recentemente posto alcune domande, tra le quali la seguente:

• Lo studio a scuola della matematica può influire sulla futura consapevolezza nel voto?

Platone pensava che la democrazia fosse il peggior male dopo la tirannide. E c'è chi la ritiene un male necessario, nel senso che, purtroppo, non si è trovato nulla di meglio. Comunque sia, e in qualsiasi modo ci si arrivi, quando si arriva alla democrazia, il problema decisionale si presenta con tutta la sua forza. Come eleggere chi dovrà prendere le decisioni per il bene di tutti? All'interno dell'organismo eletto, diciamo il Parlamento, come garantire che le scelte operate rispecchino davvero la volontà della maggioranza? Dal 2004 a oggi, in almeno tre casi sulle prime pagine dei quotidiani sono apparse accese discussioni sulla efficienza e la credibilità del sistema democratico. In occasione della proclamazione della Costituzione Europea, della elezione del Presidente Bush e nelle recentissime elezioni politiche in Italia.

Il sistema di maggioranza qualificata europeo prevede che una decisione sia appoggiata dal 55% degli stati membri, e che questi al tempo stesso rappresentino il 65% della popolazione dell'Unione ([1]) E' un sistema a doppia maggioranza.

Questo sistema venne aspramente criticato, da più parti. Due studiosi, K. Zyczkowski e W. Slomczynski, dimostrarono in un articolo ([2]) pubblicato su Physics World che questo metoto tende a favorire sia gli stati più grandi che quelli più piccoli, a scapito dei medi. Essi proposero una alternativa, basata in parte sulle teorie dello psichiatra e matematico inglese Lionel S. Penrose:

• Il peso di uno stato S non deve essere proporzionale alla popolazione P di S, ma alla radice quadrata di P
• E' sufficiente allora una sola soglia, calcolata dagli autori intorno al 62%

Il caso Europeo è certamente molto particolare e può sembrare singolarmente difficile. In realtà il "problema del voto" è stato, nella sua generalità, a lungo studiato, con risultati niente affatto ovvii.

Qui ci limiteremo ad accennare al famoso "Teorema di Impossibilità" ([4]) di Kenneth J. Arrow , premio Nobel per l'economia nel 1972.

Arrow propose una assiomatizzazione del problema del "Social Welfare".

Presenteremo le idee di Arrow nella loro forma più semplice e al tempo stesso (assiomaticamente) più forte.

Cominciamo a fare un poco di pratica con i termini stessi del problema.

Lo scenario generale è il seguente:

Ci sono N votanti, che devono scegliere tra K alternative a₁, a₂, ... , a_K. Ogni votante ha una preferenza P che ordina le K alternative. Una preferenza è semplicemente un ordinamento, una disposizione delle alternative. Sono possibili K! preferenze.

Naturalmente, quasi sempre solo una parte delle preferenze possibili sarà effettivamente presente nella popolazione.

Esempio 1

Elezioni alla presidenza. Ci sono tre candidati: A, B, C e cento votanti. In questo caso sono possibili sei preferenze:

1. A B C
2. A C B
3. B A C
4. B C A
5. C A B
6. C B A

Diciamo profilo una distribuzione delle preferenze. Supponiamo di essere nella situazione seguente:

- Profilo 1 -
35 elettori hanno la preferenza 1 : A B C
33 elettori hanno la preferenza 5 : C A B
32 elettori hanno la preferenza 3 : B A C

Il sistema più ovvio di votazione è la maggioranza semplice. Si considerano solo i candidati che appaiono al primo posto, e tra questi si sceglie quello che ha più voti. Nel nostro caso tutti i candidati sono proposti come vincitori da una parte della popolazione. Tra i tre, A è quello che ha più voti e vince.

Molti accettano questo risultato senza discussioni, ma non è perfetto come può sembrare: osserviamo che il 65% dei votanti non vuole A come presidente.

Uno dei primi studiosi di queste problematiche fu Condorcet (Marie Jean Antoine Nicolas de Caritat, Marquis de Condorcet, 1743 - 1794), insigne filosofo e matematico francese. Condorcet partecipò attivamente alla Rivoluzione. In questo grandioso movimento egli vedeva l'incarnazione delle sue idee di razionalismo sociale. Prese posizione contro l'esecuzione di Luigi XVI e l'arresto dei Girondini. Per questo suo "moderatismo" fu costretto alla fuga e morì in carcere, in circostanze non chiare, nel 1794. E' notevole il fatto che proprio negli ultimi, dolorosi, anni Condorcet - invece di rinnegare i principi rivoluzionari - scriveva il famoso "Abbozzo di un quadro storico dei progressi dello spirito umano", nel quale presenta la storia dell'umanità nella forma di un progresso incessante che culminerà nella eliminazione delle diseguaglianze tra i popoli e tra gli individui, e nel perfezionamento della stessa natura umana.

Il metodo proposto da Condorcet è il seguente:

Un candidato vince se è anteposto a tutti gli altri da una maggioranza della popolazione.

Ricordiamo che una preferenza è un ordinamento. Quindi il Profilo 1 si interpreta così:

1   A > B > C per il 35% della popolazione
2   C > A > B per il 33% della popolazione
3   B > A > C per il 32% della popolazione

Pertanto:

A > B per il 68%, in quanto A > B appare in 1 e in 2
A > C per il 67%, in quanto A > C appare in 1e in 3

Dunque, anche con il principio di Condorcet A vince. Consideriamo un secondo profilo possibile.

- Profilo 2 -
35 elettori hanno la preferenza 1 : A B C
33 elettori hanno la preferenza 5 : C A B
32 elettori hanno la preferenza 4 : B C A

A continua a vincere, come prima, se si utilizza la maggioranza semplice: ai primi posti non è cambiato nulla.

Vediamo che cosa accade secondo Condorcet:

A > B per il 68%
A > C per il 35%
B > A per il 32%
B > C per il 67%
C > A per il 65%
C > B per il 33%

Non c'è nessun vincitore! A vince con B ma perde con C, B vince con C ma perde con A, C vince con A me perde con B. Quello che si ottiene non è un ordinamento, ma un risultato paradossale:

A > B > C > A

Questo risultato è detto, a volte, paradosso di Condorcet.

Questa situazione di stallo non si verifica mai con un altro notissimo metodo: il conteggio di Borda.

Jean-Charles Chevalier de Borda (1733 - 1799) fu un militare, matematico, scienziato e navigatore. Nel 1756 divenne membro dell' Accademia di Francia per i suoi lavori sul moto dei proiettili. Prese parte, in America, alla Guerra di indipendenza tra il 1777 e il 1778. Propose il suo sistema di conteggio proprio in alternativa a quello di Condorcet. Esso si basa sull'idea di attribuire un valore diverso alle posizioni che un candidato assume nelle preferenze che gli vengono date:

Supponiamo che ci siano K candidati (o alternative). Un primo posto nelle preferenze vale K punti, un secondo posto vale K-1 punti, ... , l'ultimo posto vale 1 punto. Vince chi ha il punteggio più alto.

Applichiamo il "Borda count" al Profilo 1.

A risulta primo in 35 preferenze e secondo in 65:
A prende 3 X 35 + 2 X 65 = 235 punti.
B risulta primo in 32 preferenze, secondo in 35 e terzo in 33:
B prende 3 X 32 + 2 X 35 + 1 X 33 = 199 punti.
C risulta primo in 33 preferenze e terzo in 67:
C prende 3 X 33 + 1 X 67 = 166 punti.

Risultato delle elezioni A > B > C

Proviamo ora con il Profilo 2.

A risulta primo in 35 preferenze, secondo in 33 e terzo in 32:
A prende 3 X 35 + 2 X 33 + 1 X 32 = 203 punti.
B risulta primo in 32 preferenze, secondo in 35 e terzo in 33:
B prende 3 X 32 + 2 X 35 + 1 X 33 = 199 punti.
C risulta primo in 33 preferenze, secondo in 32 e terzo in 35:
C prende 3 X 33 + 2 X 32 + 1 X 35 = 198 punti.

Risultato delle elezioni A > B > C

Si noti che con il metodo Borda c'è sempre un vincitore, e si evita il paradosso di Condorcet. Naturalmente sono possibili situazioni di parità, per le quali, in situazioni reali, occorrerà un apposito regolamento.

Il metodo Borda non va mai in stallo ma ha un difetto notevole, e non immediatamente visibile. Vediamo che cosa può accadere in un altro esempio.

I membri di una associazione organizzano una cena presso il lussuoso ristorante "Unica Scelta". Si tratta di un locale caratteristico, per grandi comitive, dove ci si serve a volontà al buffet per antipasti e dolci ma il piatto centrale deve essere uno solo per tutti.

Per questo piatto speciale ci sono quattro alternative:

a₁: pasta
a₂: pesce
a₃: pizza
a₄: pollo

Sono teoricamente possibili 24 preferenze:

• pasta - pesce - pizza - pollo
  
• pasta - pesce - pollo - pizza
  
• pasta - pizza - pesce - pollo
  
• pasta - pizza - pollo - pesce
  
• pasta - pollo - pesce - pizza
  
• pasta - pollo - pizza - pesce
  
• ....

    .....

• pollo - pizza - pesce - pasta

Però in realtà i soci si dividono in due soli gruppi:

59 condividono l'ordinamento pasta - pesce - pizza - pollo
e 41 l'ordinamento pizza - pesce - pollo - pasta

In base al metodo Borda abbiamo i seguenti punteggi:

la pasta ottiene 4 x 59 + 1 x 41 = 277 punti
il pesce ottiene 3 x 59 + 3 x 41 = 300 punti
la pizza ottiene 2 x 59 + 4 x 41 = 282 punti
il pollo ottiene 1 x 59 + 2 x 41 = 141 punti

Ordinamento collettivo risultante: pesce > pizza > pasta > pollo

E' utile che ci sia un ordinamento, come risultato della scelta collettiva, e non solo un vincitore. Infatti, se per per disgrazia dovesse quella sera mancare il pesce si sa già che cosa chiedere: la seconda scelta, ovvero la pizza.

I nostri cento amici arrivano all'"Unica Scelta", e prima ancora di sedersi si sentono dire: "Cari signori, vi avvertiamo che, purtroppo, non c'è il pollo!". Tutti alzano le spalle, "Tanto non ci interessa!". Ma uno dice "Rifacciamo un attimo i conti, cari amici!".

Ecco i nuovi punteggi:

In assenza di pollo la distribuzione di preferenze diventa:
59 condividono l'ordinamento pasta - pesce - pizza
e 41 l'ordinamento pizza - pesce - pasta

la pasta ottiene 3 x 59 + 1 x 41 = 218 punti
il pesce ottiene 2 x 59 + 2 x 41 = 200 punti
la pizza ottiene 1 x 59 + 3 x 41 = 182 punti

Ordinamento collettivo risultante: pasta  > pesce > pizza

I soci sono stupiti, ma si tratta di gente seria: si è scelto questo metodo e lo si deve seguire fino in fondo!

Alcuni discutono del fatto durante la cena, mentre mangiano la pasta (per altro ottima). "Avevamo scelto il pesce, ed è arrivata la pasta! Dicono che il cambiamento sia dovuto alla mancanza del pollo! Ma scusa, il pollo che cosa c'entrava?", "Hai ragione! L'alternativa del pollo non esisteva, per tutti era l'ultima o penultima scelta! Però il risultato è cambiato eliminandola... Sembra che il metodo di Borda dipenda da alternative irrilevanti! Mah! ... "

Ricordiamo che sono dati N votanti (che costituiscono la popolazione), ognuno dei quali possiede una preferenza (un ordinamento) riguardo a K alternative. Abbiamo chiamato profilo una lista delle preferenze della popolazione. Diciamo funzione di scelta sociale una funzione S che ad ogni possibile profilo p associ un ordinamento delle alternative S(p). L'ordinamento S(p) è l'ordinamento collettivo, quello che, proprio in base al principio democratico, deve essere accettato da tutti. Abbiamo appena visto alcuni esempi. Si noti che il metodo di Condorcet non è una fuzione di scelta sociale, perché, come si è visto sopra, il risultato può non essere un ordinamento delle alternative.

Diciamo che una funzione di scelta sociale:

1. Rispetta il principio di unanimità se dato un profilo p nel quale si trovi A > B in tutte le preferenze individuali, allora risulta A > B nella preferenza collettiva S(p).
2. E' indipendente dalle alternative irrilevanti se la posizione di A rispetto a B nella preferenza collettiva S(p) dipende solo dalle posizioni relative di A e B nelle preferenze individuali che formano il profilo p (e non da alternative C diverse sia da A che da B, e quindi non rilevanti nel confronto tra A e B).
3. E' non dittatoriale se non esiste un cittadino D tale che, per ogni profilo p, la preferenza collettiva S(p) coincide sempre con l'ordinamento individuale di D.

Se ci sono almeno tre alternative, non esiste una funzione di scelta sociale per la quale valgano simultaneamente 1, 2 e 3.

Segue in particolare che soltanto nelle dittature possono valere sia il principio di unanimità che quello di indipendenza dalle alternative irrilevanti.

In realtà la situazione è meno drammatica di quello che non sembri. Il principio 2 (che è il vero motore della dimostrazione di Arrow) è necessariamente rispettato quando si consideri il comportamento razionale di un singolo individuo. Ma è probabilmente illusorio ritenerlo vero nelle decisioni colettive, nelle quali la sola presenza di C può spostare voti da A a B. Inoltre il teorema di Arrow non vale più se si pongono restrizioni alle preferenze individuali. Le cose cambiano se, per esempio, si suppone che le spese per la Sanità debbano sempre superare quelle per lo Sport....

Lo studio delle funzioni di scelta sociale, dei metodi per passare da insiemi di milioni di preferenze individuali a una preferenza collettiva, è estremamente importante, è oggetto di attive e fruttuose ricerche e viene affrontato con avanzate tecniche matematiche. E' possibile però in modo semplice mostrare che si tratta di un problema complesso e delicato, che riguarda tutti. E forse nei Licei si potrebbe dedicare a questo un paio di ore.

Concludo con tre osservazioni:

• Il problema del come votare è complesso.
  
• Prima di cambiare un sistema elettorale i governi dovrebbero riflettere molto bene, e ascoltare il parere di veri esperti.
  
• Una volta che sia stato scelto un sistema elettorale, i risultati delle votazioni devono essere accettati, anche quando non coincidono con quanto si sperava!

[1] Il nuovo sistema di voto a maggioranza qualificata
[2] K. Zyczkowski e W. Slomczynski - Voting in the European Union: The square root system of Penrose and a critical point
[3] La Matematica delle Elezioni dal sito della rivista Rudi Mathematici
[4] Kenneth J. Arrow, Difficulty in the Concept of Social Welfare, (1950) The Journal of Political Economy, 58, 328-346.