21 settembre 2019

Numeri di Fibonacci e potenze perfette

Tutti conoscono la successione di Fibonacci $F_n$, definita per ricorrenza come $$F_0=0, \quad F_1=1, \quad  F_n=F_{n-1}+F_{n-2}$$ e i cui primi termini sono $$0, \,1, \,1, \,2, \,3, \,5, \,8, \,13, \,21, \,34, \,55, \,89, \,144, \ldots$$ Una domanda naturale è quali siano numeri di Fibonacci che siano anche quadrati perfetti, o cubi perfetti o, più generalmente, $n$-esime potenze perfette. Semplici esperimenti al calcolatore suggeriscono la seguente
Congettura: Le sole potenze perfette nella successione di Fibonacci sono 1, 8, 144.
Come spesso accade in Teoria dei Numeri, un enunciato ingannevolmente semplice nasconde un problema molto difficile. Infatti, la Congettura è vera, ma la dimostrazione completa si è avuta solo pochi anni fa, per mezzo di tecniche simili a quelle utilizzate per la dimostrazione dell’Ultimo Teorema di Fermat.

Sembra che il problema sia stata proposto (indipendentemente) da Moser-Carlitz e Rollet nel 1963. Il caso dei quadrati fu risolto (ancora indipendentemente) da Cohn e Wyler nel 1963. Quello per i cubi è invece un risultato della dissertazione dottorale di Finkelstein (1964).

Nei decenni successivi furono proposte varie dimostrazioni per specifici valori di $n$, finché il caso generale venne risolto nel 2006 da Bugeaud, Mignotte and Siksek in un complesso lavoro su Annals of Mathematics  [1].

Per ulteriori dettagli, il lettore può consultare il post su MathOverflow [2] e il survey paper [3].


Riferimenti.

[1] Y. Bugeaud, M. Mignotte, S. Siksek: Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers, Annals of Mathematics 163 (2006), 969-1018.


[3] V. Andreijc: On Fibonacci powers, Univ. Beograd. Publ. Elektrotehn. Fak., Ser. Math 17 (2006), 38-44.

08 settembre 2019

La congettura di Pólya

Considerato l’insieme $M(n)$ dei numeri naturali minori o uguali a $n$, possiamo considerare la sua partizione formata dai due sottoinsiemi $O(n)$ e $E(n)$, dove $O(n)$ sono gli elementi di $M(n)$ aventi un numero dispari di fattori primi (contati con molteplicità) e $E(n)$  sono quelli aventi un numero pari di fattori primi.

Nel 1919, il matematico ungherese G. Pólya congetturò [1] che $O(n)$ è sempre più numeroso di $E(n)$, ossia che “più della metà” dei numeri naturali possiede un numero dispari di fattori primi distinti. Questa divenne nota come congettura di Pólya [2].

In termini tecnici, la congettura di Polya si può esprimere come $$L(n) = |E(n)|-|O(n)|= \sum_{k=1}^n \lambda(k)  \leq 0,$$ dove $\lambda(k)$  è la funzione di Liouville, che vale $1$ se $k$ ha un numero pari di fattori primi (sempre contati con molteplicità) e $-1$ altrimenti.

La congettura di Pólya è verificata fino a valori di $n$ superiori a $900$ milioni.  Tuttavia, essa venne confutata da C. B. Haselgrove nel 1958 [3], e il primo controesempio esplicito ($n=906180359$, per il quale $L(n)=1$) venne esibito da R. S. Lehman nel 1960 [4]. Oggi si sa che il più piccolo controesempio è $n = 906150257$, come dimostrato da M. Tanaka nel 1980 [5].

Questo è un tipico esempio che mostra come la mera evidenza numerica di un dato risultato aritmetico, anche per numeri che ci sembrano piuttosto grandi, implica ben poco riguardo la sua validità generale.

I primi valori di $n$ per i quali $L(n)=0$ sono $$n=2, \, 4, \, 6, \, 10, \,16, \, 26, \, 40, \, 96, \, 586, \, 906150256, \ldots$$
vedi la successione OEIS A028488. Recentemente, è stato dimostrato che la funzione $L(n)$ cambia segno infinite volte, vedi [6] e [7].


G. Pólya (circa 1973, fonte Wikipedia)

Riferimenti.

[1] G. Pólya: Verschiedene Bemerkungen zur Zahlentheorie, Jahresber. deutschen Math.-Verein. 28 (1919), 31-40.
[3] C. B. Haselgrove: A Disproof of a Conjecture of Pólya, Mathematika (1958), 141-145.
[4] R. S. Lehman: On Liouville's Function,  Math. Comput. 14 (1960), 311-320.
[5] M. Tanaka: A Numerical Investigation on Cumulative Sum of the Liouville FunctionTokyo J. Math. (1980), 187-189.
[6] P. Borwein, R. Ferguson, M. J. Mossinghoff: Sign Changes in Sums of the Liouville Function, Mathematics of Computation 77 (2008), no. 263, 1681–1694.
[7] P. Humphries: The distribution of weighted sums of the Liouville function and Pólya’s conjecture, Journal of Number Theory 133 (2013), 545–582.