\documentclass[12pt]{report}

\textheight 22cm
\textwidth 15.5cm
\oddsidemargin 0pt\evensidemargin 0pt
%\oddsidemargin 14pt\evensidemargin 0pt
%\topmargin -40pt
\topmargin-30pt
%\bottommargin0pt
\def\baselinestretch{1.1}
%\addtolength{\parskip}{1ex}
\jot=.5ex
%\parskip = 0.02in


\setlength\arraycolsep{2pt}



\usepackage{amssymb}
\usepackage{amsmath,bm}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsfonts}         
\usepackage{fancybox}   

%\usepackage[numbers]{natbib}

\usepackage{enumitem}

\usepackage{slashed}




\usepackage[usenames,dvipsnames]{xcolor}%http://en.wikibooks.org/wiki/LaTeX/Colors

\definecolor{darkgreen}{rgb}{0,0.4,0}
\definecolor{darkred}{rgb}{0.4,0,0}
\definecolor{darkblue}{rgb}{0,0,0.4}
\definecolor{lightblue}{rgb}{.6,.6,0.9}
\newcommand{\cobl}{\color{darkblue}}

\newcommand{\cor}{\color{red}}
\newcommand{\cog}{\color{darkgreen}}
\newcommand{\cob}{\color{black}}

\definecolor{uglybrown}{rgb}{0.8,  0.7,  0.5}

\def\ii{{\bf i}}
\def\Ione{\mathbb{I}}
\def\UU{{\bf U}}
\def\HH{{\bf H}}
\def\pp{{\bf p}}
\def\aa{{\bf a}}
\def\qq{{\bf q}}
\def\eps{\epsilon}
\def\half{{1\over 2}}
\def\Tr{{{\rm Tr~ }}}
\def\tr{{\rm tr}}
\def\Re{{\rm Re\hskip0.1em}}
\def\Im{{\rm Im\hskip0.1em}}
\def\ppi{\boldsymbol{\pi}}
\def\pphi{\boldsymbol{\phi}}
%\def\pphi{\phi}
\def\grad{\vec \nabla}
\def\vB{\vec B}
\def\vE{\vec E}
\def\vA{\vec A}
\def\vAA{ \vec{\bf A}}
\def\vEE{{{\vec {\bf E}}}}
\def\vBB{{\vec {\bf B}}}

\def\CL{{\cal L}}
\def\CO{{\cal O}}

\def\IZ{\mathbb{Z}}
\def\IR{\mathbb{R}}
\def\eg{{\it e.g.}~}
\def\ie{{\it i.e.}~}
\def\up{\uparrow}
\def\down{\downarrow}


\def\bra#1{\left\langle#1\right|}
\def\ket#1{\left|#1\right\rangle}
\def\bbra#1{{\langle\langle}#1|}
\def\kket#1{|#1\rangle\rangle}
\def\vev#1{\left\langle{#1}\right\rangle}

\def\ketbra#1#2{ | #1 \rangle\hskip-2pt\langle #2|}



\def\be{\begin{equation}}
\def\ee{\end{equation}}
\def\({\left(}
\def\){\right)}

%%                              TABLEAUX.TEX
%%      This  macro file is for producing a ``Young Tableau'' which is
%%      an array of little squares sometimes used in mathematical physics.
%%      For instance, the command $\tableau{6 3 2}$ will produce a tableau
%%      with 6 squares in the top row, 3 in the next, and 2 in the last.
%%                                  OOOOOO
%%      This tableau will look like OOO    but made of squares instead of O's.
%%                                  OO
%%      Any number of rows may be present, each having a nonzero number of
%%      squares.
%%
%%      A tableau is math mode material, so use $ or $$ to enclose it.
%%
%%      The size and line-thickness of the little boxes are controlled by the
%%      dimension parameters --
%%              \tableauside=1.0ex              %(size)
%%              \tableaurule=0.4pt              %(line-thickness)
%%      Change them if you want.
%%
%%                                                      -- Doug Eardley 9/19/8%%
%%
\newdimen\tableauside\tableauside=1.0ex
\newdimen\tableaurule\tableaurule=0.4pt
\newdimen\tableaustep
\def\phantomhrule#1{\hbox{\vbox to0pt{\hrule height\tableaurule width#1\vss}}}
\def\phantomvrule#1{\vbox{\hbox to0pt{\vrule width\tableaurule height#1\hss}}}
\def\sqr{\vbox{%
  \phantomhrule\tableaustep
  \hbox{\phantomvrule\tableaustep\kern\tableaustep\phantomvrule\tableaustep}%
  \hbox{\vbox{\phantomhrule\tableauside}\kern-\tableaurule}}}
