• In questa pagina trovate:
• [55] Primi Gemelli e Famose Costanti
• [56] Numeri complessi e terne pitagoriche
• [57] L'albero di Pitagora
• [58] Il paradosso del compleanno
• [59] Formule per i numeri primi
• [60] Frazioni e periodi

27 Luglio 2008

Introduciamo due notazioni.

La scrittura    a | b    è un modo veloce per asserire che " a divide b". Per esempio 3 | 15, 641 | (2³² + 1), (x + y) | (x² - y²), ...

L'espressione    z mod n    denota il resto della divisione di z per n.

Per esempio 25 mod 7 = 4, 15 mod 3 = 0, 48 mod 10 = 8, 2³¹ mod 31 = 2, ...

Nel seguito utilizzeremo, senza particolari commenti, le seguenti (ben note) proprietà
(Ricordo che due interi si dicono coprimi se non hanno fattori in comune (ovviamente 1 non viene considerato))

-------------------------------------------------------------------
Se a è coprimo con c, e a | bc allora a | b.

a mod n = b mod n se e solo se n | (a - b)
-------------------------------------------------------------------

Qualsiasi intero z è rappresentato in Z_n, mediante il suo resto z mod n.

In Z_n è contenuto un sottoinsieme molto interessante, che indichiamo con U_n

(1) Esempi

U₅ = {1, 2, 3, 4}

U₆ = {1, 5}

U₉ = {1, 2, 4, 5, 7, 8}

U₁₅ = {1, 2, 4, 7, 8, 11, 13 14}

(2) Esempio

Prodotto in U₁₅

7*8 = 56 mod 15 = 11; 11*13 = 143 mod 15 = 8; 4² = 16 mod 15 = 1; 13*7 = 91 mod 15 = 1 ...

(3) Proposizione

Siano a, x, y elementi di U_n. Allora

a*x = a*y   implica   x = y

Dimostrazione

L'ipotesi a*x = a*y in U_n significa che ax mod n = ay mod n, e quindi n | (ax - ay).
Poiché n | a(x - y) ed n è coprimo con a, n deve dividere x - y, e pertanto x = y.

Denotiamo con #X l'ordine di X.

Poniamo φ(n) = #U_n. La funzione φ è detta funzione di Eulero, ed è estremamente importante in tutta la teoria dei numeri.

(4) Proposizione

Ogni elemento a di U_n possiede un inverso, ovvero

"aÎU_n $bÎU_n : a*b = 1 (per ogni a in U_n esiste un b in U_n tale che a*b = 1)

Dimostrazione

Poniamo f_a(x) = a*x, e q = φ(n) = #U_n.
Poniamo U_n = {x₁, x₂, ... , x_q}.
Per la proposizione (3) gli elementi f_a(x₁), f_a(x₂), ... , f_a(x_q) sono tutti distinti, e pertanto sono i q elementi di U_n.
Dal momento che 1 Î U_n, deve esistere un b in U_n tale che f_a(b) = 1, e segue la tesi.

(5) Esempio

Nelle due righe sottostanti elenchiamo gli elementi di U₁₅ e i rispettivi inversi

1  2  4  7  8  11 13 14
1  8  4  13 2  11 7  14

(6) Osservazione

Sia a un elemento di U_n.

Se U_n = {x₁, x₂, ... , x_q}, allora {a*x₁, a*x₂, ... , a*x_q} è una permutazione di U_n

(7) Teoremi di Eulero e di Fermat

Per ogni a in U_n

a^φ(n) mod n = 1 (Eulero)
se n è primo, a^n-1 mod n = 1 (Fermat)

Dimostrazione

Per quanto detto nella Osservazione (6)

∏x_i = ∏(a*x_i),     con 1 ≤ i ≤q
da cui segue
∏x_i = a^φ(n)∏x_i mod n
e infine (semplificando) a^φ(n) mod n = 1.

Il Teorema di Fermat segue subito, dal momento che se n è primo allora φ(n) = n-1 (perché tutti gli interi positivi che precedono p sono coprimi con p).

Calcolo di φ(n)

Se p è primo, φ(p^e) è, per definizione, il numero degli interi positivi che precedono p^e e sono coprimi con p^e. Equivalentemente φ(p^e) è il numero degli interi positivi che precedono p^e e non sono divisibili per p. Poiché un intero ogni p è divisibile per p, ci sono, tra 1 e p^e, esattamente p^e/p = p^e-1 interi divisibili per p.

Dunque φ(p^e) = p^e - p^e-1 = p^e-1(p - 1).

Non è difficile provare che se a, b sono interi coprimi allora φ(ab) = φ(a)φ(b).

Da quanto detto segue che se conosciamo la decomposizione di n nel prodotto di primi

n = p1e1p2e2 ... pcec

allora possiamo cacolare φ(n) con questa formula

φ(n) = ∏p_j^e_j-1(p_j - 1), con 1 ≤ j ≤ c

Per il Teorema di Eulero, se a è coprimo con n, l'insieme S degli interi positivi s tali che a^s = 1 mod n non è vuoto, infatti φ(n) Î S. Ogni insieme non vuoto S di interi positivi possiede un minimo. Diciamo t questo minimo: t è, per definizione, il periodo di a modulo n.

(8) Definizione di periodo

Dato a coprimo con n, il periodo di a modulo n è il minimo intero positivo t tale che a^t = 1 mod n.

Se a è coprimo con n, denotiamo con per_n(a) il suo periodo modulo n.

(9) Esempi

Gli esempi sono formati da due righe, nella prima appaiono gli elementi di U_n, nella seconda i rispettivi periodi.

--- n = 7 ---

1,2,3,4,5,6
1,3,6,3,6,2

--- n = 15 ---

1,2,4,7,8,11,13,14
1,4,2,4,4, 2, 4, 2

--- n = 21 ---

1,2,4,5,8,10,11,13,16,17,19,20
1,6,3,6,2, 6, 6, 2, 3, 6, 6, 2

--- n = 23 ---

1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22
1,11,11,11,22,11,22,11,11,22,22,11,11,22,22,11,22,11,22,22,22, 2

Naturalmente, per ogni n, per_n(1) = 1: 1 è sempre il primo elemento che appare nella prima come nella seconda riga.

Al medesimo tempo 1 è sempre l'unico elemento di U_n che ha periodo 1, come segue dalla definizione stessa di periodo.

Per ogni n, i numeri che appaiono nella seconda riga ( i periodi) dividono la lunghezza della prima riga (che è φ(n) = #U_n).

Quando n è primo (n = 7, n = 23) vi sono elementi di periodo n-1 (per₇(3) = 6, per₂₃(5) = 22).

In effetti queste osservazioni sono sempre vere:

(10) Lemma e Teorema

Premettiamo, senza dimostrazione, il seguente

Lemma 10

10-a

Se n è primo e q è un intero positivo qualsiasi, esistono al più q elementi a Î U_n tali che a^q = 1 mod n.

10-b

Dati a, b Î U_n, esiste un elemento c Î U_n tale che

per_n(c) = mcm(per_n(a), per_n(b))
(mcm(x, y) è il minimo comune multiplo di x e y)

Teorema 10

(10-1) per_n(a) = 1 se e solo se a = 1
(10-2) dati comunque a, n, x     a^x = 1 mod n   implica   per_n(a) | x
(10-3) se n è primo esiste sempre un a tale che per_n(a) = n - 1

(10-4) se a Î U_n allora per_n(a) | φ(n)

(10-5) se n è primo e a Î U_n allora per_n(a) | n - 1

(10-6) se a Î U_n e per_n(a) = t, allora per ogni divisore d di t esiste in U_n almeno un elemento di periodo d

(10-7) se n è primo, esistono in U_n elementi di periodo d, per ogni divisore d di n - 1

Dimostrazione

(10-1)

Evidente.

(10-2)

Supponiamo

(A)   a^x = 1 mod n
Osserviamo che a^x = 1 mod n implica a Î U_n. Pertanto è definito il periodo di a modulo n.
Poniamo t = per_n(a).
Se dividiamo x per t otteniamo

x = qt +r

dove q è il quoziente della divisione e r è il resto    0 ≤ r < t.
Allora si ha

1 = a^x = a^qt+r = (a^t)^qa^r = a^r mod n

ove si è utilizzato il fatto che a^t = 1 mod n. Ricordiamo ora che t è il minimo intero positivo che verifica (A). Poiché anche r verifica (A) ed è strettamente minore di t, r non può essere positivo, e pertanto è nullo. Segue che x = qt, e la 10-2 è dimostrata.

(10-3)

Supponiamo n primo.

Diciamo m il minimo comune multiplo dei periodi degli elementi di U_n

m = mcm({per_n(a) : a Î U_n})

Per il Teorema di Fermat 7 e la proprietà 10-2 appena provata si ha che per_n(a) | n - 1, per ogni a Î U_n. Pertanto
m | n - 1 e, in particolare, m ≤ n - 1.

Poiché per_n(a) divide m per ogni a Î U_n, si ha, per ogni a Î U_n, a^m = 1 mod n. U_n contiene n - 1 elementi, e tutti soddisfano l'equazione a^m = 1 mod n. Pertanto per il Lemma 10-b n - 1 ≤ m, e segue n - 1 = m. Dal momento che n - 1 è il minimo comune multiplo dei periodi degli elementi di U_n, per il Lemma 10-b (applicato ripetutamente) esiste in U_n un elemento di periodo n-1.

(10-4)

Deriva dal Teorema di Eulero e dalla 10-2.

(10-5)

Deriva dal Teorema di Fermat e dalla 10-2.

(10-6)

Se d | t, allora t = sd. E' facile vedere che a^s ha periodo d.

(10-7)

Deriva dalla 10-3 e dalla 10-6.

Ci occuperemo ora di frazioni, ovvero di numeri razionali, della forma x = m/n, dove m ed n sono interi.

Ovviamente possiamo supporre, senza restrizioni, che le frazioni siano ridotte, ovvero che il numeratore e il denominatore siano coprimi.

Ci limiteremo inoltre al caso in cui m ed n siano entrambi positivi.

Dividendo m per n abbiamo:

dove q, r sono rispettivamente il quoziente e il resto della divisione. Si ha sempre: 0 ≤ r < n. Dividendo entrambi il lati per n:

L'intero q è detto parte intera di x, e si denota con [x]. Il razionale (strettamente minore di 1) r/n è detto parte frazionaria di x, e si denota con {x}. Quanto ci interessa non dipende per nulla dalla parte intera. Possiamo quindi supporre che x sia strettamante compreso tra 0 ed 1, ovvero x = {x}.

Riassumendo, riterremo sempre tacitamente verificate le seguenti ipotesi, dato x = m/n:

1. m, n sono interi positivi
   
2. MCD(m, n) = 1
   
3. m < n

Apparentemente la notazione m/n dice già tutto. Si divide l'unità in n parti, e di queste se ne prendono m. C'è qualcosa di non ancora rivelato?

E' possibile scoprire cose nuove semplicemente scrivendo m/n in un altro modo?

In effetti i metodi escogitati dall'uomo per identificare e scrivere i numeri sono estremamente interessanti, e hanno una loro interiore efficacia, spesso inattesa.

Attualmente la notazione più utilizzata è quella posizionale in base B (nel seguito B è sempre un intero positivo maggiore di 1).

Denotiamo con c_i le cifre. Le cifre sono comprese tra 0 e B-1.

Il numero x = m/n si scrive in base B, in modo unico, così:

L'espressione B-naria di x = m/n si trova attraverso successive divisioni per il denominatore n.

Vediamo tre esempi in base 10.

(11) Esempi

Base B = 10.

(11-1)
x = 3/4

10 ´ 3 = 7 ´ 4 + 2
10 ´ 2 = 5 ´ 4 + 0

Quindi 3/4 = 0,75

(11-2)
x = 4/7

10 ´ 4 = 5 ´ 7 + 5
10 ´ 5 = 7 ´ 7 + 1
10 ´ 1 = 1 ´ 7 + 3
10 ´ 3 = 4 ´ 7 + 2
10 ´ 2 = 2 ´ 7 + 6
10 ´ 6 = 8 ´ 7 + 4
10 ´ 4 = 5 ´ 7 + 5
10 ´ 5 = 7 ´ 7 + 1
... ...

Quindi 4/7 = 0,57142857...

(11-3)
x = 5/12

10 ´ 5 = 4 ´ 12 + 2
10 ´ 2 = 1 ´ 12 + 8
10 ´ 8 = 6 ´ 12 + 8
10 ´ 8 = 6 ´ 12 + 8
... ...

Quindi 5/12 = 0,4166...

0,75, sviluppo finito
0,57142857..., sviluppo puramente periodico
0,4166..., sviluppo periodico

Conveniamo di scrivere in rosso la parte che si ripete per sempre. Allora i tre casi diventano:

3/4 = 0,75
4/7 = 0,571428
5/12 = 0,416

Diciamo lunghezza del periodo il numero delle cifre che si ripetono (secondo la nostra convenzione è il numero delle cifre scritte in rosso).
Quindi 4/7 ha periodo di lunghezza 6, e 5/12 ha periodo lungo 1.
Se lo sviluppo è periodico, ma non puramente periodico, vi è un antiperiodo. Per esempio 5/12 ha un antiperiodo di lunghezza 2 formato dalle cifre 41.

Formalizziamo ora la procedura che trasforma un razionale x = m/n nella sua espressione B-naria.

(12) Procedura di trasformazione frazione -> espressione B-naria

Sia dato x = m/n.

Poniamo r₀ = m.

B ´ r₀ = c₀ ´ n + r₁
B ´ r₁ = c₁ ´ n + r₂
...
B ´ r_k = c_k ´ n + r_k+1
...

I c_k, k = 0, 1, 2, ..., k, ... sono le cifre della espressione binaria.
La successione r_k, k = 0, 1, 2, ..., k, ..., viene detta successione dei resti.

Questa procedura si può sempre effettuare all'infinito: ad ogni passo si divide un certo intero per n (non nullo), e questo è sempre possibile. La procedura termina in un modo, che non è un vero e proprio terminare quanto piuttosto un seguitare all'infinito in maniera prevedibile.

Termina in due casi diversi.

1) Termina se un resto r_j è nullo: in questo caso tutte le cifre successive sono 0.

2) Termina quando si trova un resto già apparso in precedenza.

Nel caso 2) la sequenza dei resti è periodica. Se 0 ≤ k < h e r_k = r_h, allora si avrà r_k+1 = r_h+1, r_k+2 = r_h+2, ..., r_k+(h-k) = r_h = r_k, ... Se poniamo t = h - k, la sequenza dei resti è periodica con periodo t a partire da r_k, ovvero

Si badi bene che, se la procedura non termina con resto 0, necessariamente si ripeterà un resto, perchè ad agni passo si divide per n, e ci sono soltanto n-1 resti non nulli.

Osserviamo inoltre che la cifra c_k è determinata dal resto r_k, infatti se dividiamo per n l'espressione

Pertanto le successioni dei resti e delle cifre sono entrambe finite oppure periodiche.

Possiamo ora dimostrare un importante Teorema.

(13) Teorema

Un numero reale α è razionale se e solo se il suo sviluppo B-nario (in qualsiasi base B) è finito oppure periodico.

Dimostrazione

Ovviamente è suffiente provare il teorema per i numeri reali compresi tra 0 ed 1, (quelli con parte intera 0).

Abbiamo appena visto che, se α è razionale allora, indipendentemente dalla base B, il suo sviluppo B-nario è finito oppure è periodico. Proviamo allora il viceversa. Il caso dello sviluppo finito è banale. Supponiamo che lo sviluppo di α sia periodico:

α = 0,c₀c₁...c_k-1c_kc_k+1....c_h-1

Evidentemente α è razionale se e solo se lo è β

β = 0,c_kc_k+1....c_h-1

β è, per definizione, la somma di questa serie:

β = (c_k´B^-1 + c_k+1´B^-2 + ... + c_h-1´B^-t) + (c_k´B^-(t+1) + c_k+1´B^-(t+2) + ... + c_h-1´B^-2t) + ...

(dove si sono associati i blocchi di lunghezza uguale al periodo t = h - k)

Poniamo S = c_kB^t-1 + c_k+1B^t-2 + ... c_h-2B + c_h-1. Si noti che S, scritto in B-nario, è il numero c_kc_k+1...c_h-1.

Segue che

β = S(B^-t + B^-2t + ... + B^-it + ...)

Ricordiamo che se 0 < b < 1, allora 1 + b + b² + ... + bⁱ + ... = 1/(1 - b) (vedi per esempio il Blog In onore di Pi)

Pertanto b + b² + ... + bⁱ + ... = 1/(1 - b) - 1 = b/(1 - b). Ponendo b = B^-t otteniamo

B^-t + B^-2t + ... + B^-it + ... = 1/(B^t - 1)

e infine

β = S/(B^t - 1) = c_kc_k+1...c_h-1/(B^t - 1)

Quindi β è un razionale. Di conseguenza lo è anche α, e il teorema è dimostrato.

(14) Corollario

Se lo sviluppo B-nario di un numero reale è infinito e non periodico, allora il numero stesso è irrazionale.

Per esempio il numero

g_B = 0,10100100010000100000100000001....

formato, nella parte decimale, da uno intercalati, successivamente, da 1, 2, 3, 4, 5 ... zeri è non periodico, e pertanto è irrazionale!

Si noti che g_B non è un numero, ma rappresenta infiniti numeri diversi (tutti irrazionali) al variare della base B.

Precisamente

g_B = B^-τ₁ + B^-τ₂ + B^-τ₃ + .... + B^-τ_n + ...

dove τ_n è l'n-esimo numero triangolare, τ_n = n(n+1)/2 (vedi Quadrati Triangolari e Ricorrenze, dove però τ_n è denotato con P_n⁽³⁾)

Per B = 2, 3, 4 abbiamo

g₂ = 0,6416325606...
g₃ = 0,3717591173...
g₄ = 0,2658700952...
(i numeri sono scritti in base 10)

(e ovviamente g₁₀ = 0,1010010001... :)

Data la frazione x = m/n si scriva il suo sviluppo B-nario, x = 0,c₀c₁...c_k-1c_kc_k+1....c_h-1.

In questo paragrafo risponderemo, tra l'altro, a queste domande:

Quali sono le lunghezze del periodo e dell'antiperiodo? Quando lo sviluppo di x è finito? Quando è puramente periodico? La lunghezza t del periodo dipende dal numeratore m? Si può eprimere in modo diretto t come funzione della base B e del denominatore n?

Ci servono un paio di definizioni.

(15) Definizioni di ν_B(n), θ_B(n), ρ_B(n)

Supponiamo che la decomposizione di B nel prodotto di numeri primi sia

B = p1e1p2e2 ... pcec

Diciamo che un intero g è un intero B-adico se la sua decomposizione nel prodotto di numeri primi è

g = p1f1p2f2 ... pcfc

