# The Cardinality of Sumsets: Different Summands

Brendan Murphy, Eyvindur Ari Palsson and Giorgis Petridis

###### Abstract

Let $h$ be a positive integer and $A,B_{1},B_{2},\dots,B_{h}$ be finite sets
in a commutative group. We bound $|A+B_{1}+\dots+B_{h}|$ from above in terms
of $|A|$, $|A+B_{1}|,\dots,|A+B_{h}|$ and $h$. Extremal examples, which
demonstrate that the bound is asymptotically sharp in all the parameters, are
furthermore provided.

##  1 Introduction

Given (non-empty) finite sets $A,B_{1},B_{2},\dots,B_{h}$ in a commutative
group, their _sumset_ (also referred to as their _Minkowski sum_) is

$A+B_{1}+\dots+B_{h}=\\{a+b_{1}+\dots+b_{h}:a\in A,b_{i}\in B_{i}\mbox{ for
$1\leq i\leq h$}\\}.$

We obtain an upper bound on the cardinality of $A+B_{1}+\dots+B_{h}$ in terms
of $h$ and the cardinalities of $A$ and $A+B_{1},\dots,A+B_{h}$. Note that the
question becomes trivial unless some constraints are put on the sets as
$|A+B_{1}+\dots+B_{h}|\leq|A|\,|B_{1}|\dots|B_{h}|$; and the bound is attained
when $A,B_{1},\dots,B_{h}$ are sets of distinct generators of a free
commutative group.

The best known upper bound is as follows.

######  Theorem 1.

Let $h$ and $m$ be positive integers and $\alpha_{1},\dots,\alpha_{h}$ be
positive real numbers. Suppose that $A,B_{1},\dots,B_{h}$ are finite sets in a
commutative group that satisfy $|A|=m$ and $|A+B_{i}|\leq\alpha_{i}m$ for all
$1\leq i\leq h$. Then

$\displaystyle|A+B_{1}+\dots+B_{h}|\leq\alpha_{1}\dots\alpha_{h}\,m^{2-1/h}.$

Theorem 1 can be proved by different methods. It can be deduced from the work
of Ruzsa in [11, 12]. It also follows by combining an inequality of Balister
and Bollobás in [2] with an inequality of Ruzsa [10]. Madiman, Marcus and
Tetali have given a different proof of the inequality of Balister and Bollobás
in [6]. We discuss the various proofs in more detail in Section 2. It is worth
pointing out here that the methods used by the three groups of authors are
different: Ruzsa relied on graph theory, Bollobás and Balister on projections
and Madiman, Marcus and Tetali on entropy.

The upper bound in Theorem 1 has the correct dependence on $\alpha$ and $m$.
The following example (a modification of similar examples given by Ruzsa in
[11, 12]) demonstrates this.

######  Example 2.

Let $h$ be a positive integer. There exist infinitely many
$(\alpha_{1},\dots,\alpha_{h})\in(\mathbb{Q}^{+})^{h}$ with the following
property. For each such $h$-tuple $(\alpha_{1},\dots,\alpha_{h})$ there exist
infinitely many $m$ and sets $A,B_{1},\dots,B_{h}$ in a commutative group with
$|A|=m$, $|A+B_{i}|\leq(1+o(1))\,\alpha_{i}m$ and

$|A+B_{1}+\dots+B_{h}|\geq(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}\,\alpha_{1}\dots\alpha_{h}\,m^{2-1/h}.$

The $o(1)$ term is $o_{m\rightarrow\infty}(1)$.

We show that the sets in Example 2 are extremal to this problem by proving a
matching upper bound and so settle the question of bounding from above the
cardinality of higher sumsets in commutative groups.

######  Theorem 3.

Let $h$ be a positive integer, $\alpha_{1},\dots,\alpha_{h}$ be positive real
numbers and $m$ an arbitrarily large integer. Suppose that
$A,B_{1},\dots,B_{h}$ are finite sets in a commutative group that satisfy
$|A|=m$ and $|A+B_{i}|\leq\alpha_{i}m$ for all $1\leq i\leq h$. Then

$\displaystyle|A+B_{1}+\dots+B_{h}|\leq(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}\,\alpha_{1}\dots\alpha_{h}\,m^{2-1/h}.$

The $o(1)$ term tends to zero as $m$ gets arbitrarily large. For large $h$ the
upper bound is roughly

$|A+B_{1}+\dots+B_{h}|\leq(1+o(1))\,\frac{e^{-1}}{h}\,\alpha_{1}\dots\alpha_{h}\,m^{2-1/h}.$

The proof is a refinement of Ruzsa’s graph theoretic approach. The upper bound
in Theorem 3 is submultiplicative with respect to Cartesian products. In other
words if one replaces $A$ by, say, its Cartesian product $A\times
A=\\{(a,a^{\prime}):a,a^{\prime}\in A\\}$ and the $B_{i}$ by their Cartesian
products $B_{i}\times B_{i}$, then (after some standard calculations of the
form $|(A\times A)+(B\times B)|=|(A+B)\times(A+B)|=|A+B|^{2}$) the resulting
upper bound is

$\frac{\alpha_{1}\dots\alpha_{h}}{\sqrt{h}}\,|A|^{2-1/h}\;,$

which is weaker than what the theorem gives. This particular feature of the
upper bound makes using one of the key ingredients in Ruzsa’s method, the
product trick, more delicate. From a technical point of view this is the
greatest difficulty that must be overcome.

The special case when $B_{1}=B_{2}=\dots=B_{h}$ and
$\alpha_{1}=\dots=\alpha_{h}=\alpha$ was considered in [8]. The sumset
$A+B_{1}+\dots+B_{h}$ in this case is abbreviated to $A+hB$. The upper bound
obtained there is slightly stronger:

$\displaystyle|A+hB|\leq(1+o(1))\,\frac{C}{h^{2}}\alpha^{h}\,m^{2-1/h}$ (1)

for an absolute constant $C>0$. The extra factor of $h$ in the denominator can
be accounted for by the fact that while
$|S_{1}+\dots+S_{h}|\leq|S_{1}|\dots|S_{h}|$ holds for general sets $S_{i}$,
when the same set $S$ is added to itself one has the stronger inequality
$|S+\dots+S|\leq\binom{|S|+h-1}{h}.$ Inequality (1) probably does not have the
correct dependence in $h$ as the largest value of $|A+hB|$ in examples is of
the order $h^{-h-1}\alpha^{h}m^{2-1/h}$. It would be of interest to bridge
that gap.

The proof of Theorem 3 is similar to that of (1). There are nonetheless
technical differences. Roughly speaking we combine ideas from the proof of (1)
with a strategy used repeatedly in the literature (for example in [4, 13]) to
prove a generalisation of the afore mentioned result of Ruzsa. We couldn’t
find a result general enough for our purposes in the literature and so give a
detailed proof in Section 5.

The paper is organized as follows. In Section 2 we discuss the different
proofs of Theorem 1. The proof of Theorem 3 is done in Section 3. Example 2 is
described in Section 4. In Section 5 the graph theoretic framework of the
proof is developed.

##  2 Proof of Theorem 1

Theorem 1 follows by combining an inequality of Balister and Bollobás with an
inequality of Ruzsa.

######  Theorem 4 (Balister-Bollobás, [2]).

Let $h$ and $m$ be positive integers and $\alpha_{1},\dots,\alpha_{h}$ be
positive real numbers. Suppose that $A,B_{1},\dots,B_{h}$ are finite sets in a
commutative group that satisfy $|A|=m$ and $|A+B_{i}|\leq\alpha_{i}m$ for all
$1\leq i\leq h$. Then for any subset $C\subseteq B_{1}+\dots+B_{h}$

$\displaystyle|A+C|\leq(\alpha_{1}\dots\alpha_{h})^{1/h}\,m\,|C|^{1-1/h}.$

The proof given by Balister and Bollobás is short and elegant. It combines an
idea of Gyarmati, Matolcsi and Ruzsa in [5] with the Box Theorem in [3].
Madiman, Marcus and Tetali gave a somewhat different proof based on entropy
[6].

The theorem can also be proved by methods developed by Ruzsa (for example in
[11, 12]).

To get Theorem 1 one naturally sets $C=B_{1}+\dots+B_{h}$. This gives

$\displaystyle|A+B_{1}+\dots+B_{h}|\leq(\alpha_{1}\dots\alpha_{h})^{1/h}\,m\,|B_{1}+\dots+B_{h}|^{1-1/h}.$
(2)

We are left with bounding $|B_{1}+\dots+B_{h}|$ in terms of $m$ and the
$\alpha_{i}$. Ruzsa achieved this by modifying a graph theoretic method of
Plünnecke in [9], a variant of which we describe in Section 5.

######  Theorem 5 (Ruzsa, [10]).

Let $h$ and $m$ be positive integers and $\alpha_{1},\dots,\alpha_{h}$ be
positive real numbers. Suppose that $A,B_{1},\dots,B_{h}$ are finite sets in a
commutative group that satisfy $|A|=m$ and $|A+B_{i}|\leq\alpha_{i}m$ for all
$1\leq i\leq h$. Then there exists a non-empty subset $\emptyset\neq
X\subseteq A$

$\displaystyle|X+B_{1}+\dots+B_{h}|\leq\alpha_{1}\dots\alpha_{h}\,|X|.$

In particular

$\displaystyle|B_{1}+\dots+B_{h}|\leq|X+B_{1}+\dots+B_{h}|\leq\alpha_{1}\dots\alpha_{h}\,|X|\leq\alpha_{1}\dots\alpha_{h}\,m.$

Substituting the last inequality in (2) gives Theorem 1.

Theorems 1 and 5 differ crucially in the exponent of $m$. Ruzsa has shown in
[13] that if one is interested in bounding $|X+B_{1}+\dots+B_{h}|$ for a
suitably chosen large subset of $A$, then the correct exponent of $m$ is 1.

Specifically he proved that for any $\varepsilon>0$ there exists a non-empty
subset $\emptyset\neq X\subseteq A$ such that $|X|>(1-\varepsilon)|A|$ and

$\displaystyle|X+B_{1}+\dots+B_{h}|\leq\left(\frac{h\,\varepsilon^{1-h}-1}{h-1}\right)\,\alpha_{1}\dots\alpha_{h}\,|X|\leq
2\varepsilon^{1-h}\,\alpha_{1}\dots\alpha_{h}\,|X|.$

So the exponent of $|X|$ in the upper bound remains 1 even when $X$ is
required to be very dense in $A$. The nature of the upper bound changes when
the whole of $A+B_{1}+\dots+B_{h}$ is bounded.

##  3 Proof of Theorem 3

The upper bound in Theorem 3 is an increasing function of the $\alpha_{i}$ and
the ratios $|A+B_{i}|/|A|$ are rational numbers so we may assume that
$\alpha_{i}\in\mathbb{Q}^{+}$.

The next step is to reduce to the special case where all the $\alpha_{i}$ are
equal. We prove the following.

######  Proposition 6.

Let $h$ be a positive integer, $\alpha$ be a positive rational number and $m$
an arbitrarily large integer. Suppose that $A,B_{1},\dots,B_{h}$ are finite
sets in a commutative group that satisfy $|A|=m$ and $|A+B_{i}|\leq\alpha m$
for all $1\leq i\leq h$. Then

$\displaystyle|A+B_{1}+\dots+B_{h}|\leq(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}\,\alpha^{h}\,m^{2-1/h}.$

The $o(1)$ term tends to zero as $m$ gets arbitrarily large.

Theorem 3 is deduced from the above proposition in a standard way by working
in Cartesian products of groups (see for example [12, 13]).

###### Deduction of Theorem 3 from Proposition 6.

Let $\alpha_{i}=p_{i}/q_{i}$ and set $n=q_{1}\dots q_{h}.$ Furthermore, let
$T_{1},\ldots,T_{h}$ be pairwise disjoint sets of generators of a free abelian
group $F$ with cardinality $n_{i}:=|T_{i}|=n\,\prod_{j\neq i}\alpha_{j}$; and
let $0$ denote the identity of $F$.

We apply Proposition 6 to the sets $A^{\prime}=A\times\\{0\\}$,
$B_{1}^{\prime}=B_{1}\times T_{1},\dots,B_{h}^{\prime}=B_{h}\times T_{h}$. As

$\displaystyle|A^{\prime}+B_{i}^{\prime}|=|T_{i}|\,|A+B_{i}|\leq
m\,n\,\prod_{j=1}^{h}\alpha_{j}=\left(n\,\prod_{j=1}^{h}\alpha_{j}\right)|A^{\prime}|$

for all $i=1,\dots,h$ it yields

$\displaystyle|A^{\prime}+B_{1}^{\prime}+\dots+B_{h}^{\prime}|$
$\displaystyle\leq$
$\displaystyle(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}\left(n\prod_{j=1}^{h}\alpha_{j}\right)^{h}\,m^{2-1/h}$
$\displaystyle=$
$\displaystyle(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}\left(\prod_{i=1}^{h}\alpha_{i}\,n_{i}\right)\,m^{2-1/h}.$

Theorem 3 follows by observing that

$\displaystyle|A^{\prime}+B_{1}^{\prime}+\dots+B_{h}^{\prime}|$
$\displaystyle=$
$\displaystyle|A+B_{1}+\dots+B_{h}|\,|\\{0\\}+T_{1}+\dots+T_{h}|$
$\displaystyle=$ $\displaystyle|A+B_{1}+\dots+B_{h}|\,\prod_{i=1}^{h}n_{i}$

and dividing by $n_{1}\cdots n_{h}$.

∎

We next prove Proposition 6. The rough strategy is as follows. We initially
apply Theorem 5 to find a non-empty subset $\emptyset\neq X_{1}\subseteq A$
whose growth under addition with the $B_{i}$ can be bounded. We are left with
bounding

$\displaystyle(A+B_{1}+\dots+B_{h})\setminus(X_{1}+B_{1}+\dots+B_{h}).$

We would like to iterate and so need to strengthen Theorem 5. From a technical
point of view, this is the heart of the argument. It requires a detour in
graph-theoretic techniques developed by Plünnecke and Ruzsa and so is left for
later sections. The key result we employ in the proof of Proposition 6
(labelled as Corollary 18 in Section 5.5) is as follows.

######  Bound for sumsets with a component removed.

Let $h$ be a positive integer. Suppose that $A,B_{1},\dots,B_{h}$ are finite
sets in a commutative group and $E\subseteq A$ a subset of $A$.

If $\emptyset\neq X\subseteq A\setminus E$ is a subset of $A\setminus E$ that
minimizes the quantity

$\displaystyle\mu(Z):=\frac{1}{h}\sum_{i=1}^{h}\frac{|(Z+B_{i})\setminus(E+B_{i})|}{|Z|}$

over all non-empty subsets $\emptyset\neq Z\subseteq A\setminus E$, then

