2 Preliminaries

The lemmata in this section present the (elementary) version of the Szemerédi–Trotter theorem we need and show how it is used to furnish energy estimates.

In particular, for $k\geq 2$ the number of lines (curves) with $\geq k$ points is ${\displaystyle O\left(\frac{(|A||B|)^2}{k^3}\right)\,.}$

Note that affine lines have finite nonzero slopes. For an elementary “lucky pairs” proof of Lemma 1 when L is the set of affine lines see [Reference Solymosi and Tardos28]. The same proof works for translates of a convex curve.

The next two lemmata collect the bounds we need, based on Lemma 1.

Lemma 2 Let $A, B, C,\, \Pi_1,\Pi_2\subset \mathbb {R}$ be finite sets with the property that $r_{\Pi_1\Pi_2}(a)\geq T$ for all $a\in A$ and some $T\geq 1$ . Then if $|\Pi_1||C|\leq |\Pi_2|^2|B|^2,$

(2·1) \begin{equation}|\{c=a-b;\,a\in A, b\in B,\,c\in C\}| \ll \frac{(|\Pi_1||\Pi_2||B||C|)^{2/3}}{T}\,.\end{equation}

Besides, if $|\Pi_1||A|\leq |\Pi_2|^2|B|,$

(2·2) \begin{equation}\mathsf{E}_3(A,B)\ll\frac{|B|^2|\Pi_1|^2|\Pi_2|^2\log|A|}{T^3}\end{equation}

and for $s \in (1,3)$

(2·3) \begin{equation}\mathsf{E}_s (A,B)\ll_s\frac{(|\Pi_1| |\Pi_2|)^{s-1}|B|^{{(s+1)}/{2}}|A|^{{(3-s)}/{2}}}{T^{{3(s-1)}/{2}}}\,.\end{equation}

Furthermore, if A is convex, then if $|C|\leq |A||B|^2$ ,

\[|\{c=a-b;\,a\in A, b\in B,\,c\in C\}| \ll |A|^{1/3}(||B||C|)^{2/3}\,.\]

and for $s \in (1,3)$

\[\mathsf{E}_s(A,B)\ll_s |A||B|^{\frac{s+1}{2}}\,, \qquad \mathsf{E}_3(A,B)\ll |A||B|^2\log|A| \,.\]

Proof. Note that the cardinality relations between the sets involved serve only for one to be able to disregard the trivial term $|L|$ in the Szemerédi–Trotter incidence estimate of Lemma 1. Without loss of generality $|\Pi_1|\leq |\Pi_2|$ .

To prove (2·1) observe that

(2·4) \begin{equation} \begin{aligned}|\{c=a-b;\,a\in A, b\in B,c\in C\}| & \leq T^{-1} |\{c=pq-b;\,p\in \Pi_1,q\in \Pi_2, b\in B, c\in C\}| \\ & \ll T^{-1}[(|C||B||\Pi_1||\Pi_2|)^{2/3} + |\Pi_1||C|] \\ & \ll T^{-1} (|C||B||\Pi_1||\Pi_2|)^{2/3} ,\,\end{aligned}\end{equation}

by Lemma 1 and the assumptions on set cardinalities.

Furthermore, for an integer $k \in [1, \min(|A|,|B|)]$ define

\[D_k :=\{d \in A-B:\,r_{A-B}(x)\geq k\}\,\]

as the set of k-popular differences, clearly $|D_k|\leq |A||B|$ .

By definition of $D_k$ , as in (2·4), with $D_k$ as C in its right-hand side we have

\begin{align*}|D_k|k &\leq \frac1{T}|\{d=pq-b\colon d\in D_k,p\in \Pi_1,q\in \Pi_2,b\in B\}|\\&\ll\frac1{T} (|D_k||B||\Pi_1||\Pi_2|)^{2/3}\,.\end{align*}

Hence

(2·5) \begin{equation}|D_k| \ll \frac{ (|B||\Pi_1||\Pi_2|)^{2}}{(kT)^3}\,.\end{equation}

Then bound (2·2) follows after dyadic summation in $k=2^j$ , namely

\[\mathsf{E}_3(A,B) \ll \sum_{1\leq j \ll \log|A|} (2^{3j}) |D_{2^j}| \ll \frac{|B|^2|\Pi_1|^2|\Pi_2|^2\log|A|}{T^3},\]

as claimed.

Similarly, for $1<s<3$ dyadic summation leads, for any $k \in [1,\min(|A|,|B|)]$ , to the bound

\[\sum_{x\in A-B:\,r_{A-B} (x) \geq k} r^s_{A-B}(x) \ll_s \frac{1}{k^{3-s}} \frac{|B|^2|\Pi_1|^2|\Pi_2|^2}{T^3}\,,\]

where the hidden constant depends on s.

The remaining counterpart of $\mathsf{E}_s(A,B)$ is

\[\sum_{x\in A-B:\,r_{A-B} (x) < k} r^s_{A-B} (x) \leq k^{s-1} |A||B|\,.\]

Optimising the two latter bounds by choosing

\[k = |\Pi_1| |\Pi_2| \sqrt{ \frac{|B|}{|A|T^3}}\]

completes the proof of inequality (2·3).

For a convex $A=f([|A|])$ we want to show that same bounds as (2·2), (2·3) hold if one formally replaces $|\Pi_1|=|\Pi_2|=T=|A|$ . Let us use the same notation $D_k$ as above, writing for a single representation of each of its element d in $\geq \lfloor |A|/2\rfloor$ ways

\[d = f(i) - b_i = f(i+j - j) - b_i = f(l - j) - b_i\,.\]

