# Additive combinatorics and a Diophantine equation

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

• You seem to be after the Balog-Szemeredi-Gowers theorem. – Seva Oct 6 '15 at 13:27
• 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. – Kurisuto Asutora Oct 6 '15 at 13:48
• 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? – Kurisuto Asutora Oct 6 '15 at 14:34
• 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 – gowers Oct 6 '15 at 15:53