$\displaystyle|(X+B_{1}+\dots+B_{h})\,\setminus(E+B_{1}+\cdots+B_{h})|\leq\mu^{h}\,|X|,$

where

$\displaystyle\mu=\mu(X)=\frac{1}{h}\sum_{i=1}^{h}\frac{|(X+B_{i})\setminus(E+B_{i})|}{|X|}.$

Note that setting $E=\emptyset$ gives Theorem 5 for the special case when
$\alpha_{1}=\dots=\alpha_{h}=\alpha$, as

$\displaystyle\mu=\min_{\emptyset\neq Z\subseteq
A}\frac{1}{h}\sum_{i=1}^{h}\frac{|Z+B_{i}|}{|Z|}\leq\frac{1}{h}\sum_{i=1}^{h}\frac{|A+B_{i}|}{|A|}\leq\alpha.$

###### Proof of Proposition 6.

Applying the bound stated above successively we partition $A$ into
$X_{1}\cup\dots\cup X_{k}$ for some finite ($A$ is finite) $k$, whose exact
value is irrelevant to the argument. More precisely in the $j$th step set we
set $E=\bigcup_{\ell=1}^{j-1}X_{\ell}$ ($E=\emptyset$ for $j=1$) and chose
$X_{j}$ to be the _minimal_ non-empty subset of $A\setminus E$ that minimizes
the quantity

$\displaystyle\frac{1}{h}\sum_{i=1}^{h}\frac{|(Z+B_{i})\setminus(E+B_{i})|}{|Z|},$

which we set to be $\mu_{j}$. The inequality we get is

$\displaystyle\left|\left(X_{j}+B_{1}+\dots+B_{h}\right)\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{1}+\dots+B_{h}\right)\right|\leq\mu_{j}^{h}|X_{j}|.$
(3)

It is crucial to observe that the defining properties (and especially the
minimality) of the $X_{j}$ imply that the $\mu_{j}$ form an increasing
sequence. Indeed $\mu_{j}\leq\mu_{j+1}$ as

$\displaystyle\mu_{j}|X_{j}|+\mu_{j}|X_{j+1}|$ $\displaystyle=$
$\displaystyle\mu_{j}|X_{j}\cup X_{j+1}|$ $\displaystyle\leq$
$\displaystyle\frac{1}{h}\sum_{i=1}^{h}\left|\left((X_{j}\cup
X_{j+1})+B_{i}\right)\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{i}\right)\right|$
$\displaystyle=$
$\displaystyle\frac{1}{h}\sum_{i=1}^{h}\left|(X_{j}+B_{i})\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{i}\right)\right|$
$\displaystyle~{}+~{}\frac{1}{h}\sum_{i=1}^{h}\left|(X_{j+1}+B_{i})\setminus\left(\bigcup_{\ell=1}^{j}X_{\ell}+B_{i}\right)\right|$
$\displaystyle=$ $\displaystyle\mu_{j}|X_{j}|+\mu_{j+1}|X_{j+1}|.$

When the $\mu_{j}$ are large it turns out that replacing the estimate in (3)
by a more elementary one is more economical. We have

$\displaystyle\left|\left(X_{j}+B_{1}+\dots+B_{h}\right)\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{1}+\dots+B_{h}\right)\right|$
$\displaystyle\leq$ $\displaystyle|X_{j}+B_{1}+\dots+B_{h}|$
$\displaystyle\leq$ $\displaystyle|X_{j}|\,|B_{1}+\dots+B_{h}|.$

To bound $|B_{1}+\dots+B_{h}|$ we adapt accordingly the argument in Theorem 5.

$\displaystyle|B_{1}+\dots+B_{h}|\leq|X_{1}+B_{1}+\dots+B_{h}|\leq\mu_{1}^{h}|X|\leq\mu_{1}^{h}\,m.$

Combining (3) with the last two inequalities gives

$\displaystyle\left|\left(X_{j}+B_{1}+\dots+B_{h}\right)\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{1}+\dots+B_{h}\right)\right|\leq\min\left\\{\mu_{j}^{h},\mu_{1}^{h}\,m\right\\}|X_{j}|.$

Summing over $j=1,\dots,k$ gives

$\displaystyle|A+B_{1}+\dots+B_{h}|$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{k}\left|\left(X_{j}+B_{1}+\dots+B_{h}\right)\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{1}+\dots+B_{h}\right)\right|$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{k}\min\left\\{\mu_{j}^{h},\mu_{1}^{h}\,m\right\\}|X_{j}|.$

We are left with bounding the sum
$\sum_{j=1}^{k}\min\left\\{\mu_{j}^{h}\,,\,\mu_{1}^{h}\,m\right\\}\,|X_{j}|$
subject to two constraints:

$\displaystyle\sum_{j=1}^{k}|X_{j}|=m$

and

$\displaystyle\sum_{j=1}^{k}\mu_{j}\,|X_{j}|$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{k}\left(\frac{1}{h}\sum_{i=1}^{h}\left|(X_{j}+B_{i})\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{i}\right)\right|\right)$
$\displaystyle=$
$\displaystyle\frac{1}{h}\sum_{i=1}^{h}\left(\sum_{j=1}^{k}\left|(X_{j}+B_{i})\setminus\left(\bigcup_{\ell=1}^{j-1}X_{\ell}+B_{i}\right)\right|\right)$
$\displaystyle=$ $\displaystyle\frac{1}{h}\sum_{i=1}^{h}|A+B_{i}|$
$\displaystyle\leq$ $\displaystyle\alpha m.$

The two quantities inside the $\min$ are equal if

$\displaystyle\mu_{j}=\mu_{*}:=\mu_{1}\,m^{1/h}.$

As $\mu_{j}\geq\mu_{1}$ for all $1\leq j\leq h$, we can replace the $\min$ by
the straight line

$\displaystyle\mu_{1}^{h}+(\mu_{j}-\mu_{1})\frac{\mu_{*}^{h}-\mu_{1}^{h}}{\mu_{*}-\mu_{1}},$

which, thought of as function of $\mu_{j}$, intersects the curve $\mu_{j}^{h}$
at $\mu_{j}=\mu_{1}$ and $\mu_{j}=\mu_{*}.$ The slope of the line is
asymptotically equal to

$\displaystyle\frac{\mu_{*}^{h}-\mu_{1}^{h}}{\mu_{*}-\mu_{1}}=(1+o(1))\,\mu_{*}^{h-1}\,,$

as $m$ is assumed to be arbitrarily large and so $\mu_{*}=\mu_{1}m^{1/h}$ is
much larger than $\mu_{1}$. Therefore

$\displaystyle|A+B_{1}+\dots+B_{h}|$ $\displaystyle\leq$
$\displaystyle(1+o(1))\,\sum_{j=1}^{k}\left(\mu_{1}^{h}+(\mu_{j}-\mu_{1})\mu_{*}^{h-1}\right)\,|X_{j}|$
$\displaystyle=$
$\displaystyle(1+o(1))\left(\mu_{1}^{h}\sum_{j=1}^{k}|X_{j}|+\mu_{*}^{h-1}\sum_{j=1}^{k}\mu_{j}|X_{j}|-\mu_{1}\,\mu_{*}^{h-1}\sum_{j=1}^{k}|X_{j}|\right)$
$\displaystyle\leq$
$\displaystyle(1+o(1))\,\left(\mu_{1}^{h}m+(\alpha-\mu_{1})\mu_{*}^{h-1}m\right)$
$\displaystyle\leq$
$\displaystyle(1+o(1))\,\left(\alpha^{h}m+(\alpha-\mu_{1})\mu_{1}^{h-1}m^{2-1/h}\right).$

The final task is to select the value of $1\leq\mu_{1}\leq\alpha$ that
maximizes this expression. Differentiating the expression
$(\alpha-\mu_{1})\mu_{1}^{h}$ with respect to $\mu_{1}$ gives that it is
maximized when

$\displaystyle(h-1)\,(\alpha-\mu_{1})=\mu_{1}\implies\mu_{1}=\left(1-\frac{1}{h}\right)\alpha\mbox{
or }\alpha-\mu_{1}=\frac{\alpha}{h}.$

Substituting above gives

$\displaystyle|A+B_{1}+\dots+B_{h}|$ $\displaystyle\leq$
$\displaystyle(1+o(1))\,\left(\alpha^{h}m+\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}m^{2-1/h}\right).$

The first summand is then absorbed in the $o(1)$ term and the claimed
asymptotic bound on $|A+B_{1}+\dots+B_{h}|$ follows. ∎

This completes the proof of Proposition 6 modulo the proof of the estimate on
p. Bound for sumsets with a component removed, which as we have seen implies
Theorem 3. The proof of the estimate is given in Section 5. We next provide
examples which show that the upper bound given by Theorem 3 is asymptotically
sharp.

##  4 Examples

We construct the sets in Example 2. To keep the notation simple we assume that
the $\alpha_{i}$ are all equal: $\alpha_{1}=\dots=\alpha_{h}=\alpha.$

Once these examples have been constructed, it is straightforward to construct
examples for different $(\alpha_{1},\dots,\alpha_{h})$ by considering
Cartesian products. Very much like in the first step of the proof of Theorem 3
in Section 3 one then considers sets
$A^{\prime}=A\times\\{0\\},B_{1}^{\prime}=B_{1}\times
T_{1},\dots,B_{h}^{\prime}=B_{h}\times T_{h}$ to get a different $h$-tuple
$(\alpha_{1},\dots,\alpha_{h})$, where $\alpha_{i}=\alpha\,|T_{i}|$. The
$T_{i}$ are sets of distinct generators of a free commutative group. The
details are as follows,

$\displaystyle\frac{|A^{\prime}+B_{i}^{\prime}|}{|A^{\prime}|}=\frac{|(A+B_{i})\times
T_{i}|}{|A|}=\frac{|A+B_{i}|}{|A|}\,|T_{i}|\leq(1+o(1))\,\alpha\,|T_{i}|$

and

$\displaystyle|A^{\prime}+B_{1}^{\prime}+\dots+B_{h}^{\prime}|$
$\displaystyle=$
$\displaystyle|(A+B_{1}+\dots+B_{h})\times(T_{1}+\dots+T_{h})|$
$\displaystyle=$ $\displaystyle|A+B_{1}+\dots+B_{h}|\,|T_{1}+\dots+T_{h}|$
$\displaystyle\geq$
$\displaystyle(1+o(1))\,\alpha^{h}|A|^{2-1/h}\,|T_{1}|\cdots|T_{h}|$
$\displaystyle=$
$\displaystyle(1+o(1))\,\alpha_{1}\cdots\alpha_{h}|A^{\prime}|^{2-1/h}.$

To construct the sets for the special case when $\alpha_{i}=\alpha$ for all
$i$, we fix $h$ and let $a$ and $l$ be integers, which we consider as
variables with $a$ assumed to be arbitrarily large and divisible by $h-1$. We
set $b=la$ and work in $\mathbb{Z}_{b}^{k}$, where $k=h+a^{h-1}/(h-1)$. We
write $x_{i}$ for the $i$th coordinate of the vector $x$.

We consider $A=A_{1}\cup A_{2}$ where

$\displaystyle
A_{1}=\\{x:x_{i}\in\\{0,l,2l,\dots,(a-1)l\\}~{}\mbox{for}~{}1\leq i\leq
h~{}\mbox{and}~{}x_{i}=0~{}\mbox{otherwise}\\}$

and $A_{2}$ is a collection of $a^{h-1}/(h-1)$ independent points

$\displaystyle A_{2}=\bigcup_{j=h+1}^{k}\\{x:x_{j}=1\,,\;x_{j}=0\mbox{
otherwise}\\}.$

$B_{i}$ is taken to be a copy of $\mathbb{Z}_{b}$

$\displaystyle B_{i}=\\{x:x_{i}\in\\{0,\dots,b-1\\}\,,\;x_{j}=0\mbox{ for all
}j\neq i\\}.$

We now estimate the cardinality of the sets that interest us,

$\displaystyle|A|=|A_{1}|+|A_{2}|=a^{h}+\frac{a^{h-1}}{h-1}=(1+o(1))a^{h}.$

As $h$ is fixed different values of $a$ result to different values of $m$.

To bound $|A+B_{i}|$ we note that

$\displaystyle\left|A_{1}+B_{i}\right|=\left|\\{x:x_{i}\in\\{0,\dots,b-1\\}\,,\;x_{j}\in\\{0,\ell,2\ell,\dots,(a-1)\ell\\}\mbox{
for all }i\neq j\leq h\\}\right|=ba^{h-1}$

and that

$\displaystyle|A_{2}+B_{i}|=|B_{i}|\,|A_{2}|=\frac{ba^{h-1}}{h-1}.$

Thus

$\displaystyle|A+B_{i}|$ $\displaystyle\leq$
$\displaystyle|A_{1}+B_{i}|+|A_{2}+B_{i}|$ $\displaystyle\leq$ $\displaystyle
ba^{h-1}+\frac{ba^{h-1}}{h-1}$ $\displaystyle=$
$\displaystyle\left(1+\frac{1}{h-1}\right)la^{h}$ $\displaystyle=$
$\displaystyle(1+o(1))\,\left(1+\frac{1}{h-1}\right)\,l\,m.$

$\alpha$ is therefore

$\alpha=\left(1+\frac{1}{h-1}\right)l.$

$h$ is fixed and so different values of $l$ result to different values of
$\alpha$.

To bound $|A+B_{1}+\dots+B_{h}|$ from below observe that
$|B_{1}+\dots+B_{h}|=|\mathbb{Z}_{b}^{h}|=b^{h}$ and that for $a,a^{\prime}\in
A_{2}$ the intersection
$(a+B_{1}+\dots+B_{h})\cap(a^{\prime}+B_{1}+\dots+B_{h})$ is emty. Thus

$\displaystyle|A+B_{1}+\dots+B_{h}|$ $\displaystyle\geq$
$\displaystyle|A_{2}+B_{1}+\dots+B_{h}|$ $\displaystyle=$
$\displaystyle|A_{2}|\,|B_{1}+\dots+B_{h}|$ $\displaystyle=$
$\displaystyle\frac{a^{h-1}}{h-1}\,b^{h}$ $\displaystyle=$
$\displaystyle\frac{l^{h}}{h-1}\,a^{2h-1}$ $\displaystyle=$
$\displaystyle(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h}}{h-1}\,\alpha^{h}\,m^{2-1/h}$
$\displaystyle=$
$\displaystyle(1+o(1))\,\frac{\left(1-\frac{1}{h}\right)^{h-1}}{h}\,\alpha^{h}\,m^{2-1/h}.$

We are done. As is expected the structure of the sets presented here is such
that every inequality in Section 3 is more or less attained.

##  5 Graph theory

