Mayor subconjunto de { 0, 1, 2, ..., n } que no tiene 3+ elemento progresiones aritméticas?

Question

De todos los subconjuntos de a $\lbrace 0, 1, 2, ..., n \rbrace$ para un determinado$n$, ¿cómo puedo calcular el tamaño del subconjunto más grande que no tiene progresiones aritméticas con 3 o más elementos?

Sospecho que esto puede ser un bien investigado problema, pero me parece que no puede divino apropiado de los términos de búsqueda.

Answer 1

Esto está relacionado con el teorema de Szemerédi. Para las progresiones de longitud 3, mira un resultado por Roth. La página de la Wikipedia sugiere que la mejor conocida es obligado $$O\left(\frac{n (\log\log n)^5}{\log n}\right)$$ I don't think exact values are known except for small values of $$n.