Problem 11 - An Introduction to Mathematical Cryptography

Question

The group \(\mathcal{S}_{3}\) consists of the following six distinct elements $$ e, \sigma, \sigma^{2}, \tau, \sigma \tau, \sigma^{2} \tau, $$ where \(e\) is the identity element and multiplication is performed using the rules $$ \sigma^{3}=e, \quad \tau^{2}=1, \quad \tau \sigma=\sigma^{2} \tau . $$ Compute the following values in the group \(\mathcal{S}_{3}\) : (a) \(\tau \sigma^{2}\) (b) \(\tau(\sigma \tau)\) (c) \((\sigma \tau)(\sigma \tau)\) (d) \((\sigma \tau)\left(\sigma^{2} \tau\right)\). Is \(\mathcal{S}_{3}\) a commutative group?

Step-by-Step Solution

Answer

(a) \(\sigma\); (b) \(\sigma^2\); (c) \(e\); (d) \(\sigma^2\). \(\mathcal{S}_{3}\) is not commutative.

Step 1: Compute τσ²

To compute \( \tau \sigma^{2} \), we use the given relation \( \tau \sigma = \sigma^{2} \tau \). First, apply \( \tau \) to \( \sigma^{2} \) as \( \tau (\sigma \sigma) \). Use the associativity to rearrange as \( (\tau \sigma) \sigma \) and apply the relation to get \( \sigma^{2} \tau \sigma \). Since \( \tau \sigma = \sigma^{2} \tau \), substitute to get \( \sigma^{2} (\sigma^{2} \tau) \). Apply associativity again:\[\sigma^{2} \sigma^{2} \tau = e \tau = \tau \]. So, \( \tau \sigma^{2} = \sigma \).

Step 2: Compute τ(σ τ)

Given \( \tau (\sigma \tau) \), apply in order. First, consider \( \tau \sigma \tau = (\tau \sigma) \tau \). Use the relation \( \tau \sigma = \sigma^{2} \tau \), leading to \( \sigma^{2} \tau \tau \). Simplify using \( \tau^{2} = e \) which further simplifies the expression to \( \sigma^{2} e = \sigma^{2} \). So \( \tau (\sigma \tau) = \sigma^{2} \).

Step 3: Compute (σ τ)(σ τ)

To find \( (\sigma \tau)(\sigma \tau) \), rewrite as \( \sigma \tau \sigma \tau \). Apply \( \tau \sigma = \sigma^{2} \tau \), thus \( \sigma (\sigma^{2} \tau) \tau \) can be rearranged into \( (\sigma \sigma^{2}) (\tau \tau) \). This simplifies using \( \sigma^{3} = e \) and \( \tau^{2} = e \), resulting in \( e \cdot e = e \). So, \( (\sigma \tau)(\sigma \tau) = e \).

Step 4: Compute (σ τ)(σ² τ)

Compute \( (\sigma \tau)(\sigma^{2} \tau) \) by processing \( \sigma \tau \sigma^{2} \tau \). Replace \( \tau \sigma^{2} \) with \( \sigma \) from Step 1 into \( \sigma (\sigma) (\tau \tau) \). Simplify using \( \tau^{2} = e \), obtaining \( \sigma \sigma e \), which simplifies further to \( \sigma^{2} \). Thus, \( (\sigma \tau)(\sigma^{2} \tau) = \sigma^{2} \).

Step 5: Check Commutativity

A group \( \mathcal{S}_{3} \) is commutative if, for any elements \( a, b \in \mathcal{S}_{3} \), \( ab = ba \). Test with \( \sigma, \tau \): using given relations, \( \sigma \tau eq \tau \sigma \). Therefore, \( \mathcal{S}_{3} \) is not commutative.

Key Concepts

S3 Group

The \(\mathcal{S}_{3}\) group is a fundamental concept in group theory. It represents the symmetric group of all permutations of three objects. With six distinct elements denoted by \(e, \sigma, \sigma^{2}, \tau, \sigma \tau, \) and \(\sigma^{2} \tau\), \(\mathcal{S}_{3}\) is the smallest non-abelian group, meaning it is the simplest example of a group where the order of multiplications affects the result.
These elements are structured by their properties and operations, such as:

• \(\sigma^{3} = e\) indicates that three applications of \(\sigma\) bring you back to the identity.
• \(\tau^{2} = e\) means \(\tau\) is its own inverse, returning to the identity after two applications.
• \(\tau \sigma = \sigma^{2} \tau\) shows how multiplication order alters the product.

The identity element \(e\) plays a crucial role by leaving any element it multiplies unchanged.
This group is widely used in various fields such as chemistry for molecular symmetry and in mathematics for testing algebraic properties.

Non-commutative Groups

A non-commutative group is one where the order of multiplying two elements affects the outcome, meaning \( ab eq ba \) for some elements \(a\) and \(b\).
This is the case with the \(\mathcal{S}_{3}\) group. Non-commutative nature is notably displayed when swapping the elements \(\sigma\) and \(\tau\), where their product isn't symmetrical:

• Using the relation \(\tau \sigma = \sigma^{2} \tau\), it is clear that changing the order results in a different configuration.
• This demonstrates why when calculating new combinations in \(\mathcal{S}_{3}\), it's crucial to follow specific operational rules.

Non-commutative groups such as \(\mathcal{S}_{3}\) provide a framework for understanding operations that do not have symmetrical properties, and this framework is pivotal in topology and quantum mechanics applications.

Group Element Multiplication

In the context of group theory, multiplication refers to the composition of group elements, an operation defined within the group.
In \(\mathcal{S}_{3}\), multiplication follows specific rules that govern interactions between elements:

• When multiplying \(\sigma^{2}\) by \(\tau\), use the relation \(\tau \sigma = \sigma^{2} \tau\) to evaluate and adjust expressions accordingly.
• The order of operations is crucial for reaching correct results, i.e., following prescribed rules such as associativity and using given relations appropriately.
• Outputs like \(\tau(\sigma \tau) = \sigma^{2}\) result from understanding and applying proper sequences of multiplication.

Employing these principles ensures the computations within groups are consistent, showcasing the utility of structured rules in assessing mathematical properties.

Group Identity Element

The identity element is a fundamental component of any group. It is symbolized by \(e\) in \(\mathcal{S}_{3}\) and has a pivotal role in maintaining the group's structure.
The identity element has characteristics that define its interactions with other elements:

• When any element \(a\) is multiplied by the identity, \(a \, e = e \, a = a\), it will remain unchanged.
• The presence of \(e\) enables the group to fulfill the axioms of the group structure, particularly identity and inverse properties.
• It provides a base point, a kind of "reset" within group operations that are crucial for solving equations where closure and order are essential.

Overall, understanding the role of the identity element \(e\) offers deep insights into how groups operate, facilitating clearer analysis in both basic and complex algebraic systems.