Proof of Theorem 1.1

For the given sets, $A=\{a_1,a_2,\ldots ,a_k\}$ in which the consecutive differences are all distinct and an arbitrary set $B=\{b_1,\ldots ,b_\ell \}$ we define a geometric graph, G. The vertices of the graph are points on the x axis, the values of the sumset $A+B.$ Two vertices, $u,v\in \{A+B\}$ are connected by an edge, an upper semicircular arc, iff there is an $a_i\in A$ and $b_j\in B$ such that $u=a_i+b_j$ and $v=a_{i+1}+b_j.$ So G consists of translates of the path, $P,$ with vertex set A where the consecutive vertices are connected by a semicircular arc (Figure 1). Since the consecutive differences are all different in $A,$ the graph has no multiple edges. We are going to bound the crossing number of this graph from below and from above to get a bound on $|A+B|.$ For the upper bound, note that any two translates of P have at most $2k-1$ crossings, so the number of crossings in G is at most

(2.1) $$ \begin{align} cr(G)\leq \binom{|B|}{2}(2k-1)\leq |B|^2{k}. \end{align} $$

Figure 1 The number of crossings between two translates of A is at most $2k-1$ .

There are various bounds on the crossing number of graphs. In our case, this is the convex crossing number (which is the same as the one-page crossing number) applies. The lower bound is a bit better than for general crossing numbers. It was proved in [Reference Shahrokhi, Sýkora, Székely and Vrt’o11] that for $|B|(k-1)$ edges and $|A+B|$ vertices the number of crossings is at least

(2.2) $$ \begin{align} cr(G)\geq \frac{(|B|(k-1))^3}{27|A+B|^2}, \end{align} $$

which proves Theorem 1.1, with the constant $c=1/\sqrt {27}\approx 0.19,$ since

(2.3) $$ \begin{align} |B|^2{k} \geq \frac{(|B|(k-1))^3}{27|A+B|^2}, \end{align} $$

implies that

$$ \begin{align*} |A+B| \geq \frac{|A||B|^{1/2}}{\sqrt{27}}. \end{align*} $$

▪

Proof We will work with G as defined in the proof of Theorem 1.1 and we are going to use a simple crossing bound from [Reference Pach, Solymosi and Tardos6].

Lemma 2.4 (Lemma 2.1 in [Reference Pach, Solymosi and Tardos6])

Let $G(U,V)$ be a bipartite graph with vertex classes U and $V,$ and suppose that its number of edges satisfies $e \geq 6 \max (|U|,|V|).$ Then we have

$$ \begin{align*} cr(G(U,V))\geq \frac{e^3}{108|U||V|}. \end{align*} $$

▪

From the proof of Theorem 1.1, we know that $cr(G)\leq |A||B|^2.$ There are two simple cases to consider; when a $\delta $ -fraction of the edges with an endpoint in S are inside of $S,$ or the $(1-\delta )$ -fraction of them connect S with the outside of S (we are going to optimize for $0<\delta <1$ at the end of our calculation). For the first case, we apply a classical crossing bound for the induced subgraph of G on $S,$ denoted by $H_S.$ By inequality (2.2), we have

$$ \begin{align*} |A||B|^2\geq cr(H_S)\geq \frac{(\delta|A||B|/\Delta)^3}{27|S|^2}\geq \frac{(\delta|A||B|/\Delta)^3}{27|A+B||S|}, \end{align*} $$

which gives the required inequality

$$ \begin{align*} |A+B|\geq \left(\frac{\delta}{3\Delta}\right)^3\frac{|B||A|^2}{|S|}. \end{align*} $$

In the second case, we can assume that $|A||B|^2\geq 6|A+B|,$ so Lemma 2 is applicable with $V=S$ and $U=\{A+B\}\setminus S.$

$$ \begin{align*} |A||B|^2\geq \frac{e^3}{108|U||V|}> \frac{((1-\delta)|A||B|/\Delta)^3}{125|S||A+B|}, \end{align*} $$

which gives

$$ \begin{align*} |A+B|> \left(\frac{1-\delta}{5\Delta}\right)^3\frac{|B||A|^2}{|S|}. \end{align*} $$

Choosing $\delta $ to make the constant multipliers in the two cases equal, we see that one can set $c_\Delta>1/(2\Delta )^3$ in Theorem 2.3.▪

Proof Set

$$ \begin{align*} \Delta=\frac{|A||B|}{t|S_t|} \end{align*} $$

so the following inequality holds

$$ \begin{align*} \sum_{x\in S_t}r_{A+B}(x)\geq|S_t|t=\frac{|A||B|}{\Delta}, \end{align*} $$

and we can apply Theorem 2.3. Solving inequality (2.5) for $|S_t|$ we get the desired result. ▪

Claim 2.6 Let A and B be finite sets of real numbers with $|A| = k$ and $|B| = \ell .$ If in A any consecutive difference, $a_i-a_{i-1},$ has multiplicity at most m then