In this section we develop the graph theoretic framework necessary for our
proof of the estimate on p.Bound for sumsets with a component removed, the
last step of the proof of Theorem 3. Following Ruzsa [13], we define a type of
layered commutative graph, called a _commutative hypercube graph_ , that
generalizes the addition graph associated to sumsets of the form
$A+B_{1}+\cdots+B_{h}$, defined in the first example below. The class of
commutative hypercube graphs includes graphs that result from removing a
component from an addition graph. The main result of this section is an analog
of Theorem 5 for commutative hypercube graphs. Throughout this section
$\biguplus$ stands for disjoint union.

###  5.1 Hypercube graphs and their products

Let $Q_{h}$ denote the set of all subsets of $\\{1,\ldots,h\\}$ and for $I$ in
$Q_{h}$, let $|I|$ denote the cardinality of $I$. Given $I$ and $I^{\prime}$
in $Q_{h}$, we will write $I\to I^{\prime}$ if $I^{\prime}=I\cup\\{i\\}$ for
some $i\not\in I$.

######  Definition 7 (Hypercube Graph).

Let $\mathcal{G}$ be a directed graph with vertex set $V$ and edge set $E$. We
say that $\mathcal{G}$ is a _hypercube graph indexed by $Q_{h}$_ if it
satisfies two conditions:

  1. 1.

For each $I$ in $Q_{h}$ there exists a set $U_{I}\subseteq V$ such that $V$ is
the disjoint union of the $U_{I}$’s: $V=\biguplus_{I\in Q_{h}}U_{I}$.

  2. 2.

There is an edge $u\to v$ in $E$ only if $u\in U_{I}$ and $v\in
U_{I^{\prime}}$ where $I\to I^{\prime}$.

For short, we may say $\mathcal{G}$ is a “$Q_{h}$-hypercube graph.” Note that
a $Q_{h}$-hypercube graph is a layered graph with $h+1$ layers:
$V=V_{0}\cup\cdots\cup V_{h}$, where $V_{i}=\biguplus_{|I|=i}U_{I}$.

We give some examples of hypercube graphs. The most important example of a
hypercube graph is an addition graph with different summands, which are
featured in [13].

######  Example (Addition graphs).

Let $A,B_{1},\ldots,B_{h}$ be finite subsets of a commutative group $G$. Their
addition graph $\mathcal{G}_{+}(A,B_{1},\ldots,B_{h})$ is defined as follows:
for each $I$ in $Q_{h}$, let $U_{I}=A+\sum_{i\in I}B_{i}$. We consider each
$U_{I}$ to be contained in a separate copy of $G$, and we let
$V=\biguplus_{I\in Q_{h}}U_{I}$. For each vertex $x$ in $U_{I}$ there is an
edge to $y$ in $U_{I^{\prime}}$ if $I^{\prime}=I\cup\\{i\\}$ and $y=x+b$ for
some $b$ in $B_{i}$. Thus $\mathcal{G}_{+}(A,B_{1},\ldots,B_{h})$ is a
hypercube graph indexed by $Q_{h}$.

Note that any subgraph of a $Q_{h}$-hypercube graph is automatically a
$Q_{h}$-hypercube graph. For certain induced subgraphs of a hypercube graph,
we can say something more. We recall from [12] a definition.

######  Definition (Channels of directed graphs).

Given a directed graph $\mathcal{G}=\mathcal{G}(V,E)$ and two sets of vertices
$X,Y\subseteq V$, the _channel $\overline{\mathcal{G}}(X,Y)$_ between $X$ and
$Y$ is the subgraph of $\mathcal{G}$ induced by the set of vertices that lie
on a path from $X$ to $Y$ (including endpoints).

######  Example.

Let $\mathcal{G}$ be a hypercube graph indexed by $Q_{h}$ and let $I$ and
$I^{\prime}$ be elements of $Q_{h}$ such that $I\subseteq I^{\prime}$. Given
subsets $X\subseteq U_{I}$ and $Y\subseteq U_{I^{\prime}}$, the channel
$\overline{\mathcal{G}}(X,Y)$ is a hypercube graph indexed by $Q_{j}$, where
$j=|I^{\prime}\setminus I|$.

###### Proof.

Since the edges of $\overline{\mathcal{G}}$ are edges of $\mathcal{G}$,
condition 2 of Definition 7 is automatically satisfied. Thus it remains to be
shown that condition 1 is satisfied.

Note that the set of $J$ in $Q_{h}$ such that $I\subseteq J\subseteq
I^{\prime}$ is in one-to-one correspondence with $Q_{j}$. Fixing one such
correspondence, let $\bar{}J$ denote the element in $Q_{j}$ corresponding to
$J$ and set $U_{\bar{}J}(\overline{\mathcal{G}})=V(\overline{\mathcal{G}})\cap
U_{J}$. Since any vertex in $V(\overline{\mathcal{G}})$ must be an element of
some $U_{J}$ with $I\subseteq J\subseteq I^{\prime}$, we have
$V(\overline{\mathcal{G}})=\biguplus_{\bar{}J\in
Q_{j}}U_{\bar{}J}(\overline{\mathcal{G}})$, as desired. ∎

To prove the analog of Theorem 5, we must define a type of graph product
between hypercube graphs that is motivated by addition graphs of product sets.

######  Definition (Hypercube Product).

Let $\mathcal{G}^{\prime}$ and $\mathcal{G}^{\prime\prime}$ be hypercube
graphs indexed by $Q_{h}$. We define a hypercube graph
$\mathcal{G}=\mathcal{G}^{\prime}\otimes\mathcal{G}^{\prime\prime}$ also
indexed by $Q_{h}$ as follows: for each $I\in Q_{h}$, we define
$U_{I}(\mathcal{G})=U_{I}(\mathcal{G}^{\prime})\times
U_{I}(\mathcal{G}^{\prime\prime})$, and for $(u,v)\in
U_{I}(\mathcal{G}),(u^{\prime},v^{\prime})\in U_{I^{\prime}}(\mathcal{G})$, we
have $(u,v)\to(u^{\prime},v^{\prime})$ if and only if $u\to u^{\prime}$ and
$v\to v^{\prime}$. We call $\mathcal{G}$ the _hypercube product_ of
$\mathcal{G}^{\prime}$ and $\mathcal{G}^{\prime\prime}$.

It is easy to see that $\mathcal{G}_{+}(A^{\prime}\times
A^{\prime\prime},B_{1}^{\prime}\times
B_{1}^{\prime\prime},\ldots,B_{h}^{\prime}\times B_{h}^{\prime\prime})$ is the
hypercube product of
$\mathcal{G}_{+}(A^{\prime},B_{1}^{\prime},\ldots,B_{h}^{\prime})$ and
$\mathcal{G}_{+}(A^{\prime\prime},B_{1}^{\prime\prime},\ldots,B_{h}^{\prime\prime})$.

###  5.2 Square commutativity

The key feature of addition graphs that makes them useful in additive number
theory is that they capture in a graph theoretic way the commutativity of
addition. This particular feature was first exploited by Plünnecke in [9], who
worked with a class of directed layered graphs he called _commutative_. The
importance of commutative graphs to additive number theory is detailed in [7,
15, 12]. We will only mention them briefly as we need a stronger form of
commutativity in order to prove Theorem 5, one that works better for hypercube
graphs.

First we make an auxiliary definition: given index sets $I,I^{\prime},$ and
$I^{\prime\prime}$ in $Q_{h}$ such that $I\to I^{\prime}\to I^{\prime\prime}$,
there is a unique index set $I^{\prime}_{c}$ in $Q_{h}$ such that
$I^{\prime}_{c}\not=I^{\prime}$ and $I\to I^{\prime}_{c}\to I^{\prime\prime}$;
explicitly $I^{\prime}_{c}=I\cup(I^{\prime\prime}\setminus I^{\prime})$. We
will call $I^{\prime}_{c}$ the _complement_ of $I^{\prime}$.

######  Definition (Square Commutativity).

Let $\mathcal{G}$ be a hypercube graph indexed by $Q_{h}$. We say that
$\mathcal{G}$ is _square commutative_ if it satisfies two conditions:

  1. 1.

Upward square commutativity: Given indices $I,I^{\prime}$ and
$I^{\prime\prime}$ in $Q_{h}$ such that $I\to I^{\prime}\to I^{\prime\prime}$,
and vertices $v\in U_{I}$, $v^{\prime}\in U_{I^{\prime}}$, and
$v_{1}^{\prime\prime},\ldots,v_{n}^{\prime\prime}\in U_{I^{\prime\prime}}$
such that $v\to v^{\prime}\to v_{i}^{\prime\prime}$ for $i=1,\ldots,n$, there
exist distinct vertices $v_{1}^{\prime},\ldots,v_{n}^{\prime}\in
U_{I^{\prime}_{c}}$ such that $v\to v_{i}^{\prime}\to v_{i}^{\prime\prime}$
for $i=1,\ldots,n$.

  2. 2.

Downward square commutativity: Given indices $I,I^{\prime}$ and
$I^{\prime\prime}$ in $Q_{h}$ such that $I\to I^{\prime}\to I^{\prime\prime}$,
and vertices $v_{1},\ldots,v_{n}\in U_{I}$, $v^{\prime}\in U_{I^{\prime}}$,
and $v^{\prime\prime}\in U_{I^{\prime\prime}}$ such that $v_{i}\to
v^{\prime}\to v^{\prime\prime}$ for $i=1,\ldots,n$, there exist distinct
vertices $v_{1}^{\prime},\ldots,v_{n}^{\prime}\in U_{I^{\prime}_{c}}$ such
that $v_{i}\to v_{i}^{\prime}\to v^{\prime\prime}$ for $i=1,\ldots,n$.

Square commutative graphs are commutative in the sense defined by Plünnecke;
square commutativity strengthens commutativity by requiring that the alternate
paths from $v$ to $v^{\prime\prime}_{i}$ (or from $v_{i}$ to
$v^{\prime\prime}$) go through the complementary vertex set. This is an
important observation as later on we will need to apply Plünnecke’s result.

In our language, Ruzsa has already shown in pp. 597-598 of [13] that addition
graphs are square commutative:

######  Proposition 8 (Ruzsa, [13]).

Let $A,B_{1},\ldots,B_{h}$ be subsets of a commutative group. Then their
addition graph $\mathcal{G}_{+}(A,B_{1},\ldots,B_{h})$ is square commutative.

Channels of square commutative hypercube graphs are also square commutative.

######  Lemma 9.

Let $\mathcal{G}$ be a square commutative hypercube graph indexed by $Q_{h}$,
and let $\overline{\mathcal{G}}=\overline{\mathcal{G}}(X,Y)$ be a channel of
$\mathcal{G}$. Then $\overline{\mathcal{G}}$ is square commutative.
Additionally, if $X\subseteq U_{I}$ and $Y\subseteq U_{I^{\prime}}$ where
$I\subsetneq I^{\prime}\in Q_{h}$, then $\overline{\mathcal{G}}$ is a $Q_{j}$
square commutative hypercube graph, where $j=|I^{\prime}\setminus I|$.

###### Proof.

We have already shown on p.Example that $\overline{\mathcal{G}}$ is a
hypercube graph indexed by $Q_{|I^{\prime}\setminus I|}$. That it is square
commutative follows from the fact that $\mathcal{G}$ is square commutative
combined with the fact that if $x,z\in V(\overline{\mathcal{G}})$ and $x\to
y\to z$ then $y\in V(\overline{\mathcal{G}})$. ∎

Now that we have shown that the main examples of hypercube graphs are square
commutative, we will prove that square commutativity is inherited by products.

######  Lemma 10.

Let $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ be square commutative hypercube
graphs indexed by $Q_{h}$, and let
$\mathcal{G}=\mathcal{G}_{1}\otimes\mathcal{G}_{2}$ be their hypercube
product. Then $\mathcal{G}$ is square commutative.

###### Proof.

The proof is a straightforward verification of square commutativity. We will
prove only the upward condition, since the proof of the downward condition is
similar.

Let $I,I^{\prime},$ and $I^{\prime\prime}$ be indices in $Q_{h}$ such that
$I\to I^{\prime}\to I^{\prime\prime}$, and suppose we have vertices $(u,v)\in
U_{I}(\mathcal{G})$, $(u^{\prime},v^{\prime})\in U_{I^{\prime}}(\mathcal{G})$,
and
$(u^{\prime\prime}_{1},v^{\prime\prime}_{1}),\ldots,(u^{\prime\prime}_{n},v^{\prime\prime}_{n})\in
U_{I^{\prime\prime}}(\mathcal{G})$ such that
$(u,v)\to(u^{\prime},v^{\prime})\to(u^{\prime\prime}_{i},v^{\prime\prime}_{i})$
for $i=1,\ldots,n$. We must find
$(u^{\prime}_{1},v^{\prime}_{1}),\ldots,(u^{\prime}_{n},v^{\prime}_{n})\in
U_{I^{\prime}_{c}}(\mathcal{G})$ such that
$(u,v)\to(u^{\prime}_{i},v^{\prime}_{i})\to(u^{\prime\prime}_{i},v^{\prime\prime}_{i})$
for $i=1,\ldots,n$.

Consider the sequences of vertices $u\to u^{\prime}\to u^{\prime\prime}_{i}$
in $\mathcal{G}_{1}$. Since $\mathcal{G}_{1}$ is square commutative, there
exist distinct vertices $u^{\prime}_{i}\in
U_{I^{\prime}_{c}}(\mathcal{G}_{1})$ such that $u\to u^{\prime}_{i}\to
u^{\prime\prime}_{i}$ for $i=1,\ldots,n$. Similarly there exist distinct
vertices $v^{\prime}_{i}\in U_{I^{\prime}_{c}}(\mathcal{G}_{2})$ such that
$v\to v^{\prime}_{i}\to v^{\prime\prime}_{i}$ for $i=1,\ldots,n$. Thus we have
distinct vertices $(u^{\prime}_{i},v^{\prime}_{i})\in
U_{I^{\prime}_{c}}(\mathcal{G}_{1})\times
U_{I^{\prime}_{c}}(\mathcal{G}_{2})=U_{I^{\prime}_{c}}(\mathcal{G})$ such that
$(u,v)\to(u^{\prime}_{i},v^{\prime}_{i})\to(u^{\prime\prime}_{i},v^{\prime\prime}_{i})$
for $i=1,\ldots,n$, as desired. ∎

###  5.3 A Plünnecke-type inequality for square commutative graphs

The main goal in this section is to extend Ruzsa’s Theorem 5. Our result can
furthermore be thought of as an extension to square commutative graphs of
Plünnecke’s inequality (Theorem 11 below). Before we do this we need to
establish some notation and lemmas regarding magnification ratios.

