Sums, Differences, and Dilates Jonathan Cutler Luke Pebody Amites Sarkar

###### Abstract

Given a set of integers $A$ and an integer $k$, write $A+k\cdot A$ for the set
$\\{a+kb:a\in A,b\in A\\}$. Hanson and Petridis [6] showed that if $|A+A|\leq
K|A|$ then $|A+2\cdot A|\leq K^{2.95}|A|$. At a presentation of this result,
Petridis stated that the highest known value for $\frac{\log(|A+2\cdot
A|/|A|)}{\log(|A+A|/|A|)}$ (bounded above by 2.95) was $\frac{\log 4}{\log
3}$. We show that, for all $\epsilon>0$, there exist $A$ and $K$ with
$|A+A|\leq K|A|$ but with $|A+2\cdot A|\geq K^{2-\epsilon}|A|$.

Further, we analyse a method of Ruzsa [10], and generalise it to give
continuous analogues of the sizes of sumsets, differences and dilates. We
apply this method to a construction of Hennecart, Robert and Yudin [3] to
prove that, for all $\epsilon>0$, there exists a set $A$ with
$|A-A|\geq|A|^{2-\epsilon}$ but with $|A+A|<|A|^{1.7354+\epsilon}$.

The second author would like to thank E. Papavassilopoulos for useful
discussions about how to improve the efficiency of his computer searches.

##  1 Introduction and Definitions

The study of the size of the sumset $|A+A|$ and difference set $|A-A|$
(sometimes denoted $DA$) in terms of $|A|$ is a central theme in additive
combinatorics. For instance, Freiman’s theorem states that if $|A+A|\leq
K|A|$, then $A$ must be a large fraction of a generalized arithmetic
progression, and the Balog-Szemerédi-Gowers theorem states that if $A$ has
large additive energy, then $A$ must contain a large subset $A^{\prime}$ such
that $|A^{\prime}+A^{\prime}|/|A^{\prime}|$ is small. For the precise
definitions and statements, we refer the reader to [11]. Given a number $x\in
Z$ the multiplicity of x in $A+A$ (and correspondingly in $A-A$) are defined
by

$\displaystyle\mathrm{Mult}_{A+A}(x)$
$\displaystyle=|A\cap(x-A)|=|\\{(a,b):a\in A,b\in A,a+b=x\\}|$
$\displaystyle\mathrm{Mult}_{A-A}(x)$
$\displaystyle=|A\cap(x+A)|=|\\{(a,b):a\in A,b\in A,a-b=x\\}|.$

For a finite set $A\subset\mathbb{Z}$, with $|A|=n$, we have that

$|A+A|\leq\frac{n(n+1)}{2}{\rm\ \ \ and\ \ \ }|A-A|\leq n^{2}-n+1,$

with equality in both cases precisely when $A$ is a Sidon set, that is a set
containing no nontrivial additive quadruple $(a,b,c,d)\in A^{4}$ with
$a+b=c+d$ (and consequently no nontrivial $(a,b,c,d)$ with $a-b=c-d$). In
other words, if $|A+A|$ is as large as it can possibly be, then so is $|A-A|$,
and conversely. In 1992, Ruzsa [10] showed, using an ingenious probabilistic
construction, that $|A+A|$ can be small, while $|A-A|$ can be almost as large
as possible, and vice-versa. In particular, he showed the following.

######  Theorem 1 (Ruzsa, 1992).

For every large enough $n$, there is a set $A$ such that $|A|=n$ with

$|A+A|\leq n^{2-c}\qquad\text{and}\qquad|A-A|\geq n^{2}-n^{2-c},$

where $c$ is a positive absolute constant. Also, there is a set $B$ with
$|B|=n$,

$|B-B|\leq n^{2-c},\qquad\text{and}\qquad|B+B|\geq\frac{n^{2}}{2}-n^{2-c}.$

A few years later, Hennecart, Robert and Yudin [3] constructed a set $A$ of
size $n$ with $|A+A|\sim n^{1.4519}$ but $|A-A|\sim n^{1.8462}$. Their
construction was inspired by convex geometry, specifically the difference body
inequality of Rogers and Shephard [2]. In the other direction, the study and
classification of MSTD sets (sets with more sums than differences) began with
Conway in 1967, and has now attracted a large literature (see [5] for a recent
survey).

Another line of investigation was opened by Bukh [1] in 2008. Given a set of
integers $A$ and an integer $k$, define the dilate set

$A+k\cdot A=\\{a_{1}+ka_{2}:a_{1},a_{2}\in A\\}.$

For $k=1$, this is just the sumset, $A+A$, and for $k=-1$ it is the difference
set, $A-A$. Note that, for example, the dilate set $A+2\cdot A$ is generally
not the same set as $A+A+A$, where each of the three summands can be distinct.
We define the multiplicity of $x$ in $A+k\cdot A$ to be

$\mathrm{Mult}_{A+k\cdot A}(x)=|A\cap(x-k\cdot A)|=|\\{(a,b):a\in A,b\in
A,a+kb=x\\}|.$

Bukh proved many results on general sums of dilates $\lambda_{1}\cdot
A+\cdots+\lambda_{k}\cdot A$ (for arbitrary integers
$\lambda_{1},\ldots,\lambda_{k}$), including lower and upper bounds on their
sizes. Some of these results were phrased in terms of sets with small
doubling, namely, sets $A\subset\mathbb{Z}$ with $|A+A|\leq K|A|$, for some
fixed constant $K$ (known as the doubling constant). For such a set $A$,
Plünnecke’s inequality [8] (see also [7]) shows that

$|A+2\cdot A|\leq|A+A+A|\leq K^{3}|A|,$

and Bukh asked if the exponent 3 could be improved. This question was answered
affirmatively in 2021 by Hanson and Petridis [6], who proved the following.

######  Theorem 2 (Hanson-Petridis, 2021).

If $A\subset\mathbb{Z}$ and $|A+A|\leq K|A|$, then

$|A+2\cdot A|\leq K^{2.95}|A|.$

They were also able to prove a result that improves Theorem 2 when $K$ is
large.

######  Theorem 3 (Hanson-Petridis, 2021).

If $A\subset\mathbb{Z}$ and $|A+A|\leq K|A|$, then

$|A+2\cdot A|\leq(K|A|)^{4/3}.$

Our contributions in this paper are best understood in the context of feasible
regions of the plane and so we make the following definition.

######  Definition.

For fixed integers $k$ and $l$, we define the _feasible region_ $F_{k,l}$ to
be the closure of the set $E_{k,l}$ of attainable points

$E_{k,l}=\left\\{\left(\frac{\log|A+k\cdot A|}{\log|A|},\frac{\log|A+l\cdot
A|}{\log|A|}\right)\right\\}.$

as $A$ ranges over finite sets of integers.

Note that for any $k$ and $l$, we have that $E_{k,l}\subset[1,2]^{2}$, which
follows from the fact that $|A|\leq|A+k\cdot A|\leq|A|^{2}$ for all $A$. For
every $k$ and $l$, each $A$ produces a point in $E_{k,l}$. With $A$ fixed, we
can generate a sequence of sets, indexed by the dimension $d$, by taking a
Cartesian product $A^{d}\subset\mathbb{Z}^{d}$, and then we will have
$|A^{d}+k\cdot A^{d}|=|A+k\cdot A|^{d}$. The advantage of the logarithmic
measure we are using is that all examples in this sequence, generated from the
same set $A$, correspond to the same point $(x,y)\in E_{k,l}$. Another useful
fact is that the set $F_{k,l}$ is convex. This is proved in Section 2.

The first series of results in this paper concerns the size of the dilate set
$A+2\cdot A$. We present a construction, the Hypercube+Interval construction,
which improves all previous bounds, and is close to the upper bounds in
Theorems 2 and 3 of Hanson and Petridis. Specifically, this construction shows
that graph $(x,y)$ of the piecewise-linear function

$y=\min\left(2x-1,(\log_{3}4)x\right)=\begin{cases}2x-1&1\leq
x\leq\log_{\frac{9}{4}}3=1.3548\ldots\\\ (\log_{3}4)x&\log_{\frac{9}{4}}3\leq
x\leq 2\\\ \end{cases}$

is entirely contained in $F_{1,2}$. This will allow us to prove a partial
converse to Theorem 2, namely that for any $\epsilon>0$, there exist positive
constants $K$ and sets $A$ with $|A+A|\leq K|A|$ but $|A+2\cdot A|\geq
K^{2-\epsilon}|A|$. Thus the true bound here is between 2 and 2.95. We also
give some negative results, showing that neither Sidon Sets, nor subsets of
$\\{0,1\\}^{d}\subset\mathbb{Z}^{d}$, can give rise to feasible points outside
the regions already proved feasible. Finally, we give a lower bound for the
region $F_{1,2}$, which is an easy consequence of Plünnecke’s inequality. All
these bounds and constructions are illustrated in Figure 2.

Our next series of results concerns the relationship between the sizes of
$A+A$ and $A-A$, and thus relates to the feasible region $F_{1,-1}$. This is
one of the oldest topics in additive combinatorics, with results going back to
Freiman and Pigarev [4] and Ruzsa [9] in the 1970s (and indeed Conway in the
60s). We analyse and generalise Ruzsa’s method from [10], leading to the
following concept which can be seen as a continuous analogue of the size of a
sumset and that of a dilate.

######  Definition.

Define a fractional dilate $\gamma$ to be a map
$\gamma:\mathbb{Z}\to\mathbb{R}^{+}\cup\\{0\\}$ with a finite support. We
denote the size of a fractional dilate to be

$\lVert\gamma\rVert=\inf_{0<p<1}\sum_{n\in\mathbb{Z}}\gamma(n)^{p}.$

We define a fractional set to be a fractional dilate $\alpha$ for which
$\alpha(n)\leq 1$ for all $n\in Z$. Note that the formula for the size of a
fractional set simplifies to
$\lVert\alpha\rVert=\sum_{n\in\mathbb{Z}}\alpha(n)$.

Given fractional sets $\alpha,\beta$ and an integer $k$, let
$\alpha+k\cdot\beta$ denote the fractional dilate defined by

$(\alpha+k\cdot\beta)(n)=\sum_{i+kj=n}\alpha(i)\beta(j).$

Given a fractional set $\alpha$, let us say that a random set
$S_{n}\subseteq\mathbb{Z}^{n}$ is drawn from $\alpha^{n}$ if each element of
$\mathbb{Z}^{n}$ is chosen independently, and the probability that
$(i_{1},i_{2},\ldots,i_{n})$ is selected is
$\alpha(i_{1})\alpha(i_{2})\ldots\alpha(i_{n}).$

We can identify an actual subset $S$ of $\mathbb{Z}$ with the fractional set
$\mathbbm{1}_{S}$ and then for any sets $S,T$, $|S+k\cdot T|$ can easily be
seen to be equal to $\lVert\mathbbm{1}_{S}+k\cdot\mathbbm{1}_{T}\rVert$.

We describe a fractional dilate $\gamma$ as being spartan if
$\sum_{n\in\mathbb{Z}:\gamma(n)\neq 0}\gamma(n)\log\gamma(n)<0$, opulent if
$\sum_{n\in\mathbb{Z}:\gamma(n)\neq 0}\log\gamma(n)>0$ and comfortable if
neither of these holds. In the case that $\gamma$ is comfortable, there will
be a unique $p\in[0,1]$ with $\sum_{n\in\mathbb{Z}:\gamma(n)\neq
0}\gamma(n)^{p}\log\gamma(n)=0$. If we wish to emphasise, we will say that
$\gamma$ is $p$-comfortable.

We will show this alternate characterisation of the size of a fractional
dilate.

######  Theorem 4.

The size of a fractional dilate $\gamma$ is

$\begin{cases}\sum_{n\in\mathbb{Z}}\gamma(n)\textrm{ if }\gamma\textrm{ is
spartan},\\\ |\\{n:n\in\mathbb{Z},\gamma(n)\neq 0\\}|\textrm{ if
}\gamma\textrm{ is opulent},\\\ \sum_{n\in\mathbb{Z}}\gamma(n)^{p}\textrm{ if
}\gamma\textrm{ is $p$-comfortable}.\\\ \end{cases}$

In Section 4 and Section 5, we prove the following.

######  Theorem 5.

Let $\alpha$ and $\beta$ be fractional sets, and suppose
$S_{n},T_{n}\subseteq\mathbb{Z}^{n}$ are drawn from $\alpha^{n}$ and
$\beta^{n}$ respectively. Then

$\displaystyle\lim_{n\to\infty}(\mathbb{E}|S_{n}+k\cdot T_{n}|)^{1/n}$
$\displaystyle\to\lVert\alpha+k\cdot\beta\rVert$
$\displaystyle\lim_{n\to\infty}(\mathbb{E}|S_{n}+k\cdot S_{n}|)^{1/n}$
$\displaystyle\to\begin{cases}\lVert\alpha+k\cdot\alpha\rVert\textrm{ if
}\lVert\alpha\rVert\geq 1\\\ \lVert\alpha\rVert\textrm{
otherwise.}\end{cases}$

Furthermore, if $\alpha+k\cdot\beta$ is spartan then

$\mathbb{E}|S_{n}||T_{n}|-|S_{n}+k\cdot
T_{n}|=o(\lVert\alpha+k\cdot\beta\rVert^{n})$

and similarly if $\alpha+k\cdot\alpha$ is spartan then

$\displaystyle\mathbb{E}|S_{n}|^{2}-|S_{n}+k\cdot S_{n}|$
$\displaystyle=o(\lVert\alpha+k\cdot\alpha\rVert^{n})\textrm{ if }k\neq 1$
$\displaystyle\mathbb{E}\frac{|S_{n}|^{2}}{2}-|S_{n}+k\cdot S_{n}|$
$\displaystyle=o(\lVert\alpha+k\cdot\alpha\rVert^{n})\textrm{ if }k=1$

