Subsets of $(\mathbb{Z}/p)^{\times n}$

Question

There seems to be some combinatorial fact that every subset $A$ of $G=(\mathbb{Z}/p)^{\times n}$ of cardinality $\frac{p^n-1}{p-1}+1$ containing $\vec{0}$ satisfies $(p-1)A=G$. ($p$ is a prime number.) Is that true and known in the literature? I would appreciate a reference or a proof. Thanks!

Answer 1

There is an alternative elementary way to prove this and see where the number $\frac{p^n-1}{p-1}+1$ comes from.

Lemma: If $|A|\geq \frac{p^n-1}{p-1}+1$ then every point in $\mathbb F_p^n$ lies in a line that passes from two distinct points in $A$.

Proof: If this was false then there would be a point $P\notin A$ such that every line through $P$ contains at most one point of $A$. However the number of distinct lines passing through $P$ is $\frac{p^n-1}{p-1}$, the size of the corresponding projective space. This gives a contradiction, since it implies $|A|\le \frac{p^n-1}{p-1}$.

Returning to the statement in the OP, starting with an arbitrary point $P\in \mathbb F_p^n$ the lemma tells us that there are points $M,N\in A$ such that $-P$ lies in the line passing through $M$ and $N$. Now consider the line consisting of the points $kM+(p-1-k)N$, for $0\le k\le p-1$. This line contains $(p-1)M$ and $(p-1)N$, therefore it also contains $(p-1)(-P)=P$. This means that $P=kM+(p-1-k)N$ for some $k$, which is in $(p-1)A$, as desired.

Answer 2

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. (Indeed, I was led to the downset/compression literature by recognizing Seva's example as a downset.) 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.)