# Are all multivariate functions on finite fields equivalent to a unique polynomial of smallest degree?

Consider a field field $$\mathbb{F}$$ and a function $$f:\mathbb{F}^n\rightarrow\mathbb{F}$$. Let $$P$$ be the set of all polynomials that agree with $$f$$ on all inputs, that is, $$P=\{p:\forall x\in\mathbb{F}^n,p(x)=f(x)\}$$. Because there always exists some n-variate polynomial $$p$$ such that $$p(x) = f(x)$$, we know that $$P\neq\emptyset$$. Therefore we can define a set $$L$$ consisting of all elements of $$P$$ with lowest degree, that is, $$L=\{p\in P:\forall q\in P,deg(p)≤deg(q)\}$$.

Must it be the case that $$|L|=1$$?

Here is my attempt at proving so:
Assume $$p,q$$ are different polynomials, both of lowest degree $$d$$. Their difference is a polynomial of degree $$d$$ or lower, and as a function, takes all elements of $$\mathbb{F}^n$$ to $$0$$. I'm not sure what to do next.

NOTE
If it is possible for there to be multiple polynomials of lowest degree, (equivalently, $$|L|>1$$), I would be interested in knowing for which finite fields and values of n this is the case.

• $L=1$, if you bound the degree to $\le q-1$ individually for all the variables. So $x^3y^3$ would have degree 3 in both $x$ and $y$ rather than have a total degree six. – Jyrki Lahtonen Nov 6 '20 at 9:22
• This is the oldest variant of the question I could find. Because I answered that one, it would be in bad taste to suggest that this is a duplicate because it is not clear cut - your focus is different. I simply want to improve the interlinking on the site. Upvotes to all :-) – Jyrki Lahtonen Nov 6 '20 at 9:33
• @JyrkiLahtonen, thanks for this info! I appreciate your help – Mathew Nov 6 '20 at 22:34

We assume that the field $$\Bbb F$$ is finite and $$|\Bbb F|=q$$. Litho’s example shows that it can happen that $$|L|>1$$.

On the other hand, we can achieve an uniqueness of polynomials of $$L$$, imposing a natural restriction on their degrees. Indeed, given $$f$$, by induction with respect to $$n$$ we can construct a multidimensional Lagrange interpolation polynomial for $$f$$, which has degree at most $$q-1$$ with respect to each variable (and so a total degree at most $$(q-1)n$$). It follows that the set $$L$$ is non-empty.

Since $$x^q=x$$ for each $$x\in\mathbb F$$, given any polynomial $$p\in L$$ represented as a sum of monomials, if we substitute, as orangeskid suggested, in each of the monomials a factor $$x_i^{n_i}$$ by $$x_i^{m_i}$$, where $$m_i\in \{1,2,\ldots, q-1\}$$, and $$n_i\equiv m_i \mod (q-1)$$, we obtain a reduced polynomial $$\bar p$$ which has degree at most $$q-1$$ with respect to each variable and $$\bar p(x)=p(x)$$ for each $$x\in \Bbb F^n$$.

For any polynomials $$p,r\in L$$, a polynomial $$\bar p-\bar r$$ has degree at most $$q-1$$ with respect to each variable. So it is zero by the following

Theorem (Combinatorial Nullstellensatz II). [A] Let $$\Bbb F$$ be a ﬁeld and $$f\in \Bbb F[x_1,\dots, x_n]$$. Suppose $$\deg f =\sum_{i=1}^n t_i$$ for some nonnegative integers $$t_i$$ and the coefficient of $$\prod_{i=1}^n x_i^{t_i}$$ is nonzero. If $$S_1,\dots, S_n\subset \Bbb F$$ such that $$|S_i| > t_i$$ then there exists $$s_1\in S_1,\dots, s_n\in S_n$$ such that $$f(s_1,\dots,s_n)\ne 0$$.

References

[A] N. Alon, Combinatorial Nullstellensatz, Combinatorics, Probability and Computing 8 (1999), 7–29.

See (3) in this answer for more references.

• I don't think you used the Nullstellensatz correctly (or I'm misunderstanding): it gives sets large enough $\Rightarrow$ nonzero; it does not give the opposite implication sets smaller than that $\Rightarrow$ zero. – It'sNotALie. Dec 30 '20 at 12:14
• @It'sNotALie. The Nullstellensatz can be used as follows. Suppose for a contradiction that a polynomial $g=\bar p-\bar r$ is non-zero. Let $\deg g=\sum_{i=1}^n t_i$ for some non-negative integers $t_i$ and the coefficient of $\prod_{i=1}^n x_i^{t_i}$ is non-zero. For each $i$ put $S_i=\Bbb F$. Then $|S_i|=q$. Since the polynomial $g$ has degree at most $q-1$ with respect to to each variable, we have $t_i\le q-1<q=|S_i|$ for each $i$. By the Nullstellensatz, there exists $s_1\in S_1,\dots, s_n\in S_n$ such that $g(s_1,\dots,s_n)\ne 0$, a contradiction. Sorry for the delay with the answer. – Alex Ravsky Jan 3 at 11:05

Take, for example $$\mathbb{F} = \mathbb{Z}/2\mathbb{Z}$$, $$n=2$$, and $$f(x, y) = xy$$. It is easy to check that no polynomial of degree $$\leq 1$$ agrees with this function on all inputs, i.e., the minimal degree is $$2$$. But $$xy + x(x-1)$$ is another polynomial of degree $$2$$ which agrees with the function on all inputs.

A similar example can be constructed whenever $$n\geq |\mathbb{F}|$$.

Edit: actually, $$n=2$$ seems to be enough for any finite field: take $$p(x,y) = \left(\prod\limits_{a\in\mathbb{F}\backslash \{0\}} (x-a)\right) y$$ and $$q(x,y) = p(x,y) + \prod\limits_{a\in\mathbb{F}} (x-a)$$.

If $$A_1$$, $$A_2$$, $$\ldots$$, $$A_n$$ are finite subsets of a field $$\mathbb{F}$$, then any function $$f\colon A_1\times \cdots \times A_n\to \mathbb{F}$$ is given by a unique polynomial $$p\in \mathbb{F}[x_1, \ldots, x_n]$$, with $$\deg_{x_i}p \le |A_i|-1$$. This is basically the Lagrange interpolation polynomial.

In the case of a finite field $$\mathbb{F}$$ of cardinality $$q$$, your unique minimal polynomial will have the degree in each variable $$\le q-1$$.

How to get the minimal polynomial from a polynomial? Note that we can substitute any $$x_i^q$$ with $$x$$. Thefore, we can substitute any $$x_i^n$$ $$n\ge q$$ with $$x_i^m$$, $$m\in \{1,2,\ldots, q-1\}$$, and $$n\equiv m \mod (q-1)$$. This should give the minimal polynomial, and also show the uniqueness.