5

Question:

Let set $A=\{1,2,\cdots,100\}$ ,find the least $k$ such that any subset of order $k$ contains 4 terms in arithmetic progression.

It seem interesting problem.

Now I have found $k$ must $k\ge 43$,because I found following set has $42$ elements and contains no 4 terms in arithmetic progression. take$$\{1,3,6,7,9,10,14,16,17,19,20,21,26,27,29,30,33,34,35,47,50,52,53,54,57,58,59,63,64,66,72,77,80,83,87,89,90,92,96,97,98,100\}.$$ so I think $k\ge 43$?

math110
  • 93,304
  • What? You should really reformulate your problem, in the current version $k=4$ would be the smallest, but it is not an interesting problem at all... – Dirk Apr 07 '17 at 11:19
  • @Bernie I decided (i.e. "guessed") that the OP means: find the least $k$ such that ANY subset of order $k$ contains $4$ terms in arithmetic progression. Of course, we should get confirmation on that. – lulu Apr 07 '17 at 11:20
  • @lulu In this case you still have $k=4$. As soon as we have 5 or more elements, we can always pick $a,b,c,d,e$ ordered increasingly. As $a,b,c,d$ have to be a progression and $b,c,d,e$ has to be one, $a,b,c,e$ will not work. So even with your guess, it is still not interesting at all... – Dirk Apr 07 '17 at 11:23
  • @Bemte No...the subset ${1,2,3,5}$ does not have four elements in progression. So we know that $k_{min}>4$ (with my definition). Similarly ${1,2,3,5,6,7}$ shows that $k_{min}>6$ and ${1,2,3,5,6,7,94,95,96,98,99,100}$ shows that $k_{min}>12$ Finding $k_{min}$ in this context seems like a real question. – lulu Apr 07 '17 at 11:27
  • @lulu Ah, this is how you mean it, ok. You are right, seeing it this way it might be a little bit more interesting. – Dirk Apr 07 '17 at 11:32
  • @lulu,yes, you mean is right. – math110 Apr 07 '17 at 11:43
  • 2
    Probably a hard problem. Where did it come up, please? – Gerry Myerson Apr 07 '17 at 12:37
  • The set $\lbrace 1, 2, 4, 5, 7, 8, 9, 14, 15, 17, 18, 23, 24, 26, 27, 28, 45, 46, 47, 49, 52, 53, 56, 58, 59, 61, 73, 74, 75, 80, 81, 83, 84, 90, 91, 92, 95, 96, 98, 100 \rbrace$ has 40 elements and contains no $4$ terms in arithmetic progression, so $k_{min} \geq 41$. – Ewan Delanoy Apr 07 '17 at 15:19
  • Any reaction to my answer, function? – Gerry Myerson Apr 11 '17 at 12:48
  • @GerryMyerson,I think $41$ is not answer.I have found $k=42$ such, – math110 Apr 20 '17 at 04:25
  • OK, but that's not exactly a reaction to my answer. Have you looked at any of the references I gave? Have you found them to be at all helpful? – Gerry Myerson Apr 20 '17 at 07:11
  • By "subset of order $k$" I guess you mean a $k$-element subset? – bof Apr 20 '17 at 09:06
  • HAVE YOU LOOKED AT ANY OF THE REFERENCES I GAVE? HAVE YOU FOUND THEM TO BE AT ALL HELPFUL? – Gerry Myerson Apr 22 '17 at 13:43
  • Here's an idea: – Franklin Pezzuti Dyer Apr 26 '17 at 19:59

1 Answers1

2

There is some discussion of this in Guy, Unsolved Problems in Number Theory, 3rd edition, section E10 (I found the following at https://books.google.com.au/books?id=t_3lBwAAQBAJ&pg=PA113&lpg=PA113&dq=%22introduced+long+years+ago+by%22&source=bl&ots=xXUDWLeUSX&sig=Wk_o0Ux0Z_zm1Gj4JThp0BR8N7U&hl=en&sa=X&ved=0ahUKEwiR6_aRyLzTAhXDNpQKHV13DTkQ6AEIKjAD#v=onepage&q=%22introduced%20long%20years%20ago%20by%22&f=false). He refers to "$r_k(n)$, introduced long years ago by Erdos and Turan: the least $r$ such that the sequence $1\le a_1<a_2<\cdots<a_r\le n$ of $r$ numbers not exceeding $n$ must contain a $k$-term arithmetic progression.... Rankin showed that $$r_k(n)>n^{1-c_s/(\log n)^{s/(s+1)}}$$ where $s$ is defined by $2^s<k\le2^{s+1}$." We're interested in $k=4$, so $s=1$. There are some other things at E10 that will be of interest.

Very relevant is http://oeis.org/A005048 which tabulates the "minimal span of set of $n$ elements with no 4-term arithmetic progression," where "span" is the difference between the largest and smallest elements. E.g., the entry for 34 is 69, meaning that there's a size-34 subset of $\{\,0,1,\dots,69\,\}$ with no 4-term AP (but no such subset for $\{\,0,1,\dots\,68\,\}$).

Also of interest is http://oeis.org/A005839 which is the "greedy sequence" with no 4-term AP.

Gerry Myerson
  • 179,216