Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
Motivation. This question arises in the context of a certain finite analogue of Borel equivalence relation theory. I explained in
this answer that the purpose of Borel equivalence relation theory is to analyze the complexity of various
naturally occuring equivalence relations in mathematics, such as the isomorphism relations on various types of structures. It turns out that many of the
most natural equivalence relations arising in mathematics are Borel relations on a standard Borel space, and these fit into a hierarchy under Borel reducibility. Thus, this subject allows us make precise the idea that some classification problems are wild and others tame, by fitting them into a precise hierarchy where they can be compared with one another under reducibility. Recently, there has
been some work adapting this research project to other contexts. Last Friday, for example, Sy Friedman gave a
talk for our seminar on an effective analogue of the Borel theory. Part of his analysis provided
a way to think about very fine distinctions in the relative difficulty even of the various problems of classifying finite structures,
using methods from complexity theory, such as considering NP equivalence relations under polytime reductions.
For a part of his application, it turned out that fruitful conclusions could be made when one knows something about
the asymptotic growth rate of the number of isomorphism classes, for the kinds of objects under consideration.
This is where MathOverflow comes in. I find it likely that there are MO people who know about the number of groups.
Therefore, please feel free to ignore all the motivation above, and
kindly tell us all about the values or asymptotics of the
following functions, where n is a natural number:
-
G(n) = the number of groups of size at most n.
-
R(n) = the number of rings of size at most n.
-
F(n) = the number of fields of size at most n.
-
Γ(n) = the number of graphs of size at most n.
-
P(n) = the number of partial orders of size at most n.
Of course, in each case, I mean the number of isomorphism types of such objects. These particular functions are representative, though of course, there
are numerous variations. Basically I am interested in the number of isomorphism classes of any kind of natural finite structure, limited by size.
For example, one could modify Γ for various specific kinds of graphs, or modify P for various kinds of partial orders, such as trees,
lattices or orders with height or width bounds. And so on.
Therefore, please answer with other natural classes of finite structures, but I shall plan to accept the answer for my favored
functions above. In many of these other cases, there are easy answers. For example, the
number of equivalence relations
with n points is the intensely studied partition number of n. The number of Boolean
algebras of size at most n is just log2(n), since all finite Boolean algebras are finite power sets.
Best Answer
Roughly speaking, the more high powers of primes divide $n$, the more groups of order $n$ there should be. In fact, if $f(n)$ is the number of isomorphism classes of groups of order $n$, then $$ f(n)\leq n^{(\frac{2}{27}+o(1))e(n)^{2}}% $$ where $e(n)$ is the largest exponent of a prime dividing $n$ and $o(1)\rightarrow0$ as $e(n)\rightarrow\infty$ (see Pyber, L. Enumerating finite groups of given order. Ann. of Math. (2) 137 (1993), no. 1, 203--220. MR1200081).
From my Group Theory notes page 12.