COMPUTING RATIONAL POINTS IN CONVEX SEMIALGEBRAIC SETS AND SUM OF SQUARES DECOMPOSITIONS

Let P = {h(1), ... , h(s)} subset of Z[Y-1, ... , Y-k], D >= deg(h(i)) for 1 <= i <= s, sigma bounding the bit length of the coefficients of the h(i)'s, and let Phi be a quantifier-free P-formula defining a convex semialgebraic set. We design an algorithm returning a rational point in S if and only if S boolean AND Q not equal empty set. It requires sigma(O)(1) D-O(k(3)) bit operations. If a rational point is outputted, its coordinates have bit length dominated by sigma D-O(k(3)). Using this result, we obtain a procedure for deciding whether a polynomial f is an element of 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 = ((n+d) (n)), and k <= D(D + 1) - ((n+2d) (n)). This procedure requires tau(O)(1) D-O(k(3)) bit operations, and the coefficients of the outputted polynomials have bit length dominated by tau D-O(k(3)).