8
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Zack Wolske
    Commented Nov 5, 2011 at 7:25
  • $\begingroup$ 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. $\endgroup$
    – Zack Wolske
    Commented Nov 5, 2011 at 7:40
  • $\begingroup$ To which work(s) of Stanley and Odlyzko are you referring? $\endgroup$
    – Kevin O'Bryant
    Commented Nov 6, 2011 at 2:50
  • $\begingroup$ Kevin, here's a link to the work that Odlyzko and Stanley did on greedy sequences: dtc.umn.edu/~odlyzko/unpublished 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. $\endgroup$
    – Mike
    Commented Nov 6, 2011 at 16:25

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .