Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computational-group-theory]

22
votes
5answers
3k 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 ...
12
votes
2answers
1k 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$,...
1
vote
1answer
181 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
0answers
35 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 ...
6
votes
2answers
381 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 ...
8
votes
0answers
97 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
2answers
560 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 ...
3
votes
1answer
252 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]$, ...
7
votes
0answers
243 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 ...
42
votes
1answer
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
2answers
868 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{...
16
votes
0answers
833 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
3answers
465 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
0answers
106 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
1answer
453 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
1answer
207 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 \...
6
votes
0answers
254 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
vote
0answers
63 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
1answer
140 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 ...
10
votes
2answers
286 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 ...
12
votes
0answers
516 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 $...
2
votes
0answers
52 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)? ...
2
votes
0answers
107 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 ...
0
votes
0answers
96 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 ...
8
votes
0answers
383 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^c$ be its lattice ...
5
votes
0answers
79 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, ...
2
votes
2answers
289 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 $|[...
2
votes
0answers
142 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 ...
6
votes
1answer
596 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 ...
12
votes
2answers
1k 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
2answers
734 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,\...
4
votes
0answers
211 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 ...
3
votes
1answer
189 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 ...
1
vote
0answers
75 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 \...
3
votes
2answers
275 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} \...
0
votes
1answer
71 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|}$, ...
2
votes
1answer
165 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]}}$ ...
0
votes
1answer
259 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 ...
5
votes
4answers
4k 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 ...
3
votes
1answer
248 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 ...
1
vote
0answers
177 views

Are the finite groups inclusions, almost all relatively cyclic?

Definition: An inclusion of finite groups $(A \subset B)$ is relatively cyclic if $\exists b \in B$ such that $\langle A,b \rangle = B$. Definition: Two inclusions of finite groups are equivalent, $(...
1
vote
1answer
205 views

Is a prime index inclusion of finite groups, separating?

Let $(H \subset G)$ be an inclusion of finite groups. Let $\{ g_i \ \vert \ i \in I=[1, \dots ,n] \}$ a subset of $G$ of double coset representatives, i.e. $$G = \coprod_{i \in I} Hg_iH$$ On the ...
3
votes
0answers
176 views

Generalization of the fundamental theorem of cyclic groups 2

This post is a sequel of 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$ ...
5
votes
1answer
1k 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 ...
21
votes
3answers
753 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 ...
5
votes
1answer
279 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 ...
10
votes
0answers
532 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 ...
4
votes
1answer
139 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
0answers
176 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: ...
2
votes
1answer
224 views

Classification of indecomposable inclusions $(H \subset G)$ with $G$ decomposable

Definition: A group $G$ is indecomposable if: $G = G_1 \times G_2 \Rightarrow \exists i \ G_i = 1$. We can generalize the notion of indecomposable from groups to inclusion of groups as ...