24

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, 1977/78.
There is a hierarchy of the recursive functions known as the (difficult to pronounce) Grzegorczyk Hierarchy $E_0 \subset E_1 \subset E_2 \subset \cdots$, ...

gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem

19

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.

19

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 machines where this is decidable but difficult. However, one must be careful in the encoding. In
Isoperimetric and Isodiametric Functions of Groups,
Mark V. ...

gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem

13

I'll only consider the case of $S_N$ to start with.
Given $(g_1,\ldots,g_d)\in S_N^d$, define a directed graph $G$ on vertices $\lbrace 1,\ldots,N\rbrace$ whose edges are coloured with elements of $Z_2^d$. Edge $i{\to}j$ is coloured $(\epsilon_1,\ldots,\epsilon_d)$, where $\epsilon_t=1$ iff $g_t$ maps $i$ onto $j$. You can remove loops and edges of colour ...

11

I am not an expert, but I remember seeing this press release from MIT not too long ago. The corresponding arXiv article should answer your second question.

11

There are finitely presented groups whose word problem is undecidable. See, for example, https://en.wikipedia.org/wiki/Word_problem_for_groups .

gr.group-theory computational-complexity geometric-group-theory computational-group-theory word-problem

10

Babai, Codenotti, and Qiao (ICALP 2012 from Babai's homepage, also in Codenotti's thesis) show how to test permutational isomorphism (=conjugacy - but this might be another good phrase to search with) of permutation groups in time that is polynomial in the order of the groups and simply exponential ($c^n$ for fixed $c$) in the size of the permutation domain. ...

10

A quick way to obtain canonical conjugates of permutation groups would of
course be nice, but hoping for that may be a bit too optimistic.
Rather than trying to go that route, in your situation I would try to reduce
the number of pairs of groups to be tested for conjugacy -- and my guess is
in practice you can usually obtain quite a big reduction. Concretely,...

10

I guess I should try and answer that!
I don't really have a good answer to the question of why the random method is not mentioned in the book, and I would agree that it might to be the fastest method if you simply want to compute and store a complete transversal.
I guess the point is that in many applications you want to do something a little different ...

10

There are algorithms that can find all quotients of a finitely presented group isomorphic to ${\rm PSL}(2,q)$ for some $q$: see W. Plesken and A. Fabianska.
An L2-quotient algorithm for finitely presented groups.
J. Algebra, 322(3):914--935, 2009, and arXiv:1402.6788.
I believe that some progress has been made also with general $L_3(q)$ and $U_3(q)$ ...

9

UPDATE 22/10/17: The question is answered for many classes of simple quotients in this preprint of Bridson--Evans--Liebeck--Segal.
Here's what I know.
Martin Bridson and I proved the theorem mentioned in the question, namely that it is undecidable whether or not a fp group has a non-trivial finite quotient. As you say, it follow trivially that, for at ...

9

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 Combinatorics and Algebra, with some members (such as Rosemary Bailey) working on computations and applications.
In Ireland, Graham Ellis's group at NUI Galway is ...

7

You probably already noticed that, but $B_{p,q}$ is the fundamental group of
$$
X_n/(S_p \times S_q)
$$
where $X_n$ is the configuration space of $n$ points in the complex plane. Ths may help to guess some facts about these groups.
So far I know these group are usually called "mixed braid groups" in the litterature, though this name is sometimes used for ...

7

I think it might be more sensible to ask questions like this on the GAP forum, but I can help you with the first of your examples. I haven't tried the second. A standard method of trying to prove finitely presented groups infinite is to look for subgroups of low index and compute their abelian invariants, hoping that you will find a subgroup with an infinite ...

6

This seems to be one of the biggest holes in the practical isomorphism arsenal. Various non-trivial possibilities come to mind, but their efficiency relies a lot on a more basic question. Define (and efficiently compute) a total order on labelled finite permutation groups. Thus, for any two permutation groups $G_1,G_2$ given by permutation generators, ...

6

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 generator $R_g(x)=xg$ and conjugation by a generator $C_g^{\pm}(x)=g^{\pm 1}xg^{\mp 1}$.
To see this, just rewrite
$$
xax^{-1}yby^{-1} \ldots wpw^{-1}zqz^{-1} =...

6

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 known to be as hard as graph isomorphism, thus not believed to be in P, too.
There are also NP-hard problems known for permutation groups, see e.g. https://www....

5

There may be some clever trick to do this by elementary arguments, but I don't see it at the moment. With CFSG, the following argument shows that it is likely to be rare to have a Grothendieck ring with multiplicity $1$, if it happens at all. Let $b$ the the largest character degree of the non-Abelian finite simple group $G$, and suppose that $G$ has $k$ ...

5

The answer of the main question is yes. Let $G$ be a finite group and $H$ a subgroup.
Definition: The group $G$ is called $H$-cyclic if $\exists g \in G$ such that $\langle H,g \rangle = G$.
Note that: $\langle H,g \rangle = G \Leftrightarrow \langle Hg \rangle = G$.
Ore's theorem for intervals (1938): If the interval $[H,G]$ is distributive, then $G$ is $...

5

Yes, $G(2,5)$ is a quotient of your group $G$.
-- We can find generators $a$ and $b$ of $G(2,5)$ satisfying
the relations in a few seconds with GAP (so in particular
there is no need to buy Magma for this!):
gap> G25 := SimpleGroup("G2(5)");
G2(5)
gap> cl2 := G25.1^G25;; # conjugacy class of involutions
gap> cl3 := G25.2^G25;; # one of the 2 ...

5

Yes there is algorithm for this due to John Cannon. The original reference is
CANNON, J.J. (1973): Construction of defining relators for finite groups, Discrete Math. 5, pp. 105–129.
You can also read about this and related algorithms in Chapter 6 of "Handbook of Computational Group Theory" by Holt, Eick, and O'Brien.
If you want an presentation on your ...

5

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 certified for correctness programs, and certifying existing programs for correctness.
You might have heard about computer-certified proofs of theorems, such as Odd ...

4

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-hard, J. Algorithms 2, 311-313 (1981). ZBL0467.68046.
This asserts that the calculation of the diameter of a Cayley graph of a permutation group is NP-Hard. I ...

4

This answer is really just intended to add some keywords to the discussion.
If $G=\langle x_1,\ldots,x_m\mid r_1,\ldots,r_n\rangle$ then the set $\mathrm{Hom}(G,H)$ is naturally in bijection with the set of solutions to the system of equations
$r_1(x_1,\ldots,x_m)=1$
$\ldots$
$r_n(x_1,\ldots,x_m)=1$
in $H$.
For this reason, the study of $\mathrm{Hom}(G,...

4

If you have the automorphism group of $F/K$, it should be easy. As you already know, this automorphism group needs to have a cyclic subgroup of order $n$, say $G$. If the fixed field $F^G$ (which is computable) has genus zero and a place of degree $1$, then it is rational. Finally, $F/F^G$ is Kummer if $K$ contains an $n$-root of unity. These are your ...

4

Hi Tom,
the answer (at least to your second, refined question) is "Yes! or at least "Yes, soon!" :). I first wanted to post this as a comment, but since it is rather lengthy, I figured it made more sense to give this as an answer, even though it might not be completely satisfying.
There are algorithms that can generate all groups up to a given order; ...

4

This is not a proper answer, but is a bit too long for a comment. You should look at the following paper:
Groups and Lattices by P.P. Palfy
First, he states a stronger version of Ore's result:
Theorem: Let $G$ be any group. The subgroup lattice $\mathcal{L}(G)$
is distributive if
and only if the group
$G$
is locally cyclic. (i.e. every ...

4

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 lattice complements on the given Boolean interval in the subgroup lattice. The latter condition does not always hold; in the same paper they present examples where ...

3

Say $G=S_n$ and $H$ is a Young subgroup with three orbits, no two of which have the same size and no two of which have sizes summing to $n/2$. Then the only subgroups between $H$ and $G$ should be three Young subgroups with two orbits, no one of which contains any other and no two of which have the same order.

3

Here's the proof for the decidability when the family $\mathcal{F}$ consists of all abelian simple groups $C_p$ along with all $PSL(2,q)$ for $q$ prime power.
The first remark is that a group has a quotient in $\mathcal{F}$ iff it has a nontrivial representation in $SL(2,q)$ for some $q$. (Including abelian simple groups in $\mathcal{F}$ allows me not to ...

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

#### Related Tags

computational-group-theory × 61gr.group-theory × 52

finite-groups × 30

permutation-groups × 13

co.combinatorics × 10

lattice-theory × 8

computer-algebra × 5

nt.number-theory × 4

rt.representation-theory × 4

algorithms × 4

lattices × 3

braid-groups × 3

graph-theory × 2

computational-complexity × 2

computability-theory × 2

geometric-group-theory × 2

computational-number-theory × 2

symmetric-groups × 2

algebraic-combinatorics × 2

career × 2

ag.algebraic-geometry

at.algebraic-topology

linear-algebra

ac.commutative-algebra

matrices