Burnside's Lemma, whose list of names is longer than the proof, says that the number of orbits of a permutation group is the average number of fixed points of its elements. It's a very elegant result, but I'm a bit disappointed by the fact that the examples given in the textbooks always amount to counting some colorings of a symmetric object, up to symmetry (the less original example probably being the cube). My question is then: do you know some funnier (but still rather direct) applications of this result?

  • 1
    $\begingroup$ You left out Redfield. $\endgroup$ – MJD Nov 9 '12 at 22:32
  • $\begingroup$ This MSE link has a nice application of Burnside to the enumeration of non-isomorphic binary structures on $N$ elememts as well as additional PET links. $\endgroup$ – Marko Riedel Jan 25 '14 at 23:09

Burnside's lemma can be used to prove the Polya enumeration theorem, which has many applications; see, for example, these two blog posts. The application to the symmetric groups alone is the well-known exponential formula in combinatorics, which has many applications; see this blog post.

It also has applications to representation theory. If $X$ is a set on which a group $G$ acts, then the free vector space on $X$ is a representation $V$ of $G$ with character $\text{Fix}(g)$. Burnside's lemma and the orthogonality relations then tell you that the dimension of the invariant subspace of $V$ is the number of orbits of the action of $G$ on $X$. They also tell you that if $V$ decomposes as a direct sum $\oplus n_k V_k$ where the $V_k$ are irreducible, then $\sum n_k^2$ is the number of orbits of $G$ acting on $X \times X$. In particular, if $G$ acts double transitively there are two such orbits, so $V$ is the sum of a trivial representation and an irreducible representation.

(This application to representation theory, in turn, has applications to graph theory. See this blog post.)

Edit: Here are some MO and math.SE answers where I have used Burnside's lemma:

I want to point out one of the applications I mention in one of the above blog posts which I think is particularly "funny": Fermat's little theorem! Consider the cyclic group of order $p$ acting on the set of strings of length $p$ from an alphabet of size $a$. By Burnside's lemma the total number of orbits is

$$\frac{1}{p} \left( a^p + (p-1)a \right)$$

since there is one element which fixes every string and $p-1$ elements which only fix strings which repeat one letter $p$ times. The integrality of this number is equivalent to Fermat's little theorem. (For a generalization, see these two blog posts.)


Yes, there are many more funny applications, for sure, here are three of them:

  1. You can apply it in order to compute the sum of reciprocals of cardinals all all endomorphisms of a vector space of dimension $n$ over some field with $p$ elements ($p$ a prime).

  2. You can apply it in order to characterize those finite groups that have an abelian automorphism group.

  3. It can be applied in order to (pun intended!) calculate the multiplicative order of some $u$ such that $u$ is co-prime to a given $n$ (that is, to calculate the smallest $k$ such that $n$ divides $u^k-1$).

I share with you the disappointment: this is such a general thing that it is only conceivable that the range of applications is bounded only by the imagination of the user...

  • 2
    $\begingroup$ This is too vague to be of use. $\endgroup$ – Phira Nov 15 '12 at 18:52

You can use it to count the number of isomorphism classes of representations of a quiver over a finite field; Burnside's lemma was used for this purpose by Kac and Stanley (see Root Systems, Representations of Quivers and Invariant Theory by Victor G. Kac).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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