Given a directed graph $\mathcal{G}$ and subsets $X,Y\subseteq
V(\mathcal{G})$, we will use $\operatorname{Im}_{\mathcal{G}}(X,Y)$ to denote
the set of elements in $Y$ that can be reached from $X$ by paths in
$\mathcal{G}$.

If $\mathcal{G}$ has layers $V_{0},\ldots,V_{h}$, we will use
$D_{i}(\mathcal{G})$ to denote the _$i$ th magnification ratio_ of
$\mathcal{G}$, which is defined as

$\displaystyle D_{i}(\mathcal{G}):=\min_{\varnothing\not=Z\subseteq
V_{0}}\frac{|\operatorname{Im}_{\mathcal{G}}(Z,V_{i})|}{|Z|}.$

Plünnecke bounded the growth of magnification ratios of commutative graphs. We
state a special case of his result that will be applied later.

######  Theorem 11 (Plünnecke, [9]).

Let $h\geq 1$ be a positive integer and $\mathcal{G}$ be a commutative graph.
Then

$\displaystyle D_{h}(\mathcal{G})\leq D_{1}(\mathcal{G})^{h}.$

Square commutative graphs are commutative, so Theorem 11 applies; however, the
bound on $D_{h}(\mathcal{G})$ is not adequate for our purpose. The goal of
this subsection is to improve it for square commutative graphs.

If $\mathcal{G}$ is a hypercube graph indexed by $Q_{h}$, then the
magnification of a subset $\emptyset\neq X\subseteq V_{0}$ in $U_{I}$, where
$I\in Q_{h}$, is defined as

$\displaystyle\beta_{I}(X):=\frac{|\operatorname{Im}_{\mathcal{G}}(X,U_{I})|}{|X|}.$

If $I=\\{i\\}$, then we will use $\beta_{i}(X)$ to denote
$\beta_{\\{i\\}}(X)$. The following lemma relates the $\beta_{I}$ to the usual
magnification ratio $D_{i}$.

######  Lemma 12.

Let $\mathcal{G}$ be a hypercube graph indexed by $Q_{h}$. For any
$\emptyset\neq X\subseteq V_{0}(\mathcal{G})$ we have

$\displaystyle D_{i}(\mathcal{G})\leq\sum_{|I|=i}\beta_{I}(X),$

with equality if and only if $X$ achieves $D_{i}(\mathcal{G})$.

###### Proof.

By the definition of $D_{i}(\mathcal{G})$ we have

$\displaystyle
D_{i}(\mathcal{G})\leq\frac{|\operatorname{Im}_{\mathcal{G}}(X,V_{i})|}{|X|}$

with equality if and only if $X$ achieves $D_{i}(\mathcal{G})$. Since $V_{i}$
is a disjoint union of the $U_{I}$ such that $|I|=i$, we have

$\displaystyle\frac{|\operatorname{Im}_{\mathcal{G}}(X,V_{i})|}{|X|}=\frac{|\biguplus_{|I|=i}\operatorname{Im}_{\mathcal{G}}(X,U_{I})|}{|X|}=\sum_{|I|=i}\frac{|\operatorname{Im}_{\mathcal{G}}(X,U_{I})|}{|X|}=\sum_{|I|=i}\beta_{I}(X).$

Combining these two equations yields the desired inequality. ∎

Later we will also need the following elementary identity, which asserts that
the $\beta_{i}$ are multiplicative.

######  Lemma 13.

Let $\mathcal{G}^{\prime},\mathcal{G}^{\prime\prime}$ be hypercube graphs
indexed by $Q_{h}$ and
$\mathcal{G}=\mathcal{G}^{\prime}\otimes\mathcal{G}^{\prime\prime}$. Then for
all $i=1,\dots,h$ and $Z^{\prime}\subseteq V_{0}(\mathcal{G}^{\prime})$,
$Z^{\prime\prime}\subseteq V_{0}(\mathcal{G}^{\prime\prime})$ we have:

$\displaystyle\beta_{i}(Z^{\prime}\times
Z^{\prime\prime})=\beta_{i}(Z^{\prime})\,\beta_{i}(Z^{\prime\prime}).$

###### Proof.

We have $V_{1}(\mathcal{G}^{\prime})=\biguplus_{i=1}^{h}U^{\prime}_{\\{i\\}}$
and
$V_{1}(\mathcal{G}^{\prime\prime})=\biguplus_{i=1}^{h}U^{\prime\prime}_{\\{i\\}}$.
The way $\mathcal{G}$ is constructed gives
$V_{1}(\mathcal{G})=\biguplus_{i=1}^{h}(U^{\prime}_{\\{i\\}}\times
U^{\prime\prime}_{\\{i\\}})$. Note that

$\displaystyle\operatorname{Im}_{\mathcal{G}}(Z^{\prime}\times
Z^{\prime\prime},U^{\prime}_{\\{i\\}}\times
U^{\prime\prime}_{\\{i\\}})=\operatorname{Im}_{\mathcal{G}^{\prime}}(Z^{\prime},U^{\prime}_{\\{i\\}})\times\operatorname{Im}_{\mathcal{G}^{\prime\prime}}(Z^{\prime\prime},U^{\prime\prime}_{\\{i\\}}).$

The claim follows by taking cardinalities:

$\displaystyle\beta_{i}(Z^{\prime}\times
Z^{\prime\prime})=\frac{|\operatorname{Im}_{\mathcal{G}}(Z^{\prime}\times
Z^{\prime\prime},U^{\prime}_{\\{i\\}}\times
U^{\prime\prime}_{\\{i\\}})|}{|Z^{\prime}\times
Z^{\prime\prime}|}=\frac{|\operatorname{Im}_{\mathcal{G}^{\prime}}(Z^{\prime},U^{\prime}_{\\{i\\}})|}{|Z^{\prime}|}\,\frac{|\operatorname{Im}_{\mathcal{G}^{\prime\prime}}(Z^{\prime\prime},U^{\prime\prime}_{\\{i\\}})|}{|Z^{\prime\prime}|}=\beta_{i}(Z^{\prime})\,\beta_{i}(Z^{\prime\prime}).$

∎

For the standard (often also referred to as Cartesian) product of layered
graphs, the magnification ratio is multiplicative. However, for hypercube
graphs this is only true for the top level magnification ratio, which is
multiplicative for square commutative hypercube graphs111Square commutativity
is not necessary, but it is sufficient (logically and for our purposes)..

######  Lemma 14.

Let $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ be commutative hypercube graphs
indexed by $Q_{h}$, and let $\mathcal{G}_{3}$ be the hypercube product
$\mathcal{G}_{1}\otimes\mathcal{G}_{2}$. Then
$D_{h}(\mathcal{G}_{3})=D_{h}(\mathcal{G}_{1})D_{h}(\mathcal{G}_{2})$.

###### Proof.

For $i=1,2,3$, we will define an auxiliary layered graph
$\hat{}\mathcal{G}_{i}$ as follows:
$V_{0}(\hat{}\mathcal{G}_{i}):=V_{0}(\mathcal{G}_{i})$,
$V_{1}(\hat{}\mathcal{G}_{i}):=V_{h}(\mathcal{G}_{i})$, and $(v,v^{\prime})\in
E(\hat{}\mathcal{G}_{i})$ if and only if there is a path from $v$ to
$v^{\prime}$ in $\mathcal{G}_{i}$. The proof rests on the following fact:

######  Claim.

$\hat{}\mathcal{G}_{3}=\hat{}\mathcal{G}_{1}\times\hat{}\mathcal{G}_{2}$.

In words, $\hat{}\mathcal{G}_{3}$ is the directed layered Cartesian product of
$\hat{}\mathcal{G}_{1}$ and $\hat{}\mathcal{G}_{2}$. It should be noted here
that this would not be the case if we were working with $i$th magnification
ratios for $1\leq i<h$, and that square commutativity is essential for our
proof.

###### Proof of claim.

It suffices to show that for any pair of vertices $(u_{0},v_{0})$ in
$V_{0}(\mathcal{G}_{1})\times V_{0}(\mathcal{G}_{2})$ and any pair of vertices
$(u_{h},v_{h})$ in $V_{h}(\mathcal{G}_{1})\times V_{h}(\mathcal{G}_{2})$, we
can find a sequence of index sets $\emptyset\to I_{1}\to\cdots\to
I_{h}=\\{1,\ldots,h\\}$, and paths $u_{0}\to u_{1}\to\cdots\to u_{h}$ in
$\mathcal{G}_{1}$ and $v_{0}\to v_{1}\to\cdots\to v_{h}$ in $\mathcal{G}_{2}$
such that $u_{j}\in U_{I_{j}}(\mathcal{G}_{1})$ and $v_{j}\in
U_{I_{j}}(\mathcal{G}_{2})$. This guarantees that the product path
$(u_{0},v_{0})\to(u_{1},v_{1})\to\cdots\to(u_{h},v_{h})$ is contained in the
hypercube product $\mathcal{G}_{1}\otimes\mathcal{G}_{2}$, hence the edge
$(u_{0},v_{0})\to(u_{h},v_{h})$ is contained in $\hat{}\mathcal{G}_{3}$.

Let $u_{0}\to u_{1}\to\cdots\to u_{h}$ be any path in $\mathcal{G}_{1}$ from
$u_{0}$ to $u_{h}$. We will use square commutativity to show that there is a
path $u_{0}\to u_{1}^{\prime}\to\cdots\to u_{h-1}^{\prime}\to u_{h}$ such that
$u_{j}^{\prime}\in U_{\\{1,\ldots,j\\}}$. Applying the same argument for a
path $v_{0}\to v_{1}\to\cdots\to v_{h}$ will prove the claim.

For each $u_{j}$, let $I_{j}$ be the index set in $Q_{h}$ such that $u_{j}\in
U_{I_{j}}(\mathcal{G}_{1})$. By definition, $u_{j}\to u_{j+1}$ only if there
exists $i_{j+1}$ such that $I_{j+1}=I_{j}\cup\\{i_{j+1}\\}$. Thus we may
represent the sequence of index sets by a permutation:

$\displaystyle\begin{pmatrix}1&2&\cdots&h\\\
i_{1}&i_{2}&\cdots&i_{h}\end{pmatrix}.$

Applying upward square commutativity to the sequence $I_{j-1}\to I_{j}\to
I_{j+1}$ is equivalent to switching the pair $i_{j}$ and $i_{j+1}$. An example
that illustrates this, is that by applying upward square commutativity to the
layers $V_{0}$, $V_{1}$ and $V_{2}$ we transform the sequence
$V_{0}=U_{\emptyset}\to U_{\\{i_{1}\\}}\to U_{\\{i_{1},i_{2}\\}}$ to
$V_{0}=U_{\emptyset}\to U_{\\{i_{2}\\}}\to U_{\\{i_{1},i_{2}\\}}$ and so, in
the permutation notation, we get

$\displaystyle\begin{pmatrix}1&2&3&\cdots&h\\\
i_{1}&i_{2}&i_{3}&\cdots&i_{h}\end{pmatrix}\to\begin{pmatrix}1&2&3&\cdots&h\\\
i_{2}&i_{1}&i_{3}&\cdots&i_{h}\end{pmatrix}.$

Thus by repeated application of upward square commutativity, we can find a
path $u_{0}\to u_{1}^{\prime}\to u_{2}^{\prime}\to\cdots\to u_{h}$ such that
$u_{1}^{\prime}\in U_{\\{1\\}}(\mathcal{G}_{1})$. Again by repeated
application of square commutativity, we can find a path $u_{0}\to
u_{1}^{\prime}\to u_{2}^{\prime\prime}\to u_{3}^{\prime\prime}\to\cdots\to
u_{h}$ such that $u_{2}^{\prime\prime}\in U_{\\{1,2\\}}(\mathcal{G}_{1})$, and
so on. ∎

Now we continue with the proof of the lemma. By definition of
$\hat{}\mathcal{G}_{i}$, we have
$D_{1}(\hat{}\mathcal{G}_{i})=D_{h}(\mathcal{G}_{i})$ for $i=1,2,3$. Since
$\hat{}\mathcal{G}_{3}$ is the layered product of $\hat{}\mathcal{G}_{1}$ and
$\hat{}\mathcal{G}_{2}$, by the multiplicativity of magnification ratios of
directed layered graphs (e.g. Theorem 7.1 in [7]) we have
$D_{1}(\hat{}\mathcal{G}_{3})=D_{1}(\hat{}\mathcal{G}_{1})D_{1}(\hat{}\mathcal{G}_{2})$.
Thus $D_{h}(\mathcal{G}_{3})=D_{h}(\mathcal{G}_{1})D_{h}(\mathcal{G}_{2})$, as
desired. ∎

We are now ready to state and prove the theorem.

######  Theorem 15 (A Plünnecke-type inequality for square commutative
graphs).

Let $\mathcal{G}$ be a square commutative graph indexed by $Q_{h}$. Then for
every $\emptyset\neq Z\subseteq V_{0}$ we have

$\displaystyle D_{h}(\mathcal{G})\leq\beta_{1}(Z)\cdots\beta_{h}(Z).$

Moreover,

$\displaystyle
D_{h}(\mathcal{G})\leq\left(\frac{D_{1}(\mathcal{G})}{h}\right)^{h}.$

###### Proof.

As usual $\biguplus_{i=0}^{h}V_{i}$ is the vertex set of $\mathcal{G}$ and
$V_{1}=\biguplus_{i=1}^{h}U_{\\{i\\}}$.

$\mathcal{G}$ is a square commutative graph and so in particular is
commutative. Applying Theorem 11 and Lemma 12 successively gives:

$\displaystyle D_{h}(\mathcal{G})\leq
D_{1}(\mathcal{G})^{h}\leq\left(\sum_{i=1}^{h}\beta_{i}(Z)\right)^{h},$

for all $\emptyset\neq Z\subseteq V_{0}.$ A first improvement is as follows.

######  Claim 16.

For all $\emptyset\neq Z\subseteq V_{0}$, we have

$\displaystyle D_{h}(\mathcal{G})\leq\left(\max_{1\leq i\leq
h}\beta_{i}(Z)\right)^{h}.$ (4)

To prove Claim 16 we use the tensor product trick ([13], see also [14]). Let
$n$ be any positive integer. We let
$\mathcal{G}^{n}=\mathcal{G}\otimes\cdots\otimes\mathcal{G}$ denote the
$n$-fold hypercube product of $\mathcal{G}$ with itself and $S^{n}\subseteq
V_{i}(\mathcal{G}^{n})$ the subset of $V_{i}(\mathcal{G}^{n})$ that is
precisely the $n$-fold product of $S$ with itself.

By Lemma 14 and Theorem 11 & Lemma 10 we get that for all positive integers
$n$

$\displaystyle D_{h}(\mathcal{G})^{n}=D_{h}(\mathcal{G}^{n})\leq
D_{1}(\mathcal{G}^{n})^{h}.$

