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

From Theorem 10 of

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

we know that if $A_1,\dots,A_k$ are subsets of $({\bf Z}/p)^{\times n}$ then $$ |A_1+\dots+A_k| \geq |I_1+\dots+I_k|$$ where $I_j$ is the initial segment of $({\bf Z}/p)^{\times n}$ of the same cardinality as $A_j$. (Strictly speaking, Theorem 10 only claims the $k=2$ case of this inequality, but the general case follows immediately by induction, together with the observation that the sum of two initial segments is again an initial segment; see also Corollary 7.) In particular, in the current context one has $$ |(p-1)A| \geq |(p-1)I|$$ where $I$ is the initial segment of length $\frac{p^n-1}{p-1}+1$. This is the set of length $n$ strings base $p$ whose first non-zero coordinate is $1$, together with the string $(0,\dots,0)$ - basically the set already identified by Seva's comment. It is then a routine matter to check that $(p-1)I = ({\bf Z}/p)^{\times n}$, giving the claim. (Indeed, for $1 \leq j \leq p-1$, one can check by induction that $jI$ consists of the length $n$ string whose first non-zero coordinate is at most $j$, plus the all-zero string.)

Terry Tao
  • 114.1k
  • 33
  • 462
  • 539