Home > Discussions > Algebra

Note: this page uses MathJax for formatting, so may take a few seconds to load.

MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
**Mathematica Programs:**

p[0]=1;

Do[

p[n]=0;

k=1;

While[n-k (3k-1)/2>=0,p[n]=p[n]+p[n-k (3k-1)/2](-1)^(k+1);k++];

k=1;

While[n-k (3k+1)/2>=0,p[n]=p[n]+p[n-k (3k+1)/2](-1)^(k+1);k++],

{n,1,100}]

Table[p[n],{n,0,50}]

{1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,

8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226}

a[0]=2;

Do[

a[n]=If[IntegerQ[Sqrt[n/2]],3(-1)^Sqrt[n/2],0];

k=1;

While[n-k (3k-1)/2>=0,a[n]=a[n]+a[n-k (3k-1)/2](-1)^(k+1);k++];

k=1;

While[n-k (3k+1)/2>=0,a[n]=a[n]+a[n-k (3k+1)/2](-1)^(k+1);k++], {n,1,100}]

Table[a[n],{n,0,50}]

{2,2,1,3,4,5,7,9,14,18,24,31,43,55,72,94,123,156,200,254,324,408,513,641,804,997,1236,1526,1883,2308,2829,3451,4209,5109,6194,

7485,9038,10871,13063,15654,18738,22365,26665,31716,37682,44669,52887,62494,73767,86902,102260}

**References:**

G. E. Andrews and K. Eriksson ,*Integer Partitions*. Cambridge University Press, Cambridge, 2004.

Note: this page uses MathJax for formatting, so may take a few seconds to load.

Conjugation

Conjugation consists of an operation followed by a second operation, then followed by the inverse of the first operation. In symbols, the conjugate of $g$ by $h$ is $hgh^{-1}$. (We read the operations from left to right.) A typical setting is where $g$ and $h$ are elements of a group.

A straightforward example of conjugation is the calculation of a reflection matrix in $\mathbf{R}^2$. This is a matrix that reflects with respect to the line passing through the origin at an angle $\theta$ measured counter-clockwise from the positive $x$-axis. The rotation matrix, which rotates every vector around the origin by an angle $\theta$, is \[ R_{\theta}=\left[\begin{array}{cc}\cos \theta & -\sin \theta\\\sin \theta & \cos \theta\end{array}\right]. \] The matrix that reflects with respect to the $x$-axis is \[ \left[\begin{array}{cc} 1 & 0\\ 0 & -1 \end{array}\right]. \] Thus, the general reflction matrix is \[ M=R_{\theta}\left[\begin{array}{cc}1 & 0\\0 & -1\end{array}\right]R_{-\theta}= \left[\begin{array}{cc}\cos^2 \theta - \sin^2 \theta & 2\sin \theta \cos\theta\\2\sin \theta \cos \theta & \sin^2 \theta -\cos^2 \theta\end{array}\right]. \] ($R_{-\theta}$ is the inverse of $R_{\theta}$.)

In general, given an element $g$ in a group $G$, its *conjugacy class* is the set
\[
\text{ccl}(g)=\{xgx^{-1} \colon x \in G\}.
\]

The *centralizer subgroup* $G_g$ is the set of all elements $x$ that fix $g$ upon conjugation:
\[
G_g=\{x \in G \colon xgx^{-1}=g\}.
\]
The size of a conjugacy class is the size of the group divided by the size of the centralizer subgroup:
\[
|\text{ccl}(g)|=\frac{|G|}{|G_g|}.
\]
This follows from the fact that the conjugacy classes are in bijective correspondence with the cosets of the centralizer subgroup.

A subgroup $N$ of a group $G$ is *normal* if $N$ contains the conjugacy classes of all its elements. That is, for every
$g \in N$ and $x \in G$, we have $xgx^{-1} \in N$. If $N$ is a normal subgroup of $G$, then its cosets form a group called
the *quotient group*.

