Back
 APM  Vol.11 No.10 , October 2021
A Minimal Presentation of a Two-Generator Permutation Group on the Set of Integers
Abstract: In this paper, we investigate the algebraic structure of certain 2-generator groups of permutations of the integers. The groups fall into two infinite classes: one class terminates with the quaternion group and the other class terminates with the Klein-four group. We show that all the groups are finitely presented and we determine minimal presentations in each case. Finally, we determine the order of each group.

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., + = { , 3 + , 2 + , 1 + ,0 + ,1 + ,2 + ,3 + , } , = { , 3 , 2 , 1 ,0 ,1 ,2 ,3 , } , and let S = + . 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:

· σ ( x + ) = ( x 1 ) +

· σ ( x ) = ( x + 1 )

· τ ( x ) = x +

· τ ( x + ) = ( ( x + 2 ) x 0 ( mod 2 ) ( x 2 ) x 1 ( mod 2 )

We illustrate σ and τ in Figure 1.

We state a few pertinent definitions.

Definition 1.1 Let G ˜ be an arbitrary group.

1) A group G ˜ is finitely generated by elements g 1 , g 2 , , g j G ˜ if each x G ˜ has a representation x = x 1 x 2 x n with each x i { g 1 , g 1 1 , g 2 , g 2 1 , , g j , g j 1 } . For the following definitions, we assume that G ˜ has a specified set of generators g 1 , g 2 , , g j .

2) A word in G ˜ is a sequence x 1 , x 2 , , x n with each x i { g 1 , g 1 1 , g 2 , g 2 1 , , g j , g j 1 } . The word w = x 1 , x 2 , , x n represents the element x 1 x 2 x n G ˜ , so we will write w = x 1 x 2 x n . We will allow the empty word (no symbols) which represents the identity in G ˜ .

3) If w = x 1 x 2 x n is a word, then w 1 = x n 1 x n 1 1 x 1 1 .

4) A relator is a word that represents the identity. A trivial relator is a word w = x x 1 with x a word. The set of relators is denoted R ( G ˜ ) .

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 x , y are words, then x 1 y x 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 ω 1 = A B (with A , B words) to obtain a new word ω 2 = A z B by multiplying ω 1 on the right by B 1 z B , i.e., ω 1 = A B A B ( B 1 z B ) = A z B = ω 2 .

8) If ω 1 , ω 2 , , ω n are words, then N ( ω 1 , ω 2 , , ω n ) is the set of words that are the finite products of the conjugates of ω 1 , ω 1 1 , ω 2 , ω 2 1 , , ω n , ω n 1 . If each ω i R ( G ˜ ) , then N ( ω 1 , ω 2 , , ω n ) R ( G ˜ ) .

9) G ˜ is finitely presented if there is a finite set of relators { z 1 , z 2 , , z n } such that R ( G ˜ ) = N ( z 1 , z 2 , , z n ) . The presentation { z 1 , z 2 , , z n } is minimal if R ( G ˜ ) N ( z 1 , z 2 , , z i 1 , z i + 1 , , z n ) for i = 1,2, , n .

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 x 0 ( mod 2 ) , then

· τ 2 ( x + ) = ( x + 2 ) + , and τ 2 ( x + ) = ( x 2 ) +

· τ 2 ( x ) = ( x + 2 ) , and τ 2 ( x ) = ( x 2 )

· ( τ σ ) 2 ( x + ) = ( x 2 ) + , and ( τ σ ) 2 ( x + ) = ( x + 2 ) +

· ( τ σ ) 2 ( x ) = ( x + 2 ) , and ( τ σ ) 2 ( x ) = ( x 2 )

2) If x 1 ( mod 2 ) , then

τ 2 ( x + ) = ( x 2 ) + , and τ 2 ( x + ) = ( x + 2 ) +

· τ 2 ( x ) = ( x 2 ) , and τ 2 ( x ) = ( x + 2 )

· ( τ σ ) 2 ( x + ) = ( x + 2 ) + , and ( τ σ ) 2 ( x ) = ( x 2 ) +

· ( τ σ ) 2 ( x ) = ( x 2 ) , and ( τ σ ) 2 ( x + ) = ( x + 2 ) .

Proof: (1.) Suppose x 0 ( mod 2 ) . We prove the first formula:

· τ 2 ( x + ) = τ ( ( x + 2 ) ) = ( x + 2 ) + ,

· τ 2 ( x ) = τ ( x + ) = ( x + 2 ) ,

· τ σ τ σ ( x + ) = τ σ τ ( ( x 1 ) + ) = τ σ ( ( x 3 ) ) = τ ( ( x 2 ) ) = ( x 2 ) + ,

· τ σ τ σ ( x ) = τ σ τ ( ( x + 1 ) ) = τ σ ( ( x + 1 ) + ) = τ ( x + ) = ( x + 2 ) .

To determine inverses, note that τ 2 and ( τ σ ) 2 preserve both sign parity (i.e., +, −) and even/odd parity. If τ 2 ( x + ) = y + , then x + = τ 2 ( y + ) = ( y + 2 ) + , so y = x 2 , and thus, τ 2 ( x + ) = ( x 2 ) + . The proofs of the other formulas are similar. (2.) Suppose x 1 ( mod 2 ) . We prove the first formula:

· τ 2 ( x + ) = τ ( ( x 2 ) ) = ( x 2 ) + ,

· τ 2 ( x ) = τ ( x + ) = ( x 2 ) ,

· τ σ τ σ ( x + ) = τ σ τ ( ( x 1 ) + ) = τ σ ( ( x + 1 ) ) = τ ( ( x + 2 ) ) = ( x + 2 ) + ,

· τ σ τ σ ( x ) = τ σ τ ( ( x + 1 ) ) = τ σ ( ( x + 1 ) + ) = τ ( x + ) = ( x 2 ) .

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 a , b , c and x 2 .

1).

