## Franklin's Notes

### Congruent and equivalent polynomials

Given two polynomials $F,G$ with integer coefficients in $n$ variables $x_1,\cdots,x_n$, we say that $F$ and $G$ are congruent (modulo a prime $p$) if the coefficients of corresponding terms of $F,G$ are congruent mod $p$. In this case, we write If the polynomials $F,G$ "agree" for all choices of values $(c_1,\cdots,c_n)\in\mathbb Z_p^n$, so that $F(c_1,\cdots,c_n)$ and $G(c_1,\cdots,c_n)$ are always congruent modulo $p$, then we say that $F$ and $G$ are equivalent modulo $p$, and write $F\sim G$. Clearly $F\equiv G$ implies $F\sim G$, but the converse is not necessarily the case: consider $F(x_1)=x_1$ and $G(x_1)=x_1^p$, which are equivalent by Fermat's Little Theorem (corollary of Euler's Theorem ).

Notice that since $a^p\equiv a$ modulo $p$ for any $a\in\mathbb Z$, if any term of $F$ contains a power of $x_i$ greater than or equal to $x_i^{p}$, then this power can be decremented by $\varphi(p)=p-1$ without changing any of the values of $F$, thereby obtaining an equivalent polynomial. Since we can repeatedly decrease the powers of $x_i$ in each term of $F$ until they are all strictly less than $p$, we have that every polynomial $F$ is equivalent to at least one reduced polynomial, namely a polynomial $F^\ast(x_1,\cdots,x_n)$ in which all powers of each $x_i$ are less than $p$.

As a matter of fact, every polynomial $F$ is equivalent to exactly one reduced polynomial. We can prove this using a pigeonhole-style argument.

• Using polynomial interpolation (e.g. Lagrange interpolation), we can show that every function $f:\mathbb Z_p^n\to \mathbb Z_p$ is equivalent to some polynomial.

• There are $p^{p^n}$ total distinct functions $\mathbb Z_p^n\to \mathbb Z_p$.

• There are $p^n$ distinct reduced monomials of the form $x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$ (where each $k_i$ is less than $p$), since there are $p$ choices for each exponent $k_i$.

• This means that there are $p^{p^n}$ total reduced polynomials, since there are $p^n$ possible reduced monomial terms and $p$ choices of coefficient for each term.

• If there existed a polynomial $F$ which was congruent to two distinct reduced polynomials, then there would necessarily exist a function which is not equivalent to any reduced polynomial, since there are $p^{p^n}$ distinct functions and the same number of reduced polynomials.

• This is impossible, since every function is equivalent to a polynomial, and every polynomial can be reduced to some equivalent reduced polynomial. Hence, every polynomial (and every function) must be equivalent to exactly one reduced polynomial.

Hence, we have:

Proposition 1. Every polynomial $F\in \mathbb Z_p[x_1,\cdots,x_n]$, and furthermore every function $f:\mathbb Z_p^n\to\mathbb Z_p$ is equivalent to exactly one reduced polynomial in $Z_p[x_1,\cdots,x_n]$.

This can be used to prove some surprising results, such as:

Proposition 2. If $F$ is a polynomial of overall degree $<n$, then it cannot have exactly one root.

Proof. Suppose $F$ has exactly one root, namely at Then $F^{p-1}$ is a polynomial which takes on the value $0$ at that point only, and a value of $1$ everywhere else. Thus, $1-F^{p-1}$ takes on the value $0$ everywhere except at that point, and a value of $1$ at $(c_1,\cdots,c_n)$. Note that the polynomial $1-F^{p-1}$ has degree $d(p-1)<n(p-1)$. Now, there is another polynomial which takes the exact same values, namely and this polynomial is already a reduced polynomial, so $H^\ast = H$. Since $1-F^{p-1}$ and $H$ take the same values, we have that $(1-F^{p-1})^\ast=H^\ast=H$. But $H$ has degree $n(p-1)$ and $(1-F^{p-1})^\ast$ less than or equal to $d(p-1)$, which is impossible! $\blacksquare$

Question: How much of the above can be generalized to finite fields $\mathbb F_{p^k}$ as opposed to just $\mathbb F_p$?