פעולה של חבורה על קבוצה

מה זה בכלל

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

עוד מעט אני אתן כמה דוגמאות, אבל בואו נתחיל הפעם דווקא מההגדרה הכללית. ניקח חבורה \( G \) כלשהי וקבוצה \( X \) כלשהי. ייתכן ש-\( X \) היא בעצמה חבורה, או מרחב וקטורי, או המספרים הממשיים או כל דבר אחר שתרצו, אבל אני לא צריך להניח שום דבר מיוחד עליה. פעולה של \( G \) על \( X \) היא פונקציה \( G\times X\to X \), כלומר אנחנו לוקחים \( a\in G \) ו-\( x\in X \) ו”כופלים” אותם לקבלת איבר \( ax\in X \). כדי שתהיה משמעות כלשהי לכך ש-\( G \) היא חבורה, הפעולה צריכה איכשהו להתייחס למבנה הזה של חבורה. האינטואיציה, כאמור, לקוחה מהעולם שבו אברי החבורה הן תמורות של \( X \), ולכן אנחנו רוצים שהפעולה של \( G \) תתנהג כמו הרכבה: שיתקיים \( a\left(bx\right)=\left(ab\right)x \). במילים אחרות, שזה לא משנה אם קודם נפעיל את \( b \) על \( x \) ואז את \( a \) נפעיל על התוצאה, או שקודם כל נכפול את \( a,b \) ונקבל איבר חדש \( ab \) ואז אותו נפעיל על \( x \).

הדרישה הזו לבדה לא מספיקה - צריך איכשהו לערב את האספקטים הנוספים של חבורה, שהם קיום איבר יחידה וקיום הופכי. מסתבר שמספיק לדרוש דרישה על איבר היחידה כדי שהדרישה ה”טבעית” להופכי תבוא מאליה: אנחנו דורשים שאם \( e\in G \) הוא איבר היחידה של \( G \) אז \( ex=x \) לכל \( x\in X \). מכאן נובע ש-\( x=ex=\left(a^{-1}a\right)x=a^{-1}\left(ax\right) \), כלומר שהפעולה של \( a^{-1} \) על אברי \( X \) היא ההפך מהפעולה של \( a \) על אברי \( X \). כדי שזה יוכל לקרות, הפעולה של \( a \) על אברי \( X \) צריכה להיות פונקציה חח”ע ועל. פורמלית: קיימת תמורה \( \sigma_{a}\in S_{X} \) כך ש-\( \sigma_{a}\left(x\right)=ax \).

אם כן, ראינו שפעולה של \( G \) על \( X \) מגדירה לנו פונקציה \( a\mapsto\sigma_{a} \). מכיוון ש-\( ab\mapsto\sigma_{ab}=\sigma_{a}\sigma_{b} \) הפונקציה הזו היא הומומורפיזם. כלומר, “פעולה של \( G \) על \( X \)” זה שם מפוצץ ל”הומומורפיזם של \( G \) עם \( S_{X} \)”. אז למה בכלל לתת את השם המפוצץ הזה? פשוט כי יותר נוח להשתמש בו - יותר קל לומר “\( G \) פועלת על \( X \) באמצעות כך-וכך” מאשר להתחיל לדבר על הומומורפיזמים עם חבורות של תמורות וכדומה. הפואנטה העקרונית זהה ולא משנה מה הטרמינולוגיה שלנו - להסתכל על הומומורפיזמים שונים של \( G \) לתוך \( S_{X} \) זה מועיל ומעניין.

חבורה שפועלת על עצמה באמצעות כפל

