La successione di Sylvester: una ricorrenza semplice che nasconde primi, frazioni egizie e crescita doppiamente esponenziale

Prendi il numero [math]2[/math].

Elevalo al quadrato, sottrai il numero stesso e aggiungi [math]1[/math]:

[math]\displaystyle 2^2-2+1=3.[/math]

Ripeti l’operazione con [math]3[/math]:

[math]\displaystyle 3^2-3+1=7.[/math]

Poi con [math]7[/math]:

[math]\displaystyle 7^2-7+1=43.[/math]

E ancora:

[math]\displaystyle 43^2-43+1=1807.[/math]

La successione comincia quindi così:

[math]\displaystyle 2,\;3,\;7,\;43,\;1807,\;3263443,\ldots[/math]

La regola che la genera sembra quasi troppo semplice per produrre qualcosa di interessante:

[math]\displaystyle a_1=2,\qquad a_{n+1}=a_n^2-a_n+1.[/math]

Eppure questa è la successione di Sylvester, una delle successioni ricorsive più curiose della teoria dei numeri.

I suoi termini diventano rapidamente enormi, sono a due a due coprimi, hanno vincoli molto rigidi sui loro fattori primi e, attraverso i reciproci, costruiscono una rappresentazione di [math]1[/math] come somma infinita di frazioni unitarie. La stessa ricorrenza conduce inoltre a un problema di irrazionalità e a una rappresentazione sorprendentemente precisa della successione mediante una costante reale elevata a potenze [math]2^n[/math].

La cosa interessante, però, non è soltanto che i numeri crescano rapidamente. È vedere quanta struttura matematica possa essere nascosta dentro una formula che, all’inizio, sembra soltanto una curiosità aritmetica.

Da una ricorrenza quadratica a un prodotto sorprendente

Consideriamo la successione

[math]\displaystyle a_1=2,\qquad a_{n+1}=a_n^2-a_n+1.[/math]

La prima osservazione importante arriva riscrivendo la ricorrenza:

[math]\displaystyle a_{n+1}-1=a_n(a_n-1).[/math]

Questa forma permette di individuare una relazione molto più profonda:

[math]\displaystyle \boxed{a_{n+1}=1+a_1a_2\cdots a_n}.[/math]

Per dimostrarla basta procedere per induzione.

Per [math]n=1[/math],

[math]\displaystyle a_2=3=1+2.[/math]

Supponiamo ora che

[math]\displaystyle a_n-1=a_1a_2\cdots a_{n-1}.[/math]

Dalla ricorrenza segue

[math]\displaystyle a_{n+1}-1=a_n(a_n-1),[/math]

e quindi

[math]\displaystyle \begin{aligned}
a_{n+1}-1 &= a_n\,a_1a_2\cdots a_{n-1} \\
&= a_1a_2\cdots a_n.
\end{aligned}[/math]

Pertanto

[math]\displaystyle a_{n+1}=1+a_1a_2\cdots a_n.[/math]

Per esempio,

[math]\displaystyle a_4=1+2\cdot3\cdot7=43.[/math]

Questa identità cambia completamente il modo in cui possiamo guardare la successione. Non abbiamo più soltanto una ricorrenza quadratica: ogni nuovo termine è uguale a [math]1[/math] più il prodotto di tutti quelli che lo precedono.

Ogni termine è coprimo con tutti gli altri

La relazione precedente contiene immediatamente una conseguenza molto forte.

Supponiamo che [math]i<j[/math]. Poiché [math]a_i[/math] compare nel prodotto che definisce [math]a_j[/math],

[math]\displaystyle a_j=1+a_1a_2\cdots a_{j-1}[/math]

implica

[math]\displaystyle a_j\equiv 1 \pmod{a_i}.[/math]

Di conseguenza,

[math]\displaystyle \gcd(a_i,a_j)=1.[/math]

Abbiamo quindi

[math]\displaystyle \boxed{\gcd(a_i,a_j)=1\qquad\text{per }i\neq j.}[/math]

I termini della successione sono dunque a due a due coprimi.

È una proprietà che ricorda immediatamente la dimostrazione euclidea dell’infinità dei numeri primi: costruendo numeri che non condividono fattori primi con quelli precedenti, si è costretti a introdurre continuamente nuovi primi.

Nel caso della successione di Sylvester il meccanismo è ancora più interessante, perché possiamo dire qualcosa non soltanto sull’esistenza di nuovi fattori primi, ma anche sulla loro forma modulo [math]6[/math] e modulo [math]12[/math].

Quali primi possono dividere un termine della successione?

Supponiamo che [math]p[/math] sia un primo che divide [math]a_n[/math], con [math]n>2[/math].

Poniamo

[math]\displaystyle x=a_{n-1}.[/math]

Dalla ricorrenza abbiamo

[math]\displaystyle x^2-x+1\equiv 0\pmod p.[/math]

Il numero [math]x[/math] non è nullo modulo [math]p[/math], perché altrimenti avremmo

[math]\displaystyle x^2-x+1\equiv 1\pmod p,[/math]

che non può essere [math]0[/math].

Ora osserviamo che

[math]\displaystyle x^3+1=(x+1)(x^2-x+1).[/math]

Poiché

[math]\displaystyle x^2-x+1\equiv 0\pmod p,[/math]

segue che

[math]\displaystyle x^3\equiv -1\pmod p,[/math]

e quindi

[math]\displaystyle x^6\equiv 1\pmod p.[/math]

L’ordine moltiplicativo di [math]x[/math] modulo [math]p[/math] divide dunque [math]6[/math].

I possibili ordini sono [math]1,2,3,6[/math], ma i primi tre possono essere esclusi.

Se l’ordine fosse [math]1[/math], avremmo [math]x\equiv 1\pmod p[/math], e quindi

[math]\displaystyle x^2-x+1\equiv 1\pmod p,[/math]

assurdo.

Se l’ordine fosse [math]2[/math], avremmo [math]x\equiv -1\pmod p[/math], da cui

[math]\displaystyle x^2-x+1\equiv 3\pmod p.[/math]

Questo richiederebbe [math]p=3[/math], ma [math]3[/math] divide [math]a_2[/math] e non può dividere [math]a_n[/math] per [math]n>2[/math], perché i termini sono a due a due coprimi.

Se l’ordine fosse [math]3[/math], avremmo contemporaneamente

[math]\displaystyle x^3\equiv 1\pmod p[/math]

e

[math]\displaystyle x^3\equiv -1\pmod p,[/math]

da cui [math]2\equiv 0\pmod p[/math], impossibile perché i termini [math]a_n[/math], per [math]n>1[/math], sono dispari.

Rimane quindi soltanto

[math]\displaystyle \operatorname{ord}_p(x)=6.[/math]

Per il teorema di Lagrange applicato al gruppo moltiplicativo modulo [math]p[/math], l’ordine di un elemento divide [math]p-1[/math]. Pertanto

[math]\displaystyle 6\mid p-1,[/math]

e dunque

[math]\displaystyle \boxed{p\equiv 1\pmod 6}.[/math]

Questa conclusione vale per ogni primo che divide [math]a_n[/math] con [math]n>2[/math].

Il primo [math]3[/math] costituisce naturalmente l’eccezione iniziale, perché

[math]\displaystyle a_2=3.[/math]

Una successione che non contiene quadrati perfetti

La stessa ricorrenza permette di stabilire in modo elementare che nessun termine, a partire da [math]a_2[/math], è un quadrato perfetto.

Poniamo

[math]\displaystyle x=a_{n-1}.[/math]

Allora

[math]\displaystyle a_n=x^2-x+1.[/math]

Per [math]x>1[/math],

[math]\displaystyle (x-1)^2<x^2-x+1<x^2.[/math]

Infatti,

[math]\displaystyle x^2-x+1-(x-1)^2=x>0[/math]

e

[math]\displaystyle x^2-(x^2-x+1)=x-1>0.[/math]

Quindi [math]a_n[/math] è strettamente compreso tra i due quadrati consecutivi

[math]\displaystyle (x-1)^2 \quad\text{e}\quad x^2.[/math]

Non può quindi essere un quadrato perfetto.

Abbiamo così

