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

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

ניסוח הלמה

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

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

כלומר - מספר המסלולים (שהוא תמיד מספר טבעי או אינסוף) הוא הממוצע של גדלי ה- $\ \operatorname {Fix}$ .

דוגמה

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

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

הסיבובים והשיקופים יוצרים את החבורה הדיהדרלית $\ 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} _{diagonal}+\underbrace {2\cdot 64} _{middle}+\underbrace {2\cdot 8} _{90^{\circ }}+\underbrace {1\cdot 32} _{180^{\circ }}+\underbrace {1\cdot 512} _{Id})=102$ , כלומר, 102 כרטיסים שונים.

הוכחה

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

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