dove gli esponenti f_j sono interi qualsiasi non negativi. Gli f_j possono benissimo essere 0: per esempio il numero 1 è un intero B-adico su qualsiasi base B (ed è l'unico intero che gode di questa proprietà). Quello che conta è che l'insieme dei primi che dividono g sia contenuto nell'insieme dei primi che dividono B.

E' evidente che se n è un intero B-adico esiste sempre un esponente s tale che n | B^s. Diciamo il più piccolo di questi s B-altezza di n. La B-altezza dell'intero B-adico n sarà denotata con ν_B(n). Si ricordi sempre che la B-altezza è definita solo se n è un intero B-adico.

Il numero 1, per ogni base B, è l'unico intero che ha B-altezza 0.

Esempi

ν_B(1) = 0.
ν₄₅(9) = 1.
ν₄₅(75) = 2.
ν₁₀(8) = 3.
ν₁₀(50) = 2.
ν₃₀(9) = 2.
ν₃₀(75) = 2.
ν₃₀(8) = 3.
ν₃₀(50) = 2.

Alcune osservazioni.

Basi diverse possono avere lo stesso insieme di interi B-adici. Per esempio n è 15-adico se e solo se è 45-adico. Però possono cambiare le altezze, cioè le rispettive funzioni ν_B, anche se definite sugli stessi insiemi, non sono uguali. Per esempio ν₄₅(9) = 1, mentre ν₁₅(9) = 2.

Dato un intero positivo n diciamo parte B-adica di n il più grande intero B-adico che divide n. Denoteremo la parte B-adica di n con θ_B(n).

Diciamo poi parte B-prima di n l'intero ρ_B(n) = n/θ_B(n). Chiaramente ρ_B(n) è il più grande divisore di n coprimo con B.

Esempi

n       =  90 91 92 93 94 95 96 97 98 99 100
θ10(n)   = 10  1  4  1  2  5  32 1  2  1 100
θ6(n)    = 18  1  4  3  2  1  96 1  2  9 4

Vi sono due casi estremi: se n è un intero B-adico allora θ_B(n) = n e ρ_B(n) = 1, se n è coprimo con B θ_B(n) = 1 e ρ_B(n) = n.

(16) Teorema

Sia x = 0,c₀c₁...c_k-1c_kc_k+1....c_h-1 lo sviluppo B-nario di x = m/n.

Sia n = θ_B(n)ρ_B(n) (vedi le Definizioni (15)).

Allora k è la B-altezza di θ_B(n) e t è il periodo di B modulo ρ_B(n).

Dimostrazione

Ricordiamo la procedura per il calcolo delle cifre di x in base B:

Si pone r₀ = m.

B ´ r₀ = c₀ ´ n + r₁
B ´ r₁ = c₁ ´ n + r₂
...
B ´ r_k = c_k ´ n + r_k+1
...

Vediamo l'intera procedura modulo n. Poiché n = 0 mod n, la procedura diventa

B ´ r₀ = r₁ mod n
B ´ r₁ = r₂ mod n
...
B ´ r_k = r_k+1 mod n
...

La prima riga si può riscrivere Bm = r₁ mod n, e la seconda B(Bm) = r₂ mod n = B²m mod n, e così via. Quindi, in generale

(D)   B^jm = r_j mod n

La (D) vale per ogni intero j ≥ 0.

Abbiamo osservato più volte che la sequenza dei resti è periodica. Esistono k, h minimi 0 ≤ k < h tali che r_k = r_h.

Sappiamo che k è la lunghezza dell'antiperiodo e t = h - k è la lunghezza del periodo. Se r_k = r_h, dalla (D) si ottiene

B^hm = B^km mod n

e pertanto n divide B^hm - B^km = m(B^h - B^k). Poiché per ipotesi m ed n sono coprimi, n deve dividere B^h - B^k. Infine si ha

(E)    n | B^k(B^t - 1)

Ricordiamo le Definizioni (15) e poniamo u = θ_B(n) e v = ρ_B(n).

Poiché B^t - 1 è coprimo con B, la (E) vale se e solo se u | B^k e v | (B^t - 1). A noi interessano i più piccoli u e v. Da quanto precede dovrebbe essere chiaro che

k = ν_B(u)
t = per_v(B)

(17) Corollario 1

Un numero razionale x = m/n ha sviluppo finito in base B se e solo se n è un intero B-adico.

Dimostrazione

Se x ha sviluppo finito 0,c₀c₁...c_k-1, allora x = m/n =c₀c₁...c_k-1/B^k = s/B^k. Segue che n | B^k e pertanto n è B-adico.

Viceversa, se n è B-adico, esiste un k tale che n | B^k, ovvero B^k = sn. Allora x = m/n = (sm)/B^k, e x ha sviluppo finito in base B.

(18) Corollario 2

Un numero razionale x = m/n ha sviluppo puramente periodico in base B se e solo se n è coprimo con B.

Dimostrazione

Per definizione x ha sviluppo puramente periodico in base B se e solo se l'antiperiodo ha lunghezza 0. Per il teorema 16 questo è vero se e solo se l'altezza della parte B-adica di n è zero. Questo equivale a dire che la parte B-adica di n è 1: dunque n coincide con la sua parte B-prima.

Dati x = m/n e la base B:

Lo sviluppo di x in base B è finito se e solo se θ_B(n) = n (Equivalentemente ρ_B(n) = 1)

In tutti gli altri casi lo sviluppo è periodico con lunghezza del periodo t = per_n(B). Inoltre

Lo sviluppo è puramente periodico se e solo se θ_B(n) = 1. Altrimenti esiste un antiperiodo di lunghezza ν_B(n)

(19) Procedura di trasformazione espressione B-naria -> frazione

Supponiamo assegnati:

una base B
un antiperiodo c₀c₁...c_k-1
un periodo c_kc_k+1....c_h-1

Vogliamo trovare la frazione x = m/n alla quale corrisponde lo sviluppo B-nario α = 0,c₀c₁...c_k-1c_kc_k+1....c_h-1

La lunghezza dell'antiperiodo è k, la lunghezza del periodo è t = h - k.

Prima di tutto trasformiamo l'antiperiodo e il periodo in numeri:

nant = c₀B^k-1 + c₁B^k-2 + ... + c_k-1

nper = c_kB^t-1 + c_k+1B^t-2 + ... + c_h-1

Nel corso della dimostrazione del Teorema 13 abbiamo visto che β = nper/(B^t - 1) = 0,c_kc_k+1....c_h-1

Adesso dobbiamo fare spazio all'antiperiodo, dobbiamo aggiungere k zeri dopo la virgola a β. Calcoliamo dunque β' = β/B^k

L'antiperiodo viene rappresentato dal numero B-adico γ = nant/B^k

E infine, sommandoli, otteniamo α = γ + β'

α = nant/B^k + nper/(B^k(B^t - 1))

Esempi

Scegliamo questa forma numerica, che si può leggere in tutte le basi:

α = 0,111100

I dati seguenti restano fissi per ogni base B:

ant = 11
per = 1100
k = 2
t = 4

Ora calcoliamo il valore delle frazioni corispondenti per le basi B = 2, 8, 10.

B = 2
nant = 3
nper = 12

α = 3/2² + 12/(2²(2⁴-1) = 3/4 + 12/(4´15) = 3/4 + 12/60 = 19/20

B = 8
nant = 9
nper = 576

α = 9/8² + 576/(8²(8⁴-1) = 9/64 + 576/(64´4095) = 9/64 + 576/262080 = 4159/29120

B = 10
nant = 11
nper = 1100

α = 11/10² + 1100/(10²(10⁴-1) = 11/100 + 1100/(100´9999) = 11/100 + 1100/999900 = 10099/90900

Si noti la forma numerica di α può sembrare ambigua.

Infatti la forma seguente dà luogo allo stesso numero:

α = 0,11110011

In questo caso i parametri sono

ant = 1111
per = 0011
k = 4
t = 4

Naturalmente rifacendo i calcoli si trovano le stesse frazioni.

Una analisi più approfondita fa sparire la ambiguità. La lunghezza del periodo, ricordiamolo, è ν_B(θ_B(n)), ovvero l'altezza della parte B-adica di n. Con B = 2 si ha n = 20, la parte 2-adica è 4 che ha altezza 2. Con B = 8 si ha n = 29120 = 2⁶ ´ 5 ´ 7 ´ 13, la parte 8-adica è 64 che ha altezza 2. Con B = 10 si ha n = 90900, la cui parte 10-adica è 100 che ha altezza 2.

In tutti i tre casi, se eseguite la procedura di trasformazione frazione - espressione B-naria, osserverete che la sequenza dei resti comincia a ripetersi da r₂. Quindi l'antiperiodo ha lunghezza 2, e l'espresione corretta di α è la prima che è stata data.

Questo fatto non è casuale, è un caso particolare del famoso Teorema di Midy, che vedremo nel prossimo paragrafo.

Per il Teorema di Midy ci servono due Lemmi

(20-1) Lemma

Supponiamo n primo.

Se a Î U_n e t = per_n(a) = 2h, allora a^h = n-1 mod n.

Dimostrazione

Per ipotesi a^2h = 1 mod n. Poniamo z = a^h mod n. Allora z² = 1 mod n. Per il Lemma 10-a, con q = 2, esistono al più due soluzioni di z² = 1. Effettivamente esse esistono e sono ovviamente 1, -1. Si noti che -1 = n-1 mod n. Non si può avere z = 1 mod n, perché altrimenti avremmo a^h = 1 (mod n) e il periodo di non sarebbe 2h. Quindi z = a^h = n-1 mod n.

Esempio

n = 43, a = 2
per₄₃(2) = 14
2⁷ = 42 mod 43

(20-2) Lemma

Supponiamo che α sia un numero reale positivo non intero.

Allora [-α] = -[α] - 1

Dimostrazione

Supponiamo che [α] = b. Per definizione b è il più grande intero minore di α. Ovvero b < α < b + 1.

Quindi -(b + 1) < α < - b, e segue la tesi.

(21) Teorema di Midy

Supponiamo n primo e B non divisibile per n.
Supponiamo che la frazione x = m/n abbia periodo pari, t = 2h.

x = 0,c₀c₁...c_2h-1
Allora se si divide il periodo in due parti U e V di lunghezza h, la sequenza delle cifre di V è il complemento a B-1 della sequenza delle cifre di U.

Equivalentemente:    c_j + c_j+h = B - 1    per ogni j, con 0 ≤ j ≤ h-1

Si noti che se consideriamo U e V come numeri interi e non soltanto come successioni di cifre, allora il teorema asserisce che

U + V = B^h - 1

Dimostrazione

Vediamo un esempio, per chiarire quanto vogliamo provare.

Siano x = 51/73 e B = 10. Allora x = 0,69863013. Abbiamo t = 8, h = 4.

U = 6986, V = 3013 e 6986 + 3013 = 9999 = 10⁴ - 1.

Sappiamo che, nelle ipotesi fatte, lo sviluppo B-nario di x è puramente periodico.
La successione delle cifre è c₀c₁...c_2h-1c₀c₁....
La successione dei resti sia r₀ = m, r₁, ..., r_h-1, r_h = r₀, r_h+1 = r₁ ...

La lunghezza t del periodo è il periodo di B modulo n: t = 2h = per_n(B). Dal Lemma 20-1 segue che B^h = - 1 mod n (scriviamo -1 invece di n-1 per comodità). Ricordando che r_k = B^kr₀ mod n, si ottiene che
r_h = - r₀ mod n, r_h+1 = - r₁ mod n, e in generale r_j+h = n - r_j (torniamo a scrivere, correttamente, n - a, invece di -a mod n) per ogni j, con 0 ≤ j ≤ h-1.

Ovvero la successione dei resti si divide in due parti di lunghezza h, dove i resti della seconda parte sono i complementi a n dei resti della prima parte. Nell'esempio fatto (x = 51/73) la successione dei resti è 51, 72, 63, 46, 22, 1, 10, 27. In effetti si ha che 51 + 22 = 73, 72 + 1 = 73, 63 + 10 = 73, 46 + 27 = 73.

Consideriamo un indice s = j + h, con 0 ≤ j ≤ h-1. Abbiamo visto che r_s = n - r_j. Sappiamo che i resti determinano le cifre secondo questa formula:

c_s = [Br_s/n]

Quindi c_s = [Br_s/n] = [B(n - r_j)/n] = B + [ - Br_j/n] = B - [Br_j/n] - 1, per il Lemma 20-2.

Del resto

c_j = [Br_j/n]

e pertanto c_s = B - c_j - 1 e infine

∀j  0 ≤ j ≤ h-1   c_j+h + c_j = B - 1

7, 11, 13, 17, 19, 23, 29, 47, 59, 61, 73, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 157, 167, 179, 181, 193, 197, 211, 223, 229, 233, 241, 251, 257, 263, 269, 281, 293, 313, 331, 337, 349, 353, 367, 373, 379, 383, 389, 401, 409, 419, 421, 433, 449, 457, 461, 463, 487, 491, 499, 503, 509, 521, 541, 557, 569, 571, 577, 593, 601, 607, 617, 619, 641, 647, 653, 659, 661, 673, 677, 691, 701, 709, 727, 739, 743, 761, 769, 809, 811, 821, 823, 829, 857, 859, 863, 877, 881, 887, 929, 937, 941, 953, 967, 971, 977, 983, 997

Si tratta di 109 primi su 168 primi minori di 1000.

Segue l'elenco delle lunghezze dei 109 periodi di 10 modulo questi primi

6, 2, 6, 16, 18, 22, 28, 46, 58, 60, 8, 44, 96, 4, 34, 108, 112, 42, 130, 8, 46, 148, 78, 166, 178, 180, 192, 98, 30, 222, 228, 232, 30, 50, 256, 262, 268, 28, 146, 312, 110, 336, 116, 32, 366, 186, 378, 382, 388, 200, 204, 418, 140, 432, 32, 152, 460, 154, 486, 490, 498, 502, 508, 52, 540, 278, 284, 570, 576, 592, 300, 202, 88, 618, 32, 646, 326, 658, 220, 224, 338, 230, 700, 708, 726, 246, 742, 380, 192, 202, 810, 820, 822, 276, 856, 26, 862, 438, 440, 886, 464, 936, 940, 952, 322, 970, 976, 982, 166

I primi p minori di 1000 tali che la base 2 ha periodo pari modulo p sono 117:

3, 5, 11, 13, 17, 19, 29, 37, 41, 43, 53, 59, 61, 67, 83, 97, 101, 107, 109, 113, 131, 137, 139, 149, 157, 163, 173, 179, 181, 193, 197, 211, 227, 229, 241, 251, 257, 269, 277, 281, 283, 293, 307, 313, 317, 331, 347, 349, 353, 373, 379, 389, 397, 401, 409, 419, 421, 433, 443, 449, 457, 461, 467, 491, 499, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 613, 617, 619, 641, 643, 653, 659, 661, 673, 677, 683, 691, 701, 709, 733, 739, 757, 761, 769, 773, 787, 797, 809, 811, 821, 827, 829, 853, 857, 859, 877, 883, 907, 929, 941, 947, 953, 971, 977, 997

E queste sono le lunghezze dei periodi:

2, 4, 10, 12, 8, 18, 28, 36, 20, 14, 52, 58, 60, 66, 82, 48, 100, 106, 36, 28, 130, 68, 138, 148, 52, 162, 172, 178, 180, 96, 196, 210, 226, 76, 24, 50, 16, 268, 92, 70, 94, 292, 102, 156, 316, 30, 346, 348, 88, 372, 378, 388, 44, 200, 204, 418, 420, 72, 442, 224, 76, 460, 466, 490, 166, 508, 260, 522, 540, 546, 556, 562, 284, 114, 144, 586, 148, 612, 154, 618, 64, 214, 652, 658, 660, 48, 676, 22, 230, 700, 708, 244, 246, 756, 380, 384, 772, 786, 796, 404, 270, 820, 826, 828, 852, 428, 858, 876, 882, 906, 464, 940, 946, 68, 194, 488, 332

Concludiamo con due domande. La risposta alla prima è nota, mentre nessuno sa rispondere alla seconda.

Domanda 1

Abbiamo visto che, se n è primo, per_n(B) divide sempre n - 1, per ogni base B coprima con n.

Il numero 561 non è primo. Però si può constatare che per₅₆₁(B) divide 560 per ogni base coprima con 561.

Per esempio se B = 10, 500/561 = 0.8912655971479500 ha periodo 16, ovvero per₅₆₁(10) = 16, che divide 560.

Potete verificare che questo vale per ogni base B che non sia divisibile per 3, 11 e 17.

Esistono altri numeri non primi con questa proprietà? Come si possono caratterizzare? Ce ne sono infiniti?

Domanda 2

Se n è primo, può accadere che una base B abbia periodo n - 1 (sappiamo che in ogni modo per_n(B) divide n - 1).

Questi sono i primi p minori di 1000 tali che 10 ha il massimo periodo possibile p - 1:

7, 17, 19, 23, 29, 47, 59, 61, 97, 109, 113, 131, 149, 167, 179, 181, 193, 223, 229, 233, 257, 263, 269, 313, 337, 367, 379, 383, 389, 419, 433, 461, 487, 491, 499, 503, 509, 541, 571, 577, 593, 619, 647, 659, 701, 709, 727, 743, 811, 821, 823, 857, 863, 887, 937, 941, 953, 971, 977, 983

Questo elenco può proseguire all'infinito? (Si veda A001913 in OEIS)

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

12 Marzo 2008

1 - Introduzione

Ricevo, con una certa frequenza, lettere di appassionati della teoria dei numeri, non professionisti, che mi annunciano, con giusta trepidazione, di avere risolto il mistero dei numeri primi.

Ma qual è poi questo mistero?

La cosa principale da avere in mente è che esistono due principali punti di vista sui numeri primi:

• L'approccio algoritmico (i primi visti da vicino)
• L'approccio qualitativo (i primi visti da lontano)

Nel primo caso le domande sono, per esempio:

• A.1 Quali e quanti sono i primi minori di N?
• A.2 Qual è il primo numero primo dopo N?
• A.3 N è primo?

• Q.1 Come aumenta il numero dei primi minori di N al crescere di N?
• Q.2 Che cosa si può dire sull'intervallo tra due primi consecutivi?
• Q.3 Ci sono infiniti primi p di una certa forma (per esempio p = n² + 1)?

Non è lo stesso per quelle di tipo Q, specialmente quando pongono un quesito preciso. Non è per nulla detto che l'umanità, anche in un remoto futuro, scopra la verità riguardo a Q.3.

Le domande Q.1 e Q.2 non possiedono, per loro stessa formulazione, una risposta univoca. La risposta migliore che abbiamo a Q.1 è data dal Teorema dei Numeri Primi:

In (TNP) la funzione p(x) è la funzione che "conta" i primi: p(x) è il numero dei numeri primi che precedono x.

Il (TNP) dice che p(x) è asintoticamente uguale a x/log(x). Ovvero:

lim x® ¥  p(x)log(x) x = 1

In questo Blog ci occupiamo esclusivamente dell'approccio algoritmico. Uno degli algoritmi più antichi è certamente il Crivello di Eratostene.

Il Crivello di Eratostene, se portato abbastanza avanti, ci fa vedere tutti i primi minori di N, li scopre: essi sono i sopravvissuti alla cancellazione!

Il Crivello di Eratostene

Scriviamo i numeri interi da 2 a N.

Cancelliamo i multipli di 2, 2 escluso, dalla lista.

Prendiamo il primo intero rimasto dopo 2 (che è 3) e cancelliamo tutti i multipli di 3, 3 escluso, dalla lista.

Prendiamo il primo intero rimasto dopo 3 (che è 5) e cancelliamo tutti i multipli di 5, 5 escluso, dalla lista.

......

Prendiamo il primo intero rimasto dopo p_k-1 (che è p_k) e cancelliamo tutti i multipli di p_k, p_k escluso, dalla lista.

......

Fermiamoci quando p_k supera la radice quadrata di N.

Poiché ogni numero composto possiede un fattore primo minore o uguale alla sua radice quadrata, gli interi rimasti nella lista sono tutti e soli i primi compresi tra 2 e N.

         Per esempio, per trovare i primi fino a N = 25, poiché 6 è maggiore della radice quadrata di 25, è sufficiente setacciare
         fino a 6:

Lista iniziale: {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25}

Elimino i multipli propri di 2:

{2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25}

Elimino i multipli propri di 3:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 25}

Elimino i multipli propri di 5:

{2, 3, 5, 7, 11, 13, 17, 19, 23}

Poiché il primo intero sopravvissuto è 7, che è maggiore di 6, sono primi tutti gli interi rimasti.

Chi vuole può esercitarsi con questo Crivello in Java-script, creato da H.B. Meyer, Faust-Gymnasium Staufen

Ebbene, moltissime formule esistono già in letteratura, tutte inutili al calcolo effettivo, ma vere. Alcune non aggiungono nulla a quanto si sa, sono quasi delle "trovate". Altre invece, pur se inefficaci, sono affascinanti. Ne vedremo alcune.

2 - Una funzione F(x) che vale 0 se e solo se x è un numero primo

Il famoso teorema di Wilson asserisce che un intero n è primo se e solo se:

(TW)     (n - 1)! ≡ -1 (mod n)

Equivalentemente: un intero n maggiore di 1 è primo se e solo se il quoziente (1 + (n - 1)!)/n è intero.

H. C. Pocklington nel 1911 introdusse la funzione F(x) così definita

F(x) = F2(x) + Y2 æ è 1 + G(x) x ö ø

G(x) = ó õ ¥ 0  tx-1 e-t  dt

(TP)     Per ogni intero x maggiore di 1, F(x) = 0 se e solo se x è un numero primo

Pertanto un intero x maggiore di 1 è primo se e solo se

Non è una bella formula? Prendete un qualsiaisi x reale maggiore di 1. Per la (F1), F(x) = 0 se e solo se x è un numero intero primo!

Non è stato, però, svelato alcun mistero.

Spiegazione di (F1)

Basta ricordare questi fatti:

1. La funzione sin(px) si annulla se e solo se x è un intero.
2. La funzione G(n), con n intero positivo, vale (n-1)!
3. Per (TW) (1 + (n-1)!)/n è intero se e solo se n è primo oppure n = 1.

Sotto vedete il grafico di F(x), per x compreso tra 1 e 16:

La F(x) si annulla in
1, 2, 3, 5, 7, 11. 13

La funzione F(x) descrive esattamente l'insieme dei numeri primi. Essa però non dice nulla di più del Teorema di Wilson (TW).

Il Teorema di Wilson, può essere effettivamente utilizzato, con i calcolatori moderni, per testare la primalità di interi non grandi.

Si noti che non è vero, come si legge persino su alcuni testi di teoria dei numeri, che il Teorema di Wilson è inutilizzabile perché x! cresce troppo velocemente. E' verissimo che la crescita di x! è catastroficamente grande, al crescere di x, è una crescita più che esponenziale. Ma è anche vero che noi dobbiamo soltanto calcolare (n - 1)! modulo n, e non (n - 1)! in sè.

Il programma giusto per testare la primalità di n con (TW) non è questo:

x = 1;
for( j = 1, j < n, ++j ) {
x = j * x }
y = x % n;
if( y == n - 1 )
return(1);
else
return(0);

x = 1;
for( j = 1, j < n, ++j ) {
x = (j * x) % n }
if( x== n - 1 )
return(1);
else
return(0);

Frammenti di codice in C. Ricordiamo che a%n è il resto della divisione di a per n, ovvero a%n = a mod n

Si noti che gli interi che intervengono nel calcolo non superano mai n - 1.

Facciamo un esempio. Se n = 132241, (n - 1)! è un numero di 619821 cifre. Occorrono centinaia di pagine per scriverlo. Ma a noi non interessa in realtà 13240!, ma 13240! mod 132241. Gia per n = 9, n! supera 132241, e quindi si riduce:

9! = 362880, pertanto 9! mod 132241 = 98398. Proseguendo

10! mod 132241 = 983980 mod 132241 = 58293, etc....

In tutti i passi non si supera mai n - 1 = 132240.

In questo modo 132240! mod 132241 = 132240 viene calcolato in meno di un secondo sul mio portatile (e questo prova che 132241 è primo).

Il problema non è la crescita di n!, ma il fatto che devo fare n moltiplicazioni e divisioni. Se n ha 80 cifre l'algoritmo deve fare 10⁸⁰ passi, cosa che è del tutto impraticabile, in tempi umani.

3 - Un risultato sorprendente

Ricordiamo che ëaû denota la parte intera di a.

Nel 1946 Mills pubblicò il seguente incredibile risultato

(TM)

Esiste un numero reale q tale che bn =  ë q3n û è primo per n = 1, 2, 3, 4, ...

(TI)

Esiste una costante k tale che per ogni x tra x e kx^5/8 c'è sempre un numero primo.

p_n+1 -  p_n < kp_n^5/8

Recentemente (2005) Chris K. Caldwell e Yuanyou Cheng hanno provato (utilizzando la Congettura di Riemann) che

(TCC)

Per ogni x maggiore di 0,26 tra x³ e (x + 1)³ c'è sempre un numero primo.

(Si noti che nessuno è in grado di provare che tra x² e (x + 1)² c'è sempre un numero primo, anche se si ritiene che sia vero.)

Costante di Mills

In linea di principio (i calcoli effettivi sono molto pesanti) è possibile calcolare la successione dei primi di Mills, cioè la successione dei b_n che appare in (TM), dove q è il numero (soluzione minima) che si calcola con il metodo di Chris K. Caldwell e Yuanyou Cheng.
Ecco i primi sei primi di Mills:

b₁ = 2

b₂ = 11

b₃ = 1361

b₄ = 2521008887

b₅ = 16022236204009818131831320183

b₆ = 4113101149215104800030529537915953170486139623539759933135949994882770404074832568499

4 - Una ricorsione che dà soltanto uno o numeri primi

Nella NKS Summer School del 2003, venne studiata, tra le molte altre cose, questa funzione, definita ricorsivamente:

f(1) = n₁,     f(n) = f(n - 1) + MCD(n, f(n - 1))

{7, 8, 9, 10, 15, 18, 19, 20, 21, 22, 33, 36, 37, 38, 39, 40, 41, 42, 43, 44,
45, 46, 69, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87,
88, 89, 90, 91, 92, 93, 94, 141, 144, 145, 150, 153, 154, 155, 156, 157, 158,
159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173,
174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188,
189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 303,
306, 307, 308, 315, 316, 317, 318, 319, 330, 333, 334, 335, 336, 337, 338,
351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365,
366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380,
381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395,
396, 397, 398, 399, 400, 401, 402, 403, 404, 405, 406, 407, 408, 409, 410,
411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425,
426, 427, 428, 429, 430, 431, 432, 433, 434, 435, 436, 437, 438, 439, 440,
441, 442, 443, 444, 445, 446, 447, 448, 449, 450, 451, 452, 453, 454, 455,
456, 457, 458, 459, 460, 461, 462, 463, 464, 465, 466, 699, 702, 703, 704,
705, 706, 707, 708}

Funzione f

La funzione f fa salti improvvisi.

Introduciamo la funzione differenza g

g(n) = f(n) - f(n - 1) = MCD(n, f(n - 1))

{1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 101, 3,
1, 1, 7, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 233, 3, 1, 1, 1, 1, 1, 1}

Ebbene questo è stato dimostrato!

Nell'autunno 2007 Eric S. Rowland ha dimostrato che

(TR)

Se f(1) = 7, per ogni n maggiore di 1 gli unici divisori di g(n) sono 1 e g(n).

Questo è l'elenco dei primi che via via si trovano (cioè i g(n) diversi da 1):

5, 3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3, 7, 1889, 3, 3779, 3,
7559, 3, 13, 15131, 3, 53, 3, 7, 30323, 3, 60647, 3, 5, 3, 101, 3, 121403, 3, 242807, 3, 5, 3, 19, 7,
5, 3, 47, 3, 37, 5, 3, 17, 3, 199, 53, 3, 29, 3, 486041, 3, 7, 421, 23, 3, 972533, 3, 577, 7, 1945649,
3, 163, 7, 3891467, 3, 5, 3, 127, 443, 3, 31, 7783541, 3, 7, 15567089, 3, 19, 29, 3, 5323, 7, 5, 3,
31139561, 3, 41, 3, 5, 3, 62279171, 3, 7, 83, 3, 19, 29, 3, 1103, 3, 5, 3, 13, 7, 124559609, 3, 107, 3,
911, 3, 249120239, 3, 11, 3, 7, 61, 37, 179, 3, 31, 19051, 7, 3793, 23, 3, 5, 3, 6257, 3, 43, 11, 3, 13,
5, 3, 739, 37, 5, 3, 498270791, 3, 19, 11, 3, 41, 3, 5, 3, 996541661, 3, 7, 37, 5, 3, 67, 1993083437,
3, 5, 3, 83, 3, 5, 3, 73, 157, 7, 5, 3, 13, 3986167223, 3, 7, 73, 5, 3, 7, 37, 7, 11, 3, 13, 17, 3, . . .

Rowland ci lascia questa congettura:

Congettura di Rowland

Per ogni seme f(1) esiste un N tale che, per tutti gli n maggiori di N, gli unici divisori di g(n) sono 1 e g(n).

Underwood Dudley, History of a Formula for Primes, The American Mathematical Monthly, Vol. 76, No. 1. (Jan.,1969), pp. 23-28.

Underwood Dudley, Formulas for Primes, Mathematics Magazine, Vol. 56, No. 1. (Jan., 1983), pp. 17-22.

Chris K. Caldwell - Yuanyou Cheng, Determining Mills' Constant and a Note on Honaker's Problem, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.1

ERIC S. ROWLAND, A SIMPLE PRIME-GENERATING RECURRENCE, 0710.3217v2, Submitted on 17 Oct 2007, last revised 28 Jan 2008

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

[58] 14 Gennaio 2008

1 - L'illusione della linearità

Sembra che, per la maggior parte degli uomini, il ragionamento proporzionale sia del tutto spontaneo, forse necessario, e certamente il primo a essere usato.

L'esempio più citato di questo fenomeno viene dal Menone di Platone. Socrate ha disegnato un quadrato di due piedi di lato, ed è riuscito a far "ricordare" al ragazzo che lo accompagna (un giovane schiavo, privo di istruzione) il valore dell'area di questa figura, quattro piedi. Poi il dialogo prosegue così:

SOCRATE: E quanti sono, allora, due volte due piedi? Fa' il conto e dillo.
RAGAZZO: Quattro, o Socrate.
SOCRATE: E non potrebbe darsi un'altra superficie doppia di questa, ma tale da avere tutti i lati eguali come questa?
RAGAZZO: Sì.
SOCRATE: Di quanti piedi sarà dunque?
RAGAZZO: Di otto.
SOCRATE: E ora cerca di dirmi di quanto sarà ciascun lato di essa. Il lato di questa è di due piedi; e, allora, di quanto sarà quello di quella doppia?
RAGAZZO: E' chiaro, o Socrate, che sarà doppio.

In un articolo che ho letto recentemente ([ 5 ]) gli autori riportano quanto avvenuto nel corso di un esame per maestri elementari. Ecco il problema.

Susanna e Giulia corrono alla stessa velocità su una pista circolare. Susanna parte prima. Quando Susanna ha percorso 9 giri, Giulia ne ha fatti 3.
Quando Giulia è arrivata a 15 giri, quanti giri ha percorso ha percorso Susanna?

Questa equazione si basa sull'idea che il rapporto tra il numero dei giri fatti da Susanna e quello corrispondente di Giulia rimanga costante.

Risultato x = 45. Invece il risultato corretto è 21, perché è la differenza tra i numeri dei giri a rimanere costante, in quanto le ragazze corrono alla medesima velocità.

Qualche settimana fa un mio caro amico, l'avvocato Arcangelo Papi, conoscendo la mia passione, mi proponeva alcuni divertimenti matematici, tra i quali il seguente.

Il terzo problemino poneva un quesito di crescita esponenziale. Data una ameba, che posta in idonea soluzione zuccherina - riproducendosi per scissione - raddoppia ogni tre minuti, e dato che in un'ora il vaso è interamento riempito dalle amebe che si sono riprodotte, quanto tempo ci vorrebbe per riempire il recipiente allorchè le amebe iniziali fossero due invece che una soltanto? Qui la soluzione è semplice, e come dice Wertheimer, è una meravigliosa capriola quando si comunica la risposta esatta (tratto da Albert Einstein e Max Wertheimer di Peter Damerow, in L'eredità di Einstein a cura di G. Pisent e J. Renn, il Poligrafo, Padova, 1991).

Il ragionamento proporzionale è molto pericoloso nel caso della crescita esponenziale, vediamo un altro esempio.

Gli oceani sono infestati da un'alga tremenda e indistruttibile, la cui popolazione si raddoppia ogni giorno. In trenta giorni l'alga ha ricoperto un ottavo della superficie totale degli oceani. Quanto tempo ci rimane prima che ogni centimetro quadrato dei mari sia ricoperto di alghe?

Molti cosiddetti paradossi della teoria della probabilità derivano dall'abuso del pensiero lineare.

La probabilità viene percepita essenzialmente come rapporto, rapporto tra il numero dei casi favorevoli e quello dei casi possibili. Proprio questo la rende particolarmente sensibile alle errate applicazioni del pensiero proporzionale.

Anche il grande matematico Cardano (1501-1576) fu tratto in errore dalla presunta linearità. Egli sapeva che la probabilità di ottenere due 6 lanciando due dadi è 1/36. Deduceva da questo che tirando i dadi 18 volte si ottenesse il doppio 6 con probabilità 18/36 = 0,5. Questo ragionamento è evidentemente falso. Se fosse così, con 36 tiri avremmo probabilità 36/36 = 1, ovvero la certezza!

Molti testi di storia della teoria della Probabilità riportano, alle origini della concezione moderna, l'episodio del cavaliere de Méré.

Il cavaliere de Méré (1607-1684), giocatore e acuto osservatore, si accorse empiricamente che alla lunga si vince se si scommette a favore della uscita di un 6, lanciando 4 volte un dado. Ragionando proprozionalmente, de Méré dedusse che lo stesso deve accadere se, lanciando due dadi, si scommette che in 24 tiri uscirà una coppia di 6 (un dodici). Infatti 4/6 = 24/36.

In sostanza de Méré ragionava così: nel passaggio da un dado a due dadi il numero dei casi possibili diventa sei volte più grande, e quindi la probabilità si riduce a un sesto della precedente. Questa diminuzione è compensata sestuplicando il numero dei lanci.

La pratica però non coincideva con la teoria, e de Méré dovette constatare, a sue spese, che nel caso della coppia di dadi si perdeva, in media, con 24 lanci.

Assai stupito ne parlò a Pascal (1623-1662) e Fermat (1601-1665), i quali, incuriositi, iniziarono gli studi sui fondamenti della Probabilità.

Lanciando un dado la probabilità che non venga 6 è 5/6. La probabilità che il 6 non venga per k lanci è (5/6)^k.

Pertanto la probabilità che venga 6 in k lanci è p₁(k) = 1 - (5/6)^k.

Facendo i conti si vede che:

p₁(3) = 0,421... e p₁(4) = 0,517... > 0,5

Quindi effettivamente conviene scommettere che in 4 lanci uscirà un 6.

Lanciando due dadi la probabilità che non venga 12 è 35/36. La probabilità che il 12 non venga per k lanci è (35/36)^k.

Pertanto la probabilità che venga 12 in k lanci è p₂(k) = 1 - (35/66)^k.

Facendo i conti si vede che:

p₂(24) = 0,491... e p₂(25) = 0,505... > 0,5

Quindi avere un vantaggio bisogna scommettere che in 25 lanci uscirà un 12. La scommessa sui 24 lanci è perdente.

Uno dei più noti (e anche dei più applicati) è il paradosso del compleanno.

2 - Il paradosso del compleanno

Problema del compleanno

Qual è la probabilità β(k) che, prese k persone a caso, almeno due di esse siano nate nello stesso giorno?
In particolare quante devono essere affinché si possa scommettere con vantaggio su questa eventualità
(ovvero si abbia β(k) > 0,5)?

Molte persone tentano di risolvere il problema del compleanno in modo lineare, proporzionale.

Ingenuità lineare

Ci sono k compleanni disponibili, e 365 compleanni possibili. Per avere β(k) maggiore di 0,5 è chiaro che k deve essere almeno 183, più della metà dei casi possibili.

Soluzione del problema del compleanno

Denotiamo con α(k) la probabilità che, date a caso n persone, esse siano nate in giorni differenti.

Chiaramente β(k) = 1 - α(k).

Supponiamo di avere k individui e una grande sala, nella quale entrano uno alla volta. Ogni volta vogliamo valutare la probabilità che le h persone presenti siano nate in giorni differenti, cioè vogliamo calcolare α(h).

Entra il primo, e il problema non si pone neanche.
Entra il secondo. Poiché un giorno dell'anno è occupato dal primo ne rimangono 364 disponibili, e la probabilità che il secondo sia nato in un giorno differente è 364/365 = 1 - 1/365.
Pertanto α(2) = 1 - 1/365.

Entra il terzo. Poiché due giorni dell'anno sono occupati dal primo e dal secondo personaggio rimangono 363 giorni disponibili, e la probabilità che il terzo sia nato in un giorno differente dai primi due è 363/365 = 1 - 2/365.
La probabilità che i due eventi (per ipotesi indipendenti) di verifichino entrambi è il prodotto delle due probabilità, e dunque
α(3) = (1 - 1/365)(1 - 2/365).

E' evidente ora come prosegue la vicenda. Alla fine otteniamo:

a(k) = (1 - 1 365 )(1 - 2 365 ) ¼(1 - k-1 365 ) = k-1 Õ h=1  (1 - h 365 )

Ovvero:

b(k)   =  1  -   k-1 Õ h=1  (1 - h 365 )

Figura 1 - Funzione β(k)

Nella tavola sottostante si leggono nella prima riga i valori di k, per k che varia da 10 a 100 (con intervalli di 10), e nella seconda i corrispondenti valori (approssimati alla settima cifra) di β(k).

Dai calcoli si ottiene β(22) = 0.4756953... e β(23) = 0.5072972... .

Abbiamo la soluzione del problema del compleanno! Per scommetere con vantaggio che, prese k persone a caso, almeno due di esse siano nate nello stesso giorno è sufficiente che k sia almeno 23. Non è sorprendente? Ma forse non lo è di meno pensare che oltre le 50 si ha praticamente la certezza, e con 35 siamo sopra l'80%.

Coloro che sono interessati a trovare conferma della teoria presentata possono fare ricerche personali in ambienti affollati, come discoteche e mezzi di trasporto, oppure, senza faticare ma affidandosi alla serietà della giovane professoressa Susan Holmes, della Stanford University, possono ricorrere ad una simulazione in rete. L'applet della Holmes genera k date casuali e segnala le coincidenze. L'applet è inizializzata con k = 50. Con questo valore si trovano assai spesso tre o più coincidenze. Ovviamente, se pure di rado (in media), possono non essercene. E' interessante variare il valore di k, e verificare sperimentalmente le formule teoriche.

3 - Come è piccolo il mondo!

Sovente non sarebbe il caso di stupirsi tanto, siamo soltanto di fronte al manifestarsi del paradosso del compleanno, nella sua formulazione più generale, che ora vediamo.

Formulazione generale del problema del compleanno

E' dato un insieme X di oggetti, classificabili in n classi equidistribuite in X. (Per esempio X è l'insieme degli abitanti di Roma, e le classi corrispondono ai 365 giorni dell'anno. Gli abitanti sono classificati a seconda del giorno di nascita.)

Qual è la probabilità β(k, n) che, scelti a caso k elementi in X, almeno due di essi appartengano alla stessa classe?

In particolare quanto deve essere grande k affinché β(k, n) > 0,5?

Possiamo scrivere β(k, n) semplicemente sostituendo n a 365.

Questa bella formula risponde in modo completo alla prima domanda del problema generale del compleanno.

Qualsiasi sia n le curve β(k, n), dove la variabile è k, hanno tutte la stessa forma e tendono a 1 al crescere di k, come in Figura 1.

Diciamo η(n) il minimo intero positivo k tale che β(k, n) > 1/2.

Per ogni n che ci venga assegnato possiamo, facendo i conti, trovare quanto vale η(n).

Questo metodo presenta però due grossi svantaggi.

1. Se n è molto grande il calcolo del prodotto diventa impraticabile.
2. Non viene evidenziata nessuna relazione tra n e η(n).

Vediamo, con un poco di analisi, come superare questi ostacoli.

Dalla (1) segue che β(k, n) > 1/2 se e solo se

Applichiamo la funzione log a entrambi i lati della (2) (con log(x) denotiamo il logaritmo naturale di x, in base e)

Nella (3) abbiamo usato la ben nota proprietà del logaritmo log(xy) = log(x) + log(y).

Poiché h < k ≤ n si ha h/n < 1, e possiamo utilizzare lo sviluppo di Taylor di log(1 - x) (4), valido quando |x| < 1

A partire dalla (5) si può proseguire in vari modi ([ 4 ]). Seguiamo la strada più semplice, che, in questo caso, dà ottimi risultati.

Se h/n è piccolo possiamo trascurare, nella serie che esprime log(1 - h/n), le potenze di h/n con esponente m > 1.

Ovvero utilizziamo l'approssimazione lineare (ecco che il pensiero lineare si prende la sua rivincita!) di log(1 - x)

Mediante l'approssimazione data dalla (6) la (5) diventa

Ricordando la ben nota identità

e il fatto che

la (7) diventa

Infine, risovendo la (10) otteniamo

Abbiamo dunque trovato una approssimazione di η(n), che chiamiamo ν(n)

La funzione ν(n) è una approssimazione molto buona di η(n). Per esempio

• ν(365) = 22,98 e η(365) = 23
• ν(3000) = 64,96 e η(3000) = 65
• ν(10000) = 118,2 e η(10000) = 119
• ν(50000) = 832,76 e η(50000) = 833
• ν(100000) = 1177,5 e η(100000) = 1178

La (12) ci assicura che l'ordine di grandezza di η(n); è la radice quadrata di n.

Questa constatazione non è banale e spiega molte cose ([ 2 ]).

Quando esclamiamo "Ma sono uguali! Come è possibile, ce ne sono di diecimila forme diverse!" dobbiamo riflettere. Se abbiamo davanti più di 119 oggetti la probabilità che due di essi abbiano la stessa forma (su 10000 possibili forme) è già maggiore di 1/2. Se ne esaminiamo 200 la probabilità di una coincidenza supera l'86%!

4 - Una applicazione al metodo di fattorizzazione di Pollard

J. M. Pollard nel 1975 pubblicò un aricolo ([ 3 ]), dal titolo "A Monte Carlo method for factorization", che ebbe un impatto straordinario.

L'idea è geniale. Sia N l'intero che vogliamo fattorizzare e sia p un fattore primo di N. Ci sono p classi di resto modulo p, determinate dai possibili resti della divisione per p: 0, 1, ... , p-1. Se mettiamo insieme, in modo casuale, k numeri interi, per il paradosso del compleanno la probabilità che due di essi appartengano alla stessa classe di resto modulo p sarà circa 1/2 se k è dell'ordine della radice quadrata di p.

Se gli interi a, b stanno nella stessa classe di resto modulo p, ovvero se a ≡ b (mod p), allora p divide c = a - b.

Poiché p divide sia c che N, p divide il massimo comun divisore d = MCD(c, N). Pertanto, se non siamo nel caso sfortunato e improbabile che lo stesso N divida c, d è un fattore proprio di N.

Un grande successo del metodo di Pollard (con un miglioramento dovuto a Brent) fu la fattorizzazione del'ottavo numero di Fermat

Questo numero è particolarmente difficile da fattorizzare, perché, come si è scoperto dopo averlo fattorizzato, è il prodotto di due primi grandi (il più piccolo ha 16 cifre).

Pollard e Brent ([ 1 ]) scoprirono che:

Si trattò di un risultato straordinario e il calcolo richiese appena due ore su una macchina UNIVAC 1100/42.

[ 1 ] Richard P. Brent; John M. Pollard - Factorization of the Eighth Fermat Number - Mathematics of Computation, Vol. 36,
       No. 154. (Apr., 1981), pp. 627-630.

[ 2 ] Robert Matthews - The Law of Credulity - The Mathematical Gazette, Vol. 77, No. 480. (Nov., 1993), pp. 327-328.

[ 3 ]J. M. Pollard; - A Monte Carlo method for factorization - BIT, v. 15, 1975, pp. 331-334.

[ 4 ]Boaz Tsaban - Bernoulli numbers and the probability of a birthday surprise - arXiv:math.NA/0304028 v3 9 Nov 2004

[ 5 ]Wim Van Dooren; Dirk De Bock; Fien Depaepe; Dirk Janssens; Lieven Verschaffel - The Illusion of Linearity: Expanding the
       Evidence towards Probabilistic Reasoning - Educational Studies in Mathematics, Vol. 53, No. 2. (2003), pp. 113-138.

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

[57] 27 Ottobre 2007

Introduzione

Ricordiamo dal Blog Numeri complessi e terne pitagoriche che l'acronimo CPP sta per "Coppia Pitagorica Primitiva". Una CPP è una coppia di interi coprimi (a, b) tali che a² + b² è un quadrato. Ovvero:

Per fissare la notazione supporremo sempre nel seguito che a sia dispari e b sia pari.

Alla CPP (a, b) corrisponde la TPP (Terna Pitagorica Primitiva) (a, b, c).

Non mi risulta che sia largamente noto che l'insieme delle CPP (equivalentemente delle TPP) forma un albero ternario. In effetti si tratta di una struttura mirabile, che cercheremo di vedere insieme.

La radice dell'albero (piano 0) è la CPP primigenia (3, 4) (cui corrisponde la famosa TPP (3, 4, 5)).

Nascono da essa tre arboscelli (piano 1) : (15, 8), (21, 20) e (5, 12). Ognuno di essi si triforca, e così via all'infinito: è appunto quello che in termini matematici si dice un albero ternario.

Al piano n-esimo di questo albero-palazzo stanno 3ⁿ CPP. Ogni CPP si trova in un piano, e sta dunque ad una certa altezza n.

Come calcolare l'altezza di una terna pitagorica primitiva?
Per esempio quanto è alta la terna (4579622019, 19016013580, 19559696069)?
Nel contesto equivalente che abbiamo scelto per risparmiare spazio, quello delle coppie, a quale piano risiede la CPP
X = (4579622019, 19016013580)?

Partendo dalla radice (3, 4) si può raggiungere ogni CPP (x, y) , sull'albero, seguendo un unico percorso che chiamiamo
indirizzo di (x, y).

Sopra ogni CPP, sull'albero ternario, ci sono tre strade (che conducono ad altrettante CPP): sinistra, centro e destra. Le etichettiamo rispettivamente con s, c, d. Pertanto l'indirizzo di una CPP qualsiasi è una stringa finita di s, c, d. Per esempio "scscdd" è un indirizzo. Chi abita lì?

Risponderemo nel seguito a queste domande.

Ma ci sono anche domande cui non sappiamo rispondere (io almeno non conosco la risposta).

Nel precedente Blog abbiamo visto che è definito in modo naturale un prodotto di CPP (o di TPP).

Problemi:

Dati gli indirizzi di A = (x, y) e B = (u, v), si può determinare a priori l'indirizzo del prodotto A x B?

Più modestamente:

Se A sta al piano m, e B sta al piano n, a quale piano sta il prodotto A x B?

Le tre vie

Definiamo tre funzioni sull'insieme delle CPP, di nome sinistra, centro e destra.

Denotiamo con rad[n] la radice quadrata del numero n.

Per ogni CPP (a, b) definiamo

sin(a, b) = {2rad[a² + b²] - a + 2b, 2rad[a² + b²] - 2a + b}

cen(a, b) = {2rad[a² + b²] + a + 2b, 2rad[a² + b²] + 2a + b}

des(a, b) = {2rad[a² + b²] + a - 2b, 2rad[a² + b²] + 2a - b}

1 - Esempio

sin(33, 56) = (209, 120)
cen(33, 56) = (275, 252)
des(33, 56) = (51,140)

sin(a, b), cen(a, b), des(a, b), sono veramente delle CPP?

Se calcoliamo i valori delle tre funzioni in corrispondenza di CPP scelte a caso, troviamo sempre CPP. Sebbene questa procedura sia molto convincente, tuttavia non è una dimostrazione. Vediamo dunque perché questo accade.

2 - Proposizione

Se (a, b) è una CPP anche sin(a, b), cen(a, b), des(a, b) sono CPP.

Dimostrazione.

Tanto per rimanere neutrali dimostriamolo per la funzione centrale (le altre prove sono identiche, mutatis mutandis).

Supponiamo dunque a² + b² = c² e poniamo (x, y) = cen(a, b).
Per definizione si ha:

x = 2rad[a² + b²] + a + 2b
y = 2rad[a² + b²] + 2a + b

Calcoliamo x² + y², per vedere se viene davvero un quadrato.
Ricordiamo che (u + v + z)² = (u² + v² + z² + 2uv + 2uz + 2vz), e che, per ipotesi, si ha rad[a² + b²] = c.

x² + y² = (2rad[a² + b²] + a + 2b)² + (2rad[a² + b²] + 2a + b)² = (2c + a + 2b)² + (2c + 2a +b)² =
(4c² + a² + 4b² + 4ac + 8bc + 4ab) + (4c² + 4a² + b² + 8ac + 4bc + 4ab) =
8c² + 5a² + 5b² + 12ac + 12bc + 8ab

Se ora ricordiamo che c² = a² + b², e sostituiamo nell'ultima espressione, otteniamo:

x² + y² = 9c² + 4a² + 4b² + 12ac + 12bc + 8ab = (3c + 2a + 2b)²

Se poniamo (x, y) = sin(a, b), si ha x² + y² = (3c - 2a + 2b)²
Se poniamo (x, y) = cen(a, b), si ha x² + y² = (3c + 2a + 2b)²
Se poniamo (x, y) = des(a, b), si ha x² + y² = (3c + 2a - 2b)²

3 - Proposizione

Se si parte dalla CPP (3, 4) e si applicano successivamente in tutti i modi le funzioni sin, cen e des si trovano tutte le CPP.

Figura 1 - L'Albero di Pitagora

Indirizzi, percorsi periodici e ricorrenze lineari

Tra il piano 0 (piano terra) e il piano 3 si trovano ad ogni piano, rispettivamente 1, 3, 9 e 27 CPP:

Piano 0

(3, 4)

Piano 1

(15, 8), (21, 20), (5, 12)

Piano 2

(35, 12), (65, 72), (33, 56), (77, 36), (119, 120), (39, 80), (45, 28), (55, 48), (7, 24)

Piano 3

(63, 16), (133, 156), (85, 132), (273, 136), (403, 396), (115, 252), (209, 120), (275, 252), (51, 140), (165, 52), (319, 360), (175, 288), (459, 220), (697, 696), (217, 456), (299, 180), (377, 336), (57, 176), (117,44), (207, 224), (95, 168), (187, 84), (297, 304), (105, 208), (91, 60), (105, 88), (9, 40)

Diciamo questa stringa indirizzo di (a, b). Per esempio se calcoliamo sin(cen(sin(3,4))) otteniamo (273, 136). Diciamo allora che "scs" è l'indirizzo di (273, 136).
Nella Figura 1 alle lettere s, c, d corrispondono, rispettivamente, le azioni di procedere verso il nodo rosso, verde, blu. Per esempio se partiamo dalla radice (3, 4) e seguiamo il percorso blu, blu, rosso arriviamo in (91, 60) che ha pertanto "dds" come indirizzo.

Ci siamo chiesti all'inizio chi abiti in "scscdd": si tratta della CPP des(des(cen(sin(cen(sin(3, 4)))))) = (2919, 9440).

Supponiamo di seguire un percorso periodico, che si ripete sempre. Per esempio il "cammino dell'ubriaco":

C'è una qualche regolarità nelle CPP che si susseguono? Partiamo da C₀ = (3, 4).
Dalla Figura vediamo che la prima CPP che si trova, dopo "sd" è C₁ = (33, 56) = des(sin(3, 4)).
Si noti che si va prima a sinistra e poi a destra, quindi si applica prima la funzione sin e poi la funzione des: al cammino "sd" corrisponde la funzione des(sin( )).
Si trova poi all'indirizzo "sdsd" C₂ = (451, 780) = des(sin(des(sin(3, 4)))) = des(sin(33, 56))
E seguitando a sbandare si trova la sequenza di CPP:
(6273, 10864), (87363, 151316), (1216801, 2107560), (16947843, 29354524), (236052993, 408855776), (3287794051, 5694626340), (45793063713, 79315912984), (637815097923, 1104728155436), ...

Se diciamo C_n la n-esima CPP incontrata, si verifica che, per ogni n maggiore di 2:

In altri termini, la successione dei C_n è una successione ricorrente lineare di polinomio caratteristico

Per esempio C₇ = 15C₆ - 15C₅ + C₄, cioè:

E, in effetti, è immediato constatare che:

Questo fatto è sorprendente, ma non misterioso. Infatti deriva dal seguente noto Teorema:

4 - Teorema

Data una matrice quadrata M di dimensione d, e dato un vettore iniziale V₀ di lunghezza d, la successione

V_n = MⁿV₀    n = 0, 1, 2, 3, ...

e una successione ricorrente lineare di grado d che ha come polinomio caratteristico quello di M.

5 - Esempio

Sia M la matrice di Fibonacci

0 1

1 1

M ha polinomio caratteristico: x² - x - 1

Applicando più volte M ad un vettore iniziale V₀ si trova una sequenza di vettori V_n tale che, per ogni n maggiore di 1 si ha:

V_n = V_n-1 + V_n-2

Per esempio se V₀ = (2, 1), applicando M a V₀ si ha:

MV₀ = V₁ = (1, 3)

e proseguendo si ottiene:

(3, 4), (4, 7), (7, 11), (11, 18), (18, 29), (29, 47), (47, 76), (76, 123), (123, 199)...

(Si trova parecchio materiale sulle successioni lineari ricorrenti in questi due Blog:

La Sezione Aurea e i Numeri di Fibonacci

Quadrati Triangolari e Ricorrenze )

In realtà se passiamo dalle Coppie Pitagoriche Primitive alle Terne Pitagoriche Primitive (TPP) le funzioni sin, cen e des si linearizzano.

Utilizzando ancora il metodo delle matrici si trova che i quattro percorsi "cscscscscscscs...", "scscscscscscsc...", "cdcdcdcdcdcdcd...", "dcdcdcdcdcdcdc..." hanno tutti lo stesso polinomio caratteristico:

Procedere sempre verso sinistra "ssssssssss..." o verso destra "dddddddddd..." dà lo stesso polinomio:

Ovviamente questo è il polinomio caratteristico sia di M_sin che di M_des. Invece il polinomio caratteristico di M_cen è

Questo polinomio determina la ricorrenza delle CPP (o TPP) che si ottengono seguendo sempre la via verde.

4 - Le altezze

Ogni CPP X ha una altezza alt(X) che è il il numero del piano su cui si trova nell'albero, ovvero la lunghezza del percorso che ci porta dalla radice a X.

Per esempio, se X = (4579622019, 19016013580), poiché il percorso che congiunge (3, 4) a X è "scdssccddssscccddd", che ha lunghezza 18, abbiamo: alt(X) = 18.

Vogliamo ora osservare che la funzione altezza ha un comportamento apparentemente imprevedibile rispetto al prodotto di CPP introdotto nel Blog precedente.

Per comodità del lettore riportiamo qui sotto la definizione del prodotto (che è quella di due numeri complessi):

A rigore il nostro albero di Pitagora non è chiuso rispetto al prodotto, per esempio (3, 4) x (119, 120) = (-123, 836), mentre sull'albero tutte le coppie sono positive. Pensiamo allora di estendere il nostro ambiente, allargando il giardino, e consideriamo quattro alberi:

1. Albero 1 = il nostro
2. Albero 2 così definito, (a, -b) sta in Albero 2 se e solo se (a, b) sta in Albero 1
3. Albero 3 così definito, (-a, -b) sta in Albero 3 se e solo se (a, b) sta in Albero 1
4. Albero 4 così definito, (-a, b) sta in Albero 4 se e solo se (a, b) sta in Albero 1

Si noti che (3, 4) ha altezza 0 e indirizzo vuoto "", (119 120) ha altezza 2 e indirizzo "cc", mentre il loro prodotto ha altezza 7 e indirizzo "sdddddd".

Consideriamo la successione P(3, 4) delle potenze di (3, 4), P(3, 4) = {(3, 4), (3, 4)² = (-7, 24), (3, 4)³ = (-117,44), ...}.

Ecco i primi 12 elementi di P(3, 4):

(3, 4), (-7, 24), (-117, 44), (-527, -336), (-237, -3116),
(11753, -10296), (76443, 16124), (164833, 354144), (-922077, 1721764),
(-9653287, 1476984), (-34867797, -34182196), (32125393, -242017776)

Per esempio

Se applichiamo la funzione alt alla sequenza P(3, 4) otteniamo la successione delle altezze delle potenze di (3, 4).
Qui sotto ci sono le prime 100 altezze:

0, 2, 3, 4, 13, 9, 8, 12, 38, 17, 14, 39, 23, 17, 26, 35, 64, 28, 38, 30, 42,
166, 48, 52, 50, 39, 85, 36, 52, 116, 177, 80, 169, 83, 93, 153, 224, 98, 87,
67, 101, 126, 81, 104, 100, 74, 142, 109, 173, 151, 129, 129, 88, 108, 294,
168, 203, 143, 121, 219, 229, 207, 118, 111, 208, 335, 225, 525, 1441, 473,
267, 156, 156, 155, 146, 184, 303, 211, 215, 294, 289, 915, 1350, 400, 181,
155, 289, 437, 1378, 780, 434, 239, 287, 619, 334, 192, 336, 432, 318, 224

Nella figura seguente vediamo il grafo delle altezze:

Figura 2 - Le prime 100 altezze delle potenze di (3,4)

Colpiscono subito tre potenze,corrispondenti agli esponenti 69, 83 e 89, di altezze, rispettivamente, 1441, 1350, 1378.
Colpiscono anche perché appaiono come picchi: prima e dopo ci sono altezze molto inferiori.

Abbiamo:

alt(P₆₈(3, 4)) = 525,   alt(P₆₉(3, 4)) = 1441,   alt(P₇₀(3, 4)) = 473.

alt(P₈₂(3, 4)) = 915,   alt(P₈₃(3, 4)) = 1350,   alt(P₈₄(3, 4)) = 400.

alt(P₈₈(3, 4)) = 437,   alt(P₈₉(3, 4)) = 1378,   alt(P₉₀(3, 4)) = 780.

Data la CPP (a, b) definiamo spettro(a, b) la terna (S, C, D), dove S è il numero dei passi s che appaiono nell'indirizzo di (a, b), C è il numero dei passi c che appaiono nell'indirizzo di (a, b) e D è il numero dei passi d che appaiono nell'indirizzo di (a, b).

Per esempio
spettro(P₁₈(3, 4)) = spettro((3, 4)¹⁸) = spettro(-2114245277767, -3175197967656) = (12, 5, 11),
perché l'indirizzo di P₁₈(3, 4) è "sssscddcsssdcddddddcsscdsssd".

In corrispondenza dei tre picchi trovati, gli spettri sono:

Notiamo un fortissimo sbilanciamento verso la destra. Per P₆₉(3, 4) i passi verso destra superano il 93,6%!

Se calcoliamo le altezze fino a P₂₀₀(3, 4) troviamo il seguente grafico:

Figura 3 - Le prime 200 altezze delle potenze di (3,4)

0, 2, 3, 4, 13, 9, 8, 12, 38, 17, 14, 39, 23, 17, 26, 35, 64, 28, 38, 30, 42,
166, 48, 52, 50, 39, 85, 36, 52, 116, 177, 80, 169, 83, 93, 153, 224, 98, 87,
67, 101, 126, 81, 104, 100, 74, 142, 109, 173, 151, 129, 129, 88, 108, 294,
168, 203, 143, 121, 219, 229, 207, 118, 111, 208, 335, 225, 525, 1441, 473,
267, 156, 156, 155, 146, 184, 303, 211, 215, 294, 289, 915, 1350, 400, 181,
155, 289, 437, 1378, 780, 434, 239, 287, 619, 334, 192, 336, 432, 318, 224,
274, 558, 668, 253, 245, 232, 324, 546, 356, 284, 338, 245, 237, 283, 202,
280, 274, 372, 396, 257, 442, 267, 451, 567, 422, 418, 378, 345, 569, 844,
393, 280, 575, 925, 493, 592, 1922, 7466, 1744, 1003, 556, 526, 493, 518,
305, 336, 632, 1530, 6315, 1487, 668, 666, 598, 1461, 562, 465, 433, 665,
1987, 1469, 4492, 1768, 3612, 1027, 525, 494, 481, 538, 475, 498, 556, 820,
2121, 786, 398, 522, 528, 840, 483, 515, 606, 1365, 2307, 953, 967, 1327,
1107, 688, 487, 425, 701, 1471, 5609, 25953, 5600, 1456, 706, 552, 1089, 2269

Si constata che alt(P₁₉₄(3, 4)) = 25953.

Lo spettro di P₁₉₄(3, 4) è (25795, 46, 112). Questa volta i passi a sinistra sono più del 99%.

Sembra quasi che le potenze per salire più in alto debbano essere estremiste!

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

[56] 30 Giugno 2007

1 - I numeri complessi

Ai nostri giorni regna l' horror vacui. Riempire tutto, colmare ogni buco: questa è la regola. I lettori meno giovani ricorderanno i primi gloriosi anni della televisione. Quanta nostalgia di quelle pause immense, gratuitamente e pacificamente occupate da pecorelle, prati (in bianco e nero, il verde lo mettevamo noi), campanili e chiese...

Oggi la pubblicità invade ogni più riposto angolo, vorrebbe esaurire per intero lo spazio dei nostri desideri. Personalmente non sento la necessità di avere ogni istante di vita pieno di qualcosa. Qualcosa che non c'è veramente, che è pura costruzione, bisogno fittizio. Qualcosa che porta soltanto alla riproduzione parossistica del nulla.

Insomma, siamo pieni di cose, ma manca l'essenziale. La Matematica ci insegna ad agire al contrario: procuriamoci l'essenziale e tutto il resto verrà da solo, come sovrabbondante regalo!

Consideriamo l'insieme dei numeri reali R. In R si avverte subito la mancanza di numeri che pur dovrebbero esserci, da qualche parte ...

Per esempio l'equazione x³ = 1, ha una soluzione reale, ma intuitivamente dovrebbe averne tre. Del resto il polinomio x³ - 1 si fattorizza in modo ovvio come (x - 1)(x² + x + 1) e x² + x + 1 non ha zeri reali. Cerchiamo il caso più semplice. Dove sono gli zeri di x² + 1?

Manca la radice quadrata di -1. Aggiungiamola, la chiamiamo i. Pertanto si ha, per definizione stessa, i² = -1.

Abbiamo un nuovo ambiente algebrico che denotiamo con R(i). Gli elementi di R(i) vengono chiamati numeri complessi, e sono della forma z = a + bi, dove a e b sono numeri reali, detti rispettivamente la parte reale e la parte immaginaria di z.

Le operazioni di somma e prodotto sono indotte semplicemente dalle analoghe operazioni di R, e dalla definizione di i.

Dati z = a + bi e w = c + di si ha:

z + w = (a + bi) + (c + di) = (a + c) + (b + d)i

zw = (a + bi)(c + di) = ac + adi + bci + bdi² =
ac + adi + bci - bd = (ac - bd) + (ad + bc)i

Si ha

zconj(z) = (a + bi)(a - bi) = a² + b².

Si verifica anche subito che conj(zw) = conj(z)conj(w).

Diciamo norma di z il numero N(z) = zconj(z) = a² + b².

La norma è moltiplicativa, infatti:

N(zw) = zwconj(zw) = zwconj(z)conj(w) = (zconj(z))(wconj(w)) = N(z)N(w)

[1]     (ac - bd)² + (ad + bc)² = (a² + b²)(c² + d²)

In R(i) ogni elemento diverso da 0 ha un inverso, infatti, se la norma di z non è nulla si ha

z(conj(z)/N(z)) = (zconj(z))/N(z) = N(z)/N(z) = 1

e pertanto

z^-1 = conj(z)/N(z)

Il Teorema Fondamentale dell'Algebra (TEOFAL) asserisce che:

C è algebricamente chiuso: un polinomio qualsiasi di grado n con i coefficienti in C, ha n zeri in C, contati con la loro molteplicità (in altri termini: tutti gli zeri del polinomio si trovano in C).

Abbiamo aggiunto a R l'essenziale, uno zero di x² + 1, e abbiamo ottenuto tutto: gli zeri di tutti i polinomi!

Il campo C, oltre a essere algebricamente chiuso, possiede una utilissima rappresentazione grafica, infatti il numero complesso a + bi si rappresenta in modo naturale nel piano cartesiano come punto P di coordinate (a, b). Facciamo un esempio.

In C ci sono le radici n-esime dell'unità per ogni n. Esse sono rappresentate nel piano dai punti di coordinate

Nella figura sottostante si vede il poligono regolare con 17 lati, i cui vertici sono gli zeri di x¹⁷ - 1.

Figura 1

Questo poligono, come dimostrò Gauss, è costruibile con riga e compasso, perché il suo numero di lati è un primo di Fermat. Gauss provò questo risultato nel 1797 (aveva 19 anni), e fornì anche una costruzione esplicita. Il giovane Gauss era (giustamente) molto orgoglioso di questo risultato, tanto che il poligono con 17 lati, in forma stellata, è scolpito sul basamento del monumento dedicato a Gauss, in Braunschweig, sua città natale (vedi sotto).

Versione stellata del poligono regolare di 17 lati.

2 - Il gruppo del cerchio e le terne pitagoriche

Diciamo terna pitagorica (TP) una terna di numeri interi (a, b, c) tali che a² + b² = c². Credo che tutti, dalle scuole elementari, ricordiamo la famosa terna (3, 4, 5). Ovviamente ogni multiplo intero (ka, kb, kc) di una TP è ancora una TP. Se a, b, c non hanno fattori propri in comune diciamo che la terna pitagorica è primitiva (TPP). Ammettiamo anche lo 0, e diciamo singolari le TP nelle quali appare uno 0. Diciamo coppia pitagorica (CP) una coppia di interi (a, b) che faccia parte di una TP (a, b, c). Se a e b sono coprimi, la coppia si dice primitiva (CPP). Consideriamo primitive anche le coppie singolari (1, 0), (-1, 0), (0, 1), (0, -1)

La formula [1] ci dice che le CP si possono moltiplicare, proprio come i numeri complessi!

Associamo alle CP (a, b) e (d, e), facenti parte rispettivamente delle TP (a, b, c) e (d, e, f), i numeri complessi α = a + bi e β = d + ei.
Per ipotesi abbiamo N(α) = c² e N(β) = f². Pertanto N(αβ) = (cf)².

Poiché αβ = (a + bi)(d + ei) = (ad - be) + (ae + bd)i, abbiamo ottenuto una nuova CP, "prodotto" delle due assegnate:

Per esempio (3, 4) x (8, 15) = (-36, 77), e 36² + 77² = 85². L'operazione tra CP copia il prodotto di numeri complessi, quindi è commutativa e associativa. La coppia singolare (1, 0) funge da elemento neutro: abbiamo quindi un semigruppo. Per avere un gruppo ci mancano gli inversi. A questo punto entra in scena il gruppo del cerchio.

L'insieme U dei numeri complessi di norma 1 è chiuso rispetto al prodotto (perché la norma è moltiplicativa). Inoltre se α ha norma 1 anche il suo inverso ha norma 1. Si noti che in questo caso l'inverso è semplicemente il coniugato conj(α). Dunque U è un gruppo, detto gruppo del cerchio perché la sua rappresentazione nel piano complesso è la circonferenza di raggio 1 con centro nella origine (è precisamente quella circoscritta al poligono di Figura 1).

E' noto che i punti del cerchio untario si parametrizzano con le coppie (cos(t), sin(t)). Come insieme di numeri complessi si ha:

Il parametro t (che è un angolo) si dice argomento di α = cos(t) + sin(t)i. Consideriamo un altro elemento di U, β = cos(u) + sin(u)i. Moltiplicando si ottiene αβ = (cos(t)cos(u) - sin(t)sin(u)) + (cos(t)sin(u) + sin(t)cos(u))i.

Ricordando un poco di trigonometria otteniamo αβ = cos(t+u) + sin(t+u)i. Moltiplicare in U significa sommare gli argomenti.

L'inverso di α avrà dunque argomento opposto, sarà cos(-t) + sin(-t)i = cos(t) - sin(t)i (il coniugato, come già osservato).

Il gruppo del cerchio è dunque una copia del (è isomorfo al) gruppo additivo dei numeri reali compresi tra 0 e 2π (2π escluso), dove la somma avviene modulo 2π, ovvero a meno di multipli di 2π.

U possiede un sottogruppo molto interessante, formato dai numeri complessi di norma 1 con componenti razionali. Chiamiamo UR questo sottogruppo. Pertanto un numero complesso α appartiene a UR se e solo se:

• N(α) = 1
• La parte reale e la parte immaginaria di α sono numeri razionali

Possiamo determinare questi punti razionali ricorrendo ancora alla trigonometria.
Le funzioni cos(x) e sin(x) hanno espressioni razionali in funzione di t = tan(x/2).

Precisamente:

• cos(x) = (1 - t²)/(1 + t²)
• sin(x) = 2t/(1 + t²)

Otteniamo quindi i punti razionali sul cerchio unitario considerando i valori razionali di t, ovvero ponendo t = m/n. Si trova con semplice calcolo che:

E' ben noto che le TPP (a, b, c), con c maggiore di 0, si trovano tutte così (a parte l'ordine di a e b):

dove m, n sono interi coprimi di diversa parità.

Questo evidenzia una precisa corrispondenza tra le TPP (o le CPP) e i punti razionali sul cerchio unitario!

La corrispondenza (vista in modo più naturale) g tra l'insieme delle CP, diverse da (0, 0), e l'insieme UR dei punti razionali sul cerchio unitario, manda (a, b) in g(a, b) = (a/c) + (b/c)i, dove c è il terzo elemento della TP relativa a (a, b), ovvero a² + b² = c².
Infatti N( (a/c) + (b/c)i) = (a/c)² + (b/c)² = 1. Nel seguito supporremo sempre c positivo.

La funzione g è suriettiva. Dato infatti un qualsiasi numero complesso α = (a/c) + (b/c)i in UR si ha α = g(a, b), dove (a, b) è una CP, parte della TP (a, b, c).

Se mettiamo insieme le CP che hanno la medesima immagine mediante g otteniamo delle classi di equivalenza,
che denotiamo con [a, b]. Ovvero, fissata la CP (a, b) si ha per definizione:

Ogni classe è rappresentata da un'unica CPP.

Riassumiamo:

Data la CP (a, b), se a e b sono entrambi non nulli [a, b] = { (ka, kb): k è un intero positivo }. Inoltre [a, b] = [a/d, b/d] dove d = MCD(a, b) e (a/d, b/d) è una CPP.

Se b = 0 e a è positivo [a, 0] = { (ka, 0): k è un intero positivo } = [1, 0].

Se b = 0 e a è negativo [a, 0] = { (ka, 0): k è un intero positivo } = [-1, 0].

Se a = 0 e b è positivo [0, b] = { (0, kb): k è un intero positivo } = [0, 1].

Se a = 0 e b è negativo [0, b] = { (0,kb): k è un intero positivo } = [0, -1].

[a, b] x [d, e] = [(a, b) x (d, e)].

La corrispondenza g agisce in maniera ovvia sulle classi:

g[a, b] = g(a, b)

e inoltre conserva il prodotto:

dove il prodotto a destra è quello ordinario tra numeri complessi.

Per esempio g([3, 4] x [8, 15]) = g[-36, 77] = (-36/85) + (77/85)i = (3/5 + 4/5i)(8/17 + 15/17i) = g[3, 4]g[8, 15].

E' chiaro ora che l'insieme delle classi [a, b], con il prodotto che abbiamo definito, è un gruppo isomorfo a UR. Ogni classe è rappresentata da un'unica CPP. Quindi si ha il seguente bellissimo teorema:

L'insieme delle coppie pitagoriche primitive forma un gruppo isomorfo al gruppo dei punti razionali sul cerchio unitario.

Chiamiamo questo gruppo Gruppo Pitagorico e lo denotiamo con GP.

Si noti che l'inverso di [a, b] in GP è [a, -b]. Infatti [a, b] x [a, -b] = [c, 0] = [1, 0].

Osserviamo anche che l'insieme delle quattro classi singolari { [1, 0], [0, 1], [-1, 0], [0, -1] } è un sottogruppo di GP. E' un sottogruppo ciclico di ordine 4, generato da [0, 1], isomorfo al sottogruppo generato da i in UR che è costituito dalle 4 radici quarte di 1.

Per scoprire la mirabile struttura del Gruppo Pitagorico dobbiamo studiare un poco gli interi di Gauss.

3 - Gli interi di Gauss

Diciamo IG l'insieme formato da tutti i numeri complessi con parti reale e immaginaria intere:

IG è un anello, proprio come l'anello Z dei numeri interi. In Z gli unici elementi invertibili sono 1 e -1. In IG ci sono 4 invertibili, che sono esattamente la intersezione di IG con UR, ovvero le quattro radici quarte di 1 di cui si è parlato sopra.

Due interi di Gauss α e β si dicono associati se uno si ottiene dall'altro moltiplicandolo per un invertibile (in Z sono associati n e -n).

Dato α = a + bi in IG, gli associati di α sono:

β = 1α = a + bi

β = -1α = -a - bi

β = iα = -b + ai

β = -iα = b - ai

Diciamo che α divide β se esiste un γ, sempre in IG, tale che β = αγ. Se α divide β scriviamo

Per esempio, sappiamo che 3 + 4i|-36 + 77i perché -36 + 77i = (3 + 4i)(8 + 15i).

Si noti bene la differenza tra i simboli | e /. L'espressione 3 + 4i|-36 + 77i è una affermazione, equivale a dire "3 + 4i è un divisore di
-36 + 77i", mentre -36 + 77i/3 + 4i è il risultato di una operazione, del dividere -36 + 77i per 3 + 4i,  -36 + 77i/3 + 4i = 8 + 15i.

Nell'anello Z, anche se m non divide n è possibile dividere n per m, con un certo resto. Tutti sappiamo dividere due interi e conosciamo l'algoritmo di divisione in Z (anche se magari abbiamo qualche difficoltà con gli interi negativi ...). Diamo qui sotto un algoritmo diverso da quello che usiamo sempre, ma più facimente generalizzabile a casi in cui non c'è un ordinamento naturale nell'anello.

Con |x| denotiamo ovviamente il valore assoluto di x.
Se x è un numero reale denotiamo con round(x) l'intero più vicino a x; in caso di equidistanza da due interi scegliamo l'intero con valore assoluto minore. Per esempio round(-3/2) = -1, round(1/2) = 0. Si ha sempre |x - round(x)| ≤ 1/2.

Algoritmo generalizzabile di divisione in Z.

Dati n ed m in Z non nulli, esistono q ed r interi tali che:

n = mq + r

dove r = 0 oppure r è un intero tale che |r| < |m|.

Dimostrazione costruttiva:

Poniamo q = round(n/m), e poniamo r = n - mq.
Allora |r| = |n - mq| = |m||n/m -q| = |m||n/m - round(n/m)| ≤ (1/2)|m| < |m|. Esempi

n = 8, m = 5
q = round(8/5) = 2, r = -2

n = 8, m = -5
q = round(-8/5) = -2, r = -2

n = -8, m = 5
q = round(-8/5) = -2, r = 2

n = -8, m = -5
q = round(8/5) = 2, r = 2

In IG l'algoritmo generalizzabile ci dà direttamente un valido algoritmo di divisione tra interi di Gauss, semplicemente sostituendo la norma N(x) al valore assoluto |x|.

Algoritmo di divisione in IG

Dati due interi di Gauss non nulli α e β esistono interi di Gauss μ e ρ tali che:

α = βμ + ρ

dove ρ = 0 oppure N(ρ) < N(β).

Dimostrazione costruttiva:

Poniamo u + vi = α/β, dove la divisione avviene nel campo C dei numeri complessi. Si ha pertanto

u + vi = αβ^-1 = αconj(β)/N(β).

Poiché il prodotto αconj(β) è ancora un intero di Gauss, i coefficienti u e v sono numeri razionali. Poniamo

μ = round(u) + round(v)i   e   ρ = α - βμ. Si ha:

N(ρ) = N(α - βμ) = N(β)N(α/β - μ) = N(β)N(u + vi - (round(u) + round(v)i)) = N(β)N( (u - round(u)) + (v - round(v))i ) =
= N(β)((u - round(u))² + (v - round(v))²) ≤ N(β)((1/2)² + (1/2)²) = (1/2)N(β) < N(β).

Ricordiamo la definizione:

Diciamo che γ è MCD di α e β se:

• γ|α e γ|β
• δ|α e δ|β implica δ|γ

Vogliamo ora introdurre il concetto di primo di Gauss. Pensiamo ai numeri primi ordinari. Se p è primo e p = ab, possiamo essere certi che uno dei fattori è invertibile e l'altro è associato a p (ovviamente in Z). Per esempio 7 = 7x1, o 7 = -7x-1, a parte l'ordine. Per imitazione, definiamo:

α si dice primo in IG se α = βγ implica che β o γ è invertibile.

α è primo in IG se e solo se α = βγ implica che N(β) = 1 o N(γ) = 1.

detto in altro modo:

α non è primo se e solo se α = βγ con N(β) < N(α) e N(γ) < N(α).

Per esempio 239 + 180i ha norma 89521, che è primo. Quindi 239 + 180i è primo in IG.

Il Teorema Fondamentale dell'Aritmetica (TEOFAR) asserisce che:

Ogni intero n in Z, non nullo e non invertibile, è prodotto di numeri primi. Il prodotto è unico a meno dell'ordine e di associati.

Per esempio 2873850 = 2x3x5x5x7x7x17x23 = 23x(-2)x(-3)x7x5x(-5)x17x(-7) = ....

TEOFARIG

Ogni α non nullo e non invertibile in IG è prodotto di primi. Il prodotto è unico a meno dell'ordine e di associati.

Dimostrazione

Si fa per assurdo. Sia S l'insieme degli interi di Gauss, non nulli e non invertibili, che non sono prodotto di primi. Supponiamo che S non sia vuoto. Poiché le norme sono numeri interi positivi, esiste in S un α tale che N(α) è minimo, ovvero:

(i) per ogni β in S, N(α) ≤ N(β)

Poiché α appartiene a S, α non può essere primo. Dunque α = βγ con N(β) < N(α) e N(γ) < N(α).

Per la minimalità di N(α), né β né γ appartengono a S. Dunque β e γ sono prodotto di primi. Ma allora anche α = βγ è prodotto di primi, che è assurdo. Pertanto S è vuoto!

Si prova poi facilmente la unicità, utilizzando questi fatti:

• se un primo divide un prodotto divide almeno uno dei fattori
  
• se un primo divide un altro primo i due risultano associati

1. ogni primo π in IG divide un unico primo ordinario p.
2. 1 + i è primo, di norma 2.
3. se p è primo della forma 4k + 3, p rimane primo in IG, con norma p².
4. se p è primo della forma 4k + 1, p in IG si fattorizza nel prodotto πconj(π), dove π e conj(π) sono primi coniugati non associati, di norma p.

E' noto che se p è congruo a 1 modulo 4, allora esiste una radice quadrata di -1 modulo p. Per esempio, se p = 13,
5² = 25 = -1 modulo 13.
Sia dunque a un intero tale che a² modulo p è -1.

Allora p|(a² + 1). In IG p divide (a - i)(a + i). Poiché p, ovviamente, non divide né a + i, né a - i, p non è primo in IG. Quindi p = πτ dove π non è associato a p, e τ non ha norma 1. Segue immediatamente che N(π) = N(τ) = p.

Come conseguenza, otteniamo gratuitamente questo risultato (Fermat):

E' facile poi dimostrare che la espressione di p come somma di due quadrati (ovvero come norma di π) è unica, a parte l'ordine.

Da quanto detto si ottiene che si possono elencare i primi in IG, elencando i fattori in IG dei primi ordinari.

Questo procedimento è essenzialmente lo stesso dell'esprimere i primi p (del tipo 4k + 1) come somma di due quadrati. Infatti se p è congruo a 3 modulo 4 rimane primo e non si fattorizza. Se p = 4k + 1, allora p = a² + b² e p si fattorizza in IG nel prodotto di due primi:
p = (a + bi)(a - bi).
Pertanto, in questo caso, p genera in IG due primi non associati: a + bi e b + ai ( = i(a - bi)).

Come elencare i primi di Gauss

Per quanto detto è sufficiente scrivere i fattori primi (in IG) dei numeri primi ordinari.

2 => 1 + i (2 è associato al quadrato del primo 1 + i)
3 => 3 (rimane primo)
5 => 1 + 2i, 2 + i (2 + i è associato al coniugato di 1 + 2i)
7 => 7
11 => 11
13 => 2 +3i, 3 + 2i
17 => 1 + 4i, 4 + i
19 => 19
23 => 23
29 => 2 + 5i, 5 + 2i
31 => 31
....
2017 => 9 + 44i, 44 + 9i
....

Figura 2

Abbiamo visto che 2 e i primi congrui a 1 modulo 4 sono somma di due quadrati. Rispondiamo ora alla domanda: quali interi sono somma di due quadrati? Osserviamo che ogni intero n si può scrivere nella forma m²p₁p₂...p_s, dove i p_j sono primi distinti. Ovviamente m può essere 1; in questo caso n è prodotto di primi distinti e si dice privo di quadrati (square free).

Teorema sulla somma di due quadrati

Dato un intero n = m²p₁p₂...p_s, n è somma di due quadrati se e solo se ogni p_j è congruo a 1 modulo 4.

Diamo una dimostrazione costruttiva della parte se

Poiché per ipotesi ogni p_j è della forma 4k + 1, esistono primi di Gauss π₁, ..., π_s tali che per ogni j compreso tra 1 ed s si ha N(π_j) = p_j. Inoltre ovviamente N(m) = m². Quindi:

n = N(m)N(π₁) ... N(π_j) ... N(π_s) = N(mπ₁ ... π_j ... π_s) = N(z) = a² + b².

Esempio

Sia dato n = 8742825 = 3²x5²x7²x13x61 = (105)²x13x61.

Abbiamo m = 105, p₁ = 13 = 4 + 9 = N(2 + 3i) = N(π₁) e p₂ = 61 = 25 + 36 = N(5 + 6i) = N(π₂).
Dunque z = mπ₁π₂ = 105((2 + 3i))((5 + 6i)) = 105(-8 + 27i) = (-840 + 2835i).

Pertanto n = N(z) = 840² + 2835².

Il Gruppo Pitagorico è un gruppo abeliano (commutativo) infinito. E' facile vedere che gli unici elementi di GP con periodo finito sono le quattro classi singolari: esse formano il gruppo di torsione di GP. Ricordiamo che il periodo di un elemento x in un gruppo G è il minimo intero positivo e tale che x^e = 1_G, dove 1_G è l'elemento neutro di G. Se non esiste alcun intero positivo tale che x^e = 1_G, diciamo che x ha periodo infinito. In GP dunque tutti gli elementi hanno periodo infinito tranne l'elemento neutro [1, 0] che ha periodo 1, [-1,0] che ha periodo 2, e gli elementi [0, 1] e [0, -1] che hanno periodo 4.

Chiamiamo T il sottogruppo di torsione.

Nel teorema che segue vediamo che il gruppo GP, modulo T, è costituito dai quadrati degli interi di Gauss.

Lavorare modulo T significa che se [a, b] è non singolare, si identificano le classi

Data questa identificazione e visto che in una CPP a e b devono avere parità diverse, possiamo supporre senza restrizioni che b sia pari e positivo. Si noti che le quattro classi singolari si identificano tra di loro, venendo a coincidere con la classe elemento neutro [1, 0].

Teorema dei quadrati

1 - Se [a, b] è un elemento non singolare di GP esiste un intero di Gauss u + vi di norma dispari tale che a + bi = (u + vi)² e MCD(u, v) = 1.

2 - Se MCD(u, v) = 1 e poniamo a + bi = (u + vi)², allora [a, b] è un elemento non singolare di GP.

3 - Se MCD(a, b) = 1, a² + b² = z e z è dispari, allora ogni divisore primo (in Z) di z è congruo a 1 modulo 4.

Dimostrazione della parte 1

1 - Per ipotesi MCD(a, b) = 1 e, come si è detto, possiamo supporre b pari e positivo.
Poiché (a, b) è una CPP esiste c tale che a² + b² = c², e c² - a² = (c - a)(c + a) = b².
c ed a sono entrambi dispari e coprimi. Quindi (c + a)/2 e (c - a)/2 sono interi e quadrati.
Posto u = ( (c + a)/2)^1/2 e v = ( (c - a)/2)^1/2 (u e v positivi) si ha:

2uv = 2( (c + a)/2)^1/2( (c - a)/2)^1/2 = 2((c + a)(c - a)/4)^1/2 = 2(b²/4)^1/2 = b
u² - v² = (c + a)/2 - (c - a)/2 = a

Quindi (u + vi)² = (u² - v²) + 2uvi = a + bi. MCD(u, v) = 1 perché a e b sono coprimi. Inoltre, poiché a è dispari, u e v devono avere parità diverse e la norma di u + vi è dispari.

Esempio

Consideriamo la classe [-15, 8], cioè a = -15 e b = 8.
a² + b² = 289, e c = 17.
(c + a)/2 = 1 e quindi u = 1
(c - a)/2 = 16 e quindi v = 4
-15 + 8i = (1 + 4i)²

Dimostrazione della parte 2

Posto a + bi = (u + vi)² e detta c la norma di u + vi, si ha che N(a + bi) = c².
Pertanto a² + b² = c².

Dimostrazione della parte 3

Per ipotesi a² + b² = (a + bi)(a - bi) = z
z è dispari, e quindi i divisori di z sono diversi da 2.
Se p divide z e p è primo in IG, allora p deve dividere a + bi o a - bi. Ma questo non può essere perché MCD(a, b) = 1.
Quindi p è un primo di Z che non rimane primo in IG: pertanto p è della forma 4k + 1.

Dato p in S, p si fattorizza in IG nel prodotto ρconj(ρ), con ρ e conj(ρ) in SIG. Poniamo ρ = s + ti, e conseguentemente conj(ρ) = s - ti. ρ ha quattro associati in IG: s + t i, - s - ti, - t + si, t - si.
Anche conj(ρ) ha quattro associati: s - t i, - s + ti, - t - si, t + si
Questi otto interi di Gauss sono tutti primi. Tra di essi ce n'è uno solo che ha entrambe le componenti positive e quella reale maggiore di quella immaginaria: lo denotiamo con π_p = u_p + v_pi. Sappiamo che p = N(π_p) = u_p² + v_p².

Indichiamo con [a_p, b_p] la classe che proviene da π_p², cioè la classe dove:

Chiamiamo queste particolari classi generatrici, e le corrispondenti CPP coppie generatrici.

Questo è l'insieme dei primi 100 elementi di S:

{5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181, 193, 197, 229, 233, 241, 257, 269, 277, 281, 293, 313, 317, 337, 349, 353, 373, 389, 397, 401, 409, 421, 433, 449, 457, 461, 509, 521, 541, 557, 569, 577, 593, 601, 613, 617, 641, 653, 661, 673, 677, 701, 709, 733, 757, 761, 769, 773, 797, 809, 821, 829, 853, 857, 877, 881, 929, 937, 941, 953, 977, 997, 1009, 1013, 1021, 1033, 1049, 1061, 1069, 1093, 1097, 1109, 1117, 1129, 1153, 1181, 1193, 1201, 1213, 1217, 1229, 1237}

E questo è l'insieme delle corrispondenti classi generatrici:

{[3,4], [5,12], [15,8], [21,20], [35,12], [9,40], [45,28], [11,60], [55,48], [39,80], [65,72], [99,20], [91,60], [15,112], [105,88], [51,140], [85,132], [165,52], [19,180], [95,168], [195,28], [221,60], [105,208], [209,120], [255,32], [69,260], [115,252], [231,160], [285,68], [25,312], [75,308], [175,288], [299,180], [225,272], [275,252], [189,340], [325,228], [399,40], [391,120], [29,420], [145,408], [351,280], [425,168], [261,380], [459,220], [279,440], [341,420], [165,532], [231,520], [575,48], [465,368], [551,240], [35,612], [105,608], [609,200], [315,572], [589,300], [385,552], [675,52], [651,260], [259,660], [725,108], [595,468], [39,760], [481,600], [195,748], [555,572], [759,280], [429,700], [629,540], [205,828], [825,232], [805,348], [369,800], [129,920], [215,912], [741,580], [615,728], [945,248], [925,372], [559,840], [45,1012], [779,660], [1015,192], [999,320], [861,620], [731,780], [1085,132], [585,928], [141,1100], [235,1092], [329,1080], [1025,528], [1131,340], [855,832], [49,1200], [245,1188], [705,992], [1221,140], [1075,612]}

Come si è detto sopra, c'è un semplice algoritmo per passare dalla prima alla seconda lista:

Si sceglie un primo p in S, per esempio p = 1201.
Si scrive p come somma di due quadrati, p = u_p² + v_p², nel nostro caso 1201 = 25² + 24²
Si determina la classe: [u_p² - v_p², 2u_pv_p] = [25² - 24², 2x24x25] = [49, 1200]

Si noti che in realtà al primo p corrispondono due classi: [a, b] e [-a, b]. Abbiamo scelto come generatrici quelle con il primo termine positivo. Si noti che [-a, b] è uguale a [a, -b] modulo T, e quindi [-a, b] è la inversa di [a, b]: [-a, b] = [a, b]^-1.
Si noti che la classe [-a, b], sempre ragionando modulo T, proviene dal quadrato di conj(π_p).

Siamo ora in grado di determinare completamente la struttura di GP:

Teorema di struttura di GP

Ogni [a, b] in IG è prodotto di potenze di classi generatrici.

Dimostrazione costruttiva

Data [a, b], abbiamo visto che a + bi = (u + vi)², con MCD(u, v) = 1.
In IG u + vi si fattorizza in modo unico in un prodotto di primi, eventualmente ripetuti. Poiché la norma di u + vi è dispari, il primo 1 + i (che ha norma 2) non divide u + vi. I primi ordinari p in IG (i primi congrui a 3 modulo 4) non dividono u + vi perché MCD(u, v) = 1.
Quindi u + vi = ρ₁ρ₂...ρ_t, dove i ρ_j sono tutti in SIG.
Segue che a + bi = ρ₁²ρ₂²...ρ_t².
Ritornando alle classi, questo significa che [a, b] è prodotto di potenze (eventualmente negative) di classi generatrici.

Esempio

Sia [a, b] = [17591337, 8514584]. Il terzo elemento c della corrispondente TPP è 19543625.
Calcoliamo u, la radice quadrata di (c + a)/2. Si trova u = 4309.
Calcoliamo v, la radice quadrata di (c - a)/2. Si trova v = 988.
Si ha pertanto 17591337 + 8514584i = (4309 + 988i)².
Fattorizzando 4309 + 988i in IG si ottiene 4309 + 988i = i(2 - i)³(4 + i)²(21 - 10i)
Con le notazioni precedenti 4309 + 988i = i(conj(π₅)³π₁₇²conj(π₅₄₁)).
Ai quadrati π₅², π₁₇², π₅₄₁² corrispondono rispettivamente le classi generatrici [3, 4], [15, 8], [341, 420].

Pertanto in GP [17591337, 8514584] = [-3, 4]³[15, 8]²[-341, 420]

Abbiamo visto che la teoria delle terne pitagoriche è completamente controllata dall'insieme S dei numeri primi della forma 4k + 1, attraverso la sequenza primo ordinario p in S  =>  primi di Gauss π_p = u_p + v_pi e  conj(π_p)   =>
=>  terne pitagoriche (a_p, b_p, c_p)  e  (-a_p, b_p, c_p)  dove:

Si ottengono così tutte le terne generatrici. Tutte le altre sono prodotti di queste, nel senso sopra specificato:

Per esempio alla successione delle potenze di 5, { 5, 25, 125, 625, ... } corrisponde la successione di terne pitagoriche:

P5 = { (3, 4, 5),  (7, 24, 25),  (117, 44, 125),  (527, 336, 625),  ... }.

Dovrebbe a questo punto essere chiaro che P5 è determinata dalle potenze di 3 + 4i, o - equivalentemente - dalle potenze pari di 2 + i. Ovviamente l'insieme delle potenze di α = a + bi, ricorre con polinomio x² - 2ax + (a² + b²), polinomio che ha come zeri α e conj(α).

Nel caso di α = 3 + 4i, il polinomio di ricorsione è x² - 6x + 25. Le potenze di 3 + 4i sono:

{  1 + 0i, 3 + 4i, -7 + 24i, -117 + 44i, -527 -336i, ...  }

La parte reale e quella immaginaria ricorrono con il polinomio suddetto, per esempio:

-336 = 6x44 - 25x24     e    -527 = 6x(-117) - 25x(-7)

L'universo delle terne pitagoriche è intessuto di successioni ricorrenti di secondo ordine!

Questo stesso universo è sostenuto da una potente e celata struttura, un albero ternario: l'Albero di Pitagora. Parleremo di questa pianta celeste tra breve!

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

[55] 06 Aprile 2007

1 - I nuovi campioni

Due numeri primi p e q tali che q = p + 2 si dicono primi gemelli.

2 - Dove cercare i primi e particolarmente i gemelli

Penso che molti lettori (a giudicare dalle lettere che ho ricevuto) si siano accorti, meditando per loro conto sui misteri dei numeri, che i primi (tranne 2 e 3) sono tutti contenuti nelle successioni

6k + 1 = {1, 7, 13, 19, 25, 31, 37, 43, 49, 55, 61, 67, ... }
6k + 5 = {5, 11, 17, 23, 29, 35, 41, 47, 53, 59, 65, 69, ... }

Questo fatto si spiega con un minimo di aritmetica modulare. Se prendiamo un intero n positivo e lo dividiamo per 6, il resto della divisione sarà un intero compreso tra 0 e 5. Quindi n cadrà in una e una sola di queste sei successioni aritmetiche

6k
6k + 1
6k + 2
6k + 3
6k + 4
6k + 5

Si tratta di un vantaggio notevole: gli interi del tipo 6k +1 o 6k + 5 sono appena un terzo di tutti gli interi. Ma si può fare di meglio, prendendo come modulo 30. I numeri primi possono stare soltanto nelle successioni 30k + c dove c è coprimo con 30 (cioè non è divisibile per 2, 3 o 5).
Ci sono 8 classi, nelle quali stanno tutti i primi (tranne 2, 3 e 5):

30k + 29 =    {29, 59, 89, 119, 149, 179, 209, 239, 269, 299, 329, 359, ... }
30k + 1  = {1, 31, 61, 91, 121, 151, 181, 211, 241, 271, 301, 331, ... }

30k + 7  = {7, 37, 67, 97, 127, 157, 187, 217, 247, 277, 307, 337, ... }

30k + 11 = {11, 41, 71, 101, 131, 161, 191, 221, 251, 281, 311, 341, ... }
30k + 13 = {13, 43, 73, 103, 133, 163, 193, 223, 253, 283, 313, 343, ... }

30k + 17 = {17, 47, 77, 107, 137, 167, 197, 227, 257, 287, 317, 347, ... }
30k + 19 = {19, 49, 79, 109, 139, 169, 199, 229, 259, 289, 319, 349, ... }

30k + 23 = {23, 53, 83, 113, 143, 173, 203, 233, 263, 293, 323, 353, ... }

(30k + 29, 30(k+1) + 1)
(30k + 11, 30k + 13)
(30k + 17, 30k + 19)

Osserviamo che i campioni appena scoperti sono della terza forma.

Chiaramente si può procedere e prendere come modulo 210 = 2 × 3 × 5 × 7, ...

3 - Quanti sono i primi gemelli?

Il Teorema dei Numeri Primi (TNP) asserisce che:

Per esempio p(10) = 4, perché i primi minori o uguali a 10 sono 2, 3, 5, 7.

La (1) equivale a:

Figura 1

Si pensi che p(16.000.000) = 1.031.130, mentre il logaritmo integrale per x = 16.000.000 dà 1.031.434, con un errore di appena 314 e con una percentuale di errore di circa 3 su 10.000.

In Figura 2 si vede il grafico della differenza li(x) - p(x), per x fino a circa 10 milioni.

Figura 2

Il TNP (1) ci dice che la probabilità che un numero n preso a caso tra 1 e x sia primo è all'incirca 1/log(x). Nel caso dei primi gemelli
(p, p+2), trattandosi di una coppia, potremmo pensare ad una probabilità dell'ordine di 1/log²(x). Questo però sarebbe vero se i due eventi, estrarre p e p+2 primi, fossero indipendenti, cosa che è ben lungi dall'essere vera, in quanto p+2, per esempio, se p è primo, deve essere dispari, perché tutti i primi p maggiori di 2 sono dispari, e per questo solo fatto raddoppia in un colpo solo la probabilità di essere primo, rispetto ad un n casuale.

Se q è un generico primo, p può appartenere, in quanto non divisibile per q, a q-1 classi di resto modulo q (abbiamo usato questo fatto nel paragrafo 2) e di queste q-1 solo q-2 restano disponibili per p+2.

Un intero casuale ha probabilità (q-1)/q di non essere divisibile per q, mentre la probabilità di p+2 è (q-2)/(q-1).

C'è dunque un "vantaggio" per p+2, nel superare il test della divisione per q, quantificabile con il rapporto ((q-2)/(q-1))/((q-1)/q).

Questo ragionamento ci induce a considerare la costante C₂ così definita:

La costante C₂ si può effettivamente calcolare con grande precisione (sono note 5.020 cifre) e si trova

Ricordando il fattore 2 di cui si è parlato sopra, possiamo, euristicamente, supporre che:

dove p₂(x) denota in numero delle coppie di primi gemelli minori di x, e li₂(x) è

Naturalmente la (5) non è un teorema, ma soltanto una ipotesi, basata sulle considerazioni precedenti.

Si tratta però di una ipotesi molto buona!

Figura 3

In Figura 3 la curva disegnata con tratto nero sottile è p₂(x), per x che varia da 3 a 148.948.100.
La curva verde rappresenta invece 2C₂ li₂(x) nel medesimo intervallo. Le curve si sovrappongono quasi perfettamente.

In realtà il confronto con i dati sperimantali è impressionante. Nell'estremo destro di Figura 3 abbiamo:

p₂(148.948.100) = 626.554, e 2C₂li₂(148.948.100) = 626.531,86..., con una differenza di appena 23 coppie! La percentuale di errore è di circa 3,67 centomillesimi!

Nella figura sottostante vediamo la differenza tra il numero effettivo delle coppie gemelle ed il numero stimato mediante la (5):

Figura 4

Per disegnare il grafico della Figura 4 ho preso le 626.554 coppie di primi gemelli minori di N=148.948.100, ho diviso l'intervallo tra 1 e N in mille parti e nei mille estremi destri ho calcolato F(x) = p₂(x) - 2C₂li₂(x).

Malgrado l'abbondanza di dati sperimentali, rimane comunque irrisolta la famosa Congettura dei primi gemelli:

4 - Altre tre notevoli costanti matematiche.

Se la congettura dei primi gemelli è sbagliata allora la somma dei reciproci dei primi gemelli è certamente finita, è un ben preciso numero razionale positivo.

Anche se fossero infiniti, però, la somma della serie dei reciproci dei gemelli potrebbe essere finita ( si ricordi, per esempio, che la somma dei reciproci dei quadrati è p²/6 ).

In effetti Viggo Brun (1885-1978), nel 1919, provò che la serie dei reciproci dei gemelli converge! Quindi si ha:

Il numero B (del quale si sa ben poco) è detto costante di Brun.

Definiamo la funzione b(x) nel modo seguente:

La b(x) è una funzione a scalini, data dalle somme parziali della serie (7).
Per esempio b(32) = b(33) = b(34) = b(35) = b(36) = b(37) = 1,2657...
Nella figura sottostante si vede il grafo di b(x):

Figura 5

La convergenza di b(x) è molto lenta e incerta. Per il teorema di Brun siamo sicuri che la serie converge, ma è assai difficile fissare le cifre decimali del limite. Si sono calcolate (utilizzando argomenti e metodi di calcolo assai sofisticati) le prime 9 cifre decimali di B:

Come si intuisce dalla Figura 5, la strada per arrivare vicino a B deve essere molto, molto, molto lunga....

Se invece di sommare i reciproci dei primi gemelli sommiamo i reciproci dei numeri primi otteniamo, come già provò Eulero, una serie divergente.

Questa serie sembra divergere in modo molto simile al tendere all'infinito di log(log(p)), con grande calma e dignità.

Mi pare fosse Lenstra che, con una battuta, diceva "si sa che log(log(n)) va all'infinito, ma nessuno l'ha mai visto arrivarci!".

Figura 6

Nella Figura 6 la curva rossa rapprenta log(log(p_n)), dove p_n è l'n-esimo primo, e n va da 1 a 10⁶.

La curva nera è la somma di 1/p_n, nel medesimo intervallo.

Entrambe le funzioni di Figura 6 divergono, tendono all'infinito, se pur lentamente. Si nota subito, però, che sembrano parallele, quasi che la loro differenza sia costante.

Quello che accade è che la loro differenza tende ad una costante M, detta (attualmente) costante di Mertens.

Fu infatti Mertens a provare il seguente Teorema:

Della costante di Mertens sono note 8.010 cifre:

Poiché la somma dei reciproci dei numeri primi diverge, a maggior ragione divergerà la somma dei reciproci degli interi, la cosiddetta serie armonica.

Poiché, come è ben noto:

il logaritmo log(n) è il valore dell'area sottostante all'iperbole y = 1/x nel tratto compreso tra x = 1 e x = n:

Figura 7

Possiamo sovrastimare l'area, ovvero log(n), sommando le aree dei rettangoli le cui basi hanno tutte ampiezza 1,e le cui altezze sono rispettivamente 1, 1/2, 1/3, ...

Pertanto avremo certamente:

La somma a sinistra della (13) è la n-esima somma parziale della serie armonica (11): la denotiamo con H_n. I numeri razionali H_n vengono chiamati numeri armonici

Nella figura seguente:

Figura 8

la linea nera è il grafo di H_n, e quella sotto, rossa, rappresenta log(n), al variare di n.

La figura è abbastanza precisa, per esempio per n = 7x10⁵, si vede che H_n è circa 14, e log(n) si può valutare intorno a 13,5.
In effetti i valori reali sono H_n = 14,0361... e log(n) = 13,4588...

La Figura 8, come la Figura 6, sembra suggerire che la differenza tra H_n e log(n) tenda a divenire costante. Ed è proprio così, il limite della differenza esiste ed è la famosa costante "gamma" di Eulero - Mascheroni:

La costante g si calcola molto più facilmente delle tre viste in precedenza, e di essa sono noti milioni di cifre decimali. Il record attuale sembra appartenere al giovane studente Alex Yee, che nel dicembre del 2006 ha calcolato 116,6 milioni di cifre di g.

Malgrado g sia (o sembri) così noto, nessuno sa se è un numero razionale o meno! Nel bellissimo libro di Havel ([1]) si osserva, a pagina 97, che Thomas Papanikolaou ha calcolato lo sviluppo in frazione continua di g fino al 470.006-esimo quoziente parziale. Un numero reale è razionale se e solo se il suo sviluppo in frazione continua è finito, ... dunque questa era la speranza di Papanikolaou... Malgrado lo sviluppo non sia terminato, lasciando così irrisolto il mistero della irrazionalità di g, ha portato come risultato il fatto che, se g è razionale, il denominatore della frazione che lo rapprenta deve avere più di 240.000 cifre!

Ci sembra (ma è un sentimento, questo sì, irrazionale) impossibile che un numero come g, legato alla più ovvia delle sequenze, quella dei numeri armonici, sia tanto strano! E ben volentieri ci associamo alla seguente Congettura g:

Non resisto dal citare, sempre da [1], questa frase di David Hilbert (1900):

Consideriamo i problemi irrisolti, come la questione della irrazionalità della costante di Eulero - Mascheroni o l'esistenza di infiniti primi della forma 2ⁿ + 1. Per quanto possano sembrare inavvicinabili, questi problemi, e sebbene ci poniamo di fronte a loro quasi senza speranza, abbiamo nondimeno la ferma convinzione che la loro soluzione deve seguire da un numero finito di processi puramente logici.

Il mondo matematico è ancora in attesa di quel particolare numero finito di processi puramente logici.

La costante g appare in molte notevoli formule matematiche, per esempio nel Teorema di Mertens:

La covergenza della serie a sinistra nella (16) è drammaticamente veloce:

Figura 9

La linea nera rappresenta le prime 50 somme parziali della serie (si sono quindi utilizzati solo i primi 50 numeri primi). Proseguendo non è visibile in figura nessuna variazione, la curva (in realtà a gradini) che rappresenta la sequenza delle somme parziali si schiaccia letteralmante sula linea orizzontale rossa, che segna la costante M - g.

La (16) è di per sè un teorema assai interessante, che è dimostrato (Teorema 428) nel testo fondamentale di Hardy e Wrigth ([2]) a pagina 351.

Le costanti matematiche costituiscono un capitolo della matematica molto studiato e attivo. Uno dei massimi esperti del campo è Steven R. Finch che ha scritto anche un libro sull'argomento; si veda il suo importante sito: Mathematical Constants .

Naturalmente siamo noi che "promuoviamo" alcuni numeri, dando loro uno status privilegiato, in base ai nostri interessi, alle nostre conoscenze. Per quanto avanti proceda la storia dell'umanità solo un numero finito di numeri potrà essere promosso. Siamo esseri finiti e limitati.

Soltanto Dio conosce i numeri uno a uno, può ammirare le loro segrete relazioni e ascoltare la loro inesauribile e profonda armonia!

[1] - Julian Havil, Exploring Euler's Constant, Priceton University Press (2003)

[2] - G.H. Hardy - E. M. Wright, An Introduction to the Theory Of Numbers, Oxford University Press, (fourth edition) (1975)

Twin Primes

Introduction to twin primes and Brun's constant computation

Euler-Mascheroni constant

Numbers, constants and computation