Suite de Sylvester

La suite de Sylvester est définie par récurrence forte :

${\displaystyle s_{0}=2,\ \forall n\geqslant 0,\,s_{n+1}=1+\prod _{k=0}^{n}s_{k}}$

On vérifie alors que ${\displaystyle s_{n+1}-1=\prod _{k=0}^{n}s_{k}=(s_{n}-1)s_{n}}$, si bien qu'on peut également la définir par récurrence simple :

${\displaystyle s_{0}=2,\ \forall n\geqslant 0,\,s_{n+1}=s_{n}(s_{n}-1)+1\quad [1]}$

On en déduit aussi une définition par récurrence double :

${\displaystyle s_{0}=2,s_{1}=3,\,\forall n\geqslant 0\,\,s_{n+2}=s_{n+1}^{2}-s_{n}(s_{n}-1)}$

On obtient une suite strictement croissante d'entiers, donc de limite infinie.

Comme ${\displaystyle {\frac {s_{n+1}}{s_{n}}}=s_{n}-1+{1 \over {s_{n}}}\sim s_{n}\longrightarrow +\infty }$, la série de terme général ${\displaystyle 1/s_{n}}$ est convergente d'après le critère de D'Alembert.

Un résultat remarquable est que la somme de cette série est égale à 1.

En effet, il résulte de la relation de récurrence [1] que :

${\displaystyle {\frac {1}{s_{n}-1}}-{\frac {1}{s_{n+1}-1}}={\frac {1}{s_{n}}}}$;

La somme des termes de ${\displaystyle 1/s_{0}}$ à ${\displaystyle 1/s_{N}}$ se réduit alors, par téléscopage, à :

${\displaystyle \sum _{n=0}^{N}{\frac {1}{s_{n}}}=\sum _{n=0}^{N}\left({\frac {1}{s_{n}-1}}-{\frac {1}{s_{n+1}-1}}\right)={\frac {1}{s_{0}-1}}-{\frac {1}{s_{N+1}-1}}=1-{\frac {1}{s_{N+1}-1}}\quad [2].}$

Puisque la suite ${\displaystyle (s_{n})}$ tend vers l'infini, ${\displaystyle \sum _{n=0}^{N}{\frac {1}{s_{n}}}}$ tend bien vers 1.

On peut donc écrire :

