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.

Read the rest of this entry »

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.

Read the rest of this entry »