\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{4}{September 21, 2005}{Madhu Sudan}{Karola M\'esz\'aros} %%%% body goes in here %%%% \begin{center} \begin{Large} Membership algorithm for the permutation group \end{Large}\end{center} In the last lecture we only sketched the proof of Gauss's lemma. \vspace{0.1in} \textbf{Exercise 1.} Prove Gauss's lemma rigorously. \vspace{0.1in} The problem we are considering today is as follows: given a group $G$, subgroup of the symmetric group $S_n$, and an element $\pi \in S_n$, we would like to know whether $\pi$ belongs to $G$. In order to ask this question we must have a way to represent the group $G$, and the most natural way to do so is by giving a set $S=\{\pi_1, \ldots, \pi_l\}$ such that $\pi_i \in S_n$ for all $i \in [l]$, and $G=$, generated by the set $S$. Moreover, we represent every permutation $\pi$ by specifying the image of any $k\in [n]$ under $\pi$ (given such a representation we can also easily verify if it is really a permutation). Back to our original question of whether $\pi$ is in $G$, one way to show that $\pi$ is in $G$ is to write $\pi$ as a product of elements in $S$. However, as it turns out this is not a very efficient way, since: \vspace{0.1in} \textbf{Exercise 2.} Given $G \subset S_n$, generated by less than or equal to $n$ elements, there is a permutation $\pi \in G$ such that the shortest product of its generators representing $\pi$ is exponential in $n$. \vspace{0.1in} \textbf{Exercise 3.} Express the towers of Hanoi as a permutation group problem. \vspace{0.1in} Since we saw that if $G$ is given by just any set of generators $S$ it won't be efficient to look for a representation of elements as product of the given generators, we will shortly introduce the notion of a strong generating set of $G$. The idea is that we would like to have a (relatively) short representation for any $\pi$, and by adding some special elements to our set of generators we might be able to do this (start with the empty set and successively add suitable generators). \vspace{0.1in} \textbf{Definition.} $T \subset G$ is a \textit{strong generating set} (SGS) of $G$ if for every $j=G$. \vspace{0.1in} \textit{Proof.} (a) It is clear that any group $G$ has a SGS since $G$ itself is a SGS. Moreover, we see from the definition of SGS that for every $j, k, j \neq k$ there is at most one generator in $T$. This, $|T|$ is less than or equal to $n$ choose $2$. (b) To prove this we introduce the following concept. For $T\subset G$ define $\bar{T}$ as the elements obtained by greedy (right-to-left) movements using elements of $T$. See the illustration: \begin{center} \epsfbox{greedy.eps} \end{center} \vspace{0.1in} \textbf{Definition.} For every permutation $\sigma \in S_n$, let $k(\sigma)$ be the largest $k$ such that $\sigma(k) \neq k$. Then, for a SGS $T$ of $G$ we define $\bar{T}=\{\sigma_1\sigma_2 \dots \sigma_t |\sigma_1,\sigma_2, \ldots, \sigma_t \in G \}$. \begin{center} \epsfbox{k.eps} \end{center} It is clear that if $T \subset G$ then $\bar{T} \subset \subset G$. If $T$ is a SGS for $G$ then $G \subset \bar{T}$. Now, returning to our original problem of whether or not $\pi$ belongs to $G$, we can give the following algorithm: \vspace{0.1in} MEM-WITH-SGS($\pi, G, T$) // Does the group $G$ with SGS $T$ conain $\pi$? let $k=k(\pi)$ let $j={\pi}^{-1}(k)$ let $\sigma_t \in T$ such that $\sigma_t(j)=k, k(\sigma_t)=k$ let $\sigma_1,\sigma_2, \dots, \sigma_{t-1}$ generate $\pi{\sigma_k}^{-1}$ in $\bar{T}$ Output($\sigma_1,\sigma_2, \dots, \sigma_t$) \vspace{0.1in} Note that this algorithm also shows $G \subset \bar{T}$. For a proof see Professor Sudan's notes. Since the above algorithm is very efficient, we see that if we had a SGS for $G$ then we could easily tell whether $\pi$ belongs to $G$ or not. Thus, given $G$ with some set of generators $S$ we will construct a SGS. Once we do this, we solve our problem of deciding $\pi \in G$. The idea for building a SGS for $T$ is to start with the empty set and successively add in suitable elements, where suitable means that we will get a SGS at the end. Basically while there are elements that are not in $\bar{T}$ but are in $$, we will add some suitable $\sigma$ to $T$. Note that there is a big difference in the notion of $$ and $\bar{T}$ in that in $\bar{T}$ we can only ``jugle right to left''. Indeed, if in the illustration below $\sigma_2 \in T \cup S$ is the upper permutation and $\sigma_1 \in T \cup S$ the lower one, then we can tell that $\sigma_1\sigma_2 \in $, whereas it is not sure that $\sigma_1\sigma_2$ is in $\bar{T}$. \begin{center} \epsfbox{sigma.eps} \end{center} We can obtain a SGS for $G$ is by the followong procedure. Set $T=\emptyset$ at the beginning, then: \vspace{0.1in} ADD-ELEM($S, T, \sigma)$ if there is $\tau \in T$ such that $k(\tau)=k(\sigma)=k$ and $j={\sigma}^{-1}(k)={\tau}^{-1}(k)$ then ADD-ELEM($S, T, \sigma {\tau}^{-1}$) else add $\sigma$ to $T$. See illustration for an explanation of the algorithm: \begin{center} \epsfbox{tau.eps} \end{center} \textbf{Lemma.} If (1) $T \subset $, (2) $S \subset \bar{T}$, (3) for every $\sigma_1, \sigma_2 \in T$, $\sigma_1\sigma_2 \in \bar{T}$, then $T$ is a SGS for $$. For a careful proof take a look at Professor Sudan's notes. An idea here how to prove this: Part 1. It follows from (1), (2), (3), that $\subset \bar{T}$. $\bar{T}$ closed under multiplication; use subtle induction. Part 2. Using above we claim that $T$ is a SGS for $$. Given $\pi \in $, $k(\pi)=k, \pi(j)=k$, we need to show that there exists $\pi' \in T$ such that $k(\pi')=k, \pi'(j)=k$. If $\pi=\pi_1\pi_2\dots \pi_l$, with $\pi_1,\pi_2, l\dots, \pi_l \in T$ then $\pi_l$ satisfies the condition. \end{document}