Don't take life too seriously: it's just a temporary situation

Lehmer (numeri di) (I)

Sequenze 

I numeri di Lehmer, chiamati così perché studiati nel 1930 da Derrick Henry Lehmer (Berkeley, California, 23/2/1905 – Berkeley, California, 22/5/1991) nella sua tesi, sono una generalizzazione dei numeri di Fibonacci,.

 

Dati due numeri complessi α e β, tali che αβ = q e α + β = sqrt(r), con q e r interi primi tra loro e α / β non radice dell’unità, i numeri di Lehmer sono i numeri che formano la sequenza di Lehmer Formula per i numeri di Lehmer di indice dispari per n dispari e Formula per i numeri di Lehmer di indice pari per n pari, mentre i numeri associati di Lehmer sono i numeri che formano la sequenza di Lehmer associata Formula per i numeri di Lehmer associati di indice dispari per n dispari e Vn = αn + βn per n pari. Il legame tra le due sequenze è analogo a quello tra i numeri di Fibonacci e quelli di Lucas (I).

Dalla definizione segue che Formula per α e Formula per β, con a e b interi.

 

I numeri di Lehmer si possono anche ottenere con la ricorrenza: U0 = 0, U1 = 1, U2 = 1, Formula per U(n).

 

Con α = φ e β = 1 – φ, si ottengono i numeri di Fibonacci prendendo i termini di Un per n pari e quelli di Vn per n dispari e quelli di Lucas prendendo i termini di Vn per n pari e quelli di Un per n dispari.

 

Alcune proprietà:

  • MCD(αβ, Un) = 1;

  • MCD(Um, Un) = UMCD(m, n);

  • se d divide n e n > 2, Ud divide Un e MCD(U(n) / U(d), U(d)) divide n / d;

  • se un primo dispari p divide (α – β)2, divide Up, inoltre se p > 3, p2 non divide Up;

  • se un primo dispari p divide (α + β)2, divide U2p, inoltre se p > 3, p2 non divide U2p;

  • se un primo p non divide αβ(α2 – β2)2, divide Up – 1Up + 1;

  • se un primo p divide Um, divide U(mp) / U(m), inoltre se p è dispari, p2 non divide U(mp) / U(m);

  • se Um è un multiplo di 4, U(2m) / U(m) è multiplo di 2 ma non di 4;

  • se q = 1 e 2n + 1 è composto, Un + 1 + Un + e Un + 1Un non sono numeri primi.

 

I numeri di Lehmer soddisfano relazioni analoghe a quelle dei numeri di Lucas (I) e sono utilizzati in alcuni test per stabilire se un intero è primo.

 

Si dice che un numero di Lehmer Un ha un divisore primitivo se è divisibile per un numero primo che non divide alcun altro Uk con 0 < k < n né (α2 – β2)2. Due coppie di numeri (α, β) e (α’, β’) si dicono “equivalenti” se α / β = α' / β' = ±1 o α / β = α' / β' = ±sqrt(–1); due coppie equivalenti generano numeri di Lehmer privi di divisori primitivi per gli stessi valori di n, quindi nella ricerca si considerano solo coppie non equivalenti.

Un primo p è un divisore primitivo di Un se e solo se è divisore primitivo di Ln, termine n-esimo della sequenza di Lucas generata dagli stessi valori di α e β.

 

Un problema sui numeri di Lehmer che è stato completamente risolto solo in tempi relativamente recenti è quali abbiano divisori primitivi.

 

Il primo passo si deve a K. Zsigmondy, che nel 1892 dimostrò che se α e β sono interi, Un ha un divisore primitivo per n > 6.

 

Nel 1913 P.D. Carmichael dimostrò che se α e β sono reali, Ln ha un divisore primitivo per n > 12.

 

M. Ward nel 1955 dimostrò che se α2 e β2 sono reali e n è diverso da 6 e 12, Un ha un divisore primitivo.

 

Un grande progresso si deve a Andrzej Schinzel, che nel 1962 dimostrò che se α e β sono complessi, Un ha un divisore primitivo per n abbastanza grande.

Nel 1974 lo stesso Schinzel dimostrò che esiste un valore n0 indipendente da α e β, tale che per n > n0 Un ha un divisore primitivo. C. Stewart dimostrò nel 1977 che n0 ≤ 467e452 ≈ 4.3563748210 • 10236; P.M Voutier ridusse il limite a 2 • 1010 nel 1995 e a 30010 l’anno seguente.

Stewart dimostrò anche che, considerando tutti i valori di α e β, per n > 6 e diverso da 8, 10 e 12 i numeri di Lehmer privi di divisori primitivi sono in numero finito, mentre esistono infinite eccezioni per gli altri valori di n. Il metodo di Stewart permette di trovare tutte le eccezioni, fissato n.

 

Utilizzando il metodo di Stewart, P.M Voutier completò nel 1995 l’elenco dei numeri di Lehmer senza divisori primitivi per n ≤ 250, a meno di equivalenze, mostrato nella tabella seguente, nella quale k e m rappresentano numeri naturali.

n

(a, b)

1

Tutti

2

Tutti

3

(1 + q, 1 – 3q) per q diverso da 1, (3k + q, 3k – 3q) per q non multiplo di 3, k > 0 e k e q non entrambi uguali a 1

4

(1 + 2q, 1 – 2q) per q diverso da 1, (2k + 2q, 2k – 2q) per q dispari e k > 2 se q = 1, k > 0 altrimenti

5

(Fk – 2m, Fk – 2m – 4Fk) per k > 2, (Lk – 2m, Lk – 2m – 4Lk) per k diverso da 1

