# Understanding Advanced Permutation Group by Example

Trying to wrap my head around the following passage but am having difficulty. It seems there are a few advanced topics that are assumed to be understood without providing examples. I would like to understand the missing pieces described in the following passage.

### (A) Passage

...We consider permutation groups. A permutation representation $(G, A, f)$ is a group $G$ that acts on a set $A$ through a function $f \in G \to \mathcal{I}A$ (where $\mathcal{I}A$ is the set of bijections on $A$) such that $f(1)$ is the identity transformation and the function composition operation $\circ$ is compatible with the group operation,

$$\overset{G^2}{\underset{g,h}{\forall}}\ \ f(h) \circ f(g) = f(g \cdot h)$$

For a partition $\textbf{P}$ of a set $\textit{P}$, the permutation group $(G, \textbf{P}, f)$ allows to represent a set of partitions that are coarser than $\textbf{P}$ using the group structure of $G$. For any subgroup $S$ of $G$, two elements of $\textit{P}$ are contained in the same cell of the partition of $\textit{P}$ induced by S through the permutation group $(G, \textbf{P}, f)$ iff their containing cells of $\textbf{P}$ lie on the same orbit of $S$.

### (B) Question

If I could boil this down to one question, that would be:

What a complete example of the permutation group looks like based on the definitions provided in the passage.

That is, what would be what some examples of $f$ are in the passage (inputs and outputs), and some definition variations, so I can get a sense of how to apply the function. I don't understand the function inputs/outputs/structure so I can't apply it.

$$\overset{G^2}{\underset{g,h}{\forall}}\ \ f(h) \circ f(g) = f(g \cdot h)$$

That is, wondering what a complete example would be, i.e.

• An example group $G$, say the set of integers $\mathbb{Z}$ if that's helpful, but anything would be fine.
• A few example permutations $A$ or $\textbf{P}$ (not sure if they are the same).
• A few example inputs/outputs for the function $f$.
• An example orbit of the subgroup of $G$.

This would demonstrate a complete example of how to apply the permutation representation/group to a set using the function $f$.

• Wow! (1) I'd advice you to shorten a lot your exposition, and then (2) ask one specific question. It could be not many will read all the above... – DonAntonio Apr 21 '18 at 0:07
• @DonAntonio okay I added a tl;dr section at the top based on your feedback, with roughly one question (what a complete example of the permutation group would look like based on the definitions provided in the passage). I left the original block just in case that was helpful in explaining where I am misunderstanding stuff. – Lance Pollard Apr 21 '18 at 0:17
• This seems to be an odd definition of a what is called a group action on a set. I'm not quite sure what the part about the partition is saying, but it's definitely related to what are called the orbits of a group action. You can read about group actions in any introductory book on group theory, and I think the wikipedia page even has some nice examples. – Joppy Apr 21 '18 at 4:01

The following was partly taken out of the original question to pose as an answer, albeit an incomplete and incorrect one. Maybe it might be helpful for further elaboration so wanted to post it in case. It's about all I can get from the passage :(

### Elements

So from what I can gather the elements are:

1. A group $G$.
2. A set $A$.
3. A function $f \in G \to \mathcal{I}A$.
4. A permutation representation $(G, A, f)$ ($G$ acting on $A$ through $f$).
5. $\mathcal{I}A$ is the set of all bijections of $A$.
6. The function composition operation $\circ$ is compatible with the group operation $\cdot$.
7. $f(1)$ is the identity transformation.
8. $\overset{G^2}{\underset{g,h}{\forall}}\ \ f(h) \circ f(g) = f(g \cdot h)$.
9. A partition $\textbf{P}$ of a set $\textit{P}$.
10. A permutation group $(G, \textbf{P}, f)$.
11. A subgroup $S$.
12. An orbit of $S$.

### Analysis

My understanding is as follows (the numbers match the numbered list above).

1. I understand the definition of a group in group theory.
2. A set makes sense. What I'm confused about is if $A$ is an arbitrary set, or if $A$ is a subset of the group $G$.
3. This to me means two things (please correct if wrong):
1. It seems like it could also be written $f : G \to \mathcal{I}A$ instead of $f \in G \to \mathcal{I}A$ ($:$ vs. $\in$).
2. This is really saying $f : A \to \{a,b : a,b \in A \times A\}$, so $f$ maps an element of $A$ to a pair of $A \times A$.
4. A permutation representation is the result of applying $f$ to elements of $A$, using elements of $G$. I'm not sure how this works though (more on that in (8)).
5. The set of bijections of A is $A \to A$, so this makes me think it is the set $\{ x \in y \mid y : A \to A \}$.
6. By "compatible" they mean that $\circ$ is compatible with $\cdot$, but not necessarily vice versa. Not sure exactly what compatible means.
7. This is referencing the identity transformation of a group in group theory. To me it means $f(1) \cdot f(x) \to f(x)$, where $\cdot$ is the group operation not necessarily $\circ$. And $f(x)$ is an arbitrary application of an element $x \in G$, which returns a $\{x,y \mid x \in G, y \in A\}$.
8. My interpretation is:
1. For every $g,h \in G^2$ or alternatively $g,h \in G \times G$, $f(h) \circ f(g) = f(g \cdot h)$
2. Composing $f(h)$ and $f(g)$ is the same thing as applying the group operation on $g$ and $h$ then applying the function $f$.
3. I'm not sure what the "output" is of applying the function $f$. An example would be very helpful. It seems if $x \in G$ is an arbitrary element of $G$, then $f(x) \mapsto (a,b)$ where $(a,b) \in \mathcal{I}A$ is a bijection/ordered pair from $f : G \to \mathcal{I}A$.
9. These variables were introduced without previous description.
10. Wondering a few things:
1. If the permutation group $(G, \textbf{P}, f)$ is the same as the permutation representation $(G, A, f)$. That is, $A \equiv \textbf{P}$. Or maybe $\textbf{P}$ is a group/subgroup of $G$, but not sure. Doesn't seem to say that.
2. The meaning of the clause "...allows to represent a set of partitions that are coarser than $\textbf{P}$ using the group structure of $G$.". To me that means that $(G, \textbf{P}, f)$ allows you to represent partitions coarser (less detailed? not sure by what measure) than $\textbf{P}$ somehow by "using the group structure of $G$".
11. I understand the definition of a subgroup.
12. I understand the definition of an orbit relative to group theory. However, it is pretty advanced since it involves group actions which I am still working on understanding, so understanding how it applies would be helpful.

### Remaining Questions

In the bullet points above I listed where my misunderstandings occurred. Here I will list the key points where I am having difficulty:

1. Wondering if $A$ is an arbitrary set, or if $A$ is a subset of the group $G$.
2. Wondering if the definition of $f$ could be written $f : G \to \mathcal{I}A$ or even $f : A \to \{a,b : a,b \in A \times A\}$, so $f$ maps an element of $A$ to a pair of $A \times A$. Also wondering if $f$ is just a group homomorphism, since it seems similar.
3. Wondering if the set of bijections on A could be written $\{ x \in y \mid y : A \to A \}$ or even $\{ (a,b) \mid a,b \in A \times A\}$.
4. Regarding (8.3), wondering what some example outputs would be for the function $f(arbitrary_{value})$. Wondering if the output is $(a,b) \in A \times A$ or $a \in A$, or perhaps is a function $x : A \to A$, or maybe a function $x : A \to A \approx (a, b) \mid a,b \in A \times A$. A bit confused how to interpret that.
5. Wondering if the permutation group $(G, \textbf{P}, f)$ is the same as the permutation representation $(G, A, f)$.
6. Wondering the meaning (and an example of) the clause "...allows to represent a set of partitions that are coarser than $\textbf{P}$ using the group structure of $G$.". Specifically not sure how it "uses the group structure", and what an example partition would look like.
7. An example of an orbit in this context would provide a boost but isn't necessary.

### Example

It seems like a permutation representation and permutation group are the same thing, so we will just deal with $A$. And it seems that $A$ is unrelated to the group elements.

So lets say we have a group $G = (X, \cdot)$, where $X$ is a set and $\cdot$ is the group operation (in this case, function composition). Or by "compatible" perhaps it means it can do composition, but maybe it has an arbitrary other operation. So:

\begin{align*} \cdot = \left\{ \begin{array}{r@{}l} (x \in \mathbb{Z}, y \in \mathbb{Z}) &\to z \in \mathbb{Z}\\ (x \in \mathbb{X}, y \in \mathbb{X}) &\to x \circ y \end{array} \right. \end{align*}

where $\mathbb{X}$ is the set of all functions. That is essentially saying, our group operation $\cdot$ has 2 totally separate implementations, one handling the integers (just made that up), and the other handling the composition. Now that function "is compatible" with composition.

Then we have a function $f : X \to \mathcal{I}A$, where $\mathcal{I}A = \{ (a,b) \mid a,b \in A \times A\}$ So in essence, $f$ is a pair $f = ((a, b), c)$ where $(a, b) \in A \times A$ and $c \in X$. Notice that a and b are from $A$ while $c$ is from $X$ (from the group). So $c \in G$, but $a, b \notin G$.

So say our $X$ is $\{1, 2, 3, 4, 5, 6\}$. We know the identity function $f(1) \circ f(x) \mapsto f(x)$ (where $f(x)$ is an arbitrary invocation of $f$ with $x \in G$) by definition. What $f(1)$ maps to itself, I don't know, perhaps another element of $G$, not sure. Another example is trying the rest of the values in the group:

\begin{align*} f(1) &\circ f(x) \mapsto f(x)\\ f(2) &\circ f(x) \mapsto ?\\ f(3) &\circ f(x) \mapsto ?\\ f(4) &\circ f(x) \mapsto ?\\ f(5) &\circ f(x) \mapsto ?\\ f(6) &\circ f(x) \mapsto ? \end{align*}

(I am really lost by this point)

Given that we know how the functions map to each other, we can now create permutations of the set $A$:

\begin{align*} f(1) \mapsto perm_1?\\ f(2) \mapsto perm_2?\\ f(3) \mapsto perm_3?\\ f(4) \mapsto perm_4?\\ f(5) \mapsto perm_5?\\ f(6) \mapsto perm_6? \end{align*}

To summarize, we have:

\begin{align*} G &= (X, \cdot)\\ \dot{G} &= (G, A, f)\\ f &: X \to \mathcal{I}A\\ \mathcal{I}A &= \{ (a,b) \mid a,b \in A \times A\}\\ X &= \{1, 2, 3, 4, 5, 6\}\\ f(1) \circ f(x) &\mapsto f(x)\\ f(2) \circ f(x) &\mapsto ?\\ f(3) \circ f(x) &\mapsto ?\\ f(4) \circ f(x) &\mapsto ?\\ f(5) \circ f(x) &\mapsto ?\\ f(6) \circ f(x) &\mapsto ?\\ f(1) &\mapsto perm_1?\\ f(2) &\mapsto perm_2?\\ f(3) &\mapsto perm_3?\\ f(4) &\mapsto perm_4?\\ f(5) &\mapsto perm_5?\\ f(6) &\mapsto perm_6? \end{align*}