Return to Answer

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

Proof 7 Use the Alon-F"uredi theorem to show that for every polynomial $P$ of degree less than $n(q-1)$ there are at least two points where $P$ does not vanish.

Proof 8 Use the coefficient formula which says that if a polynomial $P \in \mathbb{F}[x_1, \dots, x_n]$ has degree at most $c_1 + \cdots + c_n$ for some positive integers $c_i$'s, then the coefficient of $\prod x_i^{c_i}$ in $P$ is equal to $$\sum_{(a_1, \dots, a_n) \in A_1 \times \cdots \times A_n} \frac{P(a_1, \dots, a_n)}{\varphi_1'(a_1)\cdots\varphi_n'(a_n)}$$ where $A_i$ is an arbitrary finite subset of $\mathbb{F}$ of cardinality $c_i$ and $\varphi_i(x_i) = \prod_{\alpha \in A_i}(x_i - \alpha)$.

(I'll keep adding more proofs as I discover them)

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

Proof 7 Use the Alon-F"uredi theorem to show that for every polynomial $P$ of degree less than $n(q-1)$ there are at least two points where $P$ does not vanish.

Proof 8 Use the coefficient formula which says that if a polynomial $P \in \mathbb{F}[x_1, \dots, x_n]$ has degree at most $c_1 + \cdots + c_n$ for some positive integers $c_i$'s, then the coefficient of $\prod x_i^{c_i}$ in $P$ is equal to $$\sum_{(a_1, \dots, a_n) \in A_1 \times \cdots \times A_n} \frac{P(a_1, \dots, a_n)}{\varphi_1'(a_1)\cdots\varphi_n'(a_n)}$$ where $A_i$ is an arbitrary finite subset of $\mathbb{F}$ of cardinality $c_i + 1$ and $\varphi_i(x_i) = \prod_{\alpha \in A_i}(x_i - \alpha)$.

(I'll keep adding more proofs as I discover them)

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

(I'll keep adding more proofs as I discover them)

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

Proof 7 Use the Alon-F"uredi theorem to show that for every polynomial $P$ of degree less than $n(q-1)$ there are at least two points where $P$ does not vanish.

Proof 8 Use the coefficient formula which says that if a polynomial $P \in \mathbb{F}[x_1, \dots, x_n]$ has degree at most $c_1 + \cdots + c_n$ for some positive integers $c_i$'s, then the coefficient of $\prod x_i^{c_i}$ in $P$ is equal to $$\sum_{(a_1, \dots, a_n) \in A_1 \times \cdots \times A_n} \frac{P(a_1, \dots, a_n)}{\varphi_1'(a_1)\cdots\varphi_n'(a_n)}$$ where $A_i$ is an arbitrary finite subset of $\mathbb{F}$ of cardinality $c_i$ and $\varphi_i(x_i) = \prod_{\alpha \in A_i}(x_i - \alpha)$.

(I'll keep adding more proofs as I discover them)

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

(I'll keep adding more proofs as I discover them)

For Chevalley's theorem, i.e., number of common zeroes not being one, any new proof of the following Lemma would give a 'new' proof.

Lemma Let $P \in \mathbb{F}_q[x_1, \ldots, x_n]$ such that $P(a) \neq 0$ for some fixed $a = (a_1, \ldots, a_n) \in \mathbb{F}_q^n$ but $P(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. Then $\deg P \geq n(q-1)$.

For given $P_1, \ldots, P_r$ in $\mathbb{F}_q[x_1, \ldots, x_n]$ with $\sum \deg P_i < n$, the trick is to define $P = \prod (1 - P_i^{q-1})$ as mentioned in Peter Clark's answer. If the set of common zeroes is a singleton then we have a contradiction to the Lemma above, hence proving the Chevalley's theorem.

So, let's discuss some possible proofs of the Lemma. Define $Q := \prod_{i = 1}^n (1 - ( x_i - a_i)^{q-1})$ and let $P(a) = \lambda \neq 0$. Note that $\deg Q = n(q-1)$, $Q(a) = 1$ and $Q(x) = 0$ for all $x \in \mathbb{F}_q^n \setminus \{a\}$. We'll use $Q$ in Proof 1 and 2.

Proof 1. If $\deg P < n(q-1)$, then $\lambda Q - P$ is a non-zero polynomial of degree $n(q-1)$ that vanishes on the grid $\mathbb{F}_q^n$ but has a non-zero coefficient of the term $\prod x_i^{q-1}$, contradicting Alon's combinatorial nullstellensatz.

Proof 2. It can be shown that for every polynomial $P$ there exists a unique polynomial $\widehat P$ such that $P - \widehat P \in I = \langle x_1^q - x_1, \ldots, x_n^q - x_n \rangle$ ($I$ is the ideal of polynomials vanishing everywhere on $\mathbb{F}_q^n$) and $\deg_{x_i} \widehat P \leq q-1$ for all $i$. Moreover, $\deg P \geq \deg \widehat P$. Now, since $\widehat P - \lambda Q$ vanishes everywhere it must be the zero polynomial (degree in each variable is at most $q-1$). Therefore $\widehat P = \lambda Q$ and $\deg P \geq \deg \widehat P = \deg Q = n(q-1)$.

Proof 3. For each $r \in \mathbb{F} \setminus \{a_1\}$ the polynomial $\widehat P(r, x_2, \ldots, x_n)$ is the zero polynomial, and hence $x_1 - r$ divides $\widehat P$. This can be done for every $i$ and every $r \in \mathbb{F}_q \setminus \{a_i\}$. Therefore, $\deg P \geq \deg \widehat P \geq n(q-1)$.

Proof 4. There is a bijection between functions from $\mathbb{F}_q^n$ to $\mathbb{F}_q$ and polynomials with degree in each variable at most $q-1$. For any $b \in \mathbb{F}_q^n$ define the polynomial $P_b = \widehat P (x - (b-a))$. Since each $P_b$ vanishes everywhere except at $b$, by Lagrange interpolation, $P_b$'s span the whole space of polynomials/functions. In particular, the monomial $\prod x_i^{q-1}$ must be a linear combination of $P_b$'s. This means that the coefficient of $\prod x_i^{q-1}$ in $\widehat P$, which is the same as its coefficient in every $P_b$, must be non-zero.

Proof 5 Use Ax's lemma, i.e., if $\deg P < n(q-1)$ then $\sum_{x \in \mathbb{F}_q^n} P(x) = 0$. But we know that this sum is equal to $P(a) \neq 0$.

Proof 6 WLOG let $a = (0, \ldots, 0)$ and let $\alpha \in \mathbb{F}_q^\times$. Then by division over $\mathbb{F}_q[x_2, \ldots, x_n][x_1]$ we can write $P = (x_1 - \alpha)Q_\alpha + R_\alpha$. It is easy to see that $R_\alpha = P(\alpha, x_2, \ldots, x_n) \in \mathbb{F}_q[x_2, \ldots, x_n]$. By substituting $x_1 = \alpha$ in the equation above, we see that $R_\alpha(x) = 0$ for all $x \in \mathbb{F}_q^{n-1}$ and hence, $R_\alpha \in \langle x_2^q - x_2, \ldots, x_n^q - x_n \rangle \subseteq I$. Moreover, $\deg P \geq \deg R_\alpha$.

We can repeat this for the polynomial $Q_\alpha$, by picking some $\beta \neq \alpha$ in $\mathbb{F}_q^\times$. We could do this for every non-zero element in $\mathbb{F}_q^\times$ and every variable to finally get $$P = \left(\prod_i (x_i^{q-1} - 1)\right)Q + R$$ where $R \in I$, $\deg P \geq \deg R$ and $Q \neq 0$. Therefore, $\deg P \geq n(q-1)\deg Q \geq n(q-1)$.

(I'll keep adding more proofs as I discover them)