All Questions
126 questions
2
votes
0
answers
163
views
Nonabelian groups where every element has small order
Let $G$ be a finite nonabelian group with the property that if $g \in G$, then
$$\DeclareMathOperator{\ord}{ord} \ord(g) \leqslant 10 \log_2 |G|, $$
where $\ord(g)$ is the order of the element $g$, ...
- 1,354
8
votes
1
answer
1k
views
GAP cannot solve Rubik's cube 4x4x4 and higher ? (Practical limits of Schreier–Sims algorithm)
According to our practical experiments and literature search - computer algebra system GAP cannot "solve" Rubik's cube 4x4x4 and higher. That means cannot decompose given random element of ...
- 24.9k
4
votes
0
answers
115
views
Complexity to find "short" (e.g. polynomial in diameter) decomposition of the permutation into the product of generators?
Question 1: Consider the symmetric group $S_n$ and some set of permutations $p_i$. Given permutation $g$ - what is known about the algorithmic complexity to decompose $g$ into product of $p_i$ ...
- 24.9k
9
votes
0
answers
292
views
Tilings in finite (not necessarily Abelian) groups
Let $G$ be a finite (not necessarily abelian) group. We call $A \subseteq G$ a right-tiling (for simplicity, a tiling) of $G$ if there exists a $B \subseteq G$ so that
$$ G = \bigsqcup_{b\in B} bA.$$
...
- 1,354
0
votes
1
answer
155
views
Combinatorial problem in $G(54, \, 5)$ - Reprise
This post is a follow-up to my previous post MO479127. I am trying to concentrate on a subset of relations, hoping to find some structure on the set of solutions that explains why the whole set of ...
- 66.3k
3
votes
0
answers
359
views
Combinatorial problem in $G(54,\, 5)$
I have asked (probably) easier versions of this question in the past, see MO379272 and MO380292. At the moment, it is not clear to me how the beautiful answers to those questions can be helpful here.
...
- 66.3k
2
votes
0
answers
98
views
Estimating the cardinality of the set of conjugacy classes of subgroups in a finite group of given order
1. Let $G$ be a finite group of order $n$. I need an estimate for the number $c$ of conjugacy classes of subgroups $D\subseteq G$.
Note that any subgroup of $G$ contains $1_G$, and so the set of all ...
- 14.1k
4
votes
0
answers
227
views
Polynomials of growth for finite Heisenberg groups
Take a standard finite Heisenberg group with two standard generators and let's consider its growth polynomial - the polynomial which coefficients are equal to the sphere sizes.
For example for $H_3(Z/...
5
votes
1
answer
365
views
Number of $k$-tuples of elements generating a cyclic group
Let $k$, $m$ be natural numbers, and $C_m:=\mathbb{Z}/ m \mathbb{Z}$ be the cyclic group of order $m$.
Let $N_{k, \, m}$ be the cardinality of the following set: $$\{(a_1, \ldots, a_k) \in (C_m)^k \; ...
- 66.3k
20
votes
1
answer
993
views
Proof of CFSG assuming every simple group is two-generated
It is well-known that one of the corollaries of the classification of finite simple groups (CFSG) is that every finite simple group can be generated by two elements. In a comment on an answer to an ...
1
vote
0
answers
175
views
Random walk on N-Rubik cube group is going like sqrt(number of moves) or linear (number of moves) or? "commutative" vs. "free"(like) group pattern?
Consider higher (NxNxN) Rubik's cube group, with specific set of generators described below.
What is important - that there are huge COMMUTING subsets of generators.
Question: Consider a random walk ...
- 24.9k
5
votes
0
answers
200
views
Subgroups of the symmetric group and binary relations
Motivation
The following came up in my work recently. (NB this is the motivation, not the question I'm asking. You can skip to the actual question below, which is self-contained, but not self-...
- 756
12
votes
1
answer
450
views
abelian quotients of permutation groups
Let $G$ be a subgroup of the permutation group $S_n$, and let $H$ be a normal subgroup of $G$ such that the quotient group $G/H$ is abelian. What is the best known upper estimate for the cardinality $...
- 1,294
4
votes
0
answers
108
views
Doubly stochastic matrices that remain doubly stochastic after conjugating by the character table of a finite abelian group
I am curious if anything is known about the following.
Let $\Gamma$ be a finite abelian group, and let $\chi$ be its character table, normalized so that it is a unitary matrix. E.g., if $\Gamma$ is $\...
- 2,339
5
votes
1
answer
358
views
The number of polynomials on a finite group, II
This question is follow up of this MO-post.
First let us recall the necessary definitions.
A function $f:X\to X$ on a group $X$ is called a polynomial if there exists $n\in\mathbb N$ and elements $a_0,...
- 41.8k
3
votes
0
answers
100
views
Commuting probabilities for a conjugacy class of a finite simple group $G$ which generates $G$
Let $G$ be a nonabelian finite simple group. Let $C\subset G$ be a conjugacy class which generates $G$. Let $E\subset C\times C$ be the subset consisting of pairs $(c,d)$ with $cd =dc$. Define the ...
- 7,527
0
votes
1
answer
130
views
Number of reduced decompositions of the dihedral group $D_6$ [closed]
The Weyl group of $\frak{g}_2$ is the dihedral $D_6$. Let us denote its longest element by $w_0$. How many reduced decompositions does $w_0$ have?
- 327
54
votes
4
answers
5k
views
How many square roots can a non-identity element in a group have?
Let $G$ be a finite group. Let $r_2\colon G \to \mathbb{N}$ be the square-root counting function, assigning to each $g\in G$ the number of $x\in G$ with $x^2=g$. Perhaps surprisingly, $r_2$ does not ...
- 805
2
votes
0
answers
203
views
Can the relation between count of commuting pairs and conjugacy classes for finite groups be generalized to semigroups?
It is well-known that number of pairs of commuting elements in finite group G is equal to number of conjugacy classes multiplied by cardinality of G.
More generally here (MO275769) Qiaochu Yuan ...
- 24.9k
0
votes
0
answers
121
views
Another question concerning finite metacyclic groups
Given a non-split finite metacyclic group $H$, does there always exist a finite split metacyclic group $G$ with a normal cyclic subgroup $N$ of prime power order such that $H \cong G/N$?
Based on my ...
28
votes
6
answers
1k
views
Are there always more conjugacy classes in the kernel of a morphism to $Z_2$ than not?
Let $G$ be a finite group and let $\phi:G\to Z_2$ be a homomorphism to the group with two elements. Is it always the case that there are more conjugacy classes in the kernel of $\phi$ than conjugacy ...
- 513
2
votes
2
answers
309
views
Combinatorial problem in $G(32, \, 6)$
The following problem arose when studying the same type of questions in Algebraic Geometry that led me to my previous question MO379272.
Let us consider the group $G$ of order $32$ whose label in GAP4 ...
- 66.3k
1
vote
0
answers
144
views
Simultaneous similarity classes of pairs in $\mathrm{GL}_{n}(\Bbb Z / p\Bbb Z)$?
$\DeclareMathOperator{\GL}{\operatorname{GL}}$Let $G$ be an elementary abelian $p$-group of rank $2$. Let $\alpha, \beta :G\rightarrow \GL_{n}(\Bbb Z / p\Bbb Z)$ be two injective homomorphisms. The ...
- 181
3
votes
0
answers
210
views
How many conjugacy classes of elementary abelian subgroups of order $p^2$ does $\operatorname{GL}_{4}(\Bbb Z / p\Bbb Z)$ have?
$\DeclareMathOperator\Hom{Hom}\DeclareMathOperator\GL{GL}\DeclareMathOperator\Aut{Aut}$Let $f\in \Hom((\Bbb Z/p\Bbb Z)^2,\GL_{4}(\Bbb Z / p\Bbb Z))$ be an injective homomorphism. What is the number of ...
- 463
8
votes
0
answers
247
views
Computing the number of elementary abelian p-subgroups of rank 2 in $GL_{n}(\mathbb{F}_{p})$
Let $p$ be a prime number, and let $\mathbb{F}_{p}$ be a finite
field of order $p$. Let $GL_{n}(\mathbb{F}_{p})$ denote the general linear
group and $U_{n}$ denote the unitriangular group of $n\times ...
- 463
3
votes
0
answers
92
views
Symmetric group in terms of block permutations
For $i+j+k=N$, consider the permutation $\Pi_{i,j,k}\in S_N$, which keeps the numbers $0,\ldots,i-1$ fixed, and exchanges the numbers $i,\ldots,i+j-1$ with the numbers $i+j,\ldots,i+j+k-1$.
$$\Pi_{i,j,...
- 3,001
-1
votes
1
answer
215
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
- 2,089
8
votes
2
answers
4k
views
Order of product of group elements
Let $G$ be a finite non-commutative group of order $N$, and let $x, y \in G$. Let $a$ and $b$ be the orders of $x$ and $y$, respectively. Can we say anything non-trivial about the order of $xy$ in ...
- 1,703
28
votes
1
answer
2k
views
Multiplying all the elements in a group
Let $G = \{ g_i | i = 1, ...,n \}$ be a finite group and denote by $G!$ the multiset consisting of all the products of all different elements of $G$ in any order, that is
$$ G! = [ \prod_i g_{\sigma(i)...
- 943
1
vote
1
answer
267
views
Adding $n$-tuples over groups
Consider a finite abelian group $\mathcal{G}$. Let $S_0$ be a $n$-tuple of elements of $\mathcal{G}$, and let $S_i$ be the cyclically shifted version of $S_0$ by $i$ indices to the right. So for ...
- 431
-1
votes
1
answer
325
views
Isomorphism classes of split extensions [closed]
Let $p$ be a prime number and $n$ an integer such that $p\geq n$. Let $P(n)$ denotes the number of partitions of $n$. Can we conclude from Theorem 1.1 and Theorem 1.3 in the reference FINITE_p-...
- 181
1
vote
0
answers
247
views
Sidon sets in finite groups
Suppose $G$ is a group, $S \subset G$. Let’s call $S$ a Sidon subset iff $\forall$ quadruples $(a, b, c, d)$ of distinct elements of $S$ we have $ab \neq cd$ (named after Simon Sidon who studied such ...
- 2,618
16
votes
1
answer
395
views
Geometric interpretation of the exceptional isomorphism $PSp(4,3)=PSU(4,2^2)$
It is well-known that there is an isomorphism between $PSp(4,3)$ (the symplectic group of dimension $4$ over $\mathbb F_3$) and $PSU(4,2^2)$ (the unitary group defined by $4\times4$ unitary matrices ...
- 9,501
1
vote
1
answer
255
views
Number of commuting pairs in p-group
Let $p$ be a prime number and $G=GL_n ( \mathbb{Z} / p \mathbb{Z}
)$. Consider the set $U$ of upper-triangular matrices of $G$ having
entries of $1$ on the diagonal. The set $U$ is a Sylow $p$-...
- 181
12
votes
2
answers
406
views
Does asymmetric fraction of finite groups tend to $0$?
Let’s define asymmetric fraction of a finite group $G$ as the number $$\mathrm{af}(G) = \frac{|\{(g, a) \in G \times \mathrm{Aut}(G)\mid a(g) = g\}|}{|G|\cdot|\mathrm{Aut}(G)|}.$$ Equivalently it can ...
- 2,618
7
votes
1
answer
581
views
Wreath product $S_k\wr S_n$ inside $S_{kn}$
I want to understand wreath products a little better.
Currently, my intuition about them is as follows. Take $nk$ disks, pile them in order forming $n$ piles of $k$ disks (one pile contains disks {1,...
- 1,549
5
votes
1
answer
275
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 237
5
votes
0
answers
196
views
Are finite groups of exponent $d$ rare for $d \neq 4$?
Is there a way to prove, that $\lim_{n \to \infty} \frac{\text{the number of all groups of exponent }d \text{ and order less than }n}{\text{the number of all groups of order less than } n} = 0$ for $d ...
- 2,618
9
votes
1
answer
357
views
Is there a way to prove, that $2$-generated groups are rare among finite groups?
Is there a way to prove, that $\lim_{n \to \infty} \frac{\text{the number of all } 2 \text{-generated groups of order less than }n}{\text{the number of all groups of order less than } n} = 0$?
This ...
- 2,618
3
votes
1
answer
193
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,...
1
vote
0
answers
127
views
Lower and upper bounds of the distance between two Frobenius numbers
I consider two sequences of numbers: $A=\{a_1,...,a_{m-1},n\}$ and $B=\{n-a_{m-1},...,n-a_1,n\}$, where $a_1 < a_2 < ... < a_{m-1} < n$ and $\gcd(A) = \gcd(B) = 1$.
I investigate the ...
- 13
11
votes
1
answer
550
views
Probability of words summing to $1$ in $S_n$ or $\mathrm{PGL}_2(n)$
$\DeclareMathOperator\PGL{PGL}\DeclareMathOperator\Conj{Conj}$Let $G$ be the symmetric group $S_n$ or the projective general linear group $\PGL_2(n)$.
Let $X$ be a cyclically reduced word in the ...
- 9,501
3
votes
2
answers
178
views
Asymptotics of regular semisimple elements in finite groups of lie type
Let $G$ be a reductive algebraic group defined over $\mathbb{F}_{q}$. Let $G(\mathbb{F_{q}})$ denote the finite group of fixed points under the Frobenius map $F$. Now, we know that the set of regular ...
- 424
0
votes
1
answer
223
views
Greatest common divisor of two specified sequences of numbers (search for equality)
I consider two sequences of numbers $A=\{a_1,...,a_n\}$ and $B=\{k-a_1,...,k-a_n\}$, where $a_1 \le a_2 \le ... \le a_n \le k$.
I am looking for such conditions under which: $\gcd(a_1,...,a_n) = \gcd(...
- 13
5
votes
1
answer
316
views
Connected permutation groups and wreath product
Let $G$ and $H$ be subgroups of the symmetric groups $\mathfrak S_m$ and $\mathfrak S_n$. Assume that $n>1$ and that $H$ is a 'connected' permutation group, that is, there is no non-trivial $H$-...
- 5,822
2
votes
0
answers
116
views
On covers of groups by cosets
Suppose that ${\cal A}=\{a_sG_s\}_{s=1}^k$ is a cover of a group $G$ by (finitely many) left cosets with $a_tG_t$ irredundant (where $1\le t\le k$). Then the index $[G:G_t]$ is known to be finite. In ...
- 15.6k
31
votes
2
answers
1k
views
Does the symmetric group $S_{10}$ factor as a knit product of symmetric subgroups $S_6$ and $S_7$?
By knit product (alias: Zappa-Szép product), I mean a product $AB$ of subgroups for which $A\cap B=1$. In particular, note that neither subgroup is required to be normal, thus making this a ...
- 1,068
3
votes
0
answers
303
views
Growth functions of finite group - computation, typical behaviour, surveys?
Looking on the growth function for Rubik's group and symmetric group, one sees rather different behaviour:
Rubik's growth in LOG scale (see MO322877):
S_n n=9 growth and nice fit by normal ...
- 24.9k
13
votes
1
answer
2k
views
Number of positions of Rubik's cube grows with multiplier 13 with the distance - what are explanations and groups with similar growth pattern?
Rubik's cube and its generalizations attracts certain attention of mathematical community. It is somehow "noteworthy" that it has been proved that diameter of the Rubik's cube group is 20, i.e. ...
- 24.9k
4
votes
0
answers
266
views
Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)
In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
- 24.9k