Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A sparse version of Reznick's Positivstellensatz

Abstract : If $f$ is a positive definite form, Reznick's Positivstellensatz [Mathematische Zeitschrift. 220 (1995), pp. 75--97] states that there exists $k\in\mathbf{N}$ such that ${\| x \|^{2k}_2}f$ is a sum of squares of polynomials. Assuming that $f$ can be written as a sum of forms $\sum_{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 {\em running intersection property}, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists $k \in \mathbf{N}$ such that $f=\sum_{l = 1}^p {{\sigma_l}/{H_l^{k}}}$, where $\sigma_l$ is a sum of squares of polynomials, $H_l$ is a uniform polynomial denominator, and both polynomials $\sigma_l,H_l$ involve the same variables as $f_l$, for each $l=1,\dots,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 non-compact) basic semialgebraic set, assuming that the input data satisfy the running intersection property. Both are sparse versions of a positivity certificate due to Putinar and Vasilescu.
Complete list of metadata
Contributor : Victor Magron <>
Submitted on : Thursday, February 13, 2020 - 12:11:50 PM
Last modification on : Thursday, June 10, 2021 - 3:07:13 AM

Links full text


  • HAL Id : hal-02477339, version 1
  • ARXIV : 2002.05101


N. H. A. Mai, Victor Magron, Jean-Bernard Lasserre. A sparse version of Reznick's Positivstellensatz. 2020. ⟨hal-02477339⟩



Record views