Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
mNo edit summary
No edit summary
 
(560 intermediate revisions by more than 100 users not shown)
Line 1: Line 1:
'''Burnside's lemma''', sometimes also called '''Burnside's counting theorem''', the '''Cauchy–Frobenius lemma''' or the '''orbit-counting theorem''', is a result in [[group theory]] which is often  useful in taking account of [[symmetry]] when counting mathematical objects.  Its various eponyms include [[William Burnside]], [[George Pólya]], [[Augustin Louis Cauchy]], and [[Ferdinand Georg Frobenius]]. The result is not due to Burnside himself, who merely quotes it in his book 'On the Theory of Groups of Finite Order', attributing it instead to {{harvtxt|Frobenius|1887}}.<ref>{{harvnb|Burnside|1897|loc=§119}}</ref>
This is a preview for the new '''MathML rendering mode''' (with SVG fallback), which is availble in production for registered users.


In the following, let ''G'' be a [[finite set|finite]] [[group (mathematics)|group]] that [[Group action|acts]] on a [[Set (mathematics)|set]] ''X''. For each ''g'' in ''G'' let ''X<sup>g</sup>'' denote the set of [[element (mathematics)|element]]s in ''X'' that are [[fixed point (mathematics)|fixed by]] ''g''. Burnside's lemma asserts the following formula for the number of [[orbit (group theory)|orbit]]s, denoted |''X''/''G''|:<ref>{{harvnb|Rotman|1995|loc=Chapter 3}}</ref>
If you would like use the '''MathML''' rendering mode, you need a wikipedia user account that can be registered here [[https://en.wikipedia.org/wiki/Special:UserLogin/signup]]
* Only registered users will be able to execute this rendering mode.
* Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.


:<math>|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|.</math>
Registered users will be able to choose between the following three rendering modes:  


Thus the number of orbits (a [[natural number]] or [[Extended real number line|+∞]]) is equal to the [[mean|average]] number of points fixed by an element of ''G'' (which is also a natural number or infinity). If ''G'' is infinite, the division by |''G''| may not be well-defined; in this case the following statement in [[cardinal arithmetic]] holds:
'''MathML'''
:<math forcemathmode="mathml">E=mc^2</math>


:<math>|G| |X/G| = \sum_{g \in G}|X^g|.</math>
<!--'''PNG'''  (currently default in production)
:<math forcemathmode="png">E=mc^2</math>


== Example application ==
'''source'''
The number of rotationally distinct colourings of the faces of a [[Cube (geometry)|cube]] using three colours can be determined from this formula as follows.
:<math forcemathmode="source">E=mc^2</math> -->


Let ''X'' be the set of 3<sup>6</sup> possible face colour combinations that can be applied to a cube in one particular orientation, and let the rotation group ''G'' of the cube act on ''X'' in the natural manner. Then two elements of ''X'' belong to the same orbit precisely when one is simply a rotation of the other. The number of rotationally distinct colourings is thus the same as the number of orbits and can be found by counting the sizes of the [[fixed set]]s for the 24 elements of ''G''.
<span style="color: red">Follow this [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering link] to change your Math rendering settings.</span> You can also add a [https://en.wikipedia.org/wiki/Special:Preferences#mw-prefsection-rendering-skin Custom CSS] to force the MathML/SVG rendering or select different font families. See [https://www.mediawiki.org/wiki/Extension:Math#CSS_for_the_MathML_with_SVG_fallback_mode these examples].


[[Image:Face colored cube.png|thumb|Cube with coloured faces]]
==Demos==
* one  identity element which leaves all 3<sup>6</sup> elements of ''X'' unchanged
* six  90-degree face rotations, each of which leaves 3<sup>3</sup> of the elements of ''X'' unchanged
* three  180-degree face rotations, each of which leaves 3<sup>4</sup> of the elements of ''X'' unchanged
* eight  120-degree vertex rotations, each of which leaves 3<sup>2</sup> of the elements of ''X'' unchanged
* six  180-degree edge rotations, each of which leaves 3<sup>3</sup> of the elements of ''X'' unchanged


A detailed examination of these automorphisms may be found
Here are some [https://commons.wikimedia.org/w/index.php?title=Special:ListFiles/Frederic.wang demos]:
[[Cycle index#The cycle index of the face permutations of a cube|here]].


The average fix size is thus


: <math> \frac{1}{24}\left(3^6+6\cdot 3^3 + 3 \cdot 3^4 + 8 \cdot 3^2 + 6 \cdot 3^3 \right) = 57. </math>
* accessibility:
** Safari + VoiceOver: [https://commons.wikimedia.org/wiki/File:VoiceOver-Mac-Safari.ogv video only], [[File:Voiceover-mathml-example-1.wav|thumb|Voiceover-mathml-example-1]], [[File:Voiceover-mathml-example-2.wav|thumb|Voiceover-mathml-example-2]], [[File:Voiceover-mathml-example-3.wav|thumb|Voiceover-mathml-example-3]], [[File:Voiceover-mathml-example-4.wav|thumb|Voiceover-mathml-example-4]], [[File:Voiceover-mathml-example-5.wav|thumb|Voiceover-mathml-example-5]], [[File:Voiceover-mathml-example-6.wav|thumb|Voiceover-mathml-example-6]], [[File:Voiceover-mathml-example-7.wav|thumb|Voiceover-mathml-example-7]]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Audio-Windows7-InternetExplorer.ogg Internet Explorer + MathPlayer (audio)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-SynchronizedHighlighting-WIndows7-InternetExplorer.png Internet Explorer + MathPlayer (synchronized highlighting)]
** [https://commons.wikimedia.org/wiki/File:MathPlayer-Braille-Windows7-InternetExplorer.png Internet Explorer + MathPlayer (braille)]
** NVDA+MathPlayer: [[File:Nvda-mathml-example-1.wav|thumb|Nvda-mathml-example-1]], [[File:Nvda-mathml-example-2.wav|thumb|Nvda-mathml-example-2]], [[File:Nvda-mathml-example-3.wav|thumb|Nvda-mathml-example-3]], [[File:Nvda-mathml-example-4.wav|thumb|Nvda-mathml-example-4]], [[File:Nvda-mathml-example-5.wav|thumb|Nvda-mathml-example-5]], [[File:Nvda-mathml-example-6.wav|thumb|Nvda-mathml-example-6]], [[File:Nvda-mathml-example-7.wav|thumb|Nvda-mathml-example-7]].
** Orca: There is ongoing work, but no support at all at the moment [[File:Orca-mathml-example-1.wav|thumb|Orca-mathml-example-1]], [[File:Orca-mathml-example-2.wav|thumb|Orca-mathml-example-2]], [[File:Orca-mathml-example-3.wav|thumb|Orca-mathml-example-3]], [[File:Orca-mathml-example-4.wav|thumb|Orca-mathml-example-4]], [[File:Orca-mathml-example-5.wav|thumb|Orca-mathml-example-5]], [[File:Orca-mathml-example-6.wav|thumb|Orca-mathml-example-6]], [[File:Orca-mathml-example-7.wav|thumb|Orca-mathml-example-7]].
** From our testing, ChromeVox and JAWS are not able to read the formulas generated by the MathML mode.


Hence there are 57 rotationally distinct colourings of the faces of a cube in three colours. In general, the number of rotationally distinct colorings of the faces of a cube in ''n'' colors is given by
==Test pages ==


: <math> \frac{1}{24}\left(n^6+3n^4 + 12n^3 + 8n^2\right). </math>
To test the '''MathML''', '''PNG''', and '''source''' rendering modes, please go to one of the following test pages:
*[[Displaystyle]]
*[[MathAxisAlignment]]
*[[Styling]]
*[[Linebreaking]]
*[[Unique Ids]]
*[[Help:Formula]]


== Proof ==
*[[Inputtypes|Inputtypes (private Wikis only)]]
 
*[[Url2Image|Url2Image (private Wikis only)]]
The first step in the proof of the lemma is to re-express the sum over the group elements ''g''&nbsp;∈&nbsp;''G'' as an equivalent sum over the set elements ''x''&nbsp;∈&nbsp;''X'':
==Bug reporting==
 
If you find any bugs, please report them at [https://bugzilla.wikimedia.org/enter_bug.cgi?product=MediaWiki%20extensions&component=Math&version=master&short_desc=Math-preview%20rendering%20problem Bugzilla], or write an email to math_bugs (at) ckurs (dot) de .
:<math>\sum_{g \in G}|X^g| = |\{(g,x)\in G\times X \mid g.x = x\}| = \sum_{x \in X} |G_x|.</math>
 
(Here ''X<sup>g</sup>''&nbsp;=&nbsp;{''x''&nbsp;∈&nbsp;''X''&nbsp;|&nbsp;''g.x''&nbsp;=&nbsp;''x''} is the subset of all points of ''X'' fixed by ''g''&nbsp;∈&nbsp;''G'', whereas ''G<sub>x</sub>''&nbsp;=&nbsp;{''g''&nbsp;∈&nbsp;''G''&nbsp;|&nbsp;''g.x''&nbsp;=&nbsp;''x''} is the [[Orbit-stabilizer theorem#Orbits and stabilizers|stabilizer subgroup]] of G that fixes the point ''x''&nbsp;∈&nbsp;''X''.)
 
The [[Orbit-stabilizer theorem#Orbits and stabilizers|orbit-stabilizer theorem]] says that there is a natural [[bijection]] for each ''x''&nbsp;∈&nbsp;''X'' between the orbit of ''x'', ''G.x''&nbsp;=&nbsp;{''g.x''&nbsp;|&nbsp;''g''&nbsp;∈&nbsp;''G''}&nbsp;⊆&nbsp;''X'', and the set of left cosets ''G/G<sub>x</sub>'' of its stabilizer subgroup ''G<sub>x</sub>''. With [[Lagrange's theorem (group theory)|Lagrange's theorem]] this implies
 
:<math>|G.x| = [G\,:\,G_x] = |G| / |G_x|.</math>
 
Our sum over the set ''X'' may therefore be rewritten as
 
:<math>\sum_{x \in X} |G_x| = \sum_{x \in X} \frac{|G|}{|G. x|} = |G| \sum_{x \in X}\frac{1}{|G. x|}.</math>
 
Finally, notice that ''X'' is the disjoint union of all its orbits in ''X/G'', which means the sum over ''X'' may be broken up into separate sums over each individual orbit.
 
:<math>\sum_{x \in X}\frac{1}{|G. x|} = \sum_{A\in X/G} \sum_{x\in A} \frac{1}{|A|} = \sum_{A\in X/G} 1 = |X/G|.</math>
 
Putting everything together gives the desired result:
 
:<math>\sum_{g \in G}|X^g| = |G| \cdot |X/G|.</math>
 
==History: the lemma that is not Burnside's==
[[William Burnside]] stated and proved this lemma, attributing it to {{harvnb|Frobenius|1887}} in his 1897 book on finite groups.  But, even prior to Frobenius, the formula was known to [[Cauchy]] in 1845. In fact, the lemma was apparently so well known that Burnside simply omitted to attribute it to Cauchy. Consequently, this lemma is sometimes referred to as '''the lemma that is not Burnside's'''.<ref>{{harvnb|Neumann|1979}}</ref> (see also [[Stigler's law of eponymy]]). This is less ambiguous than it may seem: Burnside contributed many lemmas to this field.
 
== See also ==
* [[Pólya enumeration theorem]]
 
==Notes==
{{reflist}}
 
== References ==
*Burnside, William (1897) ''[http://www.gutenberg.org/ebooks/40395 Theory of Groups of Finite Order]'', [[Cambridge University Press]], at [[Project Gutenberg]] and [https://archive.org/details/theorygroupsfin00burngoog here] at [[Archive.org]].  (This is the first edition; the introduction to the second edition contains Burnside's famous ''volte face'' regarding the utility of [[representation theory]].)
* {{citation | last=Frobenius |first=Ferdinand Georg |authorlink=Ferdinand Georg Frobenius |title=Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul |journal=Crelle |volume=CI |year=1887 |page=288}}.
* {{Citation | last1=Neumann | first1=Peter M. | author1-link=Peter M. Neumann | title=A lemma that is not Burnside's | mr=562002 | year=1979 | journal=The Mathematical Scientist | issn=0312-3685 | volume=4 | issue=2 | pages=133–141}}.
* {{citation | last=Rotman |first=Joseph |title=An introduction to the theory of groups |publisher=Springer-Verlag |year=1995 |isbn=0-387-94285-8}}.
 
[[Category:Lemmas]]
[[Category:Group theory]]

Latest revision as of 23:52, 15 September 2019

This is a preview for the new MathML rendering mode (with SVG fallback), which is availble in production for registered users.

If you would like use the MathML rendering mode, you need a wikipedia user account that can be registered here [[1]]

  • Only registered users will be able to execute this rendering mode.
  • Note: you need not enter a email address (nor any other private information). Please do not use a password that you use elsewhere.

Registered users will be able to choose between the following three rendering modes:

MathML


Follow this link to change your Math rendering settings. You can also add a Custom CSS to force the MathML/SVG rendering or select different font families. See these examples.

Demos

Here are some demos:


Test pages

To test the MathML, PNG, and source rendering modes, please go to one of the following test pages:

Bug reporting

If you find any bugs, please report them at Bugzilla, or write an email to math_bugs (at) ckurs (dot) de .

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=329754"