Estimate of Minkowski sum

Question

Let A $\subset [0:2]^n$, where $[0:2]=\{0,1,2\}$, then define $2A= \{ a+b\mid a,b \in A \}$. I wanted to know the best known lower-bound estimates for $|2A|$.

I intuitively expect that $|2A| \geq |A|^{\log_3{5}}$ as this estimate works for $n=1$ and if we take $A= [0:2]^n$, then $|2A| = [0:4]^n$ and the bound fits. For $A \subset [0:d]^n$, I expect $|2A| \geq |A|^{\log_{d+1}{(2d+1)}}$. Are there any known results for such settings?

Answer 1

This is only a partial answer to your question; I believe there is more current work, and have forwarded your question to someone working in this area to see if they have more recent results.

In Theorem 5 of

Bourgain, Jean; Dilworth, Stephen; Ford, Kevin; Konyagin, Sergei; Kutzarova, Denka, Explicit constructions of RIP matrices and related problems, Duke Math. J. 159, No. 1, 145-185 (2011). ZBL1236.94027.

it is shown (in your notation) that $|2A| \geq |A|^{2\tau}$ for $A \subset [0:d]^n$, where $\tau$ solves the equation $$ (\frac{1}{d+1})^{2\tau} + (\frac{d}{d+1})^\tau = 1.$$ They do not believe this result to be sharp, and (as you do) conjecture that $|2A| \geq |A|^{\log_{d+1}(2d+1)}$ instead. This is known for $d=1$, see

Woodall, D. R., A theorem on cubes, Mathematika, London 24, 60-62 (1977). ZBL0349.05010.

From the method of compressions one may assume without loss of generality that $A$ is a downset. If one then restricts $2A$ to the set $[0:d]^n$ then a sharp answer to your question was worked out in

Bollobás, Béla; Leader, Imre, Sums in the grid, Discrete Math. 162, No. 1-3, 31-48 (1996). ZBL0872.11007.

however I do not see an easy way to pass from this restricted sumset problem to the full sumset problem. Nevertheless, the method of compressions may be a promising technique to attack the problem.

There are related results in

Matolcsi, Dávid; Ruzsa, Imre Z.; Shakan, George; Zhelezov, Dmitrii, An analytic approach to cardinalities of sumsets, Combinatorica 42, No. 2, 203-236 (2022). ZBL1513.11022.

which generalize a related inequality $|2A + \{0,1\}^n| \geq 2^n |A|$ that I worked out with Ben Green in

Green, Ben; Tao, Terence, Compressions, convex geometry and the Freiman-Bilu theorem, Q. J. Math. 57, No. 4, 495-504 (2006). ZBL1160.11003.

and the analogous problem for various additive energies was studied in this recent paper of de Dios, Greenfeld, Ivanisvili, and Madrid, which would give some lower bounds on $|2A|$, but probably not the optimal ones.