A group is *simple* if its only normal subgroups are itself and the identity group. Groups of prime order are simple.
The smallest simple group of non-prime order has order $60$. We will soon see what group it is.

We will investigate conjugacy in two types of groups: symmetric groups and alternating groups.

The *symmetric group* $S_n$ on $n$ elements consists of all permutations of the $n$ elements, under composition.
The conjugacy class of an element $g$ in the symmetric group is the set of all permutations with the same cycle structure as $g$,
that is, the same lengths of cycles. The reason is that conjugacy relabels the elements of a permutation. Consider the effect
of $\pi \sigma \pi^{-1}$ on a permutation.
We have
\[
\pi \sigma \pi^{-1} (\pi(i))=\pi(\sigma(\pi(i)).
\]
Thus, $\pi \sigma \pi^{-1}$ maps $\pi(i)$ to $\pi(\sigma(\pi(i))$. This means that we can rewrite the elements of $\sigma$,
replacing $i$ by $\pi(i)$.

The conjugacy classes in $S_4$, for example, correspond to partitions of type $1+1+1+1$ (one element), $2+1+1$ (six elements), $2+2$ (three elements), $3+1$ (eight elements), and $4$ (six elements).

The *alternating group* $A_n$ on $n$ elements is the subgroup of the symmetric group on $n$ elements consisting of all $n!/2$ even
permutations (an even permutations is one composed of an even number of transpositions). The conjugacy class of an element $g$
in the alternating group is the same as the conjugacy class of $g$ in the symmetric group, except when $g$ is composed of cycles of
distinct odd lengths, in which case the conjugacy class splits into two equal size classes.

To prove this, we must determine when $\pi \in A_n$ is centralized by an odd permutation. For then both $|G|$ and $|G_g|$ are reduced by a factor of $2$, keeping $|\text{ccl}(g)|$ the same. Otherwise, $|G|$ is reduced by a factor of $2$ and $|G_g|$ is unchanged, reducing $|\text{ccl}(g)|$ by a factor of $2$.

If $\pi$ has a cycle of even length, then $\pi$ is centralized by this cycle, which is an odd permutation. If $\pi$ has two odd cycles of the same length, then $\pi$ is centralized by a permutation that exchanges the elements of these two cycles, which is an odd permutation.

If $\pi$ is a product of odd cycles of distinct lengths, then an element centralizing $\pi$ must map each cycle to itself. An element in such a cycle may be mapped to any element in the same cycle. Once that choice is made, the images of all other elements in the cycle are determined. Hence, a centralizer of $\pi$ is a product of cycles of odd length, and thus is an even permutation.

Let's see how this works for $A_4$. The conjugacy classes correspond to elements of type $1+1+1+1$ (one element), $2+2$ (three elements), and $3+1$ (eight elements). The sole element in the class $1+1+1+1$ is the identity element, which is centralized by each odd permutation in $S_4$. A typical element in the class $2+2$ is $(12)(34)$, and this is centralized by the odd permutation $(12)$. Thus, this class does not split in $A_4$. The final set of elements corresponds to $3+1$, which has distinct odd summands. Hence, the class in $S_4$ splits into two equal size classes in $A_4$. A typical element is $(1)(234)$. There is no way to conjugate this element to $(1)(243)$ by an element of $A_4$.

The characterization of the conjugacy classes of alternating groups yields a proof that $A_5$ (the rigid symmetry group of the regular dodecahedron), of order $60$, is simple. By contrast, the symmetric group $S_4$ (the symmetry group of the cube) is not simple. The subgroup $V$ (Klein's Four-Group) is a nontrivial normal subgroup. It is the group of $180^{\circ}$ rotations about axes through opposite faces of the cube. Another nontrivial normal subgroup is $A_4$. It is the group of symmetries of the cube that are also symmetries of a fixed inscribed tetrahedron. A normal subgroup is a union of conjugacy classes. The conjugacy classes corresponding to $1+1+1+1$ and $2+2$ comprise $V$, while the conjugacy classes corresponding to $1+1+1+1$, $2+2$, and $3+1$ comprise $A_4$.

It is easy to see that the symmetry group of the dodecahedron has $60$ elements. We can place the solid on any of its $12$ faces, and then rotate this face to any of five positions. This accounts for the $60$ symmetries.

Now we can establish that the symmetry group of the dodecahedron is $A_5$. It is a subgroup of $S_5$, since it permutes a set of five cubes inscribed in the dodecahedron. The edges of the cubes are diagonals of the pentagonal faces, as in the diagram below. The five diagonals of a fixed pentagon locate the five cubes.

A subgroup of index $2$ is always normal, because then a left coset equals a right coset. Since the group of symmetries has order $60$, it must be $A_5$ (as this is the unique subgroup of $S_5$ of index $2$).

The cycle types of elements of $A_5$ are $1+1+1+1+1$ (one element), $2+2+1$ (fifteen elements), $3+1+1$ (twenty elements), and $5$ (twenty-four elements). Only the last of these has distinct odd lengths, yielding two conjugacy classes of twelve elements each. There is no way to combine $1$ (the class size of the identity) with a subset of the other class sizes ($15$, $20$, $12$, $12$) to make a proper divisor of $60$. Therefore, $A_5$ is simple.

Let $p(n)$ be the number of partitions of $n$. The number of conjugacy classes in the symmetric group is $p(n)$, since partitions correspond to conjugacy classes. The number of conjugacy classes in the alternating group $A_n$ is $a(n)=(p(n)+3q(n))/2$, where $q(n)$ is the number of partitions of $n$ with distinct odd summands. This is a result of József Dénes, Paul Erdös, and Paul Turán (1969).

Write $p(n)=q(n)+r(n)$, where $r(n)$ is the number of partitions of $n$ where the summands are not distinct odd numbers. Then the formula becomes $a(n)=2q(n)+r(n)/2$. Each atypical permutation (one with cycle lengths distinct odd numbers) gives rise to two conjugacy classes in $A_n$. This explains the $2q(n)$ term in the formula. As for the $r(n)/2$ term, we want to show that among the typical partitions (those whose summands are not distinct odd numbers), half correspond to even permutations and half to odd permutations. We will do this by exhibiting a bijection between the two sets.

The rule is: Given a partition $\pi$, if $\pi$ contains an even part, then split a largest even part into two equal parts if these parts are at least as large as the largest repeated part in $\pi$. Otherwise, merge a largest pair of repeated parts in $\pi$. In each case, one partition corresponds to an even permutation, the other to an odd permutation.

We show the correspondences for $1 \leq n \leq 6$. For $n=1$, there are no typical partitions. For $n=2$, we have \begin{align*} 1+1 &\leftrightarrow 2. \end{align*} For $n=3$, we have \begin{align*} 1+1+1 &\leftrightarrow 1+2. \end{align*} For $n=4$, we have \begin{align*} 1+1+1+1 &\leftrightarrow 1+1+2\\ 2+2 &\leftrightarrow 4. \end{align*} For $n=5$, we have \begin{align*} 1+1+1+1+1 &\leftrightarrow 1+1+1+2\\ 1+1+3 &\leftrightarrow 2+3\\ 1+2+2 &\leftrightarrow 1+4. \end{align*} For $n=6$, we have \begin{align*} 1+1+1+1+1+1 &\leftrightarrow 1+1+1+1+2\\ 2+4 &\leftrightarrow 2+2+2 \\ 1+1+1+3 &\leftrightarrow 1+2+3.\\ 1+1+2+2 &\leftrightarrow 1+1+4.\\ 3+3 &\leftrightarrow 6. \end{align*} For a discussion of this bijection, see Andrews & Eriksson.

The generating function for $\{p(n)\}$, the number of partitions of $n$ (and the number of conjugacy classes in $S_n$), is \begin{align*} \prod_{k=1}^{\infty}\frac{1}{1-x^k}=&1+x+2 x^2+3 x^3+5 x^4+7 x^5+11 x^6\\ &+15 x^7+22 x^8+30 x^9+42 x^{10}+56 x^{11}\\ &+77 x^{12}+101 x^{13}+135 x^{14}+176 x^{15}+231 x^{16}\\ &+297 x^{17}+385 x^{18}+490 x^{19}+627 x^{20}+\cdots. \end{align*} (The coefficient of $x^0$ is taken to be $1$ for algebraic convenience. In many generating functions, the coefficients of initial terms such as $x^0$ and $x^1$ may be meaningless from a counting perspective; they are included to make the formulas nicer.)

The generating function for $\{q(n)\}$, the number of partitions of $n$ into distinct odd parts, is \begin{align*} \prod_{\mbox{$k$ odd}}(1+x^k)=&1 + x + x^3 + x^4 + x^5 + x^6 + x^7 + 2 x^8 + 2 x^9 + 2 x^{10}+ 2 x^{11}\\ & + 3 x^{12} + 3 x^{13} + 3 x^{14} + 4 x^{15} + 5 x^{16} + 5 x^{17} + 5 x^{18} + 6 x^{19} + 7 x^{20}+\cdots. \end{align*} Therefore, the generating function for $\{a(n)\}$, the number of conjugacy classes in $A_n$, is \begin{align*} \frac{1}{2}\prod_{k=1}^{\infty}\frac{1}{1-x^k}+\frac{3}{2}\prod_{\mbox{$k$ odd}}(1+x^k)=&2+2 x+x^2+3 x^3+4 x^4+5 x^5+7 x^6+9 x^7\\ &+14 x^8+18 x^9+24 x^{10}+31 x^{11}+43 x^{12}\\ &+55 x^{13}+72 x^{14}+94 x^{15}+123 x^{16}+156 x^{17}\\ &+200 x^{18}+254 x^{19}+324 x^{20}+\cdots. \end{align*}

In fact, \[ \lim_{n \rightarrow \infty}\frac{a(n)}{p(n)}=\frac{1}{2} \] can be proved using asymptotic estimates for $p(n)$ and $a(n)$.

It is fine to say that the numbers $p(n)$ and $a(n)$ are given by power series, but how do we actually calculate the numbers?

We can use the magic of generating functions. As we have said, the generating function for $\{p(n)\}$ is \[ \sum_{n=0}^{\infty}p(n)x^n=\prod_{k=1}^{\infty}\frac{1}{1-x^k}. \] Multiplying both sides by $\prod_{k=1}^{\infty}(1-x^k)$, we obtain \[ \prod_{k=1}^{\infty}(1-x^k)\sum_{n=0}^{\infty}p(n)x^n=1. \] This identity gives a recurrence relation for computing the partition numbers $p(n)$ very quickly. We find that \[ \prod_{k=1}^{\infty}(1-x^k)=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}-x^{35}-x^{40}+\cdots. \] Hence \[ (1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}-x^{35}-x^{40}+\cdots)\sum_{n=0}^{\infty}p(n)x^n=1. \] The coefficient of $x^n$, for $n \geq 1$, on the left side is \[ p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)-p(n-12)-p(n-15)+p(n-22)+p(n-26)-p(n-35)-p(n-40)+\cdots. \]

