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!
$\begingroup$
$\endgroup$
11
-
2$\begingroup$ @user44191 iterative sumset: $(p-1)A := \{a_1+\dots+a_{p-1} : a_1,\dots,a_{p-1} \in A\}$. $\endgroup$– mathworker21Aug 21 at 21:15
-
4$\begingroup$ The condition $0\in A$ seems irrelevant: if the assertion is true for sets satisfying this condition, then it is true for all sets. Also, the bound $(p^n-1)/(p-1)+1$, if true, is best possible: consider the set $A$ of all $n$-tuples with the last nonzero coordinate equal to $1$. $\endgroup$– SevaAug 22 at 8:49
-
1$\begingroup$ @TerryTao, the $p=2$ case is trivial: a subset $A \subseteq G$ of size $|G|$ certainly satisfies $A = G$. $\endgroup$– Peter TaylorAug 22 at 11:53
-
2$\begingroup$ Fair point. I said I didn’t do the computation :-). But if there is a generalization of the main result of that paper to higher p then in principle this could resolve the question if the numbers work out. $\endgroup$– Terry TaoAug 22 at 11:55
-
2$\begingroup$ In addition to Peter Taylor's comment, let me add that the claim is also trivial for $p=3$, since in this case $|A| > |G|/2$ which implies $|A+A|=|G|$ (as $A \cap (g-A)$ cannot be empty for any given $g \in G$). As observed by Seva, this does not use $0 \in A$. $\endgroup$– Ofir GorodetskyAug 22 at 17:19
|
Show 6 more comments
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Aug 23 at 20:46
-
2$\begingroup$ Nice argument! Basically you are able to leverage the $n=1$ case to handle the general case. $\endgroup$ Aug 23 at 21:58
-
2$\begingroup$ Very nice. Essentially makes the assertion obvious by exploiting the fact that the line through two points of a set lies in its $(p-1)$-fold sumset. $\endgroup$– SevaAug 24 at 6:25
$\begingroup$
$\endgroup$
0
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.)
