Let $(n_k)_{1 \leq k \leq N}$ be a sequence of distinct positive integers. For $v \in \mathbb{Z}$ set $$ A_N(v) = \# \Big\{ (k,\ell) \in \{1, \dots, N\}^2, ~k \neq \ell:\quad n_k - n_\ell = v \Big\}. $$

Assume that $$ \sum_{v \in \mathbb{Z}} A_N(v)^2 \geq \varepsilon N^{3} $$ for some $\varepsilon > 0$. (Assume that $\varepsilon$ is fixed and $N$ is "very large".)

Question: Does the sequence $(n_k)$ necessarily have a strong arithmetic substructure? In particular, does there necessarily exist a number $w$ such that all the numbers $$ A_N(w), \quad A_N(2 w), \quad A_N(M w) $$ for some "large" value of $M$ all are "large"? (If so, please provide something quantitative, such as: $A_N(h w) \geq const(\varepsilon)N$ for all $h \leq H(N)$ for a certain function $H$.)

(Remarks: the natural example of a sequence for which $\sum A_N(v)^2$ is large is the sequence $(1, 2, \dots, N)$. For this sequence we clearly have the desired phenomenon. Note that the given lower bound for $\sum A_N(v)^2$ is quite strong, since trivially $\sum A_N(v)^2 \leq N^3$ by the fact that all $n_k$'s are different.)

  • 1
    $\begingroup$ You seem to be after the Balog-Szemeredi-Gowers theorem. $\endgroup$ – Seva Oct 6 '15 at 13:27
  • $\begingroup$ Thanks! Yes, that's what I seem to be after. The Balog-Szemeredi-Gowers theorem is formulated for sums rather than differences, but that should be a triviality. $\endgroup$ – Kurisuto Asutora Oct 6 '15 at 13:48
  • $\begingroup$ However, as I understand it the Balog-Szemeredi-Gowers theorem does not guarantee that I can find the desired large values of $A_N(w), A_N(2w), A_N(3w)$ etc. for one specific $w$. Is there hope to obtain such a thing? $\endgroup$ – Kurisuto Asutora Oct 6 '15 at 14:34
  • 1
    $\begingroup$ You should be able to get something by combining a number of known results. After the BSG theorem you can apply a lemma of Ruzsa, which allows you to think of your sequence (or rather a suitable subsequence) as living inside a cyclic group that is not much bigger. Then there are results about long arithmetic progressions in sumsets. These will not necessarily be of the form (w,2w,3w,...) but I think a careful look at the proofs should give you this. See for example this paper: arxiv.org/pdf/1103.6000.pdf $\endgroup$ – gowers Oct 6 '15 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.