20
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ 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. $\endgroup$ – The Masked Avenger Mar 13 '14 at 4:12
  • 3
    $\begingroup$ Have you tried to verify computationally your inequality for all pairs $(A,X)$ with, say, $A\subset[1,10]$? $\endgroup$ – Seva Mar 13 '14 at 7:50
  • 1
    $\begingroup$ 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$? $\endgroup$ – Roland Bacher Mar 13 '14 at 13:02
  • 1
    $\begingroup$ @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. $\endgroup$ – Eric Naslund Mar 13 '14 at 15:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Eric Naslund Mar 13 '14 at 19:07
11
$\begingroup$

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|$.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ – Seva Mar 14 '14 at 11:30
  • $\begingroup$ @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. $\endgroup$ – Sean Eberhard Mar 14 '14 at 13:40
  • 2
    $\begingroup$ 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|$. $\endgroup$ – Sean Eberhard Mar 14 '14 at 13:42
  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Mar 14 '14 at 17:58
  • $\begingroup$ @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. $\endgroup$ – Sean Eberhard Mar 14 '14 at 21:10
7
$\begingroup$

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$.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.