Suite de Sylvester

Démonstration graphique de la convergence vers 1 de la somme 1/2 + 1/3 + 1/7 + 1/43 +... Chaque rang de n carrés de côté 1/n a une aire totale de 1/n ; l'ensemble des rangs recouvre exactement un carré plus grand, d'aire 1. (Les carrés de côté 1/1807 ou moins sont trop petits pour être dessinés sur le graphique.)

En théorie des nombres, la suite de Sylvester est une suite d'entiers telle que chaque terme est le produit de tous les termes précédents augmenté de 1, en partant d'un terme initial égal à 2. Les premiers termes de la suite sont :

2 ; 3 ; 7 ; 43 ; 1 807 ; 3 263 443 ; 10 650 056 950 807 ; 113 423 713 055 421 850 000 000 000 (Voir suite A000058 de l'OEIS).

En hommage à la démonstration par Euclide de l'infinitude des nombres premiers, les termes de cette suite sont aussi parfois appelés "nombres d'Euclide"^[1].

La suite de Sylvester doit son nom à James Joseph Sylvester qui, le premier, étudia ses propriétés dans les années 1880. Ses termes présentent une croissance exponentielle double. La série formée de la somme des inverses de cette suite converge vers 1, plus vite que toute autre série somme infinie d'inverses d'entiers convergeant vers 1.

La relation de récurrence qui définit les termes de la suite permet de factoriser ceux-ci plus facilement que toute autre série de croissance comparable, mais, du fait de la croissance rapide de la série, la décomposition en nombres premiers n'est connue que pour quelques termes. Des valeurs extraites de cette suite ont été utilisées pour construire des représentations de 1 sous forme de développement en fractions égyptiennes, et intervient dans l'étude des variétés d'Einstein sasakiennes (en).

Définitions

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

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

On vérifie alors que $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 :

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

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

Série des inverses et lien avec les fractions égyptiennes

Comme ${\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 $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 :

{\frac {1}{s_{n}-1}}-{\frac {1}{s_{n+1}-1}}={\frac {1}{s_{n}}}

;

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

\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 $(s_{n})$ tend vers l'infini, $\sum _{n=0}^{N}{\frac {1}{s_{n}}}$ tend bien vers 1.

On peut donc écrire :

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 ${\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 : $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 :

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 $k$ premiers termes de la suite $\left({1 \over s_{n}}\right)$ constitue la meilleure approximation possible par défaut de 1 à l'aide de $k$ fractions égyptienne ^[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.

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 $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.

Étude asymptotique

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

La suite $\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 $s_{n}\sim E^{2^{n+1}}$ mais qu'on peut calculer exactement les termes de la suite de Sylvester par la formule :

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

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

La croissance doublement exponentielle de la suite de Sylvester est comparable à celle de la suite des nombres de Fermat $F_{n}$ . Ceux-ci sont habituellement définis par l'expression en double exponentielle : $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 :

F_{n}=2+\prod _{k=0}^{n-1}F_{k}

.

Unicité des séries à croissance rapide ayant une limite rationnelle

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, alors 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 $a_{n}$ croît suffisamment pour qu'à partir d'un certain rang $n$ :

a_{n+1}\geq a_{n}^{2}-a_{n}+1

et si la série : $\sum {\frac {1}{a_{n}}}$

converge vers un rationnel $A$ , alors, pour tout $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 :

a_{n+1}=a_{n}^{2}-a_{n}+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 :

a_{n+1}\sim a_{n}^{2}

.

Divisibilité et factorisations

Si $i<j$ , il résulte de la définition que $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 $p$ donné est diviseur : il suffit de calculer les termes de la suite modulo $p$ à l'aide de la définition par récurrence (en répétant "remplacer $x$ par $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 $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é 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 $n$ chiffres dont on sait qu'il est premier, et Cn un nombre de $n$ chiffres dont on sait qu'il est composé, mais dont la décomposition est inconnue)

n	Facteurs de s_n
4	13 × 139
5	3263443, premier
6	547 × 607 × 1033 × 31051
7	29881 × 67003 × 9 119 521 × 6 212 157 481
8	5 295 435 634 831 × 31 401 519 357 481 260 × 77 366 930 214 022 000 000 000
9	181 × 1987 × 112 374 829 138 729 × 114 152 531 605 972 700 × P68
10	2287 × 2 271 427 × 21 430 986 826 194 127 000 000 000 000 000 000 000 000 000 × P156
11	73 × C416
12	2 589 377 038 614 498 000 000 × 2 872 413 602 289 671 000 000 000 000 × C785
13	52387 × 5 020 387 × 5 783 021 473 × 401 472 621 488 821 800 000 × 287 001 545 675 964 600 000 000 000 × C1600
14	13999 × 74203 × 9 638 659 × 57 218 683 × 10 861 631 274 478 494 000 × C3293
15	17881 × 97 822 786 011 310 110 × 54 062 008 753 544 850 000 000 000 000 000 × C6618
16	128551 × C13335
17	635263 × 1 286 773 × 21 269 959 × C26661
18	50 201 023 123 × 139 263 586 549 × 60 466 397 701 555 610 000 000 000 × C53313
19	C106721
20	352867 × 6 210 298 470 888 313 × C213419
21	387 347 773 × 1 620 516 511 × C426863
22	91 798 039 513 × C853750

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

Applications

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 $2n-1$ est au moins proportionnelle à $s_{n}$ et croît donc selon une double exponentielle de $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^[6].

Le problème de Známproblème de Znám 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 $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.

Annexes

Bibliographie

(en) Catalin Badea, « A theorem on irrationality of infinite series and applications », Acta Arithmetica, vol. 63,‎ 1993, p. 313-323
(en) Catalin Badea, « On some criteria for irrationality for series of positive rationals: a survey », 1995
(en) Charles P. Boyer, Krzysztof Galicki et János Kollár, « Einstein metrics on spheres », Ann. of Math., vol. 162, n^o 1,‎ 2005, p. 557-580 (DOI 10.4007/annals.2005.162.557, lire en ligne)
(en) Lawrence Brenton et Richard Hill, « On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities », Pacific J. Math., vol. 133, n^o 1,‎ 1988, p. 41-67 (lire en ligne)
(en) D. J. Brown, A lower bound for on-line one-dimensional bin packing algorithms ; Version = Tech. Rep. R-864, Coordinated Science Lab., Univ. Illinois, Urbana-Champaign, 1979
(en) D. R. Curtiss, « On Kellogg's diophantine problem », Amer. Math. Monthly, vol. 29,‎ 1922, p. 380-387 (DOI 10.2307/2299023, JSTOR 2299023)
(en) Michael Domaratzki, Keith Ellul, Jeffrey Shallit et Ming-Wei Wang, « Non-uniqueness and radius of cyclic unary NFAs », International Journal of Foundations of Computer Science, vol. 16, n^o 5,‎ 2005, p. 883-896 (DOI 10.1142/S0129054105003352, lire en ligne)
(en) Paul Erdős et Ronald Graham, Old and New Problems and Results in Combinatorial Number Theory, Univ. de Genève, coll. « Monographies de L'Enseignement mathématique » (n^o 28), 1980
(en) Gábor Galambos et Gerhard J. Woeginger, « On-line bin packing — A restricted survey », Mathematical Methods of Operations Research, vol. 42, n^o 1,‎ 1995, p. 25 (DOI 10.1007/BF01415672)
(en) Solomon Golomb, « On certain nonlinear recurring sequences », Amer. Math. Monthly, vol. 70, n^o 4,‎ 1963, p. 403-405 (DOI 10.2307/2311857, JSTOR 2311857)
(en) Ronald Graham, Donald Knuth et Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1989 (ISBN 0-201-55802-5), Exercise 4.37
(en) Rafe Jones, « The density of prime divisors in the arithmetic dynamics of quadratic polynomials », 2006 (arXiv math/0612415v1)
(en) Frank M. Liang, « A lower bound for on-line bin packing », Information Processing Letters, vol. 10, n^o 2,‎ 1980, p. 76-79 (DOI 10.1016/S0020-0190(80)90077-0)
(en) G. A. Miller (en), « Groups possessing a small number of sets of conjugate operators », Trans. Amer. Math. Soc., vol. 20, n^o 3,‎ 1919, p. 260-270 (DOI 10.2307/1988867, JSTOR 1988867)
(en) Martin Rosenman, « Problem 3536 », Amer. Math. Monthly, vol. 40, n^o 3,‎ 1933, p. 180 (JSTOR 2301036)
(en) H. E. Salzer, « The approximation of numbers as sums of reciprocals », Amer. Math. Monthly, vol. 54, n^o 3,‎ 1947, p. 135-142 (DOI 10.2307/2305906, JSTOR 2305906)
(en) Steven S. Seiden et Gerhard J. Woeginger, « The two-dimensional cutting stock problem revisited », Math. Prog., vol. 102, n^o 3,‎ 2005, p. 519-530 (DOI 10.1007/s10107-004-0548-1)
(en) K. Soundararajan, « Approximating 1 from below using n Egyptian fractions », 2005 (arXiv math/0502247v1)
(en) J. J. Sylvester, « On a point in the theory of vulgar fractions », Amer. J. Math., vol. 3, n^o 4,‎ 1880, p. 332-335 (DOI 10.2307/2369261, JSTOR 2369261)
(en) Ilan Vardi, Computational Recreations in Mathematica, Addison-Wesley, 1991 (ISBN 0-201-52989-0), p. 82-89

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sylvester's sequence » (voir la liste des auteurs).

↑ ^{a et b} Graham, Knuth et Patashnik (1989)
↑ Proposition généralement attribuée à Curtiss (1922), mais Miller (1919) a fait la même observation dans un article antérieur. Voir aussi Rosenman (1933), Salzer (1947) et Soundararajan (2005).
↑ Andersen, lui, a trouvé 1167 diviseurs premiers dans ces trois premiers millions.
↑ (en) R. W. K. ODONI, On the prime divisors of the sequence w(n+1) =1+w(1)⋯w(n), London, J. Lond. Math. Soc., II. Ser., 1985 (lire en ligne), p. 1–11
↑ Les facteurs premiers p de la suite de Sylvester s_n avec p < 5×10⁷ et n ≤ 200 sont listés par Vardi. Ken Takusagawa liste les factorisations jusqu'à s₉ et la factorisation de s₁₀. Les autres factorisations sont issues de Liste des factorisations de la suite de Sylvester tenue par Jens Kruse Andersen (version du 28/06/2014).
↑ Dans leur article, Seiden et Woeginger (2005) utilisent le nom de "Suite de Salzer" au lieu de celui de "Suite de Sylvester", d'après l'article de Salzer (1947) sur les problèmes de minimisation.

Voir aussi

Articles connexes

Liens externes

(en) Irrationality of Quadratic Sums, MathPages de K. S. Brown.
(en) Eric W. Weisstein, « Sylvester's Sequence », sur MathWorld

Portail des mathématiques

[:0-1] {a et b} Graham, Knuth et Patashnik (1989)

[2] Proposition généralement attribuée à Curtiss (1922), mais Miller (1919) a fait la même observation dans un article antérieur. Voir aussi Rosenman (1933), Salzer (1947) et Soundararajan (2005).

[3] Andersen, lui, a trouvé 1167 diviseurs premiers dans ces trois premiers millions.

[4] (en) R. W. K. ODONI, On the prime divisors of the sequence w(n+1) =1+w(1)⋯w(n), London, J. Lond. Math. Soc., II. Ser., 1985 (lire en ligne), p. 1–11

[5] Les facteurs premiers p de la suite de Sylvester s_n avec p < 5×10⁷ et n ≤ 200 sont listés par Vardi. Ken Takusagawa liste les factorisations jusqu'à s₉ et la factorisation de s₁₀. Les autres factorisations sont issues de Liste des factorisations de la suite de Sylvester tenue par Jens Kruse Andersen (version du 28/06/2014).

[6] Dans leur article, Seiden et Woeginger (2005) utilisent le nom de "Suite de Salzer" au lieu de celui de "Suite de Sylvester", d'après l'article de Salzer (1947) sur les problèmes de minimisation.

[1]

[2]

[3]

[4]

[5]

[6]