maths.free › Abstract Algebra › 14. Group Actions › Burnside's Counting Theorem

Burnside's Counting Theorem

Suppose that we wish to color the vertices of a square with two different colors, say black and white. We might suspect that there would be 2^4=16 different colorings. However, some of these colorings are equivalent.

Burnside's Counting Theorem

Suppose that we wish to color the vertices of a square with two different colors, say black and white. We might suspect that there would be \(2^4=16\) different colorings. However, some of these colorings are equivalent. If we color the first vertex black and the remaining vertices white, it is the same as coloring the second vertex black and the remaining ones white since we could obtain the second coloring simply by rotating the square \(90^\circ\) ().

Burnside's Counting Theorem offers a method of computing the number of distinguishable ways in which something can be done. In addition to its geometric applications, the theorem has interesting applications to areas in switching theory and chemistry. The proof of Burnside's Counting Theorem depends on the following lemma.

Lemma

Let \(X\) be a \(G\)-set and suppose that \(x \sim y\). Then \(G_x\) is isomorphic to \(G_y\). In particular, \(|G_x| = |G_y|\).

Proof

Let \(G\) act on \(X\) by \((g,x) \mapsto g \cdot x\). Since \(x \sim y\), there exists a \(g \in G\) such that \(g \cdot x=y\). Let \(a \in G_x\). Since \[\begin{aligned}\end{aligned}\], we can define a map \(\phi: G_x \rightarrow G_y\) by \(\phi(a) = gag^{-1}\). The map \(\phi\) is a homomorphism since \[\begin{aligned}\end{aligned}\]. Suppose that \(\phi(a) = \phi(b)\). Then \(gag^{-1}= gbg^{-1}\) or \(a=b\); hence, the map is injective. To show that \(\phi\) is onto, let \(b\) be in \(G_y\); then \(g^{-1}bg\) is in \(G_x\) since \[\begin{aligned}\end{aligned}\] and \(\phi(g^{-1}bg ) = b\).

Theorem: Burnside

Let \(G\) be a finite group acting on a set \(X\) and let \(k\) denote the number of orbits of \(X\). Then \[\begin{aligned}\end{aligned}\].

Proof

We look at all the fixed points \(x\) of all the elements in \(g \in G\); that is, we look at all \(g\)'s and all \(x\)'s such that \(gx =x\). If viewed in terms of fixed point sets, the number of all \(g\)'s fixing \(x\)'s is \[\begin{aligned}\end{aligned}\]. However, if viewed in terms of the stabilizer subgroups, this number is \[\begin{aligned}\end{aligned}\] hence, \(\sum_{g \in G} |X_g| = \sum_{x \in X} |G_x|\). By , \[\begin{aligned}\end{aligned}\]. By and Lagrange's Theorem, this expression is equal to \(|G|\). Summing over all of the \(k\) distinct orbits, we conclude that \[\begin{aligned}\end{aligned}\].

Example

Let \(X = \{1, 2, 3, 4, 5 \}\) and suppose that \(G\) is the permutation group \(G= \{(1), (1 \, 3), (1 \, 3)(2 \, 5), (2 \, 5) \}\). The orbits of \(X\) are \(\{1, 3\}\), \(\{2, 5\}\), and \(\{4\}\). The fixed point sets are \[\begin{aligned}X_{(1)} & = X \\ X_{(1 \, 3)} & = \{2, 4, 5 \} \\ X_{(1 \, 3)(2 \, 5)} & = \{4\} \\ X_{(2 \, 5)} & = \{1, 3, 4 \}\end{aligned}\]. Burnside's Theorem says that \[\begin{aligned}\end{aligned}\].

A Geometric Example

Before we apply Burnside's Theorem to switching-theory problems, let us examine the number of ways in which the vertices of a square can be colored black or white. Notice that we can sometimes obtain equivalent colorings by simply applying a rigid motion to the square. For instance, as we have pointed out, if we color one of the vertices black and the remaining three white, it does not matter which vertex was colored black since a rotation will give an equivalent coloring.

