A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density (Q2052162)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density |
scientific article |
Statements
A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density (English)
0 references
25 November 2021
0 references
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\).
0 references
degree of constructible and locally closed affine sets
0 references
Bézout's inequality
0 references
correct test sequences
0 references
probability
0 references
existence
0 references
equality test of lists of functions
0 references
bounded error probability
0 references
polynomial-time algorithms
0 references
0 references
0 references
0 references
0 references