· ( τ σ ) a ( x + ) = { ( x a ) + , a 0 ( mod 2 ) ( x a 2 ) , a 1 ( mod 2 )

· ( τ σ ) a ( ( x + 1 ) + ) = { ( x + 1 + a ) + , a 0 ( mod 2 ) ( x + 1 + a ) , a 1 ( mod 2 )

· ( τ σ ) a ( x ) = { ( x + a ) , a 0 ( mod 2 ) ( x + a ) + , a 1 ( mod 2 )

· ( τ σ ) a ( ( x + 1 ) ) = { ( x + 1 a ) , a 0 ( mod 2 ) ( x + 3 a ) + , a 1 ( mod 2 )

2).

· σ b τ c ( x + ) = { ( x b + c ) + , c 0 ( mod 2 ) ( x + 1 + b + c ) , c 1 ( mod 2 )

· σ b τ c ( ( x + 1 ) + ) = { ( x + 1 b c ) + , c 0 ( mod 2 ) ( x + b c ) , c 1 ( mod 2 )

· σ b τ c ( x ) = { ( x + b + c ) , c 0 ( mod 2 ) ( x b + c 1 ) + , c 1 ( mod 2 )

· σ b τ c ( ( x + 1 ) ) = { ( x + 1 + b c ) , c 0 ( mod 2 ) ( x b c + 2 ) + , c 1 ( mod 2 )

Proof:

1) First, suppose a 0 ( mod 2 ) , so a = 2 k . By Theorem 2.1,

· ( τ σ ) a ( x + ) = [ ( τ σ ) 2 ] k ( x + ) = ( x 2 k ) + = ( x a ) +

· ( τ σ ) a ( x ) = [ ( τ σ ) 2 ] k ( x ) = ( x + 2 k ) = ( x + a )

· ( τ σ ) a ( ( x + 1 ) + ) = [ ( τ σ ) 2 ] k ( ( x + 1 ) + ) = ( x + 1 + 2 k ) + = ( x + 1 + a ) +

· ( τ σ ) a ( ( x + 1 ) ) = [ ( τ σ ) 2 ] k ( ( x + 1 ) ) = ( x + 1 2 k ) = ( x + 1 a )

Now suppose a 1 ( mod 2 ) , so a = 2 k + 1 . Then

· ( τ σ ) a ( x + ) = ( τ σ ) ( τ σ ) 2 k ( x + ) = ( τ σ ) ( ( x 2 k ) + ) = ( x 2 k 3 ) = ( x a 2 )

· ( τ σ ) a ( x ) = ( τ σ ) ( τ σ ) 2 k ( x ) = ( τ σ ) ( ( x + 2 k ) ) = ( x + 2 k + 1 ) + = ( x + a ) +

· ( τ σ ) a ( ( x + 1 ) + ) = ( τ σ ) ( τ σ ) 2 k ( ( x + 1 ) + ) = ( τ σ ) ( ( x + 1 + 2 k ) + ) = ( x + 2 k + 2 ) = ( x + 1 + a )

· ( τ σ ) a ( ( x + 1 ) ) = ( τ σ ) ( τ σ ) 2 k ( ( x + 1 ) ) = ( τ σ ) ( ( x + 1 2 k ) ) = ( x + 2 2 k ) + = ( x + 3 a ) +

2) Suppose c 0 ( mod 2 ) , so c = 2 k . Then

· σ b τ c ( x + ) = σ b ( τ 2 ) k ( x + ) = σ b ( ( x + 2 k ) + ) = ( x + 2 k b ) + = ( x b + c ) +

· σ b τ c ( x ) = σ b ( τ 2 ) k ( x ) = σ b ( ( x + 2 k ) ) = ( x + 2 k + b ) = ( x + b + c )

· σ b τ c ( ( x + 1 ) + ) = σ b ( τ 2 ) k ( ( x + 1 ) + ) = σ b ( ( x + 1 2 k ) + ) = ( x + 1 b 2 k ) + = ( x + 1 b c ) +

· σ b τ c ( ( x + 1 ) ) = σ b ( τ 2 ) k ( ( x + 1 ) ) = σ b ( ( x + 1 2 k ) ) = ( x + 1 + b 2 k ) = ( x + 1 + b c ) .

Also, if c 1 ( mod 2 ) , so c = 2 k + 1 , then

· σ b τ c ( x + ) = σ b τ τ 2 k ( x + ) = σ b τ ( ( x + 2 k ) + ) = σ b ( ( x + 2 k + 2 ) ) = ( x + 2 k + 2 + b ) = ( x + b + c + 1 )

· σ b τ c ( x ) = σ b τ τ 2 k ( x ) = σ b τ ( ( x + 2 k ) ) = σ b ( ( x + 2 k ) + ) = ( x + 2 k b ) + = ( x b + c 1 ) +

· σ b τ c ( ( x + 1 ) + ) = σ b τ τ 2 k ( ( x + 1 ) + ) = σ b τ ( ( x + 1 2 k ) + ) = σ b ( ( x 1 2 k ) ) = ( x + b 1 2 k ) = ( x + b c )

· σ b τ c ( ( x + 1 ) ) = σ b τ τ 2 k ( ( x + 1 ) ) = σ b τ ( ( x + 1 2 k ) ) = σ b ( ( x + 1 2 k ) + ) = ( x + 1 2 k b ) + = ( x b c + 2 ) + .

We can use Theorem 2.2 to prove a uniqueness of representation theorem for the permutations σ , τ .

Theorem 2.3 Let a , b , c and a 0 . Suppose ( τ σ ) a = σ b τ c . Then a = b = c = 0 .

Proof. If ( τ σ ) a = σ b τ c , then their images agree on all values in S. In particular, on 0 + ,1 + ,0 and 1 . There are two cases:

1) First suppose a 0 ( mod 2 ) . Then we must have c 0 ( mod 2 ) in order to preserve sign parity. We substitute the values 0 + ,1 + ,0 and 1 into the equation ( τ σ ) a = σ b τ c and use Theorem 2.2. This yields

· At 0 + , have a = b + c .

· At 1 + , have a + 1 = b c + 1 .

· At 0 , have a = b + c .

· At 1 , have a + 1 = b c + 1 .

These equations imply that a = b = c = 0 .

2) Now suppose that a 1 ( mod 2 ) , and again substitute the values 0 + ,1 + ,0 and 1 , respectively. Now,

· At 0 + , have a 2 = b + c + 1 .

· At 1 + , have a + 1 = b c .

· At 0 , have a = b + c 1 .

· At 1 , have a + 3 = b c + 2 .

These equations imply that a = b = c = 1 . Since we assumed a 0 , this is impossible, so the desired result follows.

Now we return to the group G generated by the permutations σ , τ , σ 1 and τ 1 . We will show that G is finitely presented and determine a minimal presentation.

Theorem 2.4 The following words are in R ( G ) .

· ω 1 = τ 1 σ 2 τ σ 2

· ω 2 = σ 1 τ 2 σ τ 2

· ω 3 = σ 2 ω 1 1 σ 2 = τ 1 σ 2 τ σ 2

· ω 4 = σ 2 τ ω 1 τ 1 σ 2 = τ σ 2 τ 1 σ 2

· ω 5 = τ ω 1 1 τ 1 = τ σ 2 τ 1 σ 2

· ω 6 = σ ω 2 σ 1 = τ 2 σ τ 2 σ 1

· ω 7 = τ 2 ω 2 τ 2 = τ 2 σ 1 τ 2 σ

· ω 8 = τ 2 σ ω 2 1 σ 1 τ 2 = τ 2 σ τ 2 σ 1

Then N ( ω 1 , ω 2 ) = R ( G ) , and { ω 1 , ω 2 } is a finite presentation for G.

Proof. We will prove this theorem by demonstrating containment in both directions. To show N ( ω 1 , ω 2 ) R ( G ) , we first show that ω 1 and ω 2 are in R ( G ) . If x 0 ( mod 2 ) , then

· ω 1 ( x + ) = τ 1 σ 2 τ σ 2 ( x + ) = τ 1 σ 2 τ ( ( x 2 ) + ) = τ 1 σ 2 ( x ) = τ 1 ( ( x + 2 ) ) = x +

· ω 2 ( x + ) = σ 1 τ 2 σ τ 2 ( x + ) = σ 1 τ 2 σ ( ( x + 2 ) + ) = σ 1 τ 2 ( ( x + 1 ) + ) = σ 1 ( ( x 1 ) + ) = x +

· ω 1 ( x ) = τ 1 σ 2 τ σ 2 ( x ) = τ 1 σ 2 τ ( ( x + 2 ) ) = τ 1 σ 2 ( ( x + 2 ) + ) = τ 1 ( x + ) = x

· ω 2 ( x ) = σ 1 τ 2 σ τ 2 ( x ) = σ 1 τ 2 σ ( ( x + 2 ) ) = σ 1 τ 2 ( ( x + 3 ) ) = σ 1 ( ( x + 1 ) ) = x

If x 1 ( mod 2 ) , then

· ω 1 ( x + ) = τ 1 σ 2 τ σ 2 ( x + ) = τ 1 σ 2 τ ( ( x 2 ) + ) = τ 1 σ 2 ( ( x 4 ) ) = τ 1 ( ( x 2 ) ) = x +

· ω 2 ( x + ) = σ 1 τ 2 σ τ 2 ( x + ) = σ 1 τ 2 σ ( ( x 2 ) + ) = σ 1 τ 2 ( ( x 3 ) + ) = σ 1 ( ( x 1 ) + ) = x +

· ω 1 ( x ) = τ 1 σ 2 τ σ 2 ( x ) = τ 1 σ 2 τ ( ( x + 2 ) ) = τ 1 σ 2 ( ( x + 2 ) + ) = τ 1 ( x + ) = x

· ω 2 ( x ) = σ 1 τ 2 σ τ 2 ( x ) = σ 1 τ 2 σ ( ( x 2 ) ) = σ 1 τ 2 ( ( x 1 ) ) = σ 1 ( ( x + 1 ) ) = x

Since the conjugate of an element in R ( G ) is also in R ( G ) , it follows that N ( ω 1 , ω 2 ) R ( G ) . In addition, since ω 3 , ω 4 , , ω 8 are conjugates of ω 1 , ω 1 1 , ω 2 , or ω 2 1 , they are in R ( G ) .

Now, to show that the reverse inclusion holds, we assume that g is a word inG having the form g = A x y B , where A , B are words in G. Then g can be transformed to g ˜ = A y ˜ x ˜ B by multiplying g on the right by B 1 y 1 z y B where x , x ˜ , y , y ˜ , z are as indicated below:

Hence, g ˜ = g B 1 y 1 z y B , implying that g = g ˜ B 1 y 1 z 1 y B . Since B 1 y 1 z 1 y B N ( ω 1 , ω 2 ) , this shows that any word g G can be transformed to an element g ˜ by moving even powers of σ to the left and even powers of τ to the right. When this process is completed, g ˜ has the form σ b x τ c , where x has the form τ i 1 σ j 1 τ i 2 σ j 2 τ i n σ j n , with each i k , j k = ± 1 . If some exponent is −1, say, τ 1 , then we can represent this as τ 1 = τ τ 2 . Now, the τ 2 can be moved to the right. In this way, we eventually arrive at g ˜ = σ b ( τ σ ) a τ c , a 0 , and g ˜ = g C , with C N ( ω 1 , ω 2 ) . Now, suppose g R ( G ) . Since C N ( ω 1 , ω 2 ) , it follows that C R ( G ) . Therefore, g ˜ R ( G ) , so σ b ( τ σ ) a τ c is the identity, and ( τ σ ) a = σ b τ c in G. By Theorem 2.3, a = b = c = 0 . This means that g ˜ is the empty word, and g is the word C 1 N ( ω 1 , ω 2 ) . Thus, R ( G ) N ( ω 1 , ω 2 ) , and we have R ( G ) = N ( ω 1 , ω 2 ) .

Theorem 2.4 has an immediate corollary.

Corollary 2.5 Every word ω G has an equivalent form ω = σ b ( τ σ ) a τ c x , where x N ( ω 1 , ω 2 ) . and a 0 .

We are now ready to prove our main result.

Theorem 2.6 { ω 1 , ω 2 } is a minimal presentation for G.

Proof. We must show that ω 1 N ( ω 2 ) and ω 2 N ( ω 1 ) , where ω 1 = τ 1 σ 2 τ σ 2 and ω 2 = σ 1 τ 2 σ τ 2 . For any word x = σ i 1 τ j 1 σ i n τ j n , define e σ ( x ) = i 1 + i 2 + + i n , and e τ ( x ) = j 1 + j 2 + + j n . If y = z 1 ω 1 z , then e σ ( y ) = 4 . If y = z 1 ω 2 z , then e τ ( y ) = 4 . If y = z 1 ω 1 1 z , then e σ ( y ) = 4 . If y = z 1 ω 2 1 z , then e τ ( y ) = 4 . If x is a conjugate of ω 2 or ω 2 1 , then e σ ( x ) = 0 . If ω 1 N ( ω 2 ) , then ω 1 = x 1 x 2 x n , with each x i a conjugate of ω 2 or ω 2 1 . Therefore, 4 = e σ ( ω 1 ) = e σ ( x 1 ) + e σ ( x 2 ) + + e σ ( x n ) = 0 , a contradiction. Hence, ω 1 N ( ω 2 ) . By a similar argument, ω 2 N ( ω 1 ) .

Example 2.7 Transform ω = τ 4 σ 1 τ σ 2 τ 3 σ 3 by A x y B A y ˜ x ˜ B of Theorem 2.5 and show that ω N ( ω 1 , ω 2 ) .

The step-by-step process involves multiplying A x y B on the right by C = B 1 y 1 z y B (where z is a particular value of ω i or ω i 1 ) to obtain A y ˜ x ˜ B . At each stage, we make use of the reductions σ a σ b = σ a + b , τ a τ b = τ a + b , delete σ 0 , τ 0 . We halt the procedure when the identity, i.e., the empty word, is reached.

So the first step replaces τ 2 σ 1 with σ 1 τ 2 and simplifies by reducing exponents. At the final step, we obtain ω C 1 C 2 C 3 C 4 C 5 = I (i.e., the empty word). Hence, ω = ( C 1 C 2 C 3 C 4 C 5 ) 1 = C 5 1 C 4 1 C 3 1 C 2 1 C 1 1 . Expressing everything in terms of powers of σ and τ reduces the equation to ω = τ 4 σ 1 τ σ 2 τ 3 σ 3 , with deletion of σ 0 , τ 0 .

2.2. The Finite Permutation Groups G4n

We define a translation operation on S = + for each positive integer n. We then form equivalence classes denoted by S 4 n . The permutations σ , τ are well-defined mappings on S 4 n . The permutation group generated by σ , τ on S 4 n is denoted by G 4 n . Theorem 2.2 is generalized in order to determine the relators R ( G 4 n ) of G 4 n . We also determine the order of each G 4 n .

Definition 2.8 Let n be a positive integer and S = + . Define a mapping ϕ n : S S by

· ϕ n ( x + ) = ( x + n ) + = σ n ( x + )

· ϕ n ( x ) = ( x + n ) = σ n ( x − )

If x S , then x + n denotes ϕ n ( x ) .

Theorem 2.9 If n is even, then σ ( x + n ) = σ ( x ) + n , and τ ( x + n ) = τ ( x ) + n

Proof. If x = x + , then σ ( x + + n ) = σ ( ( x + n ) + ) = ( x + n 1 ) + = σ ( x + ) + n , and

τ ( x + + n ) = τ ( ( x + n ) + ) = { ( x + n + 2 ) , if x 0 ( mod 2 ) ( x + n 2 ) , if x 1 ( mod 2 )

=

{ τ ( x + ) + n , if x 0 ( mod 2 ) τ ( x + ) + n , if x 1 ( mod 2 )

If x = x , then σ ( x + n ) = σ ( ( x + n ) ) = ( x + n + 1 ) = σ ( x ) + n , and τ ( x + n ) = τ ( ( x + n ) ) = ( x + n ) + = τ ( x ) + n .

Definition 2.10 Let n be a positive integer. Define a relation n ˜ on S by

· x + n ˜ y + if x y ( mod 2 n )

· x n ˜ y if x y ( mod 2 n )

Theorem 2.11 n ˜ is an equivalence relation on S.

Proof. Trivial, since x y ( mod 2 n ) is an equivalence relation on .

Remark: For simplicity of notation, we write ~ instead of n ˜ when n is a fixed positive integer.

Definition 2.12 S 4 n is the set of equivalence classes of S under ~.

Example 2.13 Let [ ] denote an equivalence class in S 4 n . Then

· S 4 = { [ 0 + ] , [ 1 + ] , [ 0 ] , [ 1 ] }

· S 8 = { [ 0 + ] , [ 1 + ] , [ 2 + ] , [ 3 + ] , [ 0 ] , [ 1 ] , [ 2 ] , [ 3 ] }

Theorem 2.14 Let x , y S . If x ~ y , then σ ( x ) ~ σ ( y ) and τ ( x ) ~ τ ( y ) . Therefore, σ , τ induce permutations of S 4 n .

Proof. Suppose x + ~ y + . Then x y ( mod 2 n ) , so x + = y + + 2 k n for some k . By Theorem 2.9, σ ( x + ) = σ ( y + + 2 k n ) = σ ( y + ) + 2 k n , and τ ( x + ) = τ ( y + + 2 k n ) = τ ( y + ) + 2 k n . Therefore, σ ( x + ) ~ σ ( y + ) and τ ( x + ) ~ τ ( y + ) ; an identical argument applies to x ~ y . Therefore, σ , τ induce maps of S 4 n to S 4 n . Since σ , τ : S S are onto, the induced maps on S 4 n are onto.

RTS: the induced maps are 1-1. Suppose σ ( [ x + ] ) = σ ( [ y + ] ) . Then σ ( x + ) σ ( y + ) , implying, for some k , σ ( x + ) = σ ( y + ) + 2 k n = σ ( y + + 2 k n ) by Theorem 2.2. Since σ is 1-1, x + = y + + 2 k n , and [ x + ] = [ y + ] . Identical arguments apply to σ ( [ x ] ) = σ ( [ y ] ) , τ ( [ x + ] ) = τ ( [ y + ] ) , and τ ( [ x ] ) = τ ( [ y ] ) .

Definition 2.15 G 4 n is the group of permutations of S 4 n generated by the permutations of σ and τ .

Corollary 2.5 still applies, so that each word w in G 4 n has an equivalent word representation w = σ b ( τ σ ) a τ c x with a 0 and x N ( ω 1 , ω 2 ) . However, Theorem 2.3 no longer applies, so we require a modification.

Theorem 2.16 Let σ , τ : S 4 n S 4 n as defined above. Let a , b , c be integers. Then ( τ σ ) a = σ b τ c if

1) a b c 0 ( mod 2 ) , 2 b 0 ( mod 2 n ) , 2 c 0 ( mod 2 n ) , a b + c ( mod 2 n ) , or

2) a b c 1 ( mod 2 ) , 2 ( b + 1 ) 0 ( mod 2 n ) , 2 ( c + 1 ) 0 ( mod 2 n ) , a b + c + 1 (mod 2n).

Proof. First suppose a 0 ( mod 2 ) and ( τ σ ) a = σ b τ c . The formula for ( τ σ ) a in Theorem 2.2 imply that c 0 ( mod 2 ) . Let x 0 ( mod 2 ) . Equating ( τ σ ) a and σ b τ c on the classes [ x + ] , [ ( x + 1 ) + ] , [ x ] , [ ( x + 1 ) ] .

1) [ ( x a ) + ] = [ ( x b + c ) + ]

2) [ ( x + 1 + a ) + ] = [ ( x + 1 b c ) + ]

3) [ ( x + a ) ] = [ ( x + b + c ) ]

