VIII. On Substitution-Groups: Transitive and Intransitive Groups.

Chapter VIII.
On Substitution-Groups: Transitive and Intransitive Groups.

I t has been proved, in the theorem in § 20, that every group is capable of being represented as a group of substitutions performed on a number of symbols equal to the order of the group. For applications to Algebra, and in particular to the Theory of Equations, the presentation of a group as a group of substitutions is of special importance; and we shall now proceed to consider the more important properties of this special mode of representing groups³⁸.

Deﬁnition. When a group is represented by means of substitutions performed on a ﬁnite set of $n$ distinct symbols, the integer $n$ is called the degree of the group.

It is obvious, by a consideration of simple cases, that a group can always be represented in diﬀerent forms as a group of substitutions, the number of symbols which are permuted in two forms not being necessarily the same; examples have already been given in Chapter II. The “degree of a group” is therefore only an abbreviation of “the degree of a special representation of the group as a substitution-group.”

The $n!$ substitutions, including the identical substitution, that can be performed upon $n$ distinct symbols, clearly form a group; for they satisfy the conditions of the deﬁnition (§ 12). Moreover they form the greatest group of substitutions that can be performed on the $n$ symbols, because every possible substitution occurs among them. When a group then is spoken of as of degree $n$ , it is implicitly being regarded as a sub-group of this most general group of order $n!$ which can be represented by substitutions of the $n$ symbols; and therefore (Theorem I, § 22) the order of a substitution-group of degree $n$ must be a factor of $n!$ .

103. It has been seen in § 11 that any substitution performed on $n$ symbols can be represented in various ways as the product of transpositions; but that the number of transpositions entering in any such representation of the substitution is either always even or always odd. In particular, the identical substitution can only be represented by an even number of transpositions. Hence if $S$ and $S'$ are any two even (§ 11) substitutions of $n$ symbols, and $T$ any substitution at all of $n$ symbols, then $S S'$ and $T^{- 1} S T$ are even substitutions. The even substitutions therefore form a self-conjugate sub-group $H$ of the group $G$ of all substitutions.

If now $T$ is any odd substitution, the set of substitutions $T H$ are all odd and all distinct. Moreover they give all the odd substitutions; for if $T'$ is any odd substitution distinct from $T$ , then $T^{- 1} T'$ is an even substitution and must be contained in $H$ . Hence the number of even substitutions is equal to the number of odd substitutions: and the order of $G$ is twice that of $H$ .

Deﬁnitions. The group of order $n!$ which consists of all the substitutions that can be performed on $n$ symbols is called the symmetric group of degree $n$ .

The group of order $\frac{1}{2} n!$ which consists of all the even substitutions of $n$ symbols is called the alternating³⁹ group of degree $n$ .

If the substitutions of a group of degree $n$ are not all even, the preceding reasoning may be repeated to shew that its even substitutions form a self-conjugate sub-group whose order is half the order of the group; and this sub-group is a sub-group of the alternating group of the $n$ symbols.

104. Deﬁnition. A substitution-group is called transitive when, by means of its substitutions, a given symbol $a_{1}$ can be changed into every other symbol $a_{2}$ , $a_{3}$ , …, $a_{n}$ operated on by the group. When it has not this property, the group is called intransitive.

A transitive group contains substitutions changing any one symbol into any other. For if $S$ and $T$ respectively change $a_{1}$ into $a_{s}$ and $a_{t}$ , then $S^{- 1} T$ changes $a_{s}$ into $a_{t}$ .

THEOREM I. The substitutions of a transitive group $G$ , which leave a given symbol $a_{1}$ unchanged, form a sub-group; and the number of substitutions, which change $a_{1}$ into any other symbol $a_{r}$ , is equal to the order of this sub-group.

The substitutions which leave $a_{1}$ unchanged must form a sub-group $H$ of $G$ ; for if $S$ and $S'$ both leave $a_{1}$ unchanged, so also does $S S'$ .

Let the operations of $G$ be divided into the sets

H, H S_{1}, H S_{2}, \dots, H S_{m - 1} .

No operation of the set $H S_{p}$ leaves $a_{1}$ unchanged; and each operation of the set $H S_{p}$ changes $a_{1}$ into $a_{p}$ , if $S_{p}$ does so. If the operations of any other set $H S_{q}$ also changed $a_{1}$ into $a_{p}$ , then $S_{p} S_{q}^{- 1}$ would leave $a_{1}$ unchanged and would belong to $H$ , which it does not. Hence each set changes $a_{1}$ into a distinct symbol. The number of sets must therefore be equal to the number of symbols, while from their formation each set contains the same number of substitutions. If $N$ is the order and $n$ the degree of the transitive group $G$ , then $\frac{N}{n}$ is the order of the sub-group that leaves any symbol $a_{1}$ unchanged; and there are $\frac{N}{n}$ substitutions changing $a_{1}$ into any other given symbol $a_{p}$ .

Corollary. The order of a transitive group must be divisible by its degree.

Every group conjugate to $H$ leaves one symbol unchanged. For if $S$ changes $a_{1}$ into $a_{p}$ , then $S^{- 1} H S$ leaves $a_{p}$ unchanged. The sub-groups which leave the diﬀerent symbols unchanged form therefore a conjugate set.

A transitive group of degree $n$ and order $m n$ has, as we have just seen, $m - 1$ substitutions other than identity which leave a given symbol $a_{1}$ unchanged. Hence there must be at least $m n - 1 - n (m - 1)$ , i.e. $n - 1$ , substitutions in the group that displace every symbol. If the $m - 1$ substitutions, other than identity, that leave $a_{1}$ unchanged are all distinct from the $m - 1$ that leave $a_{p}$ unchanged, whatever other symbol $a_{p}$ may be, $n - 1$ will be the actual number of substitutions that displace all the symbols; and no operation other than identity will displace less than $n - 1$ symbols. If however the sub-groups that leave $a_{1}$ and $a_{p}$ unchanged have other substitutions besides identity in common, these substitutions must displace less than $n - 1$ symbols; and there will be more than $n - 1$ substitutions which displace all the symbols.

Ex. If the substitutions of two transitive groups of degree $n$ which displace all the symbols are the same, the groups can only diﬀer in the substitutions that keep just one symbol unchanged. (Netto.)

105. We have seen that every group can be represented as a substitution-group whose degree is equal to its order. A reference to the proof of this theorem (§ 20) will shew that such a substitution-group is transitive, and that the identical substitution is the only one which leaves any symbol unchanged.

We will now consider some of the properties of a transitive group of degree $n$ , whose operations, except identity, displace all or all but one of the $n$ symbols. It has just been seen that such a group has exactly $n - 1$ operations which displace all the $n$ symbols. If these $n - 1$ operations, with identity, form a sub-group, the sub-group must clearly be self-conjugate.

Suppose now that $n m$ is the order of the group. Then the order of the sub-group, that leaves one symbol $a_{1}$ unchanged, is $m$ ; and if $a_{2}$ is any other of the $n$ symbols, no two operations of this sub-group can change $a_{2}$ into the same symbol. For if $S$ , $S'$ were two operations of the sub-group both changing $a_{2}$ into $a_{r}$ , then $S S'^{- 1}$ would be an operation, distinct from identity, which would keep both $a_{1}$ and $a_{2}$ unchanged. Let now $P$ be any operation that displaces all the symbols. Then the set of $m$ operations $S^{- 1} P S$ , where for $S$ is put in turn each operation of the sub-group that keeps $a_{1}$ unchanged, are all distinct; for each of them changes $a_{1}$ into a diﬀerent symbol. If this set does not exhaust the operation conjugate to $P$ , and if $P_{1}$ is another such operation, then the set of $m$ operations $S^{- 1} P_{1} S$ are all distinct from each other and from those of the previous set. This process may be continued till the operations conjugate to $P$ are exhausted. The number of operations conjugate to $P$ is therefore a multiple of $m$ . Since $P$ itself does not belong to any one of the $n$ conjugate sub-groups that each keep one symbol ﬁxed, no operation conjugate to $P$ can belong to any of them. Hence each of the $k m$ operations of the conjugate set to which $P$ belongs displaces all the symbols. The $n - 1$ operations that displace all the symbols can therefore be divided into sets, so that the number in each set is a multiple of $m$ ; and hence $m$ must be a factor of $n - 1$ .

Suppose now that $p$ is any prime factor of $n$ , and that $p^{α}$ is the highest power of $p$ which divides $n$ . If $P$ is an operation whose order is a power of $p$ , and if $p^{β} μ$ is the order of the greatest sub-group $h$ that contains $P$ self-conjugately, then $P$ is one of $\frac{n m}{p^{β} μ}$ conjugate operations. Now (§ 87) the sub-group $h$ contains $k μ$ ( $k ≮ 1$ ) operations whose orders are relatively prime to $p$ ; and therefore there are $k μ$ operations of the form $P Q$ , where $Q$ is permutable with $P$ and the order of $Q$ is relatively prime to the order of $P$ . If $P'$ is any operation conjugate to $P$ , there are similarly $k μ$ operations of the form $P' Q'$ ; and (§ 16) no one of these operations can be identical with any one of those of the previous set. The group therefore will contain $\frac{n m k}{p^{β}}$ distinct operations, which are conjugate to the various operations of the set $P Q$ . Moreover since $P$ displaces all the symbols, each one of these operations must displace all the symbols.

If then the group has $r$ distinct sets of conjugate operations whose orders are powers of $p$ , the number of operations, whose orders are divisible by $p$ , is equal to