(Without loss of generality we have assumed $i\leq |A|/2$ : otherwise we wold do $i=(i-j) + j$ , which leads to the same estimate using Lemma 1.) Hence, $k|D_k|$ is bounded from above via $|A|^{-1}$ times the number of incidences between the point set $[|A|]\times B$ and $|A||D_k|$ translates of the curve $y=f(x)$ . Applying Lemma 1 yields, with no constraints on B

\[|D_k|\ll \frac{|A||B|^2}{k^3}\,.\]

The claimed energy bounds follow similar to (2·2), (2·3).

Let us finally include the aforementioned few sums, many products estimate. The following lemma is in essence a restatement of [Reference Murphy, Roche–Newton and Shkredov12, lemma 2·5]. We provide a slightly shorter proof, which easily generalises for point sets that are not Cartesian products – see the remark following the proof.

Then

(2·6) \begin{equation}\mathsf{E}^\times (A) \ll \frac{ |\Pi_1|^{3}|\Pi_2|^{3} \log|\Pi_1| }{T^4}\,.\end{equation}

Proof. To estimate

\[\mathsf{E}^\times(A) = \left| \left\{ (a,b,c,d) \in A^4:\; \frac{a}{b}=\frac{c}{d}\right\}\right|\]

observe that this quantity is bounded from above by $T^{-4}$ times the number of solutions of the equation

(2·7) \begin{equation}t = \frac{x-y}{x'-y'} = \frac{u-v}{u'-v'}\,:\,x,x',u,u'\in \Pi_1, \;y,y',v,v' \in \Pi_2\,,\;t\in \mathbb {R}\setminus\{0\}\,.\end{equation}

The latter number of solutions, the variables $x,\ldots,v', t$ belonging to the sets as specified, is

\[\sum_t \left( \sum_{x,y'} r_{(x-\Pi_2)/(\Pi_1-y')} \right)^2 \leq |\Pi_1| |\Pi_2| \sum_t \sum_{x,y'} r^2_{(x-\Pi_2)/(\Pi_1-y')}(t)\,,\]

by Cauchy–Schwarz. Rearranging the fractions

\begin{align*}&\sum_{t\in \mathbb {R}\setminus\{0\}} \sum_{x,y'} r^2_{(x-\Pi_2)/(\Pi_1-y')}(t)\\ &= \left|\left\{ \frac{x- v}{x- v'} = \frac{y' - u}{y'-u'}:\, x,u,u'\in \Pi_1,\;y',v,v'\in \Pi_2\;: y'\neq u,u'\,, x\neq v,v'\right\}\right| \,.\end{align*}