4) [ ( x + 1 a ) ] = [ ( x + 1 + b c ) ]

5) Equations (1)-(4) imply, by Definition 2.10, that a b + c ( mod 2 n )

6) a + 1 b c + 1 ( mod 2 n )

7) a b + c ( mod 2 n )

8) a + 1 b c + 1 ( mod 2 n ) . Now, (5) and (7) imply that 2 c 0 ( mod 2 n ) . Additionally, (5) and (6) imply that 2 b 0 ( mod 2 n ) . Finally, (7) implies a b + c ( mod 2 n ) . Hence, a 0 ( mod 2 ) , and Equations (1)-(4) imply

9) a b c 0 ( mod 2 )

10) 2 b 0 ( mod 2 n )

11) 2 c 0 ( mod 2 n )

12) a b + c ( mod 2 n )

Conversely, suppose 9 - 12 hold. Then, working mod 2n, a ( b + c ) b c + 2 c b + c , while a + 1 b + c + 1 b + c + 1 2 b 2 c b c + 1 , with a b + c , and thus, a + 1 ( b + c ) + 1 b c + 1 + 2 b b c + 1 , so Equations (5)-(8) hold. This Implies (1)-(4), which implies ( τ σ ) a = σ b τ c .

Now suppose a 1 ( mod 2 ) and ( τ σ ) a = σ b τ c . Again, by Theorem 2.2, we must have c 1 ( mod 2 ) and the equations

1') a 2 ( b + c + 1 ) ( mod 2 n )

2') a + 1 ( b c ) ( mod 2 n )

3') a ( b + c 1 ) ( mod 2 n )

4') a + 3 ( b c + 2 ) ( mod 2 n ) ; substituting a c 1 ( mod 2 ) into (2') yields 2 ( b 1 ) ( mod 2 ) , so

5') a b c 1 ( mod 2 ) ; (1') and (2') yields

6') 2 ( b + 1 ) 0 ( mod 2 n ) ; (1') and (3') yields

7') 2 ( c + 1 ) 0 ( mod 2 n ) ; (4') yields

8') a ( b + c + 1 ) ( mod 2 n )

Conversely, if (5')-(8') hold, then, working mod 2n,

· a 2 b c 1 2 + 2 ( b + 1 ) + 2 ( c + 1 ) b + c + 1

· a + 1 b + c + 1 + 1 2 ( c + 1 ) b c

· a b + c + 1 2 ( b + 1 ) b + c 1

· a + 3 b c 1 + 3 b c + 2

Hence, (1')-(4') hold, which implies ( τ σ ) a = σ b τ c .

Corollary 2.17 σ b ( τ σ ) a τ c is the identity in G 4 n if and only if

1) a b c 0 ( mod 2 ) , 2 b 0 ( mod 2 n ) , 2 c 0 ( mod 2 n ) , a + b + c 0 ( mod 2 n ) , or

2) a b c 1 ( mod 2 ) , 2 ( b 1 ) 0 ( mod 2 n ) , 2 ( c 1 ) 0 ( mod 2 n ) , a + b + c 1 ( mod 2 n )

Proof. σ b ( τ σ ) a τ c is the identity if and only if ( τ σ ) a = σ b τ c . Now, replace b , c with b , c in Theorem 2.14.

Corollary 2.18 If a word ω represents the identity in G 4 n , i.e., ω R ( G 4 n ) , then ω = σ b ( τ σ ) a τ c x where x N ( ω 1 , ω 2 ) and a , b , c satisfy (1) or (2) of Corollary 2.17.

Proof. By Corollary 2.5, there is a word y N ( ω 1 , ω 2 ) such that ω y = σ b ( τ σ ) a τ c . Hence, ω = σ b ( τ σ ) a τ c y 1 . Since ω and y 1 represent the identity in G 4 n , σ b ( τ σ ) a τ c represents the identity, and Cor. 2.17 applies.

We can improve Corollary 2.18 as follows:

Theorem 2.19 A word ω R ( G 4 n ) if ω = g σ b ( τ σ ) a τ c g 1 ω , where ω N ( ω 1 , ω 2 ) , g = σ or 1 (i.e., empty word), and a, b, c satisfy (henceforth (*)): a b c 0 ( mod 2 ) , 2 b 0 ( mod 2 n ) , 2 c 0 ( mod 2 n ) , a + b + c 0 ( mod 2 n ) .

Proof. Suppose ω R ( G 4 n ) . By Corollary 2.18, ω = σ b ( τ σ ) a τ c x where x N ( ω 1 , ω 2 ) , and a, b, c satisfy (1) or (2) of Corollary 2.17. Suppose they satisfy (2). Making use of τ 2 σ = σ τ 2 , which follows from the relator ω 6 = τ 2 σ τ 2 σ 1 , and τ 2 σ = σ τ 2 , which follows from the relator ω 8 = τ 2 σ τ 2 σ 1 , we can move even powers of τ to the right to obtain

ω = σ b ( τ σ ) a τ c x = σ σ b 1 ( τ σ ) a τ τ c 1 σ σ 1 x = σ σ b 1 ( τ σ ) a τ σ τ 1 c σ 1 x y = σ σ b ( τ σ ) a τ c σ 1 ω

where y N ( ω 1 , ω 2 ) , a = a + 1 , b = b 1 , c = 1 c , ω = x y N ( ω 1 , ω 2 ) . Then

a b c 0 ( mod 2 ) , 2 b 0 ( mod 2 n ) , 2 c 0 ( mod 2 n ) , and a + b + c = a + 1 + b 1 + 1 c = a + b + c 2 ( c 1 ) 1 0 ( mod 2 n ) .

If (1) holds, we can take g = 1 and ω = x .

Next we determine the relators R ( G 4 n ) and minimal presentations for G 4 n . We first consider n = 1 , then n odd and greater than 1, then n even.

Theorem 2.20 R ( G 4 ) = N ( σ 2 , ( τ σ ) 2 , τ 2 ) and { σ 2 , ( τ σ ) 2 , τ 2 } is a minimal presentation for G 4 .

Proof. The diagram for S 4 (see Figure 2) shows that σ 2 , ( τ σ ) 2 , and τ 2 all belong to R ( G 4 ) . Therefore, N ( σ 2 , ( τ σ ) 2 , τ 2 ) R ( G 4 ) . Conversely, suppose ω R ( G 4 ) . By Theorem 2.19, ω = g σ b ( τ σ ) a τ c g 1 ω with a , b , c even and ω N ( ω 1 , ω 2 ) , and g = σ or 1. But ω 1 = τ 1 σ 2 τ σ 2 and ω 2 = σ 1 τ 2 σ τ 2 belong to N ( σ 2 , ( τ σ ) 2 , τ 2 ) , so R ( G 4 ) N ( σ 2 , ( τ σ ) 2 , τ 2 ) .

Now we show that { σ 2 , ( τ σ ) 2 , τ 2 } is a minimal presentation for G 4 . First, we show that ( τ σ ) 2 cannot be expressed as a product of conjugates of σ 2 , σ 2 , τ 2 , τ 2 . Suppose it could, so (a) ( τ σ ) 2 = c 1 c 2 c k , where each c i is a conjugate of σ 2 , σ 2 , τ 2 , τ 2 . 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 { 1,2,3 } and σ = ( 12 ) , τ = ( 23 ) . Then σ 2 = τ 2 = i d ,

Figure 2. The diagram shows σ , τ on S 4 .

and τ σ = ( 132 ) , ( τ σ ) 2 = ( 123 ) as permutations in G. In G, (a) becomes ( 123 ) = i d , which is a contradiction. Therefore, ( τ σ ) 2 cannot have (a) as a representation in the free group of σ , τ .

For the other two cases, take (b) σ 2 = c 1 c 2 c k , with c i conjugate in τ 2 , ( τ σ ) 2 . Choose σ = ( 132 ) , τ = ( 23 ) , ( τ σ ) = ( 12 ) . Then (b) yields ( 123 ) = i d , a contradiction. Finally, take (c) τ 2 = c 1 c 2 c k , c i conjugate in σ 2 , ( τ σ ) 2 . Choose σ = ( 12 ) , τ = ( 132 ) , ( τ σ ) = ( 23 ) . Then (c) yields ( 123 ) = i d , a contradiction. Therefore, { σ 2 , ( τ σ ) 2 , τ 2 } is a minimal presentation for G 4 .

Theorem 2.21 If n is odd and n > 1 , then R ( G 4 n ) = N ( σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 , ω 2 ) and { σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 , ω 2 } is a minimal presentation.

Proof. Clearly, σ 2 n , ( τ σ ) 2 n , τ 2 n all satisfy the hypothesis of Theorem 2.19, so they clearly belong to R ( G 4 n ) . Since ω 1 , ω 2 also belong to R ( G 4 n ) , we have N ( σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 , ω 2 ) R ( G 4 n ) .

Conversely, suppose ω R ( G 4 n ) . By Theorem 2.19, ω = g σ b ( τ σ ) a τ c g 1 ω , with a , b , c satisfying (*), and ω N ( ω 1 , ω 2 ) with g = σ or 1. Then a , b , c are multiples of 2n, so ω N ( σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 , ω 2 ) .

Let F ( σ , τ ) be a free group on the symbols σ , τ . To show { σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 , ω 2 } is a minimal presentation, we argue as follows:

Let ω = σ i 1 τ j 1 σ i k τ j k . Define e σ ( ω ) = i 1 + i 2 + + i k , e τ ( ω ) = j 1 + j 2 + + j k Then e σ , e τ are well-defined for ω F ( σ , τ ) . Since ω 1 = τ 1 σ 2 τ σ 2 , ω 2 = σ 1 τ 2 σ τ 2 , we have e σ ( ω 1 ) = 4 , e σ ( ω 2 ) = 0 . Also, e σ ( σ 2 n ) = e σ ( ( τ σ ) 2 n ) = 2 n , and e σ ( τ 2 n ) = 0 . If ω 1 N ( σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 2 ) , applying e σ to the representation for ω 1 yields 4 0 ( mod 2 n ) . Since n 3 , this is a contradiction. Therefore, ω 1 N ( σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 2 ) . Using e τ and employing a similar argument, we obtain ω 2 N ( σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 ) .

Now suppose ( τ σ ) 2 n N ( σ 2 n , τ 2 n , ω 1 , ω 2 ) so that ( τ σ ) 2 n = c 1 c 2 c k , where each c i is a conjugate in N ( σ 2 n , τ 2 n , ω 1 , ω 2 ) . Since this equation holds in F ( σ , τ ) , it most hold in any group G in which σ , τ are assigned values. Let G be the permutation group on { 1,2, ,2 n + 1 } and set σ = ( 12 ) ( 34 ) ( 2 n 1,2 n ) , τ = ( 23 ) ( 45 ) ( 2 n ,2 n + 1 ) . Then σ 2 = τ 2 = i d , so c 1 c 2 c k = i d in G, but τ σ = ( 1 , 3 , 5 , , ( 2 n 1 ) , ( 2 n + 1 ) , 2 n , ( 2 n 2 ) , , 2 ) , which has order 2 n + 1 , so that ( τ σ ) 2 n i d in G. Therefore, ( τ σ ) 2 n N ( σ 2 n , τ 2 n , ω 1 , ω 2 ) .

To show that σ 2 n N ( τ 2 n , ( τ σ ) 2 n , ω 1 , ω 2 ) , let G be as above, with σ = ( 1 , 2 , 3 , , 2 n , 2 n + 1 ) , τ = ( 1 , 2 ) ( 3 , 2 n + 1 ) ( 4 , 2 n ) ( 5 , 2 n 1 ) ( n + 1 , n + 3 ) . Then τ σ = ( 2,2 n + 1 ) ( 3,2 n ) ( n + 1, n + 2 ) , while τ σ 2 = ( 1 , 2 n + 1 ) ( 2 , 2 n ) ( 3 , 2 n 1 ) ( n , n + 2 ) . Thus, σ 2 n i d , but τ 2 n = ( τ σ ) 2 n = i d , ω 2 = σ 1 τ 2 σ τ 2 = i d , ω 1 = τ 1 σ 2 τ σ 2 = i d . Therefore, σ 2 n N ( τ 2 n , ( τ σ ) 2 n , ω 1 , ω 2 ) .

Finally, we show that τ 2 n N ( σ 2 n , τ 2 n , ω 1 , ω 2 ) . Let G be as above, with τ = ( 1 , 2 , 3 , , 2 n , 2 n + 1 ) , σ = ( 1 , 2 ) ( 3 , 2 n + 1 ) ( 4 , 2 n ) ( 5 , 2 n 1 ) ( n + 1 , n + 3 ) . Then τ σ = ( 1 , 3 ) ( 4 , 2 n + 1 ) ( 5 , 2 n ) ( n + 2 , n + 3 ) , σ τ 2 = ( 1,2 n + 1 ) ( 2,2 n ) ( 3,2 n 1 ) ( n , n + 2 ) . Thus, σ 2 n = ( τ σ ) 2 n = i d , ω 1 = τ 1 σ 2 τ σ 2 = i d , ω 2 = σ 1 τ 2 σ τ 2 = i d , but τ 2 n i d . Therefore, τ 2 n N ( σ 2 n , ( τ σ ) 2 n , ω 1 , ω 2 ) . This proves that { σ 2 n , ( τ σ ) 2 n , τ 2 n , ω 1 , ω 2 } is a minimal presentation for R ( G 4 n ) , the relators in G 4 n .

Theorem 2.22 If n is even, then R ( G 4 n ) = N ( ( τ σ ) 2 n , σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 ) .

Proof. First note that τ 2 n , σ 2 n N ( ( τ σ ) 2 n , σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 ) , since

τ 2 n = ( τ σ ) 2 n [ ( τ σ ) n [ ( τ σ ) n τ n ] ( τ σ ) n ] ( τ σ ) n τ n and σ 2 n = σ n ( τ σ ) n [ ( τ σ ) n [ σ n ( τ σ ) n ] ( τ σ ) n ] ( τ σ ) 2 n . Therefore it is sufficient to show that R ( G 4 n ) = N ˜ = N ( σ 2 n , τ 2 n , ( τ σ ) 2 n , σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 ) . By Theorem 2.19, ω R ( G 4 n ) if ω = g σ b ( τ σ ) a τ c g 1 ω , with ω N ( ω 1 , ω 2 ) , g = σ or 1, and a b c 0 ( mod 2 ) , 2 b 2 c 0 ( mod 2 n ) , a + b + c 0 ( mod 2 n ) . The conditions on a , b , c are equivalent to a b c 0 ( mod 2 ) , a b c 0 ( mod n ) , a + b + c 0 ( mod 2 n ) . Each of the elements σ 2 n , τ 2 n , ( τ σ ) 2 n , σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 has the required form ω of Theorem 2.19. Therefore, N ˜ R ( G 4 n ) .

Conversely, suppose ω R ( G 4 n ) with ω = g σ b ( τ σ ) a τ c g 1 ω as above. It remains to show that σ b ( τ σ ) a τ c N ˜ , which would imply that ω N ˜ . There are four cases.

1) b 0 ( mod 2 n ) and c 0 ( mod 2 n ) _

Then a 0 ( mod 2 n ) , so a = 2 n a , b = 2 n b , c = 2 n c , and σ b ( τ σ ) a τ c = ( σ 2 n ) b [ ( τ σ ) 2 n ] a ( τ 2 n ) c N ˜ .

2) b 0 ( mod 2 n ) and c 0 ( mod 2 n ) _

Since a + b + c 0 ( mod 2 n ) , we must have a 0 ( mod 2 n ) . Then a = 2 n a + n , b = 2 n b , c = 2 n c + n , so

σ b ( τ σ ) a τ c = ( σ 2 n ) b [ ( τ σ ) 2 n ] a [ ( τ σ ) n τ n ] ( τ 2 n ) c N ˜ .

3) c 0 ( mod 2 n ) and b 0 ( mod 2 n ) _

Then a 0 ( mod 2 n ) , so a = 2 n a + n , b = 2 n b + n , c = 2 n c , and σ b ( τ σ ) a τ c = ( σ 2 n ) b [ σ n ( τ σ ) n ] [ ( τ σ ) 2 n ] a ( τ 2 n ) c N ˜ .

4) b 0 ( mod 2 n ) and c 0 ( mod 2 n ) _

Then a 0 ( mod 2 n ) , so a = 2 n a , b = 2 n b + n , c = 2 n c + n , and σ b ( τ σ ) a τ c = ( σ 2 n ) b [ σ n ( τ σ ) n ] [ ( τ σ ) 2 n ] a 1 [ ( τ σ ) n τ n ] ( τ 2 n ) c N ˜ .

Therefore, R ( G 4 n ) N ˜ .

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 x , y such that x n ( y x ) n = ( y x ) n y n = y 1 x 2 y x 2 = 1 . Then ( y x ) 2 n = 1 .

Proof. First note that y 1 x m y x m = 1 for all even m > 0 . This is true for m = 2 by hypothesis, and the general result follows inductively from y 1 x m + 2 y x m + 2 = y 1 x m y ( y 1 x 2 y x 2 ) x m = y 1 x m y x m = 1 . Also, x n ( y x ) n = 1 implies x n = ( y x ) n , and ( y x ) n y n = 1 implies y n = ( y x ) n , so x n = y n and ( y x ) 2 n = y 2 n . Therefore, it suffices to show that y 2 n = 1 . But x n = y n and y 1 x n y x n = 1 imply that y 2 n = y 1 y n y y n = y 1 x n y x n = 1 .

Corollary 2.24 If n is even, then R ( G 4 n ) = N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 ) .

Proof. Since ω 1 = τ 1 σ 2 τ σ 2 , Theorem 2.23 implies that

( τ σ ) 2 n N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 ) . Therefore,

R ( G 4 n ) = N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 ) . Now we determine minimal presentation for R ( G 4 n ) when n is even. We start with n = 2 .

Theorem 2.25 { σ 2 ( τ σ ) 2 , ( τ σ ) 2 τ 2 , ω 1 } is a minimal presentation for G 8 .

Proof.

1) Since σ 2 = τ 2 follows from σ 2 ( τ σ ) 2 = ( τ σ ) 2 τ 2 = 1 , this implies that ω 2 = σ 1 τ 2 σ τ 2 N ( σ 2 ( τ σ ) 2 , ( τ σ ) 2 τ 2 , ω 1 ) .

2) We have σ 2 ( τ σ ) 2 N ( ( τ σ ) 2 τ 2 , ω 1 ) since e τ ( σ 2 ( τ σ ) 2 ) = 2 , whereas e τ ( ( τ σ ) 2 τ 2 ) = 4 and e τ ( ω 1 ) = 0 are both divisible by 4.

3) We have ( τ σ ) 2 τ 2 N ( σ 2 ( τ σ ) 2 , ω 1 ) since e σ ( ( τ σ ) 2 τ 2 ) = 2 , whereas e σ ( σ 2 ( τ σ ) 2 ) = 4 and e σ ( ω 1 ) = e σ ( τ 1 σ 2 τ σ 2 ) = 4 are both divisible by 4.

4) To show that ω 1 N ( σ 2 ( τ σ ) 2 , ( τ σ ) 2 τ 2 ) , let G be the permutation group on { 1,2,3 } and set σ = τ = { 1,2,3 } . Then ( τ σ ) 2 τ 2 = σ 2 ( τ σ ) 2 = σ 6 = 1 , but ω 1 = τ 1 σ 2 τ σ 2 = σ 4 = σ 1 , so ω 1 N ( σ 2 ( τ σ ) 2 , ( τ σ ) 2 τ 2 ) .

Theorem 2.26 If n is even, n > 2 , then { σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 } is a minimal presentation for G 4 n .

Proof. Corollary 2.24 states that it is a presentation. To demonstrate its minimality, we consider two cases:

1) n 0 ( mod 4 ) _ : In this case, n = 2 m with m > 1 , m odd.

(a) σ n ( τ σ ) n N ( ( τ σ ) n τ n , ω 1 , ω 2 )

because e τ ( σ n ( τ σ ) n ) = n 0 ( mod 4 ) , whereas

e τ ( ( τ σ ) n τ n ) = 2 n 0 ( mod 4 ) , e τ ( ω 1 ) = e τ ( τ 1 σ 2 τ σ 2 ) = 0 0 ( mod 4 ) ,

and

e τ ( ω 2 ) = e τ ( σ 1 τ 2 σ τ 2 ) = 4 0 ( mod 4 )

(b) ( τ σ ) n τ n N ( σ n ( τ σ ) n , ω 1 , ω 2 ) , because e σ ( ( τ σ ) n τ n ) = n 0 ( mod 4 ) , but σ n ( τ σ ) n , ω 1 , ω 2 all have e σ values divisible by 4.

(c) ω 1 N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 2 ) because e σ ( ω 1 ) = 4 0 ( mod m ) , but the other elements have e σ values divisible by m.

(d) ω 2 N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 ) because e τ ( ω 2 ) = 4 0 ( mod m ) , but the other elements have e τ values divisible by m.

2) n 0 ( mod 4 ) _ : In this case, n = 4 k .

(a) ( τ σ ) n τ n N ( σ n ( τ σ ) n , ω 1 , ω 2 ) . Let G be the permutation group on { 1,2, ,2 n , 1 ˜ , 2 ˜ , , 2 n ˜ } . Let

σ = ( 1 , 3 ˜ , 5 , 7 ˜ , , 2 n 1 ˜ ) ( 1 ˜ , 3 , 5 ˜ , 7 , , ( 2 n 1 ) ) ( 2 n , 2 n 2 ˜ , , 2 ˜ ) ( 2 n ˜ , ( 2 n 2 ) , , 2 ) ,

