Sunday, November 2, 2008

Burnside's lemma

The last TopCoder SRM (the problem statement is at http://www.topcoder.com/stat?c=problem_statement&pm=9975, but that requires a TopCoder account to view) has inspired me to write about a small and quite easy fact in group theory which I think was the most useful part of group theory for me in programming competitions.

It's called Burnside's lemma and says (citing from Wikipedia): let G be a finite group that acts on a set X. Then the number of orbits is equal to the average number of points fixed by an element of G. What does this all mean and how is this applicable to programming competitions? Let's continue with an example.

A standard problem that is best solved using Burnside's lemma is: consider a circular stripe of n cells. How many ways are there to color these cells with two colors, black and white, up to a rotation? Here, X is a set of all colored stripes (it has 2^n elements), and G is the group of its rotations (it has n elements: rotation by 0 cells, y 1 cell, by 2 cells, etc, by (n-1) cells), and an orbit is exactly the set of all stripes that can be obtained from each other using rotations, so the number of orbits will be the number of distinct stripes up to a rotation. Now let's apply the lemma, and find the number of stripes that are fixed by the rotation by K cells. If a stripe becomes itself after rotating by K cells, then its 1st cell must have the same color as its (1+K modulo n)-th cell, which is in turn the same as its (1+2K modulo n)-th cell, etc, until we get back to the 1st cell when m*K modulo n=0. One may notice that this will happen when m=n/gcd(K,n), and thus we get n/gcd(K,n) cells that must all be of the same color. Analogously, the same amount of cells must be of the same color starting with cell 2, (2+K modulo n), etc. Thus, all cells are separated into gcd(K,n) groups, with each group being of one color, and that yields us 2^gcd(K,n) choices. An by Burnside's lemma, the answer to the original problem is sum(2^gcd(K,n))/n, where the sum is taken over K from 0 to n-1.

That was rather complicated; here's a somewhat simpler example: Consider a square of 2n times 2n cells. How many ways are there to color it into X colors, up to rotations and/or reflections? Here, the group has only 8 elements (rotations by 0, 90, 180 and 270 degrees, reflections over two diagonals, over a vertical line and over a horizontal line). Every coloring stays itself after rotating by 0 degrees, so that rotation has X^(4n^2) fixed points. Rotation by 180 degrees and reflections over a horizonal/vertical line split all cells in pairs that must be of the same color for a coloring to be unaffected by such rotation/reflection, thus there exist X^(2n^2) such colorings for each of them. Rotations by 90 and 270 degrees split cells in groups of four, thus yielding X^(n^2) fixed colorings. Reflections over diagonals split cells into 2n groups of 1 (the diagonal itself) and (2n^2-n) groups of 2 (all remaining cells), thus yielding X^(2n^2-n+2n)=X^(2n^2+n) unaffected colorings. So, the answer is (X^(4n^2)+3*X^(2n^2)+2*X^(n^2)+2*X^(2n^2+n))/8.

I understand that this looks kind of too much formulas for too little gain, but once you get the hang of it, it becomes really simple and easy to use.

And as a plus, you get to verify that you haven't made a bug: the lemma has a division in the end (e.g., the division by 8 in the last formula). If that division produces a remainder, you've miscalculated somewhere. And chances are, if you have made a mistake, feeding the program random testcases will make the formula produce a remainder quite soon.

P.S. The Formula 1 GP at Interlagos starts in 20 minutes! I will be rooting for Massa to win the championship (I don't exactly know why - maybe because he's losing :)). The event is very likely to turn out quite exciting.

14 comments:

  1. Nice explanation, I was able to understand it. Cool lemma:)

    ReplyDelete
  2. Oh my god, what a race!

    ReplyDelete
  3. The ending was thrilling! Massa lost in the final 500 meters :(

    A brazilian

    ReplyDelete
  4. very informative :) its so much more fun to read your writeup than a textbook

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Petr,
    Massa almost won! Me and all my country (Brazil) went through a high level of emotion :)
    Next year, cheers for Massa.

    A second Brazilian.

    ReplyDelete
  7. This comment has been removed by the author.

    ReplyDelete
  8. The stripe problem was not easy to understand but I've spent about 30-40 min to get the things right. :)
    I just don't understand why the formula (sum(2^gcd(K,n))/n) works when we divide by n. I didn't understand why we have to divide by n (of course that, if we don't do it, the answer will very large but I mean what's the explanation that it works when we divide by n). (Very good problem)

    ReplyDelete
  9. Very good explanation and nice theorem, thank you.

    ReplyDelete
  10. Sorry, for the post on topic which was posted a year ago, but after reading it i want to have a clear understanding of it. so, my question is about "And by Burnside's lemma, the answer to the original problem is sum(2^gcd(K,n))/n, where the sum is taken over K from 0 to n-1."
    gcd(0,n) = ??, determine the value for me, please.

    ReplyDelete
    Replies
    1. Indeed, gcd(0, n) = n.
      We are finding the number of coloured circular stripes which when rotated 0 times, remain unchanged. When we take any coloured circular stripe, rotating 0 times it remains unchanged. So total is 2 ^ gcd(0, n) = 2 ^ n.

      Delete
    2. Sorry, I did not see that it had already been answered below. I will try to explain for case k = 2, to make it more clear.
      --------------------------
      Here, if gcd(2, n) = 2 (which means n is even). This means 1, 3, 5, 7, ..., n-1 are of one colour and 2, 4, 6, 8, ..., n are of another colour. So, total we get 2 ^ 2 = 4 stripes ( we have 2 colours, black and white).
      We can see that if we take any stripe out of these 4, and rotate them by 2 we always obtain same stripe.
      --------------------------
      Now take gcd(2, n) = 1 (n is odd). Here, 1, 3, 5, ..., n, 2, 4, ..., n-1 will be of same colour. So all will be of same colour. So total there and 2 ^ gcd(2, n) = 2 stripes.
      --------------------------
      This way we can take any k (as done here) and show that no. of stripes which remain unchanged will be 2 ^ gcd(k, n). (read the blog for that part). I hope its clear.

      Delete
  11. ah, nevermind, it seems that gcd(0,n)=gcd(n,n)=n (not sure about general case, but just for the particular task we have 2^n groups for 0-cells rotations)

    ReplyDelete
  12. Why did your solution fail for that problem?

    ReplyDelete