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.? - MathOverflow

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.?

2010-04-13T21:57:07Z

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 log₂(n), since all finite Boolean algebras are finite power sets.

Answer by Rob Harron for 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.?

2010-04-13T23:14:25Z

For groups: you can check out this recent paper of John Conway, Heiko Dietrich, and E.A. O'Brien (DOI) for results and conjectures on counting the number of groups of a given order (I also seem to remember a recent article of Conway's in the Notices of the AMS (or maybe the Bulletin) on this subject).

For fields: there is a unique isomorphism class of fields of size $p^n$ for each prime $p$ and each positive integer $n$, so one can figure out the asymptotic from the prime number theorem.

For rings: the OEIS has information on this sequence here.

Answer by François G. Dorais for 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.?

2010-04-13T23:22:32Z

Community wiki of resources from the Online Encyclopedia of Integer Sequences:

Number of groups of size n A000001
Number of graphs of size n A000088
Number of posets of size n A000112
Number of abelian groups of size n A000688
Number of rings of size n A027623

Answer by Michael Lugo for 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.?

2010-04-13T23:37:00Z

Posets are A000112 in Sloane.

The asymptotics aren't given there, but are known. See D. J. Kleitman and B. L. Rothschild, The number of finite topologies, Proc. AMS 25 (1970) 276-282. This paper shows that $\log_2 P_n = n^2/4 + o(n^2)$, where $P_n$ is the number of posets on $n$ elements.

The full asymptotic formula is given in Kleitman and Rothschild, Asymptotic enumeration of partial orders on a finite set, Transactions of the American Mathematical Society 205 (1975) 205-220. This paper gives $\log P_n = n^2/4 + 3n/2 + o(\log n)$, and an explicit (but messy) asymptotic formula for $P_n$.

Edited to add: Richard Stanley, in Enumerative Combinatorics volume 1, exercise 3.3(e) (rated [3+]), gives $$ P_n \sim C \cdot 2^{n^2/4+3n/2} e^n n^{-n-1} $$ where $C = {2 \over \pi} \sum_{i \ge 0} 2^{-i(i+1)}$; he states this is a simplification of the formula from Kleitman-Rothschild (1975) that I haven't written out here.

Answer by François G. Dorais for 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.?

2010-04-13T23:47:54Z

As observed by Rob, there is exactly one field for each prime power order. The exact formula for the number of fields is then $$F(n) = \pi(n) + \pi(n^{1/2}) + \pi(n^{1/3}) + \cdots$$ where $\pi(x)$ counts the number of primes up to $x$. There are $O(\log n)$ nonzero lower order terms each of which is $O(\sqrt{n})$. So the leading term $\pi(n)$ dominates and the Prime Number Theorem gives the asymptotic $F(n) \sim \mathrm{Li}(n) \sim n/\log(n)$.

Answer by S. Carnahan for 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.?

2010-04-14T00:31:15Z

~~The asymptotics for groups are strictly speaking still open, since extensions of nonsolvable groups are apparently rather thorny.~~ Edit:It seems my information is somewhat out of date (see Milne's answer). I'm not sure how bad the $o(1)$ can be.

It is expected that 2-groups dominate by a lot, although one could reasonably argue that the numerical evidence gathered to date samples the very small end of the nonsolvable family. By a 1965 result of Higman and Sims, the number of isomorphism types of groups of order $2^n$ (and conjecturally, groups of order at most $2^n$) grows as $2^{\frac{2}{27}n^3 + O(n^{8/3})}$.

In other words, your function $G(n)$ grows very roughly like $2^{\frac{2}{27}(\log_2 n)^3}$ . More specifically, $\overline{\operatorname{lim}} \, \frac{\log G(n)}{(\log_2 n)^3} = 2/27$ .

Addendum: I did a bit of GAP computation following Brian Conrad's comment. If we weight by dividing by the order of the automorphism group, none of the orders up to 70 contribute more than 1 (including 64, which contributes 48611383/78744960), and the average contribution from non-highly-divisible orders drops pretty quickly. The cumulative sums by 10s are roughly: 0, 5.3, 7.5, 8.9, 10.3, 11.4, 12.1, 13.1. Due to the jumpiness, I can only say that the growth looks very sub-linear. Given the growth rate of isomorphism types, I suspect we'll eventually get an explosion of mass for large powers of two even with the weighting.

Answer by Kevin O'Bryant for 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.?

2010-04-14T00:55:42Z

The number of finite abelian groups (Sloane A000688) is a multiplicative function, so the asymptotics are known.

Answer by JS Milne for 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.?

2010-04-14T01:37:38Z

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.

Answer by Richard Stanley for 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.?

2010-04-14T01:50:46Z

For groups there is the book Enumeration of Finite Groups by Simon R. Blackburn, Peter M. Neumann, and Geetha Venkataraman.

Answer by Gerhard Paseman for 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.?

2010-04-14T05:24:24Z

In a more general vein, spectra of equational classes have been studied by Ralph McKenzie and others. A jumping off point is his "Locally finite varieties with large free spectra" .

I believe his work on tame congruence theory shed some light on the growth rates for certain classes of finite algebras.

Gerhard "Ask Me About System Design" Paseman, 2010.04.13