The latter quantity is the number of affine collinear triples with two $(u,v), (u',v')\in \Pi_1\times \Pi_2$ and one, different from both of the above, $(y',x)\in \Pi_2\times \Pi_1$ . The trivial aspect of the count when $(u,v) = (u',v')$ yields merely $|\Pi_1|^2|\Pi_2|^2$ .

Otherwise by Lemma 1, the number of $k\geq2$ rich affine lines in $\Pi_1\times \Pi_2$ is $O\left({|\Pi_1|^2|\Pi_2|^2}/{k^3}\right)$ . We now take dyadic values $k_j=2^j,\,j\geq 1$ , partitioning these lines into groups $L_{k_j}$ , supporting the number of points of $\Pi_1\times \Pi_2$ in the interval $[2^j,2^{j+1})$ . The number of pairs of points from $\Pi_1\times \Pi_2$ on a line from the jth group is $\leq 4 k_j^2$ . Furthermore, by Lemma 1, the number of incidences between $L_{k_j}$ and $\Pi_2\times\Pi_1$ is

\[O\left( ( |L_{k_j}| |\Pi_1| |\Pi_2|)^{2/3} + |L_{k_j}|\right) \ll \frac{|\Pi_1|^{2} |\Pi_2|^{2}}{k_j^2}\,.\]

Multiplying by the latter bound by $ |\Pi_1||\Pi_2|k_j^2$ and summing in $O(\log|\Pi_1|)$ values of j absorbs the above trivial bound for the case $(u,v) = (u',v')$ and completes the proof.

We remark that the proof of Lemma 3 easily adapts to yield the following statement.

Let $P\subset \mathbb {R}^2$ have empty intersection with coordinate axes and $Q \subset \mathbb {R}^2$ meet any line l in at most $|Q|^{1/2}$ points. Suppose, $\forall\,p\in P$ , $r_{Q-Q}(p)\geq T^2$ , for some $T\geq 1$ (or the same for $r_{Q+Q}(p)$ ). Then

\[\sum_{l :\,(0,0)\in l} |P\cap l|^2 \ll \frac{ |Q|^{3}\log|Q| }{T^4}\,.\]

3 Proposition 1

In this section we present our main proposition. Unlike the arguments of Konyagin and Shkredov [Reference Konyagin and Shkredov10, Reference Konyagin and Shkredov11] and Shakan [Reference Shakan23], we lower bound the quantity $|A A_\lambda|$ instead of the smaller quantity $|A_\lambda A_\lambda|$ (definitions forthcoming). Our proof is elementary in that it uses only geometric and combinatorial observations.

In contrast, Shakan’s analogous proof used higher energies. One can apply Shakan’s ‘less elementary’ proof to the quantity $|AA_\lambda|$ to obtain the same conclusion as the forthcoming Proposition 1. In fact, one can even replace Shakan’s choice of second- and fourth-moment energies with the ‘more natural’ (when using the Szemerédi–Trotter theorem) third moment energy to realise the same conclusion.

Proposition 1 Let $A\subseteq \mathbb {R}_{>0}$ and let $|A+A|=K|A|$ and $|AA|=M|A|$ . Suppose that the multiplicative energy of A is supported on slopes $S_\tau\subseteq A/A$ so that $r_{A/A}(\lambda)\in [\tau, 2\tau)$ for each $\lambda\in S_\tau$ and

\[|S_\tau|\tau^2 \leq \mathsf{E}^\times(A) \leq 4|S_\tau|\tau^2\log|A|\,.\]

Then there exists $S_\tau^{\prime}\subseteq S_\tau$ with $|S_\tau^{\prime}|\geq |S_\tau|/64$ such that, for every $\lambda \in S_\tau^{\prime}$ ,

\[ |AA_\lambda| \gg \frac{|A|^6}{ M^4K^8|S_\tau|^{1/2}(\log|A|)^7}\,,\]

where $A_\lambda = A \cap \lambda^{-1} A$ .

Proof. Take a natural number

(3·1) \begin{equation}N := C K^2M |A|^{-1} \log|A|\,,\end{equation}

for a sufficiently large C, say $C>128$ . From Solymosi’s inequality (1·3), it follows that $K^2 M \geq |A|\lceil \log |A|\rceil^{-1}/4$ , hence, in particular, $N>2$ . We may also assume that $N<|A|^{1/2}$ ; indeed, if $N>|A|^{1/2}$ , then it is enough to show that $|AA_\lambda|>C^4 |S_\tau|^{-1/2}\log(|A|)^{-3}$ , which is readily satisfied since $|AA_\lambda|>|A|$ .

The slopes in $S_\tau$ are positive; we order them by increasing value and partition $S_\tau$ into bunches of N consecutive lines. There are $\lfloor|S_\tau|/N\rfloor$ ‘full’ bunches of exactly N slopes, and at most one additional bunch with fewer than N slopes that we delete with no consequence, since N is very small relative to $|S_\tau|$ . Henceforth, we assume that all bunches are full.

Let $\ell_\lambda$ denote the line through the origin with slope $\lambda$ . For each pair of distinct slopes $\lambda_i,\lambda_j$ in a fixed bunch $\mathcal B$ , we create between $\tau^2$ and $4\tau^2$ vectors in $(A+A)\times (A+A)$ from the sum of each of the $\sim \tau$ elements of $A\times A$ supported on the line $\ell_{\lambda_i}$ , with each of the $\sim \tau$ elements of $A\times A$ supported on $\ell_{\lambda_j}$ . We denote these vectors by $\mathcal{A}_{\lambda_i} + \mathcal{A}_{\lambda_j}$ . These $\sim \tau^2$ vector sums lie between $\ell_{\lambda_i}$ and $\ell_{\lambda_j}$ , and in particular, between the two extremal slopes in the bunch. A new element in $(A+A)\times(A+A)$ created in this manner could appear from multiple pairs of slopes within the same bunch; we must account for this over-counting. Note however that an element of $(A+A)\times (A+A)$ created in this way cannot have come from from pairs in two different bunches.

Define, for fixed slopes $\lambda_1,\lambda_2,\lambda_3,\lambda_4$ the quantity

\[q(\lambda_1,\lambda_2,\lambda_3,\lambda_4):=\left|\left(\mathcal{A}_{\lambda_1} + \mathcal{A}_{\lambda_2} \right)\cap\left(\mathcal{A}_{\lambda_3} + \mathcal{A}_{\lambda_4} \right)\right|\,\]

and for a fixed bunch $\mathcal{B}$ , let

\[Q_B := \sum_{\lambda_1,\lambda_2,\lambda_3,\lambda_4\in B} q(\lambda_1,\lambda_2,\lambda_3,\lambda_4),\]

where the sum is taken over distinct pairs of slopes: $\lambda_1\neq \lambda_2$ , $\lambda_3\neq \lambda_4$ and $\{\lambda_1,\lambda_2\} \neq \{\lambda_3,\lambda_4\}$ .

For slopes $\lambda_1,\lambda_2,\lambda_3,\lambda_4 \in B$ , with $B\in \mathcal{B}$ , the quantity $q(\lambda_1,\lambda_2,\lambda_3,\lambda_4)$ counts (using linear algebra to eliminate the variable $a_4 \in A_{\lambda_4}$ ) the number of solutions to the equation

(3·2) \begin{equation}a_3= \frac{\lambda_1 -\lambda_4}{\lambda_3-\lambda_4} a_1 + \frac{\lambda_2-\lambda_4}{\lambda_3-\lambda_4} a_2\,,\quad a_1\in A_{\lambda_1}, a_2\in A_{\lambda_2}, a_3 \in A_{\lambda_3}\,.\end{equation}

We use the inclusion-exclusion principle to count the number of new points in $(A+A)\times (A+A)$ created from forming vector sums from a fixed bunch $B\in \mathcal{B}$ . This number is at least

(3·3) \begin{equation}\tau^2\binom{N}{2} - Q_B\,.\end{equation}

If $Q_B\leq N^2\tau^2/8$ for at least half of the bunches $B\in \mathcal{B}$ , then

\[|A+A|^2 \geq \frac12\bigg\lfloor\frac{|S_\tau|}{N}\bigg\rfloor \left(\tau^2 \binom{N}{2} - \frac{N^2}{8} \tau^2\right) \geq \frac{|S_\tau|\tau^2 N}{32} \geq \frac{|A|^4N}{128|AA|\log|A|}\,;\]

by substituting in the value for N, we obtain a contradiction. Henceforth, let us suppose that $Q_B\geq N^2 \tau^2/4$ for at least $50\% $ of the bunches and let us relabel $\mathcal{B}$ to denote these bunches.

For $B\in \mathcal{B}$ , let $\Lambda_B = \{\lambda_3\in B: \sum q(\lambda_1,\lambda_2,\lambda_3,\lambda_4) > {\tau^2 N}/{8}\}$ , where the sum is taken over slopes $\lambda_1,\lambda_2,\lambda_4\in B$ , restricted as in the definition of $Q_B$ . The lower bound on $Q_B$ implies that $|\Lambda_B|\geq N/8$ . Hence, by an application of the pigeonhole principle on the variables $\lambda_1,\lambda_2,\lambda_4$ , we can find a set of at least $N/16$ slopes $\lambda_3 \in B$ so that there exist slopes $\lambda_1,\lambda_2,\lambda_4\in B $ such that the number of distinct solutions to equation (3·2) is

(3·4) \begin{equation}\geq \frac{\tau^2}{2N^{2}} :=S\,.\end{equation}

Let us redefine $S_\tau^{\prime}$ as the subset of the above slopes $\lambda_3$ , so that $|S_\tau^{\prime}|\geq|S_\tau|/{64}$ – in fact, we can manipulate the constants in the argument so that $S_\tau^{\prime}$ constitutes any desired proportion of $S_\tau$ .

For each $\lambda\in S_\tau^{\prime}$ , let $A_\lambda^{\prime}$ be the dyadically popular subset of $A_\lambda$ . Namely, we partition the set of $a \in A_\lambda$ by dyadic values of their number of realisations as the difference above – a member of the partition is identified by integer $0\leq s\ll\log|A|$ , so that $r_{c_1A_{\lambda_1} - c_2 A_{\lambda_2}} (a)\in [2^s,2^{s+1})$ where $c_1 = (\lambda_1 - \lambda_4)(\lambda - \lambda_4)^{-1}$ and $c_2 = (\lambda_4 - \lambda_1)(\lambda - \lambda_4)^{-1}$ .

Let $A_\lambda^{\prime}$ be the dyadic subset with the largest contribution to the number of solutions to (3·2), by the pigeonhole principle

\[\forall a \in A_\lambda^{\prime}, \;\;\;r_{c_1A_{\lambda_1} - c_2 A_{\lambda_2}} (a) \geq \frac{S}{2|A_\lambda^{\prime}|\log|A|}\,.\]

Applying Lemma 3 to $A_\lambda^{\prime}$ with $T= {S}/{2|A_\lambda^{\prime}|\log|A|}$ and $|\Pi_1|,|\Pi_2|\in [\tau,2\tau)$ yields

(3·5) \begin{equation}\mathsf{E}^\times(A_\lambda^{\prime}) \ll \frac{ \tau^6 |A_\lambda^{\prime}|^4 (\log|A|)^5 }{S^4}\,.\end{equation}

After two more applications of the Cauchy–Schwarz inequality, we get

\[|AA_\lambda|\geq|AA_\lambda^{\prime}| \geq \frac{|A|^2|A_\lambda^{\prime}|^2}{\mathsf{E}^\times(A,A_\lambda^{\prime})} \geq \frac{|A|^2|A_\lambda^{\prime}|^2}{\sqrt{\mathsf{E}^\times(A)\mathsf{E}^\times(A_\lambda^{\prime})}}\,.\]

Substituting the value of S from (3·4) and $\mathsf{E}^\times(A)\gg |S_\tau|\tau^2\log^{-1}|A|$ completes the proof.

4 Proof of Theorem 1

Without loss of generality, assume that A has positive elements. Denote $|A+A|=K|A|$ and $|AA|=M|A|$ . We will show that $\max(K,M)\geq |A|^{\frac1{3}+\frac{2}{1167}-o(1)}$ .

Consider the point set $A\times A \in \mathbb {R}^2$ . We begin by an application of the dyadic pigeonhole principle to extract a subset of $A\times A$ which supports at least a logarithmic factor of the energy of A: decompose the set of $|A/A|$ slopes through the origin supporting $A\times A$ into $\ll \log|A|$ dyadic sets, where each slope in the jth dyadic set $S_j$ contains between $2^{j-1}$ and $2^j-1$ points of $A\times A$ . Then $\sum_j|S_j|2^{2(j-1)}\leq \mathsf{E}^\times(A)< \sum_j|S_j|2^{2j}$ . Let $j_0$ denote the index for which $|S_{j_0}|2^{2j_0}$ is maximal, and write $S_\tau = S_{j_0}, \tau = 2^{j_0}$ . Then $|S_\tau|\tau^2 \gg \mathsf{E}^\times(A)/\log|A|$ . We may further assume that $\tau > C$ for some (large) constant $C>0$ , since otherwise $\mathsf{E}^\times(A)\leq C^2 |A|^2$ , and there is nothing to prove.

Let the points of $A\times A$ on the line with the slope $\lambda \in S_\tau$ be written as

\[\mathcal{A}_\lambda:=\{(a,\lambda a)\in A\times A:\,a\in A_\lambda \subseteq A\}\,,\;\;|A_\lambda|\in [\tau,2\tau)\}\,.\]