בואו נתחיל מהדוגמה הבנאלית ביותר: אם \( G \) היא חבורה, אז היא פועלת על עצמה באמצעות כפל. כלומר, במקרה הזה \( X=G \) ו-\( a\cdot x \) זה פשוט לומר “נכפול את \( a \) ב-\( x \)”. התכונה הראשונה של פעולת חבורה, \( a\left(bx\right)=\left(ab\right)x \) היא פשוט תכונת האסוציאטיביות של כפל בחבורה; והתכונה השניה, \( ex=x \), נובעת מייד מהגדרת \( e \). גם העובדה שכל \( a \) עובר לאיבר של \( S_{G} \) היא לא חדשה - כבר בפוסט הראשון על חבורות אמרתי שכל איבר בחבורה מגדיר תמורה של אברי החברה על ידי כפל בהם. מה שקצת מעניין הוא שההומומורפיזם של \( G \) לתוך \( S_{G} \) הוא איזומורפיזם, כלומר הגרעין שלו טריוויאלי; זאת מכיוון שרק עבור \( e \) מתקיים \( ex=x \) לכל \( x\in G \), ואילו לאיברים אחרים זה לא יקרה ולכן התמונה שלהם אינה איבר היחידה של \( S_{G} \). המסקנה: \( G \) איזומורפית לתת-חבורה של \( S_{G} \). את התוצאה הזו ראינו כבר בפוסט שעסק בתמורות, והגיע הזמן לתת לה שם - משפט קיילי.

עכשיו אני רוצה להראות דוגמא קצת יותר מעניינת שעדיין מבוססת על כפל. בואו ניקח חבורה \( G \) ותת-חבורה \( H\subseteq G \). בואו נזכור שיש ל-\( H \) משהו שנקרא קוסטים: קבוצות מהצורה \( aH\triangleq\left\{ ah\ |\ h\in H\right\} \) שהן מעין “הזזות” של \( H \). אפשר להגדיר פעולה של \( G \) על קבוצת הקוסטים של \( H \) באמצעות כפל משמאל בנציג של הקוסט: \( g\cdot\left(aH\right)\triangleq\left(ga\right)H \). קל לראות שזו אכן פעולה, ולכן שהיא מבצעת פרמוטציה של הקוסטים של \( H \). כדי להמחיש שזה מעניין אני אוכיח משפט שמראה תנאי מסויים לכך ש-\( H \) תהיה נורמלית.

תזכורת: אינדקס של תת-חבורה \( H \), שאני אסמן כאן בתור \( \left|G:H\right| \), הוא מספר הקוסטים שלה. משפט פשוט יחסית מראה שאם \( \left|G:H\right|=2 \) אז \( H \) בהכרח נורמלית; זה נובע מכך שתת-חבורה היא נורמלית אם לכל \( a \) מתקיים \( aH=Ha \). עכשיו, \( a\in H \) אם ורק אם \( aH=H \) וגם \( Ha=H \). כלומר, בהכרח \( aH,Ha \) הן או שתיהן בו זמנית הקוסט \( H \) או שתיהן בו זמנית לא הקוסט \( H \). אם יש רק שני קוסטים, האפשרות השניה אומרת ש-\( aH,Ha \) הן בו זמנית הקוסט הנוסף היחיד ולכן \( aH=Ha \) תמיד.

אני רוצה להכליל את המשפט הזה לטענה הבאה: אם \( \left|G:H\right|=p \) כך ש-\( p \) ראשוני וזה הראשוני הקטן ביותר שמחלק את הסדר של \( G \), אז \( H \) נורמלית. בשביל לעשות את זה, אני אסתכל על הפעולה של \( G \) על הקוסטים של \( H \). מכיוון שיש \( p \) קוסטים, הפעולה הזו ניתנת לתיאור על ידי הומומורפיזם \( \pi:G\to S_{p} \). נסמן \( K=\ker\pi \) - כלומר, כל האיברים שעליהם הפעולה היא טריוויאלית. אני אוכיח ש-\( K=H \) במקרה הנוכחי, מה שגורר מייד ש-\( H \) היא נורמלית כי גרעין של הומומורפיזם הוא נורמלי.

עד עכשיו לא ברור מה הקשר להוכחה שהראיתי קודם במקרה של \( p=2 \). בואו נזכר כעת שהתחלתי מכך ש-\( aH=H \) אם ורק אם \( a\in H \); זו אבחנת מפתח גם כאן, כי היא אומרת שהאיברים של \( K \) מלכתחילה חייבים להיות רק איברים של \( H \), דהיינו \( K\subseteq H \); כל איבר של \( G \) שאינו ב-\( H \) הולך להעביר את \( H \) עצמה לקוסט אחר שלה ולכן לא נקבל פעולה טריוויאלית (למעשה, אפשר להראות ש-\( K=\bigcap_{x\in G}xHx^{-1} \) כלומר הגרעין הוא חיתוך כל ההצמדות של \( H \) אבל זה לא חשוב כרגע).

מכיוון ש-\( K\subseteq H \) אפשר להשתמש בתוצאה שמקשרת את האינדקס של \( K \) ב-\( H \) לאינדקס של \( K \) ב-\( G \):

\( \left|G:K\right|=\left|G:H\right|\left|H:K\right| \)

התוצאה הזו היא מסקנה מיידית ממשפט האיזומורפיזם השלישי אבל לא הראיתי אותה במפורש עדיין. במקרה שלנו, אם נסמן \( \left|H:K\right|=k \) נקבל ש-\( \left|G:K\right|=pk \). עכשיו, \( \left|G:K\right| \) הוא הסדר של התמונה \( \pi\left(G\right) \), כלומר של תת-חבורת הפרמוטציות שמתארות את הפעולה של \( G \) על הקוסטים של \( H \). זו תת-חבורה של \( S_{p} \) ולכן הסדר שלה מחלק את \( \left|S_{p}\right|=p! \). עכשיו נכנסת לתמונה העובדה ש-\( p \) הוא הראשוני המינימלי שמחלק את \( \left|G\right| \): אנחנו מקבלים ממשפט לגראנז’ ש-\( pk|p! \), כלומר ש-\( k|\left(p-1\right)! \). מצד שני, \( k \) חייב לחלק את הסדר של \( G \) (כי הוא מחלק את הסדר של \( H \) והסדר של \( H \) מחלק את הסדר של \( G \)). זה ש-\( k \) מחלק את \( \left(p-1\right)! \) אומר שכל הגורמים הראשוניים שלנו חייבים להיות קטנים מ-\( p \) (כי \( \left(p-1\right)! \) הוא בהגדרתו כפולה של מספרים שכולם קטנים מ-\( p \)) ומכיוון שאין גורמים כאלו שמחלקים את הסדר של \( G \), בהכרח \( k=1 \). כלומר, \( \left|H:K\right|=1 \) מה שאומר ש-\( H=K \) כפי שרצינו.

מה שנחמד במשפט הזה הוא השילוב בין הרעיון הכללי של “היי יועיל לנו להסתכל על הפעולה של \( G \) על \( H \)” ובין הפרקטיקה המאוד קטנונית של המשחק במספרים, עם \( k \) מחלק את \( \left(p-1\right)! \) והכל. זה מאפיין לא רע את האופן שבו מנסים להבין את המבנה של חבורות סופיות. נראה עוד דוגמאות לזה בהמשך.

חבורה שפועלת על עצמה באמצעות הצמדה

אני רוצה לדבר עכשיו על סוג שונה של פעולה של חבורה על עצמה. כזה שגם יתן לנו משפט מועיל למדי, וגם יתן לנו תירוץ טוב להציג מושגים כלליים יותר - פעולה באמצעות הצמדה. נתקלנו כבר בהצמדה בהקשר של חבורות של תמורות: אם \( a\in G \) הוא איבר כלשהו ו-\( x\in G \) הוא האיבר שאנחנו רוצים להצמיד את \( a \) באמצעותו, אז ההצמדה שלהם היא האיבר \( xax^{-1} \). במקרה שבו \( a \) הייתה תמורה הצמדה שלה על ידי \( x \) הייתה בעלת משמעות קונקרטית של שינוי המספרים בתוך פירוק למעגלים של \( a \) בהתאם לתמורה ש-\( x \) מגדירה. באופן כללי יותר אני לא בטוח אם יש לי אינטואיציה כללית לגבי “מה הצמדה בדיוק עושה” מעבר לכך שהיא מבצעת פרמוטציה על אברי \( G \) בדרך מעניינת.

בדוגמא שלנו עם פרמוטציות, ראינו שהצמדה מסוגלת להעביר תמורה לכל תמורה אחרת שיש לה את אותו מבנה מעגלים. יצא מכך שאפשר לפרק את כל התמורות בחבורה שלנו לתת-קבוצות, כשבכל תת-קבוצה יש את כל התמורות בעלות אותו מבנה מעגלים. תתי-הקבוצות הללו לא היו תתי-חבורות - אין סגירות לכפל - אבל הן עדיין מעניינות. זה מקרה פרטי של מה שנקרא מחלקת צמידות: אם \( G \) היא חבורה ו-\( a\in G \) הוא איבר, אז מחלקת הצמידות של \( a \) היא הקבוצה \( \left\{ xax^{-1}\ |\ x\in G\right\} \). לא קשה לראות שהצמדה היא יחס שקילות, אז “מחלקת צמידות” היא בעצם מחלקת שקילות, ובפרט כל איבר מופיע בדיוק במחלקת צמידות אחת. במקרה שבו \( G \) סופית, זה מאפשר לנו לתת אפיון כלשהו של מחלקות הצמידות: אם המחלקות הללו הן \( A_{1},\dots,A_{n} \) אז \( \left|G\right|=\sum_{i=1}^{n}\left|A_{i}\right| \).

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

ובכן, בואו ננסה להבין מה קורה בתוך מחלקת הצמידות. הקבוצה \( \left\{ xax^{-1}\ |\ x\in G\right\} \) כוללת בדיוק \( \left|G\right| \) איברים: \( xax^{-1} \) עבור כל \( x\in G \). הבעיה היא שחלק מהאיברים הללו זהים ולכן לא נספרים פעמיים. אז מתי נקבל שני איברים זהים? נניח ש-\( xax^{-1}=yay^{-1} \), אז \( y^{-1}xax^{-1}y=a \), או \( \left(y^{-1}x\right)a\left(y^{-1}x\right)^{-1} \). במילים אחרות, \( x,y \) מחזירים את אותו איבר כשמצמידים איתם את \( a \) אם ורק אם \( y^{-1}x \) הוא בעל התכונה שהוא מקבע את \( a \) - הצמדה של \( a \) איתו לא משנה את \( a \).

בואו נניח ש-\( g\in G \) הוא בעל התכונה \( gag^{-1}=a \). אז על ידי כפל ב-\( g \) נקבל \( ga=ag \). במילים אחרות, \( g \) מקבע את \( a \) בהצמדה אם ורק אם \( g \) מתחלף בכפל עם \( a \). זה מוביל למושג של המרכז (Centralizer) של \( a \) ב-\( G \): המרכז, \( C_{G}\left(a\right)\triangleq\left\{ g\in G\ |\ ag=ga\right\} \), הוא אוסף האיברים ב-\( G \) שמתחלפים עם \( a \). קל לראות שזו תת-חבורה של \( G \), אז מה שראינו הוא ש-\( x,y \) מחזירים אותו איבר אם מצמידים את \( a \) איתם אם ורק אם \( x,y \) שייכים לאותו קוסט של \( C_{G}\left(a\right) \). דהיינו, כל קוסט של \( C_{G}\left(a\right) \) מגדיר איבר אחר במחלקת הצמידות של \( a \). מכאן שגודל מחלקת הצמידות הוא בדיוק \( \left|G:C_{G}\left(a\right)\right| \).

יש עוד אופטימיזציה אחת שכדאי לנקוט בה. בואו נסתכל על \( e \) למשל: איבר היחידה של \( G \) בוודאי מתחלף עם כל איבר ב-\( G \), ולכן \( C_{G}\left(e\right)=G \) ונקבל \( \left|G:C_{G}\left(e\right)\right|=1 \). זה לא רק \( e \), זה כל איבר שמתחלף עם כל אברי החבורה, וכאלו יכולים להיות הרבה. למשל במטריצות, כל מטריצה סקלרית מתחלפת עם כל המטריצות. זה מוביל אותנו למושג של המרכז (Center) של \( G \): \( Z\left(G\right)\triangleq\left\{ g\in G\ |\ \forall a\in G:ga=ag\right\} \) - כל האיברים שמתחלפים עם כל אברי \( G \). במקום לספור 1 עבור כל איבר של המרכז, אפשר לספור את כולם ביחד. נקבל את התוצאה הבאה: אם \( a_{1},\dots,a_{n} \) הם נציגים של מחלקות הצמידות של \( G \) שאינן סינגלטונים, אז \( \left|G\right|=\left|Z\left(G\right)\right|+\sum_{i=1}^{n}\left|G:C_{G}\left(a\right)\right| \). זה ניסוח מחודש של המשוואה \( \left|G\right|=\sum_{i=1}^{n}\left|A_{i}\right| \) מלמעלה שהוא מועיל מספיק כדי לזכות לשם משוואת המחלקה (Class Equation) של החבורה. שימו לב שזו משוואה מעניינת רק במקרה של חבורה לא אבלית, כי במקרה האבלי מקבלים \( \left|G\right|=\left|Z\left(G\right)\right| \) וזהו.

