%% Testing
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Math 3094 Coxeter Groups, University of Connecticut, Fall 2018
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Anything after a percent sign is a comment.

% Necessary first line. \documentclass defines the type of document and some options (for example, try changing 12pt to 10pt.)
\documentclass[12pt]{exam}
\RequirePackage{amssymb, amsfonts, amsmath, latexsym, verbatim, xspace, setspace, mathrsfs}
\usepackage{amsmath,amsthm,amssymb,amsfonts, 
hyperref, color, graphicx}

% Here's where you edit the Class, Exam, Date, etc.
\newcommand{\class}{Math 3094 Coxeter Groups}
\newcommand{\term}{Fall 2018}
\newcommand{\examnum}{Testing Testing Final Exam}
\newcommand{\examdate}{December 10-16, 2018}
\newcommand{\timelimit}{10:30-11:20am or 12:30-1pm Friday}

\usepackage{url} % to use \url 
\usepackage{graphicx} % to use \includegraphics
\usepackage{enumerate} % to write \begin{enumerate}[a.]

% The next three lines are for writing comment boxes
\usepackage[colorinlistoftodos]{todonotes}
\newcommand{\emily}[1]{\todo[size=\small,color=yellow!30]{#1 \\ \hfill --- Emily}}
\newcommand{\Emily}[1]{\todo[size=\small,inline,color=blue!30]{#1 \\ \hfill --- Emily}}
\newcommand{\student}[1]{\todo[size=\small,color=green!30]{#1 \\ \hfill --- ReplaceWithYourName}}
\newcommand{\Student}[1]{\todo[size=\small,inline,color=cyan!30]{#1 \\ \hfill --- ReplaceWithYourName}}


\title{Math3094 Final Exam}
\author{replace with your name}
\date{}
\begin{document}

\maketitle

% These commands set up the running header on the top of the exam pages
\pagestyle{head}
\firstpageheader{\class}{\examnum\ - Page \thepage\ of \numpages}{\examdate}
\firstpageheadrule
\runningheader{\class}{\examnum\ - Page \thepage\ of \numpages}{\examdate}
\runningheadrule

% --------------------------------------------------------
%                         Start here
% --------------------------------------------------------

\begin{coverpages}
\section*{Instruction}
\Emily{remove this instruction section when you are done.}

\begin{itemize}

\item 
Deadline for sharing Overleaf file: Friday, December 14 (noon).

Note 1: If you wish to continue making changes to your Overleaf file (until Sunday, December 16 at noon), you may let me know, and I will wait to download your submission until then. 

Note 2: You may share with me your Overleaf file prior to Friday if you have questions about what you've done so far. 

\item 
You may and should use \cite{Hum90}, \cite{BB05}, class notes (including a copy of a classmate's class notes in case you missed some classes), previous homework and problem sets. 

\item 
You may use all theorems stated in class (except for problems where you are asked to prove something `from scratch'). 

\item  
You may use Sage and other technology to verify your permutation multiplication. Note that the order of composition of Sage (left to right) is opposite our convention (right to left). 

\item  
During this take-home exam, you may \emph{not} consult other resources (other textbooks, the internet, etc). You are not to discuss the exam with individuals other than the instructor until after the deadline. 

\item 
Two problems (pages) will be dropped, so please complete at least four out of six problems (pages). I will read your entire submission.

\item 
Note that the last item on each of problems 2-5 is the most challenging. Even if you do not complete this last item, you should still complete the earlier (computational) items for partial credit. 

\end{itemize}
\end{coverpages}

\newpage 
 
\begin{questions}

\question
Let $W$ be a finite reflection group and fix a simple system $\Delta$. 
Given $x\in W$, define the \emph{length} $\ell(x)$ of $x$ as in \cite[Sec 1.6, pg 12]{Hum90} (also stated in \cite[Sec 1.4, pg 15]{BB05}).

Define 
\begin{align*}
&d : W \times W \to [0,\infty) ~ \text{ by }\\ 
&d(x,y) := \ell(xy^{-1})
\end{align*}
Show that $d$ is a metric on $W$, that is, show that, for all $x,y,z \in W$, we have  
\begin{enumerate}[a.]
    \item $\ell(xy^{-1}) \geq 0$
    \item $\ell(xy^{-1})=0$ if and only if x=y
    \item $\ell(xy^{-1}) = \ell(yx^{-1})$
    \item $\ell(xz^{-1}) \leq \ell(xy^{-1}) + \ell(yz^{-1})$ (triangle inequality)
\end{enumerate}

\begin{proof}
Click here for a hint: 
%To show the triangle inequality, compare $\ell(a)$, $\ell(b)$, and $\ell(ab)$.
\end{proof}

\newpage

\question
\label{quest:lemma_inversion}
Consider the symmetric group $S_n$. 
For $i=1,2,\dots, n-1$, set 
\[
s_i :=(i,i+1)=\left(
\begin{array}{ccccccc}
1 & 2 & \dots & i & i+1 & \dots & n \\
1 & 2 & \dots & i+1 & i & \dots & n
\end{array}
\right) .
\]    

Given $x= 
    \left(
    \begin{array}{cccc}
    1 & 2 & \dots & n \\
    x(1) & x(2) & \dots & x(n)
    \end{array}
    \right) 
    \in S_n$, define \begin{align*}
    \text{INV}(x)&:=\{ \text{ pair } (i,j) : i<j, x(i) > x(j)\} ~ \text{ and let }\\
    \text{inv}(x)&:=\text{card INV}(x).    
    \end{align*}
 
\begin{enumerate}[a.]
    \item Choose a specific example of a permutation $x\in S_5$ where $\text{inv}(x)>0$. 
    Write $x$ in either window or 2-line notation. Compute $x \, s_2$ and write it in either window or 2-line notation. Write down $\text{INV}(x)$ and $\text{INV}(x \, s_2)$ and compare these two sets.
    
    \item Consider an arbitrary permutation $x= 
    \left(
    \begin{array}{cccc}
    1 & 2 & \dots & n \\
    x(1) & x(2) & \dots & x(n)
    \end{array}
    \right) 
    \in S_n$.
    Write $x \, s_i$ in window notation or 2-line notation.

\item Prove the following from scratch (don't use other theorems).

\begin{enumerate}[I.] 
\item If $x(i) < x(i+1)$, then $\text{inv}(x s_i) = \text{inv}(x) + 1$. 
\item If $x(i) > x(i+1)$, then $\text{inv}(x s_i) = \text{inv}(x) - 1$.
\end{enumerate}

\end{enumerate}

\newpage

\question 
\label{quest:length_equals_inversion_number}
Consider the symmetric group $W=S_n$. As in \cite[Sec 2.10, pg 41]{Hum90}, fix the simple system $\Delta = \{ \alpha_1 = \epsilon_1 - \epsilon_2, \alpha_2 = \epsilon_2 - \epsilon_3, \dots, \alpha_{n-1} = \epsilon_{n-1} - \epsilon_n\}$ which corresponds to the set of simple transpositions $S=\{s_1= (1,2), s_2=(2,3), \dots, s_{n-1}=(n-1,n) \}$. 

Given $x\in S_n$, define the \emph{length} $\ell(x)$ of $x$ as in \cite[Sec 1.6, pg 12]{Hum90} (or \cite[Sec 1.4, pg 15]{BB05}).

Show that $\ell(x)=\text{inv}(x)$ for all $x \in S_n$, where $\text{inv}(x)$ is defined in Problem \ref{quest:lemma_inversion}.

\begin{proof}
Hint 1: You may cite Problem \ref{quest:lemma_inversion} even if you omit it.  

Click here for Hint 2:
%You may want to use induction. For example, you may follow the proof on \cite[Prop 1.5.2, pg 20-21]{BB05}. However, their explanation is much too short. Write at least twice as much. Replace the phrase `clearly holds' with a detailed explanation. 

\end{proof}

\newpage

\question
\label{quest:longest_element}

Keep the same setup as in Problem \ref{quest:length_equals_inversion_number}. 
The positive system corresponding to $\Delta$ is  
$\Pi:=\{ \epsilon_i - \epsilon_j : 1\leq i<j \leq n  \}$ 
which corresponds to the set of transpositions $\{ (i,j) \in S_n : 1 \leq i < j \leq n \}$. 
Note that $\text{card }\Pi=n(n-1)/2$.

Let $w_0$ denote the unique element which sends $\Pi$ to $-\Pi$, see \cite[Sec 1.8, pg 15-16]{Hum90}. Since $\ell(w_0) = \text{card } \{ \text{positive roots sent to negative roots by } w_0 \}$ (due to \cite[Corollary 1.7, pg 14]{Hum90}), we have $\ell(w_0)= \text{card }\Pi=n(n-1)/2$.

By Problem \ref{quest:length_equals_inversion_number}, we have $\text{inv}(w_0)=\ell(w_0)= n(n-1)/2$. 
Since $\text{card }\{ (i,j) : 1 \leq i < j \leq n \}=n(n-1)/2$, we must have 
 $\text{INV}(w_0) = \{ \text{ pair } (i,j) : 1 \leq i < j \leq n \}$. So $w_0(1) > w_0(2) > \dots > w_0(n)$, and hence  
\[w_0:=
    \left(
    \begin{array}{ccccc}
    1 & 2 & \dots & n-1 & n \\
    n & n-1 & \dots & 2 & 1
    \end{array}
    \right).
    \]


\begin{enumerate}[a.]
    \item (Optional)  If you haven't already done so in this exam, prove the following.
    
    \noindent 
    If $x(i) < x(i+1)$, then $(i,i+1) \notin \text{INV}(x)$ and $(i,i+1) \in \text{INV}(x s_i)$.\\
    If $x(i) > x(i+1)$, then $(i,i+1) \in \text{INV}(x)$ and $(i,i+1) \notin \text{INV}(x s_i)$.
    \begin{proof}
    
    \end{proof}
    
    \item Write down $w_0 \, x \, s_i$ in either window or $2$-line notation. Click here for hints:
    
    %Hint: You've already written down $x \, s_i$ in Problem \ref{quest:lemma_inversion}. \\ Hint: $w_0(k)=n+1 - k$ for $k\in \{1,2,\dots, n\}$.
    
    \item \label{itm:lemma_INV_w0x}  Prove the following.
    \begin{enumerate}[I.]    
    
    \item If $x(i) < x(i+1)$, then 
    \\
    $(i,i+1) \in \text{INV}(w_0 \, x)$ ~ and ~ $(i,i+1) \notin \text{INV}(w_0 \, x \, s_i) $. 
    
    \item If $x(i) > x(i+1)$, then 
    \\
    $(i,i+1) \notin \text{INV}(w_0 \, x)$ ~ and ~ $(i,i+1)  \in \text{INV}(w_0 \, x \, s_i)$.
    \end{enumerate}
    
    \begin{proof}
    Click here for a hint: 
    %If $x(i) < x(i+1)$, then \[w_0 x(i) = n+1-x(i) > n+1-x(i+1) = w_0 x(i+1).\]
    \end{proof}
\end{enumerate}
    
\newpage    
    
\question
Keep the same setup as Problem \ref{quest:longest_element}. 
Let 
\begin{align*}
    \text{INV}^C(x):&=\{ (i,j): 1 \leq i<j \leq n, (i,j) \notin \text{INV}(x)\} \\ 
    &= \{ (i,j): 1 \leq i < j \leq n \} ~ \backslash ~ \text{INV}(x)
\end{align*} 
denote the `complement' of $\text{INV}(x)$.
Note that card $\text{INV}^C(x) = \ell(w_0)-$inv$(x) = n(n-1)/2 -$inv$(x)$. 
    
\begin{enumerate}[a.]
    \item 
    In window notation, let $x:=[2143]$ (length 2) and $y:=[3412]$ (length 4) in $S_4$. Compute $\text{INV}(x)$, $\text{INV}^C(x)$ and $\text{INV}(y)$, and verify that $\text{INV}^C(x)=\text{INV}(y)$. (Note that $2+4=6=4(3)/2=n(n-1)/2=\ell(w_0)$. Use Figure \ref{fig:weak_order_S4} to guess a pattern.) 
    
    \item
    Let $x:=[4123]$ (length 3). Compute $\text{INV}(x)$ and  $\text{INV}^C(x)$. Find $y\in S_n$ (length 3) and such that $\text{INV}^C(x)=\text{INV}(y)$. (Use Figure \ref{fig:weak_order_S4} to guess a pattern.)
    
    \item 
    Let $x:=[3241]$ (length 4). Compute $\text{INV}(x)$ and  $\text{INV}^C(x)$. Find $y\in S_n$ (length 2) and such that $\text{INV}^C(x)=\text{INV}(y)$. (Use Figure \ref{fig:weak_order_S4} to guess a pattern.)
    
    \item 
    Show that if $x\in S_n$ then there exists $y\in S_n$ such that $\text{INV}^C(x)=\text{INV}(y)$. \\
    Note: the set equality implies that, if $\ell(x)=r$ then $\ell(y)=\ell(w_0) - r$. 
    
    Click here for hints: 
    %Let $x=s_{i_1} s_{i_2} \dots s_{i_r}$ be a reduced expression as a product of simple transpositions $S=\{ s_1=(1,2), s_2=(2,3), \dots, s_{n-1}=(n-1,n)\}$. Let $y=w_0 \, x = w_0 \, s_{i_1} s_{i_2} \dots s_{i_r}$. Use Problem \ref{quest:longest_element} part (\ref{itm:lemma_INV_w0x}) to show that $\text{INV}^C(x)=\text{INV}(y)$.
\end{enumerate}

\begin{figure}[ht]
    \centering
    \includegraphics[width=16cm]{weak_order_S4.pdf}
    \caption{Weak order of $S_4$ from \cite[Fig. 3.2, pg 67]{BB05}}
    \label{fig:weak_order_S4}
\end{figure}

\newpage

\question
Recall that the Coxeter group of type $H_3$ can be generated by elements $\{a,b,c\}$ with relations $(ab)^5=(bc)^3=(ac)^2=a^2=b^2=c^2=1$. 
See Figure \ref{fig:weak_order_H3}. 

 
 
 \begin{enumerate}[a.]
     \item 
 Label all the edges of the weak order of $H_3$, where $u$ and $v$ are connected by an edge labeled $s$ if and only if $u=v \, s$ (if and only if $v = u \, s$). In Figure \ref{fig:weak_order_H3}, I have started to label some edges. 

My suggestion would be to draw all the edges by hand then scan/photograph  it. Add your finished figure into your Overleaf document. If you have trouble adding a figure, please send me your figure and I will add it to your Overleaf document.

Note: This is not meant to take a lot of time. Let me know if you don't understand my examples and aren't sure how to write the labels quickly. 

\item Use your labeled figure to: \\
i.) write a reduced expression of the longest element $w_0$ of $H_3$, which is of length $15$ and located at the top of the graph.  \\
ii.) find a reduced expression that is a power of $5$, that is, write  $w_0=w^5$ for some reduced expression of an element $w$ of length $3$.    

\item Consider the three elements labeled $x$,  $y$, and $z$ appearing in Figure \ref{fig:weak_order_H3}. Exactly one of them is the product of the other two. Determine the corret identity (among the six possible identities, i.e. $xy=z$, $yx=z$, $xz=y$, etc.).

\end{enumerate}

\begin{figure}[ht]
    \centering
    \includegraphics[width=16.5cm]{weak_order_H3.pdf}
    \caption{Weak order of $H_3$ from \cite[Fig. 3.3, pg 68]{BB05}}
    \label{fig:weak_order_H3}
\end{figure}

\end{questions}

% Below is how you insert citation.
\bibliographystyle{alpha} 
\bibliography{citation}

\end{document}