The set $A_\lambda=A\cap \lambda^{-1} A$ is the set of the x-coordinates of points in $\mathcal{A_\lambda}\subset \ell_\lambda$ , where $ \ell_\lambda$ is the line through the origin with slope $\lambda$ .

We apply Proposition 1 to A to pass from $\lambda\in S_\tau$ to $\lambda\in S_\tau^{\prime}$ . Clearly, $r_{A/A_\lambda}(\lambda)=|A_\lambda|$ , by definition of $A_\lambda$ .

Thus for any $a\in A$ and any $a_\lambda\in A_\lambda$ , one has

\[\lambda =\frac{a(\lambda a_\lambda)}{aa_\lambda}\in AA/AA\,.\]

(Konyagin and Shkredov refer to this truism as the Katz and Koester inclusion introduced in [Reference Katz and Koester9]). There are $|A_\lambda A|$ distinct values of the denominator $aa_\lambda$ . Thus, by the lower bound of Proposition 1,

(4·1) \begin{equation}\forall \lambda\in S_\tau^{\prime},\;\; r_{AA/AA}(\lambda) \;\geq \;|A A_\lambda | \gg \frac{|A|^6}{|S_\tau|^{1/2}M^4K^8(\log |A|)^7}:= T\,.\end{equation}

It remains to relate the set $S_\tau^{\prime}$ to A and use the Theorem 4. We choose a subset of $S_\tau^{\prime}$ by intersecting the set of at least $\tau |S_\tau^{\prime}|$ points of $A\times A$ supported on lines through the origin with slopes in $S_\tau^{\prime}$ , by a vertical line with some fixed x-coordinate $a_0\in A$ . By the pigeonhole principle, there is an element $a_0\in A$ , where the intersection has cardinality at least the average ${\tau |S_\tau^{\prime}|}/{|A|}$ .

