 Solution

Assume $n>0$; the empty case is immediate. Write $r(s)=\#\{(a,b)\in A^2:a-b=s\}$. The additive energy in the hypothesis is ${\sum }_{s}r(s{)}^2$: rearranging $x+y=z+w$ gives $x-z=w-y$. Since $r(s)\le n$, the energy is at most $n^3$, so the substantive range is $0<\alpha \le 1$.

Let $S=\{s:r(s)\ge \alpha n/2\}$. The contribution of the other differences to the energy is at most $(\alpha n/2){\sum }_{s}r(s)=\alpha n^3/2$. ConsequentlyMake a bipartite graph with two copies of $A$, joining a left vertex $a$ to a right vertex $b$ when $a-b\in S$. Put $\rho =\alpha /2$. This graph has at least $\rho n^2$ edges, and $|S|\le n/\rho$.

We prove the needed dense-graph selection rather than quote the Balog-Szemerédi-Gowers theorem. A pair of left vertices is bad if it has fewer than $\tau n$ common right neighbours, where $\tau ={\rho }^2/32$. Choose a right vertex $y$ uniformly, let $U=N(y)$, and let $b(U)$ be the number of ordered bad pairs in $U$. Averaging the degrees gives $\mathbb{E}|U|\ge \rho n$. Every bad pair lies in fewer than $\tau n$ of these neighbourhoods, so $\mathbb{E}b(U)\le \tau n^2$. Therefore some $y$ satisfiesFor this neighbourhood, $|U|\ge \rho n/2$ and $b(U)\le \rho n|U|/16\le |U{|}^2/8$. Delete vertices having more than $|U|/4$ bad partners in $U$. At most half are deleted, so the remaining set $B$ has $|B|\ge |U|/2\ge \rho n/4$.

For any $b,b^{\prime }\in B$, at least $|U|/2$ vertices $v\in U$ are good partners of both. Each such $v$ has at least $\tau n$ common neighbours with $b$ and at least $\tau n$ with $b^{\prime }$. Independently choosing those neighbours gives at leastfour-edge walks $b,u,v,w,b^{\prime }$. Repeated vertices cause no difficulty. This proves the four-step path lemma for a dense bipartite graph in the required form.

The labels of such a walk are $s_1=b-u$, $s_2=v-u$, $s_3=v-w$, $s_4=b^{\prime }-w$, all in $S$, andFor a fixed pair $(b,b^{\prime })$, its label tuple uniquely recovers $u=b-s_1$, $v=u+s_2$, and $w=v-s_3$, so distinct walks have distinct label tuples. Choose one pair representing each element of the difference set $B-B$. Tuples belonging to different differences are disjoint because their alternating sum determines that difference. HenceWe have obtained explicit constants for the small-difference-set form of the Balog-Szemerédi-Gowers theorem: