A Sparse Version of Reznick’s Positivstellensatz

If f is a positive definite form, Reznick’s Positivstellensatz states that there exists k ∈ N such that ‖ x ‖ 2 2 k f is a sum of squares of polynomials. Assuming that f can be written as a sum of forms ∑ l = 1 p f l , where each f l depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property , we provide a sparse version of Reznick’s Positivstellensatz. Namely, there exists k ∈ N such that f = ∑ l = 1 p σ l / H l k , where σ l is a sum of squares of polynomials, H l is a uniform polynomial denominator, and both polynomials σ l , H l involve the same variables as f l for each l = 1 , … , p . In other words, the sparsity pattern of f is also reflected in this sparse version of Reznick’s certificate of positivity. We next use this result to also obtain positivity certificates for (i) polynomials nonnegative on the whole space and (ii) polynomials nonnegative on a (possibly noncompact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate from Putinar and Vasilescu.