Without loss of generality $a_0=1$ . Thus we have $B\subseteq A$ , with $|B| \geq {\tau |S_\tau|}/{|A|}$ and such that $\forall b\in B,\,r_{AA/AA}(b) \gg T$ . Concretely, $B = A/a_0 \cap S_\tau^{\prime}$ .

Using $K|A|=|A+A|\geq |B+B|$ we apply Theorem 4 to the set B with $\Pi = AA$ and $T = T$ , defined in (4·1), to get a lower bound for $|B+B|$ . We group together $|S_\tau|\tau^2 \gg \mathsf{E}^\times(A)\log^{-1}|A|$ to take advantage of the Cauchy–Schwarz relation $\mathsf{E}^\times(A)\geq |A|^3/M$ , so that (suppressing powers of $\log|A|$ ):

\[K^{283}M^{176}\gtrsim |A|^{94}(|S_\tau|\tau^2)^{41/2} |S_\tau|^4\,.\]

We recycle the bound on T to bound $|S_\tau|$ : since $M|A|=|AA|\geq |AA_\lambda|\gg T$ , we have that $|S_\tau|\geq |A|^{10}M^{-10}K^{-16}$ . This yields the inequality

\[K^{694}M^{473}\gtrsim |A|^{391}\,\]

whence the claim of Theorem 1 follows.

Reviewing the proof of Theorem 1, we remark that the main reasons why, within the Konyagin–Shkredov strategy, the gain over $\delta={1}/{3}$ is so small are (i) a large power $N^8$ of N (defined by (3·1) precisely to measure the eventual gain over $\delta={1}/{3}$ ) in estimate (3·5) (where $S= \tau^2N^{-2}$ ) and (ii) the relative weakness of the forthcoming Theorem 4. Lowering the power $N^8$ would require an unlikely improvement of the symmetric version of Lemma 3. A stronger version of Theorem 4 might come from further quantitative progress in understanding the Few Products, Many Sums, alias weak Erdős–Szemerédi conjecture, thus re-emphasising its pivotal role in the sum-product theory at large.

5 Proof of Theorems 3 and 4

We begin with the following regularisation lemma.

For any such rule $\mathcal{R}_\varepsilon$ , any $s>1$ and a sufficiently large finite set A, set $c_1 = \varepsilon \log(|A|) \in (0,1)$ . Then there exists a set $B\subseteq A$ (depending on $\mathcal{R}_\varepsilon, \,s$ ), with $|B|\geq (1-c_1) |A|$ such that

\[\mathsf{E}_s(\mathcal{R}_\varepsilon(B))\geq c_2\,\mathsf{E}_s(B)\,,\]

