Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?

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.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k