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

\theoremstyle{definition}
\newtheorem{definition}[theorem]{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}{The Complexity of the Ideal Membership Problem} % topic of lecture
\newcommand{\lecturedate}{April 9, 2012}  % date of lecture
\newcommand{\studentname}{Jing Jian}    % full name of student (i.e., you)



\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\DeclareMathOperator{\mdeg}{mdeg}
\newcommand{\from}{\leftarrow}



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

\section{Overview}

Today we will discuss the complexity of the ideal membership problem. We will show a lowerbound of EXPSPACE hardness via a reduction to the ``commutative word problem.'' We will then prove a doubly-exponential via degree upperbounds by the Hilbert Nullstellensatz.  

\section{Formulation}

As a reminder, the formulation of ideal membership problem we are using today is as follows: given $f_0,f_1,\ldots,f_m\in\K[x_1,\ldots,x_n]$, are there $q_1,\ldots,q_m\in\K[x_1,\ldots,x_n]$ such that $f_0=\sum_{i=1}^mq_if_i$? 

\section{CWEP: The Commutative Word Equivalence Problem}

We show that Ideal Membership is EXPSPACE-Hard by reduction from the known EXPSACE-Complete commutative word equivalence problem.
It is formulated as follows:

\begin{definition}

We have an alphabet $\Sigma, |\Sigma| = n$ along with the implicit equivalence rule 
\begin{displaymath}
\sigma \tau = \tau \sigma, \forall \tau, \sigma \in \Sigma
\end{displaymath}

and a set of equivalence rules
\begin{displaymath}
\alpha_i = \beta_i, i = 1, ...m ....(*)
\end{displaymath}

Given two strings $\alpha, \beta$, we need to decide if $\alpha \equiv \beta$ in the setting.

\end{definition}


Due to the implicit rule, we can freely permute the letters in a string so that in any string $\alpha_i$ appears before $\beta_i$ and etc. Therefore what determines string $\alpha$ is the nubmer of occurences of the $j$th symbol for $j \in {1 \ldots n}$. The relationship between the CWEP and the ideal membership problem becomes clear since the (*) equations can be seen as relations that generate an ideal.

\subsection{Reduction}
The reduction is as follows:

\begin{itemize}

\item Let $\Sigma = {\sigma_1, \ldots , \sigma_n}$

\item Let
\begin{displaymath}
\alpha_i =\sigma_1^{i_1}\sigma_2^{i_2} ...\sigma_n^{i_n} \\
\beta_i =\sigma_1^{j_1} \sigma_2^{j_2} ...\sigma_n^{j_n}
\end{displaymath}

\item $\alpha_i = \beta_i \implies (\sigma_1^{i_1} + \sigma_2^{i_2} + ...+ \sigma_n^{i_n}) - (\sigma_1^{j_1} +\sigma_2^{j_2} +...+\sigma_n^{j_n}) = 0$

\item $f(x_1, \ldots , x_n) = (\sigma_1^{i_1} + ...+ \sigma_n^{i_n}) - (\sigma_1^{j_1} +...+\sigma_n^{j_n})$

\end{itemize}

\begin{claim}
The polynomial $f$ is in $Ideal(f_1, \ldots f_n)$ if and only if $\{ \alpha_i = \beta_i \} ^m_{j = 1}$ implies $\alpha = \beta$. 

\end{claim}
\begin{proof}
Omitted.
\end{proof}

\section{Upper Bounds}
To get EXPSPACE bounds on the problem, we need the following two things:
\begin{enumerate}
\item Linear systerm over $K$ with m equations and n variables can be solved in space $(log(m+n)^{O(1)})$
\item Degree of $q_i$ in solution only need to be doubly exponentially large in n: $deg(q_i) \leq D = (m n d)^{2^{O(n)}}$
\end{enumerate}
Combining the above we can get complexity SPACE(polylog(degree bound)). 
We will not prove statement 1 since it can be obtained via standard methods. We will focus on statement 2. 

\subsection{Two Views On Ideal Membership}
We can formulate the problem of ideal membership testing in two ways:
 
\begin{enumerate}
\item As \emph{one} linear equation over ring. Namely, given
\begin{displaymath}
f, f_1...f_m \in R = \mathbb{K}[x_i ... x_n]
\end{displaymath}

We want to know if there exist ${q_i}$ such that

\begin{displaymath}
f = \sum f_i q_i,  q_i \in R
\end{displaymath}

In a ring, this problem is hard, since we cannot do inversions like we could in a field.

\item However, we can also view it as \emph{many} linear equations over a field $\mathbb{K}$. 

We are given vectors of coefficients $f_{\vec{\beta}}, f_{1, \vec{\beta}}, ..f_m \in \mathbb{K}[x_1 \ldots x_n]$, and we want to know if there exist $\{q_{j, \vec{\alpha}}\}^{j = 1 \ldots m}_{\vec{\alpha} \in (\mathbb{Z}^{\geq 0})^n}$, $\sum \alpha_i \leq D_n$ such that $\forall \vec{\beta} \in (\mathbb{Z}^{\geq 0})^n, \sum \beta_i \leq D_n +d$ we have


\begin{displaymath}
f_{\vec{\beta}} = \sum_i \sum_{\vec{\alpha} \leq \vec{\beta}} q_{i, \vec{\alpha}} f_{i, \vec{\beta} - \vec{\alpha}}
\end{displaymath}
\end{enumerate}

