All Questions
Tagged with algorithms computational-group-theory
8 questions
5
votes
1
answer
282
views
Questions about algorithms for permutation groups
Let $G < S_n$ be a permutation group of degree $n$, $\mathcal{P(n)}$
denote the set of all partitions of $n$, and $c: G \rightarrow
\mathcal{P}(n)$, where $c(g)$ is the partition given by the ...
- 4,646
1
vote
0
answers
61
views
Is there any lower bound for basis computation in finite Abelian groups?
Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite ...
- 11
4
votes
2
answers
221
views
Algorithm for root system of Coxeter group generated by permutations
Suppose we are given a group $G$ in terms of generators $t_1, ..., t_n$ which are order 2 in $S_m$ (however we don't assume anything other than that these elements generate $G$ and have order 2). What ...
- 345
22
votes
4
answers
1k
views
Is there a way of canonically labelling permutation groups?
When working with large numbers of graphs, a canonical labelling routine is essential as, after the initial cost of canonically labelling each graph, it permits isomorphism checks to be replaced with ...
- 12.7k
0
votes
0
answers
274
views
Algorithm to compute automorphism group of a finite group
Is there an algorithm to compute automorphism group of a finite group?
GAP has a function to do this, but while perusing their GitHub repo, I could not find an implementation. I'm struggling to find ...
10
votes
2
answers
696
views
Computing a transversal of a subgroup $H$ of $G$ in expected $O(|G : H|^2 \log |G : H| + |H|)$ time
I have the book "Handbook of Computational Group Theory", by Derek Holt, and in it is a section on finding the transversal of a subgroup. Recall a transversal of a subgroup $H$ of $G$ is a single ...
- 333
1
vote
1
answer
318
views
How quickly can one compute the Hurwitz action of braid groups on finite groups?
Let $G$ be a finite group. Define the Hurwitz action of $B_{n}$ on $G^{n}$ by letting
$(x_{1},...,x_{n})\sigma_{i}=(x_{1},...,x_{i}x_{i+1}x_{i}^{-1},x_{i},x_{i+2},...,x_{n})$. I wonder what algorithms ...
6
votes
1
answer
837
views
Testing permutations to see if they generate $S_n$
Alright, so a similar question was recently asked about the theoretical bound for generating certain permutations in polynomial time. I had been thinking about a related problem in algorithms (with ...
- 1,723