2
$\begingroup$

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\}$$

Thanks.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .