Timeline for Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 29, 2015 at 19:33 | vote | accept | Bryce Sandlund | ||
| May 29, 2015 at 19:18 | comment | added | Bryce Sandlund | I also did figure out an optimization that gives an alternate complexity of $O(|G : H| \log |G : H| \sqrt{|H|})$. I'm still trying to see if it can be done in something closer to just $O(|G : H| \log |G : H|)$, with maybe an extra $O(\log |H|)$ factor. I may try to consult your second algorithm, as the bottleneck is identifying what coset a particular group element represents. | |
| May 29, 2015 at 19:12 | comment | added | Bryce Sandlund | Thanks! That makes sense. I see why you may want to generate it in the ways described, though for my purposes I need to generate and store it completely and efficiently, though it can be stored in a trie as your book mentions. For the algorithm I gave, if $H$ is $O(|G|^{.5 + \epsilon})$, then the complexity is: $O\left(\left(\frac{|G|}{|G|^{.5 + \epsilon}} \right)^2 \log \frac{|G|}{|G|^{.5 + \epsilon}} + |G|^{.5 + \epsilon}\right) = O\left(|G|^{1 - 2\epsilon} \log |G| \right)$, which is asymptotically dominated by $O(|G|)$ for any $\epsilon > 0$. | |
| May 29, 2015 at 17:36 | history | edited | Derek Holt | CC BY-SA 3.0 |
added 138 characters in body
|
| May 29, 2015 at 16:39 | history | answered | Derek Holt | CC BY-SA 3.0 |