Questions tagged [computational-group-theory]
The computational-group-theory tag has no usage guidance.
7
votes
0answers
84 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
557 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 ...
26
votes
2answers
853 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
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
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
62 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 ...
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
104 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 ...
1
vote
0answers
135 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
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
382 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 ...
3
votes
1answer
251 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]$, ...
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
288 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 ...
3
votes
1answer
187 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 \...
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 ...
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
258 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 ...
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 \...
3
votes
1answer
246 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 ...
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 ...
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 ...
10
votes
2answers
283 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 ...
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 ...
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
530 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 ...
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-...
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 ...
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 ...
5
votes
0answers
173 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: ...
7
votes
0answers
240 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 ...
8
votes
3answers
464 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 ...
12
votes
2answers
727 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,\...
6
votes
1answer
413 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 ...
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} \...
6
votes
2answers
305 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 ...
1
vote
0answers
110 views
Generator size for cyclic groups
Let $p$ be prime. Consider $\Bbb Z_{p}$, the cyclic multiplicative group.
Is it possible to choose a generator $c$ as small as $O(\log(p))$? (wiki shows $c$ as small as $O(\log^{6}(p))$ is possible ...
0
votes
0answers
286 views
Computational Ring Theory
I have tried to understand and program CGT algorithms though I am a beginner still. But I never get to hear Computational Ring Theory. Even GAP largely supports Groups Theory. Is there some initiative ...
6
votes
0answers
683 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 ...
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
$...
4
votes
0answers
210 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 ...
16
votes
0answers
829 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 ...
2
votes
0answers
245 views
Characterization of the elements of an infinite simple group
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 ...
