Left Cosets on Groups

I met Aryan Pahwani at the Hacktron AI x Secure Sips – Breaking & Building AI Meetup, who is really fucking chill, and yet very motivated and relentless. Check out his site by clicking on his name.

He asked me about left cosets on groups. I am terrible at explaining, and want to get better. This is a nice little self-contained blog/note. A little experience with proof-based math, sets, and functions is enough. Or, you can always raw-dog it and look up things along the way.

Note: I use the word function and map interchangeably, sometimes transform too. They all mean the same thing.

Whenever I write the product of two elements in a group $g g^{'}$ as $g \cdot_{G} g^{'}$ , it is to emphasize that the product is using the operator of the group $G$ .

$g \in G$ is to be read as: $g$ belongs to $G$ , or $g$ is in $G$ .

When I put a (why?), I implore the reader to pause and think, to justify the statement preceding it.

Let $G$ be a group. That means $G$ is a set, and there is an operator on $G$ that takes two elements and spits out a single element.

Imagine the elements of $G$ as (weird) people. They act on other people, and when they do, they both change into a new person. for this analogy to work, its best think that no person gets deleted, and no duplicates are made, just free transformation. In particular, when $g$ and $h$ transform to $g h$ , $g$ and $h$ are still there, and there still only one $g h$ . It would have probably been better if I said that there is only one person, and his traits are all elements of $G$ which are present at all times, but we can also think about two traits combining to jump to another trait in this fixed set of ever-present traits. I don't know, but I already wrote this out :).

A person $g$ can act on another person $h$ on the left: $g h$ ,
or on the right: $h g$ . And moreover, action of people on people is symmetric—
in the sense that $g$ acting on the left of $h$ is the same as $h$ acting on the right of $g$ .
Both are $g h$ .

There are some rules however:

Rule 1. Closure
Whenever one person acts on another, the result is still a person in the same society.

Left: $g h \in G$
Right: $h g \in G$

Rule 2. Identity
There is a special person $e$ in the society. He leaves any element $g \in G$ (including himself) unchanged, on left action or right action.

He is the only one who does not like changing people.
By symmetry, when other people act on him, they do not change—but he becomes them.

Left: $e g = g$
Right: $g e = g$

Rule 3. Associativity
Suppose $h$ acts on the left of $k$ , becoming $h k$ , and then $g$ acts on this resulting in the person $g (h k)$ . And now, suppose $g$ acts on the left of $h$ first, resulting in $g h$ , and then the person $g h$ acts on the left of person $k$ , resulting in the person $(g h) (k)$ .
Then $g (h k)$ and $(g h) k$ are the same person.
ie: $g (h k) = (g h) k$

Rule 4. Inverses
Every person $g$ has a unique partner $g^{- 1}$ who turns them into the special guy $e$ who does not change anyone.

Left: $g^{- 1} g = e$
Right: $g g^{- 1} = e$

Okay, now.

Left cosets

Take and fix a person $g$ . The idea of a left coset is to study what happens to each person $x \in G$ when $g$ acts on them, on the left.

Formally, the left coset map of $G$ is a function $f_{g} : G \to G$ where $f_{g} (x) = g x$ .

The first question: will the action of $g$ on two different people $x_{1}, x_{2}$ transform them into the same person?

That is, can it ever be that $g x_{1} = g x_{2}$ when $x_{1} \neq x_{2}$ ?

Well, pluck out the transformed person $g x_{1}$ , and then let the inverse partner of $g$ , $g^{- 1}$ , act on $x_{1}$ . Do the same for $x_{2}$ .

Then we have $g^{- 1} (g x_{1}) = g^{- 1} (g x_{2})$ . But the action is associative, so we might as well think about $(g^{- 1} g)$ acting on $x_{1}$ and $x_{2}$ .
That is, $(g^{- 1} g) x_{1} = (g^{- 1} g) x_{2}$ .

But when $g^{- 1}$ and $g$ act on each other, they become that guy who leaves everyone else unchanged. Hence:

$e x_{1} = e x_{2}$ , or $x_{1} = x_{2}$ !

Would you look at that. When our guy $g$ acts on two different people, he transforms them into two different people only.

Now, $g$ has a crush $x^{*}$ but he is also a creep and $x^{*}$ doesn’t like him.
So he has a devious plan (this is so fucked up lmao): he realizes that if he can find someone else $y$ and act on them on the left, he can turn them into $x^{*}$ , like the filthy creep he is.

Can he do this?

That is, does there exist $y \in G$ for which $g y = x^{*}$ ? Well of course. He just looks for his inverse partner $g^{- 1}$ , and then $g^{- 1} g y = g^{- 1} x^{*}$ .

From now on I will slowly dilute the weird people metaphor.

And by associativity and blah blah blah… (the reader is implored to solve the equation or fill the intermediate step(s)) we have $y = g^{- 1} x^{*}$ .

Now we notice that the specificity of creepy $g$ ’s crush $x^{*}$ has nothing to do with the above argument.
If $g$ crushes on a new $x^{* *}$ , with the same argument he can find a gullible $y^{'} = g^{- 1} x^{* *}$ , such that when he acts on the left of $y^{'}$ , he will turn into $x^{* *}$ .

What a terrible guy $g$ . Don’t be like him.

The above two arguments formally tell us that the left coset map of $g$ , $f_{g} : G \to G, f_{g} (x) = g x$ , is both injective and surjective. That is, $f_{g}$ is bijective.

Group homomorphisms and isomorphisms

Let $G, H$ be groups. Think of abstract algebra as a set with additional structure.

If I take an arbitrary function $ϕ : G \to H$ , can I call this $ϕ$ a "map between groups"?
If we strip away the operators on $G$ and $H$ ? Well, the function $ϕ$ still remains well-defined. Because functions simply take elements of one set to elements of another set.

So if our group is a set with added structure, our map $ϕ$ between groups needs to respect and take into account that extra structure.

Using the people metaphor again: imagine $ϕ$ turns people in $G$ into people in $H$ . If two people $g_{1}, g_{2} \in G$ act on each other to transform into $g_{1} \cdot_{G} g_{2}$ , and then we take $ϕ$ on it, we get the person $ϕ (g_{1} \cdot_{G} g_{2}) \in H$ .

To respect the action between people in $G$ , it better be that if the transformed $g_{1}$ in $H$ under $ϕ$ , i.e. $ϕ (g_{1})$ , when acted with the transformed $g_{2}$ in $H$ under $ϕ$ , i.e. $ϕ (g_{2})$ , we get:

$ϕ (g_{1}) \cdot_{H} ϕ (g_{2})$

and that this should be the same as $ϕ (g_{1} \cdot_{G} g_{2})$ .

That is: if two people in $G$ first act on each other and then transform into people in $H$ , that should be the same as first transforming themselves into people in $H$ and then acting on each other there.

Formally, $ϕ : G \to H$ is a group homomorphism (or just group morphism)
if for each $g_{1}, g_{2} \in G$ :

ϕ (g_{1} \cdot_{G} g_{2}) = ϕ (g_{1}) \cdot_{H} ϕ (g_{2}) .

You, the reader, I implore you to prove these small but powerful statements (or just sketch them in your head and move on; the proofs are very straightforward):

Prove that for any group $G$ , there is one and only one element $g^{*}$ for which $g^{*} g^{*} = g^{*}$ (which element is this?).
Prove that if $ϕ : G \to H$ is a group homomorphism, then $ϕ (e_{G}) = e_{H}$ (homomorphism takes identity to identity).
Prove that $ϕ (g^{- 1}) = (ϕ (g))^{- 1}$ . That is, inverting an element $g \in G$ and then taking $ϕ$ is the same as first taking $ϕ$ and then inverting the result in $H$ .
Prove that if $ϕ : G \to H$ and $λ : H \to L$ are both group homomorphisms, then the composed map $λ \circ ϕ : G \to L$ is also a group homomorphism.

Now, an isomorphism is just a bijective homomorphism.
It’s like each person $g$ in $G$ went to their government, all gave the same renaming rule $ϕ$ , changed their names to $ϕ (g)$ , and now they call themselves $H$ .

Back to left coset maps. We will now completely abandon the people metaphor and just do math.

As a note: the people metaphor is not meant to be patronizing, it’s just a fun way to think about it (at least I think). I have no doubt in your capacity to do abstract and formal math, and get intuition on your own, whoever you are. But a spoonful of sugar makes the medicine go down better, and math is medicine.

Denote $L (G) = {f_{g} : g \in G}$ as the collection of all left coset maps of $G$ .

We have a set now, and we are studying groups… so can we make this into a group?

What operator do we choose on $L (G)$ ?

The obvious choice is function composition.
That is, if $f_{g}, f_{h} \in L (G)$ , define their product as $f_{g} f_{h} := f_{g} \circ f_{h}$ . (:= means "defined equal to").

Okay, what does this look like? What is $f_{g} f_{h} (x)$ for any $x \in G$ ?
Well—it’s just $(g h) x$ . (we don’t even need to write brackets, because associative :))

What identity do we pick? Obviously $f_{e}$ .
In fact, $f_{e}$ is the identity function on $G$ , since $f_{e} (x) = e x = x$ for any $x \in G$ .

What is the inverse of $f_{g}$ ? As you may guess, it is just $f_{g^{- 1}}$ . (why?)

And of course, function composition is associative, so our operator here is associative too. And voila—we have a group.

Out of curiosity, let us make a map $h : G \to L (G)$ which takes each $g \in G$ to $f_{g} \in L (G)$ .
i.e. $h (g) = f_{g}$ .

First, obviously, this $h$ is bijective. (why?)

Now, what is $h (g_{1} g_{2})$ ?
Well, it’s $f_{g_{1} g_{2}}$ . Which is also just $f_{g_{1}} f_{g_{2}}$ . (why?)

Thus indeed, writing the equation with emphasis on which group’s product:

h (g_{1} \cdot_{G} g_{2}) = h (g_{1}) \cdot_{L (G)} h (g_{2}) .

Wow! So $h$ is a bijective homomorphism and hence an isomorphism!

So the set of left coset maps of $G$ , $L (G)$ , is isomorphic to $G$ itself!!

I will leave the reader with a warning and an optional exercise.

Warning!!

A left coset map is NOT a homomorphism.
Let $G$ be a group. Then for $f_{g} \in L (G)$ with $g \neq e$ , $f_{g}$ is not a homomorphism from $G$ to $G$ .
$f_{g} (x y) = g (x y)$ , while $f_{g} (x) f_{g} (y) = g x g y$ . Even if $G$ is abelian, $g x g y = g^{2} x y$ .

Optional exercise:

Let $G^{'}$ be a subgroup of $G$ . That is, $G^{'}$ is a subset of $G$ (as sets) and inherits the operator from $G$ , and is closed under it: for any $g_{1}^{'}, g_{2}^{'} \in G^{'}$ , $g_{1}^{'} \cdot_{G} g_{2}^{'} \in G^{'}$ , where $\cdot_{G} = \cdot_{G^{'}}$ .

What happens when you take an element inside $G^{'}$ , call it $g^{'}$ , and construct the set of left coset maps $f_{g^{'}} : G^{'} \to G^{'}$ ?
What if you extend the domain of $f_{g^{'}}$ , allowing inputs from all of $G$ : $f_{g^{'}} : G \to G^{'}$ ? Is this map even well defined? That is, for every $x \in G$ , does $g^{'} x$ lie in $G^{'}$ ?
What if we extend the range instead: restrict inputs to $G^{'}$ but output to all of $G$ : $f_{g^{'}} : G^{'} \to G$ ?
Finally, what if we extend both domain and target sets: $f_{g^{'}} : G \to G$ ?

For the above, the rule $f_{g^{'}} (x) = g^{'} x$ is always the same. But the domain and/or target sets may change. Think about:

when the map is well defined,
when we have homomorphisms,
when we have isomorphisms,
what happens if $G$ is special (e.g. abelian),
what if $G^{'}$ has special properties?

I really encourage the reader to explore such ideas, which is why the problems are vague. The best way to learn math is to generate it, rather than just read it. Be sound in logic, allow your mind to come up with whatever ideas it wants, and know there is a comfortable bed of sound mathematical logic to fall back into—to test ideas, build counterexamples, and so on.

Thank you for reading :)

Closing remarks

Yes, I did give chatGPT this note, but only to fix grammar, spacing and slight readability, the words ARE MINE AND WILL ALWAYS BE LIKE THAT, I ran multiple prompts with very specific instructions to not change my words. And hence a few em dashes crept in. I think they are tasteful here, so I'll leave them in. So don't be that guy who sees an em dash or two and immediately jump to the conclusion that is "AI slop". Also, the people metaphor and the creepy $g$ stuff may be offensive to some.