# Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions

2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let ${\cal P}=\{h_1, \ldots, h_s\}\subset \Z[Y_1, \ldots, 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 $\Phi$ be a quantifier-free ${\cal P}$-formula defining a convex semi-algebraic set. We design an algorithm returning a rational point in ${\cal S}$ if and only if ${\cal S}\cap \Q\neq\emptyset$. It requires $\sigma^{\bigO(1)}D^{\bigO(k^3)}$ bit operations. If a rational point is outputted its coordinates have bit length dominated by $\sigma D^{\bigO(k^3)}$. Using this result, we obtain a procedure deciding if a polynomial $f\in \Z[X_1, \ldots, X_n]$ is a sum of squares of polynomials in $\Q[X_1, \ldots, X_n]$. Denote by $d$ the degree of $f$, $\tau$ the maximum bit length of the coefficients in $f$, $D={{n+d}\choose{n}}$ and $k\leq D(D+1)-{{n+2d}\choose{n}}$. This procedure requires $\tau^{\bigO(1)}D^{\bigO(k^3)}$ bit operations and the coefficients of the outputted polynomials have bit length dominated by $\tau D^{\bigO(k^3)}$.
Keywords :
Document type :
Journal articles
Domain :

Cited literature [21 references]

https://hal.inria.fr/inria-00419983
Contributor : Mohab Safey El Din <>
Submitted on : Thursday, October 15, 2009 - 7:22:30 PM
Last modification on : Friday, January 8, 2021 - 5:50:04 PM
Long-term archiving on: : Tuesday, June 15, 2010 - 10:16:19 PM

### Files

RR-7045.pdf
Files produced by the author(s)

### Citation

Mohab Safey El Din, Lihong Zhi. Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions. SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2010, 20 (6), pp.2876-2889. ⟨10.1137/090772459⟩. ⟨inria-00419983⟩

Record views