When two descriptions represent one object
A circular arrangement has no privileged starting position. For instance, rotating a four-bit ring can change its written string while leaving the same circular arrangement. Counting strings and then dividing by four is tempting, but different arrangements can have different numbers of distinct rotations. We will count equivalence classes exactly rather than assume that every class has the same size.
Definition 1.2.1
(Group action, orbit, stabilizer and fixed set)
Let be a finite group and a finite set. acts on when each transforms every into an element , the identity leaves every configuration unchanged, and : applying two transformations in sequence agrees with their group product.
- The orbit of is . Orbits partition ; configurations in one orbit represent the same object under the declared symmetries.
- The stabilizer of is , the transformations that leave this one configuration unchanged.
- The fixed set of is , the configurations that this one transformation leaves unchanged.
Stabilizers are indexed by configurations and fixed sets by transformations; the proof below counts the same set of pairs in both ways. We first need the size relation between an orbit and a stabilizer.
Lemma 1.2.2
(Orbit size times stabilizer size)
For every ,
Proof
(Fibers of the map g to g acting on x)
Define by . It is onto by the definition of the orbit. Fix in the orbit and let . If , then , so lies in and . Conversely for every . Hence the fiber equals . Multiplying on the left by is injective, so every fiber has exactly elements. The fibers partition , so .
Theorem 1.2.3
(Fixed-point average)
The number of orbits is
Proof
(Counting the pairs fixed by a transformation)
Let . Counting by gives . Counting by gives . Group the second sum by orbits. For an orbit and any the lemma gives , so the elements of together contribute pairs. The orbits partition , so . Dividing by gives the formula; if is empty, both sides are zero.
Double-counting the same pairs
The proof never needs to know individual stabilizers. It only needs the fact that, orbit by orbit, the pairs add up to the same number.
Proof X-ray
Why the average counts orbits
The key move is to count twice: by transformation it is the quantity we can compute, and by configuration it splits over orbits. Each orbit contributes exactly pairs, however large or small its stabilizers are: big orbits have small stabilizers, small orbits have large ones, and the lemma makes the product constant. That constancy is what turns a sum of stabilizer sizes into a count of orbits.
Where the hypotheses enter: the inverse and the compatibility rule are used in the fiber computation. If transformations had no inverses, being in the same orbit would not be symmetric and orbits would not partition . Finiteness of lets us divide by , and finiteness of makes the sums finite. The argument closes because the orbits partition : once every orbit has contributed , the total is times the number of orbits. Without the lemma one would be left with and no way to evaluate it.
Four binary positions on a ring
Worked example 1.2.4
(Four rotations, six orbits)
Let be all four-bit strings and let contain rotations by positions. There are strings. The identity fixes all . A one-position rotation fixes only and ; a three-position rotation also fixes . A two-position rotation fixes strings, because positions opposite one another must agree. The number of rotation orbits is
One representative per orbit is . The actions here are rotations only: allowing reflections as well defines a different equivalence relation and requires a new fixed-point calculation.
Worked example 1.2.5
(Three rotations, four orbits)
Let be all three-bit strings and the rotations by positions, so and . The identity fixes all strings. A one-position rotation fixes a string exactly when its three bits are equal, so it fixes and only; the same holds for the two-position rotation. Therefore
Listing the orbits confirms this: , , , with sizes . The count is not an integer, so dividing by cannot be right here, whereas the average of fixed-point counts is.
Worked example 1.2.6
(A free action has no fixed points to correct)
Let be the four rotations and let be the positions of the ring, where the rotation by sends position to . The identity fixes all positions; every nonzero rotation fixes none, because forces . Then
There is one orbit: every position can be rotated to every other. Here every stabilizer is trivial, each orbit has elements, and gives the same answer. This is the special case in which the shortcut is valid.
Counterexample mode
Why dividing the number of strings fails
The naive calculation assumes every orbit has four members. But has one distinct rotation and has two, while has four. Orbit sizes vary because some configurations have nontrivial symmetries. The fixed-point average accounts for those stabilizers rather than treating all orbits as equal-sized.
Use and limits
The group and its action must be specified before counting: merely listing transformations without closure and inverses does not justify the proof. A fixed point is a configuration left unchanged by one particular transformation, not a configuration with no symmetries. The average is an integer because it counts orbits, even though individual fixed-point counts may vary.
If only the identity fixes any configuration, every stabilizer has size one and each orbit has size ; in that special case is valid. For a general action it need not be. The theorem counts equivalence classes; it does not automatically generate an efficient canonical representative for each class.
Concept lensAlgebraic
Orbits as invariant functions
Let act on the real-valued functions on by permuting their arguments. A function is unchanged by every exactly when it is constant on each orbit, so these invariant functions form a space whose dimension is the number of orbits. The operator projects onto that space, and the trace of a projection is its rank. Each acts as a permutation matrix with trace , so the trace is exactly the fixed-point average.
Common mistake
(Leaving out the identity or the wrong divisor)
The sum runs over every element of , including the identity, and the divisor is . For the four-bit ring, skipping the identity gives and dividing the full sum by gives ; neither is the number of orbits, which is . The identity usually contributes the largest term, .
Common mistake
(Adding reflections but keeping the divisor four)
Allowing reflections enlarges the group to elements, so the divisor must become . On four positions , the two reflections that fix two opposite positions each fix strings (two free positions and one swapped pair give three independent bits), and the two reflections that swap adjacent pairs each fix strings. The total is , and orbits. Reusing the divisor four would give , which is impossible: identifying more strings cannot produce more classes than the rotation classes.
Exercises
Quick check
(Count binary strings of length five up to rotation by the five rotations. List one representative per orbit.)
Which strings does a nonzero rotation fix when is prime?
Solution · Answer
The identity fixes strings. Each of the four nonzero rotations fixes a string only if all five bits are equal (a nonzero rotation of a length-five ring moves position through all five positions), so each fixes . The number of orbits is . Representatives are ; their orbit sizes add to .
Quick check
(For the four-bit ring, why does rotation by two positions fix exactly four strings?)
Write which positions are exchanged by the rotation.
Solution · Answer
The first and third positions must match, and the second and fourth must match. Each pair independently chooses a bit, giving strings.
Quick check
(In the four-bit example, compute the orbit sizes of , and .)
Apply all four rotations and count distinct results.
Solution · Answer
Their sizes are respectively : is unchanged; and alternate; are four distinct strings.
Quick check
(Why must adding reflections be treated as a new counting problem?)
Compare the acting group before and after.
Solution · Answer
Reflection can identify configurations that rotation alone does not, and the acting group and its fixed-point terms change. The rotation-only calculation does not include those transformations.