MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I assume we want S to be an AP in addition, here? Otherwise it's trivial... – Harrison Brown Oct 29 '09 at 20:47
Fair point. I've adjusted the question. – Mark Lewko Oct 29 '09 at 22:18

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.

share|cite|improve this answer
Boris, thanks for your comments! I like your proof of the k=6 case. It seems, however, that the k=6 argument can't (at least naively) be extended to the case of k=8. To see this, find the 4-AP with a maximal largest element and (of these) a minimal smallest element. Now pass to the sub-progression containing this 4-AP (and relabel the progression as {0,1,2,3}). The intersection of our set with this progression could look like {-3,0,1,2,3,7}, which doesn't contain a 8-half-AP. Establishing the k=8 case would be very interesting. – Mark Lewko Nov 6 '09 at 22:52

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.

share|cite|improve this answer
Crystal, thanks for your comments. My question wasn't very clear (I've attempted to update it). I intended for it to be permissible for the half of S that does not intersect A to 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. – Mark Lewko Oct 29 '09 at 22:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.