  In (Davis and Papp, 2022), the authors introduced the concept of dual
certificates of (weighted) sum-of-squares polynomials, which are vectors from
the dual cone of weighted sums of squares (WSOS) polynomials that can be
interpreted as nonnegativity certificates. This initial theoretical work showed
that for every polynomial in the interior of a WSOS cone, there exists a
rational dual certificate proving that the polynomial is WSOS. In this article,
we analyze the complexity of rational dual certificates of WSOS polynomials by
bounding the bit sizes of integer dual certificates as a function of parameters
such as the degree and the number of variables of the polynomials, or their
distance from the boundary of the cone. After providing a general bound, we
explore several special cases, such as univariate polynomials nonnegative over
the real line or a bounded interval, represented in different commonly used
bases. We also provide an algorithm which runs in rational arithmetic and
computes a rational certificate with boundable bit size for a WSOS lower bound
of the input polynomial.