Since the corresponding coefficient on the right side is $0$, we have a recurrence relation: \[ p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+p(n-12)+p(n-15)-p(n-22)-p(n-26)+p(n-35)+p(n-40)-\cdots. \] Together with the initial value $p(0)=1$, we can use this relation to obtain the sequence $\{p(n)\}$.

Leonhard Euler identified the numbers in the sequence $1$, $2$, $5$, $7$, $12$, $15$, $22$, $26$, $35$, $40$, $\ldots$.
The numbers $1$, $5$, $12$, $22$, $35$, $\ldots$ are *pentagonal numbers*, those that can be arranged in the shape of a pentagon.
They are given by the formula $k(3k-1)/2$, where $k \geq 1$.

If we take $k < 0$, we get the *pseudopentagonal numbers*, which are the other terms in the sequence: $2, 7, 15, 26, 40, \ldots$
The pentagonal numbers and pseudopentagonal numbers alternate in our sequence.
Since the intertwined sequence grows quadratically, the recurrence relation requires only on the order of $\sqrt{n}$ terms to compute $p(n)$.

Write the generating function for $\{a(n)\}$ as \[ \prod_{k=1}^{\infty}\frac{1}{1-x^k}\left(\frac{1}{2}+\frac{3}{2}\prod_{k=1}^{\infty}(1-x^k)(1+x^{2k-1})\right). \] The product $\prod_{k=1}^{\infty}(1-x^k)(1+x^{2k-1})$ is very interesting. It is equal to \[ 1+2\sum_{j=1}^{\infty}(-1)^jx^{2j^2}. \] This identity can be proved using techniques within an area of combinatorics known as ``$q$-series.''

