Sucesión de Sylvester

En teoría de números, la sucesión de Sylvester es una sucesión de números enteros en la cual cada término es el producto de todos los anteriores, más uno. Los primeros términos de la sucesión son:

Demostración gráfica de la convergencia de la suma a 1. Cada fila de k cuadrados de lado tiene un área total de , y todos los cuadrados juntos cubren de forma exacta un cuadrado mayor de área 1. Los cuadrados de lado o menor son demasiado pequeños como para poder verse en la ilustración, y por tanto no se muestran.
2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 A000058.

La sucesión de Sylvester se llama así en honor de James Joseph Sylvester, quien la investigó por primera vez en 1880. Sus términos crecen de forma doblemente exponencial, y la suma de sus inversos constituye una serie de fracciones unitarias que converge a 1 más rápidamente que ninguna otra serie de fracciones unitarias con la misma suma. La manera en que se define permite que sus términos se factoricen más fácilmente que otros números del mismo orden de magnitud, pero, debido al ritmo de crecimiento de los mismos, sólo se conoce la factorización completa en factores primos de unos pocos términos. Los términos de esta sucesión también han tenido usos en la representación finita de fracciones egipcias de suma 1, así como en las variedades sasakianas y las de Einstein.

Definiciones formales editar

Formalmente, la sucesión de Sylvester se puede definir mediante la fórmula

 

El producto de un conjunto vacío es 1, por tanto, s0 = 2.

Alternativamente, se puede definir la sucesión por recurrencia como

  con s0 = 2.

Se puede demostrar por inducción que las dos definiciones son equivalentes.

Relación con las fracciones egipcias editar

Las fracciones unitarias generadas por los inversos de los términos de la sucesión de Sylvester generan una serie:

 

Las sumas parciales de esta serie tienen una forma simple,

 

como se puede probar por inducción. Obviamente esta identidad es cierta para j = 0, ya que los dos miembros son cero. Para un j mayor, al expandir el miembro izquierdo de la identidad mediante la hipótesis de inducción se obtiene

 

como se quería demostrar. Como esta sucesión de sumas parciales (sj-2)/(sj-1) converge a uno, la serie global forma una representación infinita en fracción egipcia de la unidad:

 

Se pueden encontrar representaciones finitas en forma de fracción egipcia de la unidad, de cualquier longitud, truncando esta serie y restando uno del último denominador:

 

La suma de los k primeros términos de la serie infinita proporciona la mejor aproximación a 1 por la izquierda de una fracción egipcia arbitraria de k términos.[1]​ Por ejemplo, los cuatro primeros términos suman  , y por tanto cualquier fracción egipcia de un número perteneciente al intervalo abierto ( , 1) requiere al menos cinco términos.

Se puede considerar la sucesión de Sylvester como un algoritmo voraz para fracciones egipcias que en cada paso escoge el mínimo denominador posible que haga que la suma parcial de la serie sea menor que uno. Además, si se exceptúa el primer término, los demás se pueden ver como los denominadores de la expansión voraz impar de  .

Fórmula en forma cerrada y asíntotas editar

La sucesión de Sylvester crece de forma doblemente exponencial como función de n. Concretamente, se puede mostrar que

 

para un número E que vale aproximadamente 1,264.[2]​ De esta fórmula se deriva el siguiente algoritmo:

s0 es el entero más próximo a E2; s1 es el entero más próximo a E4; s2 es el entero más próximo a E8; para sn, tome E2, elévelo al cuadrado n veces, y tome el entero más próximo.

Este algoritmo sólo tendría un uso práctico si hubiese una forma mejor de calcular E con la precisión requerida en lugar de calcular sn y tomar repetidamente su raíz cuadrada.

El crecimiento doblemente exponencial de la sucesión de Sylvester no resulta sorprendente si se compara con la de los números de Fermat Fn, ya que los números de Fermat se suelen definir mediante una fórmula doblemente exponencial,  , pero también se pueden definir de una forma muy similar a la que define la sucesión de Sylvester:

 

Unicidad de la serie de crecimiento rápido con sumas racionales editar

Como el mismo Sylvester observó, la sucesión de Sylvester parece ser única en mostrar crecimiento tan rápido de sus términos, a la vez que la suma de sus inversos coverge a un número racional.

Más precisamente, es una consecuencia de los resultados de Badea (1993) que, si una sucesión de enteros   crece lo suficientemente rápido como para que

 

y si la serie

 

converge a un número racional A, entonces, para cada n después de cierto punto, esta sucesión debe estar definida por la misma recurrencia

 

que se emplea para definir la sucesión de Sylvester.

Erdős (1980) conjeturó que, para este tipo de resultados, la desigualdad matemática que acota el crecimiento de la sucesión se podría reemplazar por una condición más débil,

 

Badea (1995) estudia los progresos relacionados con esta conjetura, véase también Brown.

Divisibilidad y factorización editar

Si i < j, entonces se sigue de la definición que sj ≡ 1 (mod si). Por tanto, dos términos cualesquiera de la sucesión de Sylvester son primos entre sí. Esta sucesión se puede utilizar para demostrar que existen infinitos números primos, ya que cada uno de los números primos puede dividir a lo sumo uno de los términos de la sucesión.

Se ha realizado algún esfuerzo para factorizar los términos de la sucesión de Sylvester, pero quedan muchas incógnitas sobre su factorización. Por ejemplo, no se sabe si todos los términos de la sucesión son libres de cuadrados, aunque todos los que se conocen lo son.

Como Vardi (1991) describe, es fácil determinar a qué número de Sylvester (si es que hay alguno) divide un número primo p dado: basta con calcular la recurrencia que define la sucesión módulo p hasta encontrar, bien un número congruente con cero (mod p) o un módulo repetido. Mediante esta técnica, descubrió que 1166 de los primeros tres millones de primos son divisores de números de Sylvester,[3]​ y que ninguno de ellos tiene un cuadrado que divida a un número de Sylvester. Un resultado general de Jones (2006) implica que el conjunto de factores primos de Sylvester tiene densidad cero en el conjunto de los primos.

La siguiente tabla muestra la factorización de estos números (excepto los cuatro primeros, que son primos) hasta donde se conoce:[4]

n Factores de sn
4 13 × 139
5 3263443, que es primo
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

Pn y Cn denotan, respectivamente, números primos y compuestos, de n cifras.

Aplicaciones editar

Boyer et al. (2005) se valen de las propiedades de la sucesión de Sylvester para definir números grandes de variedades de Einstein-Sasaki que tienen la topología diferecial de esferas o esferas exóticas de dimensión impar. Demuestran que el número de métricas de Einstein-Sasaki sobre una esfera topológica de dimensión 2n - 1 es al menos proporcional a sn y por tanto sigue un crecimiento doblemente exponencial en función de n.

Como describen Galambos y Woeginger (1995), Brown (1979) y Liang (1980) emplean valores derivados de la sucesión de Sylvester para construir ejemplos de cota inferior de algoritmos de bin packing en línea. Seiden y Woeginger (2005) también se valen de la sucesión para acotar inferiormente el rendimiento de un algoritmo cutting stock bidimensional.[5]

El problema de Znám se refiere a conjuntos de números tales que cada número de ese conjunto divide pero no es igual al producto de todos los demás más uno. Sin el requisito de la desigualdad, los valores de la sucesión de Sylvester resolverían el problema, pero con ese requisito tiene otras soluciones que se derivan de recurrencias similares a la que define la sucesión de Sylvester. Las soluciones del problema de Znám tienen aplicaciones en la clasificación de singularidades de superficies (Brenton y Hill, 1988) y en la teoría de los autómatas finitos no determinísticos (Domaratzki et al. 2005).

Curtiss (1922) describe una aplicación de las aproximaciones más próximas a uno por sumas de k términos de fracciones unitarias, para acotar inferiormente del número de divisores de cualquier número perfecto, y Miller (1919) usa la misma propiedad para acotar inferiormente el tamaño de ciertos grupos.

Véase también editar

Notas editar

  1. Esta afirmación se suele atribuir a Curtiss (1922), pero Miller (1919) parece hacer la misma afirmación en un trabajo anterior. Véase también Rosenman (1933), Salzer (1947) y Soundararajan (2005).
  2. Graham, Knuth y Patashnik (1989) lo proponen a modo de ejercicio, véase también Golomb (1963).
  3. Esto parece ser un error tipográfico, ya que Andersen encontró 1167 divisores primos en este rango.
  4. Todos los factores primos p de números de Sylvester sn con p < 5×107 y n ≤ 200 están catalogados por Vardi. Ken Takusagawa enumera las sucesivas factorizaciones hasta s9 y la factorización de s10. Las factorizaciones restantes están en una lista de factorizaciones de la sucesión de Sylvester mantenida por Jens Kruse Andersen, consultada el 2 de octubre de 2007.
  5. En su trabajo, Seiden y Woeginger se refieren a la sucesión de Sylvester como "sucesión de Salzer" debido al trabajo de este en 1947.

Referencias editar

  • Badea, Catalin (1993). «A theorem on irrationality of infinite series and applications». Acta Arithmetica 63: 313-323. MR 1218459. 
  • Brown, D. J. (1979). A lower bound for on-line one-dimensional bin packing algorithms. Tech. Rep. R-864. Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign. 
  • Erdős, Paul and Graham, Ronald L. (1980). Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève. MR 0592420. 
  • Galambos, Gábor; Woeginger, Gerhard J. (1995). «On-line bin packing — A restricted survey». Mathematical Methods of Operations Research 42 (1). doi:10.1007/BF01415672. MR 1346486. 
  • Seiden, Steven S.; Woeginger, Gerhard J. (2005). «The two-dimensional cutting stock problem revisited». Mathematical Programming 102 (3): 519-530. doi:10.1007/s10107-004-0548-1. MR 2136225. 
  • Vardi, Ilan (1991). Computational Recreations in Mathematica. Addison-Wesley. pp. 82-89. ISBN 0-201-52989-0.