\sum_{s = 1}^{s = r} \frac{n m k_{s}}{p^{β_{s}}} .

Also the number of operations, which displace all the symbols and the orders of which are not divisible by $p$ , is of the form $\frac{n k_{0}}{p^{α}} - 1$ (§ 87).

Hence ﬁnally

\begin{array}{l} m \sum_{s = 1}^{s = r} \frac{k_{s}}{p^{β_{s}}} & = \frac{1}{n} \{n - 1 - (\frac{n k_{0}}{p^{α}} - 1)\} \\ = \frac{p^{α} - k_{0}}{p^{α}} . \end{array}

The greatest possible value of $m$ will correspond to the suppositions

r = 1, k_{1} = 1, k_{0} = 1;

and these give

m = p^{α} - 1 .

Hence if $n = p^{α} q^{β} \dots r^{γ}$ , where $p$ , $q$ , …, $r$ are distinct primes, $m$ cannot be greater than the least of the numbers

p^{α} - 1, q^{β} - 1, \dots, r^{γ} - 1 .

Certain particular cases may be specially noticed. First, a group of degree $n$ and order $n (n - 1)$ , whose operations other than identity displace all or all but one of the symbols, can exist only when $n$ is the power of a prime⁴⁰. Groups which satisfy these conditions will be discussed in § 112.

Similarly, a group of degree $n$ and order $n m$ , where $m$ is not less than $\sqrt{n}$ , whose operations other than identity displace all or all but one of the symbols, can only exist when $n$ is the power of a prime.

If $n$ is equal to twice an odd number, a transitive group of degree $n$ , none of whose operations except identity leave two symbols unchanged, must be of order $n$ .

Lastly we may shew that, if $m$ is even, a group of degree $n$ and order $n m$ , none of whose operations except identity leave two symbols unchanged, must contain a self-conjugate Abelian sub-group of order and degree $n$ .

A sub-group that keeps one symbol ﬁxed must, if $m$ is even, contain an operation of order $2$ . If it contained $r$ such operations, the group would contain $n r$ ; and each of these could be expressed as the product of $\frac{1}{2} (n - 1)$ independent transpositions. Now from $n$ symbols $\frac{1}{2} n (n - 1)$ transpositions can be formed. If then $r$ were greater than $1$ , among the operations of order $2$ that keep one symbol ﬁxed there would be pairs of operations with a common transposition; and the product of two such operations would be an operation, distinct from identity, which would keep two symbols at least ﬁxed. This is impossible; therefore $r$ must be unity. Now let

A_{1}, A_{2}, \dots, A_{n}

be the

n

operations of order

2

belonging to the group. Since no two of these operations contain a common transposition,

A_{1} A_{r}, A_{2} A_{r}, \dots, A_{r - 1} A_{r}, A_{r + 1} A_{r}, \dots, A_{n} A_{r}

are the

n - 1

operations which displace all the symbols. These operations may also be expressed in the form

A_{r} A_{1}, A_{r} A_{2}, \dots, A_{r} A_{r - 1}, A_{r} A_{r + 1}, \dots, A_{r} A_{n};

and since

A_{p} A_{r} \cdot A_{r} A_{q} = A_{p} A_{q},

the product of any two of these operations is either identity or another operation which displaces all the symbols. Hence the

n - 1

operations which displace all the symbols, with identity, form a self-conjugate sub-group. Now

A_{r} \cdot A_{p} A_{r} \cdot A_{r} = A_{r} A_{p},

so that

A_{r}

transforms every operation of this sub-group into its inverse. Hence

A_{r} A_{p} \cdot A_{q} A_{r} = A_{q} A_{p} = A_{q} A_{r} \cdot A_{r} A_{q};

i.e. every two operations of this sub-group are permutable, and the sub-group is therefore Abelian.

106. If

S = (a_{1} a_{2} \dots a_{i}) (a_{i + 1} a_{i + 2} \dots a_{j}) \dots,

and

T = (\binom{a_{1}, a_{2}, \dots, a_{n}}{b_{1}, b_{2}, \dots, b_{n}}),

are any two substitutions of a group, then (§ 10)

T^{- 1} S T = (b_{1} b_{2} \dots b_{i}) (b_{i + 1} b_{i + 2} \dots b_{j}) \dots .

Hence every substitution of the group, which is conjugate to $S$ , is also similar to $S$ . It does not necessarily or generally follow that two similar substitutions of a group are conjugate. That this is true however of the symmetric group is obvious, for then the substitution $T$ may be chosen so as to replace the $n$ symbols by any permutation of them whatever.

A self-conjugate substitution of a transitive group of degree $n$ must be a regular substitution (§ 9) changing all the $n$ symbols. For if it did not change all the $n$ symbols, it would belong to one of the sub-groups that keep a symbol unchanged. Hence, since it is a self-conjugate substitution, it would belong to each sub-group that keeps a symbol unchanged, which is impossible unless it is the identical substitution. Again if it were not regular, one of its powers would keep two or more symbols unchanged, and this cannot be the case since every power of a self-conjugate substitution must be self-conjugate. On the other hand, a self-conjugate sub-group of a transitive group need not contain any substitution which displaces all the symbols. Thus if

\begin{array}{l} S & = (12) (34), \\ T & = (135) (246), \end{array}

then ${S, T}$ is a transitive group of degree $6$ . The only substitutions conjugate to $S$ are

T^{- 1} S T = (34) (56) and T S T^{- 1} = (12) (56);

and these, with

S

and identity, form a self-conjugate sub-group of order

4

, none of whose substitutions displace more than

4

symbols. The form of a self-conjugate sub-group of a transitive group will be considered in greater detail in the next Chapter.

107. Since a self-conjugate substitution of a transitive substitution-group $G$ of degree $n$ must be a regular substitution which displaces all the symbols, the self-conjugate sub-group $H$ of $G$ which consists of all its self-conjugate operations must have $n$ or some submultiple of $n$ for its order. For if $S$ and $S'$ are two self-conjugate substitutions of $G$ , so also is $S^{- 1} S'$ ; and therefore $S$ and $S'$ cannot both change $a$ into $b$ . The order of $H$ therefore cannot exceed $n$ ; and if the order is $n'$ , the substitutions of $H$ must interchange the $n$ symbols in sets of $n'$ , so that $n'$ is a factor of $n$ . Let now $S$ , some substitution performed on the $n$ symbols of the transitive substitution-group $G$ of degree $n$ , be permutable with every substitution of $G$ . Then $S$ is a self-conjugate operation of the transitive substitution-group ${S, G}$ of degree $n$ , and it is therefore a regular substitution in all the $n$ symbols. The totality of the substitutions $S$ , which are permutable with every substitution of $G$ , form a group (not necessarily Abelian); and the order of this group is $n$ or a factor of $n$ .

The special case, in which $G$ is a group whose order $n$ is equal to its degree, is of suﬃcient importance to merit particular attention. If

S_{1} (= 1), S_{2}, \dots, S_{n}

are the operations of

G

, it has been seen (§ 20) that the substitution-group can be expressed as consisting of the

n

substitutions

(\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{1} S_{x}, S_{2} S_{x}, \dots, S_{n} S_{x}}), (x = 1, 2, \dots, n),

performed upon the symbols of the operations of the group.

Now if pre-multiplication be used in the place of post-multiplication, it may be veriﬁed exactly as in § 20 that the $n$ substitutions

(\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{x} S_{1}, S_{x} S_{2}, \dots, S_{x} S_{n}}), (x = 1, 2, \dots, n)

form a group

G'

simply isomorphic with

G

; and the substitution of

G'

which is given corresponds to the operation

S_{x}^{- 1}

G

. Moreover

\begin{matrix} {(\binom{S_{1}, \dots, S_{n}}{S_{x} S_{1}, \dots, S_{x} S_{n}})}^{- 1} (\binom{S_{1}, \dots, S_{n}}{S_{1} S_{y}, \dots, S_{n} S_{y}}) (\binom{S_{1}, \dots, S_{n}}{S_{x} S_{1}, \dots, S_{x} S_{n}}) \\ \begin{aligned} = (\binom{S_{x} S_{1}, \dots, S_{x} S_{n}}{S_{1} S_{y}, \dots, S_{1} S_{n}}) (\binom{S_{1} S_{y}, \dots, S_{n} S_{y}}{S_{x} S_{1} S_{y}, \dots, S_{x} S_{n} S_{y}}) \\ = (\binom{S_{x} S_{1}, \dots, S_{x} S_{n}}{S_{x} S_{1} S_{y}, \dots, S_{x} S_{n} S_{y}}) = (\binom{S_{1}, \dots, S_{n}}{S_{1} S_{y}, \dots, S_{n} S_{y}}), \end{aligned} \end{matrix}

so that every operation of $G'$ is permutable with every operation of $G$ , while $G$ and $G'$ can be expressed as transitive substitution-groups in the same $n$ symbols. Hence:—

THEOREM II. Those substitutions of $n$ symbols which are permutable with every substitution of a substitution-group $G$ of order $n$ , transitive in the $n$ symbols, form a group $G'$ of order and degree $n$ , simply isomorphic with $G$ ⁴¹.

It has, in fact, been seen that there is a substitution-group $G'$ of order and degree $n$ , every one of whose substitutions is permutable with every substitution of $G$ ; and also that the order of any such group cannot exceed $n$ .

If $S_{x}$ is a self-conjugate substitution of $G$ , the substitutions

(\binom{S_{1}, \dots, S_{n}}{S_{1} S_{x}, \dots, S_{n} S_{x}}) and (\binom{S_{1}, \dots, S_{n}}{S_{x} S_{1}, \dots, S_{x} S_{n}})

