Questions tagged [computational-group-theory]
The computational-group-theory tag has no usage guidance.
75
questions
0
votes
0answers
122 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 ...
5
votes
0answers
113 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 ...
0
votes
0answers
29 views
Rearrangements of Jordan–Holder quotients
Suppose we have a composition series
$$0=M_n\subset M_{n-1}\subset\cdots\subset M_1\subset M_0$$
of $R$-modules, or one of groups:
$$1=G_n\lhd G_{n-1}\lhd\cdots\lhd G_1\lhd G_0$$
(not necessarily ...
4
votes
2answers
138 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
1answer
193 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
1answer
199 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
2answers
291 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)...
3
votes
1answer
194 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....
4
votes
1answer
179 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. ...
8
votes
2answers
682 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
1answer
358 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
1answer
162 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,...
2
votes
0answers
129 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 ...
0
votes
0answers
60 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 ...
22
votes
5answers
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 ...
9
votes
0answers
131 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
681 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
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{...
3
votes
0answers
124 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 ...
9
votes
1answer
638 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
75 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
163 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
63 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)? ...
3
votes
0answers
123 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
1answer
248 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
100 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
419 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 ...
3
votes
2answers
356 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
87 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
305 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
148 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 ...
4
votes
1answer
252 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
76 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
604 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
73 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
168 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
284 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
216 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
304 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 ...
44
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
209 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
473 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
183 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
295 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 ...
11
votes
0answers
648 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 ...
5
votes
1answer
154 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
495 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
233 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 ...
