Chapter X.
On Substitution Groups: Transitivity and Primitivity: (Concluding Properties.)

T he determination of all distinct transitive sub-groups of the symmetric group of $n$ symbols has been carried out for values of $n$ up to $12$⁵³. This investigation, if carried out for sufficiently great values of $n$, would involve the expression of all types of group in all possible transitive forms.

From the point of view of one of the chief problems of pure group-theory, namely, the determination of all distinct types of group of a given order, this analysis of the symmetric group of $n$ symbols is not a succinct process, as it continually involves the redetermination of groups which have been already obtained. Thus a simple group of degree $mn$, in which the symbols are permuted in $m$ imprimitive systems of $n$ each, would in this analysis have been already obtained as a group of degree $m$. With reference then to the more restricted problem of determining all types of simple groups, it would certainly be sufficient to find all primitive sub-groups of the symmetric group.

139. We shall proceed to determine a superior limit to the order of a primitive group of degree $n$, other than the alternating or the symmetric group.

Let $G$ be a primitive group of degree $n$, and suppose that $G$ contains a sub-group $H$ which leaves $n-m$ symbols unchanged and is transitive in the remaining $m$. Since $G$ is primitive, $H$ and the sub-groups conjugate to it must generate a transitive self-conjugate sub-group of $G$; and therefore there must be some sub-group $H\prime$, conjugate to $H$, such that the $m$ symbols operated on by $H$ and the $m$ operated on by $H\prime$ are not all distinct. Suppose $H\prime$ is chosen so that these two sets of $m$ symbols have as great a number in common as possible, say $s$; and represent by

where $r+s=m$, the symbols operated on by $H$ and $H\prime$ respectively. Then is a transitive group in the $2r+s$ symbols $\alpha$, $\beta$, and $\gamma$, which leaves unaltered all the remaining symbols of $G$.

If $S$ is an operation of $H$ which changes ${\alpha }_2$ into ${\alpha }_1$, $S^{-1}H\prime S$ does not affect ${\alpha }_1$. Hence, unless $S$ interchanges the $\alpha$’s among themselves, the $m$ symbols operated on by $H\prime$ and the $m$ operated on by $S^{-1}H\prime S$ will have more than $s$ in common. Every operation of $H$ which changes one $\alpha$ into another must therefore interchange all the $\alpha$’s among themselves; hence $H$ must be imprimitive.

If then $H$ is primitive, $s$ must be equal to $m-1$. In any case, if $s=m-1$,  is a doubly transitive and therefore primitive group of degree $m+1$, which leaves the remaining $n-m-1$ symbols of $G$ unchanged. We may reason about this sub-group as we have done about $H$. Among the sub-groups conjugate to , there must be one at least which operates on $m$ of the symbols displaced by . This, with , generates a triply transitive group of degree $m+2$, which leaves $n-m-2$ symbols unchanged. Proceeding thus, we find finally that $G$ itself must be -ply transitive.

140. If $s$ is less than $m-1$, we may again deal with the sub-group , or $H_1$, exactly as we have dealt with $H$. It is a transitive group of degree $m_1$ ($>m$), which leaves $n-m_1$ symbols unchanged. If, among the sub-groups conjugate to $H_1$, none operates on more than $s_1$ of the symbols affected by $H_1$, and if $H\prime$ is a suitably chosen conjugate sub-group, then is a transitive group of degree $2m_1-s_1$, which leaves $n-2m_1+s_1$ symbols unchanged. Continuing this process, we must, before arriving at a group of degree $n$, reach a stage at which the number $s_r$ is equal to $m_r-1$.

For suppose, if possible, that among the groups conjugate to $K$, of degree $\rho +\sigma$, none displaces more than $\sigma$ of the symbols acted on by $K$, while at the same time $2\rho +\sigma =n$. If

are the symbols affected by $K$ and $K\prime$ respectively, then since $G$ is primitive, it must contain an operation $S$ which changes ${\alpha }_1$ into ${\alpha }_2$ without at the same time changing all the $\alpha$’s into $\alpha$’s. If then we transform $K\prime$ by $S$, the two groups $K\prime$ and $S^{-1}K\prime S$ must operate on more than $\sigma$ common symbols, contrary to supposition.

Hence $G$ must in this case certainly contain a transitive sub-group of degree $n-1$, and therefore is itself at least doubly transitive⁵⁴.

141. Returning to the case in which $H$ is primitive and $G$ therefore -ply transitive, we at once obtain an inferior limit for $m$. We have seen, in fact, in Theorem IV, § 110, that a group of degree $n$, other than the alternating or the symmetric group, cannot be more than -ply transitive. Hence

THEOREM I. A primitive group $G$ of degree $n$, which has a sub-group $H$ that keeps $n-m$ symbols unchanged and is transitive in the remaining $m$ symbols, is at least doubly transitive. If $H$ is primitive and $G$ does not contain the alternating group, $m$ cannot be less than $\frac{2}{3}n$, and $G$ is -ply transitive.

Corollary. The order of a primitive group of degree $n$ cannot exceed $\frac{n!}{2\cdot 3\dots p}$, where $2$, $3$, … $p$ are the distinct primes which are less than $\frac{2}{3}n$.

If $q^{\alpha }$ is the highest power of a prime $q$ that divides $n!$, the sub-groups of order $q^{\alpha }$ of the symmetric group form a single conjugate set, and each of them must contain circular substitutions of order $q$. Hence if $q<\frac{2}{3}n$, it follows by the theorem that no primitive group of degree $n$, other than the alternating or the symmetric group, can contain a sub-group of order $q^{\alpha }$; and therefore $q^{\alpha -1}$ is the highest power of $q$ that can divide the order of the group.