are the same. Hence

G

and

G'

have for their greatest common sub-group, that which is constituted by the self-conjugate substitutions of either; and if

n'

is the order of this sub-group, the order of

{G, G'}

\frac{n^{2}}{n'}

. In particular, if

G

is Abelian,

G

and

G'

coincide; and if

G

has no self-conjugate operation except identity,

{G, G'}

is the direct product of

G

and

G'

The sub-group of ${G, G'}$ which leaves one symbol, say $S_{1}$ , unchanged, is formed of the distinct substitutions of the set

(\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{x}^{- 1} S_{1} S_{x}, S_{x}^{- 1} S_{2} S_{x}, \dots, S_{x}^{- 1} S_{n} S_{x}}), (x = 1, 2, \dots, n) .

When $G$ has no self-conjugate operation except identity, the order of this sub-group is $n$ , and it is simply isomorphic with $G$ . In fact, in this case the order of ${G, G'}$ , a transitive group of degree $n$ , is $n^{2}$ , and therefore the order of a sub-group that keeps one symbol unchanged is $n$ . Again

\begin{matrix} (\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{x}^{- 1} S_{1} S_{x}, S_{x}^{- 1} S_{2} S_{x}, \dots, S_{x}^{- 1} S_{n} S_{x}}) (\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{y}^{- 1} S_{1} S_{y}, S_{y}^{- 1} S_{2} S_{y}, \dots, S_{y}^{- 1} S_{n} S_{y}}) \\ \begin{aligned} = (\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{x}^{- 1} S_{1} S_{x}, S_{x}^{- 1} S_{2} S_{x}, \dots, S_{x}^{- 1} S_{n} S_{x}}) \\ (\binom{S_{x}^{- 1} S_{1} S_{x}, S_{x}^{- 1} S_{2} S_{x}, \dots, S_{x}^{- 1} S_{n} S_{x}}{S_{y}^{- 1} S_{x}^{- 1} S_{1} S_{x} S_{y}, S_{y}^{- 1} S_{x}^{- 1} S_{2} S_{x} S_{y}, \dots, S_{y}^{- 1} S_{x}^{- 1} S_{n} S_{x} S_{y}}) \\ = (\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{y}^{- 1} S_{x}^{- 1} S_{1} S_{x} S_{y}, S_{y}^{- 1} S_{x}^{- 1} S_{2} S_{x} S_{y}, \dots, S_{y}^{- 1} S_{x}^{- 1} S_{n} S_{x} S_{y}}); \end{aligned} \end{matrix}

thus giving a direct veriﬁcation that the sub-group is isomorphic with the group whose operations are

S_{1}, S_{2}, \dots, S_{n} .

When $G$ contains self-conjugate operations, it will be multiply isomorphic with the sub-group $K_{1}$ of ${G, G'}$ which keeps the symbol $S_{1}$ ﬁxed; and if $g$ is the group constituted by the self-conjugate operations of $G$ (or $G'$ ), then $K_{1}$ is simply isomorphic with $\frac{G}{g}$ .

If $K_{1}$ is not a maximum sub-group of ${G, G'}$ , let $I$ be a greater sub-group containing $K_{1}$ . Then $I$ and $G'$ (or $G$ ) must contain common substitutions. For every substitution of ${G, G'}$ is of the form

(\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{y} S_{1} S_{x}, S_{y} S_{2} S_{x}, \dots, S_{y} S_{n} S_{x}});

and if this substitution belongs to

I

, then

(\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{y} S_{1} S_{x}, S_{y} S_{2} S_{x}, \dots, S_{y} S_{n} S_{x}}) (\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{x} S_{1} S_{x}^{- 1}, S_{x} S_{2} S_{x}^{- 1}, \dots, S_{x} S_{n} S_{x}^{- 1}}),

(\binom{S_{1}, S_{2}, \dots, S_{n}}{S_{x} S_{y} S_{1}, S_{x} S_{y} S_{2}, \dots, S_{x} S_{y} S_{n}}),

is a substitution of

G'

which belongs to

I

. Moreover, since

G'

is a self-conjugate sub-group of

