1
$\begingroup$

Recently I have questioned in here to understand the terms used for expressing Burnside's lemma $|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$. Someone explained the terms like the following way but I can not understand it.

Here a group $G$ acts on a set $X$. $X/G$ is the quotient of $X$ by $G$; that is, the set of orbits $\{G\cdot x\mid x\in X\}$, or equivalently the set of equivalence classes of $X$ where the equivalence relation is that $x\sim y$ if there is an element $g\in G$ so that $g\cdot x=y$. $X^g$ is the set of fixed points of a group element $g\in G$; i.e. $X^g=\{x\in X\mid g\cdot x=x\}$. So what the equation is saying that the umber of orbits is equal to the average number of fixed points.

I want to solve Necklace problem using Burnside's lemma .What do I need to do or know for intuitive understanding of Burnside's lemma and having capability to apply this lemma to solve the above problem?

$\endgroup$
  • $\begingroup$ A friendly suggestion from your friendly community moderator: Search the site. There are many examples with varying degrees of explanations. You also learn to use the site more efficiently - well worth your while for the future. $\endgroup$ – Jyrki Lahtonen Dec 29 '14 at 10:48
2
$\begingroup$

Consider a matrix whose columns are indexed by elements of $G$ and whose rows are indexed by elements of $X$ with the property that the entry $(g, x)$ of the matrix is either $1$ or $0$ depending on whether $g$ fixes $x$ or not.

Start with an element $x \in X.$ The sum of the elements of the row $x$ is equals to $|G_x|,$ the stabilizer of $x.$ Also for any $y \in G.x := \{gx | g \in G\},$ the sum of the elements of the row is $y$ is again $|G_y|,$ because $G_x$ and $G_y$ are conjugate. Now $|G/G_x| = |G.x| \Rightarrow$ the sum of all the row-sums, as $y$ varies over a fixed orbit, is $|G|$ and this is independent of orbits. But the orbits partitioned $X$ into disjoint subsets. So the sum of the all the entries of the matrix is $|G| \times r,$ where $r$ is the number of distinct orbits of $X.$

On the other hand, the sum of the elements of a column $g$ is clearly $|X^g|.$ So the sum of the column-sums is $\sum_{g \in G} |X^g|.$

$\endgroup$
1
$\begingroup$

I think first try to see that this sum equal to $1$ if there is only one orbit i.e the action is transitive.

Let the action is transitive, We need to show that

$$\sum_{g\in G}|X^g|=|G|$$.

Note that we are making oversume as $a$ can be element of both $X^{g_1}$ and $X^{g_2}$. How many times we oversum $a$ ?

Not surpsingly, $|Stab(a)|$ times. Since it is tru for every elements of $X$. Then the sum is equal to $|Stab(a)||X|=|G|$. Thus, we are done.

In general, the sum is equal to $|G|$ on every orbits then the result follows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.