\documentclass[10pt]{article}
\usepackage{amsfonts}
\usepackage{rotating}
\newtheorem{define}{Definition}

%\newcommand{\Z}{{\bf Z}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

\lecture{2}{February 13, 2012}{Madhu Sudan}{Zeyuan Allen Zhu}

\section{Administrivia}
\begin{itemize}\itemsep -1pt
\item Students signed them up on a piece of paper today. If you missed the first class, please subscribe to the course mailing list yourself.
\item Please sign-up for scribing by sending an email to Prof. Sudan. All students (including listeners) need to scribe at least once.
\item Lectures always start on time, so do not come late to the classroom.
\item Will have one or two problem sets.
\item Madhu will select topics beyond the course materials for students to present as course projects. That requires each student to spend 10 minutes to explain the work in class, and complete a write-up that can be useful for others. It is a casual and fun job, and encouraged to done in pairs.
\end{itemize}

\section{Membership Problem in Permutation Groups}
Instead of listing potential topics that we plan to cover in this course now, we start with a concrete example.
\begin{center}
How can we solve a cube?
\end{center}
\emph{(In class Prof. Sudan handed to the students a fancy cube that few of us have seen before, found in Prof. Erik Demaine's office.)}
This is an algorithmic challenge to us. We have this cubic object, and can do a few moves on it. Can we reach some given state from the beginning, and how? We now formalize a broader class of such problems in a purely mathematical way.

Suppose that we are given finite number of $n$ pieces and there are some basic moves allowed. In a traditional cube, there are $n=54$ pieces (stickers) and we can take for instance the top or side face and rotate.
We introduce now a few notions before we proceed:
\begin{itemize}\itemsep -1pt
\item $[n] := \{1,2,\dots,n\}$.
\item $S_n := \{\pi : [n] \to [n] : \pi\textrm{ is one-to-one}\}$.
\item $\langle S\rangle:=\{\textrm{group of permutations obtained by composing members of }S\}$.
\end{itemize}


Suppose that the operations allowed are permutations $\pi_1,\pi_2,\dots,\pi_k \in S_n$, and we can do any combination of them. Let $S=\{\pi_1,\pi_2,\dots,\pi_k\}$ and $\langle S \rangle$ is a subgroup of $S_n$. Given an arbitrary permutation $\pi \in S_n$, does $\pi \in \langle S \rangle$? Can we solve this problem efficiently?

\newcommand{\polylog}{\mathsf{polylog}}
\renewcommand{\poly}{\mathsf{poly}}
In general, we consider cases where $k=|S|=O(n)$ and we expect \emph{efficient} algorithms to run in time $\poly(n)$.\footnote{Typically even writing done a permutation requires $O(n)$ time. There are other ways to represent permutations in a more concise way, and thus one may also expect the existence of algorithms that runs in time $\polylog(n)$, though a little too ambitious.}
We note that it may take a very large number of compositions to generate $\langle S \rangle$. For instance, it is an exercise to given an example $S\subseteq S_n$ such that $\exists \sigma \in \langle S\rangle$ while
$$\min_l \{l\textrm{ s.t. }\sigma=s_1s_2\cdots s_l \wedge \forall i, s_i\in S\} = \exp(n^{1/10}) \enspace.$$
In order to overcome this, we need the idea of an arithmetic circuit. We will not use much of this notion today, but the definition is as follows:

\subsection{Arithmetic Circuit over Group}
(In the future we will also consider it over rings or fields.)

\begin{itemize} \itemsep -1pt
\item Input: $S\subseteq G$.
\item Circuit: $C=(t_1,t_2,\dots,t_m)$ a collection of group elements, such that for each $t_i$:
\begin{itemize} \itemsep -1pt
\item either $t_i \in S$,
\item or $t_i = t_j\cdot t_k$ such that $j,k < i$.
\end{itemize}
\item We say that $C$ computes $T$ if $T \subseteq \{t_1,t_2,\dots,t_m\}$.
\end{itemize}

\noindent In this language, our question can be formalized as:
\begin{itemize} \itemsep -1pt
\item Input: $n$, $S\subseteq S_n$, and a permutation $\pi \in S_n$.
\item Output: YES if there exists an arithmetic circuit computing $\{\pi\}$ using input $S$, or NO if there isn't any.
\end{itemize}

\noindent We remark here that such a question is general itself because:
\begin{fact}
Every finite group is a (subgroup of) permutation group.
\end{fact}
\begin{proof}
Given a finite group $G$ with $|G|=n$, we consider the following multiplication map:
\begin{center}
$g\in G$ is mapped to $\pi_g \in S_n$, where $\pi_g : G\to G$ by $\alpha \mapsto g\alpha$.
\end{center}
It satisfies that $\pi_a \pi_b = \pi_{ab}$, and every element is mapped to a permutation whose length is as large as the group itself.
\end{proof}

A big challenge in group theory is to ask that: is there a way to represent an element by not $n$ numbers but perhaps $\log n$ or $\polylog(n)$ numbers? For instance, can we solve the membership question without going through this intermediate permutation group for certain problems?

\subsection{The Sims Algorithm}
(Most of the materials are following a book \emph{Permutation Group Algorithms} by \'{A}kos Seress.)

Let us define $\mathcal{C}_{k,j} = \{ \pi | \pi(i)=i \forall i<k, \textrm{ and } \pi^{-1}(k)=j\} \subset S_n$, and notice that $\mathcal{C}_{k,j} \cap \mathcal{C}_{k',j'}=\emptyset$ as long as $(k,j)\neq (k',j')$. We always assume that $j>k$. Now, the entire space of permutation group $S_n$ is partitioned by such $\mathcal{C}$'s:
$$e \cup \bigcup_{1\leq k<j \leq n} \mathcal{C}_{k,j} = S_n \enspace.$$

We say that the $k$-value of a permutation $\pi$ is $k_0$ if $\pi \in \mathcal{C}_{k_0,j}$ for some $j>k_0$. We further define (and notice that $T$ can be any set, not necessarily a subgroup of $S_n$):
\begin{definition}
$ $
\begin{itemize}\itemsep -1pt
\item \emph{Minimal set}: $T$ is minimal if $|T \cap \mathcal{C}_{k,j}| \leq 1$ for all $k,j$.
\item \emph{Representative set}: $T\subseteq G$ is a representative set for $G=\langle S \rangle$, if $|T \cap \mathcal{C}_{k,j}| \geq 1 \Leftrightarrow |G \cap \mathcal{C}_{k,j}| \geq 1$ for all $k,j$.
\item \emph{Strong generating set (SGS)}: $T$ is an SGS for $G$ if $T$ is both minimal and representative for $G$.
\end{itemize}
\end{definition}
\begin{fact}
For any group $G$, there exists SGS $T$, and $|T|\leq \binom{n}{2}$.
\end{fact}

\subsection{Membership Testing Given SGS}
Given $\pi$ and suppose we want to check if $\pi \in G = \langle S \rangle$.
We have that $\pi \in \mathcal{C}_{k,j}$ is in some unique $\mathcal{C}_{k,j}$. If $T \cap \mathcal{C}_{k,j}=\emptyset$ we are done, because this implies $G \cap \mathcal{C}_{k,j}=\emptyset$ and thus it cannot be the case that $\pi \in \mathcal{C}_{k,j}$.

Otherwise, we can find some $\sigma \in T \cap \mathcal{C}_{k,j}$. So can apply $\sigma^{-1} \pi$ and verify if $\sigma^{-1} \pi \in G$. This verification suffices because: 1) $\sigma^{-1} \pi$ will have a strictly smaller $k$-value than $\pi$; 2) $\pi \in G$ if and only if $\sigma^{-1} \pi \in G$, as $\sigma$ is an element in $G$.


\subsection{Computing Strong Generating Set}
Let us start with a simple trial of computing SGS.
\begin{itemize}
\item Start with $T\leftarrow \emptyset$.
\item INSERT($\sigma,T$)
\begin{itemize}
\item If $\sigma$ is identity, we stop.
\item If $\sigma \in T$, we stop.
\item If $\sigma \in \mathcal{C}_{k,j}$ and $T\cap \mathcal{C}_{k,j}=\emptyset$, $T\leftarrow T\cup \{\sigma\}$.
\item If $\sigma \in \mathcal{C}_{k,j}$ and $T\cap \mathcal{C}_{k,j}=\{\tau\}$, INSERT($\tau^{-1}\sigma,T$).
\end{itemize}
\end{itemize}

\begin{definition}
Canonical product is the product of previously inserted elements whose $k$-values are increasing.
\end{definition}

It satisfies that if two canonical products of elements from minimal sets are identical, i.e., $\sigma_1\sigma_2\cdots\sigma_l=\tau_1\tau_2\cdots\tau_m$ while $\sigma_1,\dots,\sigma_l,\tau_1,\dots,\tau_m\in T$ and $T$ is a minimal set, then $l=m$ and for all $i$, $\sigma_i = \tau_i$.

\begin{definition}
$Closure(T) = \bar T = \{\textrm{canonical products of elements of T}\}$.
\end{definition}

In this language, what we have shown earlier regarding having an SGS we can test membership, is equivalent to:
\begin{center}
$T$ is an SGS $\Rightarrow$ $\bar{T} = G$.
\end{center}

\begin{fact}
INSERT($\sigma,T$) will make sure that $\sigma \in \bar{T}$ after the procedure.
\end{fact}
And this above fact suggests that we can insert all elements from $S$ into $T$ and this ensures that $S\subseteq \bar T$. This does not fully answer our question yet, since we still need to show that $\bar{T}$ is a subgroup of $S_n$ (i.e., closed under multiplications). Ideally, we can fix this by taking two elements from the closure $\bar{T}$ and try to insert it, but unfortunately there will be too many such elements in $\bar{T}$. So, instead we consider the following algorithm:

\vspace{5mm}
\noindent \textbf{Computing SGS $(n,S)$:}
\begin{itemize}
\item Start with $T\leftarrow \emptyset$.
\item While there exists $\sigma \in S$ or $\sigma \in T\cdot T$, such that INSERT($\sigma,T$) is a non-trivial operation (i.e., it changes $T$), do it.
\end{itemize}

This algorithm terminates in polynomial time because $T$ is a minimal set and has no more than $\binom{n}{2}$ permutations. Its correctness will be shown with the help of the next lemma:
\begin{lemma}\label{lemma:main}
If $T\cdot T\subseteq \bar{T}$, then $\bar{T}\cdot \bar{T} = \bar{T}$ forms a subgroup.
\end{lemma}
%If $T$ is minimal and $S\subseteq \bar{T}$, then
It is obvious that if the above lemma holds (i.e., $\bar{T}\cdot \bar{T} = \bar{T}$ is a subgroup), and we know that $\hat{T}$ contains $S$, it must be that $\bar{T}=\langle S \rangle$. To show that $T$ is an SGS, we only need to notice that for all $k,j$, such that $\langle S \rangle\cap \mathcal{C}_{k,j}\neq \emptyset$ $\Rightarrow$ $\bar{T}\cap \mathcal{C}_{k,j}\neq \emptyset$ $\Rightarrow$ $T\cap \mathcal{C}_{k,j}\neq \emptyset$, using the property of canonical products.

Therefore, the only thing left is to prove Lemma~\ref{lemma:main}.

\vspace{5mm}
\begin{proof}[of Lemma~\ref{lemma:main}]
We prove by induction.\footnote{The scribe today wants to point out here that this proof was not covered in class and written with the help from the course notes in 2005. However, in 2005 the $k$-value was defined in an opposite way which leads to a different inductive proof.}

Take two elements $\sigma, \tau \in \bar{T}$ and we want to show that $\sigma \tau \in \bar{T}$.
Assume that $\sigma=\sigma_1\cdots \sigma_l$ is the canonical representation with $\sigma_i\in T$ and $k(\sigma_i)<k(\sigma_{i+1})$. Here we use $k(\cdot)$ to represent the $k$-value of a permutation. Similarly we assume that $\tau=\tau_1\cdots \tau_m$. We prove by double induction on the decreasing of $k=k(\tau_1)$ and then on the increasing of $l$.

If $k=n$ this means $\tau=e$ is the identity permutation, and the claim trivially holds.

If $k<n$ and $k(\sigma_l)<k=k(\tau_1)$, then $\sigma_1\dots \sigma_l \tau_1\dots \tau_m$ is of the increasing $k$-value and thus in $\bar{T}$.

If $k<n$ but $k(\sigma_l)\geq k=k(\tau_1)$, then since $T\cdot T \subseteq \bar{T}$, we can write $\sigma_l \tau_1 = \alpha_1\cdots \alpha_p \in \bar{T}$ where $\alpha_i$'s are of increasing $k$-values.

\newcommand{\verteq}[0]{\begin{turn}{90} $=$\end{turn}}
\begin{equation}
\begin{array}{llrcl}
\sigma\tau & = & \sigma_1\cdots \sigma_{l-1}  &  \underline{\sigma_l \tau_1} &  \tau_2 \cdots \tau_m \\
           &   &                          &   \begin{turn}{90} = \end{turn}  & \\
           &   &                          & \alpha_1\alpha_2 \cdots \alpha_p & \\
           \\
           & = & \sigma_1\cdots \sigma_{l-1} & \alpha_1 \alpha' & \tau' 
\end{array}
\end{equation}
In fact, since $k(\sigma_l) \geq k$ and $k(\tau_1)=k$, we have that $k(\alpha_1) \geq k$ while all $k(\alpha_2), \dots, k(\alpha_p) > k$. If we define $\tau'=\tau_2 \cdots \tau_m$ while $\alpha' = \alpha_2 \cdots \alpha_p$, we have that by induction $\alpha'\tau' \in \bar{T}$ since $k(\tau_2)>k$. Furthermore, since $k(\alpha'\tau')>k$ (as both $k(\alpha'), k(\tau')>k$), we know $\alpha_1 \alpha' \tau' = \sigma_l \tau \in \bar{T}$. At last, having that $k(\sigma_l \cdot \tau) \geq k$, and by induction on $l$, we have that $\sigma\tau = (\sigma_1\cdots \sigma_{l-1}) (\sigma_l\tau) \in \bar{T}$. We conclude that $\bar{T}$ is closed under multiplication.
\end{proof}

\subsection{Other Works}
Babai and Codenotti (FOCS'08) have also been looking at other representations of groups. For instance, for subsets of matrices $\mathbb{F}_q^{n\times n}$. They achieved efficient algorithms except for two caveats: one needs to be able to factor certain numbers such as $q-1$ or $q^5-1$, and do discrete log over $\mathbb{F}_q$.




\section{Contents of the course}
\begin{itemize}
\item Berlekamp's algorithm for factoring univariate polynomials over $\mathbb{F}_p$ for large prime $p$. This algorithm was introduced in 1972 and is randomized. It remains an open question to factor even simple polynomials like $x^2 - a$ in deterministic polynomial time (i.e., $\polylog(p)$).
\item Finite fields.
\item (Factoring) multivariate polynomials.
\item Factorization over rational polynomials (LLL).
\item Techniques to solve multivariate systems of polynomial equations.
\item Two different models for algebraic computations.
\begin{itemize} \itemsep -1pt
\item Blum-Shub-Smale model of computing. A hard problem under this model is given polynomials $P_1,\dots,P_m\in \mathbb{C}[x_1,\dots,x_n]$ with coefficients being 0-1's, and to check if they have a common zero.
\item Valiant model of computing. A hard problem under this model is the permanent of matrices.
\end{itemize}
\end{itemize}

\section{Assignment}
Email madhu@mit.edu with your favorite and surprising algorithm and explain why. Due by the end of this week.


\end{document}

