Questions tagged [computational-group-theory]
The computational-group-theory tag has no usage guidance.
93 questions
4
votes
1
answer
379
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 ...
- 12.3k
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 ...
- 5,654
4
votes
0
answers
115
views
Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?
Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
- 24.9k
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 $\...
- 2,183
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
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 ...
10
votes
1
answer
640
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 ...
- 426
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 ...
- 236k
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$ ...
- 236k
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 ...
- 236k
1
vote
0
answers
87
views
complexity of membership problem in finite general linear group
Suppose $G$ is a subgroup of $GL(n,q)$ given by a list of generators. What is known about the complexity of the corresponding "membership problem", that is, the problem of deciding whether a ...
- 2,287
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,713
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 ...
- 2,821
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? (...
- 2,821
4
votes
0
answers
166
views
Is there any good methods for writing down basis for laws of groups?
I am wondering if there is a good method to write down a finite equational basis for a finite group.
Especially I am wondering if there is a good method in following situations:
We can write a group ...
- 93
3
votes
1
answer
133
views
Determine if a 2-cocycle is zero in $H^2(G,\mathbb C^\times)$
Let $G$ be a finite group with trivial action on $\mathbb C^\times$. And given a 2-cocycle $\alpha$ in its Schur multiplier group $H^2(G,\mathbb C^\times)$, as an explicit map from $G\times G\to \...
- 231
1
vote
0
answers
61
views
Is there any lower bound for basis computation in finite Abelian groups?
Victor Shoup in this paper has given a lower bound for discrete logarithm. The algorithms that I have come across use discrete logarithms (extended discrete logarithms) to compute a basis for a finite ...
- 11
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 $...
- 2,773
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$, ...
- 4,713
0
votes
0
answers
106
views
A decision problem of an inverse problem in finite group theory
A finite group $G$ is called integral if there is a finite group $H$ such that $G\cong H'$.
In Araujo, Cameron, Casolo, Matucci's paper, integrals of groups, they tried to solve a problem as following:...
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 ...
- 4,713
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
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&...
- 156k
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 ...
- 37.4k
0
votes
0
answers
274
views
Algorithm to compute automorphism group of a finite group
Is there an algorithm to compute automorphism group of a finite group?
GAP has a function to do this, but while perusing their GitHub repo, I could not find an implementation. I'm struggling to find ...
- 63.9k
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.
...
- 185
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
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 ...
- 1,846
4
votes
1
answer
423
views
A global code for the character table of PSL(2,q)
We can easily get the character table of $\mathrm{PSL}(2,q)$ for some fixed small prime power $q$, we can just do (for example):
...
4
votes
1
answer
274
views
Isomorphism of semidirect products of surface groups
Recall that the fundamental group of a closed Riemann surface of genus $h$ has the presentation $$\Pi_h= \langle a_1, \,b_1, \ldots, a_h,\, b_h \; | \; [a_1, \, b_1]\ldots [a_h, \, b_h]=1 \rangle.$$ ...
- 496
1
vote
2
answers
411
views
Are the character degrees determined by the conjugacy class sizes?
The computation below (part 1) shows that if two finite groups of order at most $100$ have the same (ordered) list of conjugacy class sizes, then they also have the same (ordered) list of (irreducible)...
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 ...
- 3,736
3
votes
1
answer
226
views
Can MAGMA compute almost projective $kG$-homomorphisms?
Let $G$ be a finite group and $k$ be a finite field (big enough) whith char$(k)=p$ and $p\mid |G|$.
Let $M$ be a finitely generated $kG$-module.
We denote the first syzygy of $M$ by $\Omega(M)$, i.e....
- 1,143
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.
- 44.8k
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 $\{ ...
- 1,388
4
votes
1
answer
350
views
Where or how can I find matrix representatives of the conjugacy classes of Conway's group Co₀?
I would like to find ($24\times 24$) matrices representing the various conjugacy classes of Conway's group $\mathrm{Co}_0$ acting on the Leech lattice in the usual coordinate system given by the MOG. ...
- 32.5k
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 (...
- 44.4k
1
vote
1
answer
431
views
The sporadic numbers
Let call $n$ a sporadic number if the set of groups $G \neq A_n,S_n$ having a core-free maximal subgroup of index $n$ is non-empty and contains only sporadic simple groups.
By GAP, the set of all the ...
- 37.4k
3
votes
1
answer
193
views
Maximal factorization of finite simple groups and no extra intermediate
The book The maximal factorizations of the finite simple groups and their automorphism groups (by Martin W. Liebeck, Cheryl E. Praeger and Jan Saxl) provides a classification of all the triples $(G,A,...
- 44.4k
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 ...
2
votes
0
answers
228
views
Satake correspondence for groups over finite field
I asked the same question in MSE, but I didn't get any answer. So I decided to post it here, too.
In Langlands' program, Satake correspondence gives a correspondence between unramified ...
- 2,215
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 ...
1
vote
1
answer
318
views
How quickly can one compute the Hurwitz action of braid groups on finite groups?
Let $G$ be a finite group. Define the Hurwitz action of $B_{n}$ on $G^{n}$ by letting
$(x_{1},...,x_{n})\sigma_{i}=(x_{1},...,x_{i}x_{i+1}x_{i}^{-1},x_{i},x_{i+2},...,x_{n})$. I wonder what algorithms ...
0
votes
0
answers
99
views
nauty/traces orbit sizes for colored graph?
I'm given a graph $G$ (<1000 vertices, large automorphism group), and a large number (~10^6-10^10) of different colorings of said graph. I have two tasks.
Calculate the canonical coloring. I can ...
- 91
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 ...
- 11.2k
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
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
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
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
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{...
- 18.2k