Skip to main content
clarification
Source Link
Tobias Fritz
  • 6.4k
  • 2
  • 27
  • 52

The answer is yes.

Recall first that the sums-of-squares polynomials of degree at most $D$ and in $n$ variables form a spectrahedron, and in particular a semialgebraic set.

Now if $f \in P_{d,n}$ is a positive¹ polynomial, then by Hilbert's 17th problem and Artin's solution there are sums-of-squares polynomials $g$ and $h$ such that $f = \frac{g}{h}$. It is possible to bound the relevant degrees of $g$ and $h$ in terms of $n$ and $d$. (I'm not sure what the best currently known degree bounds are, but the linked 2014 paper gives a tower of five exponentials!)

Thus the $f \in P_{d,n}$ are characterized in terms of the equations $hf = g$ and $h \neq 0$ for sums-of-squares polynomials $g$ and $h$ with a given number of unknown coefficients. Hence $P_{d,n}$ is the projection of a semialgebraic set, and by Tarski's theorem therefore semialgebraic itself.

¹ "Positive polynomial" is the standard term for nowhere nonnegativenegative polynomial.

The answer is yes.

Recall first that the sums-of-squares polynomials of degree at most $D$ and in $n$ variables form a spectrahedron, and in particular a semialgebraic set.

Now if $f \in P_{d,n}$ is a positive¹ polynomial, then by Hilbert's 17th problem and Artin's solution there are sums-of-squares polynomials $g$ and $h$ such that $f = \frac{g}{h}$. It is possible to bound the relevant degrees of $g$ and $h$ in terms of $n$ and $d$. (I'm not sure what the best known degree bounds are, but the linked 2014 paper gives a tower of five exponentials!)

Thus the $f \in P_{d,n}$ are characterized in terms of the equations $hf = g$ and $h \neq 0$ for sums-of-squares polynomials $g$ and $h$ with a given number of unknown coefficients. Hence $P_{d,n}$ is the projection of a semialgebraic set, and by Tarski's theorem therefore semialgebraic itself.

¹ "Positive polynomial" is the standard term for nowhere nonnegative polynomial.

The answer is yes.

Recall first that the sums-of-squares polynomials of degree at most $D$ and in $n$ variables form a spectrahedron, and in particular a semialgebraic set.

Now if $f \in P_{d,n}$ is a positive¹ polynomial, then by Hilbert's 17th problem and Artin's solution there are sums-of-squares polynomials $g$ and $h$ such that $f = \frac{g}{h}$. It is possible to bound the relevant degrees of $g$ and $h$ in terms of $n$ and $d$. (I'm not sure what the best currently known degree bounds are, but the linked 2014 paper gives a tower of five exponentials!)

Thus the $f \in P_{d,n}$ are characterized in terms of the equations $hf = g$ and $h \neq 0$ for sums-of-squares polynomials $g$ and $h$ with a given number of unknown coefficients. Hence $P_{d,n}$ is the projection of a semialgebraic set, and by Tarski's theorem therefore semialgebraic itself.

¹ "Positive polynomial" is the standard term for nowhere negative polynomial.

Source Link
Tobias Fritz
  • 6.4k
  • 2
  • 27
  • 52

The answer is yes.

Recall first that the sums-of-squares polynomials of degree at most $D$ and in $n$ variables form a spectrahedron, and in particular a semialgebraic set.

Now if $f \in P_{d,n}$ is a positive¹ polynomial, then by Hilbert's 17th problem and Artin's solution there are sums-of-squares polynomials $g$ and $h$ such that $f = \frac{g}{h}$. It is possible to bound the relevant degrees of $g$ and $h$ in terms of $n$ and $d$. (I'm not sure what the best known degree bounds are, but the linked 2014 paper gives a tower of five exponentials!)

Thus the $f \in P_{d,n}$ are characterized in terms of the equations $hf = g$ and $h \neq 0$ for sums-of-squares polynomials $g$ and $h$ with a given number of unknown coefficients. Hence $P_{d,n}$ is the projection of a semialgebraic set, and by Tarski's theorem therefore semialgebraic itself.

¹ "Positive polynomial" is the standard term for nowhere nonnegative polynomial.