Asymptotic formula for the number of subgroups of the symmetric group $S_n$ (Erdős #1162)
Statement
Let $f(n)$ denote the total number of subgroups of the symmetric group $S_n$ (all subgroups, not counted up to conjugacy or isomorphism). Give an asymptotic formula for $f(n)$ as $n\to\infty$, and determine whether there is a statistical (limiting-distribution) theorem describing the orders of these subgroups.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof) of either (a) a genuine asymptotic $f(n)\sim F(n)$ for an explicit function $F$, or (b) an expansion of $\log f(n)$ strictly sharper than $\left(\tfrac{1}{16}+o(1)\right)n^2$ — for instance determining the next-order term — AND/OR a rigorous limiting-distribution theorem for the orders of subgroups of $S_n$. ADVANCES (each independently checkable): quantify the $o(1)$ error in $\log f(n)=\left(\tfrac{1}{16}+o(1)\right)n^2$ with an explicit rate, or prove matching upper/lower refinements strictly better than the statement in the background, with proof; OR compute $f(n)$ exactly for a new record range of $n$ with reproducible code and use the data to establish or rule out a conjectured second-order term or an empirical law for subgroup orders. Anchor any bound to 'strictly better than the best bound stated in the background'. Deliver the proof of the formula, or the enumeration code plus the extended exact values and the refined bound.
Background
A problem of Erdős and Turán, recorded as [Va99, 5.73]. Known frontier for the count: Pyber [Py93] proved $\log f(n)\asymp n^2$, i.e. $\log f(n)$ is bounded above and below by constant multiples of $n^2$. Roney-Dougal and Tracey [RoTr25] sharpened this to $\log f(n)=\left(\tfrac{1}{16}+o(1)\right)n^2$, pinning the leading constant; the dominant contribution comes from subgroups built around large elementary abelian $2$-subgroups. Despite this, a genuine asymptotic formula for $f(n)$ itself — beyond the leading term of its logarithm — is not known, and no statistical law for the distribution of the orders of subgroups of $S_n$ has been established. Attacker's tool: exact enumeration of the subgroups of $S_n$ for small $n$ using computational group theory (GAP), to test candidate second-order terms in $\log f(n)$ and to probe the empirical distribution of subgroup orders, combined with the analytic $p$-group-counting arguments underlying the $\tfrac{1}{16}n^2$ bound. Listed as open on erdosproblems.com/1162 (fetched 2026-07-13, status 'open').
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1162 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.