Todd-Coxeter: Left Vs Right Actions Explained

by Lucas 46 views

The Todd-Coxeter algorithm is a powerful technique in group theory, particularly useful for exploring groups defined by generators and relations. It allows us to compute the action of a group on cosets, which in turn provides a homomorphism from the group into a permutation group. But, guys, have you ever wondered about the subtle yet crucial difference between using left actions versus right actions in this algorithm? Let's dive in and break it down!

Understanding Group Actions

Before we get into the nitty-gritty of the Todd-Coxeter algorithm, let's ensure we're all on the same page regarding group actions. A group action is essentially a way a group can act on a set, transforming its elements. Think of it as a dance where the group provides the steps, and the set's elements are the dancers.

Left Actions

A left action of a group G on a set X is a function G × X → X, denoted as (g, x) ↦ g ⋅ x, satisfying two key properties:

  1. Compatibility: g ⋅ (h ⋅ x) = (gh) ⋅ x for all g, h ∈ G and x ∈ X.
  2. Identity: e ⋅ x = x for all x ∈ X, where e is the identity element of G.

In simpler terms, applying two group elements one after the other is the same as applying their product, and the identity element leaves everything unchanged. Imagine rotating a square; doing a 90-degree rotation followed by another 90-degree rotation is the same as doing a single 180-degree rotation. The identity element is like doing no rotation at all.

Right Actions

Now, a right action of a group G on a set X is a function X × G → X, denoted as (x, g) ↦ x ⋅ g, satisfying these properties:

  1. Compatibility: (x ⋅ g) ⋅ h = x ⋅ (gh) for all g, h ∈ G and x ∈ X.
  2. Identity: x ⋅ e = x for all x ∈ X, where e is the identity element of G.

Notice the order in the compatibility condition! This is the crucial difference. With right actions, applying two group elements is like applying them in reverse order when considering the group product. Think of it like putting on socks and then shoes; the order matters! The identity element still leaves everything unchanged.

Why Does It Matter?

The choice between left and right actions might seem like a mere notational preference, but it significantly impacts how we set up and interpret the Todd-Coxeter algorithm. The algorithm relies on consistently applying group elements to cosets, and the order of application matters for correctness. It ensures that the relations defining the group are respected as we fill in the coset table.

The Todd-Coxeter Algorithm: A Quick Recap

Before we delve into how left and right actions affect the algorithm, let's briefly recap what the Todd-Coxeter algorithm does. In essence, it systematically enumerates the cosets of a subgroup H in a group G, where G is defined by a presentation (generators and relations). The algorithm constructs a coset table that represents how the generators of G act on these cosets.

Core Steps

  1. Define the Group Presentation: Start with a group G given by generators and relations, like <a, b | a^3 = b^2 = (ab)^2 = 1>. This is the presentation for the symmetric group S_3.
  2. Choose a Subgroup: Select a subgroup H of G. For example, H = {e} (the trivial subgroup) or a subgroup generated by one of the generators.
  3. Create the Coset Table: Set up a table with rows representing the cosets of H in G and columns representing the generators of G and their inverses. The first row typically represents the coset H itself.
  4. Deduce Coset Representatives: Systematically fill in the table using the relations of G. This involves tracing the action of generators on cosets until all entries are determined. If a relation forces two cosets to be equal, we merge them.
  5. Determine the Index: The number of rows in the completed coset table gives the index of H in G, denoted as [G:H]. This is the number of cosets of H in G.

The Todd-Coxeter algorithm is incredibly powerful for determining the order of a group, understanding its subgroup structure, and even constructing permutation representations of the group.

Left vs. Right Actions in the Todd-Coxeter Algorithm

Now, let's get to the heart of the matter: how the choice between left and right actions affects the Todd-Coxeter algorithm. Listen up, guys, this is where it gets interesting.

Left Actions in Todd-Coxeter

When using left actions, we interpret the coset table as follows: if the entry in row i and column g is j, it means g â‹… (H g_i) = H g_j, where H g_i and H g_j are coset representatives. In other words, multiplying the coset representative g_i on the left by the generator g results in the coset H g_j.

Example: Suppose we have G = <a, b | a^2 = b^2 = 1, ab = ba> and H = {e}. If our coset table, using left actions, has an entry 2 in row 1 and column a, it means a â‹… H = H g_2, where g_2 is the representative of the second coset. So, applying a on the left to the coset H gives us the coset H g_2.

Right Actions in Todd-Coxeter

When using right actions, the interpretation changes. Now, the entry j in row i and column g means (g_i H) â‹… g = g_j H. In this case, we are multiplying the coset representative g_i on the right by the generator g to get the coset g_j H.

Example: Using the same group and subgroup as above, if our coset table, using right actions, has an entry 2 in row 1 and column a, it means H â‹… a = g_2 H. Applying a on the right to the coset H gives us the coset g_2 H.

Key Differences in Implementation

The primary difference lies in how you trace the relations in the Todd-Coxeter algorithm. Let's say we have the relation aba = 1.

  • Left Actions: When using left actions, we would trace a(a(aH)) = H. We start with H, apply a on the left, then apply a on the left again to the result, and finally, apply b on the left. The product must return us to H.
  • Right Actions: With right actions, we trace (H a)b)a = H. We start with H, apply a on the right, then apply b on the right to the result, and finally, apply a on the right. The product must again return us to H.

Why This Matters in Practice

The choice between left and right actions doesn't affect the final result (the index [G:H]), but it changes the intermediate steps and the interpretation of the coset table. Consistency is key. If you start with left actions, stick with them throughout the entire algorithm. Switching mid-way will lead to incorrect results.

Practical Considerations and Examples

To solidify our understanding, let's consider a practical example. Suppose we have the group G = <a, b | a^3 = b^2 = (ab)^2 = 1>, the presentation for S_3, and we want to find the index of the subgroup H = <a> in G.

Using Left Actions

  1. Initial Setup: We start with the coset table, where row 1 represents H = <a>. We have columns for a, a^{-1}, b, and b^{-1}.
  2. Applying Relations:
    • a^3 = 1: This tells us that a(a(aH)) = H. If aH is a new coset (let's call it H_2), then a(aH_2) must be H. This helps us fill in the table.
    • b^2 = 1: This means b(bH) = H. If bH is a new coset (let's call it H_3), then bH_3 must be H.
    • (ab)^2 = 1: This means (ab)(ab)H = H, which expands to ababH = H. This is where tracing becomes crucial. We apply a to H, then b to the result, then a again, and finally b again, and we must end up back at H.
  3. Completing the Table: By carefully tracing these relations, we can fill in the entire coset table. In this case, we would find that there are two cosets, meaning [G:H] = 2.

Using Right Actions

  1. Initial Setup: The setup is the same, but the interpretation is different.
  2. Applying Relations:
    • a^3 = 1: This tells us that (H a)a)a = H.
    • b^2 = 1: This means (H b)b = H.
    • (ab)^2 = 1: This means H(ab)(ab) = H, which expands to Habab = H. Now, we trace H, apply a on the right, then b on the right, then a again, and finally b again, and we must end up back at H.
  3. Completing the Table: Again, by carefully tracing these relations with the right action interpretation, we can fill in the table and arrive at the same conclusion: [G:H] = 2.

Choosing the Right Approach

So, which approach should you choose? The answer is: it doesn't really matter! As long as you are consistent throughout the entire process, both left and right actions will lead you to the correct answer. Some people might find one approach more intuitive than the other, so it really comes down to personal preference.

Conclusion

The distinction between left and right actions in the Todd-Coxeter algorithm is subtle but important. While the final result remains the same, the interpretation of the coset table and the method of tracing relations differ significantly. Remember, guys, consistency is key! Whether you prefer left or right actions, make sure to stick with your choice throughout the entire algorithm to avoid errors. Understanding this nuance will help you wield the Todd-Coxeter algorithm with greater confidence and accuracy in your group theory adventures.