8
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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". $\endgroup$
    – gowers
    Sep 9, 2010 at 21:27
  • $\begingroup$ What do you mean by "dense subsets of {1,2,...,n}"? $\endgroup$
    – user5810
    Sep 9, 2010 at 21:29
  • $\begingroup$ 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 α. $\endgroup$
    – gowers
    Sep 9, 2010 at 21:50

1 Answer 1

5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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