"half arithmetic progressions" in dense sets - MathOverflow

"half arithmetic progressions" in dense sets

2009-10-29T19:27:49Z

Fix a positive real number d>0. Szemeredi's theorem implies that for every integer k, there exists an integer N(k,d) such that if A is a subset of the interval [1,N] with density greater than d >0, then A contains a k-term arithmetic progression.

Let us now define a half AP of length 2N, to be a AP of 2N integers, say S, such that S intersect A is exactly either the first half or the second half of S. Note that we do not require S to be completely contained in [1,N]. That is if A=[1,10] then S=[-9,10] is a half AP of length 20.

Edit: On the other hand, however, the elements of S that do not intersect A can lie in [1,N]. For example, if A=[4/10N, 5/10N] it is valid to take S = [3/10N,5/10N] to produce a half AP of length 2/10N.

Does there exists an integer N(k,d) such that if A is a subset of [1,N] of density d>0 then we can find a half AP of length k?

Answer by Kristal Cantwell for "half arithmetic progressions" in dense sets

2009-10-29T21:49:44Z

I don't think we can do this for all k and d. Look at the subset of [1,N] consisting of all points greater then (4/10)N and less then (5/10)N this will have density 1/10 and any half arithmetic progression of length 4 will have to hit the set twice so the the difference of the arithemetic progression must be 1/10 of N or less but the arithmetic progression must jump from below zero or above N and hence must have difference greater than 4/10 N which gives a contradiction.

Answer by Boris Bukh for "half arithmetic progressions" in dense sets

2009-11-06T20:31:04Z

Here is the proof for k=6 (i.e. we look for 6-half-AP with 3-elements in the set, and 3 outside). First, by Roth's theorem there is a 3-AP. Let {a,b,c} be the 3-AP with the maximum value of c. If there is more than one 3-AP with this value of c, choose one with the minimum value of a. Now consider only those elements of A that lie in the same arithmetic progression as {a,b,c}. After affine transformation we can assume that {a,b,c}={0,1,2} (I no longer assume that my set is a subset of [1,N]). Now, 3 is not in A because if it was, then {1,2,3} would be a longer 3-AP. Similarly, 4 is not in A for the fear of {0,2,4} being a 3-AP. Then 5 is in A because otherwise 0,1,..,5 is a 6-half-AP. Since 5 is not part of any 3-AP, it follows that -5,-3 and -1 are not in A. Since -3,-2,-1,0,1,2 is not 6-half-AP, we conclude that -2 is in A. However, -2,0,2 is a 3-AP in A with the same value of c, but smaller value of a, contradicting our choice of {a,b,c}.

My guess on this problem is that the answer is 'yes' in general, but I do not have great confidence. The general framework in which this problem falls is the following. Given an induced structure one wants to find, and large ambient structure in which to look, the large structure usually contains the small unless the large structure is of very special form. The induced structure here is k-half-AP, large structure here is a subset A of Z/pZ, and 'special form' is that the subset should be either nearly empty or nearly equal to Z/pZ. Given the current techniques for proving Szemerédi's theorem are 'local' (they find a density increment on some local piece), it might be a tough problem. If we knew the inverse conjecture for Gowers norms, it might be more attackable, but that conjecture is still in the works. Of course, it might happen that some simple trick, like one above can be used to deduce this problem from Szemerédi's theorem.