Do powers of 2 maximise the group-count: is $g(n)\le g(2^m)$ for all $n\le 2^m$? (Erdős #1160)
Statement
Let $g(n)$ denote the number of groups of order $n$ up to isomorphism (the group-enumeration function, OEIS A000001). The conjecture asserts that powers of $2$ maximise $g$ over every initial segment of arguments: for every $m$ and every integer $n$ with $n\le 2^m$, one has $g(n)\le g(2^m)$.
Acceptance. FULLY RESOLVES: a complete proof — machine-checkable (Lean/Coq) preferred, else a full written proof with all steps — that $g(n)\le g(2^m)$ for every $m$ and every $n\le 2^m$; OR a counterexample: an explicit pair $(n,m)$ with $n\le 2^m$ and $g(n)>g(2^m)$, giving both group counts together with a certificate of their correctness (e.g. a verified enumeration or GAP SmallGroups computation). ADVANCES (each independently checkable): remove or weaken a hypothesis in the best conditional result stated in the background (currently Pantelidakis: $n$ odd, $m\ge 3619$) with proof; OR prove the stronger summatory form $\sum_{n<2^m}g(n)\le g(2^m)$ for a new class of $m$; OR extend the exhaustively verified range, confirming $g(n)\le g(2^m)$ for all $n$ up to a new record $2^M$ strictly beyond any range stated in the background, with reproducible code and an exhaustiveness certificate. Deliver the proof file, the certified counterexample, or the search code plus the verified range.
Background
Recorded as [Va99, 5.71] and listed as an open problem (Question 22.16) in the monograph of Blackburn, Neumann and Venkataraman on the enumeration of finite groups [BNV07], who describe it as a natural conjecture whose origin they could not trace, attributed at various times to Paul Erdős and to Graham Higman. The intuition is that $g$ is dominated by $p$-groups and grows explosively at prime powers: for the $2$-power case one has the Higman–Sims estimate $\log_2 g(2^m)\sim \tfrac{2}{27}m^3$, far outstripping $g(n)$ for any non-prime-power $n$ nearby. Question 22.18 of [BNV07] proposes the stronger summatory form $\sum_{n<2^m}g(n)\le g(2^m)$ for all sufficiently large $m$ (perhaps as soon as $m\ge 7$). Partial progress: Pantelidakis [Pa03] proved the original conjecture holds when $n$ is odd and $m\ge 3619$. This is the same group-enumeration (gnu) function studied by the venue problem on whether gnu is surjective onto the positive integers (Kourovka 15.99), but the question here is monotonicity/maximality rather than surjectivity. Attacker's tool: exact computation of $g(n)$ via the GAP SmallGroups library to verify the inequality on the largest feasible initial range of $n$, combined with number-theoretic upper bounds on $g(n)$ for non-prime-power $n$ to rule out challengers. Listed as open on erdosproblems.com/1160 (fetched 2026-07-13, status 'open').
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1160 (T. F. Bloom) | website |
| REF-02 | OEIS A000001 — number of groups of order n | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.