Questions tagged [computational-group-theory]
The computational-group-theory tag has no usage guidance.
93 questions
2
votes
1
answer
191
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]}}$ ...
- 1,990
0
votes
1
answer
330
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 ...
- 201
9
votes
1
answer
235
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
1
answer
500
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 ...
user76098
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 ...
- 19.6k
1
vote
0
answers
179
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
1
answer
225
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
2
answers
696
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 ...
- 333
4
votes
0
answers
199
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$ ...
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 ...
5
votes
1
answer
327
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 ...
12
votes
0
answers
699
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 ...
- 19.6k
5
votes
1
answer
165
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 ...
7
votes
1
answer
565
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
1
answer
254
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 ...
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 $\...
5
votes
0
answers
300
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
0
answers
302
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 ...
- 19.6k
8
votes
3
answers
505
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 ...
- 19.6k
14
votes
2
answers
1k
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,\...
- 3,104
6
votes
1
answer
517
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 ...
- 656
4
votes
2
answers
308
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} \...
- 2,811
8
votes
2
answers
588
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 ...
- 19.6k
1
vote
0
answers
112
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 ...
- 13.9k
0
votes
0
answers
461
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 ...
- 133
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.
...
- 19.6k
12
votes
0
answers
558
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
$...
- 19.6k
6
votes
3
answers
872
views
An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.
Edited (this question contains two versions of a similar question)
Is there some finitely presented group $G$ generated by $g_1,...,g_n$ such that
there is an element $g\in G$ expressed as a finite ...
- 14.3k
5
votes
0
answers
244
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 ...
- 19.6k
17
votes
0
answers
969
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 ...
- 19.6k
2
votes
0
answers
261
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 ...
- 19.6k
6
votes
1
answer
562
views
Relations in a particular subgroup of the braid group.
I think this should be a 10 minute exercise in a decent computer algebra package - unfortunately I'm hopelessly ignorant of such things, so I'm putting it up here in the hope that someone will be kind ...
- 460
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.
- 151
22
votes
4
answers
1k
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 ...
- 12.7k
17
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$, ...
- 63.1k
5
votes
3
answers
411
views
Computability and complexity of computing $|Hom(G,H)|$ for finitely presented groups G, H.
In the general case, I want to say that determining $|Hom(G,H)|$ is incomputable, arguing that you could use the number to test for simplicity of a presentation, but I am new to this area and I keep ...
0
votes
1
answer
342
views
Necessary/Sufficient condition/Algorithm that tells me a function field is a kummer extension
I start my question with an example. Suppose $F/K$ be the function field generated by $x^n - yx^{n-1} - 1 = 0$. It is not a cyclic over K(y), but if I set $t = yx^{n-1}$ then we have $K(x,t) \subset K(...
- 601
4
votes
1
answer
446
views
Finding groups of odd order without non-cyclic nilpotent quotients
I hope that my question is appropriate for MO, since it might turn out te be mainly a question about GAP or other group theory software.
Is there an algorithm to produce all non-nilpotent groups of ...
- 6,614
9
votes
1
answer
3k
views
How to generate all finite groups of order n? [closed]
I know how to generate all Abelian groups of order n, but how would I generate the others? I can't seem to find anything about this.
By "generate", I mean produce the Cayley tables for all groups of ...
- 193
8
votes
4
answers
7k
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 ...
6
votes
1
answer
837
views
Testing permutations to see if they generate $S_n$
Alright, so a similar question was recently asked about the theoretical bound for generating certain permutations in polynomial time. I had been thinking about a related problem in algorithms (with ...
- 1,723
4
votes
2
answers
544
views
Membership problem in monoids
What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ ...
- 41
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 258