4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ $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. $\endgroup$ – Jyrki Lahtonen Nov 6 '20 at 9:22
  • 1
    $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Nov 6 '20 at 9:33
  • $\begingroup$ @JyrkiLahtonen, thanks for this info! I appreciate your help $\endgroup$ – Mathew Nov 6 '20 at 22:34
3
+50
$\begingroup$

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 field 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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – It'sNotALie. Dec 30 '20 at 12:14
  • $\begingroup$ @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. $\endgroup$ – Alex Ravsky Jan 3 at 11:05
6
$\begingroup$

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)$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.