By Lemma 12 and Lemma 13 we have
$D_{1}(\mathcal{G}^{n})\leq\sum_{i=1}^{h}\beta_{i}(Z^{n})=\sum_{i=1}^{h}\beta_{i}(Z)^{n}$
and so

$\displaystyle
D_{h}(\mathcal{G})\leq\left(\sum_{i=1}^{h}\beta_{i}(Z)^{n}\right)^{h/n}.$

Letting $n$ go to infinity proves Claim 16.

To deduce the first inequality in the statement of the theorem we use a trick
of Ruzsa (e.g. [12]), which appears in his proof of Theorem 5 and is similar
to that used in the deduction of Theorem 3 from Proposition 6.

We begin by recalling that $Z$ is fixed. Let $T_{1},\ldots,T_{h}$ be pairwise
disjoint sets of generators of a free abelian group with identity $0$. For now
we leave $n_{i}=|T_{i}|$ undetermined, but note that they will depend on $Z$.

Let $\mathcal{T}$ denote the addition graph
$\mathcal{G}_{+}(\\{0\\},T_{1},\ldots,T_{h})$ and let
$\mathcal{G}^{\prime}=\mathcal{G}\otimes\mathcal{T}$. The subsets of
$V_{0}(\mathcal{G}^{\prime})$ are of the form $S\times\\{0\\}$ for $S\subseteq
V_{0}.$ Combining Claim 16 with Lemma 13 gives

$\displaystyle D_{h}(\mathcal{G}^{\prime})\leq\left(\max_{1\leq i\leq
h}\beta_{i}(Z\times\\{0\\})\right)^{h}=\left(\max_{1\leq i\leq
h}\beta_{i}(Z)\,\beta_{i}(\\{0\\})\right)^{h}=\left(\max_{1\leq i\leq
h}\beta_{i}(Z)\,n_{i}\right)^{h}.$

We now chose the value of the $n_{i}$. The $\beta_{i}(Z)$ are rational numbers
so we set $\beta_{i}(Z)=p_{i}/q_{i}$ and $n=q_{1}\cdots q_{h}$. By choosing
$n_{i}=n\prod_{j\not=i}\beta_{j}(Z)$ we have
$\beta_{i}(Z)n_{i}=n\prod_{\ell=1}^{h}n_{\ell}=\beta_{j}(Z)n_{j}$ for all
$i,j=1,\ldots,n$. Thus

$\displaystyle\left(\max_{1\leq i\leq
k}\beta_{i}(Z)\,n_{i}\right)^{h}=\prod_{i=1}^{h}\beta_{i}(Z)\,n_{i}.$

On the other hand Lemma 14 gives

$\displaystyle
D_{h}(\mathcal{G}^{\prime})=D_{h}(\mathcal{G})\,D_{h}(\mathcal{T})=D_{h}(\mathcal{G})\,|T_{1}+\dots+T_{h}|=D_{h}(\mathcal{G})\,n_{1}\dots
n_{h}.$

Combining the above proves the first inequality in the statement of the
theorem:

$\displaystyle
D_{h}(\mathcal{G})=\frac{D_{h}(\mathcal{G}^{\prime})}{n_{1}\dots
n_{h}}\leq\frac{\left(\max_{1\leq i\leq
h}\beta_{i}(Z)\,n_{i}\right)^{h}}{n_{1}\dots
n_{h}}=\frac{\prod_{i=1}^{h}\beta_{i}(Z)\,n_{i}}{n_{1}\dots
n_{h}}=\prod_{i=1}^{h}\beta_{i}(Z).$

To get the second inequality in the statement of the theorem we first apply
the arithmetic mean - geometric mean inequality and get

$\displaystyle
D_{h}(\mathcal{G})\leq\beta_{1}(Z)\cdots\beta_{h}(Z)\leq\left(\frac{1}{h}\sum_{i=1}^{h}\beta_{i}(Z)\right)^{h}.$

The last step is to let $\emptyset\neq X\subseteq V_{0}$ be the subset that
achieves the first magnification ratio $D_{1}(\mathcal{G})$. Lemma 12 gives
$\sum_{i=1}^{h}\beta_{i}(X)=D_{1}(\mathcal{G})$ and we are done. ∎

Considering $\mathcal{G}=\mathcal{G}_{+}(\\{0\\},T_{1},\dots,T_{h})$ as
constructed above with $|T_{1}|=\dots=|T_{h}|$ shows that the upper bound
cannot be trivially improved. The fact that Theorem 11 follows from Theorem 15
is clear since $h\geq 1$.

###  5.4 A stronger Plünnecke-type inequality for square commutative graphs

Theorem 15 has one unsatisfactory aspect from a technical point of view: it
does not provide any information on the subset $\emptyset\neq Z\subseteq
V_{0}$ that achieves $D_{h}(\mathcal{G})$. We strengthen Theorem 15 by proving
that the subset $\emptyset\neq X\subseteq V_{0}$ that achieves
$D_{1}(\mathcal{G})$ has restricted growth and in fact satisfies the bound
given in Theorem 15.

######  Theorem 17.

Let $\mathcal{G}$ be a square commutative graph with vertex set
$V_{0}\cup\dots\cup V_{h}$. Suppose that $\emptyset\neq X\subseteq V_{0}$
achieves $D_{1}(\mathcal{G})$. Then

$\displaystyle|\operatorname{Im}_{\mathcal{G}}(X,V_{h})|\leq\left(\frac{D_{1}(\mathcal{G})}{h}\right)^{h}|X|.$

###### Proof.

We work in the channel $\mathcal{G}^{\prime}=\overline{\mathcal{G}}(X,V_{h})$
rather than the original square commutative graph. In this context we will
prove that if $\mathcal{G}^{\prime}$ is a commutative graph with vertex set
$V^{\prime}_{0}\cup\dots\cup V^{\prime}_{h}$, which satisfies
$D_{1}(\mathcal{G}^{\prime})=|V^{\prime}_{1}|/|V^{\prime}_{0}|$, then

$\displaystyle|V^{\prime}_{h}|\leq\left(\frac{D_{1}(\mathcal{G}^{\prime})}{h}\right)^{h}|V^{\prime}_{0}|.$

Suppose not. Let $\mathcal{G}^{\prime}$ be a counterexample where
$|V^{\prime}_{0}|$ is minimal. Theorem 15 implies that the collection

$\displaystyle\left\\{\emptyset\neq Z\subseteq
V^{\prime}_{0}:|\operatorname{Im}_{\mathcal{G}^{\prime}}(Z,V^{\prime}_{h})|\leq\left(\frac{D_{1}({\mathcal{G}^{\prime}})}{h}\right)^{h}|Z|\right\\}$

is nonempty.

Let $S\subsetneq V^{\prime}_{0}$ be a set of maximal cardinality in the
collection ($S$ cannot equal $V_{0}^{\prime}$ as we have assumed that
$\mathcal{G}^{\prime}$ is a counter example) and
$\mathcal{H}=\overline{\mathcal{G}^{\prime}}(V^{\prime}_{0}\setminus
S,V^{\prime}_{h}\setminus\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{h}))$.
In words $\mathcal{H}$ is the channel consisting of paths in
${\mathcal{G}^{\prime}}$ that do not start in $S$ and do not end in its image
in $V^{\prime}_{h}$. Suppose that $W_{0}\cup W_{1}\cup\dots\cup W_{h}$ are the
layers of $\mathcal{H}$. Observe also that for all $Z\subseteq W_{0}$ and all
$i=1,\dots,h$ we have
$\operatorname{Im}_{\mathcal{H}}(Z,W_{i})=\operatorname{Im}_{\mathcal{G}^{\prime}}(Z,W_{i})$.

$W_{1}$ does not intersect
$\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{1})$ as there would
then exist a path in $\mathcal{H}$ leading to
$\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{h})$. We therefore
have

$\displaystyle|W_{1}|\leq|V^{\prime}_{1}|-|\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{1})|\leq|V^{\prime}_{1}|-D_{1}({\mathcal{G}^{\prime}})|S|=|V^{\prime}_{1}|-\frac{|V^{\prime}_{1}|}{|V^{\prime}_{0}|}\,|S|=|V^{\prime}_{1}|\,\frac{|V^{\prime}_{0}|-|S|}{|V^{\prime}_{0}|}=|W_{0}|\,\frac{|V^{\prime}_{1}|}{|V^{\prime}_{0}|},$

as $|W_{0}|=|V^{\prime}_{0}|-|S|$. Consequently

$\displaystyle
D_{1}(\mathcal{H})\leq\frac{|W_{1}|}{|W_{0}|}\leq\frac{|V^{\prime}_{1}|}{|V^{\prime}_{0}|}=D_{1}({\mathcal{G}^{\prime}}).$
(5)

Let $\emptyset\neq T\subseteq W_{0}$ be any subset that satisfies
$|\operatorname{Im}_{\mathcal{H}}(T,W_{1})|=D_{1}(\mathcal{H})\,|T|$. Let us
get a lower bound on $|\operatorname{Im}_{\mathcal{H}}(T,W_{h})|$. We know
from the maximality of $|S|$ that

$\displaystyle\left(\frac{D_{1}({\mathcal{G}^{\prime}})}{h}\right)^{h}\,|S\cup
T|$ $\displaystyle<$
$\displaystyle|\operatorname{Im}_{\mathcal{G}^{\prime}}(S\cup
T,V^{\prime}_{h})|$ $\displaystyle=$
$\displaystyle|\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{h})|+|\operatorname{Im}_{\mathcal{G}^{\prime}}(T,V^{\prime}_{h})\setminus\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{h})|$
$\displaystyle=$
$\displaystyle|\operatorname{Im}_{\mathcal{G}^{\prime}}(S,V^{\prime}_{h})|+|\operatorname{Im}_{\mathcal{H}}(T,W_{h})|$
$\displaystyle\leq$
$\displaystyle\left(\frac{D_{1}({\mathcal{G}^{\prime}})}{h}\right)^{h}\,|S|+|\operatorname{Im}_{\mathcal{H}}(T,W_{h})|.$

This implies

$\displaystyle|\operatorname{Im}_{\mathcal{H}}(T,W_{h})|>\left(\frac{D_{1}({\mathcal{G}^{\prime}})}{h}\right)^{h}\,|T|.$
(6)

Finally we consider $\mathcal{H}^{\prime}=\overline{\mathcal{H}}(T,W_{h})$,
the channel consisting of all paths in $\mathcal{H}$ starting at $T$.
$\mathcal{H}^{\prime}$ is a square commutative graph with layers
$T_{0}\cup\dots\cup T_{h}$ and magnification ratio
$D_{1}(\mathcal{H}^{\prime})=D_{1}(\mathcal{H})$. By inequalities (6) and (5)
we get:

$\displaystyle|T_{h}|=|\operatorname{Im}_{\mathcal{H}^{\prime}}(T,W_{h})|=|\operatorname{Im}_{\mathcal{H}}(T,W_{h})|>\left(\frac{D_{1}({\mathcal{G}^{\prime}})}{h}\right)^{h}|T|\geq\left(\frac{D_{1}(\mathcal{H})}{h}\right)^{h}|T_{0}|=\left(\frac{D_{1}(\mathcal{H}^{\prime})}{h}\right)^{h}|T_{0}|.$

Thus $\mathcal{H}^{\prime}$ is another counterexample. However,
$|T_{0}|=|T|\leq|W_{0}|=|V^{\prime}_{0}\setminus S|<|V^{\prime}_{0}|$, which
contradicts the minimality of $|V^{\prime}_{0}|$. ∎

A similar result was proven for commutative graphs in [8].

###  5.5 Application to sumsets with a component removed

Our final task is to deduce from Theorem 17 the upper bound on sumsets with a
component removed, which was used in Section 3 .

######  Corollary 18.

Let $h$ be a positive integer. Suppose that $A,B_{1},\dots,B_{h}$ are finite
sets in a commutative group and $E\subseteq A$ a subset of $A$.

If $\emptyset\neq X\subseteq A\setminus E$ is a subset of $A\setminus E$ that
minimizes the quantity

$\displaystyle\sum_{i=1}^{h}\frac{|(Z+B_{i})\setminus(E+B_{i})|}{|Z|}$

over all non-empty subsets $\emptyset\neq Z\subseteq A\setminus E$, then

$\displaystyle|(X+B_{1}+\dots+B_{h})\,\setminus(E+B_{1}+\cdots+B_{h})|\leq\mu^{h}\,|X|,$

where

$\displaystyle\mu:=\mu(X)=\frac{1}{h}\sum_{i=1}^{h}\frac{|(X+B_{i})\setminus(E+B_{i})|}{|X|}.$

###### Proof.

We work in to the hypercube graph $\mathcal{G}$ indexed by $Q_{h}$ with vertex
set given by $U_{I}=(A+\sum_{i\in I}B_{i})\setminus(E+\sum_{i\in I}B_{i})$;
and edge set determined as follows: an edge exists between $u\in V_{I}$ and
$v\in V_{I\cup\\{j\\}}$ if $v-u\in B_{j}.$

$\mathcal{G}$ is square commutative by Lemma 9, because it is precisely the
channel

$\displaystyle\overline{\mathcal{G}}\left(A\setminus
E\,,(A+\sum_{i=1}^{h}B_{i})\setminus(E+\sum_{i=1}^{h}B_{i})\right)$

in the square commutative addition graph
$\mathcal{G}_{+}(A,B_{1},\dots,B_{h})$.

Identifying $Z\subseteq A\setminus E$ with the corresponding subset of
$V_{0}(\mathcal{G})$ gives

$\displaystyle\sum_{i=1}^{h}\frac{|(Z+B_{i})\setminus(E+B_{i})|}{|Z|}=\frac{|\operatorname{Im}_{\mathcal{G}}(Z,V_{1})|}{|Z|}.$

In particular the defining property of $X$ implies that $X$ achieves
$D_{1}(\mathcal{G})$ and so

$\displaystyle\frac{D_{1}(\mathcal{G})}{h}=\frac{1}{h}\,\frac{|\operatorname{Im}_{\mathcal{G}}(X,V_{1})|}{|X|}=\frac{1}{h}\sum_{i=1}^{h}\frac{|\operatorname{Im}_{\mathcal{G}}(X,U_{\\{i\\}})|}{|X|}=\frac{1}{h}\sum_{i=1}^{h}\frac{|(X+B_{i})\setminus(E+B_{i})|}{|X|}=\mu.$

The condition in Theorem 17 is satisfied and so

$\displaystyle|(X+B_{1}+\dots+B_{h})\,\setminus(E+B_{1}+\cdots+B_{h})|=\operatorname{Im}_{\mathcal{G}}(X,V_{h})\leq\left(\frac{D_{1}(\mathcal{G})}{h}\right)^{h}=\mu^{h}\,|X|,$

as claimed. ∎