6

(1 – 3q, 1 – q) per q diverso da 1, (2k + 3q, 2kq) per q dispari e k > 0, (2k3m + 3q, 2k3mq) per q dispari e non multiplo di 3, k > 0 e m > 0, (3k + 3q, 3kq) per q non multiplo di 3 e k > 0

7

(1, –7), (1, –19), (3, –5), (5, –7), (13, –3), (14, –22)

8

(Qkm, Qkm – 4Pk) per k > 1, (Pkm, Pkm – 2Qk) per k > 1, dove Pn è un numero di Pell e numero di Pell e Qn è un numero di Pell – Lucas

9

(5, –3), (7, –1), (7, –5)

10

(Fk – 2m – 4Fk, Fk – 2m) per k > 2, (Lk – 2m – 4Lk, Lk – 2m) per k diverso da 1

12

(–Rk – 2m, Rk) per k > 1, dove Rn è definito dalla ricorrenza R0 = 0, R1 = 1, Rn + 1 = 4RnRn – 1,

(–Sk – 2m, Sk) per k > 0, dove Sn è definito dalla ricorrenza S0 = 1, S1 = 2, Sn + 1 = 4SnSn – 1,

(–Tk – 2m, Tk) per k > 0, dove Tn è definito dalla ricorrenza T0 = 1, T1 = 3, Tn + 1 = 4TnTn – 1,

(–Uk – 2m, Uk) per k > 0, dove Un è definito dalla ricorrenza U0 = 1, U1 = 5, Un + 1 = 4UnUn – 1

13

(1, –7)

14

(3, –13), (5, –3), (7, –1), (7, –5), (19, –1), (22, –14),

15

(7, –1), (10, –2)

18

(1, –7), (3, –5), (5, –7)

24

(3, –5), (5, –3)

26

(7, –1)

30

(1, –7), (2, –10)

 

La tabella spinse Voutier a supporre che n1 = 30.

 

Finalmente nel 1999 Yuri Bilu, Guillaume Hanrot e Paul M. Voutier dimostrarono che non esistono numeri di Lehmer senza divisori primitivi per n > 30, e che quindi l’elenco sopra riportato è completo.

 

Nel 1962 Schinzel dimostrò che infiniti numeri di una sequenza di Lehmer con α e β interi hanno almeno due divisori primitivi. Più precisamente se k = Π(αβ(α – β)2(α + β)2), dove Π(n) è il prodotto dei primi che dividono n, ciascuno preso una sola volta (v. funzione Π), m = 1 se k ≡ 1 mod 4, m = 2 altrimenti, n è maggiore di 4 e diverso da 6 e n / km è un intero dispari, allora Un ha almeno due divisori primitivi, tranne per alcune eccezioni per n < 12 • 109.

Nello stesso anno A. Rotkiewicz estese il teorema alle sequenze con α e β reali.

 

Nel 2007 Robert Juricevic dimostrò nella sua tesi di laurea che il teorema vale anche per α e β complessi e che le non vi sono eccezioni per n > n2, con n2 non maggiore di 12 • 109. Juricevic stabilì inoltre che n2 è almeno 84, per il caso α = (sqrt(3) + sqrt(–5)) / 2, β = (sqrt(3) – sqrt(–5)) / 2, ma il valore di n2 per α e β complessi è ancora da stabilire.

 

I lavori di questi matematici permettono di stabilire che la lista completa delle eccezioni, ossia dei numeri di Lehmer che hanno un solo divisore primitivo, per α e β reali.

La lista per α e β interi, a meno di equivalenze è quella riportata nella tabella seguente, nella quale k rappresenta un numero naturale e p un numero primo dispari.

n

(α, β)

1

((2k + 1)2, (2k – 1)2), ((p^k + 1)^2 / 4, (p^k – 1)^2 / 4)

2

((2k + 1)2, –(2k – 1)2), ((p^k + 1)^2 / 4, –(p^k – 1)^2 / 4)

3

(3, –1), (4, –1), (4, –3)

4

(2, ±1)

6

(3, 1), (4, –1), (4, 3)

12

(2, ±1), (3, ±2)

20

(2, ±1)

La lista completa delle eccezioni per α e β reali ma non interi, n > 4 e n diverso da 6 è quella riportata nella tabella seguente, a meno di equivalenze.

n

(α, β)

5

((sqrt(5) + 1) / 2, (sqrt(5) – 1) / 2), ((3 + sqrt(5)) / 2, (3 – sqrt(5)) / 2)

7

((sqrt(3) + sqrt(7)) / 2, (sqrt(3) – sqrt(7)) / 2)

10

((1 + sqrt(5)) / 2, (1 – sqrt(5)) / 2), ((sqrt(5) + 3) / 2, (sqrt(5) – 3) / 2)

12

(2, ±1), (3, ±2), 1 + sqrt(2), 1 – sqrt(2), ((sqrt(2) + sqrt(6)) / 2, ±(sqrt(2) – sqrt(6)) / 2)

14

((sqrt(7) + sqrt(3)) / 2, (sqrt(7) – sqrt(3)) / 2)

15

((sqrt(5) + 1) / 2, (sqrt(5) – 1) / 2)

20

(2, ±1)

30

((1 + sqrt(5)) / 2, (1 – sqrt(5)) / 2)

 

Il lavoro di Juricevic rende estremamente plausibile l’esistenza di alcune famiglie infinite di eccezioni per α e β complessi, ma manca per ora una dimostrazione rigorosa.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.