Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 --- 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
up vote 3 down vote accepted

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

share|cite|improve this answer
Sweet, I finally understand enough to ask an unsolved problem ;) – Joseph Garvin Dec 4 '12 at 23:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.