## References

  * [1]
  * [2] P. Balister and B. Bollobás, _Projections, entropy and sumsets_ , Combinatorica 32 (2012), 125–141.
  * [3] B. Bollobás and A. Thomason, _Projections of bodies and hereditary properties of hypergraphs_ , Bull. London Math. Soc. 27 (1995), 417 424.
  * [4] K. Gyarmati, M. Matolcsi and I.Z. Ruzsa, _Plünnecke’s inequality for different summands_ , in: Building Bridges: between mathematics and computer science, M. Grötschel and G.O.H. Katona. (eds.), Bolyai Society Mathematical Studies Vol. 19, Springer, New York, 2008, 309–320.
  * [5] K. Gyarmati, M. Matolcsi and I.Z. Ruzsa, _A supperadditivity and submultiplicativity property for cardinalities of sumsets_ , Combinatorica 30 (2010), 163–174.
  * [6] M. Madiman, and A.W. Marcus, and P. Tetali, _Entropy and set cardinality inequalities for partition-determined functions_ , Random Structures Algorithms 40 (2012), 399–424.
  * [7] M.B. Nathanson, _Additive Number Theory: Inverse Problems and the Geometry of Sumsets_ , Springer, New York, 1996.
  * [8] G. Petridis, _Upper bounds on the cardinality of higher sumsets_ , To appear in Acta Arithmetica, Preprint: arXiv:1101.5001.
  * [9] H. Plünnecke, _Eine zahlentheoretische Anwendung der Graphtheorie_ , J. Reine Angew. Math. 243 (1970), 171–183.
  * [10] I.Z. Ruzsa, _An application of graph theory to additive number theory_ , Scientia, Ser. A 3 (1989), 97–109.
  * [11] I.Z. Ruzsa, _Cardinality questions about sumsets_ , in: Additive Combinatorics, A. Granville and M.B. Nathanson and J. Solymosi (eds.), CRM Proceedings $\&$ Lecture Notes, American Mathematical Society, New York, 2006, 195–204.
  * [12] I.Z. Ruzsa, _Sumsets and Structure_ , in: Combinatorial Number theory and Additive Group Theory, Springer, New York, 2009.
  * [13] I.Z. Ruzsa, _Towards a noncommutative Plünnecke-type inequality_ , in: An Irregular Mind: Szemerédi is 70 (Bolyai Society Mathematical Studies), Springer, New York, 2010.
  * [14] T. Tao, _Tricks Wiki article: The tensor power trick_ , available at http://terrytao.wordpress.com/2008/08/25/tricks-wiki-article-the-tensor-product-trick/.
  * [15] T. Tao and V.H. Vu, _Additive Combinatorics_ , Cambridge University Press, Cambridge, 2006.

Department Mathematics, University of Rochester, Rochester, NY, USA

Email addresses<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>


††thanks: Present address: Centre de recherche et de restauration des musées
de France, F-75001 Paris

# Mastering disorder in a first-order transition by ion irradiation

S. Cervera  Institut des NanoSciences de Paris, CNRS, Sorbonne Université,
F-75005 Paris, France  M. LoBue  SATIE, ENS Paris Saclay, CNRS, Université
Paris-Saclay, F-91190 Gif-sur-Yvette, France  E. Fontana Present address:
Institut Néel, CNRS, F-38042, Grenoble, France Institut des NanoSciences de
Paris, CNRS, Sorbonne Université, F-75005 Paris, France  Department of Applied
Science and Technology, Politecnico di Torino, I-10129 Torino, Italy  M.
Eddrief  Institut des NanoSciences de Paris, CNRS, Sorbonne Université,
F-75005 Paris, France  V.H. Etgens  Institut des NanoSciences de Paris, CNRS,
Sorbonne Université, F-75005 Paris, France  E. Lamour  Institut des
NanoSciences de Paris, CNRS, Sorbonne Université, F-75005 Paris, France  S.
Macé  Institut des NanoSciences de Paris, CNRS, Sorbonne Université, F-75005
Paris, France  M. Marangolo  Institut des NanoSciences de Paris, CNRS,
Sorbonne Université, F-75005 Paris, France  E. Plouet  Institut des
NanoSciences de Paris, CNRS, Sorbonne Université, F-75005 Paris, France  C.
Prigent  Institut des NanoSciences de Paris, CNRS, Sorbonne Université,
F-75005 Paris, France  S. Steydli  Institut des NanoSciences de Paris, CNRS,
Sorbonne Université, F-75005 Paris, France  D. Vernhet  Institut des
NanoSciences de Paris, CNRS, Sorbonne Université, F-75005 Paris, France  M.
Trassinelli<EMAIL_ADDRESS>Institut des NanoSciences de
Paris, CNRS, Sorbonne Université, F-75005 Paris, France

###### Abstract

The effect of ion bombardment on MnAs single crystalline thin films is
studied. The role of elastic collisions between ions and atoms of the material
is singled-out as the main process responsible for modifying the properties of
the material. Thermal hysteresis suppression, and the loss of sharpness of the
magneto-structural phase transition are studied as a function of different
irradiation conditions. While the latter is shown to be associated with the
ion induced disorder at the scale of the transition correlation length, the
former is related to the coupling between disorder and the large-scale elastic
field associated with the phase coexistence pattern.

The role of quenched disorder on phase changes has been addressed
theoretically for several decades Harris (1974); Imry and Wortis (1979);
Sethna  _et al._ (1993); Berger  _et al._ (2000); Kirkpatrick and Belitz
(2016). In the case of first-order transitions, unraveling the leading
physical mechanisms responsible for the coupling between random impurities and
order parameters is even a harder task. The coexistence of very different
characteristic lengths and the presence of non-equilibrium features like
hysteresis and kinetics make even further the task complex. Nonetheless, as
most of the known large caloric effects take place on the verge of a first-
order ferroic transition Moya  _et al._ (2014), mastering hysteresis
preserving other features (i.e. entropy and temperature changes) has been the
focus of many investigations for the last two decades. At stake, beside the
fundamental interest, such investigations can have a direct impact on the use
of caloric effects for refrigeration and energy conversion applications
Gutfleisch  _et al._ (2016); Lyubina (2017); Gottschall  _et al._ (2019).
Hysteresis reduction in magnetocaloric materials has been successfully
achieved acting on the phase transition globally, getting closer to a critical
point through chemical change (i.e. tuning stoichiometry) Brück  _et al._
(2012); Franco  _et al._ (2018), or using a secondary external field coupled
to the order parameter (e.g. hydro-static pressure, substrate strain)Liu  _et
al._ (2012); Mosca  _et al._ (2008); Moya  _et al._ (2013). Another approach
to reduce hysteresis relays on modifying the phase change mechanism using
local non-homogeneity (e.g. porosity, inclusions) fostering phase nucleation.
Indeed, controlling first-order phase changes in caloric materials using
defects and disorder has been studied at different scales, from the
atomic/chemical Sokolovskiy  _et al._ (2012); Fujita  _et al._ (2014), to the
structural one Lyubina (2011); Niemann  _et al._ (2016). Thence, the
possibility to tune the amount of disorder in a model-system represents a
unique opportunity for experimental investigations on phase change in solid-
state systems. Moreover, it can pave the way to develop new methods for
tailoring the functional properties of materials where phase changes take
place.

In this letter, we study the modifications induced by the collision and
implantation of ions in manganese arsenide thin monocrystals. Bulk manganese
arsenide (MnAs) shows a first-order magneto-structural transition from
ferromagnetic to paramagnetic order accompanied by a lattice symmetry switch
when getting above the transition temperature $T_{t}=313$ K Menyuk  _et al._
(1969). From this perspective, MnAs can be considered as a prototypical first-
order magnetocaloric material. Previous studies Trassinelli  _et al._ (2014,
2017) proved thermal hysteresis suppression in ion bombarded MnAs single
crystal films, keeping the caloric effect intensity unchanged. Here, the
mechanisms underlying the modifications of the transition after ion
bombardment are investigated on single crystalline $150$ nm thick MnAs films
under different irradiation conditions (i.e . ion mass, ion kinetic energy,
fluences, etc.).

The MnAs films have been obtained by molecular beam epitaxy on GaAs(001) $0.3$
mm thick substrates. The deposited MnAs is oriented with the
$\alpha$-MnAs$[0001]$ and $\beta$-MnAs$[001]$ axis parallel to
GaAs$[\bar{1}10]$ Breitwieser  _et al._ (2009). In thin films, due to the
epitaxial strain, the phase coexistence between the ferromagnetic
$\alpha$-phase with hexagonal structure (NiAs-type) and the paramagnetic
$\beta$-phase with orthorhombic structure (MnP-type), takes place over an
extended temperature range ($280$–$320$ K) Däweritz (2006), in contrast with
the sharper transition observed at the temperature $T_{t}=313$ K in bulk
single crystals Wilson and Kasper (1964).

Ion irradiations have been performed at two facilities: the electron-cyclotron
ion source SIMPA facility (Paris, France) Gumberidze  _et al._ (2010), and the
line IRRSUD facility at the GANIL accelerator (Caen, France). At SIMPA,
samples have been irradiated with different ions (i.e. helium, oxygen, neon,
argon and krypton) with kinetic energies ranging from $22$ to $260$ keV. The
ion fluence $\Phi$ has been varied between $1\times 10^{12}$ ions/cm2 and
$6\times 10^{15}$ ions/cm2, corresponding to an irradiation time spanning from
few tens of seconds to several hours. The energy of the different ion beams
and the incident angle have been chosen in order to reach an average
penetration depth corresponding to the half thickness of the film. At IRRSUD,
a beam of isotopic ${}^{36}\\!$Ar with an energy of $35.28$ MeV has been used.
In this case no ions are implanted in the MnAs film, most of them being
stopped in the GaAs substrate. The fluence has been varied from $4\times
10^{12}$ to $1\times 10^{15}$ ions/cm2.

During the interaction with a solid, the ion transfers its kinetic and
potential energies to the target atoms by a series of processes that can be
schematically separated in two categories: one due to the interaction with the
target nuclei, the other due to the interaction with the electrons. The
electron interaction is inelastic, and entails small or no lattice distortion
into the target. The ion energy losses, including those related to the
potential energy of the ion, are transferred to the solid via excitation of
phonons, with an increasing of the temperature along the trajectory. Nuclear
collisions are the most probable process at low velocity and/or for heavy
ions. Each collision can be assumed to be binary, and elastic Nastasi  _et
al._ (1996); Nordlund  _et al._ (2018); Nordlund (2019). It can lead to the
displacement of sample atoms from their site, with the creation of vacancies
and interstitial atoms in the sample lattice. If the energy transferred to the
recoil atom is higher than twice the displacement energy of a single atom, a
cascade of secondary collisions is generated, producing a cluster of defects
Nastasi  _et al._ (1996). For a same kinetic energy, heavy ions produces a
higher number of collisions per ion than light ions. This is due to the higher
cross-section of the primary impact, and to the more favorable momentum
transfer to target atoms, as well as to the consequent secondary collisions in
the cascade.

At the ion kinetic energies of SIMPA ($E_{\text{kin}}$ less than 300 keV), the
nucleus–nucleus interaction between incoming ions and sample atoms is the main
process responsible for induced modifications. At the ion kinetic energies of
IRRSUD, the probability of nuclear processes decreases while inelastic
processes start to occur. Due to the small ion potential energy
($E_{p}\lesssim 5$ keV), compared to the kinetic energy, and to the metallic
nature of the MnAs samples, the local heating from the electron interaction is
not expected to induce noticeable modifications in the material. As we will
see, elastic nuclear collisions remain the leading process that modify the
properties of the irradiated sample.

Figure 1:  Isofield ($H=1$ T) magnetization curves $M(T)$ (top) and
corresponding first (bottom) and second derivative (middle) measured on
reference (left) and irradiated (right) samples. The relevant temperatures
corresponding to maxima and minima of the second derivative are indicated
together with the loop area $A$ of $M(T)$ and the FWHM of the first
derivative. Cooling and heating curves are represented in blue and red,
respectively.

The two main modifications observed after ion bombardment are hysteresis
reduction, and the loss of sharpness of the transition (see Fig.1), often
referred to as rounding Imry and Wortis (1979). To investigate them, isofield
thermomagnetic $M(T)$ curves have been measured at constant field ($H=1$ T) by
a SQUID device. All the magnetization measurements have been carried along the
easy magnetization direction (i.e. in the film plane, and along the easy
axis). This makes the proportionality between $M(T)$ and the ferromagnetic
$\alpha$-phase a reliable assumption even under the application of a
relatively small field of $1$ T. Before each measurement, the material has
been heated up to $350$ K in order to erase any trace of the low-temperature
phase, resetting sample history Bratko  _et al._ (2012). Hysteresis,
transition temperatures, and rounding are extracted from $M(T)$ curves and
their derivatives. Whereas hysteresis, and its reduction, are phenomena taking
place close to transition temperature $T_{t}$, the transition rounding is
associated with a widening of the phase coexistence region far away from it.
Here, the thermal hysteresis width, $\Delta T_{hyst}$, is evaluated from the
area $A$ between the $M(T)$ heating and cooling curves (Fig. 1 top) normalized
to the saturation magnetization $M_{s}$, $\Delta T_{\mathrm{hyst}}=A/M_{s}$
111An approach commonly used in the field of loss, and hysteresis modelling;
it amounts to consider the effective width of an equivalent rectangular
hysteresis cycle. See Bertotti (1985, 1998). $M_{s}$ is the magnetization
measured at $100$ K under the application of a field $H=1$ T. Indeed, most
samples have been irradiated within regimes where the maximum magnetization
$M_{s}$ is not, or is marginally modified.

Concerning the evaluation of the rounding, the data analysis has to
disentangle the effect due to defects induced quenched-in disorder Vidal  _et
al._ (2006); Mosca  _et al._ (2008) from the strain-induced broadening at the
magnetostructural phase transition. The latter is characterized by a linear
evolution of the phase fraction, across the transition, as a function of $T$.
As shown in Kaganer  _et al._ (2000, 2002); Plake  _et al._ (2002, 2003);
Däweritz  _et al._ (2003); Breitwieser  _et al._ (2009), this behavior is
driven by a mesoscopic phase-domain stripes pattern, and by its long-range
elastic field. The former is relevant far from $T_{t}$ and is associated with
the presence of minority-phase regions whose stability is made possible by a
local shift of $T_{t}$ Imry and Wortis (1979). To tag the irradiation rounding
effect only, we introduce the variable

$\Delta
T_{\mathrm{rnd}}=\mathrm{FWHM}_{\mathrm{IRR}}-\mathrm{FWHM}_{\mathrm{REF}}$
(1)

