November 28, 2012

Almost All of the First 50 Billion Groups Have Order 1024

Posted by Tom Leinster

Here’s an incredible fact: of the 50 billion or so groups of order at most 2000, more than 99% have order 1024. This was announced here:

Hans Ulrich Besche, Bettina Eick, E.A. O’Brien, The groups of order at most 2000. Electronic Research Announcements of the American Mathematical Society 7 (2001), 1–4.

By no coincidence, the paper was submitted in the year 2000. The real advance was not that they had got up to order 2000, but that they had ‘developed practical algorithms to construct or enumerate the groups of a given order’.

I learned this amazing nugget from a recent MathOverflow answer of Ben Fairbairn.

You probably recognized that $1024 = 2^{10}$. A finite group is called a ‘$2$-group’ if the order of every element is a power of 2, or equivalently if the order of the group is a power of 2. So as Ben points out, what this computation suggests is that almost every finite group is a 2-group.

Does anyone know whether there are general results making this precise? Specifically, is it true that

$\frac{\text{number of 2-groups of order }   \leq N}{\text{number of groups of order }   \leq N} \to 1$

as $N \to \infty$?

Posted at November 28, 2012 8:47 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2575

Re: Almost All of the First 50 Billion Groups Have Order 1024

‘Some people’ think the right way to count objects in a category is with mass formulas, where each object $G$ has a weighting of $1/|\mathrm{Aut}(G)|$. I wonder how much this changes your stats.

Posted by: James Borger on November 28, 2012 10:37 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Good point. I haven’t a clue how this affects the answer.

Incidentally, I’d quibble with ‘some people’, since I think this is only the right way to count objects in a groupoid. On the other hand, my preferred way of counting objects in a category is in this case extremely uninteresting. Since the trivial group has order at most 2000 (a loose estimate, that), the category of groups of order at most 2000 has a terminal object. Hence the Euler characteristic of this category is 1.

Posted by: Tom Leinster on November 29, 2012 12:16 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

There was some discussion about this question on MathOverflow a while back, and in particular the question http://mathoverflow.net/questions/30459/ by T. Goodwillie. The best answer to the actual question seems to be R. Borcherds’, at http://mathoverflow.net/questions/30459/#35026, where the estimate is that dividing by automorphisms doesn’t much change the asymptotic count.

Posted by: Theo on November 29, 2012 4:31 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

I’d like to take this moment to advertise the (old) book “Groups of order 2^n, n \leq 6”.

Posted by: Allen Knutson on November 29, 2012 1:34 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Thanks, Allen. This book (1964) is by Marshall Hall Junior and James Kuhn Senior… which must have been causing amusement for decades.

According to the Zentralblatt review, there are 14 groups of order 16, 51 of order 32, and 267 of order 64.

Posted by: Tom Leinster on November 29, 2012 1:39 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

This isn’t surprising some how to me. 99% of all semigroups have a zero element and satisfy xyz=0. Conjecturally most of these have trivial automorphism groups and so even Jim’s solution of weighting doesn’t help. I think p-groups are the analog in group theory of nilpotent semigroups (in the above sense). It is generally believed that classification of p-groups up to isomorphism is essentially impossible. I would suspect most p-groups have small isomorphism groups, but I don’t know for sure.

Posted by: Benjamin Steinberg on November 29, 2012 2:08 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Is this just a property of small prime numbers? Of the small number of groups that are not 2-groups, do most of them have orders divisible by 6? (The link doesn’t resolve for me right now, so I can’t look at the announcement itself.) Or is there something special about “the oddest prime” other than that it’s the smallest one?

Posted by: Mike Shulman on November 29, 2012 4:06 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

According to Richard Borcherds (http://mathoverflow.net/questions/30459/#35026), the vast majority of groups that are no 2-groups have order 3 times a power of 2.

Posted by: Theo on November 29, 2012 4:34 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Ronald Solomon reported this back in 2001 here:

An ever-improving arsenal of computer algorithms for the identication of permutation groups, linear groups and more generally “black box” groups is being assembled by Kantor, Seress and many other researchers. In particular there is hope of determining all finite groups of order at most 2001 in the year 2001. On the other hand, calculation of groups of order $2^10$ has reconfirmed the long-known fact that “most” finite groups are nilpotent groups of nilpotence class at most 2 and they exist in frightening numbers.

I like what he goes on to say next, and quoted it partly in my book,

Thus the classication of all finite groups is completely infeasible. Nevertheless experience shows that most of the finite groups which occur “in nature”– in the broad sense not simply of chemistry and physics, but of number theory, topology, combinatorics, etc.– are “close” either to simple groups or to groups such as dihedral groups, Heisenberg groups, etc., which arise naturally in the study of simple groups. And so both the methodologies and the database of information generated in the course of the Classification Project remain of vital importance to the resolution of questions arising in other disciplines. (p. 347)

Posted by: David Corfield on November 29, 2012 12:40 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

I’m also unsurprised by the result. Anyone who’s spent some time in an algebra class classifying groups of small orders has noticed that the complexity increases a lot when the multiplicities of prime factors rises. Notably $log_2 (2000) > 10$, but $log_3 (2000) < 7$ and $log_5 (2000) < 5$.

Aside from the question of how it’s appropriate to weight groups, this raises the question about how one should order the orders. That is, does it make more sense to ask a question about all groups with order at most $N$, or to ask about (say) all groups with at most $M$ prime factors (with multiplicity) and each prime factor less than or equal to $P$?

More simply, it would be interesting to compare the number of groups of order $p^k$ for fixed $k$ and increasing prime $p$. Does anyone happen to know the numbers of groups of order $3^n$, $n \le 6$?

Posted by: Mark Meckes on November 29, 2012 4:12 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Cool! Turns out the number of groups of order $p^n$ for prime $p$ is

$p^{2n^3/27 + O(n^{8/3})}$

And, you can see a nice table of how many groups there are of orders $\le 2000$ here.

Posted by: John Baez on November 30, 2012 1:32 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Interesting. Does the constant in $O(n^{8/3})$ depend on $p$?

Posted by: Mark Meckes on November 30, 2012 3:12 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

I wonder if anyone’s done these counts for small finite categories.

Posted by: Jamie Vicary on December 4, 2012 6:39 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

I don’t know, but it’s a pretty fast-growing function. Ross Street told me that he once assigned the problem to his introduction to categories class of enumerating isomorphism (or maybe equivalence) types of categories with some small number of morphisms, maybe it was 4. Much to his surprise, there were thousands (as some students determined via computer). Just the number of monoids alone was some huge number, if memory of his story serves.

Posted by: Todd Trimble on December 4, 2012 11:16 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Given this post, maybe they should have looked at 5-morphism categories instead!

Posted by: Jamie Vicary on December 4, 2012 11:38 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Alas, no, for to any 4-arrow category we may freely adjoin an unrelated trivial object…

Posted by: Jesse C McKeown on December 5, 2012 1:37 AM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

Well, it may have been 4, may have been 5 – I really don’t recall the precise details. I found it kind of funny though! (At the end of the spectrum opposite to monoids, the number would also include all possible types of preorders with 4 or 5 elements, or the homeomorphism types of topological spaces with 4 or 5 elements. How many of those are there?)

Posted by: Todd Trimble on December 5, 2012 3:00 PM | Permalink | Reply to this

Re: Almost All of the First 50 Billion Groups Have Order 1024

I think it’s this sequence:

http://oeis.org/A125696

It doesn’t say so explicitly, buy this is up to isomorphism (at least that’s what I can check up to n = 4) and it goes into thousands for n = 6.

Posted by: Karol Szumiło on December 6, 2012 6:37 AM | Permalink | Reply to this

Post a New Comment