<p>As Josh mentions, there is no way around the fact that the degree of the input polynomials <span class="math-container">$d=\max\{f_i:i\in[m]\}$</span> can be arbitrarily large, whence so can be the minimal degree of a refutation. However, it is easy to see that once there is any refutation at all (i.e., the <span class="math-container">$\vec f_i$</span> have no common <span class="math-container">$\{0,1\}$</span> zero), there is one of degree at most <span class="math-container">$d+n$</span>:</p>
<p>As you already noted in the question, given
<span class="math-container">$$1=\sum_if_ig_i+\sum_i(x_i^2-x_i)h_i,$$</span>
you may replace each <span class="math-container">$g_i$</span> with its multilinearization <span class="math-container">$M(g_i)$</span> while retaining the relation
<span class="math-container">$$1-\sum_if_ig_i\in\sum_i(x_i^2-x_i)\mathbb F[\vec x].$$</span>
This ensures <span class="math-container">$\deg(g_i)\le n$</span>, thus <span class="math-container">$\deg(f_ig_i)\le d+n$</span>. Moreover,
<span class="math-container">$$h=1-\sum_if_ig_i$$</span>
is a polynomial of degree <span class="math-container">$d+n$</span> such that <span class="math-container">$M(h)=0$</span>. Thus, it remains to observe that for any polynomial <span class="math-container">$h\in\mathbb F[\vec x]$</span>, we can write
<span class="math-container">$$h-M(h)=\sum_i(x_i^2-x_i)h_i$$</span>
for some <span class="math-container">$h_i$</span> such that <span class="math-container">$\deg\bigl((x_i^2-x_i)h_i\bigr)\le\deg(h)$</span>. E.g., this can be done by successively lowering the degree of each monomial: if <span class="math-container">$e_i&gt;1$</span>, we have
<span class="math-container">$$x_1^{e_1}\cdots x_i^{e_i}\cdots x_n^{e_n}-x_1^{e_1}\cdots x_i^{e_i-1}\cdots x_n^{e_n}=(x_i^2-x_i)x_1^{e_1}\cdots x_i^{e_i-2}\cdots x_n^{e_n}.$$</span></p>

CC BY-SA 4.0
2024-12-05T07:39:23.647Z
2024-12-05T09:32:29.680Z
2024-12-05T09:32:29.680Z
Emil Jeřábek
<p>To start with, you need some assumption on the degrees of the <span class="math-container">$f_i$</span>. For example, if <span class="math-container">$f_1 = x_1^{d}-2$</span>, then although <span class="math-container">$\{f_1, x_1^2 - x_1\}$</span> is unsatisfiable, we already have <span class="math-container">$deg f_1 = d$</span>, which we could choose to be <span class="math-container">$\gg n$</span> (where <span class="math-container">$n$</span> is the number of variables; in particular, in this case we have just one variable but can choose <span class="math-container">$d$</span> as large as we like).</p>
<p>In the papers you mention in the OQ, and in many settings in (algebraic) proof complexity, the <span class="math-container">$f_i$</span> are translations of Boolean clauses, so they are multilinear (and often even constant-degree). In this setting, there is a &quot;standard&quot; &quot;truth-table&quot; proof of degree <span class="math-container">$n$</span> based on the polynomial identity <span class="math-container">$\sum_{S \subseteq [n]} \left(\prod_{i \in S} x_i\right)\left( \prod_{i \notin S} (1-x_i)\right) = 1$</span>. See for example Pitassi '96 (DIMACS).</p>