obtained by the width at half maximum ($\mathrm{FWHM}_{\mathrm{IRR}}$) of the
first derivative of $M(T)$ of the irradiated films minus the contribution
$\mathrm{FWHM}_{\mathrm{REF}}$ of the pristine sample (see Fig. 1 bottom).
Eventually, to identify the main part of the phase coexistence interval, the
second derivative $d^{2}M/dT^{2}$ is used. The upper and lower bounds, $T_{1}$
and $T_{2}$, of the steepest part of the transition are identified with the
maximum and the minimum of $d^{2}M/dT^{2}$ respectively. Some typical
irradiation induced modifications are presented, as an example, in Fig. 1
where the heating ($T^{h}_{1}$, and $T_{2}^{h}$) and cooling ($T^{c}_{1}$, and
$T_{2}^{c}$) temperatures is marked over the $M(T)$ (top) and $d^{2}M/dT^{2}$
(middle) curves of the pristine and of an irradiated sample.

In order to disentangle the role of binary-collisions induced defects, from
the one of ion implantation in modifying the target properties, we firstly
compare samples features with respect to average collision density or
implanted ion density, $\rho_{c}$, and $\rho_{i}$, respectively. These
quantities are estimated using the applied ion fluences, and the output of the
ion-matter interaction Monte Carlo code SRIM/TRIM Ziegler and Biersack (1985);
Ziegler  _et al._ (2010). The two densities induced by bombarding a sample of
thickness $t$ with a fluence $\Phi$ are estimated through the following
expressions: $\rho_{i}=f\Phi/t$, and $\rho_{c}=N_{\mathrm{coll}}\Phi/t$, where
$f$, is the fraction of ions stopped, and $N_{\mathrm{coll}}$ is the average
number of binary collisions induced by a single ion in the film 222Despite the
well-known SRIM/TRIM trend of slightly overestimating the number of induced
defects Nastasi  _et al._ (1996); Stoller  _et al._ (2013); Nordlund (2019),
the predicted agglomerations (i.e. mixed-up vacancies and interstitials
clusters) are rather similar to the ones obtained by advanced many-body
molecular dynamics calculations taking into account collective behavior and
temperature effects Nordlund  _et al._ (1999); Calder  _et al._ (2010); Kim
_et al._ (2012); Nordlund  _et al._ (2018); Nordlund (2019), and to the ones
observed experimentally as well Lu  _et al._ (2016).. For our specific cases,
$f$, and $N_{\mathrm{coll}}$ have a range of $[0,1]$ and [50,5000],
respectively. Thus $\rho_{i}$ and $\rho_{c}$ differ by order of magnitude and
strongly depend on the projectile ion characteristics

The hysteresis width $\Delta T_{\mathrm{hyst}}$ is shown in Fig.2 as a
function of $\rho_{i}$ (top frame) and of $\rho_{c}$ (bottom frame). Whereas
no correlation is apparent between $\Delta T_{\mathrm{hyst}}$ and $\rho_{i}$,
a clear trend can be appreciated when $\Delta T_{\mathrm{hyst}}$ is plotted
against $\rho_{c}$. More precisely, $\Delta T_{\mathrm{hyst}}$ decreases as a
function of $\rho_{c}$ until its total suppression at $\rho_{c}\approx
10^{21}-10^{22}$ cm-3. It is noteworthy that the three points relative to fast
Ar irradiation, where no ions get implanted into the sample, spread over the
same hysteresis decreasing trend curve when plotted against $\rho_{c}$ (bottom
frame of Fig. 2). Data from fast, and slow ions follow the same tendency with
respect to the collision density. This is one of the main findings of this
letter, and it shows that, within the considered fluence interval, the
relevant defects, in terms of modification of the phase transition, are the
ones produced by binary elastic collisions.

Figure 2: Thermal hysteresis area as a function of the average density of
implanted ions $\rho_{i}$ (top), and of the average density of elastic
collisions $\rho_{c}$ (bottom). In light blue the value of the pristine sample
is reported. The uncertainties on the $x$-axis are mainly determined by the
fluence evaluation, which can be critical for some beam preparation. The
uncertainty on the $y$-axis is due to the SQUID measurement and the
interpolation of the data affected by noise. The dashed line represents the
best fit of the data with the formula discussed in the text.  Figure 3:
Comparison between $M(T)$ loops over heating, and cooling (in red and blue),
measured on the pristine sample (top), on a He irradiated sample (middle) and
on an O irradiated sample (bottom). In the inset, the difference $\Delta
T_{2}=T^{h}_{2}-T^{c}_{2}$ between the values of $T_{2}$ over heating and
cooling is shown as function of $\rho_{c}$.

To get a better insight into the mechanisms underlying thermal hysteresis in
MnAs films, the amplitude of the phase coexistence interval, limited by the
above defined temperatures $T_{2}$, and $T_{1}$, is studied over heating, and
cooling as a function of $\rho_{c}$. When hysteresis is present, the
aforementioned second derivative maximum and minimum show different values
along the cooling, and heating curves. The temperatures corresponding to these
maxima, and minima are plotted in Fig. 3 as a function of the collision
density $\rho_{c}$ measured on heating (red), and cooling (blue).

The upper limit of the phase coexistence interval, $T_{1}$, is unaffected by
irradiation, and does not show hysteresis (i.e. values over heating and
cooling are similar, they are marked with a black dashed line in Fig. 3); on
the contrary, the difference $\Delta T_{2}=T_{2}^{h}-T_{2}^{c}$ between
$T_{2}$ over heating ($T^{h}_{2}$, red dashed lines and arrows), and cooling
is apparent and gets reduced, and eventually suppressed, as a function of
$\rho_{c}$. Following Kaganer  _et al._ (2002), $T_{1}$ can be considered as
the closest approximation to the actual transition point $T_{t}$ (i.e. the one
of a bulk single crystal). On the other hand, as apparent from Fig. 3, the
reduction of hysteresis takes place as an increasing of $T_{2}^{c}$, in
irradiated samples, with no change of $T_{2}^{h}$. In other words, hysteresis
disappears through the collapse of the cooling $M(T)$ curve onto the heating
one. Thence, hysteresis is mainly associated to supercooled metastable states.

The transition rounding $\Delta T_{\mathrm{rnd}}$ (Eq. (1)) also shows a
systematic trend as a function of the collision density $\rho_{c}$ (Fig. 4,
top). Its clear departure from the reference value, at $\rho_{c}\approx
4\times 10^{20}$ cm-3, is followed by a strong increasing with a slope
depending on the ion type used for irradiation. Furthermore, the points
collapse over the same curve when normalizing the relative rounding to the
square root of the ion mass number $m$, $\Delta T_{\mathrm{rnd}}/\sqrt{m}$
(Fig. 4, bottom).

Figure 4: Relative rounding $\Delta T_{\mathrm{rnd}}$ from the FWHM of $dM/dT$
curves without (top) and with $\sqrt{m})$ mass rescaling (bottom). The dashed
line represents the best fit of the data with the function
$f(p)=c\sqrt{p(1-p)}$ (see text).

The explanation of the observed modifications, after irradiation, is two-fold.
On the one hand, rounding takes place far from $T_{t}$ and is expected to be
driven by the phase transition correlation length $\xi$; on the other hand,
hysteresis suppression takes place near $T_{t}$ where stripes domains, and
their long-range elastic field drive transition kinetics at the mesoscale
Kaganer  _et al._ (2002). The observed rounding behavior fits pretty well
within the approach reported in Imry and Wortis (1979). Considering a magnetic
lattice model with a probability $p$ to get a lattice site occupied by some
sort of impurity, it is shown that, even when $p\ll 1$, a relevant transition
rounding can appear due to the local fluctuations of impurity density. For a
random impurity distribution, density fluctuations are proportional to the
variance $p(1-p)$. The key issue to get a stable rounding is the relationship
between the phase transition correlation length $\xi$, and the characteristic
size $L$ of the regions where the impurity density fluctuation makes the
minority phase (i.e. the high temperature phase when $T<T_{t}$, or the low
temperature one when $T>T_{t}$) energetically favored. Thence, the smearing-
out of the transition is driven by the dimensionality $d$ of the magnetic
system, and by the way the interface energy between the two phases scales with
respect to the region size $L$. Following Imry and Wortis (1979), a spin
lattice of dimensionality $d=3$, with discrete symmetry, and with a surface
tension between phases over a region of size $L$ scaling as $L^{2}$ is
expected to be unaffected by quenched disorder when $L<\xi$. Rounding appears
when $L\sim\xi$, and scales as $\sqrt{p(1-p)/L^{3}}$ when $L>\xi$. Assuming
the probability $p$, to get an impurity to be $p\propto\rho_{c}$, from Fig. 4
it can be deduced that $\xi\sim L$ when $\rho_{c}\approx 4\times 10^{20}$
cm-3. From cascade simulations, the typical volume of collision clusters is
known to be $\propto 1/m$, where $m$ is the ion mass. Assuming elastic-
collision cascades as the origin of the impurities implies $L^{3}\propto 1/m$,
a feature that explains the higher slopes showed by samples irradiated with
heavier ions, and the collapse of all the points onto the same curve after the
$1/\sqrt{m}$ normalization 333Similar curves can be obtained by normalizing
with respect to the number of collision per ion and average size of clusters
of defects.. Figure 4 (bottom) shows the mass normalized relative rounding
data fitted with a function
$f(\rho_{c})=c\sqrt{a\frac{\rho_{c}}{\rho_{0}}\left(1-a\frac{\rho_{c}}{\rho_{0}}\right)}\equiv
c\sqrt{p(1-p)}$. $\rho_{0}=2.92\times 10^{22}$ cm-3 is the atomic density of
MnAs and $a$ is a proportionality constant between $p$ and $\rho_{c}/\rho_{0}$
that incorporates possible auto-healing processes, not taken into account by
SRIM/TRIM, and possible activation thresholds. A value of $a=(9.7\pm 0.6)\%$
is found.

This shows that far away from the transition temperature, the minority phase
(i.e. the $\beta$-phase at low, and the $\alpha$-one at high temperature)
develops as randomly distributed droplets before the building-up of the
elastic-domain stripe structure. This has been observed by scanning probe
microscopy Plake  _et al._ (2002), and by atomic force microscopy Däweritz
_et al._ (2003). Actually, whereas closer to $T_{t}$ energy minimization is
dominated by the long-range elastic interaction between stripes Kaganer  _et
al._ (2000), in the first stages of the transition the leading energy terms
are local, and fully led by the size $L$ of regions where the precursor
develops.

Hysteresis is suppressed by ion bombardment within the collision density
interval $3\times 10^{20}$ cm${}^{-3}\lesssim\rho_{c}\lesssim 10^{21}$ cm-3,
as apparent in Fig. 3. However, as clearly put in Kaganer  _et al._ (2002),
after the first nucleation stage the phase-coexistence stripes pattern builds-
up and the resulting thermal hysteresis can hardly be explained through a
droplet-nucleation mechanism. Actually, while only the cooling $dM/dT$ curve
plotted in Fig. 1 (bottom) for the non-irradiated sample shows a good
agreement with the linear phase-evolution picture described in Refs. Kaganer
_et al._ (2000, 2002), all the other curves show a non-linear $M(T)$. Besides,
Fig. 1 (bottom) shows that hysteresis reduces jointly with the loss of
linearity of the cooling $M(T)$ curve. Higher values of the maximum of $dM/dT$
implying a faster phase kinetics. Similar asymmetries of transition kinetics
are a rather common feature of first order phase transitions, from the best
known example of the water-ice transition to the different kinetics observed
under cooling, and heating in FeRh films Uhlíř  _et al._ (2016). Here, as
noticeable in Fig.3, the difference between the cooling, and heating $M(T)$
curves depends on the lower slope of the formers, and on the entailed lower
$T_{2}$ (i.e. a coexistence region lasting till a lower temperature).
Furthermore, the observed loss of linearity of the cooling curves, and their
increasing slope, going hand-in-hand with hysteresis reduction, can be
interpreted as a modification of the elastic field associated with the stripes
domain structure.

A possible clue to explain this behavior comes from the observation of the
distortion of the regular stripes pattern in MnAs films after ion irradiation
Trassinelli  _et al._ (2014), with an an increasing density of finite-length
stripes. These defects have been observed in non-irradiated samples too Plake
_et al._ (2003); Däweritz  _et al._ (2003); Breitwieser  _et al._ (2009). They
are associated to the non-linear region of $M(T)$ and they mostly disappear
within the ordered stripes structure getting closer to the transition
temperature. Finite-length stripes are expected to behave as topological
defects, modifying the elastic energy with their stress field, similarly to
the way unbound edge-dislocations do in 3D solids Landau  _et al._ (1986);
Nabarro (1952), and in 2D mesomorphic phases Kleman and Lavrentovich (2003).
Their increased density in irradiated samples 444as shown in Fig.3 of
Trassinelli  _et al._ (2014) can be at the origin of the suppression of the
supercooled metastable states underlying hysteresis, either by changing the
phase fraction through nucleation of pairs or by renormalizing the effective
elastic constants.

This explanation, still rather conjectural, makes the point that ion-induced
disorder directly modifies the phase-domain patterning. In this case, the
relevant scale is the phase-domain characteristic length (i.e. the stripes
spacing, $d_{s}\approx 0.73~{}\mu$m Trassinelli  _et al._ (2014)). Over such a
large scale, the average collision density $\rho_{c}\propto p$ is expected to
be the relevant quantity. The dashed curve in Fig. 2 (bottom) is obtained
using as a fitting function $f(\rho_{c})\propto 1/(p_{0}+a\
\rho_{c}/\rho_{0})$, where $p_{0}$ is a constant describing the impurities
present in the sample before the irradiation, which is found to be
$p_{0}=(7.3\pm 2.3)\times 10^{-4}$. It shows that, besides reducing
hysteresis, collision-induced defects can be used to tailor the film domain
pattern in the phase coexistence region.

To conclude: in this letter, we address the changes induced in MnAs thin films
by ion irradiation. It is shown that elastic ion-atom collisions are the main
mechanism responsible for modifying the magnetic properties of the material.
Besides, modifications induced by ion collisions are shown to act at two
different scales. At the short range, collisions serves as nucleation seeds of
precursors responsible for the loss of sharpness of the phase change far from
the transition temperature. At a larger scale, collisions modify the elastic
energy by softening the long-range elastic field associated with the substrate
coupling. Thus new topological defects creation is favored in a distorted
stripe pattern and the thermal hysteresis is reduced until its elimination.

Disorder induced by light ions irradiation of magnetic thin films has been
recently investigated through domain wall motion measurements focusing on
spintronics applications van der Jagt  _et al._ (2022). Here, the effect of
irradiation with ions of different mass is investigated through the behavior
of the first order magneto-structural transition on MnAs thin epitaxial films.
Hysteresis suppression, transition rounding, and the tailoring of the phase-
domain pattern are observed opening unique opportunities in terms of
applications to magnetocaloric devices, and to design of novel magnetic
heterostructures.