בשביל מה כל זה היה טוב? ובכן, שתי סיבות. ראשית, צריך לזכור שאחד מהיעדים שלנו הוא להגיע למצב שבו אנחנו מסוגלים להבין מהן כל החבורות מסדרים קטנים יחסית. משהו כמו משוואת המחלקה יהיה שימושי לכך. שנית, עוד רגע אציג מושגים כלליים עבור פעולת חבורה על קבוצה שמכלילים את המושגים של “מחלקת צמידות” ו”מרכז” שכבר ראינו קודם, אז טוב שהתחלנו עם דוגמה קונקרטית. בואו נתחיל עם שימוש. חבורת \( p \), עבור מספר ראשוני \( p \), היא חבורה \( G \) כלשהי עם מספר איברים שהוא חזקה של \( p \), כלומר \( \left|G\right|=p^{\alpha} \). הנה טענה: לחבורת \( p \) תמיד יש מרכז לא טריוויאלי, כלומר \( \left|Z\left(G\right)\right|>1 \). למה? ובכן, ממשוואת המחלקה, \( \left|Z\left(G\right)\right|=\left|G\right|-\sum_{i=1}^{n}\left|G:C_{G}\left(a\right)\right| \). כל אחד מהאיברים באגף ימין הוא חזקה של \( p \), ממשפט לגראנז’ (סדר של תת-חבורה חייב לחלק את סדר החבורה, ואת \( p^{\alpha} \) מחלקות רק חזקות של \( p \)). מכיוון שהאיברים בסכום \( \sum_{i=1}^{n}\left|G:C_{G}\left(a\right)\right| \) הם עבור האיברים שאינם במרכז אז החזקה של \( p \) שמחלקת את אברי אגף ימין היא לפחות 1. כלומר, כל אגף ימין מתחלק ב-\( p \) ולכן גם אגף שמאל, מה שגורר שהוא בפרט גדול מ-1.

עכשיו, הנה יישום בנפנוף ידיים של התוצאה הזו. נניח ש-\( \left|G\right|=p^{2} \) עבור \( p \) ראשוני - אני רוצה לטעון שבמקרה הזה, \( G \) היא בהכרח אבלית. כלומר: אין חבורות לא אבליות מסדרים 4,9,25,49, וכן הלאה. למה? ובכן, אם \( Z\left(G\right) \) לא טריוויאלי, וזה מה שראינו לפני רגע, אז בהכרח \( G/Z\left(G\right) \) היא חבורה מסדר \( 1 \) או \( p \), כלומר ציקלית. והנה משפט כללי: אם \( G/Z\left(G\right) \) ציקלית אז \( G \) אבלית. הנימוק פשוט: אם \( aZ\left(G\right) \) הוא יוצר של \( G/Z\left(G\right) \) אז כל איבר של \( G \) הוא מהצורה \( a^{k}b \) כאשר \( b\in Z\left(G\right) \). כעת נכפול שני איברים כאלו:

\( \left(a^{k}b\right)\cdot\left(a^{t}b^{\prime}\right)=a^{k}a^{t}bb^{\prime}=a^{k+t}\left(b^{\prime}b\right)=\left(a^{t}b^{\prime}\right)\left(a^{k}b^{k}\right) \) וקיבלנו התחלפות בכפל (שנובעת מכך שה-\( b \)-ים הם איברים המרכז ואילו חזקות שונות של \( a \) מתחלפות זו עם זו).

מסלולים ומייצבים

