/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 1160
References:
[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference "Paul Erdős and his mathematics", Budapest, July 1999 (1999).
[BNV07] Blackburn, S. R., Neumann, P. M. and Venkataraman, G., Enumeration of finite groups. Cambridge Tracts in Mathematics 173, Cambridge University Press (2007), xii+281.
[Pa03] Pantelidakis, I., On the Number of Non-isomorphic Groups of the Same Order. DPhil thesis, University of Oxford (2003).
@[expose] public sectionopen Filternamespace Erdos1160$g(n)$, the number of groups of order $n$ up to isomorphism: the number of isomorphism classes of finite groups $G$ with $\lvert G\rvert = n$.
The groups are the objects of FiniteGrp.{0}, the category of finite groups in the lowest
universe. Every finite group is isomorphic to one of them. Two objects are in the same class if
Nonempty (G ≅ H) (CategoryTheory.isIsomorphicSetoid). We take the image of
{G | Nat.card G = n} in the quotient by this relation and count it with Set.ncard.
For $n\geq 1$ the number of classes is finite, because a group of order $n$ is determined up to
isomorphism by a multiplication table on Fin n. So Set.ncard is the true count and not the
junk value $0$ of an infinite set. For $n=0$ the set is empty (a group has an identity), so
$g(0)=0$.
noncomputable def g (n : ℕ) : ℕ :=
(Quotient.mk (CategoryTheory.isIsomorphicSetoid FiniteGrp.{0}) ''
{G : FiniteGrp.{0} | Nat.card G = n}).ncardThere are no groups of order $0$.
@[category test, AMS 20]
theorem g_zero : g 0 = 0 := ⊢ g 0 = 0
h:{G | Nat.card ↑G.toGrp = 0} = ∅⊢ g 0 = 0
All goals completed! 🐙Let $g(n)$ denote the number of groups of order $n$. If $n\leq 2^m$ then $g(n)\leq g(2^m)$.
This is [Va99, 5.71] and an open problem (Question 22.16) in [BNV07], where its origin could not be traced. It has been attributed to Erdős, Higman and others. Pantelidakis [Pa03] proved it for odd $n$ and $m\geq 3619$.
It is a conjecture, not a question. We take $n\geq 1$; for $n=0$ it holds trivially, since $g(0)=0$.
@[category research open, AMS 20]
theorem erdos_1160 : ∀ n m : ℕ, 0 < n → n ≤ 2 ^ m → g n ≤ g (2 ^ m) := ⊢ ∀ (n m : ℕ), 0 < n → n ≤ 2 ^ m → g n ≤ g (2 ^ m)
All goals completed! 🐙Question 22.18 of [BNV07] suggests the even stronger conjecture $$\sum_{n<2^m}g(n) \leq g(2^m)$$ for all sufficiently large $m$ (perhaps even as soon as $m\geq 7$).
The sum is over $1\leq n<2^m$.
@[category research open, AMS 20]
theorem erdos_1160.variants.sum :
∀ᶠ m : ℕ in atTop, ∑ n ∈ Finset.Ico 1 (2 ^ m), g n ≤ g (2 ^ m) := ⊢ ∀ᶠ (m : ℕ) in atTop, ∑ n ∈ Finset.Ico 1 (2 ^ m), g n ≤ g (2 ^ m)
All goals completed! 🐙end Erdos1160