###### Acknowledgements.

The authors acknowledge the staff (and in particular D. Hrabovsky) of the MPBT
(physical properties - low temperature) platform of Sorbonne Université for
their support. This work was supported by French state funds managed by the
ANR within the Investissements d’Avenir programme under reference
ANR-11-IDEX-0004-02, and within the framework of the Cluster of Excellence
MATISSE led by Sorbonne Universités, and of the project HiPerTher-Mag
(ANR-18-CE05-0019).

## References

  * Harris (1974) A. Brooks Harris, “Effect of random defects on the critical behaviour of Ising models,” J. Phys. C: Solid State Phys. 7, 1671 (1974).
  * Imry and Wortis (1979) Yoseph Imry and Michael Wortis, “Influence of quenched impurities on first-order phase transitions,” Phys. Rev. B 19, 3580 (1979).
  * Sethna  _et al._ (1993) James P Sethna, Karin Dahmen, Sivan Kartha, James A Krumhansl, Bruce W Roberts, and Joel D Shore, “Hysteresis and hierarchies: Dynamics of disorder-driven first-order phase transformations,” Phys. Rev. Lett. 70, 3347 (1993).
  * Berger  _et al._ (2000) A. Berger, A. Inomata, J.S. Jiang, J.E. Pearson, and SD Bader, “Experimental observation of disorder-driven hysteresis-loop criticality,” Phys. Rev. Lett. 85, 4176 (2000).
  * Kirkpatrick and Belitz (2016) T.R. Kirkpatrick and D. Belitz, “Stable phase separation and heterogeneity away from the coexistence curve,” Phys. Rev. B 93, 144203 (2016).
  * Moya  _et al._ (2014) X. Moya, S. Kar-Narayan, and N. D. Mathur, “Caloric materials near ferroic phase transitions,” Nat. Mater. 13, 439–450 (2014).
  * Gutfleisch  _et al._ (2016) O. Gutfleisch, T. Gottschall, M. Fries, D. Benke, I. Radulov, K. P. Skokov, H. Wende, M. Gruner, M. Acet, P. Entel, and M. Farle, “Mastering hysteresis in magnetocaloric materials,” Phil. Trans. R. Soc. A 374, 20150308 (2016).
  * Lyubina (2017) Julia Lyubina, “Magnetocaloric materials for energy efficient cooling,” J. Phys. D 50, 053002 (2017).
  * Gottschall  _et al._ (2019) Tino Gottschall, Konstantin P. Skokov, Maximilian Fries, Andreas Taubel, Iliya Radulov, Franziska Scheibel, Dimitri Benke, Stefan Riegg, and Oliver Gutfleisch, “Making a cool choice: The materials library of magnetic refrigeration,” Adv. Energy Mater. 9, 1901322 (2019).
  * Brück  _et al._ (2012) E. Brück, N.T. Trung, Z.Q. Ou, and K.H.J. Buschow, “Enhanced magnetocaloric effects and tunable thermal hysteresis in transition metal pnictides,” Scr. Mater. 67, 590–593 (2012).
  * Franco  _et al._ (2018) V. Franco, J. S. Blázquez, J. J. Ipus, J. Y. Law, L. M. Moreno-Ramírez, and A. Conde, “Magnetocaloric effect: From materials research to refrigeration devices,” Prog. Mater. Sci. 93, 112–232 (2018).
  * Liu  _et al._ (2012) Jian Liu, Tino Gottschall, Konstantin P. Skokov, James D. Moore, and Oliver Gutfleisch, “Giant magnetocaloric effect driven by structural transitions,” Nat. Mater. 11, 620–626 (2012).
  * Mosca  _et al._ (2008) D. H. Mosca, F. Vidal, and V. H. Etgens, “Strain engineering of the magnetocaloric effect in MnAs epilayers,” Phys. Rev. Lett. 101, 125503 (2008).
  * Moya  _et al._ (2013) X. Moya, L. E. Hueso, F. Maccherozzi, A. I. Tovstolytkin, D. I. Podyalovskii, C. Ducati, L. C. Phillips, M. Ghidini, O. Hovorka, A. Berger, M. E. Vickers, E. Defay, S. S. Dhesi, and N. D. Mathur, “Giant and reversible extrinsic magnetocaloric effects in La0.7Ca0.3MnO3 films due to strain,” Nat. Mater. 12, 52–58 (2013).
  * Sokolovskiy  _et al._ (2012) V. Sokolovskiy, V. Buchelnikov, M. Zagrebin, P. Entel, S. Sahoo, and M. Ogura, “First-principles investigation of chemical and structural disorder in magnetic Ni2Mn1+xSn1-x heusler alloys,” Phys. Rev. B 86, 134418 (2012).
  * Fujita  _et al._ (2014) A. Fujita, D. Matsunami, and H. Yako, “Realization of small intrinsic hysteresis with large magnetic entropy change in La0.8Pr0.2(Fe0.88Si0.10Al0.02)13 by controlling itinerant-electron characteristics,” Appl. Phys. Lett. 104, 122410 (2014).
  * Lyubina (2011) Julia Lyubina, “Recent advances in the microstructure design of materials for near room temperature magnetic cooling,” J. Appl. Phys. 109, 07A902 (2011).
  * Niemann  _et al._ (2016) R. Niemann, S. Hahn, A. Diestel, A. Backen, L. Schultz, K. Nielsch, M. F.-X. Wagner, and S. Fähler, “Reducing the nucleation barrier in magnetocaloric heusler alloys by nanoindentation,” APL Mater. 4, 064101 (2016).
  * Menyuk  _et al._ (1969) N. Menyuk, J.A. Kafalas, K. Dwight, and J.B. Goodenough, “Effects of pressure on the magnetic properties of MnAs,” Phys. Rev. 177, 942 (1969).
  * Trassinelli  _et al._ (2014) M. Trassinelli, M. Marangolo, M. Eddrief, V. H. Etgens, V. Gafton, S. Hidki, E. Lacaze, E. Lamour, C. Prigent, J.-P. Rozet, S. Steydli, Y. Zheng, and D. Vernhet, “Suppression of the thermal hysteresis in magnetocaloric MnAs thin film by highly charged ion bombardment,” Appl. Phys. Lett. 104, 081906 (2014).
  * Trassinelli  _et al._ (2017) M. Trassinelli, L. Bernard Carlsson, S. Cervera, M. Eddrief, V. H. Etgens, E. V. Gafton, E. Lacaze, E. Lamour, A. Lévy, S. Macé, C. Prigent, J. P. Rozet, S. Steydli, M. Marangolo, and D. Vernhet, “Low energy ne ion beam induced-modifications of magnetic properties in MnAs thin films,” J. Phys. Condens. Matter 29, 055001 (2017).
  * Breitwieser  _et al._ (2009) R. Breitwieser, Franck Vidal, I.L. Graff, Massimiliano Marangolo, Mahmoud Eddrief, J-.C. Boulliard, and VH Etgens, “Phase transition and surface morphology of MnAs/GaAs (001) studied with in situ variable-temperature scanning tunneling microscopy,” Phys. Rev. B 80, 045403 (2009).
  * Däweritz (2006) L. Däweritz, “Interplay of stress and magnetic properties in epitaxial MnAs films,” Rep. Prog. Phys. 69, 2581 (2006).
  * Wilson and Kasper (1964) R.H. Wilson and J.S. Kasper, “The crystal structure of mnas above 40 c,” Acta Crystallogr. 17, 95–101 (1964).
  * Gumberidze  _et al._ (2010) A. Gumberidze, M. Trassinelli, N. Adrouche, C. I. Szabo, P. Indelicato, F. Haranger, J. M. Isac, E. Lamour, E. O. Le Bigot, J. Merot, C. Prigent, J. P. Rozet, and D. Vernhet, “Electronic temperatures, densities, and plasma X-ray emission of a 14.5 GHz electron-cyclotron resonance ion source,” Rev. Sci. Instrum. 81, 033303–10 (2010).
  * Nastasi  _et al._ (1996) M. Nastasi, J. Mayer, and J.K. Hirvonen,  _Ion-Solid Interactions: Fundamentals and Applications_ (Cambridge University Press, 1996).
  * Nordlund  _et al._ (2018) Kai Nordlund, Steven J. Zinkle, Andrea E. Sand, Fredric Granberg, Robert S. Averback, Roger E. Stoller, Tomoaki Suzudo, Lorenzo Malerba, Florian Banhart, William J. Weber, Francois Willaime, Sergei L. Dudarev, and David Simeone, “Primary radiation damage: A review of current understanding and models,” J. Nucl. Mater 512, 450–479 (2018).
  * Nordlund (2019) K. Nordlund, “Historical review of computer simulation of radiation effects in materials,” J. Nucl. Mater 520, 273–295 (2019).
  * Bratko  _et al._ (2012) Milan Bratko, Kelly Morrison, Ariana de Campos, Sergio Gama, Lesley F. Cohen, and Karl G. Sandeman, “History dependence of directly observed magnetocaloric effects in (Mn,Fe)As,” Appl. Phys. Lett. 100, 252409 (2012).
  * Bertotti (1985) Giorgio Bertotti, “Physical interpretation of eddy current losses in ferromagnetic materials. i. theoretical considerations,” J. Appl. Phys. 57, 2110–2117 (1985).
  * Bertotti (1998) Giorgio Bertotti,  _Hysteresis in Magnetism: for Physicists, Materials Scientists, and Engineers_ (Academic Press, 1998).
  * Vidal  _et al._ (2006) F. Vidal, O. Pluchery, N. Witkowski, V. Garcia, M. Marangolo, V. H. Etgens, and Y. Borensztein, “$\alpha-\beta$ phase transition in MnAs/GaAs (001) thin films: An optical spectroscopic investigation,” Phys. Rev. B 74, 115330 (2006).
  * Kaganer  _et al._ (2000) V.M. Kaganer, B. Jenichen, F. Schippan, W. Braun, L. Däweritz, and K.H. Ploog, “Strain-mediated phase coexistence in heteroepitaxial films,” Phys. Rev. Lett. 85, 341 (2000).
  * Kaganer  _et al._ (2002) V.M. Kaganer, B. Jenichen, F. Schippan, W. Braun, L. Däweritz, and K.H. Ploog, “Strain-mediated phase coexistence in MnAs heteroepitaxial films on GaAs: An x-ray diffraction study,” Phys. Rev. B 66, 045305 (2002).
  * Plake  _et al._ (2002) T. Plake, M. Ramsteiner, V.M. Kaganer, B. Jenichen, M. Kästner, L. Däweritz, and K.H. Ploog, “Periodic elastic domains of coexisting phases in epitaxial MnAs films on GaAs,” Appl. Phys. Lett. 80, 2523–2525 (2002).
  * Plake  _et al._ (2003) T Plake, T. Hesjedal, J. Mohanty, M. Kästner, L. Däweritz, and K.H. Ploog, “Temperature-dependent magnetic force microscopy investigation of epitaxial MnAs films on GaAs (001),” Appl. Phys. Lett. 82, 2308–2310 (2003).
  * Däweritz  _et al._ (2003) L. Däweritz, M. Kästner, T. Hesjedal, T. Plake, B. Jenichen, and K.H. Ploog, “Structural and magnetic order in MnAs films grown by molecular beam epitaxy on GaAs for spin injection,” . Cryst. Growth 251, 297–302 (2003).
  * Ziegler and Biersack (1985) James F. Ziegler and Jochen P. Biersack, “The stopping and range of ions in matter,” in  _Treatise on Heavy-Ion Science: Volume 6: Astrophysics, Chemistry, and Condensed Matter_, edited by D. Allan Bromley (Springer US, Boston, MA, 1985) pp. 93–129.
  * Ziegler  _et al._ (2010) James F. Ziegler, M. D. Ziegler, and J. P. Biersack, “SRIM - the stopping and range of ions in matter (2010),” Nucl. Instrum. Methods B 268, 1818–1823 (2010).
  * Stoller  _et al._ (2013) R. E. Stoller, M. B. Toloczko, G. S. Was, A. G. Certain, S. Dwaraknath, and F. A. Garner, “On the use of srim for computing radiation damage exposure,” Nucl. Instrum. Methods B 310, 75–80 (2013).
  * Nordlund  _et al._ (1999) K. Nordlund, J. Keinonen, M. Ghaly, and R. S. Averback, “Coherent displacement of atoms during ion irradiation,” Nature 398, 49–51 (1999).
  * Calder  _et al._ (2010) A. F. Calder, D. J. Bacon, A. V. Barashev, and Yu N. Osetsky, “On the origin of large interstitial clusters in displacement cascades,” Philos. Mag. 90, 863–884 (2010).
  * Kim  _et al._ (2012) Sang-Pil Kim, Huck Beng Chew, Eric Chason, Vivek B. Shenoy, and Kyung-Suk Kim, “Nanoscale mechanisms of surface stress and morphology evolution in fcc metals under noble-gas ion bombardments,” Proc. R. Soc. A 468, 2550–2573 (2012).
  * Lu  _et al._ (2016) Chenyang Lu, Ke Jin, Laurent K. Béland, Feifei Zhang, Taini Yang, Liang Qiao, Yanwen Zhang, Hongbin Bei, Hans M. Christen, Roger E. Stoller, and Lumin Wang, “Direct observation of defect range and evolution in ion-irradiated single crystalline Ni and Ni binary alloys,” Sci. Rep. 6, 19994 (2016).
  * Uhlíř  _et al._ (2016) V. Uhlíř, Jon Ander Arregi, and Eric E. Fullerton, “Colossal magnetic phase transition asymmetry in mesoscale ferh stripes,” Nat. Commun. 7 (2016).
  * Landau  _et al._ (1986) Lev Davidovich Landau, Evgenij M Lifšic, Evegnii Mikhailovich Lifshitz, Arnold Markovich Kosevich, and Lev Petrovich Pitaevskii,  _Theory of elasticity: volume 7_ , Vol. 7 (pergamon, Oxford, 1986).
  * Nabarro (1952) Frank Reginald Nunes Nabarro, “Mathematical theory of stationary dislocations,” Adv. Phys. 1, 269–394 (1952).
  * Kleman and Lavrentovich (2003) Maurice Kleman and Oleg D. Lavrentovich,  _Soft matter physics: an introduction_ (Springer, 2003).
  * van der Jagt  _et al._ (2022) Johannes W. van der Jagt, Vincent Jeudy, André Thiaville, Mamour Sall, Nicolas Vernier, Liza Herrera Diez, Mohamed Belmeguenai, Yves Roussigné, Salim M Chérif, Mouad Fattouhi, _et al._ , “Revealing nanoscale disorder in W/Co-Fe-B/MgO ultrathin films using domain-wall motion,” Phys. Rev. Appl. 18, 054072 (2022).