In 1832, Galois introduced the concept of normal subgroups, and proved that the groups A_n (for n>4) and \mathrm{PSL}_2(\mathbb{F}_q) (for q>4) were simple, i.e. admit no non-trivial (proper) normal subgroups.  In 1892, Hölder asked for a classification of all finite simple groups, and the final classification of finite simple groups in 2004 by Aschbacher and Smith’s resolution of the quasithin case thus resolves an open problem over a century in the making. (Note: the great majority of the classification theorem concluded in the 1980’s.  A computational error was identified and resolved in 2008.)

One immediate consequence of the classification of finite simple groups (CFSG) is that the set S given by

S:=\{n \in \mathbb{N} : \text{there exists a simple group of order } n\}

has natural density 0.  Yet it seems unlikely that this result requires the tens of thousands of pages currently involved in the proof of the CFSG, and for the rest of this article we seek to bound the density of S using arithmetic methods.

Read the rest of this entry »

Advertisements

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 »

For what follows, we define a loaded die as a discrete probability distribution with six outcomes (labelled {1,…,6}), each of which has positive probability. To each such die, we associate a generating polynomial, given by

p(t):=p_1t+p_2t^2+\ldots +p_6 t^6

in which p_i denotes the probability of the outcome i.  If q(t) corresponds to another such die, we note that the product

p(t)q(t) =\sum_i a_i t^i:=\sum_{i=2}^{12}\big( \sum_{k=1}^{i-1} p_k q_{i-k}\big) t^i

has coefficients which reflect the probabilities of  certain dice sums for p and (and this is the utility of generating polynomials).  We are now ready to ask the following question:

Question: Does there exist a pair of loaded dice such that the probability of rolling any dice sum ({2,…12}) is equally likely?

Read the rest of this entry »