Que nos llame a un conjunto $S$ de los enteros escasa si para cualquiera de los cuatro enteros $a,b,c,d \in S$ tal que $a<b<c<d$,$a+d \ne b+c$. Definir $P(n)$ a ser máxima tamaño de una escasa subconjunto de $\{1,2,\dotsc,n\}$. Es cierto que $\lim\limits_{n\to \infty} P(n)/n=0$?
Respuestas
¿Demasiados anuncios?
bof
Puntos
19273
Sí, es cierto. Se sigue de (la finitary versión de Szemerédi del teorema: si un conjunto a $A\subseteq\mathbb N$ ha positiva superior de densidad, a continuación, para cada entero positivo $k$ contiene una progresión aritmética de longitud $k;$ ver Endre Szemerédi, En los conjuntos de enteros que contiene no $k$ elementos de una progresión aritmética, el Acta Arithmetica 27 (1975), 199-245. El caso de $k=4$ fue demostrado anteriormente: Endre Szemerédi, En conjuntos de números enteros que no contiene cuatro elementos en una progresión aritmética, el Acta de Matemáticas. Acad. Sci. Hungar. 20 (1969), 89-104. (Por supuesto, una "escasa" contiene ninguna progresión aritmética de longitud $4.$)
mjqxxxx
Puntos
22955
He aquí un explícito, más apretado obligado para el tamaño de un conjunto disperso. Si $A\subseteq \{1,2,\ldots,n\}$ es escasa, entonces cada par de elementos distintos de a $A$ tiene una cantidad distinta. Hay $\Theta(|A|^2)$ pares de elementos distintos, pero sólo $O(n)$ diferentes sumas de dinero que se puede tener. Por el principio del palomar llegamos a la conclusión de que $|A|$$O(\sqrt{n})$, y, por tanto,$|A|/n$$O(1/\sqrt{n})$.
