Timeline for Greedy sequences without k-term arithmetic progressions
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 2, 2013 at 16:53 | comment | added | dspyz | Thanks, So does this imply that en.wikipedia.org/wiki/… could potentially be undecidable or equivalent to AC or something like that? | |
| Jul 2, 2013 at 4:30 | comment | added | Noam D. Elkies | ... or even trying the $n=5$ jump first! ($\lbrace 1, 2, 4, 8, 9 \rbrace$, $\lbrace 1, 3, 4, 8, 9 \rbrace$) | |
| Jul 2, 2013 at 4:14 | comment | added | Noam D. Elkies | (O.O.)P.S. I would have saved some time by first finding oeis.org/A065825 ... | |
| Jul 2, 2013 at 4:12 | comment | added | Noam D. Elkies | 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). | |
| Jul 2, 2013 at 3:46 | comment | added | dspyz | Could you give an example of such a set? | |
| Jul 2, 2013 at 3:25 | comment | added | Noam D. Elkies | 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 | |
| Jul 2, 2013 at 3:13 | history | asked | dspyz | CC BY-SA 3.0 |