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$ Commented Nov 6, 2020 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$ Commented Nov 6, 2020 at 9:33
  • $\begingroup$ @JyrkiLahtonen, thanks for this info! I appreciate your help $\endgroup$
    – Mathew
    Commented Nov 6, 2020 at 22:34

3 Answers 3

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$
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$ Commented Dec 30, 2020 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$ Commented Jan 3, 2021 at 11:05
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .