Question
Let $q$ be a prime power, $k\in\{1,\ldots,q-1\}$ and $f$ be a multivariate polynomial in $\mathbb{F}_q[x_1,\ldots,x_n]$ having $q^n – k$ roots.
Show that $\deg(f) \geq (q-1)n – k + 1$.
(The inequality has been updated due to a comment of Jyrki Lahtonen. There has been the weaker inequality $\deg(f) \geq (q-1)n – k$ before.)
Motivation
For all $a\in\mathbb{F}_q$, we have $a^q = a$. This shows that we can replace $x_i^q$ in f by $x_i$ without changing the set of roots, so that we may assume that the degree in every single variables is at most $q-1$. The total degree $\deg(f)$ is then at most $(q-1)n$. It is not hard show that every function $\mathbb{F}_q^n \to \mathbb{F}_q$ can be represented by a unique polynomial with these properties (total degree at most $(q-1)m$; degree in every single variable at most $q-1$).
So the question asks for polynomials whose number of roots is close to the maximum $q^n$. The aim is to show that the degree has to be at least equally close to the maximum (in the above sense) total degree $(q-1)m$.
Best Answer
Let $V$ be the $\Bbb{F}_q$-span of monomials $\prod_{i=1}^nx_i^{m_i}$ with $0\le m_i\le q-1$ for all $i$. The dimension of the space $V$ is thus $q^n$ which is equal to the number of points in $S=\Bbb{F}_q^n$. By Lagrange interpolation any function $f:S\to\Bbb{F}_q$ can be described by evaluating a polynomial $\phi_f$. Without loss of generality (see the question) we can assume that $\phi_f\in V$. The conclusion is that $\phi_f\in V$ is uniquely determined by $f$. Therefore we can forget about the distinction between $f$ and $\phi_f$, when we restrict ourselves to $V$. However, we must be careful in that $V$ is not closed under multiplication. Rather, $V$ gives as set of representatives of all the cosets of the quotient ring $$ R_n=\Bbb{F}_q[x_1,x_2,\ldots,x_n]/\langle x_1^q-x_1,\ldots,x_n^q-x_n\rangle. $$
I think the following argument shows that whenever there are exactly $k>0$ points, $P_1,\ldots,P_k \in S$ such $f(P_i)\neq0$ for all $i=1,2,\dots,k$, then $$\deg f\ge (q-1)n-k+1.$$ That is, one higher than required.
We proceed and prove the claim by induction on $k$. The starting point $k=1$ is seen as follows. Let $P_1=(a_1,a_2,\ldots,a_n)$ be the unique point where $f$ does not vanish. The polynomial $$ f_{P_1}(x_1,\ldots,x_n):=\prod_{i=1}^n\frac{x_i^q-x_i}{x_i-a_i} $$ is one such, for the $i$th factor vanishes whenever $x_i\in \Bbb{F}_q, x_i\neq a_i$. Observe that $f_{P_1}$ is of degree $q-1$ in all the variables, so it has degree $(q-1)n$ and belongs to $V$. By the uniqueness result described above we thus have $f=\lambda f_{P_1}$ for some $\lambda\in\Bbb{F}_q^*$. This proves the base case $k=1$.
Assume that for some $k>1$ we have a polynomial $f\in V$ of degree $<(q-1)n-(k-1)$ that vanishes at all the points of $S$ except at $P_1,P_2,\ldots, P_k$. Consider the collection of maximal degree terms in $f$. Because $\deg f<n(q-1)$ there exists a monomial $\prod_i x_i^{m_i}$ of degree $\deg f$ with a non-zero coefficient in $f$ such that some exponent, say $m_{i_0}<q-1$. Let $P_k=(a_1,a_2,\ldots,a_n)$. Consider the polynomial $\tilde f:= (x_{i_0}-a_{i_0}) f$. It vanishes whenever $f$ vanishes, and also at the point $P_k$, so $\tilde{f}$ non-vanishes at at most $k-1$ points of $S$. By the induction hypothesis we have $$ \deg\tilde{f}\ge n(q-1)-((k-1)-1)=n(q-1)-(k-1)+1. $$ But, by the choice of $i_0$, we also have $\deg\tilde{f}=\deg f +1$. Therefore $$\deg f\ge n(q-1)-(k-1)$$ proving the inductive step.
I don't see the need for the assumption $k<q$. Of course, the lower bound on the degree becomes trivial rather quickly at around $k=n(q-1)$.