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, ...
Derek Holt's user avatar
  • 36.4k
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 ...
Benjamin Steinberg's user avatar
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.
Oscar Randal-Williams's user avatar
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 ...
Geoff Robinson's user avatar
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 ...
ADL's user avatar
  • 2,752
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 .
Andreas Blass's user avatar
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 (...
David E Speyer's user avatar
10 votes
Accepted

Are the character degrees determined by the conjugacy class sizes?

SmallGroup(128,227) and SmallGroup(128,731)) are counterexamples. ...
Jeremy Rickard's user avatar
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 ...
Derek Holt's user avatar
  • 36.4k
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 ...
Kasper Andersen's user avatar
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 ...
Mark Grant's user avatar
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 ...
Peter McNamara's user avatar
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-...
Nick Gill's user avatar
  • 11.2k
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 ...
Christian Remling's user avatar
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 $...
Geoff Robinson's user avatar
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 ...
Dima Pasechnik's user avatar
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 ...
Derek Holt's user avatar
  • 36.4k
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 ...
Dima Pasechnik's user avatar
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 ...
Russ Woodroofe's user avatar
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 ...
Sebastien Palcoux's user avatar
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 ...
Ryan Budney's user avatar
  • 42.8k
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 ...
Carl-Fredrik Nyberg Brodda's user avatar
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 ...
David A. Craven's user avatar
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 ...
Dima Pasechnik's user avatar
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 ...
Matthias Wendt's user avatar
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 ...
Mark's user avatar
  • 304
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.) ...
Nathan Reading's user avatar
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 ...
Giles Gardam's user avatar
  • 2,861
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 ...
Giles Gardam's user avatar
  • 2,861
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 ...
John Shareshian's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible