A beautiful formula

This month, a beautiful formula on an old door panel in Prague. (It may not be very legible in this low-resolution copy.) The formula is for l(Sn), the length of the longest chain of subgroups in the symmetric group Sn. The formula is, you increase n by 50%, rounding up if necessary; subtract the number of ones in the base 2 representation of n, and subtract another 1. Beautiful, because unexpected (I would not have anticipated a general formula for this number) and surprising (the occurrence of the base 2 representation of n hints at the method of constructing such chains, by writing n in base 2 and descending to a direct product of symmetric groups of 2-power degree).

I found this in the early 1980s; Ron Solomon and Alex Turull found it independently, and we joined forces to publish it.

A generalisation to semigroups is discussed here.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , . Bookmark the permalink.

1 Response to June

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.