Proposition

Let \(G\) be a permutation group of \(X\) and \(\widetilde{X}\) the set of functions from \(X\) to \(Y\). Then \(G\) induces a group \(\widetilde{G}\) that permutes the elements of \(\widetilde{X}\), where \(\widetilde{\sigma} \in \widetilde{G}\) is defined by \(\widetilde{\sigma}(f) = f \circ \sigma\) for \(\sigma \in G\) and \(f \in \widetilde{X}\). Furthermore, if \(n\) is the number of cycles in the cycle decomposition of \(\sigma\), then \(|\widetilde{X}_{\sigma}| = |Y|^n\).

Proof

Let \(\sigma \in G\) and \(f \in \widetilde{X}\). Since \(\sigma\) permutes the elements of \(X\), \(f \circ \sigma\) must also be in \(\widetilde{X}\). Suppose that \(g\) is another function from \(X\) to \(Y\) such that \(\widetilde{\sigma}(f) = \widetilde{\sigma}(g)\). Then for each \(x \in X\), \[\begin{aligned}\end{aligned}\]. Since \(\sigma\) is a permutation of \(X\), every element \(x'\) in \(X\) is the image of some \(x\) in \(X\) under \(\sigma\); hence, \(f\) and \(g\) agree on all elements of \(X\). Therefore, \(f=g\) and \(\widetilde{\sigma}\) is injective. The map \(\sigma \mapsto \widetilde{\sigma}\) is onto, since the two sets are the same size.

Suppose that \(\sigma\) is a permutation of \(X\) with cycle decomposition \(\sigma = \sigma_1 \sigma_2 \cdots \sigma_n\). Any \(f\) in \({\widetilde{X}}_{\sigma}\) must have the same value on each cycle of \(\sigma\). Since there are \(n\) cycles and \(|Y|\) possible values for each cycle, \(|{\widetilde{X}}_{\sigma}| = |Y|^n\).

Example

Let \(X = \{1, 2, \ldots, 7\}\) and suppose that \(Y = \{ A, B, C \}\). If \(g\) is the permutation of \(X\) given by \((1 \, 3)(2 \, 4 \, 5) = (1 \, 3)(2 \, 4 \, 5)(6)(7)\), then \(n = 4\). Any \(f \in \widetilde{X}_g\) must have the same value on each cycle in \(g\). There are \(|Y|=3\) such choices for any value, so \(|\widetilde{X}_g| = 3^4 = 81\).

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Switching Functions

In switching theory we are concerned with the design of electronic circuits with binary inputs and outputs. The simplest of these circuits is a switching function that has \(n\) inputs and a single output (). Large electronic circuits can often be constructed by combining smaller modules of this kind. The inherent problem here is that even for a simple circuit a large number of different switching functions can be constructed. With only four inputs and a single output, we can construct \(65{,}536\) different switching functions. However, we can often replace one switching function with another merely by permuting the input leads to the circuit ().

We define a switching or Boolean function of \(n\) variables to be a function from \({\mathbb Z}_2^n\) to \({\mathbb Z}_2\). Since any switching function can have two possible values for each binary \(n\)-tuple and there are \(2^n\) binary \(n\)-tuples, \(2^{2^n}\) switching functions are possible for \(n\) variables. In general, allowing permutations of the inputs greatly reduces the number of different kinds of modules that are needed to build a large circuit.

The possible switching functions with two input variables \(a\) and \(b\) are listed in . Two switching functions \(f\) and \(g\) are equivalent if \(g\) can be obtained from \(f\) by a permutation of the input variables. For example, \(g(a, b, c) = f(b, c, a)\). In this case \(g \sim f\) via the permutation \((a,c,b)\). In the case of switching functions of two variables, the permutation \((a,b)\) reduces 16 possible switching functions to 12 equivalent functions since \[\begin{aligned}f_2 & \sim f_4 \\ f_3 & \sim f_5 \\ f_{10} & \sim f_{12} \\ f_{11} & \sim f_{13}\end{aligned}\].

Inputs	Outputs
		\(f_0\)	\(f_1\)	\(f_2\)	\(f_3\)	\(f_4\)	\(f_5\)	\(f_6\)	\(f_7\)
\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)	\(0\)
\(0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)
\(1\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(0\)	\(0\)	\(1\)	\(1\)
\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)
Inputs	Outputs
		\(f_8\)	\(f_9\)	\(f_{10}\)	\(f_{11}\)	\(f_{12}\)	\(f_{13}\)	\(f_{14}\)	\(f_{15}\)
