Polynomial-time computing over quadratic maps I: sampling in real algebraic sets

Original · EN

Given a quadratic map Q: Kⁿ -> Kᵏ defined over a computable subring D of a real closed field K, and a polynomial p(Y₁,...,Yₖ) of degree d, we consider the zero set Z=Z(p(Q(X)),Kⁿ) of the polynomial p(Q(X₁,...,Xₙ)). We present a procedure that computes, in (dn)ᵒ(k) arithmetic operations in D, a set S of (real univariate representations of) sampling points in Kⁿ that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the standard methods that all have exponential dependence on n in the complexity. In particular, our procedure is polynomial-time for constant k. In contrast, the best previously known procedure (due to A.Barvinok) is only capable of deciding in nᵒ(k²) operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=sumᵢ Yᵢ² and homogeneous Q. A by-product of our procedure is a bound (dn)ᵒ(k) on the number of connected components of Z. The procedure consists of exact symbolic computations in D and outputs vectors of algebraic numbers. It involves extending K by infinitesimals and subsequent limit computation by a novel procedure that utilizes knowledge of an explicit isomorphism between real algebraic sets.