# How do group actions connect to group presentation?

I am editing this question so that it is clearer for other users with a similar question, although I consider the answers I received sufficiently explanatory for my purposes.

I am an undergraduate, and I have a hard time drawing a connection between group presentations and group actions. So, is there an explicit way to take a group presentation and derive the action of the group from this presentation?

For example, let's say you were given the presentation $$\langle x,y| x^n = y^2 = e, yx=x^{-1}y\rangle$$, which is the dihedral group $$D_{2n}$$. Is there an algorithmic or heuristic way to derive the possible actions of $$D_{2n}$$, or any group $$G$$, from its presentation, such as determining a homomorphism $$G\longrightarrow S_n$$?

• In general, learning even basic properties about a group from generators and relations can be extremely hard. One could guess from an axiom like $x^n=e$ that there could be a nontrivial action on a set with $n$ elements, but this certainly isn't obvious from general principles and requires ad hoc manipulation. Personally, I would define $D_{2n}$ as a subgroup of $S_n$, and then prove it has a nice presentation, not the other way around. Commented Aug 1, 2023 at 4:17
• There is very little information we can "easily" get from a generators-and-relations description of a group at all. For instance, there is no algorithm for determining whether a finitely-presented (= finitely many generators and relations) group is finite, or even nontrivial. In particular, I don't think you should be able to quickly guess facts about homomorphisms $D_{2n}\rightarrow S_n$ just by looking at a presentation of $D_{2n}$. Commented Aug 1, 2023 at 12:57
• @NoahSchweber and (Andrew Dudzik) I am not convinced that the absence of algorithms for determining properties such as finiteness of a group defined by a finite presentation is relevant to this particular question. There certainly are algorithms for finding homomorphisms from a finitely presented group with $r$ generators to a finite group $G$. Their complexity is at least $|G|^r$, but they can be made practical for reasonably small $G$ and $r$, and they are very useful in practice for finding finite simple images of FP-groups. Commented Aug 1, 2023 at 13:27
• Thanks for your responses! This definitely clarifies my confusion. I gather that the reason I was having trouble connecting generators to a homomorphism onto $S_n$ is because it is hard to connect generators to a homomorphism onto $S_n$. It is good to know that when $G$ and $r$ are small then there are reasonable ways to derive information about the structure of $G$. I will have to look into that. Commented Aug 1, 2023 at 13:49
• I do not understand the closure about "needs more focus" here. Surely this question admits a canonical answer - "There is no way to determine the existence of a (non-trivial) homomorphism $G\to S_n$ in general, but this is possible if $n$ is specified"? Commented Aug 24, 2023 at 7:27

There are algorithms to solve the problems that you are describing which have efficient implementations in GAP and Magma. In particular, to find the transitive actions of a group defined by a finite presentation of degree up to a specified number $$n$$, you can use the $$\mathtt{LowIndexSubgroups}$$ algorithm, which finds representatives of conjugacy classes of subgroups of index up to $$n$$.
But I am guessing that this is not what you are looking for. A very naive method of finding the homomorphisms of your finitely presented group $$G$$ to $$S_n$$ is to try all elements of $$S_n$$ as the images of each generator of $$G$$. For each such assignment of images of generators, you can check whether this extends to a homomorphism of $$G$$ by checking whether the images satisfy the relations of $$G$$. But this is impractical except for very small $$n$$. To find homomorphisms of $$D_{2n}$$ to $$S_n$$ you would need to try $$(n!)^2$$ possible generator images. This can be significantly reduced by using a bit more theory - as a first improvement, for the images of the first generator you need only try representatives of conjugacy classes of $$S_n$$, and with further refinements of that type the method would become feasible for a computer but still impractical to do by hand.