Computing rational points in convex semi-algebraic sets and SOS decompositions

Abstract

Let $\mathcal{P}=\{h_1,...,h_s\}\subset \mathbb{Z}[Y_1,...,Y_k]$, $D\ge °(h_i)$ for $1\le i\le s$, $\sigma$ bounding the bit length of the coefficients of the $h_i$'s, and $\Phi$ be a quantifier-free $\mathcal{P}$-formula defining a convex semi-algebraic set. We design an algorithm returning a rational point in $\mathcal{S}$ if and only if ${\cal S}\cap \Q\neq\emptyset$. It requires $σ^{\bigO(1)}D^{\bigO(k^3)}$ bit operations. If a rational point is outputted its coordinates have bit length dominated by $σD^{\bigO(k^3)}$. Using this result, we obtain a procedure deciding if a polynomial $f\in \mathbb{Z}[X_1,>...,X_n]$ is a sum of squares of polynomials in $\Q[X_1, ..., X_n]$. Denote by $d$ the degree of $f$, $\tau$ the maximum bit length of the coefficients in $f$, $D=\left(\genfrac{}{}{0ex}{}{n+d}{n}\right)$ and $k\le D(D+1)-\left(\genfrac{}{}{0ex}{}{n+2d}{n}\right)$. This procedure requires $τ^{\bigO(1)}D^{\bigO(k^3)}$ bit operations and the coefficients of the outputted polynomials have bit length dominated by $τD^{\bigO(k^3)}$.