2
$\begingroup$

I defined the sequence $t$ where where $t(n)$ is the number of transitive subgroups of $S_n$ where we regard conjugate subgroups as distinct, i.e. the labeled version of A002106 at the OEIS.

Then I computed this sequence using a GAP program written by a professional to get more terms. The first $13$ terms of this sequence are $$1, 1, 2, 9, 20, 279, 512, 19087, 71602, 636365, 1517042, 321965982, 240609602,$$ and I have verified that $\log(\frac{\text{A005432}(n)}{t(n)}) > \frac{n-1}{2}$ for $n$ prime and $\log(\frac{\text{A005432}(n)}{t(n)}) < \frac{n-1}{2}$ for $n$ composite (A005432) up to $n = 18$.

If it helps I have proven that $\text{A005432}(p)-t(p) \equiv 1 \bmod p$ when $p$ is prime.

$\endgroup$
8
  • 1
    $\begingroup$ @Carl-Fredrik Nyberg Brodda: Thank you for improving the question with your edits. $\endgroup$ Dec 9, 2020 at 0:20
  • $\begingroup$ for $n=7$, the equality does not seem to be true because $A005432(7)=1455$, $\lfloor\log 1455\rfloor=7, t(7)=512, (n-1)/2=3$. $\endgroup$
    – markvs
    Dec 9, 2020 at 2:55
  • $\begingroup$ @dodd: Oh dear! I typed it in wrong. I meant floor(log(A005432(n)/t(n))). Thank you. $\endgroup$ Dec 9, 2020 at 14:24
  • $\begingroup$ So you first compute $A...(7)/t(7)$ which is $1455/512$ or about $3$. Then you take log which ia $1....$ Then take floor which is $1$ and claim that it is equal to $3$. $\endgroup$
    – markvs
    Dec 9, 2020 at 14:33
  • 1
    $\begingroup$ @LSpice: Understood regarding question asking norms. Thanks for letting me know and thank you for the additional improvements. $\endgroup$ Dec 9, 2020 at 21:08

1 Answer 1

1
$\begingroup$

Here is a very rough sketch of a proof in the case when $n=p$ is prime.

First, a transitive group of prime degree $p$ is either a subgroup of $AGL(1,p)$, or it is an almost simple $2$-transitive group. (This is due to Burnside.)

Now, these almost simple groups are classified. For most values of $p$, this is only $S_p$ and $A_p$. The exceptional values are $11$, $23$ and when $p$ is of the form $\frac{q^n-1}{q-1}$ for a prime power $q$. (This is due to Guralnick I think.)

So these are very well understood. As for the transitive subgroups of $AGL(1,p)$, there is one conjugacy class for every divisor $d$ of $p-1$, with shape $C_p\rtimes C_d$. It's not hard to show that the normaliser of such a group is exactly $AGL(1,p)$, so the size of the conjugacy class is $\frac{p!}{p(p-1)}=(p-2)!$ So, if $f$ is the number of divisors function, the number of subgroups in this family is $(p-2)!f(p-1)$.

So, for non-exceptional primes $p$, we have that $t(p)=2+(p-2)!f(p-1)$. (For example, this holds for $p\in\{5,19,29,37,41,43,47...\}$.)

For exceptional primes, the number is a little larger, but it can be controlled, and I think it can be showed that it is asymptotically equal to the above.

Now, write $a(p)=A005432(p)$. According to the OEIS page, Pyber proved that $a(p)\geq c^{p^2}$, with $c$ a known constant. So, in the non-exceptional case, we have $\log\left(\frac{a(p)}{t(p)}\right)=p^2 \log c-\log t(p)$. Using Stirling's approximation, we find that $\log t(p)$ is roughly $p\log p$, so the desired result holds asymptotically. By being careful with error terms throughout, it should not too hard to close the finite gap.

As for the case $n$ composite, it's possible it's not true. We are trying to prove that $\log a(n)-log t(n) < \frac{n-1}{2}$. But by Pyber, $\log a(n)$ is very close to $n^2\log d$. Since $a(n)>t(n)$, the inequality above can only be true if there is a lot of cancellation, more precisely, it would imply $\frac{\log a(n)}{\log t(n)}\to 1$. In other words, after taking logs, "almost all" subgroups are transitive. My guess is that this is not true and, for large $n$, $\log a(n)-\log t(n)$ will grow like $kn^2$. To prove this, one would need decent upper bounds on $t(n)$. Pyber has many results of this kind, but they are sometimes hard to find, I'll try and have a look...

$\endgroup$
2
  • $\begingroup$ Much to absorb here. In light of your calculation, agreed that the claim about composites seems unlikely to hold. Unfortunately, it's hard to get data on A005432 for large $n$. $\endgroup$ Dec 18, 2020 at 13:23
  • $\begingroup$ I have had more time to digest part of this argument and, despite the interface telling me that I am not supposed to say "thanks", thank you. In particular, you have explained the preponderance of values of $t$ ending in 2 which I saw no explanation for. $\endgroup$ Dec 24, 2020 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.