Testing polynomials

In computer algebra, it is often assumed, in dealing with sparse polynomials, that a polynomial which evaluates to zero is identically zero. The purpose of the paper is to set conditions for a polynomial to be zero. Let \(S\subseteq\mathbb{N}^n\) be a finite subset. Let \(\mathbb{K}\) be a field of characteristic zero. Denote by \(P_S\) the vector space of polynomials of type \(S\), i.e. polynomials of the form \(\sum_{\alpha \in S}a_{\alpha}X^{\alpha}\), with coefficients in \(\mathbb{K}\) and \(\alpha =X_1^{\alpha^ 1}\cdots X_n^{\alpha^n}\). A set of points \(T_S\subset {\mathbb{K}}^n\) is said to be a testing set for \(S\) if for any \(P\in P_S\): \(P\vert T_S=0\) implies \(P=0\). The authors prove the following theorem: Let \(S=\alpha_1,\dots,\alpha_k\) be a finite subset of \(\mathbb{N}^n\) and set \(T_i=(2^{\alpha_i^1},\dots,2^{\alpha_i^n})\in\mathbb{K}^n\) and \(T_S=T_1,\dots,T_k\subset \mathbb{K}^n\). Then \(T_S\) is a testing set for \(S\). Any testing set must contain at least \(k\) elements. In the case of real or complex polynomials in one variable, the theorem follows from Descartes' lemma: Let \(P\in \mathbb{R}[X]\) be a polynomial in one variable with \(k\) nonzero coefficients; then \(P\) has at most \(k-1\) strictly positive real roots.

Recommendations

Cites work

Additive Complexity and Zeros of Real Polynomials

Cited in

(12)

This page was built for publication: Testing polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q755792)