142. The ratio of $2\cdot 3\dots p$ to $n$ increases rapidly as $n$ increases, and it is at once obvious that, when $n>7$, this ratio is greater than unity; hence for values of $n$ greater than $7$, the symmetric group can have no primitive sub-group of order .

The order of the greatest imprimitive sub-group of the symmetric group is $a!{\left(\frac{n}{a}!\right)}^{\alpha }$, where $a$ is the smallest factor of $n$. When $n>4$, this is less than .

The order of the greatest intransitive sub-group of the symmetric group, other than the sub-groups that keep one symbol fixed, is . This is always less than .

Hence when $n>7$, the only sub-groups of order  of the symmetric group are the sub-groups which each keep one symbol fixed; and these form a conjugate set of $n$ sub-groups.

When $n=7$, a sub-group of order  must be intransitive, and therefore the same result holds in this case; this also is true when $n$ is $3$, $4$, or $5$.

Lastly, when $n=6$, there may, by the foregoing theorem, be primitive sub-groups of order $5!$. That such sub-groups actually exist may be verified at once by considering the symmetric group of $5$ symbols. This group contains $6$ cyclical sub-groups of order $5$, and each of them is self-conjugate in a sub-group of order $20$. Hence, since the only self-conjugate sub-group contained in the symmetric group of degree $5$ is the corresponding alternating group, the symmetric group of degree $5$ can be expressed as a doubly transitive group of degree $6$. The symmetric group of degree $6$ therefore contains a set of $6$ conjugate doubly transitive sub-groups of order $5!$, which are simply isomorphic with the intransitive sub-groups that each keep one symbol fixed. Finally, if the $12$ sub-groups of order $5!$, which are thus accounted for, do not exhaust all the sub-groups of this order, any other would have in common with each of the $12$ a sub-group of order $20$; and therefore the operations of order $3$ contained in it would be distinct from those in the previous $12$. But these clearly contain all the operations of order $3$ of the symmetric group, and therefore there can be no other sub-groups of order $5!$. Hence:—

THEOREM II. The symmetric group of degree $n$ $$

contains $n$ and only $n$ sub-groups of order , which form a single conjugate set. The symmetric group of degree $6$ contains $12$ sub-groups of order $5!$, which are simply isomorphic with one another and form two conjugate sets of $6$ each.

143. We shall now discuss certain further limitations on the order of a primitive group of given degree. Though it will be seen that these do not lead to general results, similar to that given by Theorem I, § 141, yet in many special cases they are of considerable assistance in determining the possible existence of groups of given orders and degrees.

We consider first a group $G$ of order $N$ and of prime degree $p$. If $G$ is not cyclical, it must contain substitutions which keep only one symbol unchanged. For let $P$ be a substitution of $G$ of order $p$. The only substitutions permutable with $P$ are its own powers (§ 107); and the only substitutions permutable with  are substitutions which keep one symbol unchanged and are regular in the remaining $p-1$ symbols (§ 112)⁵⁵. Now if the only substitutions permutable with  are its own, then  is one of $\frac{N}{p}$ conjugate sub-groups; and these contain $N\left(1-\frac{1}{p}\right)$ substitutions of order $p$. In this case, $G$ would contain exactly exactly $\frac{N}{p}$ substitutions whose orders are not divisible by $p$. But this is clearly impossible, since $\frac{N}{p}$ is the order of a sub-group which keeps one symbol unchanged, and there are $p$ such sub-groups. Hence there must be substitutions in $G$, other than those of , which are permutable with ; and each of these substitutions keeps one symbol unchanged.

It follows from § 134 that $G$, if soluble, must contain a self-conjugate sub-group of order $p$: therefore no group of prime degree $p$, which contains more than one sub-group of order $p$, can be soluble.

If $1+kp$ is the number of sub-groups of order $p$ contained in $G$, then

If both $p$ and are primes, the order of a group of degree $p$, which contains more than one sub-group of order $p$, must be divisible by . For if the order is not divisible by , the order of the sub-group, within which a sub-group of order $p$ is self-conjugate, must be $2p$. Now the substitutions of order $2$ in this sub-group consist of transpositions, so that they are odd substitutions. The group must therefore contain a self-conjugate sub-group in which these operations of order $2$ do not occur. In such a sub-group, the only operations permutable with those of a sub-group of order $p$ are its own; and we have seen that no such group can exist. The order of the group must therefore, as stated above, be divisible by .

144. Let $G$ be a primitive group of degree $n$ and order $N$; and let $p$ be a prime, which is a factor of $N$ but not of either $n$ or $n-1$. Moreover, suppose that $n$ is congruent to ; $\nu$ being less than $p$. If $n<p^2$, and if $p^{\alpha }$ is the highest power of $p$ which divides $N$, the sub-groups of order $p^{\alpha }$ must be Abelian groups of type . In fact, such a sub-group must be intransitive, and, since $n<p^2$, the number of symbols in each transitive system of the sub-group must be $p$. In any case the number of symbols left unchanged by a sub-group of order $p^{\alpha }$ is of the form $kp+\nu$.

Suppose now that, in a sub-group of order $\frac{N}{n}$ which leaves one symbol unchanged, a sub-group $H$ of order $p^{\alpha }$ is one of $\frac{N}{p^{\alpha }mn}$ conjugate sub-groups. Then each of the $n$ sub-groups that keep one symbol unchanged contains $\frac{N}{p^{\alpha }mn}$ sub-groups of order $p^{\alpha }$; and each sub-group of order $p^{\alpha }$ belongs to $kp+\nu$ sub-groups that keep one symbol unchanged. Hence $G$ contains sub-groups of order $p^{\alpha }$, and any one of them, say $H$, is contained self-conjugately in a sub-group $I$ of order . This sub-group $I$ must interchange transitively among themselves the $kp+\nu$ symbols left unchanged by $H$. For let $a$ and $b$ be any two of these symbols; and let $S$ be an operation which changes $a$ into $b$ and transforms $H$ into $H\prime$. There must be an operation $T$ which keeps $b$ unchanged and transforms $H\prime$ into $H$, since in the sub-group that keeps $b$ unchanged there is only one conjugate set of sub-groups of order $p^{\alpha }$. Then $ST$ changes $a$ into $b$ and transforms $H$ into itself; and therefore $I$ contains substitutions which change $a$ into $b$. Now it may happen that the existence of a sub-group such as $I$ requires that $G$ is either the alternating or the symmetric group. When this is the case, we infer that the order of a primitive group of degree $n$, other than the alternating or the symmetric group, cannot be divisible by $p$.