{G, G'}

, the substitutions of

G'

which belong to

I

form a self-conjugate sub-group of

I

: this sub-group we will call

H'

Now every substitution of the group can be represented as the product of a substitution of $K_{1}$ by a substitution of $G$ : and therefore all the sub-groups conjugate to $I$ will be obtained on transforming $I$ by the operations of $G$ . Hence, because every substitution of $G$ transforms $H'$ into itself, $H'$ is common to the complete set of conjugate sub-groups to which $I$ belongs; and $H'$ is therefore a self-conjugate sub-group of ${G, G'}$ . Finally then, $K_{1}$ is a maximum sub-group of ${G, G'}$ , if and only if $G$ is a simple group.

108. Deﬁnition. A substitution-group, that contains one or more substitutions changing $k$ given symbols $a_{1}$ , $a_{2}$ , …, $a_{k}$ into any other $k$ symbols, is called $k$ -ply transitive.

Such a group clearly contains substitutions changing any set of $k$ symbols into any other set of $k$ ; and the order of the sub-group keeping any $j$ ( $≯ k$ ) symbols unchanged is independent of the particular $j$ symbols chosen.

THEOREM III. The order of a $k$ -ply transitive group of degree $n$ is $n (n - 1) \dots (n - k + 1) m$ , where $m$ is the order of the sub-group that leaves any $k$ symbols unchanged. This sub-group is contained self-conjugately in a sub-group of order $k! m$ .

If $N$ is the order of the group, the order of the sub-group which keeps one symbol ﬁxed is $\frac{N}{n}$ , by Theorem I (§ 104). Now this sub-group is a transitive group of degree $n - 1$ ; and therefore the order of the sub-group that keeps two symbols unchanged is $\frac{N}{n (n - 1)}$ . If $k > 2$ , this sub-group again is a transitive group of degree $n - 2$ ; and so on. Proceeding thus, the order of the sub-group which keeps $k$ symbols unchanged is seen to be

\frac{N}{n (n - 1) \dots (n - k + 1)},

which proves the ﬁrst part of the theorem.

Let $a_{1}$ , $a_{2}$ , …, $a_{k}$ be the $k$ symbols which are left unchanged by a sub-group $H$ of order $m$ . Since the group is $k$ -ply transitive, it must contain substitutions of the form

(\binom{a_{1}, a_{2}, \dots, a_{k}, b, c, \dots}{a', a', \dots, a', b', c', \dots}),

where

a'

a'

, …,

a'

are the same

k

symbols as

a_{1}

a_{2}

, …,

a_{k}

arranged in any other sequence. Also every substitution of this form is permutable with

H

, since it interchanges among themselves the symbols left unchanged by

H

. Further, if

S_{1}

and

S_{2}

are any two substitutions of this form,

S_{1}^{- 1} S_{2}

will belong to

H

if, and only if,

S_{1}

and

S_{2}

give the same permutation of the symbols

a_{1}

a_{2}

, …,

a_{k}

. Hence ﬁnally, since

k!

distinct substitutions can be performed on the

k

symbols, the order of the sub-group that contains

H

self-conjugately is

k! m

If $m$ is unity, the identical substitution is the only one that keeps any $k$ symbols ﬁxed, and there is just one substitution that changes $k$ symbols into any other $k$ . In the same case, the group contains substitutions which displace $n - k + 1$ symbols only, and there are none, except the identical substitution, which displace less.

If $m > 1$ , the group will contain $m - 1$ substitutions besides identity, which leave unchanged any $k$ given symbols, and therefore displace $n - k$ symbols at most.

It follows from § 105 that a $k$ -ply transitive group of degree $n$ and order $n (n - 1) \dots (n - k + 1)$ can exist only if $n - k + 2$ is the power of a prime. For such a group must contain sub-groups of order $(n - k + 2) (n - k + 1)$ , which keep $k - 2$ symbols unchanged and are doubly transitive in the remaining $n - k + 2$ . When $k$ is $n$ , the group is the symmetric group; and when $k$ is $n - 2$ , we shall see (in § 110) that the group is the alternating group. If $k$ is less than $n - 2$ , M. Jordan⁴² has shewn that, with two exceptions for $n = 11$ and $n = 12$ , the value of $k$ cannot exceed $3$ . The actual existence of triply transitive groups of order $(p^{n} + 1) p^{n} (p^{n} - 1)$ , for all prime values of $p$ , will be established in § 113.

109. A $k$ -ply transitive group, of degree $n$ and order $N$ , is not generally contained in some $(k + 1)$ -ply transitive group of degree $n + 1$ and order $N (n + 1)$ . To determine whether this is the case for any given group, M. Jordan⁴³ has suggested the following tentative process, which for moderate values of $n$ is always practicable.

Let $G$ be a transitive group of order $N$ in the $n$ symbols

a_{1}, a_{2}, \dots, a_{n};

and suppose that

G

is that sub-group of the transitive group

Γ

in the

n + 1

symbols

a_{1}, a_{2}, \dots, a_{n}, a_{n + 1},

which leaves the symbol

a_{n + 1}

unchanged. Then

Γ

must be at least doubly transitive, and it therefore contains a substitution of order

2

which interchanges the two symbols

a_{1}

and

a_{n + 1}

. Let

A

be such a substitution. Then

Γ = {G, A};

for

{G, A}

is contained in

Γ

, and its order cannot be less than the order of

Γ

. Also if

S

is any substitution of

G

which displaces

a_{1}

, two other substitutions

S'

and

S''

G

can always be found such that

A S A = S' A S'' .

In fact, if $A S A$ changes $a_{r}$ into $a_{n + 1}$ , and if $S'$ changes $a_{r}$ into $a_{1}$ , then $A S'^{- 1} A S A$ leaves $a_{n + 1}$ unchanged, and it therefore belongs to $G$ .

Conversely, if $A$ is any operation of order $2$ which changes $a_{1}$ into $a_{n + 1}$ and permutes the remaining $a$ ’s among themselves; and if, whatever substitution of $G$ is represented by $S$ ,two other substitutions of $G$ can be found such that

A S A = S' A S'';

then

{G, A}

is a group with the required properties. In fact, when these conditions are satisﬁed, every substitution of the group

{G, A}

can be expressed in one of the two forms

S_{1}, S_{2} A S_{3},

where

S_{1}

S_{2}

S_{3}

are substitutions of

G

. For instance, the substitution

\begin{array}{l} A S_{p} A S_{q} A S_{r} & = S' A S'' \cdot S_{q} A S_{r}, \\ = S' A S_{t} A S_{r}, if S'' S_{q} = S_{t}, \\ = S' S' A S'' S_{r}, \end{array}

which is of the second form. The reduction is here carried out on supposition that $S_{p}$ and $S_{t}$ displace $a_{1}$ . The modiﬁcation, when this is not the case, is obvious.

Moreover every operation of the form $S_{2} A S_{3}$ displaces $a_{n + 1}$ , and therefore the sub-group of ${G, A}$ which leaves $a_{n + 1}$ unchanged is $G$ .

It is clearly suﬃcient that the conditions

A S A = S' A S''

should be satisﬁed, when each of a set of independent generating operations of

G

is taken for

S

Ex. Construct a doubly transitive group of degree $12$ of which the sub-group that keeps one symbol unchanged is

{(123456789 a b), (256 a 4) (39 b 87)} .

110. Let

S = (a_{1} a_{2} \dots a_{i}) \dots (\dots a_{j - 1} a_{j}) (a_{j + 1} \dots a_{k - 1} a_{k} \dots) \dots

be a substitution of a

k

-ply transitive group displacing

s

(

> k

) symbols. If

j < k - 1

, take

T = (\binom{a_{1}, a_{2}, \dots, a_{k - 1}, a_{k}, \dots}{a_{1}, a_{2}, \dots, a_{k - 1}, b_{k}, \dots}),

where

b_{k}

is some other symbol occurring in

S

. Since the group is

k

-ply transitive, it must contain a substitution such as

T

. Now

T^{- 1} S T = (a_{1} a_{2} \dots a_{i}) \dots (\dots a_{j - 1} a_{j}) (a_{j + 1} \dots a_{k - 1} b_{k} \dots) \dots;

and this is certainly not identical with

S

, so that

T^{- 1} S T S^{- 1}

cannot be the identical substitution. Moreover

a_{1}

a_{2}

, …,

a_{k - 2}

are not aﬀected by

T^{- 1} S T S^{- 1}

; and therefore this substitution will displace at most

2 s - 2 k + 2

symbols.

If $j = k - 1$ , take

T = (\binom{a_{1}, a_{2}, \dots, a_{k - 1}, a_{k}, \dots}{a_{1}, a_{2}, \dots, a_{k - 1}, c_{k}, \dots}),

where

c_{k}

is a symbol that does not occur in

S

. Then

T^{- 1} S T = (a_{1} a_{2} \dots a_{i}) \dots (\dots a_{k - 2} a_{k - 1}) (c_{k} \dots),

and this cannot coincide with

S

. Now in this case,

a_{1}

a_{2}

, …,

a_{k - 1}

are not aﬀected by

T^{- 1} S T S^{- 1}

; and therefore this operation will again displace at most

2 s - 2 k + 2

symbols.

If then

2 s - 2 k + 2 < s,

s < 2 k - 2,

the group must contain a substitution aﬀecting fewer symbols than

S

. This process may be repeated till we arrive at a substitution

Σ = (α_{1} α_{2} \dots α_{i}) (α_{i + 1} \dots α_{j}) \dots (α_{j + 1} \dots α_{k}),

which aﬀects exactly

k

symbols; and if this substitution be transformed by

T = (\binom{α_{1}, α_{2}, \dots, α_{k - 1}, α_{k}, \dots}{α_{1}, α_{2}, \dots, α_{k - 1}, β_{k}, \dots}),

then

T^{- 1} Σ T = (α_{1} α_{2} \dots α_{i}) (α_{i + 1} \dots α_{j}) \dots (α_{j + 1} \dots a_{k - 1} β_{k}),

and

Σ^{- 1} T^{- 1} Σ T = (α_{k} β_{k} α_{j + 1}) .

Thus in the case under consideration the group contains one, and therefore every, circular substitution of three symbols; and hence (§ 11) it must contain every even substitution. It is therefore either the alternating or the symmetric group. If then a $k$ -ply transitive group of degree $n$ does not contain the alternating group of $n$ symbols, no one of its substitutions, except identity, must displace fewer than $2 k - 2$ symbols. It has been shewn that such a group contains substitutions displacing not more than $n - k + 1$ symbols; and therefore, for a $k$ -ply transitive group of degree $n$ , other than the alternating or the symmetric group, the inequality

n - k + 1 ≮ 2 k - 2,

k ≯ \frac{1}{3} n + 1,

must hold. Hence:—

THEOREM IV. A group of degree $n$ , which does not contain the alternating group of $n$ symbols, cannot be more than $(\frac{1}{3} n + 1)$ -ply transitive.

The symmetric group is $n$ -ply transitive; and, since of the two substitutions

(\binom{a_{1}, a_{2}, \dots, a_{n - 2}, a_{n - 1}, a_{n}}{b_{1}, b_{2}, \dots, b_{n - 2}, b_{n - 1}, b_{n}}) and (\binom{a_{1}, a_{2}, \dots, a_{n - 2}, a_{n - 1}, a_{n}}{b_{1}, b_{2}, \dots, b_{n - 2}, b_{n}, b_{n - 1}}),

one is evidently even and the other odd, the alternating group is

(n - 2)

-ply transitive. The discussion just given shews that no other group of degree

n

can be more than

(\frac{1}{3} n + 1)

-ply transitive⁴⁴.

111. The process used in the preceding paragraph may be applied to shew that, unless $n = 4$ , the alternating group of $n$ symbols is simple. It has just been shewn that the alternating group is $(n - 2)$ -ply transitive. Therefore, if $S$ is a substitution of the alternating group displacing fewer than $n - 1$ symbols, a substitution $T^{- 1} S T$ can certainly be found such that $S^{- 1} T^{- 1} S T$ is a circular substitution of three symbols. In this case, the self-conjugate group generated by $S$ and its conjugate substitutions contains all the circular substitutions of three symbols, and therefore it coincides with the alternating group itself. If $S$ displaces $n - 1$ symbols, then $T^{- 1} S T$ can be taken so that $S^{- 1} T^{- 1} S T$ displaces not more than $2 (n - 1) - 2 (n - 2) + 2$ , or $4$ symbols; and if $S$ displaces $n$ symbols, $S^{- 1} T^{- 1} S T$ can be found to displace not more than $2 n - 2 (n - 2) + 2$ , or $6$ symbols.

It is therefore only necessary to consider the case $n = 5$ , when $S$ displaces $n - 1$ symbols; and the cases $n = 4$ , $5$ , $6$ , when $S$ displaces $n$ symbols; in all other cases, the group generated by $S$ and its conjugate substitutions must contain circular substitutions of $3$ symbols.

When $n = 5$ , and $S$ is an even substitution displacing $4$ symbols, we may take

S = (12) (34) .

T = (12) (35),

then

T^{- 1} S T = (12) (45),

and

S^{- 1} T^{- 1} S T = (345) .

Hence, in this case again, we are led to the alternating group itself.

When $n = 6$ , and $S$ is an even substitution displacing all the symbols, we may take

S = (12) (3456),

S' = (123) (456) .

If now

T = (12) (3645),

then

S^{- 1} T^{- 1} S T = (356),

and

S'^{- 1} T^{- 1} S' T = (14263);

and, in either case, we are led to the alternating group.

When $n = 5$ , and $S$ is an even substitution displacing all the symbols, we may put

S = (12345) .

T = (345),

then

S^{- 1} T^{- 1} S T = (134);

and again the alternating group is generated.

When $n = 4$ , and $S$ is an even substitution displacing all the symbols, we may take

S = (12) (34) .

Here the only two substitutions conjugate to

S

are clearly

(13) (24)

and

(14) (23)

, which are permutable with each other and with

S

. Hence the alternating group of

4

symbols, which is of order

12

, has a self-conjugate sub-group of order

4

Finally when $n = 3$ , the alternating group, being the group ${(123)}$ , is a simple cyclical group of order $3$ . Hence:—

THEOREM V. The alternating group of $n$ symbols is a simple group except when $n = 4$ .

112. It has been seen in § 108 that the order of a doubly transitive group of degree $n$ is equal to or is a multiple of $n (n - 1)$ . If it is equal to this number, every substitution of the group, except identity, must displace either all or all but one of the symbols; for a sub-group of order $n - 1$ which keeps one symbol ﬁxed is transitive in the remaining $n - 1$ symbols, and therefore all its substitutions, except identity, displace all the $n - 1$ symbols.

Now it has been shewn in § 105 that a transitive group of degree $n$ and order $n (n - 1)$ , whose operations displace all or all but one of the symbols can exist only if $n$ is the power of a prime $p$ . The $n - 1$ operations displacing all the symbols are the only operations of the group whose orders are powers of $p$ ; and therefore with identity they form a self-conjugate sub-group of order $n$ . Moreover it also follows from § 105 that the $n - 1$ operations of this sub-group other than identity form a single conjugate set. Hence this sub-group must be Abelian, and all its operations are of order $p$ .

Suppose ﬁrst that $n$ is a prime $p$ , and that $P$ is any operation of the group of order $p$ . If $α$ is a primitive root of $p$ , there must be an operation $S$ in the group such that

S^{- 1} P S = P^{α};

then

S^{p - 1}

is the lowest power of

S

which is permutable with

P

. Now

S

must belong to a sub-group of order

p - 1

that keeps one symbol ﬁxed, and we have just seen that the order of

{S}

is not less than

p - 1

. The sub-group of order

p - 1

is therefore cyclical, and

S^{p - 1} = 1 .

Hence the group, if it exists, must be deﬁned by

P^{p} = 1, S^{p - 1} = 1, S^{- 1} P S = P^{α} .

It is an immediate result of a theorem, which will be proved in the next chapter (§ 123), that this group can be actually represented as a transitive substitution-group of degree $p$ ; this may be also veriﬁed directly as follows.

Let

P = (a_{1} a_{2} \dots a_{p}),

so that

P^{α} = (a_{1} a_{α + 1} a_{2 α + 1} \dots a_{(p - 1) α + 1}),

where the suﬃxes are to be reduced

(mod p)

; and suppose that

S

is a substitution that keeps unchanged. Then since

S^{- 1} P S = P^{α},

S

must change

a_{2}

into

a_{α + 1}

a_{3}

into

a_{2 α + 1}

, and generally,

a_{r}

into

a_{(r - 1) α + 1}

. Hence

S = (a_{2} a_{α + 1} a_{α^{2} + 1} \dots) \dots;

and since

α

is a primitive root of

p

, there is only a single cycle; so that

S = (a_{2} a_{α + 1} a_{α^{2} + 1} \dots a_{α^{p - 2} + 1}) .

The substitutions $P$ and $S$ thus constructed actually generate a doubly transitive substitution-group of degree $p$ and order $p (p - 1)$ .

Without making a complete investigation of the case in which $n$ is the power of a prime, we go on to shew that, $p$ being any prime, there is always a doubly transitive group of degree $p^{m}$ and order $p^{m} (p^{m} - 1)$ , in which a sub-group of order $p^{m} - 1$ is cyclical⁴⁵.

Let $i$ be a primitive root of the congruence

i^{p^{m} - 1} \equiv 1 (mod p),

so that the distinct roots of the congruence are

i, i^{2}, i^{3}, \dots, i^{p^{m} - 1} .

Every rational function of

i

with real integral coeﬃcients satisﬁes the same congruence; and therefore every such function is congruent

(mod p)

to some power of

i

not exceeding the

(p^{m} - 1)

th.

Consider now a set of transformations of the form

x' \equiv α x + β (mod p),

where

α

is a power of

i

, and

β

is either a power of

i

or zero. Two such transformations, performed successively, give another transformation of the same form; and since

α

cannot be zero, the inverse of each transformation is another deﬁnite transformation; so that the totality of transformations of this form constitute a group. Moreover

\begin{aligned} x' & \equiv α x + β, \\ a n d x' & \equiv α' x + β' \end{aligned} (mod p),

are not the same transformation unless

α \equiv α' and β \equiv β' (mod p) .

Hence, since

α

can take

p^{m} - 1

distinct values and

β

can take

p^{m}

distinct values, the order of the group, formed of the totality of these transformations, is

p^{m} (p^{m} - 1)

The transformations for which $α$ is unity clearly form a sub-group. If $S$ and $T$ represent

x' \equiv α x + β and x' \equiv x + γ

respectively,

S^{- 1} T S

represents

x' \equiv x + α γ .

Hence the transformations for which

α

is unity form a self-conjugate sub-group whose order is

p^{m}

. Every two transformations of this sub-group are clearly permutable; and the order of each of them except identity is

p

Again, the transformations for which $β$ is zero form a sub-group. Since every one of them is a power of the transformation

x' \equiv i x,

this sub-group is a cyclical sub-group of order

p^{m} - 1

. If the transformation just written be denoted by

I

, then

S^{- 1} I S

x' \equiv i x + β (1 - i) .

Hence the only operations permutable with

{I}

are its own operations, and therefore

{I}

is one of

p^{m}

conjugate sub-groups.

The set of transformations

x' \equiv α x + β

therefore forms a group of order

p^{m} (p^{m} - 1)

. This group contains a self-conjugate Abelian sub-group of order

p^{m}

and type

(1, 1, \dots, 1)

, and

p^{m}

conjugate cyclical sub-groups of order

p^{m} - 1

, none of whose operations are permutable with any of the operations of the self-conjugate sub-group.

Now if the operation

x' \equiv α x + β

be performed on each term of the series

0, i, i^{2}, \dots, i^{p^{m} - 1},

it will, since every rational integral function of

i

with real integral coeﬃcients is congruent

(mod p)

to some power of

i

, change the term into another of the same series; and since the congruence

α i^{x} + β \equiv α i^{y} + β

gives

x \equiv y (mod p^{m - 1}),

no two terms of the series can thus be transformed into the same term. Moreover the only operation that leaves every term of the series unchanged is clearly the identical operation.

To each operation of the form

x' \equiv α x + β

therefore will correspond a single substitution performed on the

p^{m}

symbols just written, so that to the product of two operations will correspond the product of the two homologous substitutions. The group is therefore simply isomorphic with a substitution group of degree

p^{m}

. Moreover since the linear congruence

x \equiv α x + β (mod p)

has only a single solution when

α

is diﬀerent from unity, and none when

α

is unity, every substitution except identity must displace all or all but one of the symbols. The substitution group is therefore doubly transitive⁴⁶.

Ex. 1. Apply the method just explained to the actual construction of a doubly transitive group of degree $8$ and order $56$ .

Ex. 2. Shew that the equations

A^{2} = 1, S^{2^{m} - 1} = 1, A S^{- 1} A S = S^{- n} A S^{n},

where

n

is such that a primitive root of the congruence,

i^{2^{m} - 1} - 1 \equiv 0 (mod 2),

satisﬁes the congruence

i^{n} + i + 1 \equiv 0 (mod 2),

suﬃce to deﬁne a group which can be expressed as a doubly transitive group of degree

2^{m}

and order

2^{m} (2^{m} - 1)

. (Messenger of Mathematics, Vol. XXV, p. 189.)

113. A slight extension of the method of the preceding paragraph will enable us to shew that, for every prime $p$ , it is possible to construct a triply transitive group of degree $p^{m} + 1$ and order $(p^{m} + 1) p^{m} (p^{m} - 1)$ . The analysis of this group will form the subject of investigation in Chapter XIV; here we shall only demonstrate its existence.

In the place of the operations of the last paragraph, we now consider those of the form

x' \equiv \frac{α x + β}{γ x + δ} (mod p),

where again

α

β

γ

δ

are powers of

i

, limited now by the condition that

α δ - β γ

is not congruent to zero

(mod p)

. When this relation is satisﬁed, the set of operations again clearly form a group. Moreover if we represent

\frac{i^{x}}{0}

\infty

for all values of

x

, any operation of this group, when carried out on the set of quantities

\infty, 0, i, i^{2}, \dots, i^{p^{m} - 1},

will change each of them into another of the set; while no operation except identity will leave each symbol of the set unchanged. Hence the group can be represented as a substitution group of degree

p^{m} + 1

Now

\frac{x' - i^{a'}}{x' - i^{b'}} \frac{i^{c'} - i^{b'}}{i^{c'} - i^{a'}} \equiv \frac{x - i^{a}}{x - i^{b}} \frac{i^{c} - i^{b}}{i^{c} - i^{a}}

is an operation of the above form, which changes the three symbols

i^{a}

i^{b}

i^{c}

into

i^{a'}

i^{b'}

i^{c'}

respectively; and it is easy to modify this form so that it holds when

0

\infty

occurs in the place of

i^{a}

, etc. Hence the substitution group is triply transitive, since it contains an operation transforming any three of the

p^{m} + 1

symbols into any other three.

On the other hand, if the typical operation keeps the symbol $x$ unchanged, then

γ x^{2} + (δ - α) x - β \equiv 0 (mod p),

and this congruence cannot have more than two roots among the set of

p^{m} + 1

symbols. Hence no substitution of the group, except identity, keeps more than two symbols ﬁxed.

Finally then, since the group is triply transitive and since it contains no operation, except identity, that keeps more than two symbols ﬁxed, its order must (§ 108) be $(p^{m} + 1) p^{m} (p^{m} - 1)$ .

114. An intransitive substitution group, as deﬁned in § 104, is one which does not contain substitutions changing $a_{1}$ into each of the other symbols $a_{2}$ , $a_{3}$ , …, $a_{n}$ operated on by the group. Let us suppose that the substitutions of such a group change $a_{1}$ into $a_{2}$ , $a_{3}$ , …, $a_{k}$ only. Then all the substitutions of the group must interchange these $k$ symbols among themselves; for if the group contained a substitution changing $a_{2}$ into $a_{k + 1}$ , then the product of any substitution changing $a_{1}$ into $a_{2}$ by this latter substitution would change $a_{1}$ into $a_{k + 1}$ . Hence the $n$ symbols operated on by the group can be divided into a number of sets, such that the substitutions of the group change the symbols of any one set transitively among themselves, but do not interchange the symbols of two distinct sets. It follows immediately that the order of the group must be a common multiple of the numbers of symbols in the diﬀerent sets.

Suppose now that $a_{1}$ , $a_{2}$ , …, $a_{k}$ is a set of symbols which are interchanged transitively by all the substitutions of a group $G$ of degree $n$ . If for a time we neglect the eﬀect of the substitutions of $G$ on the remaining $n - k$ symbols, the group $G$ will reduce to a transitive group $H$ of degree $k$ . The group $G$ is isomorphic with the group $H$ ; for if we take as the substitutions of $G$ , that correspond to a given substitution of $H$ , those which produce the same permutation of the symbols $a_{1}$ , $a_{2}$ , …, $a_{k}$ as that produced by the substitution of $H$ , then to the product of any two substitutions of $G$ will correspond the product of the corresponding two substitutions of $H$ . The isomorphism thus shewn to exist may be simple or multiple. In the former case, the order of $H$ is the same as that of $G$ ; in the latter case, the substitutions of $G$ which correspond to the identical substitution of $H$ , i.e. those substitutions of $G$ which change none of the symbols $a_{1}$ , $a_{2}$ , …, $a_{k}$ form a self-conjugate sub-group.

We will consider in particular an intransitive group $G$ which interchanges the symbols in two transitive sets; these we will refer to as the $α$ ’s and the $β$ ’s. Let $G_{α}$ and $G_{β}$ be the two groups transitive in the $α$ ’s and $β$ ’s respectively, to which $G$ reduces when we alternately leave out of account the eﬀect of the substitutions on the $β$ ’s and the $α$ ’s. Also let $g_{α}$ and $g_{β}$ be the self-conjugate sub-groups of $G$ , which keep respectively all the $β$ ’s and all the $α$ ’s unchanged; and denote the group ${g_{α}, g_{β}}$ by $g$ . This last group $g$ , which is the direct product of $g_{α}$ and $g_{β}$ , is self-conjugate in $G$ , since it is generated by the two self-conjugate groups $g_{α}$ and $g_{β}$ . Now $g_{α}$ is self-conjugate not only in $G$ but also in $G_{α}$ ; for $G_{α}$ permutes the $α$ ’s in the same way that $G$ does, while any substitution of $g_{α}$ , not aﬀecting the $β$ ’s, is necessarily permutable with every substitution performed on the $β$ ’s. The group $G_{α}$ is simply isomorphic with the group $\frac{G}{g_{β}}$ , and $G_{β}$ with $\frac{G}{g_{α}}$ ; hence, using $n_{H}$ to denote the order of a group $H$ ,

n_{G} = n_{G_{α}} n_{g_{β}} = n_{G_{β}} n_{g_{α}} .

Let the substitutions of

G

be now divided into sets in respect of the self-conjugate sub-group

g

, so that

G = g, S g, T g, \dots .

The group $\frac{G}{g}$ is deﬁned by the laws according to which these sets combine among themselves, the sets being such that, if any substitution of one set be multiplied by any substitution of a second set, the resulting substitution will belong to a deﬁnite third set.

If we now neglect the eﬀect of the substitutions on the symbols $β$ , the group $G$ reduces to $G_{α}$ and $g$ reduces to $g_{α}$ , and hence

G_{α} = g_{α}, S_{α} g_{α}, T_{α} g_{α}, \dots,

where

S_{α}

T_{α}

, … represent the substitutions

S

T

, …, so far as they aﬀect the

α

’s. Moreover the substitutions in the diﬀerent sets into which

G_{α}

is thus divided must be all distinct since, by the preceding relations between the orders of the groups, their number is just equal to the order of

G_{α}

. Hence

\frac{G_{α}}{g_{α}}

is deﬁned by the laws according to which these sets of substitutions combine. But if

S g \cdot T g = U g,

then necessarily

S_{α} g_{α} \cdot T_{α} g_{α} = U_{α} g_{α},

and therefore, ﬁnally, the three groups

\frac{G}{g}

\frac{G_{α}}{g_{α}}

, and

\frac{G_{β}}{g_{β}}

are simply isomorphic.

115. The relation of simple isomorphism between $\frac{G_{α}}{g_{α}}$ and $\frac{G_{β}}{g_{β}}$ thus arrived at establishes between the groups $G_{α}$ and $G_{β}$ an isomorphism of the most general kind (§ 32).

To every operation of $G_{α}$ correspond $n_{g_{β}}$ operations of $G_{β}$ , and to every operation of $G_{β}$ correspond $n_{g_{α}}$ operations of $G_{α}$ ; so that to the product of any two operations of $G_{α}$ (or $G_{β}$ ) there corresponds a deﬁnite set of $n_{g_{β}}$ operations of $G_{β}$ (or $n_{g_{α}}$ operations of $G_{α}$ ).

Returning now to the intransitive group $G$ , its genesis from the two transitive groups $G_{α}$ and $G_{β}$ , with which it is isomorphic, may be represented as follows. The $n_{g_{α}}$ to $n_{g_{β}}$ correspondence, such as has just been described, having been established between the groups $G_{α}$ and $G_{β}$ , each substitution of $G_{α}$ is multiplied by the $n_{g_{β}}$ substitutions that correspond to it in $G_{β}$ . The set of $n_{G_{α}} n_{g_{β}}$ substitutions so obtained form a group, for

S_{α} S_{β} \cdot S' S' = S_{α} S' \cdot S_{β} S' = S'' S'',

where, if

S_{β}

S'

are substitutions corresponding to

S_{α}

S'

, then

S''

is a substitution corresponding to

S''

. Moreover, this group may be equally well generated by multiplying every one of the substitutions of

G_{β}

by the

n_{g_{α}}

corresponding substitutions of

G_{α}

; and by a reference to the representations of

G

G_{α}

and

G_{β}

, as divided into sets of substitutions given above, it is immediately obvious that all these substitutions occur in

G

. Hence, as their number is equal to the order of

G

, the group thus formed coincides with

G

116. The general result for any intransitive group, the simplest case of which has been considered in the two last paragraphs, may be stated in the following form:—

THEOREM VI. If $G$ is an intransitive group of degree $n$ which permutes the $n$ symbols in $s$ transitive sets, and if (i) $G_{r}$ is what $G$ becomes when the substitutions of $G$ are performed on the $r$ th set of symbols only, (ii) $Γ_{r}$ is what $G$ becomes when the substitutions of $G$ are performed on all the sets except the $r$ th, (iii) $g_{r}$ is that sub-group of $G$ which changes the symbols of the $r$ th set only, (iv) $γ_{r}$ is that sub-group of $G$ which keeps all the symbols of the $r$ th set unchanged: then the groups $\frac{G_{r}}{g_{r}}$ and $\frac{Γ_{r}}{γ_{r}}$ are simply isomorphic, and $n_{r}$ , $ν_{r}$ being the orders of $g_{r}$ , $γ_{r}$ , an $n_{r}$ to $ν_{r}$ correspondence is thus established between the substitutions of the groups $G_{r}$ and $Γ_{r}$ . Moreover, the substitutions of $G$ are given, each once and once only, by multiplying each substitution of $G_{r}$ by the $ν_{r}$ substitutions of $Γ_{r}$ that correspond to it⁴⁷.

It is not necessary to give an independent proof of this theorem, since if, in the discussion of the two preceding paragraphs, $G_{α}$ , $G_{β}$ , $g_{a}$ , $g_{b}$ , $g$ be replaced by $G_{r}$ , $Γ_{r}$ , $g_{r}$ , $γ_{r}$ , ${g_{r}, γ_{r}}$ , it will be found each step of the process there carried out may be repeated without alteration.

If we regard $G_{α}$ and $G_{β}$ as two given transitive groups in distinct sets of symbols, the determination of all the intransitive groups in the combined symbols, which reduce to $G_{α}$ or $G_{β}$ when the symbols of the second or ﬁrst set are neglected, involves a knowledge of the composition of the two groups. To each distinct $m$ to $n$ isomorphism, that can be established between the two groups, there will correspond a distinct intransitive group. If $G_{α}$ is a simple group, containing therefore only itself and identity self-conjugately, then to each substitution of $G_{β}$ there must correspond either one or all of the substitutions of $G_{α}$ ; and the former can be the case only when $G_{β}$ contains a self-conjugate sub-group $H$ , such that $\frac{G_{β}}{H}$ is simply isomorphic with $G_{α}$ . Hence, if the order of $G_{β}$ is less than twice the order of $G_{α}$ , the only possible intransitive group is the direct product of $G_{α}$ and $G_{β}$ , unless $G_{β}$ is simply isomorphic with $G_{α}$ .

117. In illustration of the preceding paragraphs, we will determine the number of distinct intransitive groups of degree $7$ , when the symbols are interchanged in transitive sets of $4$ and $3$ respectively. The four symbols will be referred to as the $α$ ’s, and the three symbols as the $β$ ’s.

If a transitive group of degree $4$ contains operations of order $3$ , it must be either the symmetric or the alternating group. If it contains no operation of order $3$ , its order must be either $8$ or $4$ . By Sylow’s theorem, the symmetric group of degree $4$ , being of order $24$ , contains a single set of conjugate sub-groups of order $8$ , so that there is only one type of transitive group of degree $4$ and order $8$ . This is given by

S = (1234), T = (13),

so that

S^{4} = 1, T^{2} = 1, T S T = S^{- 1} .

This group contains three self-conjugate sub-groups of order $4$ , namely,

\begin{matrix} (i) & 1, & (1234), & (13) (24), & (1432), \\ (ii) & 1, & (12) (34), & (13) (24), & (14) (23), \\ (iii) & 1, & (13), & (13) (24), & (24) . \end{matrix}

The two latter are simply isomorphic; but as substitution groups, they are of distinct form. Hence for $G_{α}$ in the construction of the intransitive group, we may take either $G_{24}$ , the symmetric group of the $α$ ’s, or $G_{12}$ , the alternating group of the $α$ ’s, or $G_{8}$ , the above group of order $8$ , or ﬁnally $G_{4}$ , $G'$ , $G''$ , the above three groups of order $4$ . The only transitive groups of $3$ symbols are $G_{6}$ , the symmetric group, and $G_{3}$ , the alternating group: one of these must be taken for $G_{β}$ .

I. $G_{α} = G_{24}$ .

The only self-conjugate sub-groups of $G_{24}$ are $G_{12}$ and $G'$ . Also $\frac{G_{24}}{G_{12}}$ is a group of order $2$ ; and it may easily be veriﬁed that $\frac{G_{24}}{G'}$ is simply isomorphic with the symmetric group of degree $3$ .

Hence (i) if $G_{β}$ is $G_{6}$ , we may take

\begin{array}{l} g_{α} & = G_{24}, & g_{β} & = G_{6}, & so that & n_{G} & = 144, \\ g_{α} & = G_{12}, & g_{β} & = G_{3}, & ” & n_{G} & = 72, \\ g_{α} & = G', & g_{β} & = 1, & ” & n_{G} & = 24; \\ and (ii) if G_{β} is G_{3}, we must take \\ g_{α} & = G_{24}, & g_{β} & = G_{3}, & giving & n_{G} & = 72 . \end{array}

II. $G_{α} = G_{12}$ .

The only self-conjugate sub-group of $G_{12}$ is $G'$ ; and $\frac{G_{12}}{G'}$ is a cyclical group of order $3$ .

Hence (i) if $G_{β}$ is $G_{6}$ , we must take

\begin{array}{l} g_{α} & = G_{12}, & g_{β} & = G_{6}, & giving & n_{G} & = 72; \\ and (ii) if G_{β} is G_{3}, we may take \\ g_{α} & = G_{12}, & g_{β} & = G_{3}, & giving & n_{G} & = 36, \\ o r g_{α} & = G', & g_{β} & = 1, & ” & n_{G} & = 12 . \end{array}

III. $G_{α} = G_{8}$ .

The self-conjugate sub-groups of $G_{8}$ , of order $4$ , are determined above.

If (i) $G_{β}$ is $G_{6}$ , we may take

\begin{array}{l} g_{α} & = G_{8}, & g_{β} & = G_{6}, & giving & n_{G} = 48, \\ g_{α} & = G_{4}, & g_{β} & = G_{3}, & ” & n_{G} = 24, \\ g_{α} & = G', & g_{β} & = G_{3}, & ” & n_{G} = 24, \\ g_{α} & = G'', & g_{β} & = G_{3}, & ” & n_{G} = 24 . \end{array}

The two latter groups are simply isomorphic; but regarded as substitution groups, they are of distinct forms.

If (ii) $G_{β}$ is $G_{3}$ , we must take

g_{α} = G_{8}, g_{β} = G_{3}, giving n_{G} = 24 .

IV. $G_{α} = G_{4}$ .

If (i) $G_{β}$ is $G_{6}$ , we may take

g_{α} = G_{4}, g_{β} = G_{6}, giving n_{G} = 24,

g_{α} = G_{2}, g_{β} = G_{3}, ” n_{G} = 12;

G_{2}

representing the group

{1, (13) (24)}

If (ii) $G_{β}$ is $G_{3}$ , we must take

g_{α} = G_{4}, g_{β} = G_{3}, giving n_{G} = 12 .

V. $G_{α} = G'$ .

There are, exactly as in the last case, three possibilities: $G'$ taking the place of $G_{4}$ . These groups are not however simply isomorphic with the preceding three.

VI. $G_{α} = G''$ .

There are in this case four possibilities. Of these three correspond to those of IV, $G''$ taking the place of $G_{4}$ . The remaining one is given by $G_{β} = G_{6}$ , $g_{β} = G_{3}$ , $g_{α} = G'$ , where $G'$ represents the group ${1, (13)}$ . Regarded as substitution groups all these are of distinct form from the groups of V.

There are thus $22$ distinct intransitive substitution groups of degree $7$ , in which the symbols are interchanged transitively in two sets of $4$ and $3$ respectively.

118. Let $ν_{r}$ ( $r = 0, 1, 2, \dots, n$ ) be the number of substitutions of a group of degree $n$ and order $N$ which leave exactly $r$ symbols unchanged, so that

N = \sum_{r = 0}^{r = n} ν_{r} .

Suppose ﬁrst that the group is transitive; and in a sub-group, which keeps one symbol unchanged, let $ν'$ ( $r = 1, 2, \dots, n$ ) be the number of substitutions that leave exactly $r$ symbols unchanged, so that

\frac{N}{n} = \sum_{r = 1}^{r = n} ν' .

Each of the $n$ sub-groups, which leave a single symbol unchanged, have $ν'$ substitutions which leave exactly $r$ symbols unchanged; and each of these substitutions belong to $r$ sub-groups which leave one symbol unchanged. Hence

n ν' = r ν_{r},

and therefore

N = \sum_{r = 1}^{r = n} r ν_{r};

or the number of unchanged symbols in all the substitutions of a transitive group is equal to the order of the group.

Suppose, next, that the group is intransitive; and consider a set of $s$ symbols among the $n$ , which are permuted transitively among themselves by the operations of the group. Let $N_{1}$ be the order of the self-conjugate sub-group $H_{1}$ , which leaves unchanged each of this set of $s$ symbols. Then if we consider the eﬀect of the substitutions on this set of $s$ symbols only, the group reduces to a transitive group of order $\frac{N}{N_{1}}$ with which the original group is multiply isomorphic. If $S'$ is any substitution of this group of order $\frac{N}{N_{1}}$ , and if $S H_{1}$ denote the corresponding $N_{1}$ operations of the original group, then every substitution of the set $S H_{1}$ produces the same eﬀect on the $s$ symbols that $S'$ produces. Now the number of unchanged symbols in all the substitutions of the transitive group of degree $s$ and order $\frac{N}{N_{1}}$ is $\frac{N}{N_{1}}$ ; therefore, in all the substitutions of the original group, the number of symbols of the set of $s$ that remain unchanged is $N$ . The same reasoning applies to each separate set of the $n$ symbols, which are permuted transitively among themselves by the operations of the group. Hence if there are $t_{1}$ such transitive sets, the total number of symbols which remain unchanged in all the substitutions of the group is $N t_{1}$ ; or

N t_{1} = \sum_{r = 1}^{r = n} r ν_{r} .

119. The formula just obtained is the ﬁrst of a series of similar formulæ, due to Herr Frobenius,⁴⁸ which are capable of many useful applications.

Consider the symbol $(a_{1}, a_{2}, \dots, a_{p})$ , where the letters are $p$ distinct letters chosen from the $n$ which are operated on by the group, the sequence in which the $p$ letters are arranged being regarded as essential. The number of such symbols that can be formed from the $n$ letters is $n (n - 1) \dots (n - p + 1)$ . Every substitution of the group interchanges this set of symbols among themselves; and no substitution can leave one of the symbols unchanged unless it leaves each of the letters forming it unchanged. Moreover no substitution of the group, other than identity, can leave each of the set of symbols unchanged. Hence the group can be expressed as a substitution group in this set of $n (n - 1) \dots (n - p + 1)$ symbols. Every substitution of the group which leaves exactly $r$ letters unchanged will, if $r < p$ , leave none of the set of symbols unchanged; while if $r \geq p$ , it will leave exactly

r (r - 1) \dots (r - p + 1)

unchanged. Hence, if the set of symbols are interchanged by the substitutions of the group in

t_{p}

transitive sets, then

N t_{p} = \sum_{r = p}^{r = n} \frac{r!}{r - p!} ν_{r} .

From the symbol $(a_{1}, a_{2}, \dots, a_{p})$ , containing $p$ letters, may be formed $n - p$ symbols containing $p + 1$ letters, by adding any one of the remaining $n - p$ letters in the last place. If the symbol $(a_{1}, a_{2}, \dots, a_{p})$ is one of a transitive set of $s$ symbols, to these there will correspond $s (n - p)$ symbols of $p + 1$ letters. No symbol of $p + 1$ letters, which is not included among these $s (n - p)$ symbols, can enter into a transitive set with any one of the $s (n - p)$ ; since if it did, the $s$ symbols of $p$ letters would not form a transitive set. Hence the $s (n - p)$ symbols must form, by themselves, a number of transitive sets of the symbols of $p + 1$ letters; and this number clearly cannot be less than $1$ nor greater than $n - p$ . Accordingly, to every transitive set of the symbols of $p$ letters, there correspond $x$ ( $1 \leq x \leq n - p$ ) transitive sets of the symbols of $p + 1$ letters; and therefore

t_{p} \leq t_{p + 1} \leq (n - p) t_{p} .

Ex. 1. If $t_{p}$ and $t_{p + 1}$ are equal and if $p < n - 1$ , shew that $t_{p + 1}$ is unity and that the group is $(p + 1)$ -ply transitive.

Ex. 2. Apply the method of § 119 to shew that no substitution, except identity, of a $k$ -ply transitive group, which does not contain the alternating group, can displace less than $2 k - 2$ letters.

Note to § 108.

The results of M. Jordan, stated on p. 459, may be established as follows. Let $G$ be a quadruply transitive group of degree $n$ and order $n (n - 1) (n - 2) (n - 3)$ , so that $n - 2$ is the power of a prime. There is a single operation of $G$ which changes any four symbols into any other four symbols. Let $a$ , $b$ , $c$ , $d$ be four of the symbols operated on by $G$ . The operations of $G$ which permute these symbols among themselves form a sub-group $H$ , simply isomorphic with the symmetric group of degree $4$ . Suppose that the remaining $n - 4$ symbols are permuted by $H$ in transitive sets of $n_{1}$ , $n_{2}$ , … symbols each.

The only groups with which $H$ is multiply isomorphic are (i) the symmetric group of degree $3$ , (ii) a group of order $2$ . If then, when we consider the eﬀect of $H$ on a set of $n_{1}$ symbols which are permuted transitively by it, the group of degree $n_{1}$ so obtained is one with which $H$ is multiply isomorphic, this group must be either the symmetric group of degree $3$ or a group of order $2$ . Hence $n_{1}$ must be either $6$ , $3$ or $2$ . Since in this case $H$ will contain operations leaving all the $n_{1}$ symbols unchanged, the value $6$ for $n_{1}$ is inadmissible. If $n_{1}$ is $3$ , the operations of $H$ , which give the substitutions

1, (a b) (c d), (a d) (b c), (a c) (b d),

a

b

c

d

, leave the

3

symbols unchanged; and if

n_{1}

2

, the operations of

H

which give all the even substitutions of

a

b

c

d

, leave the

2

symbols unchanged.

If, on the other hand, when we consider the eﬀect of $H$ on the set of $n_{1}$ symbols only, the transitive group of degree $n_{1}$ so obtained is simply isomorphic with $H$ , then $n_{1}$ must be either $4$ , $6$ , $8$ , $12$ or $24$ . In this case, the value $4$ for $n_{1}$ is inadmissible. In fact, if $n_{1}$ were $4$ the operation of $H$ which leaves $c$ and $d$ unchanged would also leave two of the $n_{1}$ symbols unchanged; and this is impossible since no operation of $H$ , except identity, can leave more than $3$ symbols unchanged. For a similar reason, the value $12$ for $n_{1}$ is inadmissible; while, if $n_{1}$ is $6$ , the sub-group that keeps one of the $n_{1}$ symbols unchanged must be cyclical.

The only other possible value for $n_{1}$ is unity.

Suppose, ﬁrst, that $n_{1}$ is $2$ . If any of the remaining numbers $n_{2}$ , $n_{3}$ , … diﬀer from $24$ , it may be shewn immediately that $H$ contains operations which keep more than $3$ symbols ﬁxed. Hence in this case $n$ is congruent to $6 (mod 24)$ ; and since $n - 2$ cannot then be a power of a prime unless $n = 6$ , this case gives the alternating group of degree $6$ .

Next, suppose that $n_{1}$ is $3$ . The only admissible values for $n_{2}$ , $n_{3}$ , … are $8$ and $24$ . In this case, the sub-group of $H$ which keeps all the $n_{1}$ ( $= 3$ ) symbols unchanged is a non-cyclical sub-group of order $4$ . But we have seen in § 105 that, if $n - 3$ is even, a sub-group of order $n - 3$ which keeps $3$ symbols unchanged can only have a single operation of order $2$ . Hence this case cannot occur.

Next, suppose that $n_{1}$ is $8$ . The only admissible values for $n_{2}$ , $n_{3}$ , … are again $24$ . This case cannot occur since no number congruent to $10, (mod 24)$ , can be a power of a prime.

The only remaining possibilities are:

\begin{array}{l} (i) & n_{1} & = n_{2} = \dots \dots \dots \dots \dots & = 24, \\ (ii) & n_{1} & = 1, n_{2} = n_{3} = \dots \dots & = 24, \\ (iii) & n_{1} & = 6, n_{2} = n_{3} = \dots \dots & = 24, \\ (iv) & n_{1} & = 1, n_{2} = 6, n_{3} = \dots & = 24, \\ (v) & n_{1} & = 1, n_{2} = 6, n_{3} = \dots & = 0, \\ (vi) & n_{1} & = 1, n_{2} = n_{3} = \dots \dots & = 0 . \end{array}

The ﬁrst of them cannot occur, since then $n - 2$ is not the power of a prime. In the second case, an operation of $H$ which leaves $c$ and $d$ unchanged would be of the form

(a b) (α β) (γ δ) \dots,

where there are

\frac{1}{2} (n - 3)

independent transpositions; while an operation of

H

, of order

2

, which leaves none of the symbols

a

b

c

d

unchanged, will consist of the product of

\frac{1}{2} (n - 1)

independent transpositions. Now the operation

(a b) (α β) (γ δ) \dots

occurs in the group, conjugate to

H

, which permutes

a

b

α

β

, among themselves; and as an operation of this group, it must be the product of

\frac{1}{2} (n - 1)

independent transpositions. This is a contradiction: hence this case cannot occur.

In case (iii), let $1$ , $2$ , $3$ , $4$ , $5$ , $6$ be the six symbols that are permuted transitively. The self-conjugate sub-group of $H$ of order $4$ will consist of identity and the three substitutions

\begin{matrix} (a b) (c d) (34) (56) (α β) (γ δ) \dots, \\ (a c) (b d) (56) (12) (α γ) (β δ) \dots, \\ (a d) (b c) (12) (34) (α δ) (β γ) \dots . \end{matrix}

This sub-group will also occur as the self-conjugate sub-group of order $4$ of the group, conjugate to $H$ , which permutes $α$ , $β$ , $γ$ , $δ$ among themselves. If $S$ , $S'$ are two operations, of order $3$ , of these sub-groups which give the same permutation of $1$ , $2$ , $3$ , $4$ , $5$ , $6$ , then $S S'^{- 1}$ is an operation of $G$ , distinct from identity, which keeps the six symbols unchanged. Hence this case cannot occur. Precisely the same reasoning applies to case (iv).

Finally then, cases (v) and (vi), in which $n$ is respectively $11$ and $5$ are the only remaining possibilities.

When $n$ is $5$ , $G$ is the symmetric group of degree $5$ .

When $n$ is $11$ , the group $G$ , if it exists, is of degree $11$ and order $11 \cdot 10 \cdot 9 \cdot 8$ . A sub-group of order $8$ which keeps three symbols ﬁxed must contain a single operation of order $2$ ; hence it must either be cyclical or of the type given in Theorem V, § 63. When expressed in $8$ symbols, this is generated by

(1254) (3867) and (1758) (2643),

while we may take a cyclical group of order

8

to be generated by

(12835476) .

It is easy to verify that each of these substitutions transforms the group of order $9$ , generated by

(123) (456) (789) and (147) (258) (369),

into itself.

If we now apply the method of § 109, we ﬁnd that each of these doubly transitive groups of degree $9$ is contained in a triply transitive group of degree $10$ ; a repetition of the same process of trial shews that, while the group

{(123) (456) (789), (12835476)}

is not contained in a quadruply transitive group of degree

11

and order

11 \cdot 10 \cdot 9 \cdot 8

, the group

{(123) (456) (789), (1254) (3867), (1758) (2643)}

and the two substitutions

(a 2) (58) (64) (79), (a b) (57) (68) (49)

actually generate such a group.

A further trial will shew that this group and the substitution

(b c) (47) (58) (69)

generate a group of degree

12

and order

12 \cdot 11 \cdot 10 \cdot 9 \cdot 8

; but that there is no group of degree

13

which contains the last group as the sub-group that keeps one symbol ﬁxed.

The three substitutions, of order two, just given generate that sub-group of order $24$ , of the transitive group of degree $11$ and order $11 \cdot 10 \cdot 9 \cdot 8$ in the symbols

a, b, c, 2, 3, 4, 5, 6, 7, 8, 9,

which permutes

a

b

c

2

among themselves.

If $k ≮ 4$ , a $k$ -ply transitive group, of degree $n$ and order $n (n - 1) \dots (n - k + 1)$ , must contain a quadruply transitive group of degree $n - k + 4$ and order $(n - k + 4) (n - k + 3) (n - k + 2) (n - k + 1)$ . Hence, if the group is neither the alternating group nor the symmetric group of degree $n$ , it must be either the group of degree $11$ or the group of degree $12$ that have been determined above.

Note to § 110.

It may be shewn that, with a single exception when $n = 12$ , the inequality (p. 470)

k ≯ \frac{1}{3} n + 1

may be replaced by

k < \frac{1}{3} n + 1 .

Since $k$ is an integer, it is only necessary to consider the case in which $n$ is a multiple of $3$ , so that we may write $3 m$ for $n$ . If, in this case, $k = m + 1$ , then $2 k - 2 = 2 m$ ; and a $(m + 1)$ -ply transitive group of degree $3 m$ , which does not contain the alternating group, can therefore have no substitution which displaces fewer than $2 m$ symbols. Its order must therefore be $3 m (3 m - 1) \dots (2 m + 1) 2 m$ . From M. Jordan’s results, which have just been proved, such a group exists only when $n = 12$ ; and therefore when $n$ is not $12$ , a $k$ -ply transitive group of degree $n$ , which does not contain the alternating group, can only exist if $k < \frac{1}{3} n + 1$ .

ptail

top

Chapter VIII.On Substitution-Groups: Transitive and Intransitive Groups.

Note to § 108.

Note to § 110.

Chapter VIII.
On Substitution-Groups: Transitive and Intransitive Groups.