\documentclass[10pt]{article}
\usepackage{amsfonts}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\bf Z}}
\usepackage{psfig}
\usepackage{epsf}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\lecture{23}{November 30, 2005}{Madhu Sudan}{Karola M\'esz\'aros}
%%%% body goes in here %%%%
\begin{center} \begin{Large} Strassen's lower bound for polynomial evaluation and Bezout's theorem \end{Large}\end{center}
Recall Strassen's algorithm from the previous lecture:
\noindent
Given: $(a_0, \ldots, a_{n-1}), (x_1, \ldots, x_n) \in K$, and polynomial $p(x)=\sum_{i=0}^{n-1}a_i x^i$
\noindent
Task: find $(z_1, \ldots, z_n)$, $z_i=p(x_i)$
How many steps do we need to accomplish this task? Using the Fast Fourier Transform (FFT) we need $O(n \log^2 n)$ steps. Strassen was interested whether it can be done faster, and he showed that $\Omega (n \log n)$ steps are needed in algebraic computation trees.
\begin{center}
\textbf{Reminder of Algebraic Computation Trees}
\end{center}
\begin{center}
\epsfbox{act.eps}
\end{center}
Perform computations of the form $v_i:=x_j$, or $v_i:=v_j\cdot v_k$, where $j, k * \prod_{i=1}^m d_i$, where $d_i= \deg f_i$. From here we wish to derive a contradiction.
We would like to construct a polynomial $P(x_1)$ such that $P(\alpha^{(1)})=0$ for every $\alpha=(\alpha^{(1)}, \ldots, \alpha^{(n)}) \in S$, $P$ is not identically zero, and $\deg P \leq \prod_{i=1}^m d_i$. We would like to eliminate $x_2, \ldots, x_n$, so we should do quantifier elimination. This, however, does not quite work.
\textit{First construction.} Let $Q(y_1, \ldots, y_m, x_1) \in k'[y_1, \ldots, y_m, x_1]$ (where $k'$ is a slight modification of $k$, see paper by Wooley) such that $\deg_{x_1} Q \leq \prod_{i=1}^m d_i$, $Q(\widetilde{f_1}, \ldots, \widetilde{f_m}, x_1)=0$ (where $\widetilde{f_i}$ is a slight modification of $f_i$, see paper by Wooley), and $Q \not \in k'[y_1, \ldots, y_m]$.
Now, set $P_0(x_1)=Q(0, \ldots, 0, x_1)$. Then $\deg P_0 \leq \prod_{i=1}^m d_i$, and $P(\alpha^{(1)})=Q(0, \ldots, 0, \alpha^{(1)})=Q(f_1(\alpha), \ldots, f_m(\alpha), \alpha^{(m)})=Q(f_1(x), \ldots, f_m(x), x_1)|_{x=\alpha}=0$. However, this construction fails, since we cannot assert that $P_0$ is not identically zero.
\textit{A new idea}: Consider ring $k[z]$. There exist $\gamma_1, \ldots, \gamma_m \in k[z]$ such that $Q(\gamma_1 z, \ldots, \gamma_m z, x_1)\neq 0$. Set $P_1(x_1)=Q(\gamma_1 z, \ldots, \gamma_m z, x_1)$. Then $\deg P_1 \leq \prod_{i=1}^m d_i$, and $P_1$ is not identically zero. Also, $P_1(\alpha^{(1)})=Q(\gamma_1 z, \ldots, \gamma_m z, x_1)=Q(0, \ldots, 0, \alpha^{(1)}) \mbox{ mod }z=0 \mbox{ mod }z$. Now the proof uses essentially Hensel's lifting and linear algebra. Indeed, consider $P(z)$, and $\alpha_1, \ldots, \alpha_k$ such that $P(\alpha_i)=0 \mbox{ mod }N$. If $(\alpha_i-\alpha_j, N)=1$, then $k \leq deg P$. Also, to the initial set of conditions $Q(y_1, \ldots, y_m, x_1) \in k'[y_1, \ldots, y_m, x_1]$ (where $k'$ is a slight modification of $k$, see paper by Wooley) such that $\deg_{x_1} Q \leq \prod_{i=1}^m d_i$, $Q(\widetilde{f_1}, \ldots, \widetilde{f_m}, x_1)=0$ (where $\widetilde{f_i}$ is a slight modification of $f_i$, see paper by Wooley), and $Q \not \in k'[y_1, \ldots, y_m]$, condition $\widetilde{f_i}=f_i \mbox{ mod }z$ is added. For details see [Wooley, '96].
\end{document}
*