Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions
Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions
Let $\mathcal{P}=\{h_1,\dots,h_s\}\subset\mathbb{Z}[Y_1,\dots,Y_k]$, $D\geq\deg(h_i)$ for $1\leq i\leq s$, $\sigma$ bounding the bit length of the coefficients of the $h_i$'s, and let $\Phi$ be a quantifier-free $\mathcal{P}$-formula defining a convex semialgebraic set. We design an algorithm returning a rational point in $\mathcal{S}$ if and only if $\mathcal{S}\cap\mathbb{Q}\neq\emptyset$. It requires $\sigma^{\mathrm{O}(1)}D^{\mathrm{O}(k^3)}$ bit operations. …