Tuesday, June 21, 2016

Burnside Lemma

Group theory is formal study for analyzing systems and processes that have symmetry and structure. When an operation is performed on some element, it preserves some structure. Many surprising patterns and discoveries can be made about such symmetries and structures.

Groups are applicable in fields like polynomial equations, polymer structures, topology, number theory, probability, quantum physics and combinatorics. Cauchy, Galois, Cayley, Frobenius, Polya, de Brujin, Redfield and and other several mathematicians contributed to field, but Burnside collected all research and publicized it in his book Theory of groups of finite order in addition to his own contributions to the field.

Group is mathematical abstraction that consists of a set of elements and an operation that satisfies certain properties on the given set. Set of integers with addition form a group. The theory will be more beautiful in dealing with sets of finite order and their symmetry. Set of rotations of rubic cube with combining operation form a group. Symmetry group or permutation group is group whose set is set of transformations like rotation, reflection and moving of an object and whose operation is composition of transformations.

Burnside lemma is a result in group theory that says the number of orbits of input set operated under a group of transformations is equal to the average number of points fixed by the transformations of that symmetry group. It is used to count distinct possible objects or configurations considering the symmetry of objects.

Each possible configuration is an input point. Orbit of a point is set of all possible points possible by applying a transformation of group. Orbits are subset of all points. All elements of orbit share the orbit. Orbits do not overlap and they partition the set of input configurations. Fixed points of a transformation are unchanged points after applying it. Many points may be identical and are simply few transformation away from other points and are so become one orbit. The number of orbits are the number of distinct possible objects or configurations.

Example: Counting the number of bracelets with total four beads of two colors. Two bracelets are considered same if they look identical after some rotation or flipping. There are eight symmetries.
  • No movement will keep all sixteen bracelets intact.
  • Two bracelets do not change after rotation by one bead.
  • Four of them do not change to original after rotation by two beads.
  • Two of them do not change to original after rotation by three beads.
  • Four of them do not change after horizontal flip.
  • Four of them do not change after vertical flip.
  • Eight of them do not change after clockwise diagonal shift.
  • Eight of them do not change after anticlockwise diagonal shift.
  • Total fixed bracelets is  48, that is 16 + 2 + 4 + 2 + 4 + 4 + 8 + 8.
  • Total distinct number of bracelets is 48/8 or six.

No comments: