Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
7  
From OEIS: Number of groups of order n: research.att.com/~njas/sequences/A000001 –  Joel David Hamkins Apr 13 '10 at 22:08
1  
For graphs, see research.att.com/~njas/sequences/A000088 . –  Qiaochu Yuan Apr 13 '10 at 22:43
8  
"Most finite groups are 2-groups", so G(n) will be a very bumpy function. I almost want to say that it's not advisable to try and approximate it by some "simple" function like x^alpha or e^(x^alpha). To give an example: there are 11759892 groups of order at most 1023, and 49487365422 of order 1024: this is about 4000 times bigger! The number of groups of size p^e is about p^((2/27)e^3 and presumably the p=2 terms dominate. This should be enough information to see how G(n) is growing. –  Kevin Buzzard Apr 14 '10 at 0:10
8  
Wouldn't it make a lot more sense to weight things by the size of their automorphism group? (I know, it's not the same question, but is quite natural, and may have a chance at being less "bumpy".) I wonder if anyone has attacked it. Certainly for the count of finite extensions of a $p$-adic field, the answer is much more elegant with such weighting factors. –  BCnrd Apr 14 '10 at 0:29
3  
Brian, that is a very interesting question (and it reminds me of the nice enumeration of ss elliptic curves). There aren't any orders less than 16 with more than one weighted group, and I'm unwilling to work out more by hand. –  S. Carnahan Apr 14 '10 at 0:40
show 7 more comments

9 Answers

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.

share|improve this answer
    
The exact formula for fields is $F(n) = \pi(n)+\pi(n^{1/2})+\pi(n^{1/3})+\cdots$ which is about $n/\log(n)$. –  François G. Dorais Apr 13 '10 at 23:27
add comment

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
share|improve this answer
add comment

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.

share|improve this answer
add comment

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)$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
Mathworld gives the asymptotic formula A(n) ~ 2.3n (eqn. 4) mathworld.wolfram.com/AbelianGroup.html –  François G. Dorais Apr 14 '10 at 1:03
1  
Just to clarify (for those who were perplexed, like me): A(n) is the number of abelian groups of order at most n, not of order exactly n. That is, on average there are 2.3 abelian groups of a given order. (I'm marginally surprised this turns out to be finite.) The constant ~2.3 is the product zeta(2)*zeta(3)*zeta(4)*... –  Michael Lugo Apr 14 '10 at 1:17
    
Here's an article with more precise information: emis.de/journals/PIMB/088/n088p057.ps.gz –  Kevin O'Bryant Apr 14 '10 at 1:51
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
If this account could comment on questions, it would suggest a "general-algebra" tag for this question. –  Gerhard Paseman Apr 14 '10 at 5:28
    
Thanks for the answer and the suggestion. Unfortunately, MO limits us to five tags per question. –  Joel David Hamkins Apr 14 '10 at 13:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.