Sucesión de Sylvester

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

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

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

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

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

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

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

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

Las sumas parciales de esta serie tienen una forma simple,

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

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

${\displaystyle \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}},}$

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

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

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:

${\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 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 ${\displaystyle {\tfrac {1805}{1806}}}$, y por tanto cualquier fracción egipcia de un número perteneciente al intervalo abierto (${\displaystyle {\tfrac {1805}{1806}}}$, 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 ${\displaystyle {\tfrac {1}{2}}}$.

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

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

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

s₀ es el entero más próximo a E²; s₁ es el entero más próximo a E⁴; s₂ es el entero más próximo a E⁸; para s_n, tome E², 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 s_n 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 F_n, ya que los números de Fermat se suelen definir mediante una fórmula doblemente exponencial, ${\displaystyle 2^{2^{n}}+1}$, pero también se pueden definir de una forma muy similar a la que define la sucesión de Sylvester:

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

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 ${\displaystyle a_{n}}$ crece lo suficientemente rápido como para que

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

y si la serie

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

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

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

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,

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

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

Si i < j, entonces se sigue de la definición que s_j ≡ 1 (mod s_i). 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]

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

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

• Constante de Cahen
• Número pseudoperfecto primario