1
$\begingroup$

Consider $\;\alpha=(\alpha_1,...,\alpha_n)\in\mathbb{Z}_+^n\;$ such that $\;1\alpha_1+...+n\alpha_n=n.\;$ Let $\varphi$ denote Euler totient-function.

Let $\;T_\alpha\;$ be a set of permutations in $S_n\;$ of a type $[1^{\alpha_1}...n^{\alpha_n}].\;$ It's well-known that $\;\#T_\alpha=\frac{n!}{1^{\alpha_1}\cdot...\cdot n^{\alpha_n}\cdot\alpha_1!\cdot...\cdot\alpha_n!}.\;$

Obviously, $\forall\sigma\in T_\alpha\;|\{\sigma^d:\;d\in\mathbb{N}\}\cap T_\alpha|=\;\varphi(L_\alpha),\;$ where $\;L_\alpha=\min(L:\;\forall i\;(\alpha_i\neq0\;\Rightarrow\;i|L)).\;$

Let $G$ be a finite group. For $x,y\in G\;$ say, $\;(x\succeq y)\;\Leftrightarrow\;(\exists d\in\mathbb{N}: x^d=y)\;$. Say, $(x\sim y)\;\Leftrightarrow\;(x\succeq y\;\land\;y\succeq x).$

Thus, $|S_n/\sim|=\sum_\limits{\alpha\vdash n}\frac{\#T_\alpha}{\varphi(L_\alpha)}.\;$ So, I have two questions:

  1. Are there any number-theoretic proofs of integrality of $\displaystyle\frac{\#T_\alpha}{\varphi(L_\alpha)}=\frac{n!}{1^{\alpha_1}\cdot...\cdot n^{\alpha_n}\cdot\alpha_1!\cdot...\cdot\alpha_n!\cdot\varphi(\min(L:\;\forall i\;(\alpha_i\neq0\;\Rightarrow\;i|L)))}?$
  1. What is asymptotics of $|S_n/\sim|\;$ as $\;n\rightarrow\infty?$

I've heard, it's not good to ask questions here without trying to answer them oneself, but I have no idea how to do it. The only thing I can do is checking values of $|S_n/\sim|$ for small $n$.

Improve this question
$\endgroup$
6
  • $\begingroup$ Regarding the equivalence relation $\sim$: you might want to Google the keyword "power graph of a group." $\endgroup$
    – Sam Hopkins
    Commented Feb 16, 2022 at 18:39
  • $\begingroup$ By the way, another way to phrase $\sim$ (at least for finite groups $G$): $g\sim h$ if $g$ and $h$ generate the same cyclic subgroup. Hence you are asking for (an asymptotic for) the number of cyclic groups of the symmetric group. $\endgroup$
    – Sam Hopkins
    Commented Feb 16, 2022 at 18:41
  • 1
    $\begingroup$ $\varphi(L_{\alpha}) \le L_{\alpha} \le g(n)$ where $g(n)$ is OEIS A000793, so $\frac{n!}{g(n)} \le |S_n/\sim| \le n!$. In the limit, Landau's estimate for $g$ and Stirling's approximation give $n\ln n - n - \sqrt{n \ln n} + \Theta (\ln n) \le \ln |S_n/\sim| \le n\ln n-n+\Theta (\ln n)$. Is $\ln |S_n/\sim| = n\ln n - n - O(\sqrt{n \ln n})$ a good enough asymptotic for you? $\endgroup$
    – Peter Taylor
    Commented Feb 21, 2022 at 12:57
  • 1
    $\begingroup$ I don't currently have a clear idea of how to do that, but applying the last sentence of the question and computing small values I've found (a) OEIS A051625 (no given asymptotic, so possibly there isn't one in the literature); (b) for $1 \le n \le 100$ the value of $\frac{|S_n|}{|S_n/\sim|}$ seems to grow quadratically. $\endgroup$
    – Peter Taylor
    Commented Feb 21, 2022 at 16:22
  • 1
    $\begingroup$ Code to calculate terms and first 200 terms. The sequence seems to have some curious arithmetic properties. Based on prime powers up to 64, I conjecture that (a) for every prime power $q=p^k$ there is a cutoff $c_q$ such that beyond the cutoff the values modulo $q$ are periodic with period $q$; (b) for every prime $p > 2$, $c_p = p - 1$; (c) for every prime $p > 2$ and integer $n \ge p$, $f(n) \equiv 2f(n \bmod p) \pmod p$. $\endgroup$
    – Peter Taylor
    Commented Feb 23, 2022 at 0:11

0

Reset to default

You must log in to answer this question.