A Minimal Presentation of a Two-Generator Permutation Group on the Set of Integers ()
1. Introduction
We determine finite minimal presentations for certain 2-generator groups of permutations of the integers. Much of the work contained herein appeared in [1]. For further results in this area, we recommend [2] and [3]. For all algebra definitions and terminology not found in this paper, we refer the reader to [4], and for more background on permutation groups, we refer the reader to [5].
First, we introduce some notation that we will follow in this paper. We will denote by
and
two separate copies of the integers, i.e.,
,
, and let
. We denote by
the group of all one-to-one mappings of S onto itself. We will refer to
as the infinite symmetric group, and its elements will be called permutations of S. This paper will, for the most part, deal with the combinatorial group theory aspects of the permutation group G generated by
and
. In our notation,
denotes
followed by
. The permutations
that are the focus of this work are defined as follows:
·
·
·
·
We illustrate
and
in Figure 1.
We state a few pertinent definitions.
Definition 1.1 Let
be an arbitrary group.
1) A group
is finitely generated by elements
if each
has a representation
with each
. For the following definitions, we assume that
has a specified set of generators
.
2) A word in
is a sequence
with each
. The word
represents the element
, so we will write
. We will allow the empty word (no symbols) which represents the identity in
.
3) If
is a word, then
.
4) A relator is a word that represents the identity. A trivial relator is a word
with x a word. The set of relators is denoted
.
5) Two words are equivalent if one can be transformed into the other in a finite number of steps by inserting or deleting a trivial relator at an arbitrary location during each step. This is a valid equivalence relation on the set of words. Hereafter, a word will mean the equivalence class of the word.
6) If
are words, then
is a conjugate of y. The conjugate of a relator is itself a relator, and a finite product of relators is also a relator.
7) A relator z can be inserted into a word
(with
words) to obtain a new word
by multiplying
on the right by
, i.e.,
.
8) If
are words, then
is the set of words that are the finite products of the conjugates of
. If each
, then
.
9)
is finitely presented if there is a finite set of relators
such that
. The presentation
is minimal if
for
.
Figure 1. The permutation
is represented by the single arrow, and
is represented by the double arrow.
2. Main Results
2.1. Properties of τ and σ
Theorems 2.1 and 2.2 demonstrate how the application of
and
to integers impacts the resulting parities.
Theorem 2.1 The permutations
and
satisfy the following properties:
1) If
, then
·
, and
·
, and
·
, and
·
, and
2) If
, then
, and
·
, and
·
, and
·
, and
.
Proof: (1.) Suppose
. We prove the first formula:
·
·
·
·
To determine inverses, note that
and
preserve both sign parity (i.e., +, −) and even/odd parity. If
, then
, so
, and thus,
. The proofs of the other formulas are similar. (2.) Suppose
. We prove the first formula:
·
·
·
·
The inverse properties follow as in part (1.), and the other formulas follow similarly.
The next theorem generalizes Theorem 2.1.
Theorem 2.2 Let
and
.
1).
·
·
·
·
2).
·
·
·
·
Proof:
1) First, suppose
, so
. By Theorem 2.1,
·
·
·
·
Now suppose
, so
. Then
·
·
·
·
2) Suppose
, so
. Then
·
·
·
·
.
Also, if
, so
, then
·
·
·
·
.
We can use Theorem 2.2 to prove a uniqueness of representation theorem for the permutations
.
Theorem 2.3 Let
and
. Suppose
. Then
.
Proof. If
, then their images agree on all values in S. In particular, on
and
. There are two cases:
1) First suppose
. Then we must have
in order to preserve sign parity. We substitute the values
and
into the equation
and use Theorem 2.2. This yields
· At
, have
.
· At
, have
.
· At
, have
.
· At
, have
.
These equations imply that
.
2) Now suppose that
, and again substitute the values
and
, respectively. Now,
· At
, have
.
· At
, have
.
· At
, have
.
· At
, have
.
These equations imply that
. Since we assumed
, this is impossible, so the desired result follows.
Now we return to the group G generated by the permutations
and
. We will show that G is finitely presented and determine a minimal presentation.
Theorem 2.4 The following words are in
.
·
·
·
·
·
·
·
·
Then
, and
is a finite presentation for G.
Proof. We will prove this theorem by demonstrating containment in both directions. To show
, we first show that
and
are in
. If
, then
·
·
·
·
If
, then
·
·
·
·
Since the conjugate of an element in
is also in
, it follows that
. In addition, since
are conjugates of
, or
, they are in
.
Now, to show that the reverse inclusion holds, we assume that g is a word inG having the form
, where
are words in G. Then g can be transformed to
by multiplying g on the right by
where
are as indicated below:
Hence,
, implying that
. Since
, this shows that any word
can be transformed to an element
by moving even powers of
to the left and even powers of
to the right. When this process is completed,
has the form
, where x has the form
, with each
. If some exponent is −1, say,
, then we can represent this as
. Now, the
can be moved to the right. In this way, we eventually arrive at
, and
, with
. Now, suppose
. Since
, it follows that
. Therefore,
, so
is the identity, and
in G. By Theorem 2.3,
. This means that
is the empty word, and g is the word
. Thus,
, and we have
.
Theorem 2.4 has an immediate corollary.
Corollary 2.5 Every word
has an equivalent form
, where
. and
.
We are now ready to prove our main result.
Theorem 2.6
is a minimal presentation for G.
Proof. We must show that
and
, where
and
. For any word
, define
, and
. If
, then
. If
, then
. If
, then
. If
, then
. If x is a conjugate of
or
, then
. If
, then
, with each
a conjugate of
or
. Therefore,
, a contradiction. Hence,
. By a similar argument,
.
Example 2.7 Transform
by
of Theorem 2.5 and show that
.
The step-by-step process involves multiplying
on the right by
(where z is a particular value of
or
) to obtain
. At each stage, we make use of the reductions
,
, delete
. We halt the procedure when the identity, i.e., the empty word, is reached.
So the first step replaces
with
and simplifies by reducing exponents. At the final step, we obtain
(i.e., the empty word). Hence,
. Expressing everything in terms of powers of
and
reduces the equation to
, with deletion of
.
2.2. The Finite Permutation Groups G4n
We define a translation operation on
for each positive integer n. We then form equivalence classes denoted by
. The permutations
are well-defined mappings on
. The permutation group generated by
on
is denoted by
. Theorem 2.2 is generalized in order to determine the relators
of
. We also determine the order of each
.
Definition 2.8 Let n be a positive integer and
. Define a mapping
by
·
·
If
, then
denotes
.
Theorem 2.9 If n is even, then
, and
Proof. If
, then
, and
=
If
, then
, and
.
Definition 2.10 Let n be a positive integer. Define a relation
on S by
·
if
·
if
Theorem 2.11
is an equivalence relation on S.
Proof. Trivial, since
is an equivalence relation on
.
Remark: For simplicity of notation, we write ~ instead of
when n is a fixed positive integer.
Definition 2.12
is the set of equivalence classes of S under ~.
Example 2.13 Let
denote an equivalence class in
. Then
·
·
Theorem 2.14 Let
. If
, then
and
. Therefore,
induce permutations of
.
Proof. Suppose
. Then
, so
for some
. By Theorem 2.9,
, and
. Therefore,
and
; an identical argument applies to
. Therefore,
induce maps of
to
. Since
are onto, the induced maps on
are onto.
RTS: the induced maps are 1-1. Suppose
. Then
, implying, for some
,
by Theorem 2.2. Since
is 1-1,
, and
. Identical arguments apply to
, and
.
Definition 2.15
is the group of permutations of
generated by the permutations of
and
.
Corollary 2.5 still applies, so that each word w in
has an equivalent word representation
with
and
. However, Theorem 2.3 no longer applies, so we require a modification.
Theorem 2.16 Let
as defined above. Let
be integers. Then
if
1)
,
,
,
, or
2)
,
,
,
(mod 2n).
Proof. First suppose
and
. The formula for
in Theorem 2.2 imply that
. Let
. Equating
and
on the classes
.
1)
2)
3)
4)
5) Equations (1)-(4) imply, by Definition 2.10, that
6)
7)
8)
. Now, (5) and (7) imply that
. Additionally, (5) and (6) imply that
. Finally, (7) implies
. Hence,
, and Equations (1)-(4) imply
9)
10)
11)
12)
Conversely, suppose 9 - 12 hold. Then, working mod 2n,
, while
, with
, and thus,
, so Equations (5)-(8) hold. This Implies (1)-(4), which implies
.
Now suppose
and
. Again, by Theorem 2.2, we must have
and the equations
1')
2')
3')
4')
; substituting
into (2') yields
, so
5')
; (1') and (2') yields
6')
; (1') and (3') yields
7')
; (4') yields
8')
Conversely, if (5')-(8') hold, then, working mod 2n,
·
·
·
·
Hence, (1')-(4') hold, which implies
.
Corollary 2.17
is the identity in
if and only if
1)
,
,
,
, or
2)
,
,
,
Proof.
is the identity if and only if
. Now, replace
with
in Theorem 2.14.
Corollary 2.18 If a word
represents the identity in
, i.e.,
, then
where
and
satisfy (1) or (2) of Corollary 2.17.
Proof. By Corollary 2.5, there is a word
such that
. Hence,
. Since
and
represent the identity in
,
represents the identity, and Cor. 2.17 applies.
We can improve Corollary 2.18 as follows:
Theorem 2.19 A word
if
, where
,
or 1 (i.e., empty word), and a, b, c satisfy (henceforth (*)):
,
,
,
.
Proof. Suppose
. By Corollary 2.18,
where
, and a, b, c satisfy (1) or (2) of Corollary 2.17. Suppose they satisfy (2). Making use of
, which follows from the relator
, and
, which follows from the relator
, we can move even powers of
to the right to obtain
where
,
,
,
,
. Then
,
,
, and
.
If (1) holds, we can take g = 1 and
.
Next we determine the relators
and minimal presentations for
. We first consider
, then n odd and greater than 1, then n even.
Theorem 2.20
and
is a minimal presentation for
.
Proof. The diagram for
(see Figure 2) shows that
, and
all belong to
. Therefore,
. Conversely, suppose
. By Theorem 2.19,
with
even and
, and
or 1. But
and
belong to
, so
.
Now we show that
is a minimal presentation for
. First, we show that
cannot be expressed as a product of conjugates of
. Suppose it could, so (a)
, where each
is a conjugate of
. Now (a) is an equation valid in the free group on the symbols
. It must hold if
take values in any group G. Let G be the permutation group on
and
,
. Then
,
Figure 2. The diagram shows
on
.
and
,
as permutations in G. In G, (a) becomes
, which is a contradiction. Therefore,
cannot have (a) as a representation in the free group of
.
For the other two cases, take (b)
, with
conjugate in
. Choose
. Then (b) yields
, a contradiction. Finally, take (c)
,
conjugate in
. Choose
. Then (c) yields
, a contradiction. Therefore,
is a minimal presentation for
.
Theorem 2.21 If n is odd and
, then
and
is a minimal presentation.
Proof. Clearly,
all satisfy the hypothesis of Theorem 2.19, so they clearly belong to
. Since
also belong to
, we have
.
Conversely, suppose
. By Theorem 2.19,
, with
satisfying (*), and
with
or 1. Then
are multiples of 2n, so
.
Let
be a free group on the symbols
. To show
is a minimal presentation, we argue as follows:
Let
. Define
,
Then
are well-defined for
. Since
,
, we have
,
. Also,
, and
. If
, applying
to the representation for
yields
. Since
, this is a contradiction. Therefore,
. Using
and employing a similar argument, we obtain
.
Now suppose
so that
, where each
is a conjugate in
. Since this equation holds in
, it most hold in any group G in which
are assigned values. Let G be the permutation group on
and set
,
. Then
, so
in G, but
, which has order
, so that
in G. Therefore,
.
To show that
, let G be as above, with
,
. Then
, while
. Thus,
, but
,
,
. Therefore,
.
Finally, we show that
. Let G be as above, with
,
. Then
,
. Thus,
,
,
, but
. Therefore,
. This proves that
is a minimal presentation for
, the relators in
.
Theorem 2.22 If n is even, then
.
Proof. First note that
, since
and
. Therefore it is sufficient to show that
. By Theorem 2.19,
if
, with
,
or 1, and
,
,
. The conditions on
are equivalent to
,
,
. Each of the elements
has the required form
of Theorem 2.19. Therefore,
.
Conversely, suppose
with
as above. It remains to show that
, which would imply that
. There are four cases.
1)
Then
, so
, and
.
2)
Since
, we must have
. Then
, so
.
3)
Then
, so
, and
.
4)
Then
, so
, and
.
Therefore,
.
We can improve Theorem 2.22 with the following result.
Theorem 2.23 Let n be an even positive integer. Let G be any group containing elements
such that
. Then
.
Proof. First note that
for all even
. This is true for
by hypothesis, and the general result follows inductively from
. Also,
implies
, and
implies
, so
and
. Therefore, it suffices to show that
. But
and
imply that
.
Corollary 2.24 If n is even, then
.
Proof. Since
, Theorem 2.23 implies that
. Therefore,
.
Now we determine minimal presentation for
when n is even. We start with
.
Theorem 2.25
is a minimal presentation for
.
Proof.
1) Since
follows from
, this implies that
.
2) We have
since
, whereas
and
are both divisible by 4.
3) We have
since
, whereas
and
are both divisible by 4.
4) To show that
, let G be the permutation group on
and set
. Then
, but
, so
.
Theorem 2.26 If n is even,
, then
is a minimal presentation for
.
Proof. Corollary 2.24 states that it is a presentation. To demonstrate its minimality, we consider two cases:
1)
: In this case,
with
, m odd.
(a)
because
, whereas
and
(b)
, because
, but
all have
values divisible by 4.
(c)
because
, but the other elements have
values divisible by m.
(d)
because
, but the other elements have
values divisible by m.
2)
: In this case,
.
(a)
. Let G be the permutation group on
. Let
,
and
. Then
. Also,
, so
. Therefore
, but
. Let
Let
denote addition (mod 2n).
If x is odd,
If x is even,
so
in G.
For example, if
, then G is the permutation group on
.
so
For
, we have:
If x is odd,
If x is even,
Therefore,
in G.
Since
are equal to the identity in G, but
, it follows that
.
(b)
.
Using
and
from part (a), we note that
. Therefore, if we exchange the definitions of
and
, we obtain
, but
in G, which proves (b).
(c)
.
Recall that
. Let G be the permutation group on
.
If
, let
Then
, so
, but (using
)
.
If
, let
) and
Then
.
Also,
, so
But
.
Therefore
.
(d)
. Let G be defined as in part (c).
If we exchange
from part (c), we obtain
.
In summary, minimal presentations for
are:
(a)
for
;
(b)
for
;
(c)
for n odd,
;
(d)
for n even,
.
Definition 2.27 The order of a group is the number of elements in the group.
We require two lemmas to prove a theorem about the order of
:
Lemma 2.28 The following identities hold in
:
1)
2)
3)
4)
Proof (of Lemma 2.28):
1)
, so
.
2)
, so
.
3)
(since
)
.
4)
.
Lemma 2.29 Every element
has representation
with b even.
Proof (of Lemma 2.29): By Corollary 2.5, every
has a representation
, with
. If b is even, the proof is complete. Let b be odd and set
, B even. Then
(by part (3) of Lemma 2.28)
(by part (4) of Lemma 2.28)
Continuing to apply parts (3) and (4) we obtain
By parts (1) and (2) of Lemma 2.28, all powers of
can be commuted to the left of
while preserving even parity. Hence,
with
even.
Theorem 2.30 The order of
is:
1) 4n3 if n is odd
2) n3 if n is even.
Proof.
1) Suppose n is odd. By Lemma 2.29,
, with b even. By Theorems 2.20 and 2.21,
all belong to
. Therefore we can take
, with
, and
even. There are
possibilities for
. If
, then
. Since
is even, we can use the commutation rules to obtain
.
Also, Corollary 2.17 implies that
and
are both even, and
·
·
·
.
Since
, and n is odd, this implies
·
·
·
,
which implies
because of the conditions on
. Therefore the representation
is unique, and
contains
elements when n is odd.
2) Now assume n even. Again, let
, with b even.
By Theorem 2.19,
belong to
. Using
, we can transform x so that
and b is even. Using
, we can transform x so that
. Finally, using
, we can transform x into:
(*)
with
, b even.
The total number of choices for
is
. The choices yield distinct elements of
, for if
, then
, and by commuting even powers of
with
, we obtain
. By Condition (1) of Corollary 2.17, we obtain
·
·
·
.
Since
, we must have
and
. However, by Condition (1) of Corollary 2.17,
, so
, since
. Therefore, all the elements
in (*) are distinct and the order of
is
.
Finally, we determine isomorphic group structures for
and
.
Theorem 2.31
1)
is isomorphic to the Klein-4 group
.
2)
is isomorphic to the multiplicative quaternion group
.
Figure 3. The diagram shows
on
.
Proof.
1) The diagram for
is:
(
is single line,
is double line).
By Theorem 2.30,
has order 4, so
. Since
,
is Abelian, but not cyclic, it is
.
2) Quaternions
, with
·
·
·
·
·
·
·
each has a unique representation of the form
, with
,
. Also,
. The diagram for
is shown in Figure 3.
Clearly,
, and each
has a representation
, with
,
. Also,
. Therefore,
is an isomorphism defined by
for
,
.
Acknowledgements
The authors acknowledge the assistance of Dr. Nathan Kahl in the preparation of this paper. This paper is in memory of our late coauthor and friend, Dr. Michael Miniere.