Questions tagged [computational-group-theory]

Filter by
Sorted by
Tagged with
0 votes
0 answers
52 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 ...
7 votes
1 answer
454 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 ...
5 votes
1 answer
271 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 ...
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 ...
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 $\...
8 votes
1 answer
407 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? (...
4 votes
0 answers
154 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 ...
3 votes
1 answer
117 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 \...
1 vote
0 answers
59 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 ...
4 votes
4 answers
471 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 $...
16 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$, ...
7 votes
1 answer
269 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 ...
0 votes
0 answers
96 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
6k 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 ...
12 votes
0 answers
534 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 ...
15 votes
1 answer
817 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&...
8 votes
1 answer
393 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 ...
0 votes
0 answers
222 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 ...
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. ...
5 votes
0 answers
192 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 ...
4 votes
2 answers
206 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 ...
3 votes
1 answer
334 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
255 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.$$ ...
1 vote
2 answers
383 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)...
21 votes
4 answers
983 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 votes
1 answer
224 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....
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.
9 votes
1 answer
648 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 $\{ ...
4 votes
1 answer
319 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. ...
9 votes
2 answers
793 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 (...
1 vote
1 answer
416 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 ...
3 votes
1 answer
181 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,...
8 votes
0 answers
434 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
205 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 ...
26 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
312 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
87 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 ...
8 votes
2 answers
535 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 ...
9 votes
0 answers
186 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 votes
2 answers
830 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 ...
7 votes
0 answers
300 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 ...
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 ...
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{...
17 votes
0 answers
955 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 ...
8 votes
3 answers
497 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 ...
3 votes
0 answers
158 views

Generating sets of the symmetric group that yield isomorphic Cayley graphs

Let $S$ and $S'$ be subsets of size $k$ of $\mathfrak{S}_n$. Are there any necessary or sufficient conditions to determine whether or not $S$ and $S'$ yield isomorphic Cayley graphs? Assuming we ...
6 votes
1 answer
548 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-...
9 votes
1 answer
231 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 \...
1 vote
0 answers
95 views

Factoring in discrete Heisenberg group $H_3(\mathbb{Z})$

Let $H_3(\mathbb{Z})$ be the discrete Heisenberg group generated by $x=\begin{pmatrix} 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix},\ \ y=\begin{pmatrix} 1 & 0 &...
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 ...