הבטחתי להכליל את המושג של מחלקת צמידות ושל מרכז, אז בואו נעשה את זה. אם \( G \) היא חבורה שפועלת על קבוצה \( X \) כלשהי, כלומר אני לא מניח בכלל של-\( X \) יש מבנה כלשהו של חבורה הפעם, אז היחס “יש \( g\in G \) שמעביר את \( x \) אל \( y \)” הוא יחס שקילות על \( X \): \( e\cdot x=x \) לכל \( x\in X \) אז יש רפלקסיביות; אם \( a\cdot x=y \) אז \( a^{-1}\cdot y=x \) אז יש סימטריה; ואם \( a\cdot x=y \) וגם \( b\cdot y=z \) אז \( \left(ba\right)\cdot x=z \) אז יש טרנזיטיביות. למחלקת השקילות של \( x \) קוראים המסלול (Orbit) של \( x \) (ביחס לפעולה של \( G \)). אסמן אותו \( \mathcal{O}\left(x\right) \). עכשיו, אם מסלול הוא ההכללה של “מחלקת צמידות”, מה ההכללה של “מרכז”, כלומר של \( C_{G}\left(x\right) \)? אנחנו מחפשים את אוסף האיברים שכשמפעילים אותם על \( x \) הוא לא משתנה. נקרא לאוסף הזה המייצב (Stablizer) של \( x \) ונסמן אותו ב-\( G_{x}\triangleq\left\{ a\in G\ |\ a\cdot x=x\right\} \). קל לראות שאם \( ax=bx \) אז \( b^{-1}a\in G_{x} \), ומכאן כמו קודם ש-\( \left|\mathcal{O}\left(x\right)\right|=\left|G:G_{x}\right| \). האבחנה הזו נקראת לפעמים משפט מסלול-מייצב.

לסיום, אני רוצה להציג עוד משפט שמסתכל על כל זה מהכיוון ה”הפוך”. לפני רגע לקחנו איבר של הקבוצה שעליה פועלים ובדקנו מי מקבעים אותו. תחשבו על זה כמו על לקחת צורה ולבדוק מה הסימטריות שלה. עכשיו בוא נעשה ההפך - ניקח תנועה צפידה ונבדוק אילו איברים הם סימטריים ביחס אליה. פורמלית, ניקח \( a\in G \) ונסתכל על הקבוצה \( X^{g}\triangleq\left\{ x\in X\ |\ gx=x\right\} \). כעת, \( \left|X^{g}\right| \) הוא מספר האיברים ש-\( g \) מקבעת. אפשר לקחת ממוצע של המספר הזה עבור כלל האיברים בחבורה: \( \frac{\sum_{g\in G}\left|X^{g}\right|}{\left|G\right|} \). למה הממוצע הזה שווה? באופן קצת מפתיע, הוא שווה בדיוק למספר המסלולים של הפעולה של \( G \). אני יכול לסמן ב-\( X/G \) את קבוצת כל המסלולים, ואז לכתוב

\( \left|X/G\right|=\frac{\sum_{g\in G}\left|X^{g}\right|}{\left|G\right|} \)

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

ההוכחה של הלמה של ברנסייד עוברת דרך הראיה של \( X^{g} \) ו-\( G_{x} \) בתור שני צדדים של אותה המטבע. בואו נכתוב שוב את שני החברים הללו במפורש:

\( G_{x}=\left\{ g\in G\ |\ gx=x\right\} \)

\( X^{g}=\left\{ x\in X\ |\ gx=x\right\} \)

אגף ימין של שתי הקבוצות הללו - התנאי שמגדיר אותן - זהה. ההבדל הוא ב”את מי סופרים”: אפשר לספור איברים מ-\( G \) ואפשר לספור איברים מ-\( X \). הפאנץ’ הוא שכשסוכמים על כל האברים האפשריים, אנחנו סופרים את כל הזוגות שמקיימים את המשוואה של אגף ימין:

\( \sum_{g\in G}\left|X^{g}\right|=\left|\left\{ \left(g,x\right)\in G\times X\ |\ gx=x\right\} \right|=\sum_{x\in X}\left|G_{x}\right| \)