$$ \begin{align*} |A+B| \geq \frac{ck\sqrt{\ell}}{\sqrt{m}}, \end{align*} $$

where $c>0$ is a universal constant.

Proof The claim follows directly from the crossing bound for multigraphs (see e.g., in [Reference Székely15]) and from our upper bound in equation (2.1).

$$ \begin{align*} k\ell^2\geq cr(G)\geq \frac{c(k\ell)^3}{m|A+B|^2}. \end{align*} $$

▪

Claim 2.7 Let $A=\{a_1,a_2,\ldots ,a_k\}$ be a finite set of real numbers with distinct consecutive differences which are not too far from each other, i.e.,

(2.7) $$ \begin{align} a_i-a_{i-1}\leq 2(a_{j}-a_{j-1}) \end{align} $$

for any $1<i,j\leq k,$ and let $B\subset \mathbb {R}$ an arbitrary finite set. Then

$$ \begin{align*} |A+B|\geq \frac{2}{3\sqrt{3}}|A||B|^{1/2}. \end{align*} $$

Proof To see this, note that by condition (2.7) if a subgraph of $G_{|A+B|}$ on n vertices is intersection free, then it has at most $n-1$ edges. If the number of edges is at least $1.5n$ then there are at least $0.5n$ intersections. The number of edges in $G_{|A+B|}$ is $(k-1)|B|\approx |A||B|,$ so let’s select a random subgraph of $G_{|A+B|}$ choosing the vertices independently at random with probability $p=\frac {1.5|A+B|}{|A||B|}.$ Then the expected number of vertices is $\frac {1.5|A+B|^2}{|A||B|},$ the number of edges is $\frac {(1.5|A+B|)^2}{|A||B|},$ and the expected number of intersections is at least $p^4\cdot int(G_{|A+B|}).$ From here, we have

$$ \begin{align*} \left(\frac{1.5|A+B|}{|A||B|}\right)^4\cdot int(G_{|A+B|})\geq 0.5\cdot \frac{1.5|A+B|^2}{|A||B|}, \end{align*} $$

and

$$ \begin{align*} |A||B|^2\geq int(G_{|A+B|})\geq 0.5\cdot \frac{(|A||B|)^3}{1.5^3|A+B|^2}. \end{align*} $$

▪

Proof Let n and k be relative prime numbers, $1 < n < k,$ such that $k-n$ is small (we will assign their exact values later). Set A is defined as

$$ \begin{align*} A=\{jk\ |\ 0 \leq j < n/2\}. \end{align*} $$

