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

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

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

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

ניסוח הלמה

תהי $G$ חבורה סופית הפועלת על קבוצה $X$. נסמן ${\text{Fix}}(g)=\{x\in X:g(x)=x\}$, כלומר קבוצת האיברים ש-$g$ משאיר במקום. אזי מספר המסלולים של הפעולה הוא

$$N={\frac {1}{|G|}}\sum _{g\,\in \,G}|{\text{Fix}}(g)|$$

כלומר מספר המסלולים הוא ממוצע גדלי ה-${\text{Fix}}$.

הוכחה

כאמור, נסתכל על חבורה $G$ הפועלת על קבוצה $X$. נרצה לחלק את $X$ למסלולים (זוהי חלוקה לקבוצות זרות), ולבדוק כמה תורם כל מסלול לסכימה $\sum _{g\,\in \,G}|{\text{Fix}}(g)|$.

נסתכל על $x\in X$ כלשהו. נסמן את גודל המייצב שלו $m=|{\text{stab}}(x)|$, ונסתכל על כל הקבוצות ${\text{Fix}}(g)$. לפי הגדרה, $x$ מופיע בדיוק ב-$m$ קבוצות כאלה. נשים לב גם כי לכל $y$ במסלול של $x$ מתקיים $|{\text{stab}}(x)|=|{\text{stab}}(y)|$. כיוון שגודל המסלול נתון על ידי $|{\text{Orb}}(x)|=[G:{\text{stab}}(x)]={\frac {|G|}{m}}$, ישנם בדיוק ${\frac {|G|}{m}}$ איברים במסלול של $x$, שכל אחד מהם נמצא ב-$m$ קבוצות ${\text{Fix}}(g)$. לכן, בסכימה $\sum _{g\,\in \,G}|{\text{Fix}}(g)|$ כל מסלול תורם בדיוק $|G|$. לכן מתקבל $N\cdot |G|=\sum _{g\,\in \,G}|{\text{Fix}}(g)|$, כלומר $N={\frac {1}{|G|}}\sum _{g\,\in \,G}|{\text{Fix}}(g)|$.

דוגמה

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

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

הסיבובים והשיקופים יוצרים את החבורה הדיהדרלית $D_{4}$, ולכן בוחנים את פעולת החבורה הזו על קבוצת כל תבניות-החורים האפשריות. יש $2^{3\cdot 3}=512$ תבניות כאלה, ושתי תבניות יוצרות כרטיסים שונים רק אם הן לא שייכות לאותו מסלול. המטרה היא, אם כך, לספור את המסלולים בקבוצת התבניות תחת פעולת החבורה.

החבורה $D_{4}$ מורכבת מ-8 איברים:

• 2 שיקופים סביב אלכסונים – נבדוק מה מספר האפשרויות לבניית כרטיס שלא ישתנה תחת שיקוף סביב האלכסון. לכל משבצת מחוץ לאלכסון יש משבצת מתאימה מן העבר השני של האלכסון, והחורים בשתיהן צריכים להתאים זה לזה. כלומר, אף על פי שישנם 6 משבצות מחוץ לציר השיקוף, יש רק 3 בחירות בלתי תלויות, שהן $2^{3}$ אפשרויות. בנוסף, על ציר השיקוף עצמו ניתן לבחור חורים כרצוננו, ואלו עוד $2^{3}$ אפשרויות. בסך הכל, קיימות $2^{3}\cdot 2^{3}=2^{6}=64$ תבניות שאינן משתנות תחת שיקוף סביב אלכסון מסוים.
• 2 שיקופים דרך אמצעי צלעות – מאותה סיבה, יש $2^{6}=64$ תבניות שאינן משתנות תחת שיקוף דרך אמצע צלע.
• 2 סיבובים של 90° – כאן יש רק 3 בחירות בלתי תלויות, ולכן $2^{3}=8$ תבניות שאינן משתנות תחת סיבוב של 90°.
• סיבוב של 180° – כאן יש $2^{5}=32$ תבניות שאינן משתנות תחת סיבוב של 180°.
• הזהות – תחת הזהות, כל הכרטיסים נשארים אותו דבר, כלומר - $\ 2^{9}=512$ כרטיסים.

סך הכול קיבלנו: $N={\frac {1}{8}}(\underbrace {2\cdot 64} _{\rm {diagonal}}+\underbrace {2\cdot 64} _{\rm {middle}}+\underbrace {2\cdot 8} _{90^{\circ }}+\underbrace {1\cdot 32} _{180^{\circ }}+\underbrace {1\cdot 512} _{\rm {Id}})=102$, כלומר 102 כרטיסים שונים.

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

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