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

Given a quadratic map \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Q:\mathbb{K}^n \to \mathbb{K}^k $$\end{document} defined over a computable subring D of a real closed field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb{K},$$\end{document} and p ∈D[Y1,...,Yk] of degree d, we consider the zero set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$Z = Z(p(Q(X)), \mathbb{K}^n) \subseteq \mathbb{K}^n$$\end{document} of p(Q(X1,...,Xn)) ∈D[X1,...,Xn]. We present a procedure that computes, in (dn)O(k) arithmetic operations in D, a set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal{S}$$\end{document} of (real univariate representations of) sampling points in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb{K}^n$$\end{document} that intersects nontrivially each connected component of Z. As soon as k=o(n), this is faster than the known 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 is only capable of deciding in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n^{O(k^2 )} $$\end{document} operations the nonemptiness (rather than constructing sampling points) of the set Z in the case of p(Y)=∑iYi2 and homogeneous Q.