[math]\displaystyle \boxed{a_n\text{ non è un quadrato perfetto per ogni }n>1.}[/math]

Per [math]n\ge 3[/math] esiste anche una dimostrazione modulare molto rapida: la successione soddisfa [math]a_n\equiv 7\pmod{36}[/math], quindi [math]a_n\equiv 3\pmod 4[/math], mentre un quadrato intero è sempre congruo a [math]0[/math] oppure [math]1\pmod 4[/math].

La successione nascosta dentro una somma di frazioni

A questo punto la successione sembra soprattutto un esercizio di teoria dei numeri.

Ma i suoi reciproci raccontano un’altra storia.

Dalla relazione

[math]\displaystyle a_{k+1}-1=a_k(a_k-1)[/math]

otteniamo

[math]\displaystyle \frac1{a_{k+1}-1}=\frac1{a_k(a_k-1)}.[/math]

Ma

[math]\displaystyle \frac1{a_k-1}-\frac1{a_k}=\frac{1}{a_k(a_k-1)},[/math]

quindi

[math]\displaystyle \frac1{a_k}=\frac1{a_k-1}-\frac1{a_{k+1}-1}.[/math]

La somma diventa telescopica:

[math]\displaystyle \sum_{k=1}^{n}\frac1{a_k}=\frac1{a_1-1}-\frac1{a_{n+1}-1}.[/math]

Poiché [math]a_1=2[/math],

[math]\displaystyle \boxed{\sum_{k=1}^{n}\frac1{a_k}=1-\frac1{a_{n+1}-1}}.[/math]

Poiché [math]a_n[/math] tende rapidamente all’infinito,

[math]\displaystyle \boxed{\sum_{k=1}^{\infty}\frac1{a_k}=1.}[/math]

In altre parole,

[math]\displaystyle \boxed{1=\frac12+\frac13+\frac17+\frac1{43}+\frac1{1807}+\frac1{3263443}+\cdots}[/math]

Questa è una rappresentazione egizia di [math]1[/math], cioè una rappresentazione ottenuta come somma di frazioni unitarie del tipo [math]1/m[/math].

La cosa ancora più interessante è che non si tratta semplicemente di una rappresentazione qualsiasi. Le somme parziali

[math]\displaystyle \frac12+\frac13+\frac17+\cdots+\frac1{a_n}[/math]

forniscono la migliore sottostima possibile di [math]1[/math] ottenibile con [math]n[/math] frazioni unitarie; questo risultato è noto nella teoria delle frazioni egizie ed è stato dimostrato in forma classica per la successione di Sylvester.

Per esempio,

[math]\displaystyle \frac12+\frac13+\frac17+\frac1{43}=\frac{1805}{1806}.[/math]

Quindi, usando quattro frazioni unitarie, non si può ottenere una frazione egizia più vicina a [math]1[/math] senza superarla. Qualunque frazione egizia compresa strettamente tra

[math]\displaystyle \frac{1805}{1806}[/math]

e [math]1[/math] richiede almeno cinque termini.

Il comportamento della successione, quindi, non è soltanto quello di una ricorrenza che produce numeri enormi: è anche intimamente legato a un problema di approssimazione razionale.

Una congruenza sorprendentemente stabile

Consideriamo ora la successione modulo [math]36[/math].

Abbiamo

[math]\displaystyle a_3=7,[/math]

e quindi

[math]\displaystyle a_3\equiv 7\pmod{36}.[/math]

Supponiamo che

[math]\displaystyle a_n\equiv 7\pmod{36}.[/math]

Allora

[math]\displaystyle \begin{aligned}
a_{n+1} &= a_n^2-a_n+1 \\
&\equiv 7^2-7+1 \\
&= 43 \\
&\equiv 7\pmod{36}.
\end{aligned}[/math]

Per induzione,

[math]\displaystyle \boxed{a_n\equiv 7\pmod{36}\qquad(n\ge 3).}[/math]

Da questa semplice congruenza seguono diverse conseguenze.

Innanzitutto,

[math]\displaystyle a_n\equiv 3\pmod 4.[/math]

