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.

  • 1
    Small terms are shown in [OEIS](http://oeis.org/A003278)2012-12-04
  • 0
    @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.2012-12-04
  • 2
    A better OEIS reference is http://oeis.org/A003002 --- also, see the discussion at E10 in Guy, Unsolved Problems In Number Theory, 3rd ed.2012-12-04
  • 0
    @GerryMyerson: I hadn't noticed. Thanks. It may still be useful. [A003003](http://oeis.org/A003003) has the largest subset without a 4 term progression.2012-12-04
  • 0
    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.2012-12-06
  • 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