Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

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 101024 = 2^{10}. A finite group is called a ‘22-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

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

as NN \to \infty?

Posted at November 28, 2012 8:47 PM UTC

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

30 Comments & 0 Trackbacks

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 GG has a weighting of 1/|Aut(G)|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

I guess the question might become more interesting if you remove the terminal object from consideration. This reminds me of the fact that when people discuss the homology of a lattice (e.g., a geometric lattice LL), they explicitly remove the bottom 00 and top 11 and consider the homology of the nerve of that, L{0,1}L \setminus \{0, 1\}. In the specific case of a geometric lattice, this becomes sort of interesting: there is one nontrivial homology group, and its rank is measured by μ(0,1)\mu(0, 1) where μ\mu is the Möbius function in the sense of Rota. I think there might be some material on this in Stanley’s Enumerative Combinatorics, but here is a sample paper that talks about this: link.

Posted by: Todd Trimble on August 19, 2015 2:46 AM | Permalink | Reply to this

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

Another example of a motivated removal of a terminal object that one may think about in this context is the category of fields: it has the zero ring as its only terminal object, and sometimes one is led to remove it, for example, in order to give a non-tautological example of a category whose every morphism is mono.

Posted by: Peter Heinig on May 30, 2017 6:38 PM | Permalink | Reply to this

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

Are there really people who consider the zero ring to be a field?

Posted by: Mike Shulman on May 30, 2017 8:46 PM | Permalink | Reply to this

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

How many people are Alain Connes?

(-;

Posted by: Jesse C. McKeown on May 30, 2017 8:50 PM | Permalink | Reply to this

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

that’s why I thought it would be funny … (not that there are many other rings “the ‘field’ with ‘one’ ‘element’” can be…)

Posted by: Jesse C. McKeown on May 31, 2017 6:47 AM | Permalink | Reply to this

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

The “field with one element” is not the zero ring…

Posted by: Mike Shulman on May 30, 2017 11:22 PM | Permalink | Reply to this

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

Yes, that might be interesting.

One difference between the category of groups and a lattice is that the top and bottom of a nontrivial lattice are never equal, whereas the terminal group is also the initial group. What made me think of this is the following general fact:

Let AA be a finite category, and write AA' for the category obtained from AA by freely adjoining an initial object 00 and a terminal object 11. Then χ(A)=μ A(0,1)+1 \chi(A) = \mu_{A'}(0, 1) + 1 where χ\chi is the Euler characteristic and μ A\mu_{A'} is the Möbius function of AA'.

This fact tells us that if we start with a lattice LL (=A= A'), remove its top and bottom, and calculate the Euler characteristic of the result, that’s the same as calculating the Möbius function of LL and evaluating at (0,1)(0, 1). (Well, “the same” up to a predictable shift by 11.)

The point? Well, to me, chopping off the top and bottom seems unnatural, even though I can see the pragmatic justification (“it’s boring if a top or bottom exist, so let’s get rid of them”). But calculating μ(0,1)\mu(0, 1) seems entirely natural.

This fact doesn’t apply here, because the initial and terminal objects of the category of groups of order 2000\leq 2000 are the same. But I wonder whether there’s a theorem of the following form:

Let AA be a finite category, and write AA' for the category obtained from AA by freely adjoining a zero object. Then χ(A)= \chi(A) = \ldots (where \ldots is something in terms of AA').

Posted by: Tom Leinster on August 19, 2015 2:29 PM | Permalink | Reply to this

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

Agreeing that “chopping off” the top and bottom is an odd expression, at the same time the map 2L2\to L is a terribly natural thing and … is there a good way to reinterpret the chopped result as a “relative” Euler Characteristic? In homotopy we talk of relative homology quite a lot.

Posted by: Jesse C. McKeown on August 19, 2015 7:51 PM | Permalink | Reply to this

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

Hmm, my last paragraph was misguided, because the category of groups is not formed by freely adjoining a zero object to the category of nontrivial groups.

Posted by: Tom Leinster on August 19, 2015 7:56 PM | 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 102^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)>10log_2 (2000) &gt; 10, but log 3(2000)<7log_3 (2000) &lt; 7 and log 5(2000)<5log_5 (2000) &lt; 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 NN, or to ask about (say) all groups with at most MM prime factors (with multiplicity) and each prime factor less than or equal to PP?

More simply, it would be interesting to compare the number of groups of order p kp^k for fixed kk and increasing prime pp. Does anyone happen to know the numbers of groups of order 3 n3^n, n6n \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 np^n for prime pp is

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

And, you can see a nice table of how many groups there are of orders 2000\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)O(n^{8/3}) depend on pp?

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

Surely, if you have some small finite number of morphisms, then some must be identities. You cannot have more objects than identities because they are equinumerous.

Posted by: Roger Joseph Witte on March 24, 2016 6:12 PM | 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

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

I apologize for my ignorance but isn’t that the same thing as counting finite graphs?

Posted by: i.a.o on August 18, 2015 8:40 AM | Permalink | Reply to this

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

No apology needed, but no, it’s not the same. Some graphs cannot be given a category structure. Some graphs can be given a category structure in exactly one way. Some graphs can be given a category structure in many ways.

Posted by: Tom Leinster on August 18, 2015 3:57 PM | Permalink | Reply to this

Post a New Comment