# A sumset inequality

A friend asked me the following problem:

Is it true that for every $X\subset A\subset \mathbb{Z}$, where $A$ is finite and $X$ is non-empty, that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A|}?$$

Here the notation $A+B$ denotes the set $\{ a+b\ : a\in A, b\in B\}$. It follows from Rusza's triangle inequality that $$\frac{|A+X|}{|X|}\geq \frac{|A+A|}{|A-X|},$$ but since $|A-X|\geq |A|$, this isn't quite strong enough.

It is not hard to show that the inequality holds in either of the extremal cases where $A+A$ is minimal or maximal - that is when $|A+A|=|A|(|A|+1)/2$ or $|A+A|=2|A|-1$.

Is this statement true in general?

Rewriting the desired inequality as $$\frac{|A+X|}{|A+A|}\geq \frac{|X|}{|A|},$$ we are asking if adding $A$ to $X$ and looking at this as a subset of $A+A$ causes the proportion of elements to increase.

Edit: Numerical Calculations:

I did some numerical calculations where I let $A$ run through all possible subsets of $\{1,2,3,\dots,n\}$ and $X$ run through all proper subsets of $A$, and I calculated the ratio $$\frac{|A+X||A|}{|A+A||X|}.$$ The minimum of this ratio over all possible combinations of $A,X$ with $X\subsetneq A\subset\{1,2,3\dots,n\}$ appears in the following table:

$$\begin{array}{cc} \text{value of }n\ \ & \text{minimum}\\ 3 & 4/3\\ 4 & 6/5\\ 5 & 8/7\\ 6 & 10/9\\ 7 & 12/11\\ 8 & 14/13\\ 9 & 16/15\\ 10 & 18/17 \end{array}$$ Numerically the slightly stronger estimate $$\frac{|A+X|}{|A+A|}\geq\left(1+\frac{1}{2|X|+1}\right)\frac{|X|}{|A|}$$ seems to hold.

• If X is an A-basis (so that A+X=A+A), the inequality then holds for all subsets Y of A containing X. It strikes me that maximal subsets of minimal A-bases are a good case to analyze. I vote that the inequality does hold. – The Masked Avenger Mar 13 '14 at 4:12
• Have you tried to verify computationally your inequality for all pairs $(A,X)$ with, say, $A\subset[1,10]$? – Seva Mar 13 '14 at 7:50
• Have you counterexamples in additive groups other than $\mathbb Z$, in non-abelian groups (replacing $A+X$ and $A+A$ by $AX$ and $A^2$? – Roland Bacher Mar 13 '14 at 13:02
• @Seva I wrote a program which chooses $A$ as a random subset of $\{1,2,...,n\}$ and $X$ as a random subset of $A$, and for $1$ million trials with $n=100$, the inequality always holds. I'll write a program that checks all subsets of $\{1,\dots,10\}$ and all possibilities $X$ and test it. – Eric Naslund Mar 13 '14 at 15:48
• @Alvin, Seva: I checked all possible combinations $X\subsetneq A\subset \{1,2,3\dots, 10\}$ and the inequality always holds. I edit the question to this in. – Eric Naslund Mar 13 '14 at 19:07

## 3 Answers

The proposed inequality is not true. I do not claim originality for this example: all I have done is take Seva's observation that the inequality would imply an improvement $|3A|\leq K^2|A|$ given $|2A|\leq K|A|$, find a standard counterexample to this hypothetical improvement, and then simplify it a bit for the present situation.

I will work inside in $\mathbf{Z}^2$, but this makes no difference because one can always just look at the image in $\mathbf{Z}$ under $(x,y)\mapsto x + My$ for large $M$.

Let $X = [x]^2$ and $$A = X \cup \{(j,0): j\in [Kx]\}\cup\{(0,j): j\in [Kx]\}.$$ Then for $x$ large enough $|A+X|/|X|\approx 2K$ and $|A+A|/|A|\approx K^2$.

One can get something from Petridis's results though, namely that if $X\subset A$ and $|A+X|\leq K|X|$ then $|A+A|\leq K^2|A|$.

• Great! This is what I was thinking of, but couldn't recall where I saw a counterexample to $|3A|\le K^2|A|$. Is there any standard reference for this? – Seva Mar 14 '14 at 11:30
• @Seva There must be but I don't know it. I found the example on one of Ben Green's examples sheets from his additive combinatorics course in Cambridge, but I think even that is no longer on the web. Maybe there is something similar in Tao and Vu, but I haven't checked thoroughly. – Sean Eberhard Mar 14 '14 at 13:40
• For the record the counterexample to $|3A|\leq K^2|A|$ was actually the following: Work inside $\mathbf{Z}^3$ and let $X=[x]^3$ and $A=X\cup\{(j,0,0):j\in[Kx]\}\cup\cdots$. Now $|2A|\lesssim K|A|$ but $|3A|\gtrsim K^3|A|$. – Sean Eberhard Mar 14 '14 at 13:42
• I am not getting $|A+A|/|A|$ as anything near $K^2$ for the example, and suspect a typo. Can someone fix it or explain? (When the numerics make sense to me, I'll believe in it as a counterexample.) Gerhard "Likes Examples With Sensible Numerics" Paseman, 2014.03.14 – Gerhard Paseman Mar 14 '14 at 17:58
• @GerhardPaseman $A+A$ contains all $(i,j)$ with $1\leq i,j\leq Kx$, so certainly $|A+A|\geq K^2 x^2$. On the other hand $|A|\leq x^2 + 2Kx$. Now take $x$ large. – Sean Eberhard Mar 14 '14 at 21:10

In particular for $x = 5$, $K = 5$ and $M = 22$ in Sean Eberhard's example, the inequality is violated (assuming $[x]$ means $\lbrace 0,1,2,\ldots, x \rbrace$).

I get $X = \{0,1,2,3,4,5,22,23,24,25,26,27,44,45,46,47,48,49,66,67,68,69,70,71,88,89,90,91,92 ,93,110,111,112,113,114,115\}$

$A = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,44,45, 46,47,48,49,66,67,68,69,70,71,88,89,90,91,92,93,110,111,112,113,114,115,132,154,176,198,220,242,264,286,308,330,352,374,396,418,440,462,484,506,528, 550\}$

and $|X| = 36$, $|A| = 72$, $|A+X| = 307$, $|A+A| = 622$.

This is a very incomplete answer at this stage, but it establishes some connections worth recording.

A well-known lemma by Petridis says that if $A$ and $B$ are finite, non-empty subsets of an abelian group such that $|X+B|/|X|\ge|A+B|/|A|$ holds for every non-empty subset $X\subset A$, then for every finite set $C$ one has $|A+B+C||A|\le|A+B||A+C|$. Your inequality (if true) says that the assumption of Petridis' lemma always holds true in the situation where $B=A$ and the underlying group is the group of integers. As a result, $$|2A+C||A|\le|2A||A+C|$$ for any finite integer sets $A$ and $C$. Letting here $C=(n-2)A$ with integer $n\ge 3$, we conclude that if $|2A|=K|A|$, then $|nA|\le K^{n-1}|A|$. The "standard" estimate here is $K^n|A|$, and I doubt it can be improved to $K^{n-1}|A|$ - though, maybe, the integer case is special in this respect.