\documentclass[10pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb, eqnarray}
\usepackage{amsthm}
\usepackage[all]{xy}
%\usepackage{epsfig}
%\usepackage{psfig}
\newcommand{\handout}[5]{
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in { {\bf 6.S897: Algebra and Computation} \hfill #2 }
\vspace{4mm}
\hbox to 5.78in { {\Large \hfill #5 \hfill} }
\vspace{2mm}
\hbox to 5.78in { {\em #3 \hfill #4} }
}
}
\end{center}
\vspace*{4mm}
}
\newcommand{\lecture}[4]{\handout{#1}{#2}{#3}{Scribe: #4}{Lecture #1}}
% 1-inch margins, from fullpage.sty by H.Partl, Version 2, Dec. 15, 1988.
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in
\parindent 0in
\parskip 1.5ex
%\renewcommand{\baselinestretch}{1.25}
\begin{document}
\lecture{17}{\today}
{Lecturer: Madhu Sudan}{Saeed Mehraban}
%\input{preamble.tex}
%\usepackage{fullpage}
\section{ Lower bounds for multi-point polynomial evaluation}
In this lecture we look into the lower bound problem for the multipoint polynomial evaluation problem. We specially focus on the following problem:
$$
f(x_1,x_2,\ldots,x_n)= (x_1^r, x_2^r, \ldots ,x_n^r)
$$
And we show that any algebraic circuit for the above map requires size $\Omega(n \log(r))$. There are two proofs for this fact. The first one, due to Strassen, uses techniques in algebraic geometry, namely the Bezout's theorem and the second one, according to Smolensky uses simple combinatorics and elementary algebra. In this lecture we mainly focus on Strassen's proof.
\section{Strassen's Proof}
We work with and algebraic closed field $\mathbb{K}$, and thereby, any non-constant polynomial over the field contains a root in the field. Strassen views an algebraic circuit as a collection of polynomial equations of degree at most 2. A multiplication gate $(x,y)\rightarrow x*y=z$ corresponds to the polynomial equation $z-x*y=0$, and an addition gate $(x,y)\rightarrow x+y=z$ is the degree one polynomial equation $z-x-y=0$. Therefore, we work with three types of variables, the inputs $ (x_1, x_2, \ldots, x_n)$, intermediate variables $(y_1, y_2, \ldots, y_n)$ and the outputs $(z_1, z_2, \ldots, z_n)$. Each gate introduces an new variable in this setting. Therefore, a circuit of size $s$ corresponds to a set of polynomial equation:
$$
p_1(\tilde{x},\tilde{y},\tilde{z})
$$
$$
p_1(\tilde{x},\tilde{y},\tilde{z})
$$
$$
\vdots\\
$$
$$
p_s(\tilde{x},\tilde{y},\tilde{z})
$$
Thereby, computation in the circuit corresponds to finding the set of common roots in these polynomials. In order to prove a circuit lower bound for the discussed map $(x_1,x_2,\ldots,x_n)\rightarrow (x_1^r, x_2^r, \ldots ,x_n^r)$, let us consider the special case where all the outputs are ones.
\newtheorem{claim}{Claim}
\begin{claim}
Define $V=\{(\alpha, \beta)\in \mathbb{K}^{n+m}| p_j(\alpha,\beta, 1^n)=0, j \in [s]\}$, as the set of common zeros $(\tilde{x},\tilde{y})=(\alpha,beta)$, when $\tilde{z}=(1,1, \ldots, 1)$. If the polynomials are according to the circuit computing $f$, then $|V|=r^n$
\end{claim}
\begin{proof}
In order to see this, let $X$ be the set of inputs $(x_1, x_2, \ldots, x_n )$ mapped to $(x^r_1, x^r_2, \ldots, x^r_n )=(1, 1, \ldots, 1)$. If $\omega$ is the principal $r$'th root of unity, then $X=\{\omega, \omega^2, \ldots, \omega^r=1\}$. So we restricted the variables to a case where $(x_1, x_2, \ldots, x_n )\in X^n$, where $X_n$ has cardinality $r^n$.
\end{proof}
Now consider the following fact from Algebraic Geometry:
\newtheorem{thm}{Theorem}
\begin{thm}
(Classical Bezout's Theorem) if $p_1, p_2, \ldots, p_s$ are polynomials in $\mathbb{K}(x_1,x_2, \ldots, x_n)$, if $\mathbb{K}$ is an algebraically closed field, then the number of common zeros for these polynomials is upper-bounded by the product of the degrees $\prod_{j\in [s]} deg(P_j)$.
\end{thm}
So given the Bezout's theorem, for the case of the discussed problem the number of common zeros, or equivalently $|V|$ is bounded by $2^s$. So any circuit computing $f$ should satisfy $r^n \leq 2^s$ and thereby $s=\Omega(n \log(r))$.
\section{Remarks on the Bezout's theorem}
Although the statement of the Bezout's theorem is a simple one, the rigorous proof for the statement is not as simple. In this section we give a primitive sketch of the proof and further remarks on the classical Bezout's theorem.
In order to approach this problem, we need a couple of definitions. Here we introduce a stronger version of the Bezout's theorem in which we deal with essential elements and ideas in algebraic geometry. Then we prove that the stronger version of the statement readily implies the classical Bezout's theorem.
\newtheorem{dfn}{Definition}
\begin {dfn}
For a set of polynomials in $\mathbb{K}[x_1, x_2, \ldots, x_n]$, we define the associated veriety, as a subset of points $\mathbb{K}^n$ along which the set of polynomials simultaneously vanish.
\end{dfn}
Also remember that for a commutative ring $R$, and ideal is a subset of the ring which is closed under addition and multiplication by the elements of the ring. More precisely, an ideal $I$ of the ring $\mathbb{K}[x_1, x_2, \ldots, x_n]$, is a subset $I \subset \mathbb{K}[x_1, x_2, \ldots, x_n]$ such that if $p,q\in I$ and $r\in \mathbb{K}[x_1, x_2, \ldots, x_n]$, then $p+q\in \mathbb{K}[x_1, x_2, \ldots, x_n]$ and $p.r\in I$. Now for polynomials $p_1, p_2,\ldots, p_s$ define the following ideal.
\begin {dfn}
The ideal of the set of polynomials $p_1, p_2,\ldots, p_s$ in $\mathbb{K}[x_1,x_2,\ldots, x_n]$ is the set:
$$
I(p_1, p_2,\ldots, p_n)=\Big \{ \sum_{i=1}^{s} q_i p_i \Big | q_i \in \mathbb{K}[x_1,x_2,\ldots, x_n]\Big \}
$$
\end {dfn}
From these two definitions we can also define veriety of an ideal $V(I)$ for ideal $I$, to be the set of point in $\mathbb{K}^n$ along which all the members of the ideal vanish. And also define an ideal of a variety $I(V)$, to be the set of polynomials, vanishing on $V$. Clearly $I\subset I (V(I))$. Since $I(V(I))$ at least contains $I$ but it might contain more elements. Now we can define define dimension and degree for a variety.
\begin{dfn}
The dimension of $V$ is:
$$
dim(V):= \min(k) : \text{there exists and affine subspace $A$ of dimension $n-k$ such that $0