Examples of finite groups $(G,\cdot)$ where multiplication is string concatenation followed by a 'put back to standard form' algorithm.

Question

The title of the question motivates the specific mathematical question given in the next section.

---

Let $A$ be finite set.

For an integer integer $n \ge 0$, a function $s: \{k \mid k \le n \land k \gt 0\} \to A$ is said to be a word (or string) in the alphabet $A$ of length $n$. The collection of all words in $A$ is denoted by $ \mathcal W$. Note that $\emptyset \in \mathcal W$; it is called the null string and is denoted by $[\,]$.

In a natural fashion, any two strings $\mathcal W$ can be concatenated,

$\quad (s,t) \mapsto s \mid t$

so that $(\mathcal W, \; \mid \;)$ is a free monoid.

The elements in $A$ can be regarded as words of length $1$ in $\mathcal W$ and by abuse of notation we write $A \subset \mathcal W$.

Let $\mathcal R \subsetneq \mathcal W$ be a finite set with $A \subset \mathcal R$ and $[\,] \in \mathcal R$.

Let $\Gamma: \mathcal W \to \mathcal R$ be a surjective mapping satisfying

$\tag 1 \Gamma ([\,]) = [\,]$

$\tag 2 \forall a \in A, \quad\Gamma (a) = a$

$\tag 3 \forall s,t \in \mathcal W, \quad \Gamma(s \mid t) = \Gamma\bigr(\Gamma (s) \mid \Gamma (t)\bigr)$

Are there any mathematical specifications (examples) where $\text{(1)-(3)}$ holds?

My Work

I am close to working out the details to representing the symmetric groups with such a framework. I could not find any references, but if it has already been done then that would be an example; any links/comments would be appreciated.

I have a working python program using this representation theory that allowed me to supply this answer to a motivational question.

Answer 1

Here we explain the underpinnings of our main example, the symmetric group $S_n$ for $n \ge 2$.

The set $A$ of generators are the transpositions.

The standard/reduced form $\mathcal R$ is exhibited by this form

$\quad \prod\limits_{k=1}^{n}\, \big(k \; \omega(k)\big) = \big(1 \; \omega(1)\big) \circ \big(2 \; \omega(2)\big) \circ \dots \circ \big(n \; \omega(n)\big)$

where for all $k$, $\;\omega(k) \ge k$ (for more details see this).

At this point we have $\mathcal R$ and $S_n$ in bijective correspondence. The key to specifying $\Gamma$ is the following observation:

Let $s$ and $t$ be two transpositions; the following cases are mutually exclusive,

Case 1: $st = ts = [\,]$.
Case 2: $st = ts \ne [\,]$.
Case 3: $st \ne ts \text{ and } \exists \text{ transpositions } s',t' \in A \text{ such that }$
$\quad \quad \quad st = t's \land st = ts'$

Symbolic processing is used to derive both $s'$ and $t'$.

I implemented $\Gamma$ with the Python programming language but it is not efficient (or pretty). The algorithm employs a type of bubble sort (multiple times) along with the symbolic processing.

---

Example

Here we crank out the answer after taking two 'random' (but long) $\mathcal R$ words from $S_4$; the elements are

$\quad [(12)\,(23) \,(34)] \text{ and } [(14)\,(24)\,(34)]$

Anytime we have an $\mathcal R$ word of length $3$ it will have a $(34)$ on the far right. So, we begin

$\quad [(12)\,(23) \,(34)] \text{ || } [(14)\,(24)\,(34)] = (12)\,(23) \, (13) \, (34) \,(24) \,(34) =$ $\quad \quad \quad \quad \quad \quad \quad (12)\,(23) \, (13) \, (23) = [\;]$

Well that was amusing! I simply scanned my answer here looking for the first two words of length $3$ and came up with a 'cancel out story'. I encourage the interested reader to try it out on other examples.

Answer 2

After working on this answer concerning the group generated by $(13)$ and $(1234)$ in $S_4$, I was motivated to construct a non-commutative group of order $10$.

Here are the defining relations allowing us to construct $\Gamma$,

$\tag 1 TT = [\,]$ $\tag 2 CCCCC = [\,]$ $\tag 3 CT = TCCCC$

and here is the group table:

Some Comments on the Technique

It wasn't necessary to supply any logic/argument here to allow us to assert that the table satisfies the group axioms. Rather, we used a Python program to check that the operation is associative. Also, the null string is the identity and, by inspecting the table, we see that every element has an inverse.

Consider

$\quad CT = TC^k$

Setting $k = 0$ would result in $S_2$, so remove it from consideration.

Since we're not interested in the construction of an abelian group, we reject the $k = 1$ setting.

For $k \in \{2,3\}$ the constructed binary operation isn't associative if we insist there are $10$ distinct words as shown in the group table. Said another way, the relation would 'present' a smaller (collapsed) group same as when $k = 0$, but we don't really care what that group is.

So, the only way to 'seal the deal' with this idea is with $k = 4$, i.e. with $\text{(3)}$.