Seqüència de Sylvester

Demostració gràfica de la convergència a la unitat de la suma 1/2 + 1/3 + 1/7 + 1/43 + ... Cada filera de k quadrats de costat 1/k té àrea total 1/k, i tots els quadrats junts cobreint exactament un quadrat més gros que té àrea u. Els quadrats de costat 1/1807 o més petit són massa petits per ser vistos a la figura, i no hi són .

En teoria dels nombres, la seqüència de Sylvester és una seqüència d'enters en què cada membre de la seqüència és el producte dels membres anteriors més u. Els primers termes de la seqüència són: 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (successió A000058 a l'OEIS).

La seqüència de Sylvester pren el nom de James Joseph Sylvester, qui la investigà per primera vegada el 1880. Els seus valors creixen doblement exponencialment, i la suma dels seus recíprocs forma una sèrie de fraccions unitàries que convergeix a la unitat més aviat que qualsevol altra sèrie de fraccions unitàries amb la mateixa suma. La recurrència que la defineix permet una Factorització més senzilla que la d'altres nombres qualssevol de la mateixa mida, però, a causa del ràpid creixement de la seqüència, només es coneixen les factoritzacions completes en nombres primeres d'alguns dels seus termes. Els valors derivats d'aquesta seqüència s'han fet servir per construir representacions en fraccions egipcianes de suma 1, així com en varietats saskianes i les d'Einstein.

Definicions formals

Formalment, la seqüència de Sylvester es pot definir per la fórmula

$s_{n}=1+\prod _{i=0}^{n-1}s_{i}.$

El producte d'un conjunt buit és 1, car s₀ = 2.

Altrament, es pot definir la seqüència per la recurrència

$\displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,$ amb s₀ = 2.

Es pot demostrar per inducció que totes dues definicions són equivalents.

Relació amb les fraccions egipcianes

Les fraccions unitàries formades pels recíprocs dels valors de la seqüència de Sylvester generen una sèrie infinita:

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

Les sumes parcials d'aquesta sèrie tenen una forma simple,

$\sum _{i=0}^{j-1}{\frac {1}{s_{i}}}={\frac {s_{j}-2}{s_{j}-1}},$

com es pot demostrar per inducció. Aquesta identitat és certa per a j 0, ja que tots dos costats són zero. Per a j més grans, estendre el costat esquerre de la identitat fent servir la hipòtesi d'inducció dona

$\sum _{i=0}^{j-1}{\frac {1}{s_{i}}}={\frac {1}{s_{j-1}}}+\sum _{i=0}^{j-2}{\frac {1}{s_{i}}}={\frac {1}{s_{j-1}}}+{\frac {s_{j-1}-2}{s_{j-1}-1}}={\frac {s_{j-1}(s_{j-1}-1)-1}{s_{j-1}(s_{j-1}-1)}}={\frac {s_{j}-2}{s_{j}-1}},$

com es volia demostrar. Atès que aquesta seqüència de sumes parcials (s_j-2)/(s_j-1) convergeix a u, la sèrie global forma una representació en fracció egipciana infinita del nombre u:

