Questions tagged [computational-group-theory]
The computational-group-theory tag has no usage guidance.
93 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
26
votes
2
answers
1k
views
Is the cohomology ring of a finite group computable?
Is there an algorithm which halts on all inputs that takes as input a finite group ($p$-group if you like) and outputs a finite presentation of the cohomology ring (with trivial coefficients $\mathbb{...
- 3,230
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&...
14
votes
2
answers
1k
views
The Simultaneous Conjugacy Problem in the symmetric group $S_N$
We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
$$(g_1,\...
- 3,104
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
639
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
650
views
A stronger version of a problem of Kenneth Brown using representations
Let $G$ be a finite group and $\mathcal{L}(G)$ its subgroup lattice. Let $\mu$ be the Möbius function on $\mathcal{L}(G)$.
The reduced Euler characteristic of the order complex of the coset poset $\{ ...
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
4
answers
7k
views
Computational algebra: where?
I'm on my last semester of a math B.Sc. and about to start studying for a math M.Sc in the same institute.
It now seems like a good time to start thinking of a PhD.
I'm interested in both algebra and ...
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
455
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
471
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
588
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
418
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
562
views
Relations in a particular subgroup of the braid group.
I think this should be a 10 minute exercise in a decent computer algebra package - unfortunately I'm hopelessly ignorant of such things, so I'm putting it up here in the hope that someone will be kind ...
- 460
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,646
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
327
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
2
answers
544
views
Membership problem in monoids
What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ ...
- 41