Secuencia de Stanley

En matemáticas, una secuencia de Stanley es una secuencia de enteros generada por un algoritmo voraz que elige los miembros de la secuencia para evitar progresiones aritméticas . Si es un conjunto finito de enteros no negativos en el que ningún par de elementos forma una progresión aritmética (es decir, un conjunto de Salem-Spencer ), entonces la secuencia de Stanley generada a partir de comienza con los elementos de , en orden ascendente, y luego elige repetidamente cada elemento sucesivo de la secuencia para que sea un número mayor que los números ya elegidos y que no forme ninguna progresión aritmética de tres términos con ellos. Estas secuencias reciben su nombre de Richard P. Stanley .${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

La secuencia de Stanley que comienza desde el conjunto vacío consiste en aquellos números cuyas representaciones ternarias tienen solo los dígitos 0 y 1. ^{[ 1 ]} Es decir, cuando se escriben en ternario, parecen números binarios . Estos números son

0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, ... (secuencia A005836 en el OEIS )

Por su construcción como secuencia de Stanley, esta secuencia es la primera secuencia libre de progresión aritmética lexicográficamente . Sus elementos son las sumas de distintas potencias de tres , los números tales que el -ésimo coeficiente binomial central es 1 mod 3, y los números cuya representación ternaria balanceada es la misma que su representación ternaria. ^{[ 2 ]}${\displaystyle n}$${\displaystyle n}$

La construcción de esta secuencia a partir de los números ternarios es análoga a la construcción de la secuencia de Moser-de Bruijn , la secuencia de números cuyas representaciones en base 4 tienen solo los dígitos 0 y 1, y a la construcción del conjunto de Cantor como el subconjunto de números reales en el intervalo cuyas representaciones ternarias usan solo los dígitos 0 y 2. De manera más general, son una secuencia 2-regular , una de una clase de secuencias de enteros definidas por una relación de recurrencia lineal con multiplicador 2. ^{[ 3 ]}${\displaystyle [0,1]}$

Esta secuencia incluye tres potencias de dos : 1, 4 y 256 = 3⁵ ⁺ 3² ⁺ 3 + 1. Paul Erdős conjeturó que estas son las únicas potencias de dos que contiene. ^{[ 4 ]}

Andrew Odlyzko y Richard P. Stanley observaron que el número de elementos hasta cierto umbral en la secuencia binaria-ternaria, y en otras secuencias de Stanley que comienzan desde o , crece proporcionalmente a . Para otros conjuntos iniciales, las secuencias de Stanley que consideraron parecían crecer de forma más errática pero aún más dispersa. ^{[ 1 ]} Por ejemplo, el primer caso irregular es , que genera la secuencia${\displaystyle n}$${\displaystyle \{0,3^{k}\}}$${\displaystyle \{0,2\cdot 3^{k}\}}$${\displaystyle n^{\log _{2}3}\approx n^{0.631}}$${\displaystyle \{0,s\}}$${\displaystyle s=4}$

0, 4, 5, 7, 11, 12, 16, 23, 26, 31, 33, 37, 38, 44, 49, 56, 73, 78, 80, 85, 95, 99, ... (secuencia A005487 en el OEIS )

Odlyzko y Stanley conjeturaron que en tales casos el número de elementos hasta cualquier umbral es . Es decir, existe una dicotomía en la tasa de crecimiento de las secuencias de Stanley entre aquellas con un crecimiento similar a la secuencia binaria-ternaria y otras con una tasa de crecimiento mucho menor; según esta conjetura, no debería haber secuencias de Stanley con crecimiento intermedio. ^{[ 1 ] [ 5 ]}${\displaystyle n}$${\displaystyle O{\bigl (}{\sqrt {n\log n}}{\bigr )}}$

Moy demostró que las secuencias de Stanley no pueden crecer significativamente más lentamente que el límite conjeturado para las secuencias de crecimiento lento. Cada secuencia de Stanley tiene elementos hasta . Más precisamente, Moy demostró que, para cada una de estas secuencias, para cada , y para todos los suficientemente grandes , el número de elementos es al menos . ^{[ 6 ]} De manera similar, Dai y Chen demostraron que el número de elementos es al menos para infinitos . ^{[ 7 ]} Rolnick y Venkataramana también demostraron que para las secuencias de Stanley que crecen como el factor constante en sus tasas de crecimiento puede ser cualquier número racional cuyo denominador sea una potencia de tres. ^{[ 8 ]}${\displaystyle \Omega {\bigl (}{\sqrt {n}}{\bigr )}}$${\displaystyle n}$${\displaystyle \varepsilon >0}$${\displaystyle n}$${\displaystyle ({\sqrt {2}}-\varepsilon ){\sqrt {n}}}$${\displaystyle 1.77{\sqrt {n}}}$${\displaystyle n}$${\displaystyle n^{\log _{2}3}}$

En 1936, Paul Erdős y Pál Turán consideraron una variación de la secuencia binaria-ternaria (con uno añadido a cada elemento) , observando que no tiene progresión aritmética de tres términos y conjeturando (incorrectamente) que era la secuencia más densa posible sin progresión aritmética. ^{[ 9 ]}

En un trabajo inédito realizado con Andrew Odlyzko en 1978, Richard P. Stanley experimentó con el algoritmo voraz para generar secuencias libres de progresión. Las secuencias que estudiaron fueron exactamente las secuencias de Stanley para los conjuntos iniciales . ^{[ 1 ]}${\displaystyle \{0,s\}}$

Las secuencias de Stanley fueron nombradas y generalizadas a otros conjuntos iniciales distintos de , en un artículo publicado en 1999 por Erdős (póstumamente) con otros cuatro autores. ^{[ 5 ]}${\displaystyle \{0,s\}}$

• Moy, Richard A. (2017), Secuencias de Stanley con carácter impar , arXiv : 1707.02037
• Moy, Richard A.; Rolnick, David (2016), "Nuevas estructuras en secuencias de Stanley", Matemáticas Discretas , 339 (2): 689– 698, arXiv : 1502.06013 , doi : 10.1016/j.disc.2015.10.017 , MR 3431382 , S2CID 6660477  
• Rolnick, David (2017), "Sobre la clasificación de secuencias de Stanley", European Journal of Combinatorics , 59 : 51–70 , arXiv : 1408.1940 , doi : 10.1016/j.ejc.2016.06.004 , MR 3546902 
• Sawhney, Mehtaab (2017), Valores de caracteres de secuencias de Stanley , arXiv : 1706.05444