# Largest subset of { 0, 1, 2, …, n } that has no 3+ element arithmetic progressions?

Out of all the subsets of $\lbrace 0, 1, 2, ..., n \rbrace$ for some given $n$, how do I compute the size of the largest subset that has no arithmetic progressions with 3 or more elements?

I suspect this may be a well researched problem but I can't seem to divine the appropriate search terms.

-
Small terms are shown in OEIS –  Ross Millikan Dec 4 '12 at 23:06
@Ross, I think that's a little different. That's an infinite sequence with no 3-term AP, constructed greedily. But it may be that for various $n$ you can do better than an initial segment of the greedy sequence. –  Gerry Myerson Dec 4 '12 at 23:13
A better OEIS reference is oeis.org/A003002 --- also, see the discussion at E10 in Guy, Unsolved Problems In Number Theory, 3rd ed. –  Gerry Myerson Dec 4 '12 at 23:17
@GerryMyerson: I hadn't noticed. Thanks. It may still be useful. A003003 has the largest subset without a 4 term progression. –  Ross Millikan Dec 4 '12 at 23:18
I'm glad you found the link I posted. If there's no progression with 3 terms, then there's no progression with 3 or more terms. –  Gerry Myerson Dec 6 '12 at 5:46

This is related to Szemerédi's theorem. For progressions of length 3, look at a result by Roth. The Wikipedia page suggests that the best known bound is $$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$.