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

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

share|cite|improve this question
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 αn, where α is some fixed positive constant and n tends to infinity. The constant c is allowed to depend on α. – 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

It can also deal with much sparser sets.

share|cite|improve this answer

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.