# Greedy sequences without k-term arithmetic progressions

If $S_k$ is the greedy sequence with no length-k arithmetic subsequence, (ie $S_3$ = A003278 , $S_4$ = A005837 , $S_5$ = A020655 ), is it guaranteed that any other sequence $a$ with no length-k arithmetic subsequence has only terms which are $\ge$ those from $S_k$?

In other words, is it true that $\forall n, {S_k}_n \le a_n$ ? If not, can someone give a counterexample?

Also, which of these sequences are known to be small sets?

-
Already for $k=3$ this must fail eventually, because the $n$-th term grows roughly as $n^{\log_2 3}$ (e.g. the $2^k$-th term is $(3^k+1)/2$), but it's known that for large $n$ there are 3AP-avoiding sets of size $n$ in $\lbrace 1, 2, 3, \ldots, n^{1+\epsilon} \rbrace$.  P.S. I see that a variation of this was asked here in 2011 but not answered: mathoverflow.net/questions/80085 –  Noam D. Elkies Jul 2 '13 at 3:25
Could you give an example of such a set? –  dspyz Jul 2 '13 at 3:46
Behrend's construction for $n^{1+\epsilon}$ is explicit but somewhat complicated, and probably takes some time to improve on A003278. However, the big jump from $14$ to $28$ between terms $8$ and $9$ in the greedy sequence suggests that this is a good place to look, and indeed it turns out that the narrowest AP3-free set of size $9$ is $\lbrace 1, 2, 6, 7, 9, 14, 15, 18, 20 \rbrace$ (unique up to reflection, by an exhaustive search that took much longer to program in C and debug than the fraction of a second it took to run). –  Noam D. Elkies Jul 2 '13 at 4:12
(O.O.)P.S. I would have saved some time by first finding oeis.org/A065825 ... –  Noam D. Elkies Jul 2 '13 at 4:14
... or even trying the $n=5$ jump first! ($\lbrace 1, 2, 4, 8, 9 \rbrace$, $\lbrace 1, 3, 4, 8, 9 \rbrace$) –  Noam D. Elkies Jul 2 '13 at 4:30