# Orbit-counting theorem

## Contents

## Name

This result is called the **orbit-counting theorem**, **orbit-counting lemma**, **Burnside's lemma**, **Burnside's counting theorem**, and the **Cauchy-Frobenius lemma**.

## Statement

### In terms of group actions

Suppose a finite group has a group action on a set . For , denote by the stabilizer of in . Let be the set of orbits in under the action of . Further, for , let be the set of elements of fixed by . Then:

.

### In terms of linear representations

Suppose a finite group has a permutation representation on a set . When viewed as a linear representation, this has character . Then, the number of orbits of under the action of is the inner product where is the trivial (principal) character of .

## Related facts

### Related facts about group actions

### Related counting techniques

- Polya's theorem is a more sophisticated version of this that involves a group acting on combinatorial configurations on a set.

### Related ideas in other disciplines

The formula of the orbit-counting theorem, which in this case counts the number of orbits, gives an effective measure of the *size* of a quotient of a set by a group action. This formula can be generalized to a groupoid acting on a set.

### Applications to conjugacy class-representation duality

The orbit-counting theorem has important applications to conjugacy class-representation duality. In particular, it is used to prove statements of the form *for a given Galois automorphism group or group automorphism group, the number of orbits on the set of conjugacy classes is the same as the number of orbits on the set of irreducible representations*. These statements hold even in cases where the actual orbit structures differ. (For cyclic groups of automorphisms/Galois automorphisms, the orbit structures must also coincide, by Brauer's permutation lemma).

Here are some applications:

- Number of irreducible representations over rationals equals number of equivalence classes under rational conjugacy
- Number of orbits of irreducible representations equals number of orbits of conjugacy classes under any subgroup of automorphism group, of which a special case is that number of orbits of irreducible representations equals number of orbits under automorphism group

## Facts used

## Proof

We first prove equality of the first two sides, and then prove equality of the second and third side.

### Equality of the first two sides

**Given**: A group acting on a set .

**To prove**: .

**Proof**:

No. | Assertion/construction | Facts used | Given data used | Previous steps used | Explanation |
---|---|---|---|---|---|

1 | For any orbit and any , we have | Fact (1) | acts on | Fact-direct | |

2 | For any orbit and any , we have | Fact (2) | Step (1) | [SHOW MORE] | |

3 | For any orbit and any , we have . | Step (2) | Algebraic rearrangement | ||

4 | For any orbit , we have | Step (3) | [SHOW MORE] | ||

5 | We get . | Step (4) | [SHOW MORE] | ||

6 | We get | Step (5) | Algebraic rearrangement |

### Equality of the second and third side

**To prove**: .

**Proof**: Note that we can ignore the on both sides for the proof. The proof essentially relies on the observation that both sides are equal to the cardinality of the set:

.

### Alternative interpretation/proof using linear representation theory

**PLACEHOLDER FOR INFORMATION TO BE FILLED IN**: [SHOW MORE]