¿Es posible demostrar que cada subsecuencia de longitud 33 de la secuencia $1,2,3,\dotsc,122$ contiene una progresión aritmética de tres términos?
Tal vez debería publicarlo en mathoverflow
Respuestas
¿Demasiados anuncios?
A Walker
Puntos
4804
Esto no es una respuesta, pero me gustaría dirigirte a OEIS A065825.
Esta secuencia, que comienza
$$S_3=\{1, 2, 4, 5, 9, 11, 13, 14, 20, 24, 26, 30, 32, 36, 40, 41, 51, 54, 58, 63, 71, 74, 82, 84, 92, 95, 100, 104, 111, 114, 121, 122, 137, 145, 150, 157, 163, 165, 169, 174, 194\}$$ da por su $n$ el plazo mínimo $k$ tal que $[1,k]$ que tiene un $n$ -que evite $3$ -progresiones aritméticas de término (típicamente llamadas $3$ -conjunto libre). Dado que el $32$ término de esta secuencia es $122$ y el $33$ rd es $137$ se deduce que no $33$ secuencia de términos en $[1,122]$ es $3$ -libre. No se sabe mucho sobre el crecimiento de esta secuencia, y no me sorprendería que la secuencia anterior se hubiera encontrado mediante cálculos de fuerza bruta.
En un momento dado se conjeturó que la secuencia $G_3=\{1,2,4,5,10,\ldots\}$ (es decir, la secuencia obtenida añadiendo siempre el elemento más pequeño que conserva $3$ -), se obtendrían límites competitivos para $S_3$ infinitamente a menudo. Esto fue refutado por el trabajo de F. Behrend en 1946, quien elaboró ejemplos de $3$ -conjuntos libres de longitud $n$ que encajan en el intervalo $n^{1+\epsilon}$ (para los fijos $\epsilon >0$ y suficientemente grande $n$ ). En cambio, podemos demostrar que la versión "codiciosa" de este empaquetamiento requiere un espacio como $$n^{\log_2 3},$$ reconociéndolo como el conjunto de enteros cuya base $3$ representación omite el dígito $2$ , incrementado en $1$ .
Permítanme añadir algunos comentarios a Alexander Walker bonita respuesta:
El problema es estudiado por primera vez en el papel
Paul Erdős, y Pablo Frigyes. En algunas secuencias de números enteros, J. Londres Matemáticas. Soc., 11 (4), (1936), 261--264. MR1574918, Zentralblatt JFM 62.1126.01.
No $r(n)$ se define como la longitud de los más grandes de la secuencia de elementos de $\{1,\dots,n\}$ sin tres términos en una progresión aritmética. Una conjetura por Szekeres, se menciona que $$r\left(\frac12(3^k+1)\right)=2^k.$$ Esto puede ser verificado más o menos directamente por $k\le 4$. Tenga en cuenta que para $k=5$ nos da el resultado que usted solicitó. El documento menciona que $\displaystyle r\left(\frac12(3^k+1)\right)\ge 2^k$ es fácil de ver: Dado $k$, vamos a $A$ el conjunto de los enteros de la forma $u+1$ $\displaystyle 0\le u\le \frac12(3^k-1)$ y de tal manera que el ternario de expansión de $u$ no tiene pareja. Vemos entonces que el $A$ tiene el tamaño de $2^k$ y no hay tres términos están en progresión aritmética. Para $k=5$, lo $N=122$, el conjunto resultante $A$ tiene el tamaño de $32$ y es igual a $$\begin{array}{c}\{1,2,4,5,10,11,13,14,28,29,31,32,37,38,40,41,82,83,85,86,91,92,94,95,109,110,\\ 112,113,118,119,121,122\}.\end{array} $$ Esto significa que $33$ puede ser reemplazado con un número menor.
El papel (también se menciona en los comentarios)
Janusz Dybizbański. Secuencias Que Contienen No 3-Plazo De Progresiones Aritméticas, De Electrones. J. Combinat., 19 (2), (2012), documento de 15, 5 pp. MR2928630,
establece un resultado que, por primera vez, se comprueba que Szekeres conjetura tiene por $k=5$. El argumento que utiliza un equipo de búsqueda, y ningún equipo libre de enfoque combinatorio parece conocido en el momento.
Como Walker señaló en un comentario, cabe señalar que Szekeres la conjetura es en realidad falsa. El punto es que ahora tenemos una buena comprensión para el comportamiento asintótico de la función $r$, lo que choca con lo que la hipótesis se predice. En concreto, sabemos que para cualquier $\epsilon>0$, hay constantes $c,C>0$ tal que para $N$ lo suficientemente grande, tenemos $$ cN^{1-\epsilon}<r(N)<CN^{1-\epsilon}. $$ Por ejemplo, en
Tom Sanders. En Roth teorema sobre progresiones, Ann. de Matemáticas. (2), 174 (1), (2011), 619-636. MR2811612 (2012f:11019),
está demostrado que para algunas $C$, $$r(N)<C\frac{(\log\log N)^5}{\log N}N,$$ mientras que (más relevante para nuestra discusión actual), en
Félix Adalberto Behrend. En los conjuntos de números enteros que no contienen tres términos en progresión aritmética, Proc. Nat. Acad. Sci. U. S. A., De 32, (1946), 331-332. MR0018694 (8,317 d),
está demostrado que para algunas $c$, $$ r(N)>N^{1-\frac{c}{\sqrt{\log N}}}. $$ Para $N$ grande, esta desigualdad enfrentamientos con el valor predicho por Szekeres conjetura, que le da ese $r(N)\le C'N^{\log_32}$ $N$ de la forma $\displaystyle\frac12(3^k+1)$.
(En realidad, la primera refutación de Szekeres la conjetura es mucho mayor que la anterior sugiere: En
Raphaël Salem, y Donald C. Spencer. En los conjuntos de números enteros que no contienen tres términos en progresión aritmética, Proc. Nat. Acad. Sci. U. S. A., 28 (12), (1942), 561-563. MR0007405 (4,131 e),
se muestra que para cualquier $\epsilon>0$, $$ r(n)\ge n^{1-\frac{1+\epsilon}{\log\log n}}$$ for all $$ n suficientemente grande.)
Como Walker señala además en los comentarios, Jaroslaw Wroblewski ha organizado una búsqueda de conjuntos sin $3$plazo progresiones aritméticas, que en particular se ha encontrado un ejemplo de la longitud de la $128$$\{1,2,\dots,1092\}$, por lo tanto refutando Szekeres conjetura para $k=7$. Este, y los otros resultados de su búsqueda, se puede ver en esta página (la búsqueda de $a(128)$). Parece que si la hipótesis se cumple para $k=6$ todavía está abierta.
Para un buen estudio de los resultados conocidos en sets sin plazo de tres progresiones aritméticas, ver
William Gasarch, James Glenn, y Clyde P. Kruskal. Encontrar Grandes Conjuntos Sin Progresiones Aritméticas de Longitud Tres: Una Empírica de la Vista y de la Encuesta. II, 2010, preprint.