\def\squares#1{\hbox{\count0=#1\noindent\loop\sqr
  \advance\count0 by-1 \ifnum\count0>0\repeat}}
\def\tableau#1{\vcenter{\offinterlineskip
  \tableaustep=\tableauside\advance\tableaustep by-\tableaurule
  \kern\normallineskip\hbox
    {\kern\normallineskip\vbox
      {\gettableau#1 0 }%
     \kern\normallineskip\kern\tableaurule}%
  \kern\normallineskip\kern\tableaurule}}
\def\gettableau#1 {\ifnum#1=0\let\next=\null\else
  \squares{#1}\let\next=\gettableau\fi\next}

\tableauside=1.0ex
\tableaurule=0.4pt

%
             \tableauside=0.9ex              %(size)
             \tableaurule=0.8pt              %(line-thickness)
%



\newcommand{\bea}{\begin{eqnarray}}
\newcommand{\eea}{\end{eqnarray}}


\def\parfig#1#2{
\parbox{#1\textwidth}
{\includegraphics[width=#1\textwidth]{#2}}
}



%%from  Rudro Rana Biswas
\usepackage[pagebackref,  % this puts links to the page numbers where refs appear
%pdftex, 
bookmarks={false}, pdfauthor={John McGreevy}, pdftitle={Yay, physics!}]{hyperref}
\hypersetup{colorlinks=true, 
linkcolor=BrickRed, 
citecolor=Violet, 
filecolor=OliveGreen, 
urlcolor=RoyalBlue, 
filebordercolor={.8 .8 1}, 
urlbordercolor={.8 .8 0}}%http://en.wikibooks.org/wiki/LaTeX/Hyperlinks


%\usepackage{mathtools} % for inclusion arrow \xhookrightarrow{}


\renewcommand{\theequation}{\arabic{equation}}
\newif{\ifeq}           % defines a new condition @eq tested by the conditional \ifeq
\eqtrue                 % if uncommented, declares @eq to be true
%\eqfalse              % if uncommented, declares @eq to be false
%                                %
%                                % to use this, wrap text with the conditional, eg:
%                                %
%                                % \ifeq
%                                % SHOW THIS IFF \eqtrue HAS BEEN DECLARED
%                                % \fi
%
\def\answer#1
{
\ifeq
\textcolor{darkblue}{#1}
\fi
}
\begin{document}
\begin{center}

University of California at San Diego -- 
Department of Physics --
Prof.~John McGreevy

{\Large\bf  Physics 220 Symmetries Fall 2024}\\
{\Large\bf Assignment 2 \answer{--~~~ Solutions} }
\end{center}

Comment: this problem set contains many problems, but most of them are simple and many of them are bonus problems.    


\noindent
\hfill {\bf Due 3:30pm { Thursday, October 10, 2024}} 


\hrule




\begin{enumerate}

\item{\bf Brain-warmer.} What is the cycle structure
of the permutation
$(235)(245) $?  


\item {\bf Conjugacy classes of $S_n$.}
\begin{enumerate}
\item Write the following elements of $S_n$ in cycle notation:
$$\pi =  \begin{pmatrix} 1 & 2 & 3& 4 &5 \cr 2 & 3 & 1 &4 & 5 \end{pmatrix},~~
\sigma =  \begin{pmatrix} 1 & 2 & 3& 4 &5 \cr 2 & 1& 3 &4 & 5 \end{pmatrix}, ~~
\rho =  \begin{pmatrix} 1 & 2 & 3& 4 &5 \cr 2 & 3& 4 &1 & 5 \end{pmatrix}. $$



\item Check that the cycle structure is preserved by conjugation, {\it e.g.}~for
$ \pi^{-1} \sigma \pi$, $\pi^{-1} \rho \pi$.

\item Bonus problem: give a proof that this always works.



\end{enumerate}


\item{\bf Brain-warmer.} 
\begin{enumerate}
\item What group is this: $G = \vev{a,b|aba^{-1}b^{-1} = e}$?  




\item{} [Bonus problem] Find a space $X$ so that $\pi_1(X) = G$ above.






\end{enumerate}


\item {\bf Quaternions.} 

Decompose the quaternion group $Q_8$ into conjugacy classes.

\def\jj{{\bf j}}
\def\kk{{\bf k}}

\item {\bf Brain-warmer.} Check the relation $|G| = |Z(g)| |C(g)| $ 
for $g = (12)$ in $G=S_n$.
Here $Z(g)$ is the centralizer of $g$ (the set of elements of $G$ that commute with $g$)
and $C(g)$ is the conjugacy class of $g$ (by $|C(g)|$ I mean the number of elements in the conjugacy class).



\item{\bf A presentation of $A_4$.} Prove that the group $\vev{a,b|a^2=e, b^3=e, (ab)^3 = e}$ is isomorphic to $A_4$,
the group of even permutations of 4 objects,
$$A_4 = \{ e, (12)(34), (14)(23),(13)(24), (123), (132), (243), (234), (341), (314), (421), (412)\}.$$



\item{\bf Free groups are weird.} [Bonus problem] 
Show that the free group on two elements $\vev{a,b| }$ contains subgroups isomorphic to
the free group on any number of elements.




\item{\bf Counting elements of conjugacy classes of $S_k$.} 
Here is a cool trick, related to Polya enumeration,
for counting the number of elements in the conjugacy class of $S_k$ associated to a given Young diagram (cycle structure), $\lambda$.


\begin{enumerate}
\item{} [bonus problem]. Fill in the missing details of the following argument.

First, recall the object 
$ z(\sigma) \equiv z_1^{c_1(\sigma)} z_2^{c_2(\sigma)} \cdots $,
where $c_i(\sigma)$ is the number of cycles of length $i$ in the permutation $\sigma$.  
This is a conjugation-invariant weight over which we can sum:
$$ Z_{G}(z_1, z_2, \cdots) \equiv \sum_{\sigma \in S_k} z(\sigma).$$
This is (proportional to) the object we called the cycle index in our discussion of Polya enumeration (for the case with $G = S_k$).

Now consider the case where $|X| = k$ and $G = S_k$, the whole permutation group on the $k$ objects,
and we'll take $n$ colors ({\it i.e.}~an $n$-state Potts model on $X$).
Weight a coloring with $l_i$ objects of color $i$ with a factor of $W = u_1^{l_1} u_2^{l_2} \cdots $.
Polya's enumeration theorem says that the partition sum is then
\begin{align} \sum_{\text{orbits $O$}}W(O)  & = Z_{S_k}\(z_1 = u_1 + u_2 + \cdots, z_2 = u_1^2 + u_2^2 + \cdots, \cdots  \) 
\\ & = \sum_{l_1, l_2, \cdots l_n} \(\text{$\#$ of orbits with $l_1$ 1s, $l_2$ 2s...} \) u_1^{l_1}u_2^{l_2} \cdots 
\end{align}
What is this number of orbits?  Because we are modding out by the whole permutation group,
an orbit is entirely determined by specifying the number of each color.  So this number is only ever 1 or 0.  

To avoid the cases where it's zero, here's the final trick, familiar from statistical mechanics as the grand canonical ensemble: sum over $k$ (!).  Let
$$P(t, u_1, u_2, \cdots)\equiv \sum_{k=1}^\infty t^k  \sum_{\text{orbits $O$ of $S_k$}}W(O) .$$
On the one hand, this is
$$P(t, u_1, u_2, \cdots) = \sum_k t^k Z_{S_k} \(z_1 = u_1 + u_2 + \cdots, z_2 = u_1^2 + u_2^2 + \cdots, \cdots  \) . $$
On the other hand, this is
\begin{align} 
P(t, u_1, u_2, \cdots) & =  \sum_k t^k \sum_{l_1, l_2, \cdots l_n} \(\text{$\#$ of orbits with $l_1$ 1s, $l_2$ 2s...} \) u_1^{l_1}u_2^{l_2} \cdots 
\\ & = \sum_{l_1=0}^\infty (tu_1)^{l_1}  \sum_{l_2=0}^\infty (tu_2)^{l_2 }\cdots 
\\ & = \exp \( z_1 t + z_2 t^2 /2 + z_3 t^3/ 3 + \cdots \) 
\end{align} 
where $ z_i \equiv u_1^i + u_2^i + \cdots $.

\end{enumerate}

So for example, to compute the sizes of the conjugacy classes of $S_7$, 
let $T  = z_1 t + z_2 t^2/2 + z_3 t^3/3 + \cdots $ (you can stop at some number bigger than 7), 
and just find the coefficient of $t^7 $ in $e^T$.  
The result is a polynomial in the $z_i$ where the sum of the subscripts of each term adds up to 7. 
Each term is then associated with a Young diagram $\lambda$ and hence a conjugacy class.

\begin{enumerate}[resume]
\item What should you get if you set $z_i =1 $ for all $i$ and why?



\item 
Find the size of each conjugacy class of $S_4$ and $S_5$ using the result above.  (I recommend Mathematica's Series and Coefficient commands and the method described in the previous part of the problem.)
Check that your polynomial satisfies the check of the previous part.




\item{} Actually, there is a better way to learn the sizes of conjugacy classes of $S_n$.  
The order of the centralizer of $g$, $|Z_g|$, depends only on its conjugacy class.
The size of the conjugacy class is then $|C_g| = |G|/|Z_g|$ (by Lagrange's theorem).  
Show that the centralizer of an element $g$ of $S_n$ with $c_j$ cycles of length $j$ is 
\be\label{eq:size-of-centralizer} |Z_g| = \prod_j (c_j)! j^{c_j} .\ee
[Hint: Think about what elements that commute with a permutation of a given cycle structure can do, then count them.]
Write a formula for the number of elements of the conjugacy class $C_g$ and compare with your results from the previous part.


\end{enumerate}



\item {\bf Counting non-isomorphic graphs.} 
A graph with $k$ vertices can be regarded as a choice of $\{0,1\}$ for each of the $\begin{pmatrix} k \\ 2 \end{pmatrix} = { k (k-1)\over 2 }$ pairs of vertices ('1' means no edge and '1' means yes edge).
Two graphs are isomorphic if they are related by a relabelling of the vertices.
How many non-isomorphic graphs on 4 vertices are there?  
(The result of the previous problem will be useful.)


Construct the partition function which weights a graph by the number of edges, 
$Z(t) = \sum_\text{graphs, $\Gamma$} t^{\# \text{ of edges of }\Gamma} $ for $k=4$.

Bonus problem: answer the above questions for 5 vertices.



\item {\bf Quotients of the spherical model.}  
[This is a bonus problem, since (a) it uses some perhaps-unfamiliar notions from statistical mechanics and (b) I made it up from scratch.]
I mentioned that one application of the counting theorems we proved might be 
to statistical mechanics.  So far all the examples I've shown involve a finite number $N$ of degrees of freedom.  
But statistical mechanics is most interesting in the thermodynamic limit, $N\to\infty$, where there can be phase transitions, 
symmetry-breaking 
and well-defined phases.

\begin{enumerate}
\item A simple, solvable model with a phase transition at finite temperature is the following.
Place two-valued spins at each of $N$ sites (think of them as arranged in a circle) and couple them by all-to-all ferromagnetic Ising interactions, 
so the hamiltonian is
$$ H = - J \sum_{i, j=1 }^N s_i s_j $$
where each sum is over all $N$ spins.  
(The price of the solvability is that the model has no notion of locality.  
This will be an advantage for the purposes of this problem.)
We will set $J = {1\over N}$ so that there is a nice thermodynamic limit.
The model has a $\mathbb{Z}_2$ symmetry that takes $s_i \to - s_i$.

The canonical partition function is
$$ Z_0(\beta) = \sum_{\{s_i = \pm1\}} e^{ - \beta   H(s) }  = \sum_{\{s_i = \pm1\}} e^{  \beta   {1\over N } \sum_i s_i \sum_j s_j } . $$
Using the formula $ \int_{-\infty}^\infty dx e^{ - {Nx^2 \over 4 \beta} + x N M }  =  \sqrt{ 4 \pi \beta \over N} e^{ - \beta N M^2 } $
rewrite $Z_0(\beta)$ in a way so that the sum over spins factorizes.
Then argue that at large $N$ you can do the integral over $x$ by saddle point, and do so. 
Find the two phases (distinguished by whether or not the $\mathbb{Z}_2$ symmetry is spontaneously broken) by a graphical analysis of the saddle point equation.


\item In the model of the previous part, the phase transition arises by a competition between energy and entropy: 
it is energetically favorable for the spins to line up, but there are more configurations where the spins are not lined up,
so (minimizing $F = E - TS$) disorder wins at high temperature.  

Suppose we declare two spin configurations equivalent if they are related by a cyclic permutation of the spins (around the circle).
Such transformations form the group $\IZ_N$.  
(This process is called {\it gauging} this $\IZ_N$ symmetry.)
You might think this would favor the ordered phase, since 
the configurations where all spins point the same way is fixed by this transformation,
while the shift relates several disordered configurations, and therefore reduces their number.  

Using the not-Burnside lemma and its consequences, compute the partition function for the model 
with the same $H$ as above, but where configurations are orbits under $\IZ_N$.
This is easiest when $N$ is a prime number, so restrict to this case.
Explain what property of $\IZ_N$ for $N$ prime makes this case easier.



\item{} [A harder but really fun question, even more optional] Does the conclusion of the previous part change if instead of gauging $\IZ_N$, we gauge the whole $S_N$ interchanging all the spins?
[I have to admit that in the end, the not-Burnside lemma method is not the easiest way to solve this problem.
But it may be the most fun.]



\end{enumerate}
% Zee page 120



\end{enumerate}

\end{document}
