1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Noam D. Elkies
    Commented Jul 2, 2013 at 3:25
  • $\begingroup$ Could you give an example of such a set? $\endgroup$
    – dspyz
    Commented Jul 2, 2013 at 3:46
  • 2
    $\begingroup$ 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). $\endgroup$
    – Noam D. Elkies
    Commented Jul 2, 2013 at 4:12
  • 1
    $\begingroup$ (O.O.)P.S. I would have saved some time by first finding oeis.org/A065825 ... $\endgroup$
    – Noam D. Elkies
    Commented Jul 2, 2013 at 4:14
  • $\begingroup$ ... or even trying the $n=5$ jump first! ($\lbrace 1, 2, 4, 8, 9 \rbrace$, $\lbrace 1, 3, 4, 8, 9 \rbrace$) $\endgroup$
    – Noam D. Elkies
    Commented Jul 2, 2013 at 4:30

0

Reset to default

You must log in to answer this question.