Skip to main content
1 of 2
Terry Tao
  • 114.1k
  • 33
  • 462
  • 539

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.

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.

and the analogous problem for 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.

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539