where $c_2 = (1- 2\varepsilon e^{1-s} \in (0,1]$ .

Proof. Construct a sequence of subsets of A as follows. Set $A_0 := A$ ; if $\mathsf{E}_s(A_{i+1}) < c_2\ \mathsf{E}_s(A_i)$ , define $A_{i+1}:=\mathcal{R}_\varepsilon(A_i)$ . By definition of $\mathcal{R}_\varepsilon$ , we have the lower bound $|A_i|\geq (1-\varepsilon)^i|A|\geq (1-i\varepsilon)|A|$ for any index i for which $A_i$ is defined.

This process must terminate after at most $I = \lfloor \log|A| \rfloor$ iterations. Indeed, suppose that we have constructed the set $A_I$ . Then, using the trivial bound $|A_I|^2\leq \mathsf{E}_s(A_I)\leq |A_I|^{s+1}$ , we have

\[(1-c_1)^2|A|^2\leq |A_I|^2 \leq \mathsf{E}_s(A_I)< c_2\mathsf{E}_s(A_{I-1}) \leq c_2^I\mathsf{E}_s(A) \leq |A|^{s+1-\log c^{-1}_2}\,.\]

The choice of $c_2$ yields a contradiction.

In this section we prove the following statement implying both theorems.

Proof. We begin with a regularisation argument, applying Lemma 4 to the forthcoming procedure $\mathcal{R}$ . This will yield a set of $B\subseteq A$ with $|B|\gg |A|$ , containing a large subset $\mathcal{R}(B)$ supporting most of the additive energy of B. We will then study linear relations among elements of B and $\mathcal{R}(B)$ .

Let $P_\varepsilon(A)$ be the set of popular sums of A, where ‘popular’ is defined according to some $\varepsilon\in (0,1)$ :

(5·1) \begin{equation}P_\varepsilon(A):=\left\{x\in A+A:\,r_{A+A}(x) \geq \epsilon \frac{|A|^2}{|A+A|}\right\}\,.\end{equation}

The set $P_\varepsilon(A)$ supports most of the mass of $A\times A$ . That is,

\begin{equation*}|\{(a,b) \in A\times A:\,a+b\in P_\varepsilon(A)\}|\geq (1-\epsilon)|A|^2\,.\end{equation*}

Indeed, we have

\[|A|^2 = \sum_xr_{A+A}(x) = \sum_{x\in P_\varepsilon(X)}r_{A+A}(x) + \sum_{x\notin P_\varepsilon(X)}r_{A+A}(x) < \sum_{x\in P}r_{A+A}(x) + \varepsilon|A|^2\,.\]

Let $\mathcal{R}(A)\subseteq A$ correspond to ‘rich’ x-coordinates in $A\times A$ , namely

\begin{equation*}\mathcal{R}(A):=\left\{a\in A\colon |(a+A)\cap P_\varepsilon(A)| \geq \frac{1}{2}|A|\right\}\,.\end{equation*}

Clearly $\mathcal{R}$ is a deterministic procedure that creates a subset of A. We show that $|\mathcal{R}(A)|\geq (1-2\varepsilon)|A|$ , or equivalently, in the notation of Lemma 4, that $\mathcal{R}(A)=\mathcal{R}_{2\varepsilon}(A)$ . To justify this claim, we use (5·1):

\begin{align*}(1-\varepsilon)|A|^2 & \leq |\{(a,b)\in \mathcal{R}(A)\times A\colon a+b\in \mathcal{P}_\varepsilon(A)\}|\\ &\quad + |\{(a,b)\in (A\setminus\mathcal{R}(A))\times A\colon a+b\in \mathcal{P}_\varepsilon(A)\}|\\&\leq |A||\mathcal{R}(A)| + \frac{1}{2}|A|(|A|-|\mathcal{R}(A)|)\,.\end{align*}

A rearrangement shows that $|\mathcal{R}(A)|\geq (1-2\varepsilon)|A|$ and so $\mathcal{R}(A) = \mathcal{R}_{2\varepsilon}(A)$ .

Having now defined a deterministic rule, let us apply Lemma 4 to the set A, setting $\varepsilon = {1}/{2}\log^{-1}|A|$ . We obtain a set $B\subseteq A$ with $|B|\geq |A|/2$ such that $\mathsf{E}(\mathcal{R}(B)) \gg \mathsf{E}(B)$ . The advantage of dealing with the sets B and $\mathcal{R}(B)$ versus A and $\mathcal{R}(A)$ is twofold: to each $b\in \mathcal{R}(B)$ we can add at least $|B|/{2}$ distinct members of B to obtain a popular sum in $P_\varepsilon(B)$ . Secondly, we have ruled out the adverse potential scenario in which the energy of $\mathcal{R}(A)$ is much less than the energy of A.

Let $D\subseteq \mathcal{R}(B)-\mathcal{R}(B)$ be the dyadic set supporting the energy of $\mathsf{E}(\mathcal{R}(B))$ , so that, for some $\Delta \geq 1$ we have

\[\mathsf{E}(B) \ll \mathsf{E}(\mathcal{R}(B)) \ll \Delta^2|D| \log|A|\]

and for all $d\in D$ , we have $r_{\mathcal{R}(B)-\mathcal{R}(B)}(d)\in [\Delta,2\Delta)$ . Note that D also supports the energy of $\mathsf{E}(B)$ .

Having defined suitably regular sets, we now proceed to obtain the quantitative advantage of Theorem 4. This arises from studying the following truism:

(5·2) \begin{equation} r-s = (b+r)-(b+s),\end{equation}

where pairs $(r,s)\in \mathcal{R}(B)\times \mathcal{R}(B)$ are popular by energy: $r-s\in D$ , and $b\in B$ .

Let us impose the additional condition that $x:=b+r\in P_\varepsilon(B)$ , where $P_\varepsilon(B)$ is defined as in (5·1). Since $b\in B$ , there are $\gg |D|\Delta|B|$ solutions to (5·2). We will partition solutions to (5·2) as

\[d=x-y:\;d\in D,\, x\in P_\varepsilon(B),\,y\in B+B\]

by the equivalence relation

\[(r,s,b)\sim (r+t,s+t,b-t),\;t\in \mathbb R\,.\]

The number Q of pairs of related triples is bounded from above by

(5·3) \begin{equation}\sum_t r^3_{B-B}(t) = \mathsf{E}_3(B)\,.\end{equation}

Hence, by the Cauchy–Schwarz inequality, using the popularity of the set $P_\varepsilon(B)$ and the Hölder inequality respectively, we get

(5·4) \begin{align}|A|^2|D|^2\Delta^2 & \ll \mathsf{E}_3(B) |\{x-y=d\colon x\in P_\varepsilon(B)\;,y\in B+B\;,d\in D\}| \\ &\leq\epsilon^{-1} \mathsf{E}_3(B)|B+B||B|^{-2}|\{b+b' -y = d\colon b,b'\in B\;,y\in B+B\;,d\in D\}|\nonumber\\&= \epsilon^{-1}\mathsf{E}_3(B)|B+B||B|^{-2}\sum_t r_{B-D}(t)r_{(B+B)-B}(t)\nonumber \\&\leq \epsilon^{-1} \mathsf{E}_3(B) |B+B||B|^{-2}\mathsf{E}_{3/2}^{2/3}(B,D)\mathsf{E}_3^{1/3}(B,B+B)\,. \nonumber \end{align}

To each instance of $\mathsf{E}_3$ as well as $\mathsf{E}_{3/2}$ we apply Lemma 2. We only present the case (i), as the case (ii) of a convex $|A|$ uses the estimates of the same lemma, the numerology change being tantamount to $|\Pi_1|=|\Pi_2|=T=|A|.$

Thus applying Lemma 2 and rearranging we obtain

(5·5) \begin{equation}|D|^{7/6}\Delta^2 \ll \epsilon^{-7/3} |\Pi_1|^{3}|\Pi_2|^{3}|B|^{-3/2}|B+B|^{5/3}T^{-9/2}\,.\end{equation}

We can assume, again by Lemma 2, that

(5·6) \begin{equation}\Delta\ll \epsilon^{-1} \frac{|\Pi_1|^2|\Pi_2|^2|B|^2}{T^3\mathsf{E}(B)}\,.\end{equation}

Indeed, by definition of D, there are $\sim \Delta|D|$ solutions to the equation

\[r-s = d:\;\;\;r,s\in B,\;d\in D\,.\]

Estimate (5·6) follows by compare this with bound (2·1) from Lemma 2, with $C=D$ and rearranging, using $\mathsf{E}(B) \gg \epsilon |D|\Delta^2$ .

We now multiply both sides of (5·5) by $\Delta^{1/6}$ , using (5·6) in the right-hand side. After that we rearrange, use

\[|D|\Delta^2 \gg \epsilon^{-1} \mathsf{E}(B) \geq \epsilon^{-1}\frac{|B|^4}{|B+B|},\,\]

as well as $|A+A|\geq |B+B|$ and $|B|\gg |A|$ to complete the proof.

We remark that we can easily re-purpose the above proof to retrieve the best known few products, many sums inequality

\[|AA|^{14}|A+A|^{10}\geq |A|^{30-o(1)}\]

by Olmezov, Semchankau and Shkredov [Reference Olmezov, Semchankau and Shkredov18].

We note also that we can obtain similar results involving the difference set by replacing $k=2$ with $k=12/7$ in Lemma 4. This recovers the result of Schoen and Shkredov [Reference Schoen and Shkredov22] that $|A-A|\gtrsim |A|^{8/5}$ for $|A|$ convex.

6 Proof of Theorem 2

In this section we prove a new lower bound on $|AA+AA|$ . The theorem follows immediately by combining the bounds from the two forthcoming propositions, the first one being an easier version of Proposition 1 and the second of the argument in the proof of Theorem 5 around estimates (5·2) - (5·4).

We once again assume that $A\subset \mathbb {R}_{>0}$ . Similar to Proposition 1, the forthcoming Proposition 2 uses Konyagin and Shkredov’s extension of Solymosi’s geometric argument [Reference Konyagin and Shkredov10, Reference Konyagin and Shkredov11, Reference Solymosi27]. Only now the vector sums constructed lie in $(AA+AA)\times (AA+AA)$ and the set of slopes used instead of $S_\tau$ are all of the slopes from $A/A$ . This idea is due to Balog [Reference Balog1].

A variant of Proposition 2 can be extracted from the paper by Iosevich, Roche–Newton and the first author [Reference Iosevich, Roche–Newton and Rudnev8, proof of theorem 2]. Below we give a brief self-contained proof.

Proposition 2 For a finite positive set of positive reals A,

\[|AA+AA|^2\gg |A/A|^{2/3}|A|^{5/2}\,.\]

Proposition 3 Let $A\subseteq \mathbb{C}$ . Then

\[|AA+AA|^5 \gg \frac{|A|^{13}}{|A/A|^5}\log^{-9/2}|A|\,.\]

It remains to prove Propositions 2 and 3.

Proof of Proposition 2. Recall that A is positive. For each $\lambda\in A/A$ we fix some vector $v_\lambda=(a_\lambda,\lambda a_\lambda)\in A\times A$ lying on the line through the origin with slope $\lambda$ . Clearly, for any $b\in A$ , the dilates $bv_\lambda$ of the vector $v_\lambda$ are in $AA\times AA$ . Thus for any $\lambda_1,\lambda_2\in A/A$ , we have the sums of such dilates lie in $(AA+AA)\times (AA+AA)$ :

\[\forall a_1,a_2\in A,\, \lambda_1,\lambda_2 \in A/A,\, a_1 v_{\lambda_1}+ a_2 v_{\lambda_2} \in (AA+AA)\times (AA+AA)\,.\]

For fixed distinct $\lambda_1,\lambda_2\in A/A$ , we get $|A|^2$ new vector sums, with slope between $\lambda_1$ and $\lambda_2$ .

By considering only vector sums from consecutive slopes $\lambda_i,\lambda_{i+1}$ , it thus follows that

\[|AA+AA|^2\geq (|A/A| - 1) |A|^2\,;\]

we will further attempt to improve by considering vector sums constructed within bunches of slopes.

Similar to (3·1) in the proof of Proposition 1 define

\[N:= C \frac{|AA+AA|^2}{|A|^2|A/A|}\,,\]

for a sufficiently large absolute C.

As in the proof of Proposition 1, partition the set of slopes $A/A$ (equivalently, the lines through the origin supporting $A\times A$ ) into $\lfloor |A/A|/N\rfloor$ consecutive “full” bunches containing N lines, and at most one bunch consisting of fewer than N lines, which gets deleted. Once again, N is much bigger than 2 and much smaller than $|A/A|$ .

To each bunch $\mathcal B$ and distinct $\lambda_i,\lambda_j\in \mathcal B$ we construct $|A|^2$ vector sums in $(AA+AA)^2$ , by considering the vector sums of the dilates of the vectors $v_{\lambda_i}, v_{\lambda_j}$ by elements of A, to generate the sum set $Av_{\lambda_i} + Av_{\lambda_j}\subseteq (AA+AA)^2$ .

Define q and

\[Q_B = \sum_{\lambda_1,\lambda_2,\lambda_3,\lambda_4 \in B}\left| (Av_{\lambda_i} + Av_{\lambda_j})\cap(Av_{\lambda_k} + Av_{\lambda_l})\right|,\]

where the sum is taken over $\lambda_1,\lambda_2,\lambda_3,\lambda_4 \in B$ where $\lambda_1\neq \lambda_2$ , $\lambda_3\neq \lambda_4$ and $\{\lambda_1,\lambda_2\} \neq \{\lambda_3,\lambda_4\}$ .

By inclusion-exclusion, the number of new elements of $(AA+AA)\times (AA+AA)$ generated by $\mathcal B$ is at least:

\[\binom{N}{2}|A|^2 - Q_B\,.\]

It is is a direct analogue of (3·3).

By repeating verbatim the argument in the proof of Proposition 1 between (3·3) and (3·4), we argue that, owing to the above choice of N, at least for 50% of the bunches $\mathcal B$ the collision term should be large. That is, the value Q associated to at least half the bunches satisfies

\[Q\gg N^4|A|^2 \left( \frac{|A|^2|A/A|}{|AA+AA|^2} \right)^2\,.\]

Furthermore, as a direct analogue of the arguments between statements (3·2) - (3·4) in the proof of Proposition 1 we conclude that there are two dilates of A by some $c_1,\,c_2$ , so that

\[\left| \{ (a,a_1,a_2)\in A^3:\, a=c_1a_1-c_2a_2\}\right| \gg |A|^2N^{-2}\gg |A|^2 \frac{|A|^4|A/A|^2}{|AA+AA|^4} \,.\]

We compare this with the upper bound for the number of solutions, from Lemma 2; we use bound (2·1), with $\Pi_1=A$ , $\Pi_2=A/A$ and $T=A$ , since $a=b\frac{a}{b}$ for any $b\in A$ .

Rearranging completes the proof.

Proof of Proposition 3. Once again, dyadically partition the set $A-A$ to obtain $D\subseteq A-A$ and $\Delta\geq 1$ so that $\mathsf{E}(A)\geq |D|\Delta^2\log|A|$ with $r_{A-A}(d)\in [\Delta,2\Delta)$ for each $d\in D$ .

There are at least $|A||D|\Delta$ solutions $(a,b,c)\in A^3$ to the equation

\[a-c = (a+b)-(b+c):\, a-c =d\in D\,.\]

We proceed as in the proof or Theorem 5, associating an equivalence relation to these solutions, so that that $(a,b,c)\sim (a+t,b-t,c+t)$ for some $t\in \mathbb {R}$ .

We have the analogue of (5·4)

(6·1) \begin{equation}|A||D|\Delta \leq \mathsf{E}_3^{1/2}(A)|\{(x,y,d)\in (A+A)^2\times D\colon x-y=d\}|^{1/2}\,.\end{equation}

We bound the quantity $|\{x-y=d\colon x,y\in A+A, d\in D\}|$ using Lemma 2, estimate (2·1), with $\Pi_1=1/A$ , $\Pi_2=A(A+A)$ and $T=|A|$ , for $x= (ax)\frac{1}{a}$ for any $a\in A$ . It follows that

\[|\{x-y=d\colon x,y\in A+A, d\in D\}|\ll |A|^{-1/3}|A+A|^{2/3}|D|^{2/3}|A(A+A)|^{2/3}\,.\]

Furthermore, once again by Lemma 2, bound (2·2), with $\Pi_1=A$ , $\Pi_2=A/A$ , and $T=|A|$ , since $a=b{a}/{b}$ , for any $b\in A$ , we have

\[\mathsf{E}_3(A)\ll |A/A|^2|A|\log|A|\,.\]

Multiplying both sides by $\Delta^{1/3}$ , the bound (6·1) then becomes

\[|A|^{2/3}(|D|\Delta^2)^{2/3}\ll |A/A||A+A|^{1/3}|A(A+A)|^{1/3}\Delta^{1/3} \log^{1/2}|A|\,.\]

Similar to (5·6) we have

\[\Delta\ll \frac{|A||A/A|^2}{\mathsf{E}(A)}\log|A| \,,\]

Thus

\[|A|^{1/3} \mathsf{E}(A) \ll |A/A|^{5/3} |A+A|^{1/3}|A(A+A)|^{1/3} \log^{3/2}|A|\,.\]

The proof is complete after rearranging after using $\mathsf{E}(A)\geq {|A|^4}/{|A+A|}$ and dominating $A+A$ and $A(A+A)$ by $AA+AA$ .

We remark, curiously, that if one uses an additional assumption in Theorem 2 that A is convex, then its estimate improves slightly to $|AA+AA|\geq |A|^{8/5-o(1)}$ . The same exponent ${8}/{5}-o(1)$ is the best one known in the few products, many sums scenario for $|A+A|$ when $|AA|\to |A|$ , [Reference Shkredov24]. The same exponent is also the best one known for $|A-A|$ when A is convex (but not for $|A+A|$ ), [Reference Schoen and Shkredov22]. See the discussion in the outset of this paper.