Between two consecutive numbers of A there is at least one multiple of $n.$ Let us choose one of them and add it to $A.$ In this way, we have $n-1$ numbers, all below $kn/2.$ All consecutive differences are distinct since the difference is either of the form $jk-in$ or $in-jk.$ If $jk-in = j'k-i'n,$ then $(j-j')k = (i -i')n,$ so $n \mid j- j',$ $j = j'$ and then $i = i'.$ The same holds for the $in- jk = i'n -j'k$ case. If $jk - in = i'n - j'k,$ then $(j + j')k = (i + i')n,$ so $n \mid j + j', j + j' < n,$ so $j = j' = 0,$ which is not possible.

The construction of B follows the same algorithm, using numbers $m, r.$

$$ \begin{align*} B=\{jr\ |\ 0 \leq j < m/2\}. \end{align*} $$

We choose $m, r$ in a way that $A + B$ is small. To achieve this let $1 < a < b < c < d$ be four pairwise relative prime numbers close to each other, e.g., $a = 6t+1, b = 6t+2, c = 6t+3, d = 6t+5.$ Let $n = ab, k = cd, m = ac, r = bd.$ The elements in both sets are less than $abcd/2,$ so the sumset is subset of $[0, abcd).$ All elements of the sumset are divisible by one of the numbers $ a, b, c, d,$ so its cardinality is less than $4bcd.$ The cardinality of the sets is at least $a^2$ and

$$ \begin{align*} 4bcd<(4+\varepsilon)(a^2)^{3/2}. \end{align*} $$

▪

Proof For the construction of A, we are going to use a set of integers with larger difference set than sumset. Searching for sets with many more differences than sums, we selected the set $S=\{0,1,3,7,12,22,30\}.$ S has 43 distinct pairwise differences and 28 sums.

If the reader would like to follow the construction with a smaller set then one can perform all steps using the $S=\{0,1,3\}$ set, and then $c>0$ is a bit below 0.1 ( $ c\approx 0.92 $ ), but the steps are easier to check. The selected seven element set is a result of a simple optimization to maximize $c.$ We are going to revisit the selection of S at the end of the proof.

First, we construct a set of k-dimensional vectors, $Q_k,$ in a sequence that consecutive vectors have distinct (vector) differences. Let us consider S as the vertex set of a complete digraph on seven vertices, and assign a value to every edge as follows: If the edge is $v_i\rightarrow v_j$ then its value is defined as $w(i,j)=v_i-v_j.$ For example, $w(2,4)=-6,$ and $w(3,3)=0.$ We will consider walks in this digraph. The first walk is an Euler tour starting and ending in $v_1.$ Listing the indices of the vertices in sequence as the tour goes we have e.g.,

$$ \begin{align*} E &=\{1,3,5,2,6,4,7,2,4,1,5,7,3,6,1,2,3,4,5,6,7,1,7, \\ &\qquad 5,3,7,4,6,5,1,6,2,5,4,3,1,4,2,7,6,3,2,1\}. \end{align*} $$

Using the values assigned to the vertices, we have our first multiset of (one dimensional) vectors,

$$ \begin{align*} Q_1 &= \{0,3,12,1,22,7,30,1,7,0,12,30,3,22,0,1,3,7,12,22,30, \\ &\qquad 0,30,12,3,30,7,22,12,0,22,1,12,7,3,0,7,1,30,22,3,1,0\}. \end{align*} $$

By the construction, all consecutive differences are distinct, we used all differences but 0. We define $Q_{k+1}$ recursively, using $Q_k.$ There will be $43|Q_k|=43^{k+1},$ not necessarily distinct $k+1$ dimensional vectors in $Q_{k+1},$ such that all consecutive differences are distinct. The first k coordinates are periodically repeating vectors, lets take k copies, blocks, of $Q_k,$ one after the other. We choose the last, $(k+1)$ th coordinate for every vector in blocks using $Q_1$ as follows. In the first block all $(k+1)$ th coordinates are 0. In the second block, we alternate 3 and 0, as $3,0,3,0,\ldots ,0,3.$ The third is $12,3,12,3,\ldots ,3,12.$ For the ith block, $(i>1),$ we use the ith and $i-1$ th entries of $Q_1$ and alternate them starting (and ending) with the ith. Note that the first and last vectors are identical.

In this way, all consecutive vectors have distinct differences. If the differences in the last coordinate are the same in two pairs of consecutive vectors, then there are three cases.

• • First, the two pairs are selected from the same $Q_k$ block. In this case, the differences of the first k coordinates are distinct by induction.

• • The second case when one of the pairs is between two blocks. There is only one pair of blocks where the last and the first vectors have a given difference in the last coordinate, so the other pair is inside one block. But in the difference vector of pairs between blocks the first k coordinates are zero, while differences of consecutive vectors in the same block have some nonzero coordinates among the first $k.$

• • The third case is when one pair is in one block and the other is in another block. It is only possible if one pair is in a block with last coordinates $a,b,a,\ldots ,b,a$ and the other is in the block with $b,a,\ldots ,a,b,$ but in this case the positions of the two pairs relative to their blocks are different due to parity, so by induction the differences are distinct in the first k coordinates.

Figure 2 The recursion getting $Q_{k+1}$ from $Q_k.$

Our next step is to construct an increasing sequence of numbers using the vectors in $Q_k$ keeping the same order and keeping the property that consecutive elements have distinct differences. If $\vec {v_i}\in Q_k$ has coordinates $\vec {v_i}^T=[\nu _1,\nu _2,\ldots ,\nu _k],$ then let us define $b_i=\nu _1+100\nu _2+100^2\nu _3+\ldots +100^{k-1}\nu _k.$ With this definition $b_i\leq 100^k,$ and the consecutive differences (in the order of the vectors in $Q_k$ ) are all distinct. To make the sequence monotone increasing, we define

$$ \begin{align*} A=\left\{a_i \text{ }|\text{ } a_i=b_i+i100^k, 1\leq i\leq 43^k\right\}. \end{align*} $$

The sumset, $A+A,$ consists of sums $a_i+a_j=b_i+b_j+(i+j)100^k.$ From the selection of the initial set, $S,$ we see that $\left |\left \{b_i+b_j | 1\leq i,j\leq 43^k\right \}\right |\leq 28^k,$ so we have the bound $|A+A|\leq 28^k\cdot 2\cdot 43^k$ while $|A|=43^k.$ By this construction we get a set $A,$ with distinct consecutive differences and $|A+A|\leq 2|A|^{2-c}$ where

$$ \begin{align*} c= \frac{\log{\frac{43}{28}}}{\log{43}}\approx 0.11406. \end{align*} $$

From the construction, we see that we needed a set S with small sumset and large difference set. We were searching among Sidon sets, i.e., sets where all pairwise sums are distinct. In such sets, if the size of S is x then $|S+S|=\binom {x}{2}+x$ and $|S-S|= x(x-1)+1$ . As we are looking for a large c above, we want to find the maximum of the function

$$ \begin{align*} \frac{\log{\frac{x(x-1)+1}{\binom{x}{2}+x}}}{\log{x(x-1)+1}}, \end{align*} $$

for positive $x.$ The maximum is $0.114058\ldots $ when $x \approx 6.99618$ , so we selected S to be a seven-element Sidon set, $\{0,1,3,7,12,22,30\}.$ ▪