\documentclass[10pt]{article}
\usepackage{amsmath, amssymb, amsthm, amsfonts, bbm, color}
%\usepackage[left=2in, right=2in]{geometry}
\usepackage{enumerate}
\usepackage{fullpage}
\DeclareMathOperator*{\argmin}{argmin}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\newcommand{\bbF}{\mathbb{F}}
\newcommand{\bbK}{\mathbb{K}}
\newcommand{\bbQ}{\mathbb{Q}}
\newcommand{\bbZ}{\mathbb{Z}}
\renewcommand{\mod}{\mathrm{mod}\ }
\newcommand{\coeffs}{\mathrm{coeffs}}
\newcommand{\Res}{\mathrm{Res}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\Det}{\mathrm{Det}}
\newcommand{\Adj}{\mathrm{Adj}}
\newcommand{\Rad}{\mathrm{Rad}}
\newcommand{\NP}{\mathrm{NP}}
\newcommand{\RP}{\mathrm{RP}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\IM}{{\sc Ideal-Membership }}
\newcommand{\inbrace}[1]{\left \{ #1 \right \}}
\newcommand{\inparen}[1]{\left ( #1 \right )}
\newcommand{\insquare}[1]{\left [ #1 \right ]}
\newcommand{\inangle}[1]{\left \langle #1 \right \rangle}
\newcommand{\infork}[1]{\left \{ \begin{matrix} #1 \end{matrix} \right .}
\newcommand{\inmat}[1]{\begin{matrix} #1 \end{matrix}}
\newcommand{\inbmat}[1]{\begin{bmatrix} #1 \end{bmatrix}}
\newcommand{\insqmat}[1]{\insquare{\begin{matrix} #1 \end{matrix}}}
\newcommand{\inabs}[1]{\begin{vmatrix} #1 \end{vmatrix}}
\newcommand{\defeq}{\stackrel{\mathrm{def}}{=}}
\newcommand{\myignore}[1]{}
\newtheorem{problem}{Problem}
\newcommand{\Red}[1]{\textcolor{red}{#1}}
%\newenvironment{proofof}[1]{\noindent {\em Proof of #1.} \hspace{1mm}}{\hfill $\Box$}
\lecture{21}{April 27, 2015}{Madhu Sudan}{Pritish Kamath}
%%%% body goes in here %%%%
\section{Introduction}
In this lecture, we will see that the Ideal Membership problem is EXPSPACE-complete, which was shown by Mayr and Meyer \cite{MM_IM}. Next, we will see weak and strong statements of the Hilbert's Nullstellensatz.
%\begin{itemize}
%\item Complexity of Ideal Membership
%\item Hilbert Nullstellensatz\\
%$-$ Quantifier Elimination
%\end{itemize}
\section{Ideal Membership}
The ideal membership question is defined as follows,
\begin{problem}[{\sc Ideal-Membership}] \label{prob:IM}
Given polynomials $f, f_1, \cdots, f_m \in \bbK[\bx]$, decide whether $f \in \inangle{f_1, \cdots, f_m}$, or in other words, does there exist polynomials $g_1, \cdots, g_m \in \bbK[\bx]$ such that, $f = \sum_i f_i g_i$
\end{problem}
\noindent It turns out (due to \cite{MM_IM}) that {\sc Ideal-Membership} is EXPSPACE-complete! This is contrast with {\sc Radical-Ideal-Membership} that we saw in last lecture to be in PSPACE.
\subsection{EXPSPACE-hardness of \IM}
We show that \IM is EXPSPACE-hard by obtaining a reduction from Commutative Word Equivalence Problem (CWEP), which is known to be EXPSPACE-complete. It is formulated as follows:
\begin{problem}
We have an alphabet $\Sigma$ (assume $|\Sigma| = n$) along with an implicit equivalence rule,
$$\forall \ \sigma, \tau \in \Sigma \quad : \quad \sigma \tau \equiv \tau \sigma$$
and a set of $m$ equivalence rules of the type,
\begin{equation}
\alpha_i \equiv \beta_i \quad \quad \text{where } i \in [m] \text{ and } \alpha_i, \beta_i \in \Sigma^* \label{eqn:cwep}
\end{equation}
Given two strings $\alpha, \beta \in \Sigma^*$, we need to decide if $\alpha \equiv \beta$.
\end{problem}
Informally, the problem is to start with the string $\alpha \in \Sigma^*$, and we can do a series of operations which include either swapping two consecutive symbols or substituting a substring $\alpha_i$ by $\beta_i$ or vice-versa for some $i$. Due to commutativity, the order of the symbols in $\alpha$ don't matter, and thus $\alpha$ is completely determined by $\bd = (d_1, \cdots, d_n)$, where the $i$-th symbol in $\Sigma$ appears $d_i$ times in $\alpha$, that is, we can think of $\alpha$ as $\sigma_1^{d_1} \sigma_2^{d_2} \cdots \sigma_n^{d_n}$. The relationship between the CWEP and the ideal membership problem becomes clear once we interpret the substitution rules in Equation~\ref{eqn:cwep} as relations that generate an ideal.
\subsubsection*{Hard instance of \IM}
We get a reduction from CWEP as follows. Consider a CWEP instance, where $\alpha_i$'s (resp. $\beta_i$'s) correspond to the vectors $\bd_i$ (resp. $\be_i$'s), and $\alpha$ (resp. $\beta$) corresponds to the vector $\bd$ (resp. $\be$).
\noindent Let the polynomials $f_1, \cdots, f_m$ be given by $f_i = \bx^{\bd_i} - \bx^{\be_i}$ and let $f = \bx^{\bd} - \bx^{\be}$. It is easy to see that $f \in \inangle{f_1, \cdots, f_m}$ if and only if $\alpha \equiv \beta$ under the equivalence rules of $\alpha_i \equiv \beta_i$. And thus, we conclude that \IM is EXPSPACE-hard.
\subsection{EXPSPACE algorithm for \IM}
\noindent To show that \IM is in EXPSPACE, we will prove the following theorem (originally due to Hermann \cite{hermann}) as follows,
\begin{theorem}[Degree bound in \IM \cite{hermann}] \label{thm:hermann}
Consider an instance of \IM as defined in Problem~\ref{prob:IM}. Suppose that $\deg(f_i) \le d$ for all $i$ and $\deg(f) \le d$. Then for any $f \in \inangle{f_1, \cdots, f_m}$, it is possible to write $f = \sum_i g_i f_i$ where $\deg(g_i) \le (md)^{2^{O(n)}}$.
\end{theorem}
\noindent Assuming the above theorem, it is easy to see that \IM is in EXPSPACE. Namely, since we know that $\deg(g_i) \le \deg(f) + (md)^{2^{O(n)}} \defeq D$, we can set up $f = \sum_i g_i f_i$ as a linear system in $m \cdot \binom{n+D}{n}$ variables. In particular, if $f = \sum_{\beta} f^{[\beta]} \bx^{\beta}$, and $f_i = \sum_{\beta} f^{[\beta]}_{i} \bx^{\beta}$. We want to know if there exist $g_i = \sum_{\alpha} g^{[\alpha]}_{i} \bx^{\alpha}$ such that the following is true,
$$\forall \ \beta \text{ s.t. } |\beta| \le D + d \quad : \quad f_{\beta} = \sum_{i=1}^m \sum_{\alpha \preceq \beta} g^{[\alpha]}_{i} f^{[\beta - \alpha]}_{i}$$\\
This linear system can be solved in EXPSPACE. Note that we cannot do this by explicitly computing the entries because the linear system is doubly-exponentially large in $n$. However, we can still solve the system in EXPSPACE, by only implicitly dealing with the values involved in the linear system.\\
\noindent If we were allowed to formulate linear equations over a ring, instead of a field, then we can expressed the ideal membership as a single linear equation over the ring $R = \bbK[\bx]$, namely,
$$f = \sum g_i f_i \text{ where } g_i \in R$$
\noindent However, in a ring, this problem is hard since we cannot do inversions like we could in a field. We wish to bridge the gap between the two views, namely the {\em huge} linear system over $\bbK$ and the single linear equation over $R = \bbK[\bx]$. We will do this by a hybrid-type inductive argument over the number of variables $n$.\\
\noindent Define $\Pi(j)$ to be the problem obtained by looking at $f$, $f_i$'s and $g_i$'s as polynomials in $R_j[x_{j+1}, \cdots, x_n]$, where $R_j = (\bbK[x_1, \cdots, x_j])$. Note that $\Pi(n)$ is the single linear equation over $R_n = \bbK[\bx]$, whereas $\Pi(0)$ is the original linear system over $\bbK$.\\
\noindent Our inductive claim is: If $\Pi(j+1)$ has $M$ equations with each variable of degree $D$ then, $\Pi(j)$ has $\poly(M,D)$ equations with constants of degree $\poly(M,D)$. To this end, we prove the following lemma,
%Univariate example: $g_i = \sum_j g_{ij} x^j$, $f_i = \sum_j f_{ij} x^j$, $f = \sum_j f_j x^j$ We want to check
%$$\forall j \quad : \quad x^j f_j = \sum_i \sum_{\ell \le j} f_{i \ell} g_{\ell j}$$
\myignore{\begin{lemma}
Let $A\bx = b$ be an $M \times M$ linear system where entries in $A$ and $b$ are from $R[z]$ and degree $\le D$. Then, there if there exists a solution, then there exists a solution where the degree is at most $\poly(M,D)$. (Assumption. There exists a full rank minor of $A$ with monic determinant.)
\end{lemma}
\begin{proof}
See noteboook
\end{proof}
See notebook for why the monic assumption can be assumed wlog.
}
\begin{lemma}\label{lemma:low_deg_soln}
Suppose $A\bx = \bb$ is a $M \times M$ linear system, where the entries in $A$ and $\bb$ are univariate polynomials in $R[z]$, and each entry in $A$ has degree $\leq D$, and $A$ has full rank minor with monic determinant\footnote{here, we mean that $A$ has a minor $\tilde{A}$ such that $\rank(A) = \rank(\tilde{A})$ and $\Det(\tilde{A})$ is a monic polynomial in $z$}. Then if $A\bx = \bb$ has a solution, then it has a solution $\bx$ where for all $i$, $\deg(x_i) \leq \poly(MD)$.
\end{lemma}
\begin{proof}
Without the loss of generality we write
$$A = \inbmat{\tilde{A} & B \\ C & D}$$
where $\tilde{A}$ is full rank and det($\tilde{A}$) is monic. Suppose the solution looks like
$$\bx = \inbmat{\bx_1 \\ \bx_2} \quad \text{ and } \quad \bb = \inbmat{\bb_1 \\ \bb_2}$$
Note, since the rows of $\inbmat{C & D}$ are contained in the linear span of the rows of $\inbmat{\tilde{A} & B}$, we have that if a solution to $A\bx = \bb$ exists, then in fact
$$\inbmat{\tilde{A} & B} \inbmat{\bx_1 \\ \bx_2} = \inbmat{\bb_1} \implies \inbmat{C & D} \inbmat{\bx_1 \\ \bx_2} = \inbmat{\bb_2}$$
Therefore we can ignore the second constraint of $\inbmat{C & D} \bx = \inbmat{\bb_2}$, and only focus on the first constraint. Thus, we want to show that if a solution to $\inbmat{\tilde{A} & B} \bx = \inbmat{\bb_1}$ exists, then in fact there exists a solution $\bx$ such that $\deg(\bx) \le \poly(M,D)$.
\noindent We start with any solution to $\inbmat{\tilde{A} & B} \bx = \inbmat{\bb_1}$. Since $\tilde{A}$ has non-trivial determinant, we can write,
$$\bx_1 = \frac{\Adj(\tilde{A})}{\Det(\tilde{A})} (\bb_1 - B\bx_2)$$
so $\deg(\bx_i) \leq [\deg(\Adj(A)) + \deg(\bb_1) + \deg(B) + \deg(\bx_2)]$. So it suffices to show that we can obtain a solution where $\deg(\bx_2)$ is bounded by $\poly(M,D)$.\\
\noindent Now we use the observation that if $\inbmat{\bx_1 & \bx_2}^T$ is a solution to the linear system then $\inbmat{(\bx_1+ \Adj(\tilde{A})B \by) & (\bx_2 - \Det(\tilde{A}) \by)}^T$ is also a solution. Therefore by the division algorithm, we can make $\deg(\bx_2) \leq \deg(\Det(\tilde{A})) \leq MD$. Thus, we can obtain a solution $\bx$ where $\deg(\bx) \le \poly(MD)$.
\end{proof}
\noindent To show that our original problem satisfies the condition of having a full rank minor with monic determinant, we use the technique of applying a generic/random invertible linear transform. It allows us to use Lemma~\ref{lemma:low_deg_soln} and to ensure $\Det(\tilde{A})$ is monic.
\begin{lemma}\label{lemma:monic_det}
Given $A\bx = \bb$ with $A, \bb \in \bbK[x_1, \cdots, x_j]$, let $T: \bbK^j \rightarrow \bbK^j$ be an invertible affine transform. Then
\begin{enumerate}
\item $\bx$ is a solution to $A\bx = \bb$ if and only if $\bx(T)$ is a solution to $A(T)\bx(T) = \bb(T)$ and $\deg(\bx(T)) = deg(\bx)$.
\item With high probability over choices of $T$, $\Det(\tilde{A}(T))$ is monic in $x_j$.
\end{enumerate}
\end{lemma}
\begin{proofof}{Theorem \ref{thm:hermann}}
We start by writing a linear system in $\Pi(n)$, with a single equation $f = \sum_{i=1}^m g_i f_i$. We successively apply the inductive step to convert the linear system in $\Pi(j+1)$ to a linear system in $\Pi(j)$. Lemma~\ref{lemma:low_deg_soln}, in addition to Lemma~\ref{lemma:monic_det} guarantees that if the degrees of polynomials in number of equations in $\Pi(j+1)$ in $M_{j+1}$, then the degrees of the solution in $\Pi(j)$ can be made to be less than $\poly(M_{j+1},d)$ (since the enties in the linear system have degree at most $d = \max_i \deg(f_i)$). Also, going from $\Pi(j+1)$ to $\Pi(j)$ increases the number of linear equations to $M_j = \poly(M_{j+1}, d)$ (with degree at least $2$ in $M_{j+1}$). Thus finally when we get to $\Pi(0)$, the degrees of the solution can be brought down to $(md)^{2^{O(n)}}$.
\end{proofof}
\section{Hilbert's Nullstellensatz}
Hilbert's Nullstellensatz deals with the problem of finding common roots to a given set of polynomials.
\begin{problem} \label{prob:common_roots}
Given polynomials $f_1, \cdots, f_m \in \bbK[\bx]$ (where $\bbK$ is algebraically closed), decide whether there exists $(\alpha_1, \cdots, \alpha_n) = \alpha \in \bbK^n$ such that $f_j(\alpha) = 0$ for all $j \in [m]$.
\end{problem}
\noindent A more generalized version of this problem is as follows,
\begin{problem}\label{prob:gen_common_roots}
Given polynomials $f_1, \cdots, f_m, f_1', \cdots, f_{m'}'\in \bbK[\bx]$ (where $\bbK$ is algebraically closed), decide whether there exists $(\alpha_1, \cdots, \alpha_n) = \alpha \in \bbK^n$ such that $f_j(\alpha) = 0$ for all $j \in [m]$ and $f_j'(\alpha) \ne 0$ for all $j \in [m']$.
\end{problem}
\noindent We note that Problem~\ref{prob:gen_common_roots} in fact reduces to Problem~\ref{prob:common_roots}. Firstly, observe that $f_j'(\alpha) \ne 0$ for all $j \in [m']$ if and only if $F(\alpha) \defeq \prod_{j \in [m']} f_j'(\alpha) \ne 0$. Next we can reduce this to Problem~\ref{prob:common_roots} by adding an extra variable $y$ and noting that the polynomials $f_1, \cdots, f_m, (1-yF(\bx)) \in \bbK[\bx, y]$ have a common root if and only if there exists $\alpha \in \bbK^n$ such that $f_j(\alpha) = 0$ for all $j \in [m]$ and $F(\alpha) \ne 0$.\\
\noindent The statement of Hilbert's Weak Nullstellensatz is as follows,
\begin{theorem}[Weak Hilbert Nullstellensatz (WHN)] \label{thm:WHN}
For any ideal $I$ in $\bbK[\bx]$,
$$V(I) = \emptyset \quad \Leftrightarrow \quad 1 \in I$$
(Note that $1 \in I \; \Leftrightarrow \; I = \bbK[x_{1},\dots,x_{n}]$.)
\noindent In other words, polynomials $f_1, \cdots, f_m$ do not have a common zero iff there exist $g_1 \cdots g_m$ such that $1 = \sum_i f_i g_i$.
\end{theorem}
\noindent The statement of the Strong Nullstellensatz is defined in terms of the Radical Ideal, which is defined as follows,
\begin{definition}[Radical Ideal]
For any ideal $I \subseteq \bbK[\bx]$, the radical ideal of $I$ is $\Rad(I) = \set{f : \exists d \ f^d \in I}$.
\end{definition}
\begin{theorem}[Strong Hilbert Nullstellensatz (SHN)] \label{thm:SHN}
For any ideal $I$ in $\bbK[x_{1},\dots,x_{n}]$,
$$I(V(I))=\Rad(I)$$
In other words, the following are equivalent,
\begin{itemize}
\item polynomials $f_1, \cdots, f_m, F \in \bbK[\bx]$ are such that for every $\alpha \in \bbK^n$, if $f_i(\alpha) = 0$ for all $i \in [m]$, then $F(\alpha) = 0$
\item there exists $d \ge 1$ such that $F^d \in \inangle{f_1, \cdots, f_m}$
\end{itemize}
\end{theorem}
\begin{lemma}
SHN and WHN are equivalent.
\end{lemma}
\begin{proof}
Both the SHN and the WHN have trivial directions (namely, $I(V(I)) \supseteq \Rad(I)$ and $V(I)=\emptyset \Leftarrow 1 \in I$ respectively). So we only need to prove the equivalence of the non-trivial directions of the SHN and the WHN (namely, $I(V(I)) \subseteq \Rad(I)$ and $V(I)=\emptyset \Rightarrow 1 \in I$ respectively).
\noindent {\bf [SHN $\implies$ WHN]} So suppose that $V(I) = \emptyset$. Then, by the SHN, $\Rad(I) = I(\emptyset) = \bbK[\bx]$. Hence, $1 \in \Rad(I)$ and thus $1 \in I$, as claimed in the WHN.
\noindent {\bf [WHN $\implies$ SHN]} Let $F \in I(V(I))$; we need to show that $F \in \Rad(I)$. If $F$ is identically $0$, we are done; so assume that $F$ is not identically $0$. Consider the ideal $J$ in $\bbK[x_{1},\dots,x_{n},y]$, where $y$ is an auxiliary variable, defined by $J = \inangle{I,1-yF}$.
Notice that $V(J)=\emptyset$. Indeed, suppose by way of contradiction that there is $(a_{1},\dots,a_{n},b) \in V(J)$; then $(a_{1},\dots,a_{n}) \in V(I)$ and thus $f(a_{1},\dots,a_{n})=0$, and thus $1-b F(a_{1},\dots,a_{n})=1-0=1 \neq 0$; we conclude that $V(J)$ must indeed be empty.
By the WHN, since $V(J)=\emptyset$, we know that $1 \in J$, so that there must exist $p \in \bbK[x_{1},\dots,x_{n},y]$ and $q_{1},\dots,q_{d} \in I$ such that $1 = p (1-yF) + \sum_{i=0}^{d} y^{i} q_{i}$. This polynomial identity holds in $\bbK[\bx,y]$, and thus also in $\bbK(\bx)[y]$; furthermore, since $F$ is not identically $0$, $1/F$ is a well defined element in $\bbK(x_{1},\dots,x_{n})$. By setting $y=1/F$, we deduce that $1 = \sum_{i=0}^{d} F^{-i} q_{i}$, and thus $F^{d} = \sum_{i=0}^{d} F^{d-i} q_{i}$, which means that $F^{d} \in I$, and thus $F \in \Rad(I)$, as we wanted to show.
\end{proof}
\subsection{Remarks on the Nullstellensatz}
Brownawell \cite{brownawell} showed that in the statement of Weak Nullstellensatz [Theorem~\ref{thm:WHN}] we can have $\deg(g_i) \le \prod_i \deg(f_i)$. Note that one can try to invoke Theorem \ref{thm:hermann} (due to Hermann) here, since we are trying to solve an ideal membership problem here of writing $1 = \sum_i g_i f_i$. However, the bound we get is doubly-exponential in $n$, whereas Brownawell's result gives a much stronger bound.\\
\noindent This suggests that perhaps finding witnesses $g_i$'s such that $1 = \sum_i g_i f_i$ should not be a very hard problem. In particular, it is clear that it is in PSPACE. More strongly though, Koiran showed that assuming the Generalized Riemann Hypothesis, Hilbert Nullstellensatz is in $\RP^{\NP}$ \cite{koiran_HN}.
%[Brownawell '87] $\deg(g_i) \le \deg(f) \cdot \prod \deg(f_i)$.
\begin{thebibliography}{alpha}
\bibitem{MM_IM} Ernst Mayr and Albert Meyer
\newblock The complexity of the word problems for commutative semigroups and polynomial ideals
\newblock {\em Advanced in Mathematics}, Volume 46, Issue 3, December 1982, Pages 305–329%{\em STOC}, 1998.
\bibitem{hermann} G. Herrmann
\newblock Die Frage der endlich vielen Schritte in der Theorie der Polynomideale
\newblock {\em Math. Ann.} 95, (1926), 736-788.
\bibitem{brownawell} W. Dale Brownawell
\newblock Bounds for the Degrees in the Nullstellensatz
\newblock {\em Annals of Mathematics} Second Series, Vol. 126, No. 3 (Nov., 1987), pp. 577-591
\bibitem{koiran_HN} Pascal Koiran
\newblock Hilbert's Nullstellensatz is in the polynomial hierarchy.
\newblock {\em Journal of Complexity}, 12(4):273-286, 1996.
\end{thebibliography}
\end{document}