26
votes
Accepted
Are there any computational problems in groups that are harder than P?
An earlier reference for groups with this property is
J. Avenhaus and K. Madlener. Subrekursive Komplexität der Gruppen. I. Gruppen mit vorgeschriebenen Komplexität. Acta Infomat., 9 (1): 87-104, ...
20
votes
Are there any computational problems in groups that are harder than P?
As Andreas says (in his answer and his comment to it), there are groups whose word problem is undecidable and one could similarly set up a group that encodes the halting problem of a class of Turing ...
19
votes
Accepted
Is the cohomology ring of a finite group computable?
As I understand it this follows from Benson's Regularity Conjecture, proved by Symonds fairly recently. It says that $b_p = 2(|G|-1)$ will do.
17
votes
Accepted
Groups without factorization
This must be "well-known": If we have $G = AB$ when $G$ is a finite group, and $A,B$ are proper subgroups of $G$, then we may suppose that $A$ and $B$ are both maximal.
For if $A$ is not maximal, and ...
15
votes
Classes of groups with polynomial time isomorphism problem
A two-generator, one-relator group with torsion is a group with presentation of the form $\langle a, b\mid R^n\rangle$, $R\in F(a, b)$ and $n>1$. Their isomorphism problem is decidable in quadratic ...
11
votes
Are there any computational problems in groups that are harder than P?
There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .
11
votes
Conjugated subgroups in $\mathsf{GL}(m+n,\mathbb{Z})$ implies conjugated subgroups in $\mathsf{GL}(n,\mathbb{Z})$?
$\def\ZZ{\mathbb{Z}}\def\GL{\text{GL}}$We can make partial progress using:
Warfield, R. B. jun., Cancellation of modules and groups and stable range of endomorphism rings, Pac. J. Math. 91, 457-485 (...
10
votes
Accepted
Are the character degrees determined by the conjugacy class sizes?
SmallGroup(128,227) and SmallGroup(128,731)) are counterexamples.
...
10
votes
Is there a algorithm to compute the Schur multiplier of a finite group from a group presentation
A reference is:
D.F. Holt, The calculation of the Schur multiplier of a permutation group. In: Michael D. Atkinson, Edotor, Computational Group Theory (Conference proceedings, Durham, 1982), Academic ...
10
votes
Questions about algorithms for permutation groups
The following is only an answer to the first question: Consider the subgroups $G_1=\langle (12)(34),(13)(24)\rangle$ and $G_2=\langle (12)(34),(34)(56)\rangle$ of $\Sigma_6$ which are both isomorphic ...
9
votes
Accepted
Research in applied algebra
In the UK, there is the Applied Algebra and Geometry Research Network. You could browse the list of former speakers and abstracts for ideas.
The University of St Andrews has a strong group in ...
7
votes
God's number for the $n \times n \times n$-cube
Based on this discussion from 2015, God's number for the 4x4x4 cube lies beween 35 and 55 (inclusive) for the outer block turn metric, with the corresponding bounds being 32 and 53 for the single ...
6
votes
Accepted
How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?
I just came across this question and, even though I'm a bit late, I thought you might be interested in this reference:
Even, S.; Goldreich, O., The minimum-length generator sequence problem is NP-...
6
votes
Detecting/Characterising positive elements in free groups
Yes, there is an algorithm. This is based on the following simple fact: Any positive element can be reached (but in non-reduced form usually) by only applying the operations right multiplication by a ...
6
votes
Are the character degrees determined by the conjugacy class sizes?
Here is a general comment related to my answer to a previous MO question. If $\chi$ is a complex irreducible character of a finite group $G$, and $\chi$ takes a root of unity value at $x \in G$, then $...
6
votes
Are there any computational problems in groups that are harder than P?
Classical problem which is believed not to be in P is number factoring, which can be cast as computing a decomposition of a cyclic group into simple ones.
Several problems in permutation groups are ...
5
votes
The sporadic numbers
I cannot give a complete answer to this question right now, but I believe that it would be possible to answer it by writing a moderate amount of computer code that made use of existing results in the ...
5
votes
Research in applied algebra
A lot of "algebra" is happening in programming language theory and practice nowadays, with knowledge of category theory and type theory really beneficial. Practical applications involve creating ...
4
votes
Positivity of the alternating sum of indices for boolean interval of finite groups
UPDATE: The original poster of the question, together with Mamta Balodi, have shown that the labeling I suggest below is an EL-labeling if and only if group (product) complements coincide with ...
4
votes
Groups without factorization
The smallest non-abelian group without factorization is simple of order $1092$: it is $A_1(13)$.
Using the answer of Geoff and by browsing the book The maximal factorizations of the finite simple ...
4
votes
Computing homology groups with GAP
Graham Ellis would be able to better comment on the correctness of his code for $SL(5,\mathbb Z)$, as he appears to be the author of the HAP package in GAP.
But his code executes quickly and claims to ...
3
votes
Are there any computational problems in groups that are harder than P?
While most other answers have mentioned computational problems related to finitely presented (but generally infinite) groups, there are many problems in finite group theory which are either ...
3
votes
Accepted
Can MAGMA compute almost projective $kG$-homomorphisms?
I cannot answer 100%, but I can tell you what I know is there, and maybe its enough with some tweaking. AR-sequences are not something I've needed to implement in Magma yet, so I've not grappled with ...
3
votes
Accepted
Torsion-free, normal subgroups of certain Coxeter groups
There has been quite a bit of activity in "abstract regular polytopes", i.e. certain kinds of quotients of Coxeter groups with string diagram. See e.g. the book by P.McMullen and E.Schulte "Abstract ...
3
votes
Accepted
programming to compute kernel quotient image of a $\mathbb{Z}$-module endomorphism
Ok, not really beautiful, but the lines below are a simple SAGE implementation of the map $\partial$, computing both the representing matrix and the elementary divisors. In the implementation I ...
3
votes
The Simultaneous Conjugacy Problem in the symmetric group $S_N$
I used the same algorithm in several papers. I was unable to find older
references, but given how simple the algorithm is, I'm sure they must exist.
arXiv:1604.08158 (section 4.3, implementation of ...
3
votes
Accepted
Algorithm for root system of Coxeter group generated by permutations
There is a theoretical answer (as opposed to an algorithmic answer) found in Björner and Brenti's "Combinatorics of Coxeter groups", Section 1.5. (They seem to credit it to Matsumoto.) ...
3
votes
Accepted
Catalogue of groups with short finite presentations
I would very much like to have such a database and would like to contribute to its development. Prompted by this question, we talked about what such a database could look like (e.g. in terms of groups ...
2
votes
Is there a way of canonically labelling permutation groups?
In GAP, for transitive permutation groups of degree at most 30 one can use TransitiveIdentification(G) from the package TransGrp by Alexander Hulpke. This gives ...
2
votes
Accepted
What are the rank 3 boolean intervals [H,G], with G simple group?
Here is another infinite class of examples: Say $q>3$ is a prime power and $a$ is a square-free odd integer. Then $L_2(q)$ embeds in $L_2(q^a)$, and the lattice of subgroups above the image of ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
computational-group-theory × 86gr.group-theory × 73
finite-groups × 38
permutation-groups × 14
co.combinatorics × 11
algorithms × 8
lattice-theory × 8
computer-algebra × 8
rt.representation-theory × 7
nt.number-theory × 5
computational-complexity × 5
geometric-group-theory × 4
algebraic-combinatorics × 4
gap × 4
reference-request × 3
computability-theory × 3
group-cohomology × 3
lattices × 3
braid-groups × 3
graph-theory × 2
gt.geometric-topology × 2
matrices × 2
asymptotics × 2
symmetric-groups × 2
computational-number-theory × 2