# “half arithmetic progressions” in dense sets

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?

-
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