\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{url}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in
\begin{document}
\input{preamble.tex}
\newcommand{\FFT}{\mathop{{\rm FFT}}}
\newcommand{\mod}{\mathrel{{\rm mod}}}
\newtheorem{exercise}[theorem]{Exercise}
\lecture{4}{February 21, 2012}{Madhu Sudan}{Zachary Abel}
\section{Administrivia}
\begin{itemize}
\item Email list: Please make sure you are on the course email list. Email Prof.~Sudan to be added.
\item Blog: The course now has a blog: \url{http://algebraandcomputation.wordpress.com/}. Responses to ``your favorite or most surprising algorithms'' have been posted there, and you are encouraged to use this space to ask questions and contribute to course-related discussions. Instructions for posting can be found on the blog.
\item Scribing: Please sign up to scribe at least one lecture, whether you are taking the course for credit or not. Instructions for choosing dates are on the course website.
\end{itemize}
\section{Polynomial Arithmetic: Setup}
We now dicuss algorithms for performing basic operations with polynomials, such as polynomial multiplication, division with remainder, and evaluation at multiple points. Most of today focuses on efficiently multiplying two degree~$n$ polynomials. We will see a simple $O(n\log n)$ Fourier transformation (FT) based algorithm under sufficiently nice conditions and then show how this gives rise to a general $O(n\log n\log\log n)$ algorithm.
\subsection{Computational Model}
While we are mostly concerned with polynomials over a field $\F$, it will be helpful to work more generally with polynomials over a commutative ring $R$. Where appropriate, we will assume that our polynomials are \emph{monic}, i.e., have leading coefficient $1$. This can always be arranged over a field (by scalar multiplication), but this extra assumption will be necessary over general rings, for example, to even define the division-with-remainder problem. (What are the quotient and remainder when dividing $x^2$ by $2x+1$ in $\Z[x]$?)
In order to assume as little about the representation of the base ring $R$ as possible, we will measure the runtime of our algorithms in terms of basic operations in $R$. Specifically, we will separately keep track of three types of operations: additions in $R$ (which are usually cheap), general multiplications in $R$ (which are usually expensive), and ``special'' multiplications in $R$, such as by a power of 2 or other known constants. The identity of the ``special'' multiplications depends on the ring $R$ and the nature of the algorithm, but we count these separately because they are usually cheaper than general multiplications.
Note also that polynomials are represented in dense form: a polynomial $f\in R[x]$ of degree $n$ is represented by a list of $n+1$ coefficients in $R$, even if many of these coefficients are $0$.
Here are some of the fundamental problems we are interested in solving efficiently. Let the polynomials have degree at most $n$ unless otherwise specified:
\begin{enumerate}
\item Addition. Given $f,g\in R[x]$, compute $f+g$. This takes $O(n)$ additions.
\item Multiplication. Given $f,g\in R[x]$, compute $f\cdot g$. An algorithm based on the Fast Fourier Transformation will give an $O(n\log n)$ algorithm in special cases, which then leads to a general $O(n\log n\log\log n)$ algorithm.
\item Multipoint evaluation. Given $f$ and $\alpha_1,\ldots,\alpha_n\in R$, compute $f(\alpha_1),\ldots,f(\alpha_n)$. This can be done in $O(n\cdot\poly\log n)$ time, which seems surprising since each of the $n$ independent evaluations would take $O(n)$ time if done separately. Somehow we save time by doing many at once.
\item Interpolation. Given $\alpha_1,\ldots,\alpha_n,\beta_1,\ldots,\beta_n\in R$, find $f\in R[x]$ of degree at most $n-1$ such that $f(\alpha_i) = \beta_i$ for $1\le i\le n$. This is the inverse of multipoint evaluation, and also has $O(n\cdot \poly\log n)$ algorithms.
This problem is not as well-behaved over general rings, because such an $f$ may not exist, and/or there may be many solutions. For example, the interpolation problem $f(0)=f(1)=0$, $f(2)=1$ has no solutions over $\Z$ (over $\mathbb{Q}$ it is $f(x) = x(x+1)/2$). Over $\Z/6\Z$, $(x-2)(x-3)$ and the $0$ polynomial both solve the interpolation problem $f(0)=f(2)=f(3)=f(5)=0$.
If $R$ is a field, then the interpolating polynomial $f$ will always exist uniquely. More generally, if $f$ is an \emph{integral domain} (doesn't contain zero-divisors), then any $f$ will be unique if it exists.
\item Division with remainder. Given $f,g\in R[x]$ with $g$ monic, compute the unique polynomials $q,r\in R[x]$ with $\deg r < \deg g$ such that $f = g\cdot q + r$. This too can be done in nearly linear time.
\item GCD. Given $f,g\in\F[x]$ (over a field!), compute their Greatest Common Divisor.
\end{enumerate}
All of these algorithms are ``folklore'' from the 1960s, and appear in the introductory textbook \textit{Algorithms and Data Structures} by Aho, Hopcroft, and Ullman (1983). These algorithms seem to have been dropped in more modern references like \textit{Introduction to Algorithms} by Cormen et al.\ and thus seem less well-known.
Another important problem is that of polynomial factorization. The general problem of factoring a polynomial $f\in R[x]$ into irreducibles seems hard: for example, it includes factoring integers as a special case by taking $R=\Z$. But if we care only about breaking $f$ into lower-degree pieces, and not about factoring scalars in $R$, then there are polynomial-time algorithms (Berlekamp and Zassenhaus, 1970s), though no linear or nearly-linear algorithms are yet known. The most efficient factoring algorithm currently known is due to Kedlaya and Umans in 2009, which factors polynomials in $\F_p[x]$ in $\tilde O(n^{1.5})$ time. Their methods involve yet another related problem called Modular composition: given $f,g,h\in R[x]$ of degree $n$, compute $f(g(x))\mod h(x)$.
\section{Review of FT-based Multiplication}
Here we review the efficient multiplication algorithm based on the Fourier Transform (FT), and we explore what assumptions need to be placed on the ring $R$ to allow us to run this algorithm.
The basic framework for the interpolation-based polynomial multiplication algorithm is given as follows. Suppose that $f,g\in R[x]$ with $\deg f + \deg g < n$.
\begin{itemize}
\item Step 1 (Multipoint Evaluation). Pick $\alpha_0,\ldots,\alpha_{n-1}\in R$, and compute $f(\alpha_0),\ldots,f(\alpha_{n-1})$ and $g(\alpha_0),\ldots,g(\alpha_{n-1})$.
\item Step 2 (Multiplication in $R$). Compute the $n$ products $f(\alpha_i)\cdot g(\alpha_i)$ in $R$. This takes $n$ general multiplications.
\item Step 3 (Interpolation). Compute $h = f\cdot g$ as the\footnote{Any such algorithm needs to come with a proof that this interpolation problem is uniquely solvable. This comes automatically if $R$ is an integral domain, but we do not make this assumption.} polynomial of degree $\le n-1$ such that $h(\alpha_i) = f(\alpha_i)\cdot g(\alpha_i)$ for $0\le i\le n-1$.
\end{itemize}
The FT-based method makes this algorithm efficient by choosing special elements $\alpha_0,\ldots,\alpha_{n-1}$ that enable Steps~1 and~3 to be accomplished efficiently (and uniquely, for Step 3). Specifically, it chooses $\alpha_i=\omega^{i}$ where $\omega\in R$ is a \emph{primitive $n$th root of unity}:
\begin{definition}
An element $\omega\in R$ is an \emph{$n$th root of unity} if $\omega^n=1$. It is \emph{primitive} if $\omega^i\ne1$ for all $1\le i\le n-1$, or equivalently, if $\omega^d\ne1$ for all proper divisors $d$ of $n$.
\end{definition}
For the FT multiplication algorithm, we will assume $n=2^m$ is a power of $2$, $\deg f,\deg g