אז במקום להוכיח את המשוואה \( \left|X/G\right|=\frac{\sum_{g\in G}\left|X^{g}\right|}{\left|G\right|} \) די לנו להוכיח את המשוואה

\( \left|X/G\right|=\sum_{x\in X}\frac{\left|G_{x}\right|}{\left|G\right|} \)

עכשיו, מה זה \( \frac{\left|G_{x}\right|}{\left|G\right|} \)? כאן נחלץ לעזרתנו משפט מסלול-מיצב: \( \left|\mathcal{O}\left(x\right)\right|=\left|G:G_{x}\right|=\frac{\left|G\right|}{\left|G_{x}\right|} \). במילים אחרות, \( \frac{\left|G_{x}\right|}{\left|G\right|}=\frac{1}{\left|\mathcal{O}\left(x\right)\right|} \).

בפני עצמה, לא נראה שהתוצאה עזרה לנו במיוחד. עכשיו אנחנו צריכים להוכיח את

\( \left|X/G\right|=\sum_{x\in X}\frac{1}{\left|\mathcal{O}\left(x\right)\right|} \)

וחיבור של “אחד חלקי משהו-ים” זה עסק מסובך (כמה זה \( \frac{1}{13}+\frac{1}{31}+\frac{1}{73} \)?). למרבה המזל, יש עוד אבחנה זריזה אחת שהופכת את הכל לטריוויאלי: הסכום באגף ימין נלקח על כל אברי \( X \). אנחנו יכולים לפרק אותו לשני סכומים - הראשון רץ על כל המסלולים ב-\( X \) והשני רץ על אברי כל מסלול:

\( \sum_{x\in X}\frac{1}{\left|\mathcal{O}\left(x\right)\right|}=\sum_{\mathcal{O}\in X/G}\sum_{x\in\mathcal{O}}\frac{1}{\left|\mathcal{O}\left(x\right)\right|} \)

והסכום \( \sum_{x\in\mathcal{O}}\frac{1}{\left|\mathcal{O}\left(x\right)\right|} \) מן הסתם שווה ל-1, כי \( \mathcal{O}\left(x\right) \) הוא קבוע לכל \( x\in\mathcal{O} \). קיבלנו את הסכום \( \sum_{\mathcal{O}\in X/G}1=\left|X/G\right| \).

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

נניח שיש לי \( n \) צבעים. בכמה דרכים שונות אני יכול לצבוע קוביה באמצעות הצבעים? על פניו, לקוביה יש 6 פאות. לכל פאה בוחרים בנפרד צבע, ולכן יש \( n^{6} \) אפשרויות. מצד שני, האם יש הבדל בין המקרה שבו צבענו את כל הקוביה באדום למעט הפאה העליונה שנצבעה בכחול, והמקרה שבו הכל אדום למעט הפאה התחתונה שהיא כחולה? מצד אחד כן, אם אנחנו חושבים על הפאות “למעלה” ו”למטה” כדברים נפרדים; מצד שני, אם יתנו לי שתי קוביות שנצבעו בשתי הדרכים הנ”ל אני אוכל לערבב אותן ביד שלי ולסובב אותן ולהגיש לכם בחזרה ולא תוכלו לדעת מי זו מי, אז שתיהן גם זהות במובן מסויים. אם נוקטים בגישה הראשונה, התשובה של \( n^{6} \) היא הנכונה; ננקוט כעת בגישה השניה, לפיה שתי צביעות הן זהות אם אפשר לסובב את הקוביה בדרך כלשהי שמעבירה את הצביעה הראשונה אל השניה. בדרך הזו המושג של פעולת החברה בא מעצמו - \( X \) היא קבוצת כל הצביעות (יש \( n^{6} \) כאלו בסך הכל) ואילו \( G \) היא קבוצת כל הסיבובים האפשריים של הקוביה. מה שאנחנו רוצים למצוא הוא את מספר המסלולים של פעולת \( G \) על \( X \) - כל מסלול כזה מייצג את כל הצביעות שהן “זהות עד כדי סיבוב”. הלמה של ברנסייד מנחה אותנו למצוא עכשיו לכל סיבוב אפשרי את כל הצביעות שמקובעות על ידו.

הניתוח המלא של כל הסיבובים האפשריים הוא לא טריוויאלי ואשמור אותו לפוסט ייעודי שיעסוק בלמה של ברנסייד, אבל הנה בכל זאת הרעיון הכללי: ראשית, קל לראות שיש בדיוק שלוש דרכים “בסיסיות” לסובב את הקוביה - מעבירים ציר דרך האמצע של שתי פאות מנוגדות ומסובבים סביבו (תחשבו על קוביה שמונחת על השולחן ואתם מסובבים מבלי להרים אותה). יש שלושה צירים וסיבוב בסיסי הוא של 90 מעלות, כך שלכאורה יש לנו 12 סיבובים שונים - אבל למעשה, שלושה מבין הסיבובים הללו הם זהים (ה”סיבוב” שבו אנחנו מסובבים ב-360 מעלות, כלומר לא מסובבים בכלל, ואז לא משנה באיזה ציר סובבנו) כך שיש לנו 9 סיבובים “בסיסיים” ועוד סיבוב אחד של “הזהות”. סיבוב “הזהות” מקבע כל צביעה אפשרית מבין ה-\( n^{6} \) הקיימות. סיבוב של 90 מעלות בציר מסויים לא משנה את הפאות שדרכן הועבר הציר, אבל האחרות עוברות זו לזו ולכן כולן חייבות להיצבע באותו הצבע, כך שיש לנו \( n^{3} \) צביעות אפשריות שמקובעות על ידי סיבוב כזה. סיבוב של 180 מעלות הוא קצת יותר מתירני - הוא מחליף שתי פאות מנוגדות, ולכן רק נדרש שכל שתי פאות מנוגדות יהיו בעלות אותו הצבע, מה שנותן לנו חופש בחירה של 4 פאות (עליונה, תחתונה, ואחת מבין כל שתי פאות מנוגדות) וקיבלנו \( n^{4} \) צביעות לכל סיבוב כזה. סיבוב של 270 הוא בעצם סיבוב של 90 מעלות לכיוון השני ולכן גם פה יש לנו \( n^{3} \) אפשרויות.

כל יתר הסיבובים של הקוביה הם הרכבות של הסיבובים הבסיסיים הללו. לא כל הרכבה תיתן סיבוב שונה; במקום להיכנס לניתוח מסובך שלהם, הנה אינטואיציה נחמדה לכך שיש בסך הכל 24 סיבובים אפשריים: קחו את הקוביה וחלקו כל פאה לארבעה משולשים על ידי העברת האלכסונים של כל פאה. קיבלנו סך הכל 24 משולשים בכל הפאות. בואו ניקח משולש כלשהו ונצבע אותו באדום. קל לראות שלכל משולש אחר בקוביה, יש סיבוב שיעביר את המשולש האדום עליו. קל גם לראות שהסיבוב הזה הוא יחיד (כי זו תנועה צפידה). אפשר גם להמחיש את הסיבובים הללו בתור סיבובים סביב צירים שלא מועברים דרך המרכז של פאות אלא דרך צירים מסובכים יותר, אבל זה דורש חשיבה תלת ממדית שאין לי. השורה התחתונה היא שנקבל 14 סיבובים נוספים שאפשר לחלק לשתי קבוצות - קבוצה של 8 סיבובים שמקבעים \( n^{2} \) צביעות, וקבוצה של 6 סיבובים שמקבעים \( n^{3} \) צביעות. הלמה של ברנסייד כעת אומרת לנו שמספר הצביעות השונות האפשרי הוא

\( \frac{1}{24}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right) \)

למשל, עבור צביעה ב-3 צבעים נקבל את המספר הלא נחמד במיוחד 57 צביעות. אני לא מכיר דרך פשוטה יותר להגיע למספר הזה מאשר לעבור דרך הלמה של ברנסייד, מלבד לצבוע בכל הצביעות האפשריות ולמחוק מהרשימה שלנו צביעות שקולות. אם כן, אנחנו רואים שכל הנושא הזה של פעולה של חבורה על קבוצה הוא ממש שימושי! ועכשיו אסיים את הפוסט מהר לפני שתתחילו לפקפק בזה.