145. As a simple example, we will shew that the order of a group of degree $19$ cannot be divisible by $7$, unless it contains the alternating group. It follows from Theorem I, Corollary, § 141, that the order of a group of degree $19$, which does not contain the alternating group, cannot be divisible by a power of $7$ higher than the first, and that if the group contains a substitution of order $7$, the substitution must consist of two cycles of $7$ symbols each. The sub-group of order $7$ must therefore leave $5$ symbols unchanged; hence, by § 144, it must be contained self-conjugately in a sub-group whose order is divisible by $5$. Now (§ 83) a group of order $35$ is necessarily Abelian; so that the group of degree $19$ must contain a substitution of order $5$ which is permutable with a substitution of order $7$. Such a substitution of order $5$ must clearly consist of a single cycle, and its presence in a group of degree $19$ requires that the latter should contain the alternating group. It follows that, if a group of degree $19$ does not contain the alternating group, its order is not divisible by $7$.

As a second example, we will determine the possible forms for the order of a group of degree $13$, which does not contain the alternating group. It follows, from Theorem I, Corollary, § 141, that the order of such a group must be of the form $2^{\alpha }\cdot 3^{\beta }\cdot 5^{\gamma }\cdot 11^{\delta }\cdot 13$; where $\alpha$, $\beta$, $\gamma$, $\delta$ do not exceed $9$, $4$, $1$, $1$ respectively.

Suppose, first, that $\gamma$ is unity, if possible. A substitution of order $5$ must consist of two cycles of $5$ symbols each; and a sub-group of order $5$ must therefore be self-conjugate in a sub-group of order $15$. There is then a substitution of order $3$ which is permutable with a substitution of order $5$. Such a substitution must, as in the last example, consist of a single cycle; and its existence would imply that the group contains the alternating group. It follows that, for the group as specified, $\gamma$ must be zero.

Suppose, next, that $\delta$ is unity, if possible. The group is then (Theorem I, § 141) triply transitive; and the order of the sub-group, that keeps two symbols fixed and is transitive in the remaining $11$, is $2^{\alpha }\cdot 3^{\beta }\cdot 11$; and this sub-group must contain more than one sub-group of order $11$. We have seen in § 143 that no such group can exist. Therefore $\delta$ must be zero.

The two smallest numbers of the form $2^m{3}^n$ which are congruent to unity, , are $3^3$ and $2^4{3}^2$; and every number of this form, which is congruent to unity, , can be written . Hence the order of every group of order $13$, which contains no odd substitution, must be of the form , where $z$ is $2$, $3$ or $6$. Since $3^4$ is the highest power of $3$ that can divide the order of the group, the only admissible values of $x$ and $y$ are (i) $x=0$, $y=1$: (ii) $x=2$, $y=0$: (iii) $x=1$, $y=0$.

Suppose, first, that $x=0$, $y=1$. The order of the group is $2\cdot 3^3\cdot 13$, $3^4\cdot 13$, or $2\cdot 3^4\cdot 13$. There must be $13$ sub-groups of order $3^4$ (or $3^3$), and since $13$ is not congruent to unity, , there must be sub-groups of order $3^3$ (or $3^2$) common to some two sub-groups of order $3^4$ (or $3^3$). Such a sub-group must be self-conjugate (Theorem III, § 80). This case therefore cannot occur.

Next, suppose that $x=2$, $y=0$. Then $z$ must be $2$, and the order of the group is $2^9\cdot 3^4\cdot 13$. Now it is easy to verify that $2^9\cdot 3^4$ is not a possible order either for an intransitive or for an imprimitive group of degree $12$. The order of a sub-group of the group of degree $12$ which keeps one symbol fixed is $2^7\cdot 3^3$. This sub-group can have no substitution consisting of a single cycle of $3$ symbols, since no such substitution can occur in the original group. Hence it must permute the $11$ symbols in two transitive sets of $9$ and $2$ symbols respectively. It must therefore contain a self-conjugate sub-group of order $2^6\cdot 3^3$ which keeps $3$ of the $12$ symbols unchanged; and this sub-group must occur self-conjugately in $3$ of the $12$ sub-groups which keep one symbol unchanged. This however makes the group of degree $12$ imprimitive, contrary to supposition. Hence this case cannot occur.

Finally, then, the only possible values of $x$ and $y$ are $x=1$, $y=0$. The order of a group of degree $13$, which has more than one sub-group of order $13$ and no odd substitutions, is $2^5\cdot 3^2\cdot 13$, $2^4\cdot 3^3\cdot 13$, or $2^5\cdot 3^3\cdot 13$. The order of a group of order $13$ with odd substitutions will be twice one of the preceding three numbers.

A further and much more detailed examination would be necessary to determine whether groups of degree $13$ correspond to any or all of these orders. We shall see in Chapter XIV that there is a group of degree $13$ and order $2^4\cdot 3^3\cdot 13$; and M. Jordan⁵⁶ states that this is the only group of degree $13$ which contains more than one sub-group of order $13$.

