Mapping Real Algebraic Sets: A Polynomial-Time Procedure for Sampling

Title: Mapping Real Algebraic Sets: A Polynomial-Time Procedure for Sampling

Abstract: This research article presents a polynomial-time procedure for sampling real algebraic sets. The procedure is applicable to quadratic maps and is particularly useful when the number of variables (n) is less than the order of the polynomials (k). The algorithm involves exact symbolic computations in D and outputs vectors of algebraic numbers. It extends the real field by infinitesimals and performs necessary geometric transformations. The main result is a set S of sampling points that intersects nontrivially each connected component of the real algebraic set Z. The procedure is faster than previous methods and provides a bound on the number of connected components.

Research Question: How can we develop a polynomial-time procedure for sampling real algebraic sets, particularly for quadratic maps, when the number of variables is less than the order of the polynomials?

Methodology: The methodology involves symbolic computation, where all data is represented exactly, using real univariate representations. The algorithm extends the real field by infinitesimals and performs necessary geometric transformations. It operates over an arbitrary real closed field K, with the input data lying in D[X1, . . ., X n] = D[X].

Results: The results include a set S of sampling points that intersects nontrivially each connected component of the real algebraic set Z = Z(p(Q(X)), K n). The procedure is faster than previous methods and provides a bound on the number of connected components.

Implications: The implications of this research are significant for real algebraic geometry and algorithmic problems. The procedure offers a faster method for finding points in real algebraic sets, particularly for quadratic maps when the number of variables is less than the order of the polynomials. This can be particularly useful in applications where such sets are needed. Additionally, the method provides a bound on the number of connected components, which is a useful result in its own right.

Link to Article: https://arxiv.org/abs/0403008v2 Authors: arXiv ID: 0403008v2