= Solution
Set $m=\lceil p/100\rceil$ and $d=m-1$, so that $d<p/100<p$. The <dimension of a bounded-total-degree polynomial space> in $n$ variables over $\mathbb F_p$ is $\binom{n+d}{n}$. If $\#N$ were smaller than this dimension, evaluation at the points of $N$ would impose fewer homogeneous linear conditions than unknown coefficients. The <rank-nullity theorem> would give a nonzero <multivariate polynomial> $P$ of <total degree> at most $d$, vanishing on $N$.
For every $x$, select one of the promised rich <affine lines in a vector space> through $x$, and write it as $\ell=\{a+tv:t\in\mathbb F_p\}$ with $v\ne0$. The <polynomial restriction to a line> $Q(t)=P(a+tv)$ has degree at most $d$, and at least $m=d+1$ distinct <roots of a polynomial> from $N\cap\ell$. By the <root bound for a polynomial>, \b[$Q$ is identically zero], so $P(x)=0$. Since this works for every $x$, $P$ vanishes at all $p^n$ points of $\mathbb F_p^n$.
The <Schwartz-Zippel lemma> says that a nonzero <multivariate polynomial> of <total degree> $d$ has at most $d p^{n-1}$ zeros on this grid. Here $d<p$, so that count is strictly less than $p^n$, a contradiction. The distinction between a formal <polynomial> and its function on a <finite field> is crucial: our degree bound is what rules out a nonzero <polynomial> vanishing everywhere.
We have proved the stronger quantitative <rich line covering bound over a finite field>
$$
\boxed{\#N\ge\binom{n+\lceil p/100\rceil-1}{n}
=\frac{(d+1)\cdots(d+n)}{n!}
\ge\frac{p^n}{100^n n!}.}
$$
Thus \b[$\#N\gtrsim_n p^n$], as required. The implied constant may depend on the fixed dimension $n$. The very large numerical lower bound on $p$ is more than this proof needs.
Back to article page
