# Homogeneous arithmetic progressions in difference sets

I have a nasty feeling that I ought to be able to answer this question, but I've got other things to think about right now and I'm interested in the answer just so that I can reply to a mathematical email I've received. (If anyone gives me substantial help I will of course acknowledge it when I reply.)

This isn't precisely what was asked in the email, but it's closely related and would enable me to give a good answer. A result of Bourgain shows that if you take two dense subsets A and B of {1,2,...,n} then A+B must contain an arithmetic progression of length $\exp(c(\log n)^{1/3})$ or thereabouts. In particular this is true of A-A (since it contains arithmetic progressions of the same length as A-(n+1-A)). But what bounds can one get in the A-A case if one insists that the progression should be homogeneous? That is, suppose that A is a subset of {1,2,...,n} of density δ. How large an m can we guarantee to find such that there exists d such that all of -dm, -(d-1)m, ... , dm are elements of A-A?

By Szemerédi's theorem applied to A, m at least tends to infinity with n and can be taken to be n logged a few times. But can we do a lot better than this? Another small observation is that if we apply Bourgain's theorem to A-A, we can obtain a quite long homogeneous arithmetic progression in A+A-A-A.

It's been a little while since I looked at either Bourgain's proof or a subsequent improvement by Green to $\exp(c\sqrt{\log n})$, so I can't instantly say whether their arguments would give one a homogeneous progression in the case that B=-A. Based on my hazy memory, it feels as though it could go either way.

Although I think it is unlikely, there's just a small chance that this is an interesting question to which the answer is not known (or an easy consequence of known results or techniques).

-
At least on my computer, the $\exp(c\sqrt{\log n})$ comes out in the wrong place. It should appear after the words "Green to". –  gowers Sep 9 '10 at 21:27
What do you mean by "dense subsets of {1,2,...,n}"? –  Ricky Demer Sep 9 '10 at 21:29
I mean subsets of size &alpha;n, where &alpha; is some fixed positive constant and n tends to infinity. The constant c is allowed to depend on &alpha;. –  gowers Sep 9 '10 at 21:50

It's a bit late, but let me point out that there is a wonderfully short and elementary argument of Croot, Ruzsa and Schoen that gives a homogeneous arithmetic progression of length about $\log n$ in $A-A$: it can be found in a paper called Arithmetic progressions in sparse sumsets, available at http://people.math.gatech.edu/~ecroot/kterm.pdf.

It can also deal with much sparser sets.

-