Let $A$ be a set of vectors in $\mathbb Z^d$ who $\mathbb R$-span is the whole $\mathbb R^d$. Let $s_i(A)$ denote the size of $A+A+\dots A$ ($i$ times). I am interested in the following:

Question 1: Find sufficient conditions on $A$ so we have: $s_3(A)\geq (d+2)s_2(A) -\binom{d+2}{2}s_1(A)+\binom{d+2}{3} $?

For $d=1$ $A$ is just a bunch of integers. Then the inequality $s_3(A)\geq 3s_2(A)-3s_1(A)+1$ occurs if they form an arithmetic progression (in fact, equality happens). I did not find other examples, although admittedly I have not looked too hard (Seva pointed out in the comment that this hold for "generic" A). It is of course easy and classical that $s_2(A)\geq 2s_1(A)-1$.

A harder(?) question is:

Question 2: Find sufficient conditions on $A$ so we have: $s_3(A)\geq (d+1)s_2(A) -\binom{d+1}{2}s_1(A)+\binom{d+1}{3} $?

This inequality is weaker than the one in Question 1. For $d=1$ it reads $s_3(A)\geq 2s_2(A)-s_1(A)$. In fact, I do not know any sequence that fails this.

Any pointer to relevant, similar inequalities in the literature would be greatly appreciated.

  • $\begingroup$ Is there any difference between your $s_i(A)$ and the quantity commonly denoted by $|iA|$ (the size of the $i$-fold sumset $iA$)? $\endgroup$ – Seva Dec 8 '18 at 14:10
  • $\begingroup$ No, I am just not sure what is the standard notation. $\endgroup$ – Hailong Dao Dec 8 '18 at 14:11
  • $\begingroup$ I do not understand then. For a set $A$ in a general position, one has $|3A|\sim |A|^3/6$, while $|2A|=O(|A|^2)$. Therefore, your inequalities hold true for any "typical" set, not necessarily an arithmetic progression or anything else of this sort? $\endgroup$ – Seva Dec 8 '18 at 14:33
  • 1
    $\begingroup$ No, it does not. Take $A$ to be a subset of $[0,l]$ such that $2A=[0,2l]$. Then $|3A|+|A|\le 3l+|A|+1<4l+2=2|2A|$ provided $|A|<l+1$. $\endgroup$ – Seva Dec 8 '18 at 15:59
  • 1
    $\begingroup$ There are lots of papers dealing with sumset inequalities, many of them due to Imre Ruzsa, but your particular inequalities hold almost always. $\endgroup$ – Seva Dec 8 '18 at 16:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.