$1={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots$

Es poden trobar representacions de la unitat en fraccions egipcianes finites, de qualsevol longitud, truncant aquesta sèrie i restant u del darrer denominador:

$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 suma dels primers k termes de la sèrie infinita dona l'estimació per defecte més propera possible a la unitat que qualsevol fracció egipciana de k termes. Per exemple, els primers quatre termes sumen 1805/1806, i, per tant, qualsevol fracció egipciana d'un nombre dins l'interval obert (1805/1806, 1) té almenys cinc termes.

Es pot interpretar la seqüència de Sylvester com el resultat d'un algorisme voraç per a fraccions egipcianes que en cada etapa tria el denominador més petit possible que fa la suma parcial de la sèrie més petita que 1. Altrament, els termes de la seqüència després del primer es poden interpretar com els denominadors de l'expansió voraç imparell d'1/2.

Fórmula en forma tancada i asimptòtica

Els nombres de Sylvester creixen doblement exponencialment com a funció de n. En particular, es pot demostrar que

$s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor ,$

per a un nombre E que és aproximadament 1.264. Aquesta fórmula fa l'efecte de l'algorisme següent:

s₀ és l'enter més proper a E²; s₁ és l'enter més proper a E⁴; s₂ és l'enter més proper a E⁸; per a s_n, preneu E², elevau-lo al quadrat n vegades més, i preneu-hi l'enter més proper.

Això només seria un algorisme pràctic si hi hagués una forma millor de calcular E amb la precisió requerida que no calcular s_n i prendre'n l'arrel quadrada repetidament.

El creixement doblement exponencial de la seqüència de Sylvester no resulta sorprenent si se'l compara a la seqüència dels nombres de Fermat F_n; els nombres de Fermat es defineixen habitualment amb una fórmula doblement exponencial, $2^{2^{n}}+1$, però també es poden definir amb una fórmula de productes molt semblant a la que defineix la seqüència de Sylvester:

$F_{n}=2+\prod _{i=0}^{n-1}F_{i}.$

Unicitat de la sèrie de creixement ràpid amb sumes racionals

Com Sylvester mateix observà, la seqüència de Sylvester sembla l'única que té valors que creixin tan ràpidament, alhora que té una sèrie de recíprocs que convergeix a un nombre racional.

Més precisament, es deriva de resultats de Badea (1993) que, si una seqüència d'enters $a_{n}$ creix prou aviat que

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

i si la sèrie

$A=\sum {\frac {1}{a_{i}}}$

convergeix a un nombre racional A, aleshores, per a tot n després de qualque punt, aquesta seqüència ha de ser definida per la mateixa recurrència

$a_{n}=a_{n-1}^{2}-a_{n-1}+1$

que es pot fer servir per definir la seqüència de Sylvester.

Erdős (1980) conjecturà que, en els resultats d'aquesta mena, la inequalitat que limita el creixement de la seqüència es podria substituir per una condició més feble,

$\lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.$

Badea (1995) recull els progressos lligats a aquesta conjectura; vegeu també Brown.

Divisibilitat i factoritzacions

Si i < j, se segueix de la definició que s_j ≡ 1 (mod s_i). Per tant, tot parell de nombres en la seqüència de Sylvester són primers entre si. La seqüència es pot fer servir per demostrar que hi ha infinits nombres primers, ja que qualsevol primer divideix, com a màxim, un nombre de la seqüència.

S'han esmerçat esforços a factoritzar dels nombres de la seqüència de Sylvester, però es desconeix molta cosa sobre llur factorització. Per exemple, es desconeix si tots els nombres en la seqüència són lliures de quadrats, tot i que tots els termes coneguts ho són.

Com Vardi (1991) descriu, és senzill de determinar quin nombre de Sylvester (si n'hi ha cap) un nombre primer donat divideix: n'hi ha prou a computar la recurrència que defineix els nombres modulo p fins que es troba un nombre congruent a zero (mod p) o bé un mòdul repetit. Per mitjà d'aquesta tècnica trobà que 1166 dels tres primers milions de nombres primers són divisors dels nombres de Sylvester. i que cap d'aquests primers no té un quadrat que divideixi un nombre de Sylvester. Un resultat general de Jones (2006) implica que el conjunt dels factors primers dels nombres de Sylvester té densitat zero dins el conjunt de tots els primers.

La taula següent mostra les factoritzacions conegudes d'aquests nombres, (llevat dels quatre primers, que són tots primers):

n	Factors de sn
4	13 × 139
5	3263443, que és primer
6	547 × 607 × 1033 × 31051
7	29881 × 67003 × 9119521 × 6212157481
8	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × P68
10	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
11	73 × C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
14	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
15	17881 × 97822786011310111 × C6649
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
18	50201023123 × 139263586549 × C53339
19	C106721
20	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

Com és habitual, Pn i Cn denoten nombres primers i compostos de n dígits.

Aplicacions

Boyer i cols. (2005) fan servir les propietats de la seqüència de Sylvester per definir grans nombres de Sasakian Einstein manifolds que tenen la topologia diferencial d'hiperesferes de dimensió senar o d'esferes exòtiques. Demostren que el nombre de mètriques Sasakian Einstein sobre una esfera topològica de dimensió 2n − 1 is almenys proporcional a s_n i doncs té creixement doblement exponencial amb n.

Com descriuen Galambos i Woeginger (1995), Brown (1979) i Liang (1980) usaren valors derivats de la seqüència de Sylvester per construir exemples de límit inferior per a algorismes de bin packing en línia. De forma semblant, Seiden i Woeginger (2005) fan servir la seqüència per fitar inferiorment el rendiment d'un cutting stock algorithm bidimensional.

El problema de Znám es refereix a conjunts de nombres tals que cada nombre del conjunt divideix però no és igual al producte de tots els altres nombres, més u. Sense el requeriment de la inequalitat, els valors de la seqüència de Sylvester resoldrien el problema; amb aquest requeriment, té d'altres solucions derivades de recurrències semblants a la que defineix la seqüència de Sylvester. Les solucions al problema de Znám tenen aplicacions a la classificació de singularitats de superfícies (Brenton i Hill 1988) i a la teoria dels autòmats finits no determinístics (Domaratzki i cols. 2005).

Curtiss (1922) descriu una aplicació de les aproximacions més properes a la unitat amb sumes de fraccions unitàries de k termes, en la determinació d'una fita inferior dels nombre de divisors de qualsevol nombre perfecte, i Miller (1919) usa la mateixa propietat per afitar inferiorment la mida de determinats grups.

Bibliografia

• Badea, Catalin «A theorem on irrationality of infinite series and applications». Acta Arithmetica, 63, 1993, pàg. 313–323.
• Badea, Catalin. «On some criteria for irrationality for series of positive rationals: a survey», 1995. Arxivat de l'original el 2008-09-11. [Consulta: 18 abril 2008].
• Boyer, Charles P.; Galicki, Krzysztof; Kollár, János «Einstein metrics on spheres». Annals of Mathematics, 162, 1, 2005, pàg. 557–580. arXiv:math.DG/0309408. MR 2178969
• Brenton, Lawrence and Hill, Richard «On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities». Pacific Journal of Mathematics, 133, 1, 1988, pàg. 41–67. MR 0936356.
• Brown, D. J «A lower bound for on-line one-dimensional bin packing algorithms». Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign, Tech. Rep. R-864, 1979.
• Curtiss, D. R. «On Kellogg's diophantine problem». American Mathematical Monthly, 29, 1922, pàg. 380–387.
• Domaratzki, Michael; Ellul, Keith; Shallit, Jeffrey; Wang, Ming-Wei «Non-uniqueness and radius of cyclic unary NFAs». International Journal of Foundations of Computer Science, 16, 5, 2005, pàg. 883–896. DOI: 10.1142/S0129054105003352. MR 2174328.
• Erdős, Paul; Graham, Ronald L. Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève, 1980. MR 0592420. 
• Galambos, Gábor; Woeginger, Gerhard J. «On-line bin packing — A restricted survey». Mathematical Methods of Operations Research, 42, 1, 1995. DOI: 10.1007/BF01415672. MR 1346486.
• Golomb, Solomon W. «On certain nonlinear recurring sequences». American Mathematical Monthly, 70, 4, 1963, pàg. 403–405. MR 0148605.
• Graham, R.; Knuth, D. E.; Patashnik, O.. Concrete Mathematics. 2a edició. Addison-Wesley, 1989, p. Exercise 4.37. ISBN 0-201-55802-5. 
• Jones, Rafe «The density of prime divisors in the arithmetic dynamics of quadratic polynomials». J. Lond. Math. Soc., 78, 2, 2008, pàg. 523-544. arXiv: math.NT/0612415. DOI: 10.1112/jlms/jdn034.
• Liang, Frank M. «A lower bound for on-line bin packing». Information Processing Letters, 10, 2, 1980, pàg. 76–79. DOI: 10.1016/S0020-0190(80)90077-0. MR 0564503.
• Miller, G. A. «Groups possessing a small number of sets of conjugate operators». Transactions of the American Mathematical Society, 20, 3, 1919, pàg. 260–270.
• Rosenman, Martin «Problem 3536». American Mathematical Monthly, 40, 3, 1933, pàg. 180.
• Salzer, H. E. «The approximation of numbers as sums of reciprocals». American Mathematical Monthly, 54, 3, 1947, pàg. 135–142. MR 0020339.
• Seiden, Steven S.; Woeginger, Gerhard J. «The two-dimensional cutting stock problem revisited». Mathematical Programming, 102, 3, 2005, pàg. 519–530. DOI: 10.1007/s10107-004-0548-1. MR 2136225.
• Sylvester, J. J. «On a point in the theory of vulgar fractions». American Journal of Mathematics, 3, 4, 1880, pàg. 332–335.
• Vardi, Ilan. Computational Recreations in Mathematica. Addison-Wesley, 1991, p. 82–89. ISBN 0-201-52989-0. 

Enllaços externs

• Irrationality of Quadratic Sums Arxivat 2000-05-16 a Wayback Machine., a les MathPages de K. S. Brown.
• Weisstein, Eric W., «Sylvester's Sequence» a MathWorld (en anglès).