Ex. If $n$ ($>3$) and $2n+1$ are primes, shew that there is no triply transitive group of degree $2n+3$ which does not contain the alternating group.

146. As a further illustration, and for the actual value of the results themselves, we proceed to determine all types of primitive groups for degrees not exceeding $8$.

(i) $n=3$.

The symmetric group of $3$ symbols has a single sub-group, viz. the alternating group. Both these groups are necessarily primitive.

(ii) $n=4$.

Since a group whose order is the power of a prime cannot (§ 124) be represented in primitive form, a primitive group of degree $4$ must contain $3$ as a factor of its order. Hence the only primitive groups of degree $4$ are the symmetric and the alternating groups.

(iii) $n=5$.

Since $5$ is a prime, every group of degree $5$ is a primitive group. The symmetric group of degree $5$ contains $6$ cyclical sub-groups of order $5$; therefore, by Sylow’s theorem, every group of degree $5$ must contain either $1$ or $6$ sub-groups of order $5$. Since the alternating group is simple, every sub-group that contains $6$ sub-groups of order $5$ must contain the alternating group. Hence, besides the alternating and the symmetric groups, we have only sub-groups which contain a sub-group of order $5$ self-conjugately. In such a group, an operation of order $5$ can be permutable with its own powers only. Hence (§ 112) the only sub-groups of the type in question other than cyclical sub-groups, are groups of orders $20$ and $10$. These are defined by

(iv) $n=6$.

If the order of a primitive group of degree $6$ is not divisible by $5$, the order must (§ 141) be equal to or be a factor of $2^3\cdot 3$. The order of a sub-group that keeps one symbol fixed is equal to or is a factor of $2^2$. Hence the sub-group must keep two symbols fixed, and therefore (§ 128) the group cannot be primitive. Hence the order of every primitive group of degree $6$ is divisible by $5$, and every such group is at least doubly transitive. The symmetric group contains $36$ sub-groups of order $5$; and hence, since no transitive group of degree $6$ can contain a self-conjugate sub-group of order $5$, every primitive group of degree $6$, which does not contain the alternating group, must have $6$ sub-groups of order $5$.

If $G$ is such a group, the sub-group of $G$ that keeps one symbol fixed is a transitive group of degree $5$ which has a self-conjugate sub-group of order $5$. If this transitive group of degree $5$ were cyclical, every operation of the doubly transitive group $G$ of order $30$ would displace all or all but one of the symbols. Since $6$ is not the power of a prime, this is impossible (§ 105). Hence the sub-group of $G$ which keeps one symbol fixed must be of one of the two types given above; and the order of $G$ must be $120$ or $60$. Now we have seen, in § 142, that the symmetric group of degree $6$ has a single conjugate set of primitive sub-groups of order $120$ and a single set of order $60$. Hence there is a single type of primitive group of degree $6$, corresponding to each of the orders $120$ and $60$. These are defined by

where the last two substitutions in each case generate a sub-group that keeps one symbol unchanged.

(v) $n=7$.

Every transitive group of degree $7$ is primitive; and if it does not contain the alternating group, its order must (§ 141) be equal to or be a factor of $7\cdot 6\cdot 5\cdot 4$. A cyclical sub-group of order $7$ must (footnote, p. 1107), in a group of degree $7$ that contains more than one such sub-group, be self-conjugate in a group of order $21$ or $42$. Now neither $20$ nor $40$ is congruent to unity, ; and therefore $5$ cannot be a factor of the order of such a group. Hence the order of a transitive group of degree $7$, that does not contain the alternating group, is equal to or is a factor of $7\cdot 6\cdot 4$. But $8$ is the only factor of $7\cdot 6\cdot 4$ which is congruent to unity, ; and therefore, if the group contains more than one sub-group of order $7$, its order must be equal to $7\cdot 6\cdot 4$ and it must contain $8$ sub-groups of order $7$.

Such a group must be doubly transitive; for if a sub-group of order $24$ interchanges the symbols in two intransitive systems, it is easily shewn that the group would contain substitutions displacing three symbols only, and therefore that it would contain the alternating group. A sub-group of degree $24$, transitive in $6$ symbols, must contain $4$ sub-groups of order $3$. For if it contained only one, it would necessarily have circular substitutions of $6$ symbols, and the group of order $7\cdot 6\cdot 4$ would have a self-conjugate sub-group of order $7\cdot 6\cdot 2$; which is not the case. Hence the sub-groups of order $24$ must be simply isomorphic with the symmetric group of $4$ symbols.

The actual construction of the group is now reduced to a limited number of trials. A group of degree $6$, simply isomorphic with the symmetric group of $4$ symbols, and containing no odd substitutions, may always be represented in the form

It appears on trial that the group generated by the first of these is not permutable with the sub-group of order $24$, while the groups generated by the other two are. There are therefore just two groups of order $7\cdot 6\cdot 4$ which contain the given group of order $24$. Now in the symmetric group of $7$ symbols, a sub-group of order $7\cdot 6\cdot 4$ must, from the foregoing discussion, be one of a set of $30$ conjugate sub-groups. These all enter in the alternating group; and therefore, in that group, they must form two sets of $15$ conjugate sub-groups each. Each of these contains $7$ sub-groups of the type

These groups are simple; for since they are expressed as transitive groups of degree $7$, there can be no self-conjugate sub-group whose order divides $24$, while it is evident that a self-conjugate sub-group that contains an operation of order $7$ must coincide with the group itself. Also since there are $8$ sub-groups of order $7$, these groups can be expressed as doubly transitive groups of eight symbols.

A group of degree $7$, which has only one sub-group of order $7$, must either be cyclical or be contained in the group of order $7\cdot 6$ given by § 112. Such groups are defined by

The simple group of order $168$, which here occurs as a transitive group of degree $7$, is the only simple group of that order. For, if possible, let there be a simple group $G$ of order $168$ and of a distinct type from the above. It certainly cannot be expressed as a group of degree $7$; and therefore it must have $21$ sub-groups of order $8$. If two of these sub-groups have a common sub-group of order $4$, it must be contained self-conjugately (§ 80) in a sub-group of order $24$ or $56$; and this is inconsistent with the suppositions made. If on the other hand, $2$ is the order of the greatest sub-group common to two sub-groups of order $8$, such a common sub-group of order $2$ must, on the suppositions made, be self-conjugate in a sub-group of order $12$. But a group of order $12$, which has a self-conjugate operation of order $2$, must have a self-conjugate sub-group of order $3$; and therefore $G$ would only contain $7$ sub-groups of order $3$, and could be expressed as a group of degree $7$; contrary to supposition. No other supposition is possible with regard to the sub-groups of order $8$, since $21$ is not congruent to unity, . Hence, finally, there is no simple group of order $168$ distinct from the group of degree $7$.

(vi) $n=8$.

The order of a primitive group of degree $8$, which does not contain the alternating group, cannot (§ 141) be divisible by $5$. Suppose, if possible, that the order of such a group is $2^{\alpha +3}\cdot 3$ ($\alpha =0,1,2,3$). A substitution of order $3$ must consist of two cycles; and therefore the sub-group of order $2^{\alpha }\cdot 3$, which keeps one symbol fixed, must interchange the others in two intransitive systems of $3$ and $4$ respectively. In this sub-group, a sub-group of order $3$ must be one of four conjugate sub-groups, and therefore $\alpha$ is either $2$ or $3$. Now a group of order $2^5\cdot 3$ or $2^6\cdot 3$ is soluble, as is seen at once by considering the sub-groups of order $2^5$ or $2^6$. Hence a primitive group of order $2^5\cdot 3$ or $2^6\cdot 3$ must contain a transitive self-conjugate sub-group of order $8$, whose operations are all of order $2$.

If $7$ is a factor of the order of the group, the group must be doubly transitive; and from the case of $n=7$, it follows that the possible orders are $8\cdot 7$, $8\cdot 7\cdot 2$, $8\cdot 7\cdot 3$, $8\cdot 7\cdot 6$, and $8\cdot 7\cdot 6\cdot 4$. Moreover, for the orders $8\cdot 7\cdot 2$ and $8\cdot 7\cdot 6$, the group contains odd substitutions and therefore it contains self-conjugate sub-groups of order $8\cdot 7$ and $8\cdot 7\cdot 3$ respectively.

A simple group of order $8\cdot 7\cdot 3$ is necessarily identical in type with the group of this order determined on p. 606; and a group of order $8\cdot 7\cdot 3$, which is not simple, is certainly soluble. Hence a composite group of order $8\cdot 7\cdot 3$, and a group of order $8\cdot 7\cdot 6$ which does not contain a simple sub-group of order $8\cdot 7\cdot 3$, must both, if expressible as primitive groups of degree $8$, contain transitive self-conjugate sub-groups of order $8$ whose operations are all of order $2$. With the possible exception then of groups of order $8\cdot 7\cdot 6\cdot 4$, the only primitive groups of degree $8$, which do not contain a self-conjugate sub-group of order $8$, are the simple group of order $8\cdot 7\cdot 3$ and any group of $8\cdot 7\cdot 6$ which contains this self-conjugately. We have seen that the simple group of order $8\cdot 7\cdot 3$ contains a single set of $8$ conjugate sub-groups of order $21$, and therefore it can be expressed in one form only as a group of degree $8$. A group of degree $8$ and order $8\cdot 7\cdot 6$, which contains this self-conjugately, can occur only in one form, if at all; for, if it exists, it must be triply transitive, and it must be given by combining the simple group with any operation of order $2$ which transforms one of its operations of order $7$ into its own inverse. That such a group does exist has been shewn in § 113. These two groups are actually given by

where in each case the last two substitutions give a sub-group that keeps one symbol fixed.

To avoid unnecessary prolixity we shall, in dealing with the primitive groups of degree $8$, which contain a transitive self-conjugate sub-group of order $8$ whose operations are all of order $2$, anticipate some of the results of the next Chapter. It will there be shewn that, if $G$ is an Abelian group of order $N$, and $L$ a group of isomorphisms (§ 156) of $G$, a group of degree $N$ may be formed which has a transitive self-conjugate sub-group simply isomorphic with $G$, while at the same time the sub-group that keeps one symbol fixed is isomorphic with $L$ (§ 158). The group of isomorphisms of a group of order $8$, whose operations are all of order $2$, will be shewn in Chapter XIV to be identical with the simple group of order $168$. This group has a single set of conjugate sub-groups of each of the orders $7$ and $21$, but no sub-group of order $14$ or $42$. When expressed as a group of degree $7$, it has a single set of conjugate sub-groups of order $12$ (or $24$) which leave no symbols unchanged. There are therefore primitive groups of degree $8$ containing transitive self-conjugate sub-groups of order $8$ corresponding to each of the orders $8\cdot 7$, $8\cdot 7\cdot 3$, $2^5\cdot 3$, $2^6\cdot 3$, and $8\cdot 7\cdot 6\cdot 4$; and in each case there is a single type of such group.

It remains to determine whether there can be any type of group, of degree $8$ and order $8\cdot 7\cdot 6\cdot 4$, other than that just obtained. Such a group must be one of $15$ conjugate sub-groups in the alternating group of degree $8$, and can therefore itself be expressed as a group of degree $14$. Since it certainly cannot be expressed as a group of degree $7$, the group of degree $14$ must be transitive. The order of the sub-group, in this form, that keeps one symbol fixed is $2^5\cdot 3$. If this keeps only one symbol unchanged, it must interchange the remaining symbols in four intransitive systems of $3$, $3$, $3$ and $4$ respectively, since a substitution of order $3$ must clearly consist of $4$ cycles. A group of order $2^5\cdot 3$ cannot however be so expressed; and therefore the sub-group that keeps one symbol fixed must keep two fixed. The group of degree $14$ is therefore imprimitive, and the group must contain a sub-group of order $2^6\cdot 3$. Moreover, since the group cannot be expressed as a transitive group of degree $7$, this sub-group of order $2^6\cdot 3$ must contain (§ 123) a sub-group which is self-conjugate in the group itself. The order of this sub-group must be a power of $2$; since the group is primitive, it cannot be less than $2^3$. On the other hand, the order cannot be greater than $2^3$ since the group contains a simple sub-group of order $7\cdot 6\cdot 4$. Hence finally, there is no type of primitive group of degree $8$ and order $8\cdot 7\cdot 6\cdot 4$ other than that already obtained.

There is no difficulty now in actually constructing the primitive groups of degree $8$ which have a self-conjugate sub-group of order $8$. They are all contained in the group of order $8\cdot 7\cdot 6\cdot 4$; and this may be constructed from a sub-group keeping one symbol fixed, which is given on p. 606, by the method of § 109. It will thus be found that the group in question is given by

The construction of the two remaining groups, of order $2^5\cdot 3$ and $2^6\cdot 3$, is left as an exercise for the reader.

It may be noticed that it has been shewn incidentally, in discussing above the possibility of a second type of group of degree $8$ and order $8\cdot 7\cdot 6\cdot 4$, that the alternating group of degree $8$ can be expressed as a doubly transitive group of degree $15$.

It may similarly be shewn that the alternating group of degree $7$ can be expressed as a doubly transitive group of degree $15$, and the alternating group of degree $6$ as a simply transitive and primitive group of degree $15$.

147. We have seen in § 105 that a doubly transitive group, of degree $n$ and order , can exist only when $n$ is the power of a prime. For such a group, the identical operation is the only one which keeps more than one symbol unchanged. We shall now go on to consider the sub-groups of a doubly transitive group, of degree $n$ and order , which keep two symbols fixed. The order of any such sub-group is $m$; since the group contains operations changing any two symbols into any other two, the sub-groups which keep two symbols fixed must form a single conjugate set.

Suppose first that the sub-group, which keeps two symbols unchanged, displaces all the other symbols. The sub-group that keeps $a$ and $b$ unchanged cannot then be identical with that which keeps $c$ and $d$ unchanged, unless the symbols $c$ and $d$ are the same pair as $a$ and $b$. Since there are pairs of $n$ symbols, the conjugate set contains sub-groups; and each sub-group of order $m$ keeping two symbols fixed must be self-conjugate in a sub-group of order $2m$, which consists of the operations of the sub-group of order $m$ and of those operations interchanging the two symbols that the sub-group of order $m$ keeps fixed.

Suppose next that all the operations of a sub-group $H$, which keeps two symbols fixed, keep $x$ symbols fixed, while none of the remaining $n-x$ symbols are unchanged by all the operations of $H$. From $x$ symbols pairs can be formed, and therefore the sub-group that keeps one pair unchanged must keep pairs unchanged. In this case, the conjugate set contains distinct sub-groups of order $m$, and $H$ is therefore self-conjugate in a group $K$ of order . The operations of this sub-group which do not belong to $H$ interchange among themselves the $x$ symbols that are left unchanged by $H$. Now since the group itself is doubly transitive, there must be operations which change any two of these $x$ symbols into any other two; and any such operation being permutable with $H$ must belong to $K$. Hence if we consider the effect of $K$ on the $x$ symbols only which are left unchanged by $H$, $K$ reduces to a doubly transitive group of degree $x$ and order . It follows that $x$ must be a prime or the power of a prime.

148. The preceding paragraph suggests the combinatorial problem of forming from $n$ distinct symbols sets of $x$ symbols, such that every pair of symbols occurs in one set of $x$ and no pair occurs in more than one.

There is one class of cases in which a solution of this problem is given immediately by the theory of Abelian groups. Let $G$ be an Abelian group of order $p^m$, where $p$ is a prime, and type . We have seen, in § 49, that $G$ has $\frac{p^m-1}{p-1}$ sub-groups of order $p$, and $\frac{p^m-1\cdot p^{m-1}-1}{p-1\cdot p^2-1}$ sub-groups of order $p^2$. Now any pair of sub-groups of order $p$ generates a sub-group of order $p^2$, and therefore every pair of sub-groups of order $p$ occurs in one and only one sub-group of order $p^2$. Moreover, every sub-group of order $p^2$ contains $p+1$ sub-groups of order $p$. When $p$ is a prime and $m$ any integer, it is therefore always possible to form from $\frac{p^m-1}{p-1}$ symbols $\frac{p^m-1\cdot p^{m-1}-1}{p-1\cdot p^2-1}$ sets of $p+1$ symbols each, such that every pair of the symbols occurs in one set of $p+1$ and no pair occurs in more than one set.

Supposing that, for given values of $n$ and $x$, such a distribution is possible, it is still of course an open question as to whether there is a doubly transitive substitution group of the $n$ symbols, such that every substitution which keeps any two symbols unchanged keeps also unchanged the whole set of $x$ in which they occur. When $x$ is greater than $3$, the question as to the existence of such groups is one which still remains to be investigated. There is however an important class of groups, to be considered later (Chapter XIV), that possess a closely analogous property. These groups are doubly transitive; and from the $n$ symbols upon which they operate, we can form sets of $x$, that are interchanged transitively by the substitutions of the group: the sets being such that every pair occurs in one set and no pair in more than one set.

If is the order of such a group, and if $H$ is a sub-group of order $m$ which keeps a given pair fixed, then $H$ must interchange among themselves the remaining $x-2$ symbols of that set of $x$ which contains the pair kept unchanged by $H$. $H$ contains, as a self-conjugate sub-group, the group $h$ which leaves every symbol of the set of $x$ unchanged; and if $m\prime \prime$ is the order of this sub-group, while $m=m\prime m\prime \prime$, then $m\prime$ is the order of the group to which $H$ reduces when we consider its effect only on the $x-2$ symbols. Now $h$ is self-conjugate in the group $K$ that interchanges all the symbols of the set of $x$ among themselves. But since the original group is doubly transitive, it must contain substitutions which change any two of the set of $x$ into any other two, and every such substitution must belong to $K$. Hence $K$ must be doubly transitive in the $x$ symbols, and therefore finally the order of the group, to which $K$ reduces when we consider its effect on the $x$ symbols only, is . Since the order of $h$, which keeps unchanged each of the $x$ symbols is $m\prime \prime$, the order of $K$ is .

149. When $x=3$, $n$ must be of the form $6k+1$ or $6k+3$, since otherwise would not be an integer. The substitutions of a doubly transitive group of degree $n$, which possesses a complete set of triplets, must be such that every substitution which leaves two given symbols unchanged also leaves a third definite symbol unchanged.

The smallest possible value of $n$ is $7$; and the group of Ex. 2, § 35, which is one of the groups obtained in § 146, satisfies all the conditions. In fact, the group is clearly a doubly transitive group of degree $7$; and since its order is $7\cdot 6\cdot 4$, the order of the sub-group which keeps two symbols fixed is $4$. Now in the sub-group

These with identity form a sub-group of order $4$, which must therefore be the sub-group that keeps three symbols fixed. The complete set of triplets in this case is

The next smallest value of $n$ is $9$, and in this case again, a group with the required properties exists.

Ex. Shew that the group

The reader is not to infer from the examples given that, when $n$ is of the form $6k+1$ or $6k+3$, there is always a doubly transitive group of degree $n$ which possesses a complete set of triplets. It is a good exercise to verify that there is no such group when $n$ is $13$.

The case $n=13$, $x=4$ is the simplest case that can occur of the division of $n$ symbols into sets of $x$ in the manner of § 148 when $x$ is greater than $3$. We shall see in Chapter XIV that there is a doubly transitive group of degree $13$ such that from the $13$ symbols permuted by the group a complete set of $13$ quartets can be formed, which are themselves permuted by the operations of the group. Of the operations forming a sub-group that keeps two given symbols fixed, half will keep fixed the two other symbols, which form a quartet with the two given symbols, and half will permute them.

On the question of the independent formation of a complete set of triplets of $n$ symbols, and in certain cases of the group of degree $n$ which interchanges the triplets among themselves, reference may be made to the memoirs mentioned in the subjoined footnote⁵⁷.

150. We shall conclude the present Chapter with some applications of substitution groups, which enable us to complete and extend certain earlier results.

We have seen in § 107 that the substitutions of $n$ symbols, which are permutable with each of the substitutions of a regular substitution group $G$ of order $n$ of the same $n$ symbols, form another regular substitution group of order $n$; and that, if $G$ is Abelian, the latter group coincides with $G$. Hence the only substitutions of $n$ symbols, which are permutable with a circular substitution of the $n$ symbols, are the powers of the circular substitution.

Let now $S$ be a regular substitution of order $m$, in $mn$ symbols. It must permute the symbols in $n$ cycles of $m$ symbols each; and so we may take

If $T$ is permutable with $S$, and if it changes $a_{rp}$ into $a_{rq}$, it clearly must permute the $m$ symbols

Again, if $T$ changes $a_{rp}$ into $a_{sq}$, it must change the set

Now the totality of the substitutions of the $mn$ symbols, which are permutable with $S$, form a group $G_S$. This group must, from the properties of $T$ just stated, be imprimitive, interchanging the symbols in $n$ imprimitive systems of $m$ symbols each; and the symbols in any cycle of $S$ will form an imprimitive system. Moreover, the self-conjugate sub-group $H_S$ of this group, which permutes the symbols of each system among themselves, is the group of order $m^n$ generated by

In fact, every substitution of this group is clearly permutable with $S$; and conversely, every substitution of the $mn$ symbols, which does not permute the systems, must belong to this group.

Now $\frac{G_S}{H_S}$ is capable of representation as a group of degree $n$, for none of its operations changes every one of the $n$ systems into itself. Hence $n!$ is the greatest possible order of $\frac{G_S}{H_S}$. On the other hand, every operation of the group, generated by

Hence, finally, the order of $G_S$ is $m^n\cdot n!$; and $G_S$ is generated by

and

151. Let $h_r$ be a regular substitution group of order $m$ in the $m$ symbols

The method of § 150 can be applied directly to determine the group $G_H$ of degree $mn$, each of whose substitutions are permutable with every substitution of $H$. The order of this group is $m^n\cdot n!$; and it can be generated by

and

This group will contain $H$ if, and only if, $H$ is an Abelian group. Moreover, the only self-conjugate substitutions of $G_H$ are the substitutions of $H$ contained in it. For if $G_H$ contained other self-conjugate substitutions $S_1$, $S_2$, …, every operation of $G_H$ would be permutable with every operation of the group . Now $G_H$ is transitive, so that $S_1$, $S_2$, … must displace all the symbols; and therefore has all its substitutions regular in the $mn$ symbols. If its order is $m{n}_1$ where $n=n_1{n}_2$, the order of the group formed of all the substitutions of $mn$ symbols, which are permutable with each of its operations, is ; and this number is less than $m^n\cdot n!$. Thus the supposition, that $G_H$ has self-conjugate operations other than the operations of $H$ which it contains, leads to an impossibility.

By means of this and the preceding section, the reader will have no difficulty in forming the group of $n$ symbols, which is permutable with every operation of any given group in the $n$ symbols.

152. If a group, whose order is a power of a prime $p$, be expressed as a transitive substitution group, its degree must also be a power of $p$ (§ 123). Moreover such a group, since it has self-conjugate operations, must necessarily be imprimitive.

The greatest value of $m$, for which a group of order $p^m$ can be expressed as a transitive group of degree $p^n$, where $n$ is regarded as given, is determined at once by considering the symmetric group of degree $p^n$. The highest power of $p$ that divides $p^n!$ is $p^{\nu }$, where

Hence the symmetric group of degree $p^n$ contains a set of conjugate sub-groups of order $p^{\nu }$ and it contains no groups whose order is a higher power of $p$. Also, these groups are transitive in the $p^n$ symbols; for any one of them must contain a circular substitution of order $p^n$. There are therefore groups of order $p^{\nu }$ which can be expressed as transitive groups of degree $p^n$; but no group of order $p^{\nu \prime }$ ($\nu \prime >\nu$) can be so expressed. Moreover, in order that a group of order $p^m$ may be capable of representation as a transitive group of degree $p^n$, it must be simply isomorphic with a transitive sub-group of the above substitution group of order $p^{\nu }$.

This group may be constructed synthetically as follows. Since the sub-group of order $p^{\nu -n}$, that leaves one symbol unchanged, is contained in a sub-group of order $p^{\nu -n+1}$ (§ 55), there must be imprimitive systems containing $p$ symbols each. If then we distribute the $p^n$ symbols into $p^{n-1}$ sets of $p$ each, and with each set of $p$ form a circular substitution, the $p^{n-1}$ permutable and independent circular substitutions will generate an intransitive group of order $p^{p^{n-1}}$. It will be the self-conjugate sub-group of the group of order $p^{\nu }$, which permutes the symbols of each system among themselves.

Again, the systems of $p$ symbols each may be taken in sets of $p$ to form systems of $p^2$ symbols each, since the previously considered sub-group of order $p^{n-\nu +1}$ must be contained in a sub-group of order $p^{n-\nu +2}$. Hence we may form systems of $p^2$ symbols by combining the previous systems in sets of $p$; and then with each $p^2$ symbols we can form a circular substitution, whose $p$th power is the product of the $p$ circular substitutions of order $p$, which have been previously formed from the $p^2$ symbols. The symbols of any set of $p^2$ will then be interchanged by a transitive group of order $p^{p+1}$; and since there are $p^{n-2}$ such sets, we obtain in this way an intransitive group of $p^{p^{n-1}+p^{n-2}}$. The group thus formed is that self-conjugate sub-group of the original group, which interchanges among themselves the symbols of each system of $p^2$. This process may be continued, taking greater and greater systems, till at the last step we combine the $p$ systems of $p^{n-1}$ symbols each into a single system by means of a circular substitution of order $p^n$. The order of the resulting group is clearly $p^{\nu }$, as it should be.

The self-conjugate operations of this group form a sub-group of order $p$.

For suppose, if possible, they form a sub-group of order $p^r$. Every operation of this sub-group displaces all the symbols; and therefore, when expressed as a substitution group in the $p^n$ symbols, it must interchange them transitively in $p^{n-r}$ sets of $p^r$ each.

Now (§ 151) those substitutions of the $p^n$ symbols, which are permutable with every operation of this sub-group, form a group of order $p^{r{p}^{n-r}}\cdot p^{n-r}!$; this number is only divisible by $p^{\nu }$, as it must be, when $r=1$.

Ex. Shew that, for the group of degree $p^2$ and order $p^{p+1}$, the factor groups $\frac{H_{r+1}}{H_r}$ (of § 53) are all of type  except the last, which is of type .

The fact that $\nu$ is a function of $p$ when $n$ is given, explains why, in classifying all groups of order $p^n$, some of the lower primes may behave in an exceptional manner. Thus we saw, in § 73, that for certain groups of order $p^4$ it was necessary to consider separately the case $p=3$. The present article makes it clear that, while there may be more than one type of group of order $p^4$ ($p>3$), which can be expressed as a transitive group of degree $p^2$, there is only a single type of group of order $3^4$ which can be expressed transitively in $9$ symbols.

153. In the memoirs referred to in the footnote on p. 1106, M. Mathieu has demonstrated the existence of a remarkable group, of degree $12$ and order $12\cdot 11\cdot 10\cdot 9\cdot 8$, which is quintuply transitive. The generating operations of this group have been given in the note to § 108, at the end of Chapter VIII. The verification of some of the more important properties of this group, as stated in the succeeding example, forms a good exercise on the results of this and the two preceding Chapters.

Ex. Shew that the substitutions

generate a quintuply transitive group of degree $12$ and order

Prove that this group is simple; that a sub-group of degree $11$ and order $11\cdot 10\cdot 9\cdot 8$, which leaves one symbol unchanged, is a simple group; and that a sub-group of degree $10$ and order $10\cdot 9\cdot 8$, which leaves two symbols unchanged, contains a self-conjugate sub-group simply isomorphic with the alternating group of degree $6$.

Shew also that the group of degree $12$ contains (i) $1728$ sub-groups of order $11$ each of which is self-conjugate in a group of order $55$: (ii) $2376$ sub-groups of order $5$, each of which is self-conjugate in a group of order $40$: (iii) $880$ sub-groups of order $27$, each of which is self-conjugate in a group of order $108$: (iv) $1485$ sub-groups of order $64$.

Prove further that the group is a maximum sub-group of the alternating group of degree $12$.