and τ = ( 1 , 2 , 3 , , 2 n ) ( 2 n ˜ , 2 n 1 ˜ , , 2 ˜ , 1 ˜ ) . Then σ n = 1 , τ n 1 . Also, ( τ σ ) 2 = 1 , so ( τ σ ) n = 1 . Therefore σ n ( τ σ ) n = 1 , but ( τ σ ) n τ n = τ n 1 . Let

x = { y ˜ , if x = y y , if x = y ˜

Let a + b denote addition (mod 2n).

If x is odd, x σ 2 x + 4 τ ( x + 4 ) ± 1 σ 2 x ± 1 τ 1 x

If x is even, x σ 2 x 4 τ ( x 4 ) ± 1 σ 2 x ± 1 τ 1 x

so ω 1 = τ 1 σ 2 τ σ 2 = 1 in G.

For example, if n = 4 , then G is the permutation group on { 1,2,3, ,8, 1 ˜ , 2 ˜ , , 8 ˜ } .

σ = ( 1, 3 ˜ ,5, 7 ˜ ) ( 1 ˜ ,3, 5 ˜ ,7 ) ( 8, 6 ˜ ,4, 2 ˜ ) ( 8 ˜ ,6, 4 ˜ ,2 )

σ 2 = ( 1,5 ) ( 3 ˜ , 7 ˜ ) ( 1 ˜ , 5 ˜ ) ( 3,7 ) ( 8,4 ) ( 6 ˜ , 2 ˜ ) ( 8 ˜ , 4 ˜ ) ( 6,2 )

τ = ( 1,2,3, ,8 ) ( 8 ˜ , 7 ˜ , , 1 ˜ )

τ 1 = ( 8,7, ,1 ) ( 1 ˜ , 2 ˜ , , 8 ˜ )

τ σ 2 = ( 1,6,3,8,5,2,7,4 ) ( 1 ˜ , 4 ˜ , 7 ˜ , 2 ˜ , 5 ˜ , 8 ˜ , 3 ˜ , 6 ˜ )

τ 1 σ 2 = ( 1,4,7,2,5,8,3,6 ) ( 1 ˜ , 6 ˜ , 3 ˜ , 8 ˜ , 5 ˜ , 2 ˜ , 7 ˜ , 4 ˜ )

so τ 1 σ 2 τ σ 2 = 1

For ω 2 = σ 1 τ 2 σ τ 2 , we have:

If x is odd, x τ 2 x ± 2 σ [ ( x ± 2 ) + 2 ] τ 2 ( x + 2 ) σ 1 x

If x is even, x τ 2 x ± 2 σ [ ( x ± 2 ) 2 ] τ 2 ( x 2 ) σ 1 x

Therefore, ω 2 = 1 in G.

Since σ n ( τ σ ) n , ω 1 , ω 2 are equal to the identity in G, but ( τ σ ) n τ n 1 , it follows that ( τ σ ) n τ n N ( σ n ( τ σ ) n , ω 1 , ω 2 ) .

(b) σ n ( τ σ ) n N ( ( τ σ ) n τ n , ω 1 , ω 2 ) .

Using σ and τ from part (a), we note that ( σ τ ) 2 = 1 . Therefore, if we exchange the definitions of σ and τ , we obtain σ n ( τ σ ) n 1 , but ( τ σ ) n τ n = ω 1 = ω 2 = 1 in G, which proves (b).

(c) ω 1 N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 2 ) .

Recall that n = 4 k . Let G be the permutation group on { 1,2, ,8 k } .

If k = 1 , let σ = ( 1 , 2 , 3 , 4 ) ( 5 , 6 , 7 , 8 ) , τ = ( 1 , 5 ) ( 2 , 6 )

Then τ σ = ( 1,6,7,8 ) ( 2,3,4,5 ) , so σ 4 = τ 4 = ( τ σ ) 4 = 1 , but (using τ 1 = τ ) ω 1 ( 1 ) = τ σ 2 τ σ 2 ( 1 ) = τ σ 2 τ ( 3 ) = τ σ 2 ( 3 ) = τ ( 1 ) = 5 .

If k > 1 , let σ = ( 1,2, ,4 k ) ( 4 k + 1,4 k + 2, ,8 ) ) and τ = ( 1,4 k + 1 ) ( 2,4 k + 2 ) ( 4 k ,4 k + 4 k )

Then σ n = τ n = ω 2 = 1 .

Also, τ σ = ( 1 , 4 k + 2 , 3 , 4 k + 4 , , 4 k 1 , 4 k + 4 k ) ( 2 , 4 k + 3 , 4 , 4 k + 5 , , 4 k , 4 k + 1 ) , so ( τ σ ) n = 1

But ω 1 ( 1 ) = τ σ 2 τ σ 2 ( 1 ) = τ σ 2 τ ( 3 ) = τ σ 2 ( 4 k + 3 ) = τ ( 4 k + 5 ) = 5 .

Therefore ω 1 N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 2 ) .

(d) ω 2 N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 ) . Let G be defined as in part (c).

If we exchange σ , τ from part (c), we obtain ω 2 N ( σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 ) .

In summary, minimal presentations for R ( G 4 n ) are:

(a) { σ 2 , τ 2 , ( τ σ ) 2 } for n = 1 ;

(b) { σ 2 ( τ σ ) 2 , ( τ σ ) 2 τ 2 , ω 1 } for n = 2 ;

(c) { σ 2 n , τ 2 n , ( τ σ ) 2 n , ω 1 , ω 2 } for n odd, n > 1 ;

(d) { σ n ( τ σ ) n , ( τ σ ) n τ n , ω 1 , ω 2 } for n even, n > 2 .

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 G 4 n :

Lemma 2.28 The following identities hold in G 4 n :

1) ( τ σ ) 1 σ 2 = σ 2 ( τ σ ) 1

2) ( τ σ ) 1 σ 2 = σ 2 ( τ σ ) 1

3) τ ( τ σ ) a τ c = σ 2 ( τ σ ) 1 τ 1 ( τ σ ) a 1 τ c , a , c

4) τ 1 ( τ σ ) a τ c = σ 2 ( τ σ ) 1 τ ( τ σ ) a 1 τ c , a , c

Proof (of Lemma 2.28):

1) ω 1 = τ 1 σ 2 τ σ 2 R ( G 4 n ) , so τ 1 σ 2 = σ 2 τ 1 ( τ σ ) 1 σ 2 = σ 1 τ 1 σ 2 = σ 2 σ 1 τ 1 = σ 2 ( τ σ ) 1 .

2) ω 3 = τ 1 σ 2 τ σ 2 R ( G 4 n ) , so τ 1 σ 2 = σ 2 τ 1 ( τ σ ) 1 σ 2 = σ 1 τ 1 σ 2 = σ 2 σ 1 τ 1 = σ 2 ( τ σ ) 1 .

3) τ ( τ σ ) a τ c = τ 2 σ ( τ σ ) a 1 τ c = σ τ 2 ( τ σ ) a 1 τ c (since ω 2 = σ 1 τ 2 σ τ 2 R ( G 4 n ) ) = [ σ 2 ( τ σ ) 1 τ ] τ 2 ( τ σ ) a 1 τ c = σ 2 ( τ σ ) 1 τ 1 ( τ σ ) a 1 τ c .

4) τ 1 ( τ σ ) a τ c = σ ( τ σ ) a 1 τ c = σ 2 ( τ σ ) 1 τ ( τ σ ) a 1 τ c .

Lemma 2.29 Every element x G 4 n has representation x = σ b ( τ σ ) a τ c with b even.

Proof (of Lemma 2.29): By Corollary 2.5, every x G 4 n has a representation x = σ b ( τ σ ) a τ c , with a 0 . If b is even, the proof is complete. Let b be odd and set b = B + 1 , B even. Then

