3
$\begingroup$

This question came about because multiplying polynomials in Magma is slow. Hence if I want to check that a matrix with linear coefficients in a (multivariate) polynomial ring cubes to zero, I just need to evaluate the matrix on enough points, cube that matrix (fast), then check if it is zero.

It is easy to see that if $f(x)$ is a polynomial with coefficients in a field $k$ and degree at most $d$, then I can test if $f$ is zero by choosing any distinct $d+1$ points. (Perhaps I need to extend the field to do this.)

If $f(x_1,\dots,x_n)$ is a multivariate polynomial, then something similar applies. If $f$ has degree at most $d$, then I can choose $N$ co-ordinates, where $N$ is the number monomials in the $n$ variables, of degree at most $d$, test if $f$ is zero on each of these co-ordinates, and if it is, then $f=0$.

I cannot take all sets of $N$ points though, they have to be 'linearly independent', in the following sense. Order the set of $N$ monomials, then for each co-ordinate write the values of the monomials into a length $N$ vector. You must only choose $N$ co-ordinates whose corresponding vectors are linearly independent.

But I am wondering something. In the univariate case the variety of zeroes is a bunch of points, and you cannot do better. In general, the zero variety has more structure. Is there some sneaky algorithm that can check that the variety is the whole of $k^n$ in fewer than $N$ checks? Even asymptotically would be good.

$\endgroup$

1 Answer 1

Reset to default
2
+50
$\begingroup$

Theorem (Combinatorial Nullstellensatz II). [A] Let $F$ be a field and $f\in 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 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$
4
  • 1
    $\begingroup$ I just tested this with the case $n=2$, $\deg f=6$, and I get $28$ values needed by my method and 28 values needed using this method. The rectangles can overlap, but I couldn't drop it by 1. Do you know if the CN will actually reduce the number of values needed? $\endgroup$
    – David A. Craven
    Jul 29, 2020 at 12:43
  • $\begingroup$ @DavidA.Craven Oops, I see now that we cannot reduce the number of values. Indeed, given $n$ and $d$, let $L$ be the set of all multivariate polynomials of a (total) degree at most $d$. Then $L$ is a linear space with a basis consisting of monomials of $n$ variables of degree at most $d$. Thus $L$ has dimension $N$. $\endgroup$
    – Alex Ravsky
    Jul 30, 2020 at 10:06
  • $\begingroup$ For each point $x=(x_1,\dots,x_n)$, an evaluation $E_x$ map $f\mapsto f(x)$ is a linear map from $L$ to $\Bbb R$. Suppose that we have points $x^1,\dots, x^{N’}$ such that if $f\in L$ and $f(x^j)=0$ for each $j$ then $f\equiv 0$. That is linear map $L\to\Bbb R^{N’}$, $f\mapsto (E_{x^1},\dots, E_{x^{N’}})$ is injective. But then $N’\ge N$. $\endgroup$
    – Alex Ravsky
    Jul 30, 2020 at 10:06
  • 1
    $\begingroup$ OK, well that is what I thought might be the situation. I'm glad I learned something new. I never saw the CN before, just the standard one. $\endgroup$
    – David A. Craven
    Jul 30, 2020 at 10:12

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.