Erhard Aichinger, Simon Grünbacher, Paul Hametner,
"Zero testing and equation solving for sparse polynomials on rectangular domains"
, in Finite Fields and Their Applications, Vol. 95, 2024, ISSN: 1071-5797
Original Titel:
Zero testing and equation solving for sparse polynomials on rectangular domains
Sprache des Titels:
Englisch
Original Kurzfassung:
We consider sparse polynomials in $N$ variables over a finite field, and ask whether they vanish on a set $S^N$, where $S$ is a set of nonzero elements of the field. We see that if for a polynomial $f$, there is $\vb{c}\in S^N$ with $f (\vb{c}) \neq 0$, then there is such a $\vb{c}$ in every ball (with respect to the Hamming distance) inside $S^N$, where the radius of the ball is bounded by a multiple of the logarithm of the number of monomials that appear in $f$.
A similar result holds for the solutions of the equations $f_1 = \cdots = f_r = 0$ inside $S^N$. When $0 \not\in S$, this provides algorithms for testing whether a given polynomial $f$ vanishes on $S^N$ and for checking whether $f_1 = \cdots = f_r = 0$ has a solution in $S^N$ that are of time complexity in $O(n^{c \log(n)})$, where $c > 0$ and $n$ is the size of the input polynomials given in sparse representation.
Forschungs-