We want to know when does the existance of a solution to 1 implies the the existance of solutions to 2 with parameter $D_n$. 

\subsection{Strategy}
The strategy we wil use is to build a common generalized problem $\Pi(j)$ such that $\Pi(n)$ is equivalent to formulation 1 and $\Pi(0)$ is equivalent to formulation 2. 

$\Pi_j$ is a $j$-variable linear system formulated as follows:
\begin{definition}
Given  $f_{\vec{\beta}}, f_{i, \vec{\beta}} \in \mathbb{K}[x_1 \ldots x_n]$, does there exist $\{q_{i, \vec{\alpha}}\}, \sum_{\alpha_i \leq D_j}$ such that 

\begin{displaymath}
f_{\vec{\beta}} = \sum_i \sum_{\vec{\alpha} \leq \vec{\beta}} q_{i, \vec{\alpha}} f_{i, \vec{\beta} - \vec{\alpha}}
\end{displaymath}
\end{definition}

With this general formulation, if we can find a way to eliminate variables, we can interpolate between the two views of ideal membership. If we can prove the following statement, we can prove the degree bound:

\begin{lemma}
$\Pi(j+1)$ has a solution with degree $ \leq D_{j+1}$ implies $\Pi(j)$ has a solution with degree $\leq poly(d, D_j+1, m)$. 
\end{lemma}



\section{Proof of The Variable-elimination Statement}
We write the collection of linear equations as $A\vec{x} = \vec{b}$. Since we are interested in eliminating variable $j$, we see $\vec{x}, \vec{b}$ as elements of $\mathbb{K}[x_1, ...x_j][x_j] = R[z]$ where $\mathbb{K}[x_1, ...x_j] = R$. 
We need the following key supporting lemma:

\begin{lemma}
Given $A\vec{x} = \vec{b}$ is a $M \times M$ linear system over $R[z]$ of degree $\leq D$, and $A$ has full rank miner with monic determinant, then $A\vec{x} = \vec{b}$ has solution implies that it has a solution with $deg(x_i) \leq poly(mD)$.
\end{lemma}

\begin{proof}
Without the loss of generality we write 
\begin{displaymath}
A = 
 \begin{bmatrix}
  \tilde{A} & B \\
  C & D 
 \end{bmatrix}
\end{displaymath} 
Where $\tilde{A}$ is full rank and det($\tilde{A}$) is monic. The solution looks like 
\begin{displaymath}
x =
 \begin{bmatrix}
  x_i \\
 x_2
 \end{bmatrix}, \text{  } b =
 \begin{bmatrix}
  b_i \\
 b_2
 \end{bmatrix}
\end{displaymath}
Note, by rank, that (if solution exists)

\begin{displaymath}
 \begin{bmatrix}
  \tilde{A} & B
 \end{bmatrix} 
  \begin{bmatrix}
  x_1 \\ x_2
 \end{bmatrix} 
 =   \begin{bmatrix}
  b_1
 \end{bmatrix} 
\implies 
 \begin{bmatrix}
  C & D
 \end{bmatrix} 
  \begin{bmatrix}
 x_1 \\ x_2
 \end{bmatrix} 
 =   \begin{bmatrix}
  b_2
 \end{bmatrix} 
\end{displaymath}
Therefore we can ignore 
$\begin{bmatrix}
  C & D
 \end{bmatrix}$,$ 
\begin{bmatrix}
  b_2
 \end{bmatrix}$.
We want to show that WLOG deg$( 
  \begin{bmatrix}
   x_1 \\x_2
 \end{bmatrix} )$ is small.
In the case of $x_1$, we have
\begin{displaymath}
x_1 = \tilde{A}^{-1}(b_1 - Bx_2)
\end{displaymath}
so $deg(x_i) \leq deg(Adj(A) + deg (b_i) + deg(B) + deg (x_2))$, due to the fact $\tilde{A}^{-1} = Adj(A)/det(A)$. So it suffices to show that we can reduce the degree of $x_2$.

Now we use the fact that $[x_i, x_2]$ has a solution implies $(x_1+ Adj(\tilde{A})B y_2, x_2 - det(\tilde{A} y_2)$ also has a solution. Therefore we can reduce $deg(x_2) \leq deg(det(\tilde{A})) \leq mD$. 

From above, it follows that $deg(x_i) \leq O(mD)$ also.
\end{proof}


To show that our original problem satisfies the above technical condition, we use a technique called Generic/Random invertible linear transform. It allows us to use Lemma 5.1 and to ensure $det(\tilde{A})$ is monic.


\begin{lemma} Given $A\vec{x} = \vec{b}$ with $A, \vec{b}, \in \mathbb{K}[x_1, ... x_j]$, let $T: \mathbb{K}^j \rightarrow K^j$ be an invertible affine transform. Then 
\begin{enumerate}
\item
$x$ is a solution to $(A, \vec{b})$ iff and only if $\vec{x}(T)$ is a solution to $(A(T), \vec{b}(T))$; and $deg(\vec{x}(T)) = deg(\vec{x})$.
\item With high probability over choices of $T$, $det(\tilde{A}(T))$ is monic in $x_j$.
\end{enumerate} 
\end{lemma}

Combining Lemma 5.1 and Lemma 5.2, we get proof of Hermann's bound on degrees of $q_1, \ldots, q_m$. 





\end{document}
