You are currently browsing the tag archive for the ‘Permutation’ tag.

In this post, we discuss a few ways in which the symmetric and alternating groups can be realized as finite collections of self-maps on the Riemann sphere.  Throughout, our group operation will be composition of functions: as such, the maps we choose will necessarily be homeomorphisms of $\mathbb{P}^1$.  Within this broad framework, two classes are of particular interest:

1. The group of biholomorphic maps $f: \mathbb{P}^1 \to \mathbb{P}^1$ (those that respect the structure of $\mathbb{P}^1$ as a Riemann surface). It is well-known that such maps are given by Möbius transformations, i.e. rational functions of the form

$\displaystyle f(z) = \frac{a z +b}{cz +d},$

satisfying $ad-bc \neq 0 \in \mathbb{C}$. The group of Möbius transformations (also known as the Möbius Group and herein denoted $\mathcal{M}$) is naturally isomorphic to $\mathrm{PSL}_2(\mathbb{C})$, the projective (special) linear group, via:

$\displaystyle\frac{az+b}{cz+d} \mapsto \left(\begin{matrix} a & b \\ c & d \end{matrix} \right).$

2. The group of conformal maps $f: \mathbb{P}^1 \to \mathbb{P}^1$, denoted $\mathcal{C}$ for brevity.  To be clear, here we refer to those maps $f$ which preserve unsigned angle measure. (In contrast, some authors require conformal maps to preserve orientation as well.)  We recall the fundamental result that such maps contain the Möbius group as a subgroup of index two.  To be specific, any conformal self-map on $\mathbb{P}^1$ is either biholomorphic (returning to case (1)), or bijective and anti-holomorphic: a biholomorphic function of the complex conjugate $\overline{z}$.

After the fold, we begin a two-part program to calculate the maximal $n$ such that the symmetric group $S_n$ injects into $\mathcal{M}$ (resp. $\mathcal{C}$).  Along the way, we study injections of the alternating group into $\mathcal{M}$, and highlight some exceptional cases in which our injections can be attached to group actions on a finite invariant set.

Let $S_n$ denote the permutation group on n letters.  Herein, we consider the following question, brought to light by Landau in 1902:

Question: What is the maximal order of an element in $S_n$?

By convention, we shall refer to this maximal order as $g(n)$.  Thus, for instance, Lagrange’s theorem gives the elementary bound $g(n) \leq n!$.  We may obtain sharper bounds by noting that $S_n$ is centerless, but tweaks like this will fail to give more than a gain of a multiplicative constant.  A far more productive route comes from the following Proposition:

Proposition: Let $\{a_1,\ldots, a_k\}$ be a partition of n into positive integers.  Then $\prod_i a_i \leq 3^{n/3}$, with equality if and only if $a_i = 3$ for all i.

Proof: Let $\{a_1,\ldots, a_k\}$ be a partition of n such that $\prod a_i$ is maximized.  If $a_i >3$ for any i, we have $2(a_i-2)>a_i$, and the partition

$\{a_1,\ldots, a_{i-1}, 2, a_i-2,a_{i+1},\ldots, a_k\}$

admits a strictly larger product.  Thus, we may assume that $a_i =2,3$ for all i. Furthermore, the relation $2^3 <3^2$ implies that in a maximal partition we may have $a_i =2$ for at most two such i.  It now follows (by cases) that our maximal product $A(n)$ takes the form

$A(n) = \begin{cases} 3^{n/3}, \hspace{15.5 mm} n \equiv 0 \mod 3 \\ 4 \cdot 3^{(n-4)/3}, \quad n \equiv 1 \mod 3 \\ 2 \cdot 3^{(n-2)/3}, \quad n \equiv 2 \mod 3 \end{cases}.$

Our result follows from the inequalities $4 \cdot 3^{-4/3} < 2 \cdot 3^{-2/3} <1$. $\square$

Note: buried under all of this is the fact that the function $f(x) = x^{1/x}$ attains a global maximum at $x=e$, and that 3 is the closest integer to e (this also underlies the marginal appearance of 2, as the second closest integer approximation to e).  This will become more evident as we continue.

As a Corollary, we obtain a new upper bound for the function $g(n)$:

Corollary: For all n, we have $g(n) \leq 3^{n/3}$, with equality if and only if $n=3$.

Proof: We note that $g(n)$ is the maximum value of $\mathrm{lcm}(a_1,\ldots a_k)$, as $\{a_i\}$ varies over the partitions of n.  But $\mathrm{lcm}(a_1\ldots, a_k) \leq \prod a_i \leq 3^{n/3}$, with equality if and only if (1) $a_i =3$ for all and (2) the $\{a_i\}$ are pairwise coprime.  In particular, equality holds above if and only if $n=3$ (achieved with the partition $\{3\}$). $\square$

Note: this result is stronger than the commonly-cited bound $g(n) < e^{n/e}$, which holds for all n.

The bound arising from our Proposition is nevertheless weak in method (in that we have only used the fact that $\mathrm{lcm}(a_1,\ldots,a_k)$ divides $a_1\cdots a_k$), and to strengthen it significantly requires the Prime number theorem (PNT).  In fact, Landau’s classical result

$\log g(n) \sim \sqrt{n \log n}$

(which we will derive after the fold) is equivalent to the PNT by means of elementary methods.