\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)	\(1\)
\(0\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(1\)	\(1\)
\(1\)	\(0\)	\(0\)	\(0\)	\(1\)	\(1\)	\(0\)	\(0\)	\(1\)	\(1\)
\(1\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)	\(0\)	\(1\)

For three input variables there are \(2^{2^3} = 256\) possible switching functions; in the case of four variables there are \(2^{2^4} =65{,}536\). The number of equivalence classes is too large to reasonably calculate directly. It is necessary to employ Burnside's Theorem.

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

Historical Note

William Burnside was born in London in 1852. He attended Cambridge University from 1871 to 1875 and won the Smith's Prize in his last year. After his graduation he lectured at Cambridge. He was made a member of the Royal Society in 1893. Burnside wrote approximately 150 papers on topics in applied mathematics, differential geometry, and probability, but his most famous contributions were in group theory. Several of Burnside's conjectures have stimulated research to this day. One such conjecture was that every group of odd order is solvable; that is, for a group \(G\) of odd order, there exists a sequence of subgroups \[\begin{aligned}\end{aligned}\] such that \(H_i\) is normal in \(H_{i+1}\) and \(H_{i+1} / H_i\) is abelian. This conjecture was finally proven by W. Feit and J. Thompson in 1963. Burnside's The Theory of Groups of Finite Order, published in 1897, was one of the first books to treat groups in a modern context as opposed to permutation groups. The second edition, published in 1911, is still a classic.

Symbols used here

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\sigma,\ s,\ \sigma^2

standard deviation, sample s.d., variance
Typical distance from the mean; its square.

imaginary unit
i² = −1.

^\circ

degrees
1/360 of a full turn. 180° = π radians.

\mathbb{N},\ \mathbb{Z},\ \mathbb{Q},\ \mathbb{R},\ \mathbb{C}

number sets
Naturals, integers, rationals, reals, complex numbers.

\blacksquare\ \text{or}\ \square

end of proof (halmos)
Marks the point where the statement has been established.

a \equiv b \pmod n

congruent modulo n
n divides a − b; a and b have the same remainder.

a \mid b,\ \gcd(a,b)

divides, greatest common divisor
b is a multiple of a; the largest number dividing both.

(G, \cdot),\ e,\ g^{-1}

group, identity, inverse
A set with an operation; the do-nothing element; the element that undoes g.

G \cong H,\ G / N

isomorphic, quotient group
Same structure; the group of cosets of a normal subgroup N.

\mathbb{Z}/n\mathbb{Z},\ \mathbb{Z}_n

integers modulo n
The remainders 0…n−1 with clock arithmetic.

\operatorname{Hom}(A, B),\ f \circ g

arrows from A to B, composition
The set of morphisms; do g then f.

Questions people ask

What is a group, in plain words?

A set with one operation that is associative, has an identity, and lets every element be undone. Symmetries of any object form a group — that is where the idea came from.

What is the difference between a ring and a field?

A ring has addition and multiplication that behave like the integers (you cannot always divide); a field is a ring where every non-zero element has a reciprocal, like the rationals or the reals.

ჲოთრაი ჟამ.

Parts of this page are adapted from Judson, Abstract Algebra: Theory and Applications (GFDL 1.3). Condensed and re-explained here; errors are ours.

მეტი Abstract Algebra

Groups Subgroups, cosets and Lagrange's theorem Cyclic groups and permutation groups Homomorphisms, normal subgroups and quotient groups Rings and fields Galois theory: why the quintic has no formula