הלמה של ברנסייד

בתורת החבורות, הלמה של ברנסייד (הידועה גם כלמת הספירה או כמשפט קושי-פרובניוס) היא תוצאה המתקבלת מפעולה של חבורה על קבוצה. הלמה שימושית ביותר כאשר סופרים אובייקטים מתמטיים בעלי סימטריה.

הלמה נקראת על שם המתמטיקאי האנגלי ויליאם ברנסייד, אף כי לא הוא גילה אותה לראשונה. ברנסייד פרסם את הלמה עם הוכחה בשנת 1897, אף כי ידוע כי הלמה הייתה מוכרת לקושי עוד ב-1845. למעשה, מקובל להניח כי הלמה הייתה ידועה כל כך, עד כי ברנסייד לא טרח לציין כי קושי הוכיח אותה לפניו.

תוצאה של הלמה (שנובעת מיידית מניסוחה) היא כי לתמורות על מספר סופי של איברים יש בממוצע נקודת שבת אחת.

ניסוח הלמה

תהי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} חבורה סופית הפועלת על קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} . נסמן הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Server problem."): {\displaystyle {\text{Fix}}(g)=\{x\in X:g(x)=x\}} , כלומר קבוצת האיברים ש-$g$ משאיר במקום. אזי מספר המסלולים של הפעולה הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=\frac{1}{|G|}\sum_{g\,\in\,G}|\text{Fix}(g)|} כלומר מספר המסלולים הוא ממוצע גודלי ה-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Fix}} .

הוכחה

כאמור, נסתכל על חבורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} הפועלת על קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} . נרצה לחלק את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} למסלולים (זוהי חלוקה לקבוצות זרות), ולבדוק כמה תורם כל מסלול לסכימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{g\,\in\,G}|\text{Fix}(g)|} .

נסתכל על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in X} כלשהו. נסמן את גודל המייצב שלו הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m=|\text{stab}(x)|} , ונסתכל על כל הקבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Fix}(g)} . לפי הגדרה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} מופיע בדיוק ב-$m$ קבוצות כאלה. נשים לב גם כי לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle y} במסלול של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} מתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\text{stab}(x)|=|\text{stab}(y)|} . כיוון שגודל המסלול נתון על ידי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\text{Orb}(x)|=[G:\text{stab}(x)]=\frac{|G|}{m}} , ישנם בדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{|G|}{m}} איברים במסלול של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , שכל אחד מהם נמצא ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} קבוצות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Fix}(g)} . לכן, בסכימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sum_{g\,\in\,G}|\text{Fix}(g)|} כל מסלול תורם בדיוק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |G|} . לכן מתקבל $N\cdot |G|=\sum _{g\,\in \,G}|{\text{Fix}}(g)|$, כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=\frac{1}{|G|}\sum_{g\,\in\,G}|\text{Fix}(g)|} .

דוגמה

כרטיס לדוגמה. כרטיס זה לא ישתנה אם נשקף אותו סביב הציר האנכי, אך כן ישתנה אם נסובב אותו, או אם נשקף אותו דרך כל ציר אחר.

נניח כי אנו רוצים ליצור תעודות זהות מכרטיסי פלסטיק בני תשע משבצות, שבכל אחת מהן ניתן לנקב (או לא לנקב) חור. אנו רוצים לדעת כמה כרטיסים שונים ניתן ליצור, כאשר תבניות שאפשר להגיע אליהן באמצעות סיבובים או שיקופים יוצרות למעשה את אותו כרטיס.

הסיבובים והשיקופים יוצרים את החבורה הדיהדרלית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_4} , ולכן בוחנים את פעולת החבורה הזו על קבוצת כל תבניות-החורים האפשריות. יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{3\cdot3}=512} תבניות כאלה, ושתי תבניות יוצרות כרטיסים שונים רק אם הן לא שייכות לאותו מסלול. המטרה היא, אם כך, לספור את המסלולים בקבוצת התבניות תחת פעולת החבורה.

החבורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle D_4} מורכבת מ-8 איברים:

• 2 שיקופים סביב אלכסונים – נבדוק מה מספר האפשרויות לבניית כרטיס שלא ישתנה תחת שיקוף סביב האלכסון. לכל משבצת מחוץ לאלכסון יש משבצת מתאימה מן העבר השני של האלכסון, והחורים בשתיהן צריכים להתאים זה לזה. כלומר, אף על פי שישנם 6 משבצות מחוץ לציר השיקוף, יש רק 3 בחירות בלתי תלויות, שהן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^3} אפשרויות. בנוסף, על ציר השיקוף עצמו ניתן לבחור חורים כרצוננו, ואלו עוד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^3} אפשרויות. בסך הכל, קיימות הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^3\cdot2^3=2^6=64} תבניות שאינן משתנות תחת שיקוף סביב אלכסון מסוים.
• 2 שיקופים דרך אמצעי צלעות – מאותה סיבה, יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^6=64} תבניות שאינן משתנות תחת שיקוף דרך אמצע צלע.
• 2 סיבובים של 90° – כאן יש רק 3 בחירות בלתי תלויות, ולכן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^3=8} תבניות שאינן משתנות תחת סיבוב של 90°.
• סיבוב של 180° – כאן יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^5=32} תבניות שאינן משתנות תחת סיבוב של 180°.
• הזהות – תחת הזהות, כל הכרטיסים נשארים אותו דבר, כלומר - $\ 2^{9}=512$ כרטיסים.

סך הכול קיבלנו: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=\frac{1}{8}(\underbrace{2\cdot64}_{\rm diagonal}+\underbrace{2\cdot64}_{\rm middle}+\underbrace{2\cdot8}_{90^\circ}+\underbrace{1\cdot32}_{180^\circ}+\underbrace{1\cdot512}_{\rm Id})=102} , כלומר 102 כרטיסים שונים.

קישורים חיצוניים

• הלמה של ברנסייד ב planetmath
• הלמה של ברנסייד, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

הלמה של ברנסייד39173262