A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density

DOI10.1016/J.JCO.2021.101588MaRDI QIDQ2052162zbMATH OpenOpenAlexFDO

Authors Daniel Sebastian, Luis Miguel Pardo

Publication date 25 November 2021

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.15296

bounded error probability Bézout's inequality correct test sequences degree of constructible and locally closed affine sets equality test of lists of functions existence polynomial-time algorithms probability

Mathematics Subject Classification ID

Polynomials in general fields (irreducibility, etc.) (12E05) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Solving polynomial systems; resultants (13P15) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30) Analysis of algorithms (68W40)

Abstract: In Heintz-Schnorr (1982), the authors introduced the notion of correct test sequence and since then it has been widely used to design probabilistic algorithms for Polynomial Equality Test. The aim of this manuscript is to study the foundations and generalizations of this notion. We show that correct test sequences are almost omnipresent and appear in many different forms in the mathematical literature: As identity sequences for Function Identity Test, as norming sets in the field of Banach algebras or as samples in the context of Reproducing Kernel Hilbert Spaces. As main outcome, we generalize the main statement of Heintz-Schnorr (1982) proving that short correct test sequences for constructible sets of lists of polynomials do exist and are densely distributed in any constructible set of accurate dimension and degree. The main tool used to prove this result is the theory of degree of constructible sets, which we introduce and develop in this manuscript, generalizing the results of Heintz (1983) and proving two Bezout's Inequalities for two different notions of degree. We present a

algorithm to exhibit the power of correct test sequences, this algorithm decides whether a list of polynomials is a secant sequence by just evaluating the input list at some well-suited points. We show the differences between correct test sequences and Demillo-Lipton-Schwartz-Zippel probabilistic tests and we reformulate, prove and generalize two well-known results of the Polynomial Method: We prove Dvir's exponential lower bounds for Kakeya sets from lower bounds for the length of correct test sequences and generalize Alon's Combinatorial Nullstellensatz.

Review text

Let \(\kappa\) be a field and \(K\) its algebraic closure. For every positive integer \(m\in \mathbb{N}\), let \(A^m(\kappa)\) be the \(m\)-dimensional affine space over \(\kappa\). A subset \(C \subset A^m(K)\) is called constructible if it is equal to the image of an algebraic variety under the projection map from \(A^M(K)\) to \( A^m(K)\) with \(M \ge m\). In the literature, the degree of a constructible set \(C\) is defined to be the degree of its Zariski closure; however, as is shown in this paper, Bézout's inequality does not hold for this definition. In the first part of the paper, the authors present two different notions of degree for a constructible set and prove that they satisfy a Bézout inequality. Furthermore, the authors study several properties of the new notions. The second part of the paper is devoted to correct test sequences. Let \(X\) be a set, \(K\) a field and \(m\in \mathbb{N}\) a positive integer. Let \(\Omega\) be a set whose elements are sequences of length \(m\) of functions from \(X\) to \(K\). Let \(\Sigma \subset \Omega\). A correct test sequence of length \(L\) for \(\Omega\) with discriminant \(\Sigma\) is a finite set of \(L\) elements \(\{x_1, \ldots , x_L \} \subseteq X\) such that for each \(f\in \Omega\), if \(f(x_1)=\cdots=f(x_L)=(0,\ldots ,0)\) then \(f\in \Sigma\). Correct test sequences were introduced by Heintz and Schnorr in 1982 and they appeared in different places in mathematics. In this paper, by using the results of the first part, the authors prove that correct test sequences for lists of polynomials are densely distributed in any constructible set of accurate co-dimension and degree. Finally, they apply correct test sequences of asymptotically optimal length to describe a randomized algorithm to decide whether a list of polynomials forms a ``suite sécante: a sequence of polynomials \(f_1,\ldots,f_m\) in terms of \(n\) variables is called suite sécante if the associated variety has dimension \(n-m\).

Recommendations

Cites work

Cited in

(5)

This page was built for publication: A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density

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