MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Everyone knows about the problem of finding the largest set in 1,2,...,N which contains no arithmetic progression of length 3.....what happens if we look at the set which is the smallest maximal subset of 1,...,N which contains no 3-AP?

Obviously we have a square root lower bound using a greedy argument and a simple upper bound, with exponent log(2)/log(3), by looking at integers with no 2 in their base 3 representation. Is anything better known, in either direction? I know about the original work of Stanley and Odlyzko.......

share|cite|improve this question
An example of a set without 3-AP will be an upper bound for "smallest maximal subset", where maximal means no other numbers can be added without forming a 3-AP. For example, if $N=10$, then $\\{1,3,4,9,10\\}$ is a set with no 3-AP, and is also maximal, but it is not the smallest such set. $\\{2,3,5,6\\}$ has $4$ members, which is minimal, since $3$ elements can only form $6$ progressions (two for each pair), so at least one more element can be added. – Zack Wolske Nov 5 '11 at 7:25
Forgot about $2$ terms being on both ends of a progression, so really they may form $9$ progressions, and that's a bad example. A better choice is N=13, where there is a set of size 7 with no progressions, but the smallest maximal set is $'\\{3,5,8,10\\}'$, and this time a set of $3$ elements can't be maximal, by the above argument. – Zack Wolske Nov 5 '11 at 7:40
To which work(s) of Stanley and Odlyzko are you referring? – Kevin O'Bryant Nov 6 '11 at 2:50
Kevin, here's a link to the work that Odlyzko and Stanley did on greedy sequences: Also, Odlyzko has some comments here on later work. There is also a couple of articles in Discrete Mathematics, one by Erods and coauthors, which are relevant. I've been thinking about this topic on and off over the past few days and may write up what little I have. – Mike Nov 6 '11 at 16:25

Your Answer


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

Browse other questions tagged or ask your own question.