= Solution
Apply the <polynomial method in combinatorics> to the <finite-field Kakeya set> $A$. We will actually obtain the stronger estimate
$$
\boxed{|A|\geq\binom{p+n-1}{n}\geq\frac{p^n}{n!}.}
$$
Let $\mathcal P$ be the <vector space> over the <prime field> $\mathbb F_p$ of <multivariate polynomials> in $n$ variables of <total degree of a polynomial> at most $p-1$. By the <dimension of a bounded-total-degree polynomial space>, its <monomial> basis consists of $x_1^{a_1}\cdots x_n^{a_n}$ with $a_i\geq0$ and $\sum_i a_i\leq p-1$. Adding a slack exponent gives $n+1$ nonnegative exponents summing to $p-1$; the <stars and bars> count shows that
$$
\dim\mathcal P=\binom{p+n-1}{n}.
$$
If $|A|<\dim\mathcal P$, the evaluation <linear map> $\mathcal P\to\mathbb F_p^A$ has a nonzero element in its <kernel of a linear map>. Thus there is a nonzero <polynomial> $P$ of <total degree of a polynomial> $d\leq p-1$ vanishing at every point of $A$. Its degree cannot be zero, since $A$ contains a line and is nonempty. Write $P_d$ for its nonzero top <homogeneous polynomial> part.
For every nonzero $v\in\mathbb F_p^n$, the directional hypothesis supplies an <affine line in a vector space>
$$
\{a_v+tv:t\in\mathbb F_p\}\subseteq A.
$$
Directions are one-dimensional <vector subspaces>; rescaling a representative does not change this line. The univariate <polynomial> $P(a_v+tv)$ has degree at most $d<p$ and vanishes for all $p$ values of $t$. The <root bound for a polynomial> makes it the zero <polynomial>. Its coefficient of $t^d$ is exactly $P_d(v)$, so $P_d(v)=0$ for every nonzero $v$. Because $d>0$, $P_d(0)=0$ too.
To finish, we prove the relevant <polynomial nonvanishing below the field size>. A <polynomial> over $\mathbb F_p$ of degree at most $p-1$ in each variable cannot vanish on all of $\mathbb F_p^n$ unless it is zero. Induct on $n$. The one-variable case is the <root bound for a polynomial>. For more variables, write
$$
Q(x_1,\ldots,x_n)=\sum_{j=0}^{p-1}Q_j(x_1,\ldots,x_{n-1})x_n^j.
$$
Fixing the first $n-1$ coordinates gives a univariate <polynomial> with $p$ <roots of a polynomial>, so all its coefficients are zero. Hence every $Q_j$ vanishes on $\mathbb F_p^{n-1}$, and the induction hypothesis makes every $Q_j$ zero. Applying this to $P_d$, whose <total degree of a polynomial> is less than $p$, contradicts its choice as nonzero.
Therefore $|A|\geq\dim\mathcal P$. Finally,
$$
\binom{p+n-1}{n}=\frac{p(p+1)\cdots(p+n-1)}{n!}\geq\frac{p^n}{n!},
$$
which proves the requested lower bound. The crucial observation in the <finite-field Kakeya polynomial bound> is that complete lines force the highest <homogeneous polynomial> part to vanish in every direction.
Back to article page