CC BY-SA 4.0
2024-12-04T20:57:41.373Z
2024-12-04T20:57:41.373Z
Joshua Grochow
<p>I'll start with some background. Consider the polynomial ring <span class="math-container">$\mathbb{F}[x_1,\ldots,x_n]$</span>, where <span class="math-container">$\mathbb{F}$</span> is a field. Let <span class="math-container">$\mathcal{F} = \{f_1=0, \ldots, f_m=0\}$</span> be a set of polynomial constraints and let <span class="math-container">$V = \{x \in \mathbb{R}^n \ | \ f_1(x)=f_2(x)=\ldots=f_m(x)=0\}$</span> be the set of common zeros of the polynomials in <span class="math-container">$\mathcal{F}$</span>. Assume that the Boolean constraints <span class="math-container">$x_i^2 - x_i =0$</span> are included in <span class="math-container">$\mathcal{F}$</span> for every <span class="math-container">$i \in \{1, \ldots, n\}$</span>. A <em>Nullstellensatz refutation</em> of <span class="math-container">$\mathcal{F}$</span> is an identity of the form
<span class="math-container">$$ 1 = \sum_{i=1}^m g_i f_i. $$</span>
where <span class="math-container">$g_i \in \mathbb{F}[x_1, \ldots, x_n]$</span> are polynomials. The <em>degree</em> <span class="math-container">$d$</span> of the refutation is defined as <span class="math-container">$d = \max \{\deg_i g_i f_i\}$</span>.</p>
<p>It is known that whenever <span class="math-container">$S = \emptyset$</span>, i.e. when the polynomial system <span class="math-container">$\mathcal{F}$</span> is infeasible, then there exist such identities.</p>
<p>Here's what I don't understand. Many papers state (claiming it is evident) that the polynomial coefficients <span class="math-container">$g_i$</span> can be assumed to be of the degree at most <span class="math-container">$O(n)$</span>, since these polynomials can be multilinearized using the Boolean constraints <span class="math-container">$x_i^2 - x_i = 0$</span>. Therefore, the upper bound on the degree of such refutations is <span class="math-container">$O(n)$</span>. How can I see this?</p>
<p>Moreover, let's relabel the Boolean constraints as <span class="math-container">$B_1 = x_1^2 - x_1, \ldots, B_n = x_n^2 - x_n$</span>, thus <span class="math-container">$\mathcal{F} = \{f_1=0, \ldots, f_m=0, B_1=0, \ldots, B_n=0\}$</span>. If <span class="math-container">$\mathcal{F}$</span> is infeasible, then there exists a Nullstellensatz refutation
<span class="math-container">$$1 = \sum g_i f_i + \sum h_i B_i$$</span>
where <span class="math-container">$g_i, h_i \in \mathbb{F}[x_1, \ldots, x_n]$</span>. I can see why we can assume that <span class="math-container">$g_i$</span> is multilinear. But why can also <span class="math-container">$h_i$</span> be assumed to be multilinear?</p>
<p>(Some) References:</p>
<ol>
<li>D. Grigoriev, &quot;Tseitin's tautologies and lower bounds for Nullstellensatz proofs,&quot; Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), Palo Alto, CA, USA, 1998, pp. 648-652, doi: 10.1109/SFCS.1998.743515.</li>
<li>D. Grigoriev, “Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity,” Theoretical Computer Science, vol. 259, no. 1–2, pp. 613–622, May 2001, doi: 10.1016/S0304-3975(00)00157-2.</li>
</ol>

<proof-complexity>
Degree Bounds in Nullstellensatz Proof System
Alexandros
# Degree Bounds in Nullstellensatz Proof System

(Asked by: username_0 on 2024-12-04)

I'll start with some background. Consider the polynomial ring $\mathbb{F}[x\_1,\ldots,x\_n]$, where $\mathbb{F}$ is a field. Let $\mathcal{F} = \{f\_1=0, \ldots, f\_m=0\}$ be a set of polynomial constraints and let $V = \{x \in \mathbb{R}^n \ | \ f\_1(x)=f\_2(x)=\ldots=f\_m(x)=0\}$ be the set of common zeros of the polynomials in $\mathcal{F}$. Assume that the Boolean constraints $x\_i^2 - x\_i =0$ are included in $\mathcal{F}$ for every $i \in \{1, \ldots, n\}$. A *Nullstellensatz refutation* of $\mathcal{F}$ is an identity of the form
$$ 1 = \sum\_{i=1}^m g\_i f\_i. $$
where $g\_i \in \mathbb{F}[x\_1, \ldots, x\_n]$ are polynomials. The *degree* $d$ of the refutation is defined as $d = \max \{\deg\_i g\_i f\_i\}$.

It is known that whenever $S = \emptyset$, i.e. when the polynomial system $\mathcal{F}$ is infeasible, then there exist such identities.