${\displaystyle 1=\sum _{n=0}^{\infty }{\frac {1}{s_{n}}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots }$

ce qui donne une représentation de 1 sous forme de somme infinie de fractions égyptiennes.

La même formule écrite sous la forme ${\displaystyle {\frac {1}{2}}={\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots }$ fournit un développement de 1/2 en somme infinie de fractions égyptiennes de dénominateurs impairs.

De plus, la formule [2] écrite sous la forme : ${\displaystyle 1=\sum _{n=0}^{N}{\frac {1}{s_{n}}}+{\frac {1}{s_{N+1}-1}}}$ donne une représentation de 1 sous forme de somme de fractions égyptiennes de longueur quelconque (tronquer la somme infinie après un nombre arbitraire de termes et soustraire 1 du dénominateur de la dernière fraction) ; par exemple :

${\displaystyle 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{6}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{42}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{43}}+{\tfrac {1}{1806}},\quad \dots }$

La somme des ${\displaystyle k}$ premiers termes de la suite ${\displaystyle \left({1 \over s_{n}}\right)}$constitue la meilleure approximation possible par défaut de 1 à l'aide de ${\displaystyle k}$ fractions égyptiennes [2]. Par exemple, la somme des quatre premiers termes de la série vaut 1805/1806 et par conséquent, pour représenter tout nombre dans l'intervalle ouvert ]1805/1806 , 1[, une somme de fractions égyptiennes doit avoir au moins cinq termes. Pour cette raison, toute série d'inverses d'entiers convergeant vers 1 converge moins vite que la série des inverses de la suite de Sylvester.

On peut interpréter la suite de Sylvester comme le résultat de l'algorithme glouton pour la décomposition du nombre 1 en somme de fractions égyptiennes, algorithme qui, à chaque étape, choisit la plus grande fraction égyptienne dont la somme avec les précédentes est strictement inférieure à 1.

Plus précisément si on pose ${\displaystyle s_{0}=2,s_{n}=\min {\left\{m\in \mathbb {N} /\sum _{k=0}^{n-1}{1 \over s_{k}}+{1 \over m}<1\right\}}}$, on obtient de nouveau la suite de Sylvester.

Comme ${\displaystyle s_{n+1}\sim s_{n}^{2}}$, la suite de Sylvester présente une croissance doublement exponentielle.

La suite ${\displaystyle \left(s_{n}^{1/2^{n+1}}\right)}$ tend en décroissant vers un nombre E = 1,264084735305... appelé constante de Vardi (suite A076393 de l'OEIS)[1] et on montre que non seulement ${\displaystyle s_{n}\sim E^{2^{n+1}}}$mais qu'on peut calculer exactement les termes de la suite de Sylvester par la formule :

${\displaystyle s_{n}=\left\lfloor E^{2^{n+1}}\right\rceil }$

où ${\displaystyle \left\lfloor x\right\rceil }$désigne l'entier le plus proche de ${\displaystyle x}$.

La croissance doublement exponentielle de la suite de Sylvester est comparable à celle de la suite des nombres de Fermat ${\displaystyle F_{n}}$. Ceux-ci sont habituellement définis par l'expression en double exponentielle : ${\displaystyle 2^{2^{n}}+1}$, mais ils sont aussi définis par une récurrence très voisine de celle définissant la suite de Sylvester :

${\displaystyle F_{n+1}=2+\prod _{k=0}^{n}{F_{k}}}$, alors que ${\displaystyle s_{n+1}=1+\prod _{k=0}^{n}s_{k}}$.

Si ${\displaystyle i<j}$, il résulte de la définition que ${\displaystyle s_{j}\equiv 1\mod s_{i}}$. Par conséquent, deux termes quelconques de la suite de Sylvester sont premiers entre eux. La suite peut donc servir de preuve à l'assertion "il existe une infinité de nombres premiers", puisqu'un nombre premier donné ne peut diviser qu'un terme de la suite au plus.

Plusieurs travaux ont été consacrés à la factorisation des termes de la suite de Sylvester en nombres premiers, mais il demeure beaucoup d'incertitudes à ce sujet. Par exemple, on ne sait pas si tous les termes de la suite sont sans facteurs carrés, bien que tous les termes connus le soient.

Comme Vardi (1991) l'indique, il est facile de déterminer de quel terme de la suite de Sylvester (s'il existe) un nombre premier ${\displaystyle p}$ donné est diviseur : il suffit de calculer les termes de la suite modulo ${\displaystyle p}$ à l'aide de la définition par récurrence (en répétant "remplacer ${\displaystyle x}$ par ${\displaystyle x^{2}-x+1\mod p}$") jusqu'à trouver un terme nul. Et si l'on obtient un terme non nul qui avait déjà été trouvé, on est assuré que ${\displaystyle p}$ ne divise aucun terme de la suite. À l'aide de cette technique, il a obtenu qu'exactement 1166 des trois premiers millions de nombres premiers sont des diviseurs des nombres de Sylvester[3] et qu'aucun d'entre eux n'était élevé au carré.

Un résultat de Jones (2006) conclut que la densité dans l'ensemble des nombres premiers des diviseurs premiers des termes de la suite de Sylvester est nulle.

D'autre part Odoni [4] a montré que tous les diviseurs premiers des termes de la suite de Sylvester (excepté 2 et 3) sont de la forme 6k+1.

La table ci-après présente la factorisation des termes de la suite de Sylvester (à l'exception des quatre premiers termes qui sont tous des nombres premiers)[5] :

(la notation Pn représente un nombre de ${\displaystyle n}$ chiffres dont on sait qu'il est premier, et Cn un nombre de ${\displaystyle n}$ chiffres dont on sait qu'il est composé, mais dont la décomposition est inconnue)

La liste croissante des nombres premiers qui divisent un terme de la suite de Sylvester est répertoriée A007996 dans l'OEIS.

On peut généraliser l'algorithme glouton de décomposition en somme infinie de fractions égyptiennes à un réel strictement positif ${\displaystyle x}$ autre que 1 : cet algorithme choisit, à chaque étape, la plus grande fraction égyptienne dont la somme avec les précédentes est strictement inférieure à ${\displaystyle x}$.

On pose donc ${\displaystyle s_{n}=\min {\left\{m\in \mathbb {N} /\sum _{k=0}^{n-1}{1 \over s_{k}}+{1 \over m}<x\right\}}}$, ou, de façon plus pratique :

${\displaystyle x_{-1}=x}$ puis pour tout entier naturel ${\displaystyle n}$ : ${\displaystyle \left\{{\begin{matrix}{s_{n}=\lfloor {\frac {1}{x_{n-1}}}\rfloor +1}\\{x_{n}=x_{n-1}-{1 \over s_{n}}}\end{matrix}}\right.}$.

Le développement en série de Sylvester de ${\displaystyle x}$ s'écrit alors

${\displaystyle x={\frac {1}{s_{0}}}+{\frac {1}{s_{1}}}+{\frac {1}{s_{2}}}+\dotsb }$ que l'on notera ${\displaystyle ]s_{0},s_{1},...[}$.

La suite d'entiers naturels non nuls ${\displaystyle (s_{n})_{n\geqslant 0}}$ est alors définie de façon unique par le fait que ${\displaystyle s_{n+1}\geqslant s_{n}(s_{n}-1)+1}$ pour tout ${\displaystyle n}$

et le réel ${\displaystyle x}$ est rationnel si et seulement si ${\displaystyle s_{n+1}=s_{n}(s_{n}-1)+1}$ à partir d'un certain rang.

Le développement du nombre 1 correspond bien sûr à la suite de Sylvester vue ci-dessus : ${\displaystyle 1=]2,3,7,43,1807,...[}$.

Exemples irrationnels :

• ${\displaystyle {\sqrt {2}}=1+]3,13,253,218201,...[}$, voir la suite A006487 de l'OEIS

• ${\displaystyle e=2+]2,5,55,9999,3620211523,...[}$, voir la suite A006525 de l'OEIS
• ${\displaystyle \pi =3+]8,61,5020,128541455,...[}$, voir la suite A001466 de l'OEIS

Si au lieu de prendre la plus grande fraction égyptienne dont la somme avec les précédentes est strictement inférieure à ${\displaystyle x}$, on prend celle qui est inférieure ou égale à ${\displaystyle x}$, l'algorithme est identique si ${\displaystyle x}$ est irrationnel, mais il s'arrête si ${\displaystyle x}$ est rationnel et on obtient le développement égyptien glouton fini de ${\displaystyle x}$.

Par exemple, ${\displaystyle {3 \over 16}={1 \over 6}+{1 \over 48}=]6,49,2353=49\times 48+1,5534257=2353\times 2352+1,...[}$.

Le développement en série de Sylvester a des liens avec celui de Engel[6].

Sylvester observa lui-même que la suite qui porte maintenant son nom semblait posséder la propriété unique d'avoir une croissance extrêmement rapide, tandis que la série somme de ses inverses convergeait vers un rationnel.

Plus précisément, il résulte des travaux de Badea (1993) que, si une suite d'entiers ${\displaystyle (a_{n})}$ croît suffisamment pour qu'à partir d'un certain rang ${\displaystyle n}$ :

${\displaystyle a_{n+1}\geqslant a_{n}(a_{n}-1)+1}$

et si la série : ${\displaystyle \sum {\frac {1}{a_{n}}}}$ converge vers un rationnel ${\displaystyle A}$,

alors, pour tout ${\displaystyle n}$ au-delà d'une certaine valeur, la suite peut être définie par la même relation de récurrence que la suite de Sylvester :

${\displaystyle a_{n+1}=a_{n}(a_{n}-1)+1}$

En 1980, Erdős conjectura que pour les résultats de ce type, l'inégalité conditionnant la croissance de la suite pouvait être remplacée par la condition plus faible :

${\displaystyle a_{n+1}\sim a_{n}^{2}}$.

Boyer et al. (2005) utilisent les propriétés de la suite de Sylvester pour spécifier le grand nombre de variétés d'Einstein sasakiennes (en) possédant la topologie différentielle de sphères de dimension impaire ou d'autres sphères exotiques. Ils démontrent que le nombre de métriques riemanniennes des variétés d'Einstein sasakiennes sur une sphère topologique de dimension ${\displaystyle 2n-1}$ est au moins proportionnelle à ${\displaystyle s_{n}}$ et croît donc selon une double exponentielle de ${\displaystyle n}$.

Selon Galambos et Woeginger (1995), Brown (1979) et Liang (1980) ont utilisé la suite de Sylvester pour construire un algorithme séquentiel minimisant le problème de bin packing. Seiden et Woeginger (2005) ont aussi utilisé cette suite pour élaborer un algorithme minimisant le problème de bin packing à deux dimensions[7].

Le problème de Znám (en) consiste à trouver un ensemble de nombres tel que chacun divise le produit de tous les autres plus 1, sans être égal à cette valeur. Si ce n'était cette dernière condition, la suite de Sylvester serait une solution du problème. Avec cette condition, les solutions constituent une série dont la définition est similaire à celle de la suite de Sylvester. Les solutions du problème de Znám ont des applications dans la classification des singularités des surfaces Brenton et Hill (1988) et dans la théorie des automates finis non déterministes (Domaratzki et al. 2005).

Curtiss (1922) présente une approximation de 1 par la somme de ${\displaystyle k}$ fractions unitaires comme approximation inférieure du nombre de diviseurs de tout nombre parfait et Miller (1919) utilise la même propriété pour minimiser la taille de certains groupes.