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

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בתורת החבורות, הלמה של ברנסייד (הידועה גם כלמת הספירה) היא תוצאה המתקבלת מפעולה של חבורה על קבוצה. הלמה שימושית ביותר כאשר סופרים אובייקטים מתמטים בעלי סימטריה. הלמה קרוייה על שם המתמטיקאי האנגלי ויליאם ברנסייד, אף כי לא הוא גילה אותה לראשונה. ברנסייד פרסם את הלמה עם הוכחה בשנת 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}$ .

[עריכה] דוגמה

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

נניח כי אנו רוצים ליצור תעודות זהות מכרטיסי פלסטיק המחולקים ל-9 חלקים, כאשר בכל חלק ניתן לנקב חור. אנו רוצים לדעת כמה כרטיסים שונים ניתן ליצור: יש לשים לב כי שני כרטיסים הם שונים אם הם לא סיבוב או שיקוף אחד של השני.

למעשה, אנו בוחנים את פעולת החבורה הדיהדרלית $\ D_4$ על קבוצת כל הכרטיסים האפשריים. שני כרטיסים הם שונים אם הם לא שייכים לאותו מסלול. לכן, אנו בעצם רוצים לספור את מספר המסלולים בקבוצה תחת פעולת החבורה.

החבורה $\ D_4$ מורכבת מ 8 איברים:

2 שיקופים סביב אלכסונים - נבדוק מה מספר האפשרויות לבניית כרטיס שלא ישתנה תחת שיקוף סביב האלכסון. כאשר נבחר אם לחורר ריבוע שלא נמצא על ציר השיקוף, נאלץ לבחור לחורר (או לא לחורר, בהתאם לבחירה) את הריבוע שנמצא במקום שאליו הוא ישוקף. כלומר, למרות שישנם 6 ריבועים שאינם על ציר השיקוף, למעשה ניתן לבצע רק 3 בחירות בלתי תלויות, ולכן ישנן $\ 2^3$ אפשרויות. בנוסף, על ציר השיקוף עצמו ניתן לבחור חורים כרצוננו, כלומר, עוד $\ 2^3$ אפשרויות. בסך הכל, קיימים $\ 2^3 \cdot 2^3= 2^6=64$ כרטיסים שלא משתנים תחת שיקוף סביב אלכסון מסוים.
2 שיקופים דרך אמצעי צלעות - באותה דרך בדיוק ניתן לראות כי ישנם בדיוק $2\cdot 2^6=128$ כרטיסים שלא משתנים תחת שיקוף דרך אמצע צלע.
2 סיבובים של 90° - בדרך דומה ניתן לראות כי יש $\ 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$

[עריכה] הוכחה

כאמור, נסתכל על חבורה $\ 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)|$ , כלומר