You are currently browsing the tag archive for the ‘Symmetric Group’ tag.

John Wilson (1741-1793) was a well-known English mathematician in his time, whose legacy lives on in his eponymous result, Wilson’s Theorem. To recall, this is the statement that an integer n >1 is prime if and only if

(n-1)! \equiv -1 \mod n.

(The “if” part is trivial.) As is the case for many historical results, Wilson’s Theorem was not proven by Wilson. Instead, it was Joseph Lagrange who provided the first proof.

The proof, as we see it today, might be phrased as follows:

Proof: Suppose that p is prime. Then each of the nonzero residues modulo p is a unit, so that (p-1)! represents the product over all units in \mathbb{Z}/p\mathbb{Z}. If

a \not\equiv a^{-1} \mod p,   i.e.    a^2 \not\equiv 1 \mod p,

then a and its inverse each show up in our list of units. We cancel out such terms in pairs, and conclude that

\displaystyle (p-1)! \equiv \prod_{a^2 \equiv 1 (p)} a \mod p.

We have a^2 \equiv 1 \mod p if and only if p \mid (a-1)(a+1), which by primality of p forces p \mid (a-1) or p \mid (a+1). In other words, a \equiv \pm 1 \mod p. It follows that

(p-1)! \equiv 1(-1) \equiv -1 \mod p.

\square

When n is composite, the direct translation of Wilson’s problem gives

(n-1)! \equiv 0 \mod n.

The problem, here, is that we’ve multiplied a number of zero divisors together, which can be avoided by only multiplying across the units, U_n, of \mathbb{Z}/n\mathbb{Z}. In this post, we consider the product

\displaystyle \prod_{a \in U_n} a \mod n,

determine its value, give credit to Gauss for doing so over two centuries ago, and discuss a few generalizations.

Read the rest of this entry »

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 »