All Questions
Tagged with gr.group-theory computational-group-theory
79 questions
47
votes
1
answer
2k
views
Transitivity on $\mathbb{N}_0$ -- a 42 problem
Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class
transposition $\tau_{r_1(m_1),r_2(m_2)}$ be the ...
- 19.6k
28
votes
5
answers
4k
views
Are there any computational problems in groups that are harder than P?
There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).
Then there are several classes of groups like ...
- 391
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
17
votes
2
answers
3k
views
God's number for the $n \times n \times n$-cube
This is a question about Rubik's Cube and generalizations of this puzzle, such as Rubik's Revenge, Professor's cube or in general the $n \times n \times n$ cube.
Let $g(n)$ be the smallest number $m$, ...
- 63.1k
17
votes
0
answers
969
views
Groups generated by 3 involutions
Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$\tau_{r_1(m_1),r_2(m_2)}$ be the ...
- 19.6k
15
votes
4
answers
4k
views
Program for computing group cohomology
Is there any computer program with which I can compute the group cohomology H^n(G,V) for a group G acting linearly on a vector space?
I mainly care about infinite groups.
- 151
15
votes
1
answer
821
views
Conjugated subgroups in $\mathsf{GL}(m+n,\mathbb{Z})$ implies conjugated subgroups in $\mathsf{GL}(n,\mathbb{Z})$?
In my research I came up with the following question:
Question: Let $H_1$ and $H_2$ be finite abelian subgroups of $\mathsf{GL}(n,\mathbb{Z})$. Define $$ H_1'=\left\{\begin{pmatrix} I_m &0\\0&...
13
votes
2
answers
2k
views
Generalization of a theorem of Øystein Ore in group theory
Theorem (Øystein Ore, 1938): A finite group $G$ is cyclic iff its lattice of subgroups $\mathcal{L}(G)$ is distributive.
Proof: see below.
Let $(H \subset G)$ be an inclusion of finite groups and $\...
12
votes
0
answers
558
views
God's number for higher dimensional Rubik's cubes
In this MO question, user Martin Brandenburg asks about God's number for $n \times n \times n$-cubes for $n>3$. Here, God's number $g(n)$ was defined as the smallest number $m$ such that every ...
- 4,829
12
votes
0
answers
699
views
Solving a set of equations in a finite symmetric group
A standard way to find solutions to a finite set of equations in a finite symmetric group
${\rm S}_n$ is to take the equations as relators of a finitely presented group, to use
the low index subgroups ...
- 19.6k
12
votes
0
answers
558
views
Possible orders of products of 2 involutions which interchange disjoint residue classes of the integers
Definition / Question
Definition: Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where
$0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$...
- 19.6k
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
10
votes
1
answer
638
views
Computing homology groups with GAP
I’m studying the homology groups of arithmetic groups such as $SL(5,\mathbb{Z})$. I saw in the answer to this post that we can use GAP to compute some of the homology groups for $SL(3,\mathbb{Z})$. Is ...
- 545
10
votes
0
answers
194
views
Permutation groups with diameter $O(n \log n)$
I suspect that many permutation puzzles can be solved in $O(n \log n)$ moves, which has led me to the following question/conjecture:
Suppose that
1. $P_i$ for $i<k=O(1)$ are permutations on an $n$ ...
- 7,545
9
votes
2
answers
811
views
Groups without factorization
A group G is said to have a factorization if there exist proper subgroups $A$ and $B$ such that $G = AB = \{ ab \ | \ a \in A, b \in B \}$.
The paper Factorisations of sporadic simple groups (...
9
votes
1
answer
3k
views
How to generate all finite groups of order n? [closed]
I know how to generate all Abelian groups of order n, but how would I generate the others? I can't seem to find anything about this.
By "generate", I mean produce the Cayley tables for all groups of ...
- 193
9
votes
1
answer
193
views
Detecting/Characterising positive elements in free groups
Let $X$ be a set, and let $F(X)$ be the free group generated by $X$.
I will say that an element of $F(X)$ is positive if it is in the monoid generated by all the conjugates in $F(X)$ of every member ...
- 2,178
9
votes
1
answer
235
views
Is a boolean interval of finite groups linearly primitive?
Let $[H,G]$ be an interval of finite groups.
Definition: Let $W$ be a representation of $G$, and $X$ a subspace of $W$.
Let the fixed-point subspace $W^{H}:=\{w \in W \ \vert \ kw=w \ , \forall h \...
8
votes
3
answers
505
views
For which series of finite simple groups is it algorithmically decidable whether they contain a homomorphic image of a given finitely presented group?
Let $G$ be a group given by a finite presentation.
On the one hand, it is easy to determine the abelian invariants of $G$, or in other words,
it is algorithmically decidable whether $G$ surjects to a ...
- 19.6k
8
votes
1
answer
1k
views
GAP cannot solve Rubik's cube 4x4x4 and higher ? (Practical limits of Schreier–Sims algorithm)
According to our practical experiments and literature search - computer algebra system GAP cannot "solve" Rubik's cube 4x4x4 and higher. That means cannot decompose given random element of ...
- 24.9k
8
votes
1
answer
454
views
Classes of groups with polynomial time isomorphism problem
It is known that the isomorphism problem for finitely presented groups is in general undecidable. What are some classes of groups whose isomorphism problem is known to be solvable in polynomial time? (...
- 283
8
votes
1
answer
470
views
Is there a algorithm to compute the Schur multiplier of a finite group from a group presentation
Suppose we have a finite group $G$ whose presentation or Cayley table is given. Is there an algorithm (at least theoretically - without considering computational complexity) to compute the Cayley ...
- 89
8
votes
2
answers
586
views
How hard is it to compute the diameter and the growth function of a finite permutation group of small degree?
Let $G \leq {\rm S}_n$ be a finite permutation group, and let
$S = \{g_1, \dots, g_k\}$ be a generating set for $G$ which is closed
under inversion and which does not contain the identity.
The growth ...
- 19.6k
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 258
8
votes
0
answers
435
views
A relation between intersection and product on Boolean interval of finite groups
Let $[H,G]$ be a Boolean interval of finite groups (i.e. the lattice of intermediate subgroups $H \subseteq K \subseteq G$, is Boolean). For any element $K \in [H,G]$, let $K^{\complement}$ be its ...
7
votes
2
answers
867
views
Research in applied algebra
I am in my final year of my doctoral study in Mathematics, where my research topic is $p$-groups, specifically classification of $p$-groups by coclass. My work involves a great deal of computation in ...
- 243
7
votes
2
answers
417
views
Catalogue of groups with short finite presentations
For various types of groups, there exist catalogues of those groups of the
particular type which are "small" in a certain sense. — For example:
The GAP Small Groups Library catalogizes ...
- 19.6k
7
votes
1
answer
565
views
Are the distributive permutation groups linearly primitive?
An action of a group $G$ on a set $X \neq \emptyset$ is called transitive if $\forall x,y \in X$, $\exists g \in G$ such that $g.x = y$.
It is called primitive if it is transitive and preserves no non-...
7
votes
0
answers
302
views
Does this class of groups contain finitely generated infinite periodic groups?
Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class transposition
$\tau_{r_1(m_1),r_2(m_2)}$ be the ...
- 19.6k
7
votes
0
answers
1k
views
Example of a group with unsolvable word problem
Today I noticed that the last relator in the 27-relator presentation
of a group with unsolvable word problem given in
Donald J. Collins: A simple presentation of a group with unsolvable word problem.
...
- 19.6k
6
votes
3
answers
872
views
An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.
Edited (this question contains two versions of a similar question)
Is there some finitely presented group $G$ generated by $g_1,...,g_n$ such that
there is an element $g\in G$ expressed as a finite ...
- 14.3k
6
votes
1
answer
517
views
Using math software to show that the following groups are infinite?
I would like to show that the following finitely presented group in 3 generators $P, Q, R$ is infinite in certain cases:
$$P^p, Q^q, R^r, (PQ)^2, (QR)^2, (PQR)^2, (QR^{r/2+1})^a (RQR^{r/2})^b$$
For ...
- 656
6
votes
1
answer
2k
views
Generalization of the fundamental theorem of cyclic groups
Let $G$ be a finite group then the fundamental theorem of cyclic groups can be formulated as follows:
Theorem: $G$ is cyclic iff it admits no two different subgroups with the same order.
proof: see ...
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
6
votes
1
answer
629
views
Positivity of the alternating sum of indices for boolean interval of finite groups
Let $G$ be a finite group and $H$ a subgroup such that the interval $[H,G]$ is a boolean lattice.
Let $L_1, \dots , L_n$ be the maximal subgroups of $G$ containing $H$.
Let the alternative sum ...
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,636
5
votes
3
answers
411
views
Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.
In the general case, I want to say that determining $|Hom(G,H)|$ is incomputable, arguing that you could use the number to test for simplicity of a presentation, but I am new to this area and I keep ...
5
votes
1
answer
326
views
Is there a nonabelian finite simple group with Grothendieck ring of multiplicity one?
Let $G$ be a finite group. It admits finitely many irreducible complex representations $H_1, \dots, H_r$ which generate, for $\oplus$ and $\otimes$, the Grothendieck ring $\mathcal{G}(G)$ of $G$ (also ...
5
votes
1
answer
165
views
Can any finite distributive weighted lattice be realized by inclusion of groups?
By theorem 2.1 here, any finite distributive lattice $\mathcal{L}$ can be realized as an intermediate subgroups lattice.
A weighted lattice $(\mathcal{L},\tau)$ is a lattice $\mathcal{L}$ with a ...
5
votes
0
answers
216
views
Tools for computing from group presentations
What are some tools -- either theoretical/by hand or algorithmic/by computer -- that are useful for doing computations in finitely presented groups?
In my particular case, I'm working with a finitely ...
- 1,277
5
votes
0
answers
95
views
Is there an interval of finite groups, at index n, with strictly more elements than the subgroup lattice of any group, of order n?
Let $G$ be a finite group and $\mathcal{L}(G)$ its subgroup lattice.
Let $s(n):= max\{|\mathcal{L}(G)| \text{ for } |G|=n \}$.
There is an OEIS page for the sequence $s(n)$: A018216
1, 2, 2, 5, 2, ...
5
votes
0
answers
300
views
Uniqueness of the direct product decomposition of inclusions of finite groups
This post is a generalization of Uniqueness of the direct product decomposition of finite groups.
Here we look inclusions of finite groups $(H \subset G)$ instead of just finite groups.
Definition: ...
5
votes
0
answers
244
views
Finite groups generated by 3 involutions interchanging disjoint residue classes of the integers
Let $r(m)$ denote the residue class $r+m\mathbb{Z}$, where $0 \leq r < m$.
Given disjoint residue classes $r_1(m_1)$ and $r_2(m_2)$, let the class
transposition $\tau_{r_1(m_1),r_2(m_2)}$ be the ...
- 19.6k
4
votes
2
answers
308
views
Another quotient of Hurwitz group
The paper An update on Hurwitz groups by Marston Conder seems to suggest
that the Chevalley group $G(2,5)$ of order $5859000000$ is a quotient of
$G := \langle a, b \ | \ a^2, b^3, (ab)^7, [a,b]^{10} \...
- 2,811
4
votes
1
answer
266
views
Are (group theoretic) Markov properties on groups with decidable word problems, decidable?
(Link to SE duplicate: https://math.stackexchange.com/questions/4959071/are-group-theoretic-markov-properties-on-groups-with-decidable-word-problems)
The Adian-Rabin theorem says that if a property of ...
- 191
4
votes
1
answer
378
views
Where to begin in Computational Group Theory?
I'm coding a small application that looks for periodic solutions to the gravitational n-body problem. I'm trying to better understanding the symmetries of solutions, which is made up of the product of ...
- 297
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
4
votes
4
answers
485
views
What are the rank 3 boolean intervals [H,G], with G simple group?
The rank $n$ boolean lattice $B_{n}$ is the subset lattice of $\{1,2, \dots , n\}$.
The lattice $B_{3}$ is the following:
Question: What are the rank $3$ boolean intervals of the form $[H,G]$, with $...
4
votes
1
answer
446
views
Finding groups of odd order without non-cyclic nilpotent quotients
I hope that my question is appropriate for MO, since it might turn out te be mainly a question about GAP or other group theory software.
Is there an algorithm to produce all non-nilpotent groups of ...
- 6,614
4
votes
1
answer
398
views
Torsion-free, normal subgroups of certain Coxeter groups
Let $G$ be the reflection group of a regular, 4-dimensional, hyperbolic honeycomb. I would like to find a family $H_i < G$ of finite-index, torsion-free subgroups of $G$, so that I can represent ...