Un numero congruo a [math]3\pmod 4[/math] non può essere espresso come somma di due quadrati interi, perché i quadrati modulo [math]4[/math] sono soltanto [math]0[/math] e [math]1[/math], e le possibili somme sono quindi [math]0,1,2[/math].

Pertanto

[math]\displaystyle \boxed{a_n\text{ non è somma di due quadrati per }n\ge 3.}[/math]

Ma la congruenza modulo [math]36[/math] permette di arrivare anche a un risultato sui fattori primi.

Poiché [math]a_n\equiv 3\pmod 4[/math], nella fattorizzazione di [math]a_n[/math] deve comparire almeno un primo

[math]\displaystyle q\equiv 3\pmod 4.[/math]

D’altra parte, per ogni primo che divide [math]a_n[/math], con [math]n\ge 3[/math], abbiamo già dimostrato

[math]\displaystyle q\equiv 1\pmod 6.[/math]

Combinando

[math]\displaystyle q\equiv 3\pmod 4[/math]

con

[math]\displaystyle q\equiv 1\pmod 6,[/math]

si ottiene, tramite il teorema cinese del resto,

[math]\displaystyle \boxed{q\equiv 7\pmod{12}.}[/math]

Ogni [math]a_n[/math], per [math]n\ge 3[/math], possiede quindi almeno un fattore primo della forma

[math]\displaystyle 12k+7.[/math]

E poiché i termini della successione sono a due a due coprimi, possiamo scegliere questi fattori in modo che siano distinti per termini distinti della successione.

Ne consegue che esistono infiniti numeri primi congrui a [math]7\pmod{12}[/math].

È un piccolo risultato di teoria dei numeri ottenuto senza ricorrere al teorema generale di Dirichlet sulle progressioni aritmetiche: non dimostra il teorema di Dirichlet, naturalmente, ma mostra come una particolare successione ricorsiva possa produrre direttamente un’infinità di primi appartenenti a una progressione aritmetica ben precisa.

Un esercizio sull’irrazionalità

La successione offre anche un esempio interessante di dimostrazione dell’irrazionalità.

Poniamo

[math]\displaystyle d_k=a_k-1.[/math]

Otteniamo

[math]\displaystyle 1,\;2,\;6,\;42,\;1806,\ldots[/math]

e, dalla relazione precedente,

[math]\displaystyle d_{k+1}=a_k(a_k-1)=d_k(d_k+1).[/math]

In particolare,

[math]\displaystyle d_k\mid d_{k+1}[/math]

e

[math]\displaystyle \frac{d_{k+1}}{d_k}=d_k+1\ge 2.[/math]

Consideriamo la serie

[math]\displaystyle S=\sum_{k=1}^{\infty}\frac1{d_k}.[/math]

Le somme parziali possono essere scritte con denominatore comune [math]d_n[/math]:

[math]\displaystyle S_n=\sum_{k=1}^{n}\frac1{d_k}=\frac{N_n}{d_n},[/math]

con [math]N_n\in\mathbb Z[/math].

Indichiamo con

[math]\displaystyle R_n=S-S_n[/math]

il resto della serie.

Poiché i denominatori successivi crescono almeno di un fattore [math]2[/math],

[math]\displaystyle d_{n+1}\ge 2d_n,[/math]

si ottiene

[math]\displaystyle \begin{aligned}
R_n &\le \frac1{d_{n+1}}\left(1+\frac12+\frac14+\cdots\right) \\
&= \frac2{d_{n+1}}.
\end{aligned}[/math]

Supponiamo ora, per assurdo, che

[math]\displaystyle S=\frac pq[/math]

sia razionale.

Allora

[math]\displaystyle q\,d_nR_n=p\,d_n-qN_n.[/math]

Il membro di destra è un intero positivo, perché [math]R_n>0[/math]. D’altra parte,

[math]\displaystyle \begin{aligned}
q\,d_nR_n &\le \frac{2q\,d_n}{d_{n+1}} \\
&= \frac{2q}{d_n+1}.
\end{aligned}[/math]

Ma

[math]\displaystyle \frac{2q}{d_n+1}\longrightarrow 0.[/math]

Per [math]n[/math] sufficientemente grande avremmo quindi un intero positivo strettamente compreso tra [math]0[/math] e [math]1[/math], cosa impossibile.

Pertanto

[math]\displaystyle \boxed{\sum_{k=1}^{\infty}\frac1{a_k-1}\text{ è irrazionale}.}[/math]

La dimostrazione è interessante perché sfrutta direttamente la crescita dei denominatori e la loro struttura di divisibilità. Non basta dire che la serie converge molto rapidamente: è proprio il modo in cui i denominatori si incastrano gli uni negli altri a permettere di trasformare l’ipotesi di razionalità in una contraddizione.

Dalla ricorrenza a una rappresentazione quasi esplicita

La crescita della successione è così rapida da suggerire una domanda naturale: possiamo descrivere [math]a_n[/math] senza applicare la ricorrenza passo dopo passo?

La risposta è sorprendentemente vicina a una formula esplicita.

Poniamo

[math]\displaystyle b_n=a_n-\frac12.[/math]

Dalla ricorrenza segue

[math]\displaystyle b_{n+1}=a_n^2-a_n+\frac12.[/math]

Poiché

[math]\displaystyle a_n=b_n+\frac12,[/math]

abbiamo

[math]\displaystyle b_{n+1}=b_n^2+\frac14.[/math]

Quindi

[math]\displaystyle \boxed{b_{n+1}=b_n^2+\frac14,\qquad b_1=\frac32.}[/math]

Prendiamo ora i logaritmi:

[math]\displaystyle \log b_{n+1}=2\log b_n+\log\left(1+\frac1{4b_n^2}\right).[/math]

Definiamo

[math]\displaystyle L_n=\frac{\log b_n}{2^n}.[/math]

Allora

[math]\displaystyle L_{n+1}-L_n=\frac{1}{2^{n+1}}\log\left(1+\frac1{4b_n^2}\right).[/math]

Gli incrementi sono positivi e la loro somma converge, perché

[math]\displaystyle \log(1+t)\le t[/math]

per [math]t\ge 0[/math], mentre [math]b_n[/math] cresce rapidamente.

Esiste quindi un limite finito

[math]\displaystyle L=\lim_{n\to\infty}L_n.[/math]

Definiamo

[math]\displaystyle E=e^L.[/math]

La costante [math]E[/math] è circa

[math]\displaystyle \boxed{E=1{,}2640847\ldots}[/math]

ed è strettamente maggiore di [math]1[/math]. Questa costante è nota anche come costante di Vardi, in relazione alla rappresentazione della successione di Sylvester.

Dalla definizione di [math]L[/math] si può controllare con precisione quanto [math]E^{2^n}[/math] si discosti da [math]b_n[/math]. Introducendo la coda

[math]\displaystyle \delta_n=\sum_{k\ge n}2^{\,n-k-1}\log\left(1+\frac1{4b_k^2}\right),[/math]

si ottiene

[math]\displaystyle E^{2^n}=b_ne^{\delta_n}.[/math]

Poiché

[math]\displaystyle 0<\delta_n\le\frac1{4b_n^2},[/math]

e per i valori della successione considerati

[math]\displaystyle e^\delta-1\le 2\delta,[/math]

segue

[math]\displaystyle 0<E^{2^n}-b_n\le\frac1{2b_n}<1.[/math]

Ricordando che

[math]\displaystyle b_n=a_n-\frac12,[/math]

otteniamo

[math]\displaystyle a_n<E^{2^n}+\frac12<a_n+1.[/math]

Di conseguenza,

[math]\displaystyle \boxed{a_n=\left\lfloor E^{2^n}+\frac12\right\rfloor.}[/math]

Non è una “formula chiusa” elementare nel senso usuale, perché la costante [math]E[/math] è definita attraverso un limite, ma è una rappresentazione estremamente efficace della successione: la ricorrenza viene sostituita da una potenza [math]E^{2^n}[/math], con un errore così piccolo da consentire di recuperare esattamente il termine intero mediante un arrotondamento. La costante e questa rappresentazione sono documentate nella letteratura sulle costanti matematiche e nella banca dati OEIS.

Per i primi valori si vede già il meccanismo:

[math]\displaystyle E^2\approx 1{,}598,[/math]

che porta a [math]2[/math];

[math]\displaystyle E^4\approx 2{,}554,[/math]

che porta a [math]3[/math];

[math]\displaystyle E^8\approx 6{,}52,[/math]

che porta a [math]7[/math];

e per [math]n=6[/math],

[math]\displaystyle E^{64}[/math]

è già dell’ordine di [math]3{,}26\cdot10^6[/math], producendo

[math]\displaystyle 3263443.[/math]

Quanto velocemente crescono questi numeri?

La rappresentazione precedente rende evidente il comportamento asintotico:

[math]\displaystyle a_n\sim E^{2^n}.[/math]

Prendendo i logaritmi,

[math]\displaystyle \log a_n\sim 2^n\log E.[/math]

Il numero di cifre decimali di [math]a_n[/math] è quindi dell’ordine di

[math]\displaystyle \log_{10}(a_n)\sim 2^n\log_{10}E.[/math]

Poiché

[math]\displaystyle \log_{10}E\approx 0{,}1017,[/math]

il numero di cifre cresce approssimativamente come

[math]\displaystyle \boxed{0{,}1017\cdot 2^n}.[/math]

Non siamo quindi davanti a una crescita semplicemente esponenziale nel senso usuale. È l’esponente stesso a crescere esponenzialmente con [math]n[/math]: la successione ha una crescita doppiamente esponenziale.

Ed è proprio questo uno degli aspetti più divertenti della successione di Sylvester: la formula che la genera contiene soltanto un quadrato, una sottrazione e un [math]1[/math], ma dopo poche iterazioni produce numeri che sfuggono rapidamente a qualsiasi intuizione basata sull’aritmetica ordinaria.

Una successione, molti problemi diversi

La successione di Sylvester è un buon esempio di come, in matematica, una definizione molto breve possa aprire porte completamente diverse.

La relazione

[math]\displaystyle a_{n+1}=a_n^2-a_n+1[/math]

porta a

[math]\displaystyle a_{n+1}=1+a_1a_2\cdots a_n,[/math]

e da qui alla coprimalità a due a due.

La stessa ricorrenza, osservata modulo [math]p[/math], porta invece all’equazione

[math]\displaystyle x^2-x+1\equiv 0\pmod p,[/math]

che costringe i fattori primi, salvo il caso iniziale [math]3[/math], a soddisfare

[math]\displaystyle p\equiv 1\pmod 6.[/math]

La congruenza modulo [math]36[/math] aggiunge un’altra informazione,

[math]\displaystyle a_n\equiv 7\pmod{36},[/math]

dalla quale si ricava l’esistenza di fattori primi

[math]\displaystyle p\equiv 7\pmod{12}.[/math]

Guardando invece ai reciproci dei termini, la stessa successione diventa una rappresentazione egizia di [math]1[/math]:

[math]\displaystyle 1=\frac12+\frac13+\frac17+\frac1{43}+\cdots,[/math]

con somme parziali che forniscono le migliori sottostime di [math]1[/math] ottenibili con lo stesso numero di frazioni unitarie.

Spostando ancora lo sguardo, la successione dei numeri

[math]\displaystyle a_k-1[/math]

produce una serie irrazionale, mentre la trasformazione

[math]\displaystyle b_n=a_n-\frac12[/math]

porta alla costante

[math]\displaystyle E=1{,}2640847\ldots[/math]

e alla rappresentazione

[math]\displaystyle a_n=\left\lfloor E^{2^n}+\frac12\right\rfloor.[/math]

È difficile chiedere di più a una singola ricorrenza.

La successione di Sylvester non ha bisogno di essere collegata artificialmente ad applicazioni informatiche o a generiche “esplosioni combinatorie” per risultare interessante. La sua forza è tutta matematica: parte da una regola che si può calcolare con carta e penna e conduce, passo dopo passo, a coprimalità, congruenze, fattori primi, frazioni egizie, approssimazione razionale, irrazionalità e crescita doppiamente esponenziale.

Ed è proprio questa la lezione più interessante: in matematica, la semplicità della definizione non dice quasi nulla sulla profondità di ciò che può nascondere.