5
$\begingroup$

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.

  • 0
    @GerryMyerson: Oops, I misread the number on yours and thought it was different. And good point :P2012-12-06

1 Answers 1

3

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$.

  • 0
    Sweet, I finally understand enough to ask an unsolved problem ;)2012-12-04