\documentclass[runningheads, 11pt]{article}
\usepackage{graphicx,verbatim,xspace,color}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{fullpage}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{definition}
\newtheorem{remark}[theorem]{Remark}



\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\heading}[6]{
  \renewcommand{\thepage}{\arabic{page}}
  \noindent
  \begin{center}
  \framebox{
    \vbox{
      \hbox to 5.78in { \textbf{#2} \hfill #3 }
      \vspace{4mm}
      \hbox to 5.78in { {\Large \hfill #6  \hfill} }
      \vspace{2mm}
      \hbox to 5.78in { \textit{Instructor: #4 \hfill #5} }
    }
  }
  \end{center}
  \vspace*{4mm}
}
%
%\newenvironment{proof}{\noindent{\bf Proof:} \hspace*{1mm}}{
%	\hspace*{\fill} $\Box$ }
%\newenvironment{proof_of}[1]{\noindent {\bf Proof of #1:}
%	\hspace*{1mm}}{\hspace*{\fill} $\Box$ }
%\newenvironment{proof_claim}{\begin{quotation} \noindent}{
%	\hspace*{\fill} $\diamond$ \end{quotation}}

\newcommand{\lecturenotes}[4]{\heading{#1}{6.S897 Algebra and Computation}{#2}{Madhu Sudan}{Scribe: #3}{#4}}

\newcommand{\lecturenum}{15}          % lecture number
\newcommand{\lecturetitle}{Hilbert Nullstellensatz \& Quantifier Elimination} % topic of lecture
\newcommand{\lecturedate}{April 11, 2012}  % date of lecture
\newcommand{\studentname}{Alessandro Chiesa}    % full name of student (i.e., you)



\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\LL}{\mathbb{L}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\from}{\leftarrow}
\newcommand{\Ideal}{\mathrm{Ideal}}
\newcommand{\Variety}{\mathrm{Var}}
\newcommand{\Rad}{\mathrm{Rad}}
\newcommand{\Res}{\mathrm{Res}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%555
\begin{document}
\lecturenotes{\lecturenum}{\lecturedate}{\studentname}{\lecturetitle}


Throughout, $\K$ will denote an algebraically closed field.

Recall that, given a (commutative) ring $R$, an \emph{ideal} $I$ of $R$ if $I \subseteq R$, $I$ is closed under addition (i.e., $a,b \in I \implies a+b \in I$) and under multiplication by elements of $R$ (i.e., $a \in I, r \in R \implies ra \in I$).

Also recall that a subset $V$ of $\K^{n}$ is an \emph{(affine) variety} if it is the locus of points where some set of polynomials in $\K[x_{1},\dots,x_{n}]$ vanish simultaneously.

For more details about ideals and varieties (including further discussions and more detailed proofs for the Hilbert Nullstellensatz, which we will cover today), see \cite{CoxLO07}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{From Ideals to Varieties and Back}

When studying polynomials $f_{1},\dots,f_{m} \in \K[x_{1},\dots,x_{n}]$, we can choose an algebraic or geometric perspective; these two perspectives respectively give rise to the notions of the ideal and the variety of $\{f_{1},\dots,f_{m}\}$.

\begin{definition}
The \emph{ideal} of $f_{1},\dots,f_{m} \in \K[x_{1},\dots,x_{n}]$ is the set of \underline{polynomials}
\begin{equation*}
\Ideal(f_{1},\dots,f_{m})
=
\left\{
\sum_{i=1}^{m} q_{i} f_{i} \;\middle\vert\; q_{1},\dots,q_{m} \in \K[x_{1},\dots,x_{n}]
\right\}
\enspace.
\end{equation*}
\end{definition}

\begin{definition}
The \emph{variety} of $f_{1},\dots,f_{m} \in \K[x_{1},\dots,x_{n}]$ is the set of \underline{points}
\begin{equation*}
\Variety(f_{1},\dots,f_{m})
=
\left\{
(a_{1},\dots,a_{n}) \in \K^{n} \;\middle\vert\; f_{1}(a_{1},\dots,a_{n})= \cdots = f_{m}(a_{1},\dots,a_{n}) = 0
\right\}
\enspace.
\end{equation*}
\end{definition}

\noindent
More generally, given a variety $V$ in $\K^{n}$ and an ideal $I$ in $\K[x_{1},\dots,x_{n}]$, we can define
\begin{align*}
\Ideal(V)
=&
\left\{
f \in \K[x_{1},\dots,x_{n}] \;\middle\vert\; f(a_{1},\dots,a_{n})=0 \text{ for all } (a_{1},\dots,a_{n}) \in \K^{n}
\right\}
\enspace, \\
\Variety(I)
=&
\left\{
(a_{1},\dots,a_{n}) \in \K^{n} \;\middle\vert\; f(a_{1},\dots,a_{n}) = 0 \text{ for all } f \in I
\right\}
\enspace.
\end{align*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Radical of an Ideal}

An important notion that we shall need today is the radical of an ideal:

\begin{definition}
The \emph{radical} of an ideal $I$, denoted $\Rad(I)$, is the set defined as follows:
\begin{equation*}
\Rad(I) =
\left\{
f \in \K[x_{1},\dots,x_{n}]
\;\middle\vert\
\text{there is a positive integer $d$ s.t. } f^{d} \in I
\right\}
\enspace.
\end{equation*}
\end{definition}

The radical of an ideal is in fact an ideal itself:

\begin{lemma}
If $I$ is an ideal, then so is $\Rad(I)$.
\end{lemma}

\begin{proof}
Suppose that $f \in \Rad(I)$ and let $h \in \K[x_{1},\dots,x_{n}]$. From the definition of $\Rad(I)$, we know that there is a positive integer $d$ such that $f^{d} \in I$. Since $I$ is an ideal, we also know that $h^{d}f^{d} \in I$. But this means that $hf \in \Rad(I)$ as well.

Let $g \in \Rad(I)$. Again from the definition of $\Rad(I)$, we know that there is a positive integer $e$ such that $g^{e} \in I$. Note that $(f+g)^{d+e}=\sum_{i=0}^{d+e} \binom{d+e}{i} f^{i}g^{d+e-i}$ is a sum of terms each of which is divisible by either $f^{d}$ or $g^{e}$, so that $(f+g)^{d+e} \in I$, and thus $f+g \in \Rad(I)$.
\end{proof}

Note also that $\Rad(\cdot)$ is idempotent: $\Rad(\Rad(\cdot))=\Rad(\cdot)$.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Hilbert Nullstellensatz}

Note that $\Variety(\Ideal(f_{1},\dots,f_{m}))=\Variety(f_{1},\dots,f_{m})$. However, $\Ideal(\Variety(f_{1},\dots,f_{m}))$ contains, \textbf{but is not necessarily equal to}, $\Ideal(f_{1},\dots,f_{m})$. So when does the sequence of operations $\Ideal(\Variety(\Ideal(\Variety(\cdots))))$ converge?

A first observation is that, given an ideal $I$, $\Ideal(\Variety(I))$ contains not only $I$ but also its radical $\Rad(I)$. It actually turns out that $\Ideal(\Variety(I))$ contains nothing more than $\Rad(I)$ --- and thus we learn than the alternate application of $\Ideal(\cdot)$ and $\Variety(\cdot)$ ``stabilizes'' at the radical.

\begin{theorem}[Strong Hilbert Nullstellensatz (SHN)]
For any ideal $I$ in $\K[x_{1},\dots,x_{n}]$,
\begin{equation*}
\Ideal(\Variety(I))=\Rad(I)
\enspace.
\end{equation*}
In particular, $\Ideal(\Variety(\Rad(I)))=\Rad(I)$.
\end{theorem}

The proof of the SHN relies on the following simpler theorem, which states that the only way that a variety of an ideal can be empty is if the ideal contains all the possible polynomials:

\begin{theorem}[Weak Hilbert Nullstellensatz (WHN)]
For any ideal $I$ in $\K[x_{1},\dots,x_{n}]$,
\begin{equation*}
\Variety(I) = \emptyset
\;\Leftrightarrow\;
1 \in I
\enspace.
\end{equation*}
(Note that $1 \in I \;\Leftrightarrow\; I = \K[x_{1},\dots,x_{n}]$.)
\end{theorem}

Let us begin by showing the equivalence of the SHN and the WHN (and afterwards we shall prove WHN):

\begin{lemma}
The SHN and the WHN are equivalent statements.
\end{lemma}

\begin{proof}
Both the SHN and the WHN have trivial directions (respectively, $\Ideal(\Variety(I)) \supseteq \Rad(I)$ and $\Variety(I)=\emptyset \Leftarrow 1 \in I$), so we only need to prove the equivalence of the non-trivial directions of the SHN and the WHN (respectively, $\Ideal(\Variety(I)) \subseteq \Rad(I)$ and $\Variety(I)=\emptyset \Rightarrow 1 \in I$).

The easy implication is SHN $\implies$ WHN so let us begin with this one. So suppose that $\Variety(I) = \emptyset$. Then, by the SHN, $\Rad(I)=\Ideal(\Variety(I))=\Ideal(\emptyset)=\K[x_{1},\dots,x_{n}]$. Hence, $1 \in \Rad(I)$ and thus $1 \in I$, as claimed in the WHN.

So let us turn to the other implication, WHN $\implies$ SHN; this direction follows what is known as the Rabinowitsch trick \cite{Rabinowitsch30}.

Let $f \in \Ideal(\Variety(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 $\K[x_{1},\dots,x_{n},y]$, where $y$ is an auxiliary variable, defined by $J = \Ideal(I,1-yf)$.

Notice that $\Variety(J)=\emptyset$. Indeed, suppose by way of contradiction that there is $(a_{1},\dots,a_{n},b) \in \Variety(J)$; then $(a_{1},\dots,a_{n}) \in \Variety(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 $\Variety(J)$ must indeed be empty.

By the WHN, since $\Variety(J)=\emptyset$, we know that $1 \in J$, so that there must exist $p \in \K[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 $\K[x_{1},\dots,x_{n},y]$, and thus also in $\K(x_{1},\dots,x_{n})[y]$; furthermore, since $f$ is not identically $0$, $1/f$ is a valid element in $\K(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}$ is in $I$, and thus $f \in \Rad(I)$, as we wanted to show.
\end{proof}

Having established that the SHN and the WHN are equivalent statements, we concentrate on proving the WHN. The proof relies on the following lemma (which we shall prove in the next section):

\begin{lemma}[Extension Lemma]
Let $f_{1},\dots,f_{m} \in \K[x_{1},\dots,x_{n}]$ be monic in $x_{n}$ and $I = \Ideal(f_{1},\dots,f_{m})$. Let $J = I \cap \K[x_{1},\dots,x_{n-1}]$. If $(a_{1},\dots,a_{n-1}) \in \Variety(J)$ then there is $a_{n} \in \K$ such that $(a_{1},\dots,a_{n}) \in \Variety(I)$.
\end{lemma}

\begin{proof}[Proof of the WHN based on the Extension Lemma]
Recall that the non-trivial direction of the WHN is to show that if $\Variety(I) = \emptyset \implies 1 \in I$. The proof is by induction on $n$.

The base case $n=1$ is simple. In this case, $I$ is a principal ideal, say, $I = \Ideal(f)$ for some $f \in \K[x_{1}]$. Then $\Variety(I)$ is the set of roots of $f$. Since $\K$ is algebraically closed, every non-constant polynomial in $\K[x_{1}]$ has a root in $\K$, and thus $f$ has to be a constant polynomial. Thus, $1/f \in \K$ and thus $1 = (1/f) \cdot f \in I$, as desired.

So suppose that the statement holds for $n-1$. We wish to prove the statement for $n$. Say that $I = \Ideal(f_{1},\dots,f_{m})$ (recalling that every ideal is indeed finitely generated) and suppose that each $f_{i}$ is a non-constant polynomial of degree $d_{i}$ (for otherwise we are done for trivial reasons). For any $b_{1},\dots,b_{n-1} \in \K$, consider the linear transformation
\begin{equation*}
x_{1}=y_{1}+b_{1}y_{n}
\;,\;
x_{2}=y_{2}+b_{2}y_{n}
\;,\;
\dots
\;,\;
x_{n-1}=y_{n-1}+b_{n-1}y_{n}
\;,\;
x_{n}=y_{n}
\enspace.
\end{equation*}
Note that, for $i=1,\dots,m$,
\begin{align*}
  f_{i}(x_{1},\dots,x_{n})
=& f_{i}(y_{1}+b_{1}y_{n},\dots,y_{n-1}+b_{n-1}y_{n},y_{n}) \\
=& p_{i}(b_{1},\dots,b_{n-1})y_{n}^{d_{i}} + \text{ terms in which $\mathrm{deg}(y_{n})<d_{i}$}
\enspace.
\end{align*}
Because each $p_{i}(b_{1},\dots,b_{n-1})$ is some polynomial in $b_{1},\dots,b_{n-1}$ and $\K$ is algebraically closed (and thus, in particular, infinite), there are choices of $b_{1},\dots,b_{n-1}$ for which all the $p_{i}(b_{1},\dots,b_{n-1})$ are not equal to $0$. Since the constant polynomial $1$ is not affected by the transformation, this means that if $1 \in I'$ then $1 \in I$, where $I' = \Ideal(f_{1}',\dots,f_{m}') \subseteq \K[y_{1},\dots,y_{n}]$ is the ideal induced by the transformation by mapping each $f_{i}$ to a corresponding \emph{monic} polynomial $f_{i}'$. Also note that $\Variety(I)=\emptyset \implies \Variety(I')=\emptyset$.

Let $J' = I' \cap \K[x_{1},\dots,x_{n-1}]$ and suppose by way of contradiction that $1 \not\in I'$ so that, in particular, $1 \not\in J'$. By the inductive assumption, we know that there is $(a_{1},\dots,a_{n-1}) \in \Variety(J')$. Then, by invoking the Extension Lemma on the monic $f_{1}',\dots,f_{m}'$, we know that there is $a_{n} \in \K$ such that $(a_{1},\dots,a_{n}) \in \Variety(I')$, which is a contradiction.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Proving the Extension Lemma}

Recall that, for a ring $R$, given two polynomials $f$ and $g$ in $R[x]$ of positive degree $n$ and $m$ respectively, their \emph{resultant}, denoted $\Res(f,g)$, is the determinant of their corresponding $(n+m) \times (n+m)$ Sylvester matrix. The $\Res(f,g)$ is in the ideal $\Ideal(f,g)$ and, moreover, is equal to $0$ if and only if there is $h \in R[x]$ of positive degree that divides both $f$ and $g$.

We begin by proving the Extension Lemma in the special case $m=2$:

\begin{proof}[Proof of the Extension Lemma when $m=2$]
Define $p(x_{1},\dots,x_{n-1}) = \Res_{x_{n}}(f_{1},f_{2})$. Since $p \in I = \Ideal(f_{1},f_{2})$, we also know that $p \in J = I \cap \K[x_{1},\dots,x_{n-1}]$. Since $(a_{1},\dots,a_{n-1}) \in \Variety(J)$, we have that $p(a_{1},\dots,a_{n-1})=0$. Define $h_{1}(x_{n}) = f_{1}(a_{1},\dots,a_{n-1},x_{n})$ and $h_{2}(x_{n}) = f_{2}(a_{1},\dots,a_{n-1},x_{n})$. Since $f_{1}$ and $f_{2}$ are monic in $x_{n}$, both $h_{1}$ and $h_{2}$ have positive degree, and thus $\Res_{x_{n}}(h_{1},h_{2}) = \Res_{x_{n}}(f_{1},f_{2})\vert_{a_{1},\dots,a_{n-1}} = p(a_{1},\dots,a_{n-1})=0$. Thus, there must exist $g(x_{n}) \in \K[x_{n}]$ dividing both $h_{1}$ and $h_{2}$. Since $\K$ is algebraically closed, there must exist $a_{n} \in \K$ such that $g(a_{n})=0$.

Therefore, $h_{1}(a_{n})=h_{2}(a_{n})=0$, and we conclude that $f_{1}(a_{1},\dots,a_{n})=f_{2}(a_{1},\dots,a_{n})=0$, and $(a_{1},\dots,a_{n})$ is the point in $\Variety(I)$ that we wanted.
\end{proof}

We now prove the general case of the Extension Lemma by building on ideas for the $m=2$ case:

\begin{proof}[Proof of the Extension Lemma]
As before, let $I = I(f_{1},\dots,f_{n}) \subseteq \K[x_{1},\dots,x_{n}]$ with $f_{1},\dots,f_{m}$ all monic in $x_{n}$. Define $J = I \cap \K[x_{1},\dots,x_{n-1}]$ and let $(a_{1},\dots,a_{n-1}) \in \Variety(J)$. Consider the new ideal $I' = \Ideal(f_{1},F) \subseteq \K[x_{1},\dots,x_{n},y_{2},\dots,y_{m}]$ where $F(x_{1},\dots,x_{n},y_{2},\dots,y_{m}) = \sum_{i=2}^{m} f_{i}(x_{1},\dots,x_{n}) y_{i}$.

Define $p(x_{1},\dots,x_{n-1},y_{2},\dots,y_{m}) = \Res_{x_{n}}(f_{1},F)$. Note that $p(a_{1},\dots,a_{n-1},y_{2},\dots,y_{m})$ is identically zero. To show this, it suffices to prove that for all $b_{2},\dots,b_{m} \in \K$ we have $p(a_{1},\dots,a_{n-1},b_{2},\dots,b_{m})=0$. To see this, notice that $p(x_{1},\dots,x_{n-1},b_{2},\dots,b_{m}) = \Res_{x_{n}}(f_{1},F(x_{1},\dots,x_{n},b_{2},\dots,b_{m})) \in \Ideal(f_{1},F(x_{1},\dots,x_{n},b_{2},\dots,b_{m}))$ and thus is also in the ideal $I = \Ideal(f_{1},\dots,f_{m})$. We conclude that $p(x_{1},\dots,x_{n-1},b_{2},\dots,b_{m}) \in J$, so that $p(a_{1},\dots,a_{n-1},b_{2},\dots,b_{m})=0$.

Next, define $f_{1}'(x_{n}) = f_{1}(a_{1},\dots,a_{n-1},x_{n})$ and $H(x_{n},y_{2},\dots,y_{m}) = F(a_{1},\dots,a_{n-1},x_{n},y_{2},\dots,y_{m})$. Define $\LL=\overline{\K(y_{2},\dots,y_{m})}$ and note that $f_{1}',H \in \L[x_{n}]$. Due to the previous paragraph, we know that $f_{1}'$ and $H$ share a root $a_{n} \in \LL$. Since all the roots of $f_{1}'$ are in $\K$, we know that in fact $a_{n} \in \K$.

We conclude by noting that $(x_{n}-a_{n})$ divides both $f_{1}(a_{1},\dots,a_{n-1},x_{n})$ and $\sum_{i=2}^{m} f_{i}(a_{1},\dots,a_{n-1},x_{n}) y_{i}$ so that $(x_{n}-a_{n})$ divides each $f_{i}(a_{1},\dots,a_{n-1},x_{n})$. The point $(a_{1},\dots,a_{n})$ is the point in $\Variety(I)$ that we were looking for.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Degree Bounds for the Hilbert Nullstellensatz}

If $f_{1},\dots,f_{m} \in \K[x_{1},\dots,x_{n}]$ each have degree at most $d$ and there exist $q_{1},\dots,q_{m} \in \K[x_{1},\dots,x_{n}]$ such that $1 = \sum_{i=1}^{m} q_{i}f_{i}$, then what is the smallest degree bound $D_{n,m,d}$ on the $q_{i}$? The smaller $D_{n,m,d}$ can be shown to be, the easier it is to determine whether a system of polynomial equations has a solution; indeed, by the WHN, $1 \in \Ideal(f_{1},\dots,f_{m}) \Leftrightarrow \Variety(f_{1},\dots,f_{m}) = \emptyset$.
\begin{itemize}

  \item By invoking the degree bound analysis of Hermann \cite{Hermann26} for the ideal membership problem, we know that $D_{n,m,d} \leq (mdn)^{2^{O(n)}}$.

  \item Using complex analysis, Brownawell \cite{Brownawell87} showed that $D_{n,m,d} \leq (md)^{n}$; this bound is good enough to put the problem of deciding whether $1 \in I$ in $\mathsf{PSPACE}$ (as opposed to $\mathsf{EXPSPACE}$ with Hermann's weaker bound).

  \item Using cohomology, J\'{a}nos \cite{Janos88} showed the same bound, $D_{n,m,d} \leq (md)^{n}$.

  \item Using combinatorial counting arguments, Dub{\'e} \cite{Dube93} also showed the same bound, $D_{n,m,d} \leq (md)^{n}$.
  
  \item Under the Generalized Riemann Hypothesis, Koiran \cite{Koiran96} showed that deciding whether $\Variety(f_{1},\dots,f_{m}) = \emptyset$ is in $\mathsf{AM}$ (can be decided via an Arthur-Merlin protocol with two messages in which Arthur moves first).

\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Quantifier Elimination}

Given $f_{1},\dots,f_{m} \in \K[x_{1},\dots,x_{n}]$, the question of whether $\Variety(f_{1},\dots,f_{m})=\emptyset$ is the question of whether there is $(a_{1},\dots,a_{n}) \in \K^{n}$ with $f_{1}(a_{1},\dots,a_{n}) = \cdots = f_{m}(a_{1},\dots,a_{n}) = 0$.

The existential quantification in such a question is merely the ``first level'' of a question with more quantifiers we could ask. For example, at the second level, we could ask the following question:
\begin{equation*}
\text{ Is it the case that } \forall\, (a_{1},\dots,a_{n}) \in \K^{n} \;\exists\, (b_{1},\dots,b_{n}) \in \K^{n} \text{ s.t }
\begin{cases}
f_{1}(a_{1},\dots,a_{n},b_{1},\dots,b_{n})=0 \\
\vdots \\
f_{m}(a_{1},\dots,a_{n},b_{1},\dots,b_{n})=0
\end{cases}
?
\end{equation*}
More generally, we could also consider both equalities and \emph{disequalities} (i.e., asking when a certain polynomial is not equal to $0$).

How much harder are problems with such additional quantifiers relative to the basic existential question? It turns out that such problems can also be solved reasonably efficiently by showing that quantifiers can be eliminated with not too much overhead.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{alpha}
\bibliography{lect17}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%