3
$\begingroup$

Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group.

Model of computation is RAM

For all pair of $a$ and $b$ in $G$ just check $a.b - b.a = 0$ , but it is going to take much time $O(n^2)$. Is there a faster algorithm to solve this problem?

$\endgroup$
  • $\begingroup$ Oops, my mistake. Sorry about that. I read too fast. $\endgroup$ – D.W. Mar 15 '18 at 16:25
1
$\begingroup$

Based on the following snippet from https://en.wikipedia.org/wiki/Quotient_group:

In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup.

It seems that you can simply set $H$ to be the identity element of $G/H$ (taking O(1) time), and then for each element $g \in G$ that has not yet been assigned to any coset, calculate the (say, left) coset of $H$ w.r.t. $g$ explicitly: $\{gh : h \in H\}$, and assign all such elements $gh$ (not just the $g$ we started with) to this coset. Calculating the coset for a particular $g$ takes $O(|H|)$ time, but the entire second phase takes only $O(n)$ time overall, since we only consider elements $g \in G$ that have not yet been assigned to a coset -- this is allowed because (according to that page) the cosets form an equivalence class, meaning no element can appear in two different cosets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.