Thus, the generating function for $\{a(n)\}$ may be written as \[ \sum_{n=0}^{\infty}a(n)x^n=\prod_{k=1}^{\infty}\frac{1}{1-x^k}\left(2+3\sum_{j=1}^{\infty}(-1)^jx^{2j^2}\right). \] We do the same trick that we used with the partition numbers. Multiply both sides by $\prod_{k=1}^{\infty}(1-x^k)$ to obtain \[ \prod_{k=1}^{\infty}(1-x^k)\sum_{n=0}^{\infty}a(n)x^n=2+3\sum_{j=1}^{\infty}(-1)^jx^{2j^2}. \] Thus, we have the recurrence formula \[ a(n)=f(n)+a(n-1)+a(n-2)-a(n-5)-a(n-7)+a(n-12)+a(n-15)-a(n-22)-a(n-26)+a(n-35)+a(n-40)-\cdots, \] where $a(0)=2$, and $f(n)=0$ unless $n$ is of the form $2j^2$, in which case $f(n)=3(-1)^j$.

You can program a computer to easily compute the first thousand terms of the sequences $\{p(n)\}$ and $\{a(n)\}$.

p[0]=1;

Do[

p[n]=0;

k=1;

While[n-k (3k-1)/2>=0,p[n]=p[n]+p[n-k (3k-1)/2](-1)^(k+1);k++];

k=1;

While[n-k (3k+1)/2>=0,p[n]=p[n]+p[n-k (3k+1)/2](-1)^(k+1);k++],

{n,1,100}]

Table[p[n],{n,0,50}]

{1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,

8349,10143,12310,14883,17977,21637,26015,31185,37338,44583,53174,63261,75175,89134,105558,124754,147273,173525,204226}

a[0]=2;

Do[

a[n]=If[IntegerQ[Sqrt[n/2]],3(-1)^Sqrt[n/2],0];

k=1;

While[n-k (3k-1)/2>=0,a[n]=a[n]+a[n-k (3k-1)/2](-1)^(k+1);k++];

k=1;

While[n-k (3k+1)/2>=0,a[n]=a[n]+a[n-k (3k+1)/2](-1)^(k+1);k++], {n,1,100}]

Table[a[n],{n,0,50}]

{2,2,1,3,4,5,7,9,14,18,24,31,43,55,72,94,123,156,200,254,324,408,513,641,804,997,1236,1526,1883,2308,2829,3451,4209,5109,6194,

7485,9038,10871,13063,15654,18738,22365,26665,31716,37682,44669,52887,62494,73767,86902,102260}

G. E. Andrews and K. Eriksson ,