Skip to main content

Questions tagged [computational-group-theory]

Filter by
Sorted by
Tagged with
0 votes
0 answers
55 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 ...
Pierre's user avatar
  • 2,195
7 votes
1 answer
464 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 ...
Noah B's user avatar
  • 403
5 votes
1 answer
274 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 ...
Victor Miller's user avatar
8 votes
1 answer
415 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? (...
Mithrandir's user avatar
4 votes
0 answers
158 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 ...
Todor Antic's user avatar
3 votes
1 answer
120 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 \...
JKDASF's user avatar
  • 231
1 vote
0 answers
60 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 ...
Vasac's user avatar
  • 11
0 votes
0 answers
98 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:...
Zhaochen Ding's user avatar
7 votes
1 answer
271 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 ...
Stefan Kohl's user avatar
  • 19.5k
12 votes
0 answers
537 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 ...
Max Muller's user avatar
  • 4,595
15 votes
1 answer
819 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&...
Alejandro Tolcachier's user avatar
8 votes
1 answer
404 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 ...
Cloud jr's user avatar
0 votes
0 answers
233 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 ...
Jerry Halisberry's user avatar
5 votes
0 answers
195 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 ...
Ethan Dlugie's user avatar
  • 1,267
4 votes
2 answers
210 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 ...
manzana's user avatar
  • 335
3 votes
1 answer
351 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): ...
Sebastien Palcoux's user avatar
4 votes
1 answer
260 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.$$ ...
Francesco Polizzi's user avatar
1 vote
2 answers
394 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)...
Sebastien Palcoux's user avatar
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....
Bernhard Boehmler's user avatar
4 votes
1 answer
330 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. ...
Gro-Tsen's user avatar
  • 30.3k
9 votes
2 answers
796 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 (...
Sebastien Palcoux's user avatar
1 vote
1 answer
421 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 ...
Sebastien Palcoux's user avatar
3 votes
1 answer
184 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,...
Sebastien Palcoux's user avatar
2 votes
0 answers
207 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 ...
Seewoo Lee's user avatar
  • 1,911
0 votes
0 answers
91 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 ...
J Bausch's user avatar
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 ...
MSL's user avatar
  • 371
9 votes
0 answers
187 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$ ...
Dmytro Taranovsky's user avatar
7 votes
2 answers
838 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 ...
usermath's user avatar
  • 243
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{...
Joshua Grochow's user avatar
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 ...
Anthony Labarre's user avatar
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 $\{ ...
Sebastien Palcoux's user avatar
1 vote
0 answers
99 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 &...
user avatar
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 ...
user49822's user avatar
  • 2,138
2 votes
0 answers
74 views

Is the word problem in the braid group quotient $B_{n}/N$ solvable where $N$ is the normal subgroup generated by conjugates of $\sigma_{i}^{2r}$?

Let $r\geq 2$. Let $N$ be the normal subgroup of $B_{n}$ generated by conjugates of $\sigma_{i}^{2r}$. Then is the word problem in the quotient group $B_{n}/N$ solvable (in polynomial time)? ...
Joseph Van Name's user avatar
3 votes
0 answers
128 views

Extension of Tits' theorem on groups with a BN-pair of rank ≥ 3

Tits has proved that a finite simple group $G$ with a BN-pair of rank $n \ge 3$, is of Lie type. Let $B$ be the Borel subgroup and $(W,S)$ the Coxeter system. The subset lattice of the set $S$ is ...
Sebastien Palcoux's user avatar
1 vote
1 answer
314 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 ...
Joseph Van Name's user avatar
0 votes
0 answers
109 views

minimal permutation representations [duplicate]

Suppose I have a finite group $G.$ How hard is it to find the (a?) minimal degree permutation representation of $G?$ The second part of the question is: is there a table of such (hopefully for ...
Igor Rivin's user avatar
  • 95.7k
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 ...
Sebastien Palcoux's user avatar
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 $...
Sebastien Palcoux's user avatar
5 votes
0 answers
94 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, ...
Sebastien Palcoux's user avatar
2 votes
2 answers
358 views

A good upper-bound for the cardinal of an interval of finite groups

This post is a relative version of General bound for the number of subgroups of a finite group Let $[H,G]$ be a interval of finite groups with $|G:H| = n$. Question: What is a good upper-bound of $|[...
Sebastien Palcoux's user avatar
2 votes
0 answers
150 views

Nonvanishing of the dual Euler totient on boolean intervals of finite groups

The rank $n$ boolean lattice $B_n$, is the subset lattice of $\{1,2, \dotsm n \}$. Let $[H,G]$ be a boolean interval of finite groups. Its Euler totient is defined by $$\varphi(H,G):=\sum_{K \in ...
Sebastien Palcoux's user avatar
4 votes
1 answer
368 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 ...
Nikolas Breuckmann's user avatar
1 vote
0 answers
81 views

An optimal lower bound related to generators in a boolean interval of finite groups

Let $[H,G]$ be a rank $n$ boolean interval of finite groups (i.e. $[H,G] \simeq B_n$ as lattice). Let the set $E = \{ g \in G \ | \ \langle H,g \rangle = G \}$ Remark: If $g \in E$ then $Hg \...
Sebastien Palcoux's user avatar
6 votes
1 answer
622 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 ...
Sebastien Palcoux's user avatar
0 votes
1 answer
80 views

About $c(A)$ in $c(A)|A|\leq |A^{-1}A|$

Let $G$ be a finite group, $\emptyset\neq A\subseteq G$, $A^{-1}:=\{ a^{-1}:a\in A\}$, and put $$c(A):=\max\{t\in \mathbb{Z}: t|A|\leq |A^{-1}A|\}$$ It is clear that $1\leq c(A)\leq \frac{|G|}{|A|}$, ...
M.H.Hooshmand's user avatar
2 votes
1 answer
185 views

programming to compute kernel quotient image of a $\mathbb{Z}$-module endomorphism

Let the integers $n\geq 2$, $k\geq 1$, $v=0$ or $1$ and $n_1,\cdots,n_k\geq 1$ such that $$ \sum_{i=1}^k n_i+v=n. $$ Define $P_a^b=0$ if both $a,b$ are odd and $P_a^b={{[a/2]}\choose {[(a+b)/2]}}$ ...
Shiquan Ren's user avatar
  • 1,980
0 votes
1 answer
323 views

Computational Algebra and Symbolic Computation - Where? [closed]

Following the line of this question, I'm in my last year of M.Sc., and I'm looking for a place where I can start my PHD. Since that question has been asked 4 years ago, I thought it may be wise to ask ...
Exodd's user avatar
  • 201
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 \...
Sebastien Palcoux's user avatar
3 votes
1 answer
470 views

Is there a way to find an efficient set of relations for presenting the subgroup generated by two matrices in $SL(2, q)$?

Given two elements $a, b \in SL(2, \mathbb{F}_q)$, is there a way to find an efficient presentation $$\langle x, y \mid \text{relations}\rangle$$ of the subgroup $\langle a, b \rangle$? My intention ...
user avatar