Suppose we have a (finite) system of polynomials $P = \{ p_i \} \subseteq \mathbb{R}[x_1, \ldots, x_n]$. Then it is well known by the Nullstellensatz that either $P$ has a simultaneous zero over $\mathbb{C}^n$ or else there exists $G = \{g_i\} \subseteq \mathbb{R}[x_1, \ldots, x_n]$ such that $\sum g_i p_i = 1$.

Similarly the Positivstellensatz suggests we can also do the same over the reals; either $P$ has a simultaneous zero over $\mathbb{R}^n$ or else there exists $Q = \{ q_i\} \subseteq \mathbb{R}[x_1, \ldots, x_n]$ and $S = \{ s_i\} \subseteq \mathbb{R}[x_1, \ldots, x_n]$ such that $\sum q_i p_i = 1 + \sum s_i^2$

However, often we want to consider the boolean case where $x_j^2-x_j \in P$ for all $j \in \{1, \ldots, n\}$ or similar which automatically restricts the variety of $P$ to be real. In this case, it seems that the latter result follows from the Nullstellensatz as well, where $Q=G$ and $S$ can be taken to be the empty set.

Nevertheless it appears such a $P$ may have many different $Q,S$ where $S$ is not empty, and intuitively one would think that nonempty $S$ allows additional 'flexibility', and allows the polynomials in $Q,S$ to have lower degree when $S$ is nonempty, than when $S$ is empty. But while I have seen hints to this, I have not yet seen an explicit statement of this.

More formally, let $\deg(G)$ be the maximal degree of a polynomial in $G$. Is it known (or is there a simple example) of a $P$ such that: $$\inf\left\{ \deg(G) \mid \sum g_i p_i = 1\right\} > \inf\left\{ \max(\deg(Q),\deg(S)) \mid \sum q_i p_i = 1 + \sum s_i^2 \right\}$$



1 Answer 1


there has been quite a bit of research done in this area, see e.g. http://www.ams.org/distribution/mmj/vol2-4-2002/grigoriev-etal.pdf

IIRC, there are examples showing that Positivstellensatz proof systems are stronger than the Nullstellensatz ones.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.