The Finite Field Nikodym problem

Lemma

Suppose that $P\in {\text{Poly}}_{q-1}({\mathbb{F}}_q^n)$. If $P$ vanishes at every point of ${\mathbb{F}}_q^n$, then $P$ is the zero polynomial.

Proof The proof uses the vanishing lemma and induction on $n$. If $n=1$, then the result follows directly from the vanishing lemma. $P$ vanishes at $q>\text{Deg }P$ points of ${\mathbb{F}}_q$, and so $P$ is the zero polynomial. Now we proceed by induction. We let $x_1,\dots ,x_n$ be coordinates on ${\mathbb{F}}_q^n$, and we write $P$ in the form $P(x_1,\dots ,x_n)={\sum }_{j=0}^{q-1}{P}_j(x_1,\dots ,x_{n-1})x_n^j.$ In this formula, $P_j$ are polynomials in $x_1,\dots ,x_{n-1}$ of degree $\le q-1$. Fix the values of $x_1,\dots ,x_{n-1}$, and let $x_n$ vary. We have a polynomial in $x_n$, of degree $\le q-1$, that vanishes for all $x_n\in {\mathbb{F}}_q$. By vanishing lemma, this polynomial must be the zero polynomial. In other words, $P_j(x_1,\dots ,x_{n-1})=0$ for all $j$ and all $(x_1,\dots ,x_{n-1})\in {\mathbb{F}}_q^{n-1}$. But now, by induction on $n$, each polynomial $P_j$ is the zero polynomial. Then $P$ is the zero polynomial as well. $\square$

Nikodym Set

Let ${\mathbb{F}}_q$ be a finite field with $q$ elements. A set $N\subset {\mathbb{F}}_q^n$ is called a Nikodym set if, for each point $x\in {\mathbb{F}}_q^n$, there is a line $L(x)$ containing $x$ so that $L(x)\setminus \{x\}\subset N$.

A trivial example of a Nikodym set is the entire set ${\mathbb{F}}_q^n$.

The Finite-Field Nikodym Problem

Any Nikodym set $N\subset {\mathbb{F}}_q^n$ contains at least $c_n{q}^n$ elements. We can take $c_n=(10n{)}^{-n}$.

Proof We do a proof by contradiction. Let us assume that $N$ is a Nikodym set with $|N|<(10n{)}^{-n}{q}^n$. By the parameter counting argument, we can find a non-zero polynomial $P$ that vanishes on $N$ with degree bounded by $\text{Deg }P\le 2n|N{|}^{1/n}\le (1/5)q<q-1.$ Next we claim that $P$ vanishes at every point of ${\mathbb{F}}_q^n$. Let $x$ be an arbitrary point of ${\mathbb{F}}_q^n$. By the definition of a Nikodym set, there is a line $L(x)$ containing $x$ so that $L(x)\setminus \{x\}\subset N$. The polynomial $P$ vanishes on $N$, so $P$ vanishes at $\ge q-1$ points of $L(x)$. Since $\text{Deg }P<q-1$, the vanishing lemma implies that $P$ vanishes on the whole line $L(x)$. In particular, $P$ vanishes at $x$. We know that $P$ is a non-zero polynomial and that $P$ vanishes at every point of ${\mathbb{F}}_q^n$. We now get a contradiction from previous lemma.