x = σ B σ ( τ σ ) a τ c = σ B σ 2 ( τ σ ) 1 τ [ ( τ σ ) a τ c ] = σ B σ 2 ( τ σ ) 1 σ 2 ( τ σ ) 1 τ 1 ( τ σ ) a 1 τ c

(by part (3) of Lemma 2.28) = σ B σ 2 ( τ σ ) 1 σ 2 ( τ σ ) 1 σ 2 ( τ σ ) 1 τ ( τ σ ) a 2 τ c (by part (4) of Lemma 2.28)

Continuing to apply parts (3) and (4) we obtain

x = ( σ B [ σ 2 ( τ σ ) 1 ] a + 1 τ 1 τ c , a odd σ B [ σ 2 ( τ σ ) 1 ] a + 1 τ τ c , a even

By parts (1) and (2) of Lemma 2.28, all powers of σ 2 can be commuted to the left of ( τ σ ) 1 while preserving even parity. Hence, x = σ B ( τ σ ) ( a + 1 ) τ c ± 1 with B even.

Theorem 2.30 The order of G 4 n is:

1) 4n3 if n is odd

2) n3 if n is even.

Proof.

1) Suppose n is odd. By Lemma 2.29, x = σ b ( τ σ ) a τ c , with b even. By Theorems 2.20 and 2.21, σ 2 n , ( τ σ ) 2 n , τ 2 n all belong to R ( G 4 n ) . Therefore we can take x = σ b ¯ ( τ σ ) a ¯ τ c ¯ , with 0 a ¯ , b ¯ , c ¯ < 2 n , and b ¯ even. There are ( 2 n ) ( n ) ( 2 n ) = 4 n 3 possibilities for a ¯ , b ¯ , c ¯ . If σ b ¯ 1 ( τ σ ) a ¯ 1 τ c ¯ 1 = σ b ¯ 2 ( τ σ ) a ¯ 2 τ c ¯ 2 , then ( τ σ ) a ¯ 2 σ b ¯ 1 b ¯ 2 ( τ σ ) a ¯ 1 τ c ¯ 1 c ¯ 2 = 1 . Since b ¯ 1 b ¯ 2 is even, we can use the commutation rules to obtain σ ± ( b ¯ 1 b ¯ 2 ) ( τ σ ) a ¯ 1 a ¯ 2 τ c ¯ 1 c ¯ 2 = 1 .

Also, Corollary 2.17 implies that a ¯ 1 a ¯ 2 and c ¯ 1 c ¯ 2 are both even, and

· b ¯ 1 b ¯ 2 0 ( mod n )

· c ¯ 1 c ¯ 2 0 ( mod n )

· a ¯ 1 a ¯ 2 0 ( mod n ) .

Since b ¯ 1 b ¯ 2 c ¯ 1 c ¯ 2 a ¯ 1 a ¯ 2 2 ( mod n ) , and n is odd, this implies

· b ¯ 1 b ¯ 2 0 ( mod 2 n )

· c ¯ 1 c ¯ 2 0 ( mod 2 n )

· a ¯ 1 a ¯ 2 0 ( mod 2 n ) ,

which implies b ¯ 1 = b ¯ 2 , c ¯ 1 = c ¯ 2 , a ¯ 1 = a ¯ 2 because of the conditions on a ¯ i , b ¯ i , c ¯ i . Therefore the representation σ b ¯ ( τ σ ) a ¯ τ c ¯ is unique, and G 4 n contains 4 n 3 elements when n is odd.

2) Now assume n even. Again, let x = σ b ( τ σ ) a τ c , with b even.

By Theorem 2.19, σ n ( τ σ ) n , ( τ σ ) n τ n , ( τ σ ) 2 n belong to R ( G 4 n ) . Using σ n = ( τ σ ) n , we can transform x so that 0 b < n and b is even. Using ( τ σ ) n = τ n , we can transform x so that 0 a < n . Finally, using ( τ σ ) 2 n = 1 , we can transform x into:

(*) x = σ b ( τ σ ) a τ c with 0 b < n , 0 a < n , 0 c < 2 n , b even.

The total number of choices for a , b , c is n ( n 2 ) ( 2 n ) = n 3 . The choices yield distinct elements of G 4 n , for if σ b ¯ 1 ( τ σ ) a ¯ 1 τ c ¯ 1 = σ b ¯ 2 ( τ σ ) a ¯ 2 τ c ¯ 2 , then ( τ σ ) a ¯ 2 σ b ¯ 1 b ¯ 2 ( τ σ ) a ¯ 1 τ c ¯ 1 c ¯ 2 = 1 , and by commuting even powers of σ with ( τ σ ) ± 1 , we obtain σ ± ( b ¯ 1 b ¯ 2 ) ( τ σ ) a ¯ 1 a ¯ 2 τ c ¯ 1 c ¯ 2 = 1 . By Condition (1) of Corollary 2.17, we obtain

· b ¯ 1 b ¯ 2 0 ( mod n )

· c ¯ 1 c ¯ 2 0 ( mod n )

· a ¯ 1 a ¯ 2 0 ( mod n ) .

Since 0 | a ¯ 1 a ¯ 2 | , | b ¯ 1 b ¯ 2 | < n , we must have b ¯ 1 = b ¯ 2 and a ¯ 1 = a ¯ 2 . However, by Condition (1) of Corollary 2.17, c ¯ 1 c ¯ 2 0 ( mod 2 n ) , so c ¯ 1 = c ¯ 2 , since 0 | c ¯ 1 c ¯ 2 | < 2 n . Therefore, all the elements x = σ b ( τ σ ) a τ c in (*) are distinct and the order of G 4 n is n 3 .

Finally, we determine isomorphic group structures for G 4 and G 8 .

Theorem 2.31

1) G 4 is isomorphic to the Klein-4 group V .

2) G 8 is isomorphic to the multiplicative quaternion group .

Figure 3. The diagram shows σ , τ on S 8 .

Proof.

1) The diagram for G 4 is:

( σ is single line, τ is double line).

[ 0 + ] [ 1 + ] [ 0 ] [ 1 ]

By Theorem 2.30, G 4 has order 4, so G 4 = { 1 , σ , τ , σ τ = τ σ } . Since σ 2 = τ 2 = ( σ τ ) 2 = 1 , G 4 is Abelian, but not cyclic, it is V .

2) Quaternions = { 1, i , j , k , 1, i , j , k } , with

· i j = k

· j i = k

· i 2 = j 2 = k 2 = 1

· j k = i

· k j = i

· k i = j

· i k = j

each has a unique representation of the form i a j b , with 0 a 3 , 0 j 1 . Also, j i = k = i 2 i j = i 3 j . The diagram for G 8 is shown in Figure 3.

Clearly, σ 2 = τ 2 , and each x G 8 has a representation x = σ a τ b , with 0 a 3 , 0 b 1 . Also, τ σ = σ 3 τ . Therefore, ϕ : G 8 is an isomorphism defined by ϕ ( i a j b ) = σ a τ b for 0 a 3 , 0 b 1 .

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.

Cite this paper: Aloff, S. , Miniere, M. and Saccoman, J. (2021) A Minimal Presentation of a Two-Generator Permutation Group on the Set of Integers. Advances in Pure Mathematics, 11, 816-834. doi: 10.4236/apm.2021.1110055.
References

[1]   Miniere, M. (1997) Stevens Institute of Technology. Ph.D. Dissertation, Hoboken, New Jersey.

[2]   Berry, K. and Tretkoff, M. (1994) The Monodromy Group of a Transcendental Function. Contemporary Mathematics, American Mathematical Society, 169, 107-122.
https://doi.org/10.1090/conm/169/01653

[3]   Katsura, T. (2008) Permutation Presentations of Modules over Finite Groups. Journal of Algebra, 319, 3653-3665.
https://doi.org/10.1016/j.jalgebra.2008.01.023

[4]   Hungerford, T.W. (1974) Algebra. Springer-Verlag, New York.

[5]   Fraleigh, J.B. (1976) A First Course in Abstract Algebra. Addison-Wesley Publishing Company, Inc., Reading Mass.

 
 
Top