3 edited tags
2 edited tags
1

# 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).