Here's what I don't understand. Many papers state (claiming it is evident) that the polynomial coefficients $g\_i$ can be assumed to be of the degree at most $O(n)$, since these polynomials can be multilinearized using the Boolean constraints $x\_i^2 - x\_i = 0$. Therefore, the upper bound on the degree of such refutations is $O(n)$. How can I see this?

Moreover, let's relabel the Boolean constraints as $B\_1 = x\_1^2 - x\_1, \ldots, B\_n = x\_n^2 - x\_n$, thus $\mathcal{F} = \{f\_1=0, \ldots, f\_m=0, B\_1=0, \ldots, B\_n=0\}$. If $\mathcal{F}$ is infeasible, then there exists a Nullstellensatz refutation
$$1 = \sum g\_i f\_i + \sum h\_i B\_i$$
where $g\_i, h\_i \in \mathbb{F}[x\_1, \ldots, x\_n]$. I can see why we can assume that $g\_i$ is multilinear. But why can also $h\_i$ be assumed to be multilinear?

(Some) References:

1. D. Grigoriev, "Tseitin's tautologies and lower bounds for Nullstellensatz proofs," Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), Palo Alto, CA, USA, 1998, pp. 648-652, doi: 10.1109/SFCS.1998.743515.
2. D. Grigoriev, “Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity,” Theoretical Computer Science, vol. 259, no. 1–2, pp. 613–622, May 2001, doi: 10.1016/S0304-3975(00)00157-2.

**Tags:** proof-complexity


---

## 2 answers

### Answer by username_1 on 2024-12-05. Score: 4 | Accepted answer

As Josh mentions, there is no way around the fact that the degree of the input polynomials $d=\max\{f\_i:i\in[m]\}$ can be arbitrarily large, whence so can be the minimal degree of a refutation. However, it is easy to see that once there is any refutation at all (i.e., the $\vec f\_i$ have no common $\{0,1\}$ zero), there is one of degree at most $d+n$:

As you already noted in the question, given
$$1=\sum\_if\_ig\_i+\sum\_i(x\_i^2-x\_i)h\_i,$$
you may replace each $g\_i$ with its multilinearization $M(g\_i)$ while retaining the relation
$$1-\sum\_if\_ig\_i\in\sum\_i(x\_i^2-x\_i)\mathbb F[\vec x].$$
This ensures $\deg(g\_i)\le n$, thus $\deg(f\_ig\_i)\le d+n$. Moreover,
$$h=1-\sum\_if\_ig\_i$$
is a polynomial of degree $d+n$ such that $M(h)=0$. Thus, it remains to observe that for any polynomial $h\in\mathbb F[\vec x]$, we can write
$$h-M(h)=\sum\_i(x\_i^2-x\_i)h\_i$$
for some $h\_i$ such that $\deg\bigl((x\_i^2-x\_i)h\_i\bigr)\le\deg(h)$. E.g., this can be done by successively lowering the degree of each monomial: if $e\_i>1$, we have
$$x\_1^{e\_1}\cdots x\_i^{e\_i}\cdots x\_n^{e\_n}-x\_1^{e\_1}\cdots x\_i^{e\_i-1}\cdots x\_n^{e\_n}=(x\_i^2-x\_i)x\_1^{e\_1}\cdots x\_i^{e\_i-2}\cdots x\_n^{e\_n}.$$


---

### Answer by username_2 on 2024-12-04. Score: 5

To start with, you need some assumption on the degrees of the $f\_i$. For example, if $f\_1 = x\_1^{d}-2$, then although $\{f\_1, x\_1^2 - x\_1\}$ is unsatisfiable, we already have $deg f\_1 = d$, which we could choose to be $\gg n$ (where $n$ is the number of variables; in particular, in this case we have just one variable but can choose $d$ as large as we like).

In the papers you mention in the OQ, and in many settings in (algebraic) proof complexity, the $f\_i$ are translations of Boolean clauses, so they are multilinear (and often even constant-degree). In this setting, there is a "standard" "truth-table" proof of degree $n$ based on the polynomial identity $\sum\_{S \subseteq [n]} \left(\prod\_{i \in S} x\_i\right)\left( \prod\_{i \notin S} (1-x\_i)\right) = 1$. See for example Pitassi '96 (DIMACS).


---