In Section 6, we apply this method to the construction of Hennecart, Robert
and Yudin [3], to construct a fractional set $\alpha$ for which
$\alpha-\alpha$ is spartan, but $\alpha+\alpha$ is not.

######  Theorem 6.

There exists a fractional set $\alpha$ for which $\lVert\alpha\rVert>1$,
$\alpha-\alpha$ is spartan, and with
$\lVert\alpha+\alpha\rVert\leq\lVert\alpha\rVert^{1.7354}$.

This will allow us to prove that $(1.7354,2)$ is feasible for $F_{1,-1}$.

######  Corollary 7.

For all $\epsilon>0$, there exists a finite subset $A\subseteq\mathbb{Z}$ such
that $|A-A|\geq|A|^{2-\epsilon}>1$ but $|A+A|\leq|A|^{1.7354+\epsilon}$.

###### Proof.

Let $\alpha$ be the fractional set with properties as in Theorem 5, and let
$S_{n}$ be drawn from $\alpha^{n}$.

Pick $\epsilon^{\prime}$ in the range $(0,\epsilon)$. We will show that the
probabilities of the events $|S_{n}|<0.5\lVert\alpha\rVert^{n}$,
$|S_{n}|>1.5\lVert\alpha\rVert^{n}$,
$|S_{n}-S_{n}|<0.15\lVert\alpha\rVert^{2n}$ and
$|S_{n}+S_{n}|>0.5\lVert\alpha\rVert^{(1.7354+\epsilon^{\prime})n}$ all vanish
as $n\to\infty$ from which we will show that $S_{n}$ satisfies the required
conditions for $A$ with probability tending to 1.

$|S_{n}|$ is the sum of independent Bernoulli variables $(X_{i}:i\in S)$. Let
each variable $X_{i}$ have probability $p_{i}$ of being 1. Then

$\mathrm{Var}|S_{n}|=\sum_{i\in S}\mathrm{Var}X_{i}=\sum_{i\in
S}p_{i}-p_{i}^{2}\leq\sum_{i\in S}p_{i}=\mathbb{E}|S_{n}|.$

We know that $\mathbb{E}|S_{n}|$ is precisely $\lVert\alpha\rVert^{n}$, so the
variance is at most $\lVert\alpha\rVert^{n}$, so by Cauchy’s Inequality:

$\displaystyle\Pr(||S_{n}|-\lVert\alpha\rVert^{n}|>0.5\lVert\alpha\rVert^{n})$
$\displaystyle=\Pr(||S_{n}|-\mathbb{E}|S_{n}||^{2}>0.25\lVert\alpha\rVert^{2n})$
$\displaystyle\leq\mathrm{Var}|S_{n}|/0.25\lVert\alpha\rVert^{2n}$
$\displaystyle\leq 4/\lVert\alpha\rVert^{n}.$

Thus both the events $|S_{n}|<0.5\lVert\alpha\rVert^{n}$ and
$|S_{n}|>1.5\lVert\alpha\rVert^{n}$ have probabilities that vanish.

Since $\alpha-\alpha$ is spartan, Theorem 5 states that
$\mathbb{E}|S_{n}|^{2}-|S_{n}-S_{n}|$ is $o(\lVert\alpha\rVert^{2n})$. Since
$|S_{n}-S_{n}|$ is always at most as large as $|S_{n}|^{2}$, it follows that
the probability that $|S_{n}|^{2}-|S_{n}-S_{n}|>0.1\lVert\alpha\rVert^{2n}$
tends to 0. Further, since $|S_{n}|>0.5\lVert\alpha\rVert^{n}$ with
probability tending to 1, it follows that
$|S_{n}-S_{n}|>|S_{n}|^{2}-0.1\lVert\alpha\rVert^{2n}>0.15\lVert\alpha\rVert^{2n}$
with probability tending to 1.

Choose $\epsilon^{\prime\prime}$ in the range $(0,\epsilon^{\prime})$. Theorem
5 states that
$\lim_{n\to\infty}(\mathbb{E}|S_{n}+S_{n}|)^{1/n}\to\lVert\alpha+\alpha\rVert\leq\lVert\alpha\rVert^{1.7354}$,
so for all sufficiently large $n$,
$\mathbb{E}|S_{n}+S_{n}|<\lVert\alpha\rVert^{(1.7354+\epsilon^{\prime\prime})n}$,
so by Cauchy’s inequality, the probability that
$|S_{n}+S_{n}|>{\alpha}^{(1.7534+\epsilon^{\prime})n}$ is at most
$\lVert\alpha\rVert^{(\epsilon^{\prime\prime}-\epsilon^{\prime})n}$ which
vanishes.

So, for all sufficiently large $n$, with probability at least a half,
$0.5\lVert\alpha\rVert^{n}<|S_{n}|<1.5\lVert\alpha\rVert^{n}$,
$0.15\lVert\alpha\rVert^{2n}<|S_{n}-S_{n}|$ and
$|S_{n}+S_{n}|<0.5\lVert\alpha\rVert^{(1.7354+\epsilon^{\prime})n}$. Since,
for all sufficiently large $n$,
$0.15\lVert\alpha\rVert^{2n}\geq(1.5\lVert\alpha\rVert^{n})^{2-\epsilon}$ and
$\lVert\alpha\rVert^{(1.7354+\epsilon^{\prime})n}\leq(0.5\lVert\alpha\rVert^{n})^{1.7354+\epsilon}$,
it follows that for all sufficiently large $n$, with probability at least a
half, $S_{n}$ satisfies the conditions of this corollary. ∎

In the other direction, it follows from results of Freiman and Pigarev [4] and
Ruzsa [9] that $(x,2)$ is not attainable for any $x<3/2$. All these results
are illustrated in Figure 1.

Figure 1: The feasible region $F_{1,-1}$

Finally, in Section 7, we discuss many open questions about $F_{1,-1}$ and
$F_{1,2}$, and about feasible regions in general.

##  2 Feasible Regions

We remind the reader of the definition of a feasible region. For fixed
integers $k$ and $l$, the feasible region $F_{k,l}$ is defined as the closure
of the set $E_{k,l}$ of attainable points

$E_{k,l}=\left\\{\left(\frac{\log|A+k\cdot A|}{\log|A|},\frac{\log|A+l\cdot
A|}{\log|A|}\right)\right\\}\subset[1,2]^{2},$

as $A$ ranges over finite sets of integers. Note once again that the inclusion
follows from the fact that $|A|\leq|A+k\cdot A|\leq|A|^{2}$ for all such $A$.
Since $E_{k,l}\subset[1,2]^{2}$, we have also $F_{k,l}\subset[1,2]^{2}$. As
mentioned in the Introduction, we now prove that $F_{k,l}$ is convex.

######  Theorem 8.

For all nonzero $k,l$, the feasible region $F_{k,l}$ is convex, and contains
the diagonal $D=\\{(x,x):1\leq x\leq 2\\}$.

###### Proof.

First we prove the convexity. To do this, we first consider points
$(x,y),(x^{\prime},y^{\prime})\in E_{k,l}$, and take $t\in[0,1]$. We will show
that $(tx+(1-t)x^{\prime},ty+(1-t)y^{\prime})\in F_{k,l}.$ Since $(x,y)\in
E_{k,l}$, there exists a set $A\subset\mathbb{Z}$ with

$|A+k\cdot A|=|A|^{x}{\rm\ and\ }|A+l\cdot A|=|A|^{y}.$

Likewise, since $(x^{\prime},y^{\prime})\in E_{k,l}$, there exists a set
$B\subset\mathbb{Z}$ with

$|B+k\cdot B|=|B|^{x^{\prime}}{\rm\ and\ }|B+l\cdot B|=|B|^{y^{\prime}}.$

Setting $\beta=\log|B|/\log|A|$, choose a sequence $q_{1},q_{2},\ldots$ of
rational numbers such that

$\lim_{i\to\infty}q_{i}=\frac{t\beta}{1-t+t\beta}.$

For each such $q_{i}=r/s$, we consider a set $A_{i}\subset\mathbb{Z}^{s}$,
defined as

$A_{i}=\underbrace{A\times A\times\cdots\times A}_{r}\times\underbrace{B\times
B\times\cdots\times B}_{s-r},$

in which there are $r$ factors of $A$ and $s-r$ factors of $B$. We have

$\displaystyle|A_{i}|$ $\displaystyle=|A|^{r}|B|^{s-r},$
$\displaystyle|A_{i}+k\cdot A_{i}|$
$\displaystyle=|A|^{rx}|B|^{(s-r)x^{\prime}},\text{ and}$
$\displaystyle|A_{i}+l\cdot A_{i}|$
$\displaystyle=|A|^{ry}|B|^{(s-r)y^{\prime}}.$

And so,

$\displaystyle\frac{\log|A_{i}+k\cdot A_{i}|}{\log|A_{i}|}$
$\displaystyle=\frac{rx\log|A|+(s-r)x^{\prime}\log|B|}{r\log|A|+(s-r)\log|B|}$
$\displaystyle=\frac{q_{i}x+(1-q_{i})x^{\prime}\beta}{q_{i}+(1-q_{i})\beta},$

which tends to $tx+(1-t)x^{\prime}$ as $i\to\infty$. Similarly,

$\frac{\log|A_{i}+l\cdot A_{i}|}{\log|A_{i}|}\to ty+(1-t)y^{\prime},$

as $i\to\infty$. Consequently, $(tx+(1-t)x^{\prime},ty+(1-t)y^{\prime})\in
F_{k,l}$.

Now, given points $(x,y),(x^{\prime},y^{\prime})\in F_{k,l}$, we may take
sequences of points $(x_{j},y_{j})$ and $(x^{\prime}_{j},y^{\prime}_{j})$ from
$E_{k,l}$ tending to $(x,y)$ and $(x^{\prime},y^{\prime})$ respectively. For
each $j$, the above argument shows that

$(tx_{j}+(1-t)x_{j}^{\prime},ty_{j}+(1-t)y^{\prime}_{j})\in F_{k,l}.$

Consequently, letting $j\to\infty$, we have that

$(tx+(1-t)x^{\prime},ty+(1-t)y^{\prime})\in F_{k,l},$

and the convexity is proved.

To show that $(1,1)\in F_{k,l}$, we consider the set
$A:=A_{N}=\\{1,2,\ldots,N\\}$ for $N\gg\max(k,l)$. We have

$|A+k\cdot A|=(k+1)(N-1)+1{\rm\ \ and\ \ }|A+l\cdot A|=(l+1)(N-1)+1,$

so that, as $N\to\infty$,

$\left(\frac{\log|A+k\cdot A|}{\log|A|},\frac{\log|A+l\cdot
A|}{\log|A|}\right)\to(1,1).$

To show that $(2,2)\in F_{k,l}$, let $b>\max(|k|,|l|)+1$, and consider the set
$B=\\{1,b,b^{2},\ldots,b^{N}\\}$. We have

$|B+k\cdot B|\geq\tfrac{1}{2}|B|^{2}{\rm\ \ and\ \ }|B+l\cdot
B|\geq\tfrac{1}{2}|B|^{2},$

so that, as $N\to\infty$,

$\left(\frac{\log|B+k\cdot B|}{\log|B|},\frac{\log|B+l\cdot
B|}{\log|B|}\right)\to(2,2).$

It now follows by convexity that $D=\\{(x,x):1\leq x\leq 2\\}\subset F_{k,l}$.
∎

This result easily generalises to higher dimensions.

##  3 Construction for $F_{1,2}$

In this section, we present various results about the feasible region
$F_{1,2}$. As stated in the introduction, we will in particular give a partial
converse to a result of Hanson and Petridis (Theorem 2).

If set $A$ is the union of sets $A_{1},\ldots,A_{n}$, then it is clear that

$\max_{1\leq\i\leq n}|A_{i}|$ | $\leq$ | $|A|$ | $\leq\sum_{1\leq i\leq n}|A_{i}|$
---|---|---|---
$\max_{1\leq i\leq j\leq n}|A_{i}+A_{j}|$ | $\leq$ | $|A+A|$ | $\leq\sum_{1\leq i\leq j\leq n}|A_{i}+A_{j}|,\quad\text{and}$
$\max_{1\leq i,j\leq n}|A_{i}+2\cdot A_{j}|$ | $\leq$ | $|A+2\cdot A|$ |  $\leq\sum_{1\leq i,j\leq n}|A_{i}+2\cdot A_{j}|$.

Now, we are ready to describe the hypercube + interval construction. To this
end, let

$H_{n}=\left\\{\sum_{i=0}^{n-1}a_{i}4^{i}:\forall i,\
a_{i}\in\\{0,1\\}\right\\}\quad\text{and}\quad
I_{k}=\left[0,\frac{4^{k}-1}{3}\right)\cap\mathbb{Z}.$

So, $H_{n}$ denotes the set of all natural numbers with a base $4$
representation being of length at most $n$ and containing only $0$s and $1$s,
making up the hypercube portion of our construction. Of course, $I_{k}$ is
simply an interval of integers. We begin by giving the sizes of various
sumsets related to $H_{n}$ and $I_{k}$.

######  Theorem 9.

For $n\geq k>\frac{n+1}{2}$, the sizes of various sets, sumsets, and dilates
are as follows:

$\displaystyle|I_{k}|$ $\displaystyle=\frac{4^{k}-1}{3}\geq|H_{n}|=2^{n}$
$\displaystyle|H_{n}+H_{n}|$ $\displaystyle=3^{n}$
$\displaystyle|H_{n}+I_{k}|$
$\displaystyle=2\frac{4^{k}-1}{3}2^{n-k}\geq|I_{k}+I_{k}|$
$\displaystyle|H_{n}+2\cdot H_{n}|$ $\displaystyle=4^{n}\geq|H_{n}+2\cdot
I_{k}|,|I_{k}+2\cdot H_{n}|,|I_{k}+2\cdot I_{k}|.$

###### Proof.

We leave to the interested reader the job of calculating the sizes of
$|I_{k}+I_{k}|$, $|H_{n}+2\cdot I_{k}|$, $|I_{k}+2\cdot H_{n}|$,
$|I_{k}+2\cdot I_{k}|$ (spoiler warning: they are $2\frac{4^{k}-1}{3}-1$,
$2^{n+1-k}(2\times 4^{k-1}-1)$ twice and $4^{k}-3$ respectively.)

Since there are two choices for each $a_{i}$ where $0\leq i\leq n-1$, we have
that $|H_{n}|=2^{n}$. Also, since $(4^{k}-1)/3$ is an integer, we know that
$|I_{k}|=(4^{k}-1)/3$. Further, since $k\geq\frac{n+2}{2}$, $4^{k}\geq
2^{n+2}>1+3\times 2^{n}$, so $(4^{k}-1)/3>2^{n}$.

Note that $H_{n}+H_{n}=\left\\{\sum_{i=0}^{n-1}a_{i}4^{i}:\forall i,\
a_{i}\in\\{0,1,2\\}\right\\}$. In other words, elements of $H_{n}+H_{n}$ are
natural numbers whose base $4$ representation is of length at most $n$ and
contains only $0$s, $1$s, and $2$s. Thus, $|H_{n}+H_{n}|=3^{n}$. Similarly
$H_{n}+2\cdot H_{n}$ are natural numbers whose base $4$ representation is of
length at most $n$ and contains only 0s, 1s, 2s and 3s, which is $[0,4^{n})$.
Further, since the maximum element of $H_{n}$ is at least as large as the
maximum element of $I_{k}$ it is clear that all of $H_{n}+2\cdot I_{k}$,
$I_{k}+2\cdot H_{n}$ and $I_{k}+2\cdot I_{k}$ are subsets of $[0,4^{n})$ and
therefore of size at most $4^{n}$.

For $H_{n}+I_{k}$, note that $H_{n}$ is the sum of the sets $\\{0,1\\}$,
$\\{0,4\\}$ all the way up to $\\{0,4^{n-1}\\}$. Now if $p\geq q$ are positive
integers, then the sum of the integer interval $[0,p)$ with the set
$\\{0,q\\}$ is the integer interval $[0,p+q)$. Thus

$\displaystyle I_{k}+\\{0,1\\}+\\{0,4\\}+\ldots+\\{0,4^{k-1}\\}$
$\displaystyle=$
$\displaystyle[0,\frac{4^{k}-1}{3})+\\{0,1\\}+\\{0,4\\}+\ldots+\\{0,4^{k-1}\\}$
$\displaystyle=$
$\displaystyle[0,\frac{4^{k}-1}{3}+1)+\\{0,4\\}+\ldots+\\{0,4^{k-1}\\}$
$\displaystyle=$ $\displaystyle\ldots$ $\displaystyle=$
$\displaystyle[0,2\frac{4^{k}-1}{3})\supseteq I_{k}+I_{k}.$

Further the set $\\{0,4^{k}\\}+\ldots+\\{0,4^{n-1}\\}$ consists of multiples
of $4^{k}$, which are all further than $2\frac{4^{k}-1}{3}$ apart, so
$H_{n}+I_{k}$ consists of $2^{n-k}$ intervals of length $2\frac{4^{k}-1}{3}$
and contains $I_{k}+I_{k}$. ∎

Let $A_{n,k}=H_{n}\cup I_{k}$. Then, using Theorem 9, we can show the
following.

######  Corollary 10.

Let $\alpha$ be any real number in the open region $(\frac{1}{2},1)$. Then as
$n\to\infty$,

$\displaystyle\frac{\log|A_{n,\lfloor\alpha n\rfloor}|}{n}$
$\displaystyle\to\alpha\log 4,$ $\displaystyle\frac{\log|A_{n,\lfloor\alpha
n\rfloor}+A_{n,\lfloor\alpha n\rfloor}|}{n}$ $\displaystyle\to\max(\log
3,\frac{1+\alpha}{2}\log 4),\quad\text{and}$
$\displaystyle\frac{\log|A_{n,\lfloor\alpha n\rfloor}+2\cdot
A_{n,\lfloor\alpha n\rfloor}|}{n}$ $\displaystyle\to\log 4.$

###### Proof.

Note that if $k$ is a fixed constant and $a_{n,i}$ for $1\leq i\leq k$ and
$1\leq n$ are positive integers and $c_{i}$ for $1\leq i\leq k$ are real
numbers such that $\lim_{n\to\infty}\log a_{n,i}/n\to c_{i}$ for all $i$, and
integers $b_{n}$ satisfy that $\max_{i}a_{n,k}\leq b_{n}\leq\sum_{i}a_{n,k}$,
then

$\lim_{n\to\infty}\frac{\log b_{n}}{n}\to\max\\{c_{1},\ldots,c_{n}\\}.$

Let us write $k=\lfloor\alpha n\rfloor$. For the first part of the Corollary,
we note that by Theorem 9, we have

$\lim_{n\to\infty}\frac{\log|H_{n}|}{n}=\log
2<\lim_{n\to\infty}\frac{\log|I_{k}|}{n}=\alpha\log 4.$

Since we know that $I_{k}\subseteq A_{n,k}$ and
$|A_{n,k}|\leq|H_{n}|+|I_{k}|$, it follows that
$\lim_{n\to\infty}\log|A_{n,k}|/n=\alpha\log 4.$

For the sumsets, we note that (again using Theorem 9)

$\displaystyle\lim_{n\to\infty}\frac{\log|H_{n}+H_{n}|}{n}$
$\displaystyle=\log 3,\quad\text{and}$
$\displaystyle\lim_{n\to\infty}\frac{\log|H_{n}+I_{k}|}{n}$
$\displaystyle=(1-\alpha)\log 2+\alpha\log 4=\frac{1+\alpha}{2}\log
4>\lim_{n\to\infty}\frac{\log|I_{k}+I_{k}|}{n}.$

Since we know that $H_{n}+H_{n}$ and $H_{n}+I_{k}$ are both subsets of
$A_{n,k}+A_{n,k}$ and that
$|A_{n,k}+A_{n,k}|\leq|H_{n}+H_{n}|+|H_{n}+I_{k}|+|I_{k}+I_{k}|$, it follows
that $\lim_{n\to\infty}\log|A_{n,k}+A_{n,k}|/n=\max(\log
3,\frac{1+\alpha}{2}\log 4).$

Finally, for the dilates, we have

$\displaystyle\lim_{n\to\infty}\frac{\log|H_{n}+2\cdot H_{n}|}{n}=\log 4>$
$\displaystyle\lim_{n\to\infty}\frac{\log|H_{n}+2\cdot I_{k}|}{n},$
$\displaystyle\lim_{n\to\infty}\frac{\log|I_{k}+2\cdot H_{n}|}{n},$
$\displaystyle\lim_{n\to\infty}\frac{\log|I_{k}+2\cdot I_{k}|}{n}.$

Thus $\log|A_{n,k}+2\cdot A_{n,k}|/n\to\log 4$. ∎

The upper limit in the second interval above is $\log 3$ when $\alpha$ is
below $2\frac{\log 3}{\log 4}-1$, and $\frac{1+\alpha}{2}\log 4$ above it. As
mentioned above, this gives a partial converse to Theorem 2

######  Corollary 11.

For all $\epsilon>0$, there exist sets $S$ and numbers $K>1$ with $|S+S|\leq
K|S|$ but with $|S+2\cdot S|>K^{2-\epsilon}|S|.$

###### Proof.

Let $\frac{1}{2}\leq\alpha\leq 2\frac{\log 3}{\log 4}-1$. Then Corollary 10
shows that

$\frac{\log|A_{n,\lfloor\alpha n\rfloor}+2\cdot A_{n,\lfloor\alpha
n\rfloor}|-\log|A_{n,\lfloor\alpha n\rfloor}|}{\log|A_{n,\lfloor\alpha
n\rfloor}+A_{n,\lfloor\alpha n\rfloor}|-\log|A_{n,\lfloor\alpha
n\rfloor}|}\to\frac{\log 4-\alpha\log 4}{\frac{1+\alpha}{2}\log 4-\alpha\log
4}=\frac{1-\alpha}{\frac{1-\alpha}{2}}=2.$

∎

We now use this corollary to show that we have feasible points in $F_{1,2}.$
Let the function $f:[1,2]\to[1,2]$ be defined by

$f(x)=\begin{cases}\frac{1}{2}(\beta+1)&\text{if $1\leq x\leq\frac{\log
4}{\log(9/4)}$}\\\ (\log_{4}3)x&\text{if $\frac{\log 4}{\log(9/4)}\leq x\leq
2$}.\end{cases}$

######  Corollary 12.

For all $1<\beta<2$, $\left(f(\beta),\beta\right)\in F_{1,2}$.

###### Proof.

Let $\alpha=1/\beta$, then

$\displaystyle\alpha\log 4f(\beta)$ $\displaystyle=\alpha\log
4\max(\frac{1}{2}(\beta+1),(\log_{4}3)\beta)$ $\displaystyle=\alpha\log
4\max(\frac{1+\alpha}{2\alpha},\frac{\log 3}{\alpha\log 4})$
$\displaystyle=\max(\frac{1+\alpha}{2}\log 4,\log 3).$

Thus Corollary 10 gives the existence of sets where

$\displaystyle\log|A_{n,\lfloor\alpha n\rfloor}|/n$
$\displaystyle\to\alpha\log 4,$ $\displaystyle\log|A_{n,\lfloor\alpha
n\rfloor}+A_{n,\lfloor\alpha n\rfloor}|/n$ $\displaystyle\to\alpha\log
4f(\beta),\quad\text{and}$ $\displaystyle\log|A_{n,\lfloor\alpha
n\rfloor}+2\cdot A_{n,\lfloor\alpha n\rfloor}|/n$ $\displaystyle\to\log
4=\alpha\log 4\beta.$

So

$\displaystyle\log|A_{n,\lfloor\alpha n\rfloor}+A_{n,\lfloor\alpha
n\rfloor}|/\log|A_{n,\lfloor\alpha n\rfloor}|$ $\displaystyle\to
f(\beta)\quad\text{and}$ $\displaystyle\log|A_{n,\lfloor\alpha
n\rfloor}+2\cdot A_{n,\lfloor\alpha n\rfloor}|/\log|A_{n,\lfloor\alpha
n\rfloor}|$ $\displaystyle\to\beta.$

∎

Let us quickly discuss a lower bound on the feasible region given by
Plünnecke’s inequality [8].

######  Theorem 13 (Plünnecke 1970).

Let $U$ and $V$ be finite subsets of $\mathbb{Z}$ and let $X\subseteq U$ such
that

$\rho:=\frac{|X+V|}{|X|}\leq\frac{|X^{\prime}+V|}{|X^{\prime}|}$

for all nonempty subsets $\emptyset\neq X^{\prime}\subseteq X$. Then, for any
set $W$, we have

$|X+V+W|\leq\frac{|X+V||X+W|}{|X|}.$

This gives a simple upper bound on $|A+A|$ in terms of $|A+2\cdot A|$.

######  Corollary 14.

For all sets $A$, $|A+A|\leq\frac{|A+2\cdot A|^{2}}{|A|}$.

###### Proof.

Let $1\leq t\leq 2$ be such that $|A+2\cdot A|=|A|^{t}$. Suppose that
$S\subseteq A$ minimises $\frac{|S+2\cdot A|}{|S|}$. Then

$\rho:=\frac{|S+2\cdot A|}{|S|}\leq\frac{|A+2\cdot
A|}{|A|}\leq\frac{|A|^{t}}{|A|}=|A|^{t-1}.$

Further, we note that

$|A+A|=|2\cdot A+2\cdot A|\leq|S+2\cdot A+2\cdot A|\leq\frac{|S+2\cdot
A|^{2}}{|S|}=\rho^{2}|S|\leq\rho^{2}|A|,$

where the second inequality is Plünnecke’s inequality. Thus, we have

$|A+A|=|2\cdot A+2\cdot
A|\leq\rho^{2}|A|\leq(|A|^{t-1})^{2}|A|=\frac{|A+2\cdot A|^{2}}{|A|}.$

∎

So, we know that if $\log|A+2\cdot A|/\log|A|\leq t$, then
$\log|A+A|/\log|A|\leq 2t-1$. This means that anything below the line
$y=1+x/2$ is not in the feasible region $F_{1,2}$.

Also, note that the two results of Hanson and Petridis (Theorems 2 and 3) give
two upper bounds on $F_{1,2}$, namely the lines $y=2.95x-1.95$ and $y=4t/3$.
The first follows from the fact that if $|A+A|=|A|^{t}$, then by Theorem 2, we
have $|A+2\cdot A|\leq|A|^{2.95t-1.95}$. The second follows similarly. We put
all of these results together into Figure 2.

Corollary 12 shows that lines $OD$ and $DC$ are feasible, while Theorem 8
shows that the line $OE$ is feasible and hence that the entire quadrilateral
$ODCE$ is feasible.

For infeasibility, the two results of Hanson and Petridis (Theorems 2 and 3)
show that nothing can be feasible to the left of the line $OA$ and above the
line $AB$ respectively. Specifically, if $|A+A|=|A|^{t}$, Theorem 2 implies
that $|A+2\cdot A|\leq|A|^{2.95t-1.95}$ and Theorem 3 implies that $|A+2\cdot
A|\leq|A|^{4t/3}$.

Figure 2: The feasible region $F_{1,2}$

We leave as open questions whether any of the sides of the quadrilateral
$ODCE$ (other than $CE$, for which we have a proof but there is not enough
space to give it here) are actually hard bounds on feasibility. Specifically,
we ask the following:

######  Question 15.

Is it true that nothing to the left of the line $ODB$ is in $F_{1,2}$. In
other words, if $|A+A|=|A|^{t}$, is $|A+2\cdot A|\leq|A|^{1+2t}$? In yet more
other words, is it true that for all $A$, $|A||A+2\cdot A|\leq|A+A||A+A|$.

######  Question 16.

Is it true that nothing above the line $DC$ is in $F_{1,2}$. In other words,
is it true that $\frac{\log|A+2\cdot A|}{\log|A+A|}\leq\frac{\log 4}{\log 3}$
for all sets $A$? In yet more other words, is it true for all $n$ that if
$|A+A|\leq 3^{n}$, then $|A+2\cdot A|\leq 4^{n}$?

######  Question 17.

Is it true that nothing below the line $OE$ is in $F_{1,2}$. In other words,
are there no sets $A$ with $|A+A|>|A+2\cdot A|$?

We coin the term MST2D sets (or more sums than 2-dilates sets) for
counterexamples to Question 17. One of the first places you might think to
find such a set is a Sidon set (that is, a set for which $|A+A|$ is as large
as it can be). However, one can easily show that a Sidon Set cannot be an
MST2D set.

######  Lemma 18.

If $A$ is a Sidon set with at least two elements, then $|A+2\cdot A|>|A+A|$.

###### Proof.

Adding and multiplying non-zero constants to $A$ does not change $|A+A|$ or
$|A+2\cdot A|$. Thus we can assume that $0\in A$ and $\mathrm{gcd}A=1$.

Let $n=|A|$. If $X_{1},X_{2}$ are i.i.d drawn from any distribution on a
finite set $S$ then $\Pr(X_{1}=X_{2})\geq 1/|S|$.

Thus if $A_{1},A_{2},A_{3},A_{4}$ are i.i.d. drawn from the uniform (or indeed
any) distribution on $A$, then $|A+2\cdot A|\geq 1/\Pr(A_{1}+2\cdot
A_{2}=A_{3}+2\cdot A_{4})$. Now since $A$ is a sidon set,

$\Pr(A_{4}-A_{2}=k)=\Pr(A_{1}-A_{3}=k)=\begin{cases}1/n,\textrm{ if }k=0\\\
0,\textrm{ if }k\notin A-A\\\ 1/n^{2},\textrm{ otherwise}.\end{cases}$

Thus $\Pr(A_{1}+2\cdot A_{2}=A_{3}+2\cdot
A_{4})=\Pr(A_{1}-A_{3}=2(A_{4}-A_{2}))=1/n^{2}+K/n^{4}$, where $K$ is the
number of non-zero elements of $A-A$ which are double some other element of
$A-A$.

Now there are $n^{2}-n$ elements of $A-A$, but $A$ contains elements of both
parities (as $0\in A$ and $\mathrm{gcd}A=1$), so $A-A$ contains at least
$2(n-1)$ odd elements, so $K\leq n^{2}-3n+2$.

Thus

$\displaystyle|A+2\cdot A|$ $\displaystyle\geq 1/(1/n^{2}+(n^{2}-3n+2)/n^{4})$
$\displaystyle=n^{2}/(2-3/n+2/n^{2})$
$\displaystyle=(n^{2}/2)/(1-3/(2n)+1/n^{2})$
$\displaystyle\geq(n^{2}/2)(1+3/(2n)-1/n^{2})$
$\displaystyle=n^{2}/2+3n/4-1/2\geq(n^{2}+n)/2=|A+A|.$

∎

Similarly, one of the first things you might think to look for a
counterexample to Question 16 is a ”2-Sidon” set (ie one where $|A+2\cdot A|$
is as large as it can be). An easy way to construct such sets is a subset of
the Hypercube $\\{0,1\\}^{n}$. We can show that such sets in fact satisfy the
condition of Question 16

######  Lemma 19.

Suppose $A,B$ are subsets of the Hypercube $\\{0,1\\}^{n}$, then

$|A+2\cdot B|\leq\frac{\log 4}{\log 3}|A+B|.$

###### Proof.

Define a function $f:\mathbb{N}^{2}\to\mathbb{N}$ iteratively by: $f(i,j)=ij$
if $i\leq 1$ or $j\leq 1$ and otherwise
$f(i,j)=\min(f(i_{1},j_{1})+f(i_{2},j_{2})+\max(f(i_{1},j_{2}),f(i_{2},j_{1})):i_{1}+i_{2}=i,j_{1}+j_{2}=j)$.

We claim that for any finite subsets $A$, $B$ of the Hypercube, $|A+B|\geq
f(|A|,|B|)$. This is clearly true if $|A|\leq 1$ or $|B|\leq 1$. Otherwise,
assume the result is true for all smaller $|A|+|B|$. There is some coordinate
$i$ for which not every element of $A$ is identical. Then if $A_{0}=\\{x:x\in
A|x_{i}=0\\}$ and we define $A_{1},B_{0}$ and $B_{1}$ correspondingly, it is
clear that

$\displaystyle|A+B|$ $\displaystyle=|\\{x:x\in A+B|x_{i}=0\\}|+|\\{x:x\in
A+B|x_{i}=1\\}|+|\\{x:x\in A+B|x_{i}=2\\}|$
$\displaystyle=|A_{0}+B_{0}|+|(A_{0}+B_{1})\cup(A_{1}+B_{0})|+|A_{1}+B_{1}|$
$\displaystyle\geq|A_{0}+B_{0}|+|A_{1}+B_{1}|+\max(|A_{0}+B_{1}|,|A_{1}+B_{0}|)$
$\displaystyle\geq
f(|A_{0}|,|B_{0}|)+f(|A_{1}|,|B_{1}|)+\max(f(|A_{0}|,|B_{1}|),f(|A_{1}|,|B_{0}|))$
$\displaystyle\geq f(|A|,|B|),$

where the last two inequalities are the inductive hypothesis and the
definition of $f$ respectively.

We claim also that $f(i,j)\geq(ij)^{\beta}$ where $\beta=\frac{\log 3}{\log
4}$ for all $i,j$. This is clearly true if $i\leq 1$ or $j\leq 1$ and to prove
by induction we need to show that

$((i_{1}+i_{2})(j_{1}+j_{2}))^{\beta}\leq(i_{1}j_{1})^{\beta}+(i_{2}j_{2})^{\beta}+\max((i_{1}j_{2})^{\beta},(i_{2}j_{1})^{\beta})$

for all non-negative integers $i_{1},i_{2},j_{1},j_{2}$.

To that end, note that for $t>1$, $(t^{2\beta}-1)/(t-1)$ is the average value
of $(2\beta-1)x^{2\beta-1}$ over the range $x\in[1,t]$. Since $0<2\beta-1<1$,
this is a concave function and hence this average value is greater than
$(2\beta-1)((1+t)/2)^{2\beta-1}$. Further, since $(2\beta-1)>2^{2\beta-1}$,
this is larger than $(1+t)^{2\beta-1}$.

So it follows that for all $t>1$

$\displaystyle(t^{2\beta}-1)/(t-1)$ $\displaystyle>(1+t)^{2\beta-1}$
$\displaystyle(t^{2\beta}-1)$ $\displaystyle>(t-1)(1+t)^{2\beta-1}$
$\displaystyle(t^{\beta-1}-t^{-\beta-1})$
$\displaystyle>(t-1)(1+t)^{2\beta-1}/t^{\beta+1}$
$\displaystyle=\frac{(t-1)(1+t)}{t^{2}}\frac{(1+t)^{2\beta-2}}{t^{\beta-1}}$
$\displaystyle=(1-1/t^{2})(t+1/t+2)^{\beta-1}$

It then follows for all $r\geq 1$, since $r+1/r\geq 2$, that
$(t^{\beta-1}-t^{-\beta-1})>(1-1/t^{2})(t+1/t+r+1/r)^{\beta-1}$ for all $t>1$,
and hence that the function
$g(t,r)=t^{\beta}+t^{-\beta}+r^{\beta}-(t+1/t+r+1/r)^{\beta}$ is increasing in
the range $t\geq 1$ and therefore that $g(t,r)\geq
g(1,r)=2+r^{\beta}-(2+r+1/r)^{\beta}$.

Now $\beta<1$, so for all $r>1$

$\displaystyle(1+1/r)^{2\beta-2}$ $\displaystyle<1$
$\displaystyle(1+1/r)^{2\beta-1}$ $\displaystyle<1+1/r$
$\displaystyle(1+1/r)^{2\beta-1}(1-1/r)$ $\displaystyle<1$
$\displaystyle((1+1/r)^{2})^{\beta-1}(1-1/r^{2})$ $\displaystyle<1$
$\displaystyle(2+r+1/r)^{\beta-1}(1-1/r^{2})$ $\displaystyle<r^{\beta-1}$
$\displaystyle 0$ $\displaystyle<\beta
r^{\beta-1}-(1-1/r)^{2}(2+r+1/r)^{\beta}.$

It follows that $g(1,r)$ is increasing in $r$, so for all $r\geq 1,t\geq 1$,
$g(t,r)\geq g(1,r)=3-4^{\beta}=0$. Thus for all $t\geq 1$, $r\geq 1$,
$t^{\beta}+t^{-\beta}+r^{\beta}\geq(t+1/t+r+1/r)^{\beta}$. By replacing $t$
with $1/t$ if necessary, we see this inequality is true for $t>0$, $r\geq 1$.

Now if we let $t=\frac{i_{1}j_{1}}{\sqrt{i_{1}i_{2}j_{1}j_{2}}}$ and
$r=\frac{\max(i_{1}j_{2},i_{2}j_{1})}{\sqrt{i_{1}i_{2}j_{1}j_{2}}}$, we get
$(i_{1}j_{1})^{\beta}+(i_{2}j_{2})^{\beta}+\max(i_{1}j_{2},i_{2}j_{1})^{\beta}\geq((i_{1}+i_{2})(j_{1}+j_{2}))^{\beta}$
as was required. ∎

##  4 Fractional Dilates

We remind the reader of the definition of fractional dilates and their size -
a fractional dilate $\gamma$ is a map
$\gamma:\mathbb{Z}\to\mathbb{R}^{+}\cup\\{0\\}$ with a finite support. We
denote the size of a fractional dilate to be

$\lVert\gamma\rVert=\inf_{0<p<1}\sum_{n\in\mathbb{Z}}\gamma(n)^{p}.$

We describe a fractional dilate $\gamma$ as being spartan if
$\sum_{n\in\mathbb{Z}:\gamma(n)\neq 0}\gamma(n)\log\gamma(n)<0$, opulent if
$\sum_{n\in\mathbb{Z}:\gamma(n)\neq 0}\log\gamma(n)>0$ and comfortable if
neither of these holds. In the case that $\gamma$ is comfortable, there will
be a unique $p\in[0,1]$ with $\sum_{n\in\mathbb{Z}:\gamma(n)\neq
0}\gamma(n)^{p}\log\gamma(n)=0$. If we wish to emphasise, we will say that
$\gamma$ is $p$-comfortable. We will first prove Theorem 4 giving an alternate
characterisation of $\lVert\gamma\rVert$.

###### Proof of Theorem 4.

For a fixed $\gamma$ with support $S$, define a function
$f:[0,1]\to\mathbb{R}$ by $f(p)=\sum_{n\in S}\gamma(n)^{p}$. It is clear that
$f$ is doubly differentiable and that $f^{\prime\prime}(p)=\sum_{n\in
S}(\log\gamma(n))^{2}\gamma(n)^{p}>0$.

Now if $\gamma$ is spartan, then $f^{\prime}(1)=\sum_{n\in
S}\gamma(n)\log\gamma(n)<0$. It follows that $f^{\prime}(p)<0$ for all $0<p<1$
and hence
$\lVert\gamma\rVert=\inf_{0<p<1}f(p)=f(1)=\sum_{n\in\mathbb{Z}}\gamma(n)$.

If $\gamma$ is opulent, then $f^{\prime}(0)=\sum_{n\in S}\log\gamma(n)>0$. It
follows that $f^{\prime}(p)>0$ for all $0<p<1$ and hence
$\lVert\gamma\rVert=\inf_{0<p<1}f(p)=f(1)=|S|$.

Otherwise, $f^{\prime}(0)<0<f^{\prime}(1)$ and hence there is a unique $p$ for
which $0=f^{\prime}(p)=\sum_{n\in\mathbb{Z}:\gamma(n)\neq
0}\gamma(n)^{p}\log\gamma(n)$ and hence for which $\gamma$ is $p$-comfortable.
Then for this value of $p$,
$\lVert\gamma\rVert=f(p)=\sum_{n\in\mathbb{Z}}\gamma(n)^{p}$. ∎

We will give yet another alternate characterisation of $\lVert\gamma\rVert$,
if $\gamma$ has finite support. Recall that the entropy function
$H(y_{1},\ldots,y_{n})$ for positive numbers $y_{1},\ldots,y_{n}$ summing to 1
is defined to be

$H(y_{1},\ldots,y_{n})=-(y_{1}\log_{2}y_{1}+\ldots y_{n}\log_{2}y_{n}).$

######  Lemma 20.

Suppose $\gamma$ is a fractional dilate with finite support
$S=\\{s_{1},\ldots,s_{n}\\}$. Then

$\lVert\gamma\rVert=\max_{y_{1}+\ldots+y_{n}=1}2^{H(y_{1},\ldots,y_{n})}\min(1,\gamma(s_{1})^{y_{1}}\ldots\gamma(s_{n})^{y_{n}})$

###### Proof.

It is clear that for real $x$ and $0\leq p\leq 1$, that $\min(0,x)\leq px$ and
further that equality happens exactly when:

  1. 1.

$p=0$ and $x\geq 0$

  2. 2.

$p=1$ and $x\leq 0$

  3. 3.

$0<p<1$ and $x=0$.

Gibbs Inequality states that

$H(y_{1},\ldots,y_{n})\leq-\sum y_{i}\log_{2}z_{i}$

for any sequence of non-negative $z_{i}$ summing to 1 with equality only if
$y_{i}=z_{i}$ for all $i$.

For now fix $0\leq p\leq 1$ and let
$z_{i}=\frac{\gamma(s_{i})^{p}}{\sum_{i}\gamma(s_{i})^{p}}$. Clearly $\sum
z_{i}=1$.

Then for all non-negative sequences $y_{i}$ with $y_{1}+\ldots+y_{n}=1$

$\displaystyle
H(y_{1},\ldots,y_{n})+\min(0,\sum_{i}y_{i}\log_{2}\gamma(s_{i}))$
$\displaystyle\leq H(y_{1},\ldots,y_{n})+\sum_{i}py_{i}\log_{2}\gamma(s_{i})$
$\displaystyle=H(y_{1},\ldots,y_{n})+\sum_{i}y_{i}\log_{2}\gamma(s_{i})^{p}$
$\displaystyle=H(y_{1},\ldots,y_{n})+\sum_{i}y_{i}\log_{2}z_{i}+\log_{2}\sum_{i}\gamma(s_{i})^{p}$
$\displaystyle\leq\log_{2}\sum_{i}\gamma(s_{i})^{p},$

with the second inequality being Gibbs Inequality.

Raising 2 to both sides shows that

$2^{H(y_{1},\ldots,y_{n})}\min(1,\gamma(s_{i})^{y_{1}}\ldots\gamma(s_{n})^{y_{n}})\leq\sum_{i}\gamma(s_{i})^{p}$

for all $y_{1},\ldots,y_{n}$ and all $0\leq p\leq 1$. Equality here only
happens if equality happens in both the inequalities above, which is if
$\min(0,\sum_{i}y_{i}\log_{2}\gamma(s_{i}))=\sum_{i}py_{i}\log_{2}\gamma(s_{i})$
and if $y_{i}=z_{i}$ for all $i$.

To put it another way,
$\max_{y_{1}+\ldots+y_{n}=1}2^{H(y_{1},\ldots,y_{n})}\min(1,\gamma(s_{1})^{y_{1}}\ldots\gamma(s_{n})^{y_{n}})$
is bounded above by $\sum_{i}\gamma(s_{i})^{p}$ with equality only if
$\sum_{i}pz_{i}\log_{2}\gamma(s_{i})=\min(0,\sum_{i}z_{i}\log_{2}\gamma(s_{i}))$
where $z_{i}=\frac{\gamma(s_{i})^{p}}{\sum_{i}\gamma(s_{i})^{p}}$, which is
equivalent to the requirement that

$p\sum_{i}\gamma(s_{i})^{p}\log\gamma(s_{i})=\min(0,\sum_{i}\gamma(s_{i})^{p}\log\gamma(s_{i})).$

As discussed above, equality happens exactly when

  1. 1.

$p=0$ and $0<\sum_{i}\log\gamma(s_{i})$, which is the requirement for $\gamma$
to be opulent

  2. 2.

$p=1$ and $0>\sum_{i}\gamma(s_{i})\log\gamma(s_{i})$, which is the requirement
for $\gamma$ to be spartan

  3. 3.

$0<p<1$ and $\sum_{i}\gamma(s_{i})^{p}\log\gamma(s_{i})=0$, which is the
requirement that $\gamma$ to be $p$-comfortable.

Putting this all together, we see that

$\max_{y_{1}+\ldots+y_{n}=1}2^{H(y_{1},\ldots,y_{n})}\min(1,\gamma(s_{1})^{y_{1}}\ldots\gamma(s_{n})^{y_{n}}=\begin{cases}\sum_{n\in\mathbb{Z}}\gamma(n)\textrm{
if }\gamma\textrm{ is spartan},\\\ |\\{n:n\in\mathbb{Z},\gamma(n)\neq
0\\}|\textrm{ if }\gamma\textrm{ is opulent},\\\
\sum_{n\in\mathbb{Z}}\gamma(n)^{p}\textrm{ if }\gamma\textrm{ is
$p$-comfortable}.\end{cases}$

Comparing with Theorem 4, it is clear that this is equal to
$\lVert\gamma\rVert$. ∎

A fractional set is a fractional dilate $\alpha$ for which $\alpha(n)\leq 1$
for all $n\in Z$. It is clear that for $0<p<1$, $\alpha(n)^{p}\geq\alpha(n)$
for all $n\in\mathbb{Z}$ for a fractional set $\alpha$, and hence
$\lVert\alpha\rVert=\sum_{n\in\mathbb{Z}}\alpha(n)$. (It also follows
trivially from Theorem 4 since fractional sets are clearly spartan.) Given a
fractional set $\alpha$, let us say that a random set
$S_{n}\subseteq\mathbb{Z}^{n}$ is drawn from $\alpha^{n}$ if each element of
$\mathbb{Z}^{n}$ is chosen independently, and the probability that
$(i_{1},i_{2},\ldots,i_{n})$ is selected is
$\alpha(i_{1})\alpha(i_{2})\ldots\alpha(i_{n}).$

In this section we will consider two fractional sets $\alpha$ and $\beta$ and
let $S_{n},T_{n}\subseteq\mathbb{Z}^{n}$ be independently drawn from
$\alpha^{n}$ and $\beta^{n}$ respectively, and will show that
$\lim_{n\to\infty}(\mathbb{E}|S_{n}+T_{n}|)^{1/n}=\lVert\alpha+\beta\rVert$
where $\alpha+\beta$ denotes the fractional dilate defined by
$(\alpha+\beta)(n)=\sum_{i+j=n}\alpha(i)\beta(j)$. We will henceforth denote
$\alpha+\beta$ by $\gamma$. Further if $\gamma$ is spartan (in which case
$\lVert\gamma\rVert=\lVert\alpha\rVert\lVert\beta\rVert$), we prove that
$|S_{n}+T_{n}|$ is highly likely to be very close to this bound. In the next
section we consider sums and dilates of a set with itself.

When proving that $\lVert\gamma\rVert$ is a lower bound for the limit, we will
need the following technical lemma.

######  Lemma 21.

Let us suppose that $(X_{n})_{n=1}^{\infty}$ is a collection of random
variables, each of which can be written as the sum of independent Bernoulli
random variables and suppose that $\lim_{n\to\infty}(\mathbb{E}X_{n})^{1/n}$
exists and is equal to $t$. Then $\lim_{n\to\infty}\Pr(X_{n}>0)^{1/n}$ also
exists and is equal to $\min(1,t)$.

###### Proof.

We claim that if $X$ is a random variable which can be written as the sum of
independent Bernoulli random variables then
$\mathbb{E}X-\frac{(\mathbb{E}X)^{2}}{2}\leq\Pr(X>0)$. Indeed, write
$X=\sum_{i\in S}Z_{i}$ where each $i$ is Bernoulli, then

$(\mathbb{E}X)^{2}=\sum_{i\in S}\sum_{j\in S}E(Z_{i}Z_{j})\\\ \geq 2\sum_{i\in
S,j\in S,i>j}E(Z_{i}Z_{j})\\\ =2E(\binom{X}{2}),$

so
$\mathbb{E}X-\frac{(\mathbb{E}X)^{2}}{2}\leq\mathbb{E}(X-\binom{X}{2})\leq\mathbb{E}\mathbbm{1}_{X>0}=\Pr(X=0)$,
the last inequality being because $n-\binom{n}{2}\leq\mathbbm{1}_{n>0}$ for
all $n$.

Now if $t<1$, then since
$\mathbb{E}X_{n}-\Pr(X_{n}>0)\leq(\mathbb{E}X_{n})^{2}/2$, it follows that

$\limsup_{n\to\infty}(\mathbb{E}X_{n}-\Pr(X_{n}>0))^{1/n}\leq\limsup_{n\to\infty}(\frac{(\mathbb{E}X_{n})^{2}}{2})^{1/n}=t^{2}$

and hence $\Pr X_{n}>0$ is the difference between $\mathbb{E}X_{n}$ (which is
asymptotically $t^{n}$) and $\mathbb{E}X_{n}-\Pr X_{n}$ (which is
asymptotically $t^{2n}$). Since $t<1$, it follows that $(\Pr X_{n})^{1/n}\to
t$.

Given any $u<1$, we can find a collection of random variables $Y_{n}$
satisfying the conditions of the Lemma and with
$\lim(\mathbb{E}Y_{n})^{1/n}=u$ and $\Pr(X_{n}>0)>\Pr(Y_{n}>0)$ (simply reduce
the probabilities of the underlying independent Bernoulli random variables
being 1 until we get the required expectation). Then
$u=\lim_{n\to\infty}\Pr(Y_{n}>0)^{1/n}<\liminf_{n\to\infty}\Pr(X_{n}>0)^{1/n}$.
Since this is true for all $u<1$, $\lim_{n\to\infty}\Pr(X_{n}>0)^{1/n}=1$. ∎

Let us first prove the upper bound of the two-set part of Theorem 5. Recall
that the multiplicity $\mathrm{Mult}_{A+k\cdot B}(x)$ is defined to be the
number of ways of writing $x=y+kz$ where $y\in A$ and $z\in B$.

######  Theorem 22.

Let $\alpha$ and $\beta$ be fractional sets, and suppose
$S_{n},T_{n}\subseteq\mathbb{Z}^{n}$ are drawn from $\alpha^{n}$ and
$\beta^{n}$ respectively and let $\gamma=\alpha+\beta$. Then

$\mathbb{E}|S_{n}+T_{n}|\leq\lVert\gamma\rVert^{n}$

###### Proof.

Let $X$ be the support of $\gamma$. Then the possible elements of
$S_{n}+T_{n}$ are the elements of $X^{n}$. Given a particular element $x\in
X^{n}$, the probability that $x\in S_{n}+T_{n}$ is the probability that
$\mathrm{Mult}_{S_{n}+T_{n}}(x)>0$, which is bounded above by
$\min(1,\mathbb{E}\textrm{ }\mathrm{Mult}_{S_{n}+T_{n}}(x))$ and hence by
$(\mathbb{E}\textrm{ }\mathrm{Mult}_{S_{n}+T_{n}}(x))^{p}$ for all $0\leq
p\leq 1$.

Now if the coefficients of $x$ are $x=(x_{1},\ldots,x_{k})\in x^{n}$, the
expected value of the multiplicity of $x$ in $S_{n}+T_{n}$ is

$\displaystyle\mathbb{E}\textrm{ }\mathrm{Mult}_{S_{n}+T_{n}}(x)$
$\displaystyle=\Sigma_{z_{1}+y_{1}=x_{1},\ldots,z_{n}+y_{n}=x_{n}}\alpha(z_{1})\ldots\alpha(z_{n})\beta(y_{1})\ldots\beta(y_{n})$
$\displaystyle=(\Sigma_{z_{1}+y_{1}=x_{1}}\alpha(z_{1})\beta(y_{1}))\ldots(\Sigma_{z_{n}+y_{n}=x_{n}}\alpha(z_{n})\beta(y_{n}))$
$\displaystyle=\gamma(x_{1})\gamma(x_{2})\ldots\gamma(x_{n}).$

It follows that the expected size of $S_{n}+T_{n}$ is at most

$\displaystyle\mathbb{E}|S_{n}+T_{n}|$ $\displaystyle=\sum_{x\in
X^{n}}\Pr(x\in S_{n}+T_{n})$ $\displaystyle\leq\sum_{x\in
X^{n}}(\mathbb{E}\textrm{ }\mathrm{Mult}_{S_{n}+T_{n}}(x))^{p}$
$\displaystyle=\sum_{(x_{1},\ldots,x_{k})\in
X^{n}}\gamma(x_{1})^{p}\gamma(x_{2})^{p}\ldots\gamma(x_{k})^{p}$
$\displaystyle=(\sum_{x\in X}\gamma(x)^{p})^{n}$

for all $0\leq p\leq 1$.

Since $\lVert\gamma\rVert=\inf_{0<p<1}\sum_{x}\gamma(x)^{p}$, the result
follows. ∎

As a step towards the equivalent lower bound, we will use Lemma 21 to
calculate the asymptotic behaviour of the probability of vectors lying in
$S_{n}+T_{n}$.

######  Corollary 23.

Let $\alpha$ and $\beta$ be fractional sets, and suppose
$S_{n},T_{n}\subseteq\mathbb{Z}^{n}$ are drawn from $\alpha^{n}$ and
$\beta^{n}$ respectively and let $\gamma=\alpha+\beta$. Suppose also that
$x_{1},\ldots,x_{N}$ are integers, that $y_{1},\ldots,y_{N}$ are non-negative
numbers summing to 1 and that for each $n$ we have non-negative integers
$z_{1,n},\ldots,z_{N,n}$ summing to $n$ such that for each $i$,
$\lim_{n\to\infty}z_{i,n}/n=y_{i}$. Let
$t=\gamma(x_{1})^{y_{1}}\ldots\gamma(x_{N})^{y_{N}}$.

Suppose finally that for each $n$, $v_{n}$ is an $n$-dimensional vector such
that $z_{i,n}$ of the coordinates are equal to $x_{i}$. Then

$lim_{n\to\infty}\Pr(v_{n}\in A_{n}+B_{n})^{1/n}=\min(1,t).$

###### Proof.

Let vector $X_{n}=\mathrm{Mult}_{A_{n}+B_{x}}(v_{n})$. As in the proof of
Theorem 19,

$\mathbb{E}X_{n}=\gamma(x_{1})^{z_{1,n}}\gamma(x_{2})^{z_{2,n}}\ldots\gamma(x_{N})^{z_{N,n}},$

so $\lim_{n\to\infty}(\mathbb{E}X_{n})^{1/n}\to t$.

Furthermore $X_{n}$ can be written as
$\sum_{z\in\mathbb{Z}^{n}}\mathbbm{1}_{z\in A_{n},v_{n}-z\in B_{n}}$, which
are independent Bernoulli random variables. The result therefore follows from
applying Lemma 21 to the random variables $X_{n}$. ∎

######  Corollary 24.

Let $\alpha$ and $\beta$ be fractional sets with finite support, and suppose
$S_{n},T_{n}\subseteq\mathbb{Z}^{n}$ are drawn from $\alpha^{n}$ and
$\beta^{n}$ respectively and let $\gamma=\alpha+\beta$.

Then $\lim_{n\to\infty}\mathbb{E}|S_{n}+T_{n}|^{1/n}=\lVert\gamma\rVert$.

###### Proof.

By Lemma 20, if $S=\\{s_{1},\ldots,s_{N}\\}$ is the support of $\gamma$, there
exist non-negative numbers $y_{1},\ldots,y_{N}$ summing to 1 with

$\lVert\gamma\rVert=2^{H(y_{1},\ldots,y_{N})}\min(1,\gamma(s_{1})^{y_{1}}\ldots\gamma(s_{N})^{y_{N}}).$

Then we can choose integers $z_{1}+\ldots+z_{N}=n$ with $z_{i}/n\to y_{i}$ for
each $1\leq i\leq N$. There are $\binom{n}{z_{1},z_{2},\ldots,z_{N}}$
$n$-dimensional vectors with $z_{k}$ of each coordinate $i_{k}$ and they all
have the same probability $p_{n}$ of being in $A_{n}+B_{n}$, and by Lemma 23,
$p_{n}^{1/n}\to\min(1,c_{i_{1}}^{y_{1}}\ldots c_{i_{N}}^{y_{N}})$.

It is well known that $\binom{n}{z_{1},z_{2},\ldots,z_{N}}^{1/n}\to
2^{H(y_{1},\ldots,y_{n})}$.

It follows that

$\displaystyle\liminf_{n\to\infty}\mathbb{E}|A_{n}+B_{n}|^{1/n}$
$\displaystyle\geq\lim_{n\to\infty}(\binom{n}{z_{1},z_{2},\ldots,z_{N}}p_{n})^{1/n}$
$\displaystyle=2^{H(y_{1},y_{2},\ldots,y_{n})}\min(1,\gamma(i_{1})^{y_{1}}\ldots\gamma(i_{n})^{y_{N}})$
$\displaystyle=\lVert\gamma\rVert.$

By Theorem 22, it follows that the limit of $\mathbb{E}|A_{n}+B_{n}|^{1/n}$
exists and is equal to $\lVert\gamma\rVert$. ∎

######  Corollary 25.

Let $\alpha$ and $\beta$ be fractional sets with finite support, and suppose
$S_{n},T_{n}\subseteq\mathbb{Z}^{n}$ are drawn from $\alpha^{n}$ and
$\beta^{n}$ respectively and let $\gamma=\alpha+\beta$. Suppose that $\gamma$
is spartan (so $\lVert\gamma\rVert=\lVert\alpha\rVert\lVert\beta\rVert$.)

Then $\mathbb{E}|S_{n}||T_{n}|-|S_{n}+T_{n}|=o(|S_{n}||T_{n}|)$, so the
probability that $|S_{n}+T_{n}|$ is at least $0.99\lVert\gamma\rVert^{n}$
tends to 1 as $n$ tends to infinity.

###### Proof.

As in the Proof of Lemma 21, we claim that if $X$ is a random variable which
can be written as the sum of independent Bernoulli random variables then
$\mathbb{E}X-\frac{(\mathbb{E}X)^{2}}{2}\leq\Pr(X>0)$. In particular, for all
$v$, $\mathrm{Mult}_{S_{n}+T_{n}}(v)$ can be written in such a fashion, so

$\mathbb{E}\mathrm{Mult}_{S_{n}+T_{n}}(v)-\Pr(\mathrm{Mult}_{S_{n}+T_{n}}(v)>0)\leq(\mathbb{E}\mathrm{Mult}_{S_{n}+T_{n}}(v))^{2}/2\leq(\mathbb{E}\mathrm{Mult}_{S_{n}+T_{n}}(v))^{2}.$

Since it is clear that the left hand side is also at most
$\mathbb{E}\mathrm{Mult}_{S_{n}+T_{n}}(v)$, it follows that

$\mathbb{E}\mathrm{Mult}_{S_{n}+T_{n}}(v)-\Pr(\mathrm{Mult}_{S_{n}+T_{n}}(v)>0)\leq(\mathbb{E}\mathrm{Mult}_{S_{n}+T_{n}}(v))^{p}\textrm{
for all }1\leq p\leq 2.$

Then $\mathbb{E}|S_{n}||T_{n}|-|S_{n}+T_{n}|$ is the sum over all $v$ of the
expected value of $\mathbb{E}\textrm{
}\mathrm{Mult}_{S_{n}+T_{n}}(v)-\Pr(\mathrm{Mult}_{S_{n}+T_{n}}(v)>0)$, which
is at most the sum over all $v$ of
$\mathbb{E}(\mathrm{Mult}_{S_{n}+T_{n}}(v))^{p}$ for all $1\leq p\leq 2$. If
$v$ is $(v_{1},\ldots,v_{n})$ then
$\mathbb{E}(\mathrm{Mult}_{S_{n}+T_{n}}(v))=\gamma(v_{1})\ldots\gamma(v_{n})$.

It follows that

$\mathbb{E}|S_{n}||T_{n}|-|S_{n}+T_{n}|\leq\sum_{v_{1},v_{2},\ldots,v_{n}}\gamma(v_{1})^{p}\ldots\gamma(v_{n})^{p}=(\sum_{v}\gamma(v)^{p})^{n}$

for all $1\leq p\leq 2$.

Since $\gamma$ is spartan, the function $p\to\sum_{v}\gamma(v)^{p}$ is
decreasing for all $p\leq 1$ and beyond, so for all $\epsilon>0$,
$\sum_{v}\gamma(v)^{1+\epsilon}<\lVert\gamma\rVert$. Thus there exists
$\epsilon$ such that
$\mathbb{E}|S_{n}||T_{n}|-|S_{n}+T_{n}|\leq(\lVert\gamma\rVert-\epsilon)^{n}$
for all $n$. ∎

##  5 The rainbow connection

Let $\alpha$ be a fractional set and let $p$ be a non-zero integer. Let
$\gamma:=\alpha+p\cdot\alpha$ denote the fractional dilate defined by
$\gamma(n)=\sum_{i+pj=n}\alpha(i)\alpha(j)$. In this section we will show that
if $S_{n}$ is a random set drawn from $\alpha^{n}$ then
$\lim_{n\to\infty}(\mathbb{E}|S_{n}+p\cdot S_{n}|)^{1/n}$ is
$\max(\lVert\alpha\rVert,\lVert\gamma\rVert)$.

First let us deal with the easy case.

######  Lemma 26.

If $\lVert\alpha\rVert\leq 1$ then $\lim_{n\to\infty}(\mathbb{E}|S_{n}+p\cdot
S_{n}|)^{1/n}=\lVert\alpha\rVert$. On the other hand, if
$\lVert\alpha\rVert>1$, then $\lVert\gamma\rVert\geq\lVert\alpha\rVert$.

###### Proof.

Clearly $\mathbb{E}|S_{n}+p\cdot
S_{n}|\geq\mathbb{E}|S_{n}|=\lVert\alpha\rVert^{n}$. Further,
$\mathbb{E}|S_{n}+p\cdot
S_{n}|\leq\mathbb{E}|S_{n}|^{2}=(\mathbb{E}|S_{n}|)^{2}+\mathrm{Var}|S_{n}|\leq(\mathbb{E}|S_{n}|)^{2}+\mathbb{E}|S_{n}|=\lVert\alpha\rVert^{2n}+\lVert\alpha\rVert^{n}$.

Thus if $\lVert\alpha\rVert\leq 1$ then
$\lim_{n\to\infty}(\mathbb{E}|S_{n}+p\cdot S_{n}|)^{1/n}=\lVert\alpha\rVert$.

Let $S_{n}$ be drawn from $\alpha^{n}$. $|S_{n}|$ can be written as the sum of
independent Bernoulli random variables and
$\lim_{n\to\infty}(\mathbb{E}|S_{n}|)^{1/n}=\lVert\alpha\rVert>1$. Thus by
Lemma 21, $\lim_{n\to\infty}\Pr(|S_{n}|>0)^{1/n}=1$.

Let $T_{n}$ be independently drawn from $\alpha^{n}$. By Corollary 24,
$\lVert\gamma\rVert=\lim_{n\to\infty}(\mathbb{E}|S_{n}+p\cdot T_{n}|)^{1/n}$,
but $|S_{n}+p\cdot T_{n}|\geq|T_{n}|$ whenever $S_{n}$ is non-empty, so
$|S_{n}+p\cdot T_{n}|\geq|T_{n}|\mathbbm{1}_{|S_{n}|>0}$. Since $|S_{n}|$ and
$|T_{n}|$ are independent, it follows that $\mathbb{E}|S_{n}+p\cdot
T_{n}|\geq\mathbb{E}|T_{n}|\Pr(|S_{n}|>0)$, whence

$\lVert\gamma\rVert=\lim_{n\to\infty}(\mathbb{E}|S_{n}+T_{n}|)^{1/n}\geq\lim_{n\to\infty}(\mathbb{E}|T_{n}|\Pr(|S_{n}|>0)^{1/n}=\lVert\alpha\rVert.$

∎

In the $\lVert\alpha\rVert>1$ case we will prove that
$\lim_{n\to\infty}(\mathbb{E}|S_{n}+p\cdot S_{n}|)^{1/n}=\lVert\gamma\rVert$
by comparing the size of $S_{n}+p\cdot S_{n}$ with $S_{n}+p\cdot T_{n}$ where
$T_{n}$ is a random set drawn from $\alpha^{n}$ independently from $S_{n}$.
Let us say that a vector $v\in\mathbb{Z}^{n}$ is rainbow if it has at least
one copy of each coefficient from the support $\\{x_{1},\ldots,x_{k}\\}$ of
$\gamma$, and let $R_{n}$ denote the set of rainbow vectors in
$\mathbb{Z}^{n}$.

######  Theorem 27.

If $p\neq 1$ and $v$ is a rainbow vector, the probabilities that $v\in
S_{n}+p\cdot S_{n}$ and $v\in S_{n}+p\cdot T_{n}$ are the same. Hence
$\mathbb{E}|(S_{n}+p\cdot S_{n})\cap R_{n}|=\mathbb{E}|(S_{n}+p\cdot
T_{n})\cap R_{n}|$.

###### Proof.

There are a finite number of $x$ such that $\Pr(x\in S_{n},v-px\in S_{n})>0$.
Let us denote the set of all such $x$ by $S$.

We claim that there exist distinct $a,b$ in the support of $\alpha$ such that
$a+pb$ cannot be expressed in any other way as $a^{\prime}+pb^{\prime}$ where
$a^{\prime}$ and $b^{\prime}$ are in the support of $\alpha$. Indeed if $p<0$,
let $a$ and $b$ be the largest and smallest elements, respectively, of the
support of $\alpha$. If $a^{\prime}$ and $b^{\prime}$ are any elements of the
support of $\alpha$, then $a\geq a^{\prime}$ and $b\leq b^{\prime}$, so
$a+pb\geq a^{\prime}+pb^{\prime}$ with equality only if $a=a^{\prime}$ and
$b=b^{\prime}$. Similarly, if $p>1$, we can take $a$ and $b$ to be the second-
largest and largest elements, respectively, of the support of $\alpha$. If
$a^{\prime}$ and $b^{\prime}$ are any elements of the support of $\alpha$ with
$a^{\prime}+pb^{\prime}=a+pb$ but with $a^{\prime}\neq a$ and $b^{\prime}\neq
b$, it must follow that $b^{\prime}<b$ (as $b$ is the largest element), whence
$b^{\prime}\leq a$ and hence $a^{\prime}+pb^{\prime}\leq
b+pa<b+pa+(p-1)(b-a)=a+kb$, forming a contradiction.

Now since $v$ is a rainbow vector, it contains a coordinate equal to $a+kb$,
say $v_{i}=a+kb$. Then it follows that for all $x\in S$, $x_{i}=a$ and
$(v-px)_{i}=b$, and therefore for all $x\in S$, $v-px\notin S$ (as $a\neq b$).

In particular for each $x\in S$, $x\neq v-px$ and so the events $x\in S_{n}$
and $v-px\in S_{n}$ are independent, and hence $\Pr(x\in S_{n},v-px\in
S_{n})=\Pr(x\in S_{n})\Pr(v-px\in S_{n})$. Furthermore, since the sets
$\\{x,v-px\\}$ for all $x\in S$ are disjoint, these events are all
independent, so

$\displaystyle\Pr(v\in S_{n}+S_{n})$ $\displaystyle=1-\prod_{x\in
S}(1-\Pr(x\in S_{n},v-px\in S_{n}))$ $\displaystyle=1-\prod_{x\in
S}(1-\Pr(x\in S_{n})\Pr(v-px\in S_{n}))$ $\displaystyle=1-\prod_{x\in
S}(1-\Pr(x\in S_{n})\Pr(v-px\in T_{n}))$ $\displaystyle=1-\prod_{x\in
S}(1-\Pr(x\in S_{n},v-px\in T_{n}))$ $\displaystyle=\Pr(v\in S_{n}+T_{n}).$

Since $\mathbb{E}|(S_{n}+p\cdot S_{n})\cap R_{n}|$ is the sum of $\Pr(v\in
S_{n}+p\cdot S_{n})$ over all rainbow $v$, the equality of expectations
follows. ∎

This gives us a good bound on the size of $\mathbb{E}|S_{n}+p\cdot S_{n}|$
because it usually happens that all but exponentially few of the elements of
$S_{n}+p\cdot T_{n}$ are rainbow.

######  Theorem 28.

There exists an $\epsilon>0$ such that the expected size of
$\mathbb{E}|(S_{n}+p\cdot T_{n})\setminus
R_{n}|=o((\lVert\gamma\rVert-\epsilon)^{n})$.

###### Proof.

Let $p\in[0,1]$ be such that $\lVert\gamma\rVert=\sum_{z:\gamma(z)\neq
0}\gamma(z)^{p}$, and let $\alpha=\min\\{\gamma(z):\gamma(z)\neq 0\\}$.

Let $z$ be any value with $\gamma(z)\neq 0$. By a similar argument to Theorem
22, for all $0\leq q\leq 1$, the expected number of elements of $S_{n}+p\cdot
T_{n}$ with no coefficient equal to $z$ is at most $(\sum_{w\neq
z}\gamma(w)^{q})^{n}$. In particular, taking $q=p$, it is at most
$(\lVert\gamma\rVert-\alpha^{p})^{n}$.

If there are $N$ elements of the support of $\gamma$,
$\mathbb{E}|(S_{n}+p\cdot T_{n})\setminus R_{n}|$ is therefore at most
$N(\lVert\gamma\rVert-\alpha^{p})^{n}$, which is
$o((\lVert\gamma\rVert-\epsilon)^{n}$ for any $\epsilon<\alpha^{p}$. ∎

######  Corollary 29.

If $\lVert\alpha\rVert>1$ and $p\neq 1$, then
$\lim_{n\to\infty}\mathbb{E}|S_{n}+p\cdot
S_{n}|^{1/n}=\lVert\alpha+p\cdot\alpha\rVert$. Furthermore, if
$\alpha+p\cdot\alpha$ is spartan, $\mathbb{E}|S_{n}|^{2}-|S_{n}+p\cdot
S_{n}|=o(\mathbb{E}|S_{n}|^{2})$.

###### Proof.

By Theorem 22, $\mathbb{E}|S_{n}+p\cdot
S_{n}|\leq\lVert\alpha+p\cdot\alpha\rVert^{n}$.

Further, by Theorem 27,

$\displaystyle\mathbb{E}|S_{n}+p\cdot S_{n}|$
$\displaystyle\geq\mathbb{E}|(S_{n}+p\cdot S_{n})\cap R_{n}|$
$\displaystyle=\mathbb{E}|(S_{n}+p\cdot T_{n})\cap R_{n}|$
$\displaystyle=\mathbb{E}|S_{n}+p\cdot T_{n}|-\mathbb{E}|(S_{n}+p\cdot
T_{n})\setminus R_{n}|.$

By Corollary 24, $\lim_{n\to\infty}\mathbb{E}|S_{n}+p\cdot
T_{n}|^{1/n}\to\lVert\alpha+p\cdot\alpha\rVert$ and by Theorem 28,
$\mathbb{E}|(S_{n}+p\cdot T_{n})\setminus
R_{n}|=o((\lVert\alpha+p\cdot\alpha\rVert-\epsilon)^{n})$, so it follows that
$\liminf_{n\to\infty}\mathbb{E}|S_{n}+p\cdot
S_{n}|^{1/n}\geq\lVert\alpha+p\cdot\alpha\rVert$ and hence
$\lim_{n\to\infty}\mathbb{E}|S_{n}+p\cdot
S_{n}|^{1/n}=\lVert\alpha+p\cdot\alpha\rVert$.

Further, if $\alpha+p\cdot\alpha$ is spartan,
$\mathbb{E}|S_{n}|^{2}-|S_{n}+p\cdot S_{n}|$ can be expressed as:

$\displaystyle\mathbb{E}|S_{n}|^{2}-|S_{n}+p\cdot S_{n}|$
$\displaystyle=\mathbb{E}|S_{n}|^{2}-(\mathbb{E}|S_{n}|)^{2}$ (1)
$\displaystyle+(\mathbb{E}|S_{n}|)^{2}-\mathbb{E}|S_{n}||T_{n}|$ (2)
$\displaystyle+\mathbb{E}|S_{n}||T_{n}|-|S_{n}+p\cdot T_{n}|$ (3)
$\displaystyle+\mathbb{E}|(S_{n}+p\cdot T_{n})\setminus R_{n}|$ (4)
$\displaystyle+\mathbb{E}|(S_{n}+p\cdot T_{n})\cap
R_{n}|-\mathbb{E}|(S_{n}+p\cdot S_{n})\cap R_{n}|$ (5)
$\displaystyle-\mathbb{E}|(S_{n}+p\cdot S_{n})\setminus R_{n}|.$ (6)

The first line is $\mathrm{Var}|S_{n}|$ which (since $S_{n}$ is the sum of
independent Bernoulli variables) is at most
$\mathbb{E}|S_{n}|=o(\mathbb{E}|S_{n}|^{2})$. The second is clearly 0. The
third is $o(\mathbb{E}|S_{n}|^{2})$ by Corollary 25, the fourth and sixth by
Theorem 28 and the fifth is zero by Theorem 27. ∎

######  Theorem 30.

If $v$ is a rainbow vector, the probabilities that $v\in S_{n}+\cdot S_{n}$
and $v\in S_{n}+^{<}T_{n}$ are the same and hence
$\mathbb{E}|(S_{n}+S_{n})\cap R_{n}|=\mathbb{E}|(S_{n}+^{<}T_{n})\cap R_{n}|$.

###### Proof.

Similar to Theorem 27, the expectation follows directly from the probability.
Also, since $v$ is rainbow, $v/2$ is not in the support of $\alpha$. There are
a finite number of $x$ such that $\Pr(x\in S_{n},v-x\in S_{n})>0$. Let us
denote the set of all such $x$ by $S$.

Thus

$\displaystyle\Pr(v\in S_{n}+S_{n})$ $\displaystyle=\Pr(\exists x:x\in S,x\in
S_{n},v-x\in S_{n})$ $\displaystyle=\Pr(\exists x:x\in S,x\in S_{n},v-x\in
S_{n},x<(v-x))$ $\displaystyle=1-\prod_{x:x\in S,x<(v-x)}(1-\Pr(x\in
S_{n})\Pr(v-x\in S_{n}))$ $\displaystyle=1-\prod_{x:x\in S,x<(v-x)}(1-\Pr(x\in
S_{n})\Pr(v-x\in T_{n}))$ $\displaystyle=\Pr(v\in S_{n}+^{<}T_{n}).$

∎

######  Corollary 31.

If $\lVert\alpha\rVert>1$, then
$\lim_{n\to\infty}\mathbb{E}|S_{n}+S_{n}|^{1/n}=\lVert\alpha+\alpha\rVert$.
Furthermore, if $\alpha+\alpha$ is spartan,
$\mathbb{E}\frac{|S_{n}|^{2}}{2}-|S_{n}+S_{n}|=o(\mathbb{E}|S_{n}|^{2})$

###### Proof.

By Theorem 22, $\mathbb{E}|S_{n}+S_{n}|\leq\lVert\alpha+\alpha\rVert^{n}$.

Further, by Theorem 30,

$\displaystyle\mathbb{E}|S_{n}+S_{n}|$
$\displaystyle\geq\mathbb{E}|(S_{n}+S_{n})\cap R_{n}|$
$\displaystyle=\mathbb{E}|(S_{n}+^{<}T_{n})\cap R_{n}|$
$\displaystyle=\mathbb{E}|S_{n}+^{<}T_{n}|-\mathbb{E}|(S_{n}+^{<}T_{n})\setminus
R_{n}|.$

Now $S_{n}+T_{n}=(S_{n}+^{<}T_{n})\cup(T_{n}+^{<}S_{n})$ and these two sets
have the same distribution, so
$\mathbb{E}|S_{n}+^{<}T_{n}|\geq\frac{1}{2}\mathbb{E}|S_{n}+T_{n}|$. Thus by
Corollary 24 and Theorem 28,
$\lim_{n\to\infty}\mathbb{E}|S_{n}+S_{n}|^{1/n}=\lVert\alpha+\alpha\rVert$.

Furthermore,

$\displaystyle\mathbb{E}|S_{n}+S_{n}|$
$\displaystyle=\mathbb{E}|(S_{n}+S_{n})\cup
R_{n}|+\mathbb{E}|(S_{n}+S_{n})\setminus R_{n}|$
$\displaystyle=\mathbb{E}|(S_{n}+^{<}T_{n})\cup
R_{n}|+o(\lVert\alpha\rVert^{2n})$
$\displaystyle=\mathbb{E}|(S_{n}+^{<}T_{n})|+o(\lVert\alpha\rVert^{2n})$
$\displaystyle\geq\frac{1}{2}\mathbb{E}|S_{n}+T_{n}|+o(\lVert\alpha\rVert^{2n})$
$\displaystyle=\frac{1}{2}\mathbb{E}|S_{n}|\mathbb{E}|T_{n}|+o(\lVert\alpha\rVert^{2n})$
$\displaystyle=\frac{1}{2}\mathbb{E}|S_{n}|\mathbb{E}|S_{n}|+o(\lVert\alpha\rVert^{2n})$
$\displaystyle=\frac{1}{2}\mathbb{E}|S_{n}|^{2}+\frac{1}{2}\mathrm{Var}|S_{n}|+o(\lVert\alpha\rVert^{2n})=\frac{1}{2}\mathbb{E}|S_{n}|^{2}+o(\lVert\alpha\rVert^{2n})$

Since clearly $|S_{n}+S_{n}|\leq\frac{1}{2}(|S_{n}|^{2}+|S_{n}|)$ it follows
that
$\mathbb{E}|S_{n}+S_{n}|\leq\frac{1}{2}\mathbb{E}|S_{n}|^{2}+o(\lVert\alpha\rVert^{2n})$,
so we are done. ∎

##  6 Ruzsa’s Method and Hennecart, Robert and Yudin’s Construction

In [10], Ruzsa constructs sets by taking a fixed probability $0<q<1$ and a
finite set $S$ and selecting subsets of $\mathbb{Z}^{n}$ by taking each
element of $S^{n}$ independently with probability $q^{n}$. In our terminology,
this is the same as drawing from $\alpha^{n}$ where $\alpha$ is the fractional
dilate equal to $q\mathbbm{1}_{S}$.

Let us suppose that there are $M$ elements of $S$ and $N$ elements of
$S+k\cdot S$. Let us label the elements of $S+k\cdot S$ as
$\\{x_{1},\ldots,x_{N}\\}$. For $1\leq i\leq N$, let us write $\lambda_{i}$
for the number of ways of writing $x_{i}$ as $s_{1}+ks_{2}$ where
$s_{1},s_{2}\in S$. We say $\lambda_{i}$ is the multiplicity of $x_{i}$ and
say the unordered set $\\{\lambda_{1},\lambda_{2},\ldots,\lambda_{N}\\}$ is
the multiplicity spectrum of $S+k\cdot S$. Note that
$\sum_{i=1}^{N}\lambda_{i}=M^{2}$. It is clear that

$\alpha+k\cdot\alpha(x)=\begin{cases}0\textrm{ if }x\notin S+k\cdot S,\\\
q^{2}\lambda_{i}\textrm{ if }x=x_{i}.\end{cases}$

Then we can rewrite the results of Theorem 4 as

$\lVert\alpha+k\cdot\alpha\rVert=\begin{cases}(qM)^{2}\textrm{ if
}q^{2}<1/\prod_{i}\lambda_{i}^{\frac{\lambda_{i}}{\sum_{j}\lambda_{j}}},\\\
N\textrm{ if }q^{2}>1/\prod_{i}\lambda_{i}^{1/N},\\\
q^{2p}\sum_{i}\lambda_{i}^{p}\textrm{ if
}q^{2}=1/\prod_{i}\lambda_{i}^{\frac{\lambda_{i}^{p}}{\sum_{j}\lambda_{j}^{p}}}.\\\
\end{cases}$

Before proceeding into the Hennecart, Robert and Yudin construction, we first
give an easier example of the addition and subtraction of the set
$\\{0,1,3\\}$.

######  Claim 32.

For all $\epsilon>0$, there exists a set $S$ with $|S-S|>|S|^{2-\epsilon}$ and
$|S+S|<|S|^{1.9364+\epsilon}$.

###### Proof.

Let $S=\\{0,1,3\\}$ and let $\frac{1}{3}<q<1$ be some fixed probability, and
let $S_{n}$ be a random subset of $S^{n}$ chosen by choosing each element of
$S$ with probability $q^{n}$.

Then $S+S=\\{0,2,6,1,3,4\\}$ with corresponding multiplicities
$\\{1,1,1,2,2,2\\}$. As such, the limit of $\mathbb{E}|S_{n}+S_{n}|^{1/n}$ as
$n\to\infty$ is

$\lVert\alpha+\alpha\rVert=\begin{cases}(3q)^{2}\textrm{ if
}q<\frac{1}{2}^{\frac{1}{3}},\\\ 6\textrm{ if }q>\frac{1}{2}^{\frac{1}{4}},\\\
3q^{2p}(1+2^{p})\textrm{ if }q=\frac{1}{2}^{\frac{2^{p}}{2(1+2^{p})}}.\\\
\end{cases}$

.

On the other hand $S-S=\\{-3,-2,-1,0,1,2,3\\}$ with corresponding
multiplicities $\\{1,1,1,3,1,1,1\\}$, and so the limit of
$\mathbb{E}|S_{n}-S_{n}|^{1/n}$ as $n\to\infty$ is

$\lVert\alpha-\alpha\rVert=\begin{cases}(3q)^{2}\textrm{ if
}q<\frac{1}{3}^{\frac{1}{6}},\\\ 7\textrm{ if
}q>\frac{1}{3}^{\frac{1}{14}},\\\ q^{2p}(6+3^{p})\textrm{ if
}q=\frac{1}{3}^{\frac{3^{p}}{2(6+3^{p})}}.\\\ \end{cases}$

.

Now $3^{4}=81>64=2^{6}$ so it follows that
$\frac{1}{2}^{\frac{1}{4}}>\frac{1}{3}^{\frac{1}{6}}$. Thus if we take $q$
just below $\frac{1}{2}^{\frac{1}{4}}$, it will follow that
$\lVert\alpha+\alpha\rVert=6$ and $\lVert\alpha-\alpha\rVert=(3q)^{2}$.

Furthermore, since $\alpha-\alpha$ will be spartan, it will actually follow
that $\mathbb{E}|S_{n}|^{2}-|S_{n}-S_{n}|=o((3q)^{2n})$, so we get a set
$S_{n}$ for which $|S_{n}|$ is very close to $(3q)^{n}$, $|S_{n}-S_{n}|$ is
very close to $(3q)^{2n}$ and $|S_{n}+S_{n}|$ is at most $6^{n}$.

Thus, for any $\epsilon$ we find a set $S$ with $|S-S|>|S|^{2-\epsilon}$ and
$|S+S|<|S|^{\frac{\log 6}{\log 3q}+\epsilon}$, where $q$ can be chosen
arbitrarily close to $\frac{1}{2}^{\frac{1}{4}}$, so $\frac{\log 6}{\log 3q}$
can be less than 1.93647. ∎

In a 1999 paper [3], Hennecart, Robert and Yudin gave a construction of sets
$A_{k,d}\in\mathbb{Z}^{d}$ for which $|A_{k,d}-A_{k,d}|$ was a lot bigger than
$|A_{k,d}+A_{k,d}|$. Their construction was

$A_{k,d}=\\{(x_{1},\ldots,x_{d+1}):0\leq
x_{1},\ldots,x_{d+1},x_{1}+\ldots+x_{d+1}=k\\}.$

A standard textbook argument gives that $|A_{k,d}|=\binom{k+d}{d}$. It turns
out that the multiplicity spectrum for subtraction on $A_{k,d}$ is
particularly easy to describe:

######  Theorem 33.

The multiplicity spectrum for subtraction on $A_{k,d}$ consists of 1 copy of
$\binom{k+d}{d}$ and, for $1\leq t\leq k$,
$\sum_{i=1}^{\min(t,d)}\binom{d+1}{i}\binom{t-1}{i-1}\binom{t+d-i}{d-i}$
copies of $\binom{k+d-t}{d}$.

###### Proof.

Let $w=(w_{1},\ldots,w_{d+1})$ be an element of $A_{k,d}-A_{k,d}$. Then $w$
can be written as $w=x-y$ where $x=(x_{1},\ldots,x_{d+1})$ and
$y=(y_{1},\ldots,y_{d+1})$ are non-negative vectors summing to $k$. It follows
clearly that $\sum_{i}w_{i}=0$.

Now write $w^{+}$ as the vector containing only the positive coordinates of
$w$, so

$w^{+}=(\max(w_{1},0),\ldots,\max(w_{d+1},0))$

and write $w^{-}$ for the corresponding vector for the negative coordinates.
Then for all $i$, $\max(w_{i},0)\leq x_{i}$, so $\sum_{i}(w^{+})_{i}\leq k$.

Now if $w$ is any integer vector with $\sum_{i}w_{i}=0$ it is clear for non-
negative vectors $x,y$ that $w=x-y$ if and only if there is a non-negative
vector $z$ such that $x=w^{+}+z$ and $y=z-w^{-}$.

Thus the number of ways that $w$ can be written as an element of
$A_{k,d}-A_{k,d}$ is the number of non-negative $d+1$-dimensional vectors
summing to $k-\sum_{i}(w^{+})_{i}$ which is
$\binom{k-\sum_{i}(w^{+})_{i}+d}{d}$.

Now to calculate the number of $d+1$-length integer vectors summing to 0 such
that the positive elements sum to $k>0$, we split according to the number $i$
of positive elements (which must be in the range $1\leq i\leq\min(k,d)$). The
number of choices of the locations of those $i$ positive elements is
$\binom{d+1}{i}$, the number of $i$ positive numbers adding to $k$ is
$\binom{k-1}{i-1}$ and the number of $d+1-i$ non-negative numbers adding to
$k$ is $\binom{k+d-i}{d-i}$. ∎

This allows us to prove Theorem 6, namely that there exists a fractional set
$\alpha$ for which $\lVert\alpha\rVert>1$, $\alpha-\alpha$ is spartan, and
with $\lVert\alpha+\alpha\rVert\leq\lVert\alpha\rVert^{1.7354}$.

###### Proof of Theorem 6.

Our $\alpha$ will be $q\mathbbm{1}_{A_{k,d}}$, where $0<q<1$ is a probability
that we will specify later.

For $0\leq t\leq k$, let $\lambda_{t}=\binom{k+d-t}{d}$ and let $\mu_{0}=1$
and for $t>0$,

$\mu_{t}=\sum_{i=1}^{t}\binom{d+1}{i}\binom{t-1}{i-1}\binom{t+d-i}{d-i}.$

Then from Theorem 33, we know that the non-0 values of $\alpha-\alpha$ consist
of $\mu_{t}$ copies of $q^{2}\lambda_{t}$ for each $0\leq t\leq k$.

Then $\alpha-\alpha$ is spartan, by definition, when

$\displaystyle 0$
$\displaystyle>\sum_{x\in\mathbb{Z}^{d+1}:\alpha-\alpha(x)\neq
0}\alpha-\alpha(x)\log_{2}\alpha-\alpha(x)$ $\displaystyle 0$
$\displaystyle>\sum_{t=0}^{k}\mu_{t}q^{2}\lambda_{t}\log_{2}(q^{2}\lambda_{t})$
$\displaystyle-\sum_{t=0}^{k}\mu_{t}\lambda_{t}\log_{2}(\lambda_{t})$
$\displaystyle>\sum_{t=0}^{k}\mu_{t}\lambda_{t}\log_{2}(q^{2})$
$\displaystyle-\frac{\sum_{t=0}^{k}\mu_{t}\lambda_{t}\log_{2}(\lambda_{t})}{2\sum_{t=0}^{k}\mu_{t}\lambda_{t}}$
$\displaystyle>\log_{2}(q)$ $\displaystyle
2^{-\frac{\sum_{t=0}^{k}\mu_{t}\lambda_{t}\log_{2}(\lambda_{t})}{2\sum_{t=0}^{k}\mu_{t}\lambda_{t}}}$
$\displaystyle>q.$

So let
$p=2^{-\frac{\sum_{t=0}^{k}\mu_{t}\lambda_{t}\log_{2}(\lambda_{t})}{2\sum_{t=0}^{k}\mu_{t}\lambda_{t}}}$.
$\alpha-\alpha$ is spartan for all $p>q$.

Now $\lVert\alpha+\alpha\rVert\leq|A_{k,d}+A_{k,d}|=\binom{2k+d}{d}$. Note
that we believe $\alpha+\alpha$ is opulent, so we have equality here, but we
do not need that for this proof.

So if we let $\beta=\log(\binom{2k+d}{d})/\log(p|S|)$, it follows that
$\lVert\alpha+\alpha\rVert\leq\lVert\alpha\rVert^{\beta}$.

$\beta$ as a function of $d$ and $k$ seems to have a global minimum of
$\alpha=1.735383\ldots$ at $d=14929$ and $k=987$. ∎

##  7 Open Questions

We introduced the concept of a fractional dilate as a more general version of
Ruzsa’s method from [10], Ruzsa’s method being the specialisation where a
fractional dilate has all non-0 values being equal. However, we in fact only
used this same specialisation to prove Theorem 6. We believe that using a more
general fractional dilate defined on the Hennecart, Robert and Yudin sets
$A_{k,d}$ could give a better bound than 1.7354. In particular, the best bound
you can get from a Ruzsa-style dilate on $A_{2,d}$ is that for $d=23$, which
with a value of
$q=\frac{1}{5}^{\frac{1}{300}}\frac{1}{2}^{\frac{46}{625}}\frac{1}{12}^{\frac{1129}{15000}}$
gives a bound of 1.7897, whereas if you take a fractional dilate on $A_{2,22}$
with a value of approximately $0.9951$ on the elements of the form $2e_{i}$
and approximately $0.7617$ on the elements of the form $e_{i}+e_{j}$ you can
instead get a bound of 1.7889.

Our proof of Theorem 6 relies on the fact that if $S_{n}$ is drawn from
$\alpha^{n}$ and $\alpha-\alpha$ is spartan, then the size of $S_{n}-S_{n}$ is
quite clumped around the expected value. We believe this will be true without
the requirement of spartaneity.

######  Conjecture 34.

If $\alpha$ is a fractional dilate with $\lVert\alpha\rVert>1$ and $k$ is a
positive integer and $A_{n}$ is drawn from $\alpha^{n}$ then

$\lim_{n\to\infty}\frac{\log|A_{n}+k\cdot
A_{n}|}{n}=\log\lVert\alpha+k\cdot\alpha\rVert$

This would directly imply that various results for sizes of sums and
differences of sets also hold for fractional dilates - for example Rusza’s
Triangle Inequality would imply that
$\lVert\alpha\rVert\lVert\beta-\gamma\rVert\leq\lVert\alpha-\beta\rVert\lVert\alpha-\gamma\rVert$
for fractional dilates $\alpha,\beta,\gamma$.

A weaker conjecture we make is that the feasible regions for dilates are the
same as the feasible regions for fractional dilates.

######  Conjecture 35.

For any fractional dilate $\alpha$, any positive integer $N$ and any
$\epsilon>0$, there exists a finite subset $S$ of the integers such that for
all $|k|\leq N$,

$|\frac{\log\lVert\alpha+k\cdot\alpha\rVert}{\log\lVert\alpha\rVert}-\frac{\log|S+k\cdot
S|}{\log|S|}|<\epsilon$

We also ask whether the fractional dilate versions of the open questions from
Section 3 are true. Since we know that many readers 1just jump straight to the
open questions section to see if there will be anything interesting for them
to work on, we write out these questions in full, noting that Theorem 4 gives
a useful way of computing $\lVert\alpha+\alpha\rVert$ and
$\lVert\alpha+2\cdot\alpha\rVert$.

######  Question 36.

Suppose that $\alpha:\mathbb{Z}\to[0,1]$ is a function with finite sum. We
write

$\displaystyle\lVert\alpha\rVert$ $\displaystyle=\sum_{i}\alpha(i)$
$\displaystyle\lVert\alpha+\alpha\rVert$
$\displaystyle=\inf_{0<p<1}\sum_{i}(\sum_{j+k=i}\alpha(j)\alpha(k))^{p}$
$\displaystyle\lVert\alpha+2\cdot\alpha\rVert$
$\displaystyle=\inf_{0<p<1}\sum_{i}(\sum_{j+2k=i}\alpha(j)\alpha(k))^{p}.$

Are each of the following statements true for all such $\alpha$?

  1. 1.

$\lVert\alpha\rVert\lVert\alpha+2\cdot\alpha\rVert\leq\lVert\alpha+\alpha\rVert^{2}$

  2. 2.

$\lVert\alpha+2\cdot\alpha\rVert\leq\log_{3}4\lVert\alpha+\alpha\rVert$

  3. 3.

$\lVert\alpha+2\cdot\alpha\rVert\geq\lVert\alpha+\alpha\rVert$

Since a subset of the integers is equivalent to the fractional dilate of its
characteristic function, positive answers to these questions would imply
positive answers to the corresponding questions in Section 3. If either
Conjecture 34 or Conjecture 35 is true the questions in the two sections are
equivalent. A negative answer to any of these questions would either lead to
an extension of the Feasible Region $F_{1,2}$ or a better understanding of the
above Conjectures.

The biggest open question we leave is whether fractional dilates can find a
use elsewhere.

## References

  * [1] B. Bukh  “Sums of dilates”  In _Combinatorics, Probability and Computing_ 17, 2008, pp. 627–639
  * [2] Rogers C and G. Shephard  “The diference body of a convex body”  In _Arch. Math._ 8, 1957, pp. 220–233
  * [3] G. Robert F. Hennecart and A. Yudin  “On the number of sums and differences”  In _Asterisque_ 258, 1999, pp. 173–178
  * [4] G. Freiman and V. Pigarev  “The relation between the invariants $R$ and $T$”  In _Number-theoretic studies in the Markov spectrum and in the structural theory of set addition (Russian)_ , 1973, pp. 172–174
  * [5] S. Miller G. Iyer and L. Zhang  “Finding and counting MSTD sets”  In _Combinatorial and Additive Number Theory, Springer Proceedings in Mathematics and Statistics_ 101, 2014, pp. 79–98
  * [6] B. Hanson and G. Petridis  “A question of Bukh on sums of dilates”  In _Discrete Analysis_ , 2021
  * [7] G. Petridis  “New proofs of Plünnecke-type estimates for product sets in groups”  In _Combinatorica_ 32, 2012, pp. 721–733
  * [8] H. Plúnnecke  “Eine zahlentheoretische anwendung der graphentheorie”  In _J. Reine Angew. Math._ 243
  * [9] I. Ruzsa  “On the cardinality of $A+A$ and $A-A$”  In _Combinatorics: Colloq. Math. Soc. János Bolyai_ 18, 1976, pp. 933–938
  * [10] I. Ruzsa  “On the number of sums and differences”  In _Acta. Math. Hung._ 59, 1992, pp. 439–447
  * [11] Y. Zhao  “Graph Theory and Additive Combinatorics - Exploring Structure and Randomness”  Cambridge University Press, 2023