5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ What Is $[0:2]^n$? $\endgroup$
    – Seva
    Commented Aug 28, 2023 at 13:37
  • $\begingroup$ @Seva $[0:2]^n = \{ 0,1,2 \}^n$ $\endgroup$ Commented Aug 28, 2023 at 15:03

1 Answer 1

11
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ A small update: there is indeed work in progress that improves upon and generalizes some of the results mentioned here, but it is not yet ready to be made public. Stay tuned. $\endgroup$
    – Terry Tao
    Commented Sep 14, 2023 at 16:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .