חבורה אוליגומורפית

במתמטיקה, ובפרט בתורת החבורות, חבורה אוליגומורפית היא חבורה הפועלת על מרחב סופי או בן-מנייה $\Omega$, כך שמספר המסלולים בפעולתה הטבעית (לפי רכיב) על $\Omega ^{n}$ הוא סופי לכל $n$ טבעי. חבורות אוליגומורפיות מכלילות חבורות של תמורות בכך שהן מתירות למרחב $\Omega$ שהן פועלות עליו להיות אינסופי, ובכך מאפשרות להכליל תכונות חשובות גם למקרה האינסופי. לחבורות אוליגומורפיות יש יישומים במספר תחומים במתמטיקה, ביניהם תורת המודלים וקומבינטוריקה ספרתית.

הגדרה

תהי $G$ חבורת תמורות הפועלת על קבוצה סופית או בת-מנייה $\Omega$. $G$ תיקרא חבורה אוליגומורפית אם לכל $n$ טבעי, ל-$G$ יש מספר סופי של מסלולים בפעולה שלה על $\Omega ^{n}$, כאשר הפעולה היא לפי רכיבים, כלומר $g(\alpha _{1},...,\alpha _{n})=(g\alpha _{1},...,g\alpha _{n})$.

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

מכפלת זר

מכפלת זר היא מכפלה חשובה של חבורות תמורות (שאפשר להגדיר לחבורות באופן כללי).

תהי $H$ חבורת תמורות על $\Gamma$, ו-$K$ חבורת תמורות על $\Delta$. נגדיר $\Omega =\Gamma \times \Delta$, נתייחס אליו כאל $\Delta$ סיבים של $\Gamma$, ונסמן $\Gamma _{\delta }=\{(\gamma ,\delta ):\gamma \in \Gamma \}$. לכל $\delta \in \Delta$ ניקח עותק $H_{\delta }$ של $H$ הפועל על $\Gamma _{\delta }$. כעת המכפלה הקרטזית $B=\prod _{\delta \in \Delta }H_{\delta }$ פועלת על $\Omega$ לפי רכיב, והיא תת-חבורה נורמלית. $K$ פועלת גם היא על $\Omega$ על ידי הפעלת תמורות על הסיבים $\Gamma _{\delta }$. נגדיר את מכפלת הזר $G=H\wr K$ להיות המכפלה החצי-ישרה $B\rtimes K$. $B$ תיקרא הבסיס של המכפלה ו-$K$ תיקרא ראש המכפלה.

אם $G$ חבורה טרנזיטיבית אבל לא פרימיטיבית הפועלת על $\Omega$, יהי $\Gamma$ בלוק של $\Omega$ הנשמר תחת פעולת $G$, ותהי $H$ חבורת התמורות המושרה מהמייצב שלו. תהי $\Delta$ קבוצת הבלוקים ו-$K$ חבורת התמורות המושרה על $\Delta$ דרך פעולת $G$. אז $G$ משוכנת באופן טבעי כחבורת תמורות במכפלת הזר $H\wr K$.

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

פונקציות מספר המסלולים

הסימון $\Omega ^{n}=(\alpha _{1},...,\alpha _{n})$ כאשר $\alpha _{i}\in \Omega$ שמופיע בהגדרה, הוא אוסף הסדרות מאורך $n$ עם חזרות ועם חשיבות לסדר. מתברר שדרישת סופיות המסלולים על הסדרות, שקולה לסופיות של מספר המסלולים על חליפות מאורך $n$ (בלי חזרות) או צירופים מאורך $n$ (בלי חזרות ובלי חשיבות לסדר). הטענה הזו נובעת מכמה חסמים על מספר המסלולים מכל סוג, שאפשר להוכיח בעזרת טיעונים קומבינטוריים פשוטים. מסמנים ב-$f_{n}$, $F_{n}$ ו-$F_{n}^{*}$ את מספר המסלולים של ׂG על n-צירופים, n-חליפות ו-n-סדרות, מימין לשמאל בהתאמה. לשם נוחות מגדירים $f_{0}=F_{0}=F_{0}^{*}=1$.

קל לראות כי $f_{n}\leq F_{n}\leq n!f_{n}$, שהרי כל צירוף בן $n$ איברים ניתן לסדר ב-$n!$ חליפות, הנמצאות בין 1 ל-$n!$ מסלולים שונים. לכן $f_{n}$ סופי אם ורק אם $F_{n}$ סופי. בנוסף מתקיים כי $F_{n}^{*}=\sum _{k=1}^{n}S(n,k)F_{k}$, כאשר $S(n,k)$ הוא מספר סטירלינג מסוג שני. לכן $F_{n}$ סופי לכל $n$ אם ורק אם $F_{n}^{*}$ סופי לכל $n$.

על-טרנזיטיביות ועל-הומוגניות

בעזרת פונקציות מספר המסלולים ניתן להכליל בקלות תכונות מוכרות. חבורה אוליגומורפית G תיקרא n-הומוגנית אם $f_{n}=1$, ו-n-טרנזיטיבית אם $F_{n}=1$. אם G היא n-הומוגנית או n-טרנזיטיבית לכל n טבעי, G תיקרא על-הומוגנית או על-טרנזיטיבית בהתאמה. (הגדרות אלו מתיישבות עם הגדרות מוכרות). לפי החסם על מספרי המסלולים, כל חבורה על-טרנזיטיבית היא על-הומוגנית.

לדוגמה, החבורה הסימטרית $S_{\Omega }$ היא על-טרנזיטיבית (כל תמורה נמצאת בה) ולכן גם על-הומוגנית.

חבורת התמורות ששומרות על הסדר של $\mathbb {Q}$, המסומנת $Aut(\mathbb {Q} ,<)$, היא על-הומוגנית אבל לא על-טרנזיטיבית. יהיו $(b_{1},...,b_{n})$,$(a_{1},...,a_{n})$ שני n-צירופים, נסדרם כך שיהיו עולים ממש. נוכל לשלוח כל $a_{i}$ ל-$b_{i}$, וכל קטע $(a_{i},a_{i+1})$ לקטע $(b_{i},b_{i+1})$ על ידי כפל והזזה במספר רציונלי מתאים. נרחיב את התמורה לכל $\mathbb {Q}$ וקיבלנו איבר של החבורה. אז $f_{n}=1$, זה נכון לכל n ולכן החבורה על-הומוגנית. מצד שני היא לא על-טרנזיטיבית, כי תמורה שומרת סדר לא יכולה להחליף בין שני מספרים שונים, ולכן $F_{n}=n!$.

עבור חבורה על-טרנזיטיבית, כמסקנה מהחסם הקודם מתקיים $F_{n}^{*}=\sum _{k=1}^{n}S(n,k)=B(n)$, כאשר $B(n)$ הוא מספר בל.

תכונות

פונקציות מספר המסלולים הן מונוטוניות עולות. לכל חבורה אוליגומורפית, $F_{n+1}\geq F_{n}$, ומתקיים שוויון אם ורק אם $F_{n+1}=1$. טענה קצת פחות טריוויאלית היא שמתקיים גם $f_{n+1}\geq f_{n}$.

אם $G\leq H$, חבורות אוליגומורפיות, אז $f_{n}(G)\geq f_{n}(H)$, וכן $F_{n}(G)\geq F_{n}(H)$, כי מורידים איברים ב-H שמצמצמים את מספר המסלולים. יתרה מכך, $f_{n+1}(G)-f_{n}(G)\geq f_{n+1}(H)-f_{n}(H)$, כלומר קצב הגידול של מספר המסלולים בתת-חבורה הוא גדול יותר.

ניתן לנסח באלגנטיות טענות על פונקציות מספר המסלולים על ידי שימוש בפונקציות יוצרות. עבור $f_{n}$ אין חשיבות לסדר, ולכן לכל G ניתן להשתמש בפונקציה היוצרת $f_{G}(t)=\sum _{n\geq 0}f_{n}(G)t^{n}$. עבור $F_{n}$ יש חשיבות לסדר, ולכן אפשר להתבונן בפונקציה היוצרת המעריכית $F_{G}(t)=\sum _{n=0}^{\infty }{\frac {F_{n}(G)t^{n}}{n!}}$.

עבור מכפלה ישרה, מתקיים $f_{G\times H}(t)=f_{G}(t)*f_{H}(t)$, וכן $F_{G\times H}(t)=F_{G}(t)*F_{H}(t)$.

לדוגמה, אם H על-הומוגנית, אז $f_{G\times H}(t)=(\sum _{n\geq 0}f_{n}(G)t^{n})*(\sum _{n\geq 0}t^{n})$, כלומר $f_{n}(G\times H)$ היא סדרת הסכומים החלקיים של $f_{n}(G)$. בפרט, אם S היא החבורה הסימטרית, ניתן להוכיח (באינדוקציה על k) כי $f_{n}(S^{k})={\binom {n+k-1}{k-1}}$.

עבור מכפלת זר, המצב מורכב יותר. מתקיים כי $F_{G\wr H}(t)=F_{H}(F_{G}(t)-1)$. בניגוד למכפלה ישרה, את $f_{n}(G\wr H)$ אי אפשר לחשב באופן ישיר מהפונקציות המתאימות של המרכיבים במכפלת זר, אבל ניתן לחשב זאת בכלים קומבינטוריים.

סדרות קומבינטוריות מפורסמות מתבררות להיות פונקציות מספר המסלולים של חבורות אוליגומורפיות. למשל, $f_{n}(\mathbb {Z} _{2}\wr Aut(\mathbb {Q} ,<))$ הוא מספר פיבונאצ'י ה-n, ו-$f_{n}(S\wr S)=\rho (n)$ כאשר $\rho (n)$ הוא מספר החלוקות של n, ו-S היא החבורה הסימטרית.

טופולוגיה

ניתן להגדיר באופן טבעי טופולוגיה על חבורת התמורות הפועלות על $\Omega$ כאשר הוא בן-מנייה. תהי $(\alpha _{1},\alpha _{2},...)$ מנייה של $\Omega$. נאמר שסדרה של תמורות $g_{n}$ מתכנסת ל-$g$ נקודתית אם ורק אם לכל k טבעי, עבור כל n גדול מספיק, מתקיים $g_{n}(\alpha _{k})=g(\alpha _{k})$. כעת ניתן להגדיר על $S_{\Omega }$ את הטופולוגיה של התכנסות נקודתית. (כלומר הטופולוגיה המושרית על התמורות של $\Omega$ מטופולוגיית המכפלה של $\Omega ^{\Omega }$).

בטופולוגיה הזו פעולת הכפל וההיפוך הן רציפות, ולכן כל חבורה אוליגומורפית G היא חבורה טופולוגית. G פתוחה ב-$S_{\Omega }$ אם ורק אם היא מכילה את המייצב (הנקודתי) של קבוצה סופית. הקבוצות $\{g\in Sym(\Omega ):g({\bar {a}})={\bar {b}}\}$, כאשר ${\bar {a}}$, ${\bar {b}}$ הן חליפות מאותו גודל, מהוות בסיס לטופולוגיה. אלו קוסטים של מייצבים (אם החליפות נמצאות באותו מסלול, אחרת זו קבוצה ריקה).

אפשר להגדיר מטריקה על חבורת התמורות באופן הבא – $d(g,h)={\begin{cases}0&g=h\\2^{-i}&g(j)=h(j)\,for\,j<i,\,g(i)\neq h(i)\end{cases}}$ המטריקה הזו משרה את הטופולוגיה שהגדרנו, ומשמעותה – שתי תמורות קרובות יותר ככל שהן מסכימות על רישא ארוכה יותר. מרציפות ההיפוך, גם המטריקה $d'(g,h)=\max(d(g,h),d(g^{-1},h^{-1}))$ משרה את אותה טופולוגיה. היתרון שלה הוא שהיא הופכת את $S_{\Omega }$ למרחב מטרי שלם.

לכל תת-חבורה של G יש טופולוגיה המושרה מהטופולוגיה של G. העובדה ש-$S_{\Omega }$ הוא מרחב מטרי שלם מאפשרת להשתמש במשפט הקטגוריה של בייר, משפט שימושי להוכחות לא קונסטרוקטיביות בטופולוגיה.

יישומים בתורת המודלים

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

אם G חבורת תמורות מעל $\Omega$, אז יש מבנה מעל שפה יחסית (חסרת קבועים) M כך שמתקיים $G\leq Aut(M)$, וכן ל-G ול-$Aut(M)$ יש את אותם מסלולים על $\Omega ^{n}$, לכל n. נוכל לפרק את $\bigcup _{n\geq 1}\Omega ^{n}$ למסלולים $O_{2}...$,$O_{1}$. לכל מסלול $O_{i}$ נגדיר יחס $R_{i}$ עם n משתנים אם $O_{i}\subseteq \Omega ^{n}$. כעת נפרש את $R_{i}$ מעל המודל (איחוד המסלולים) להיות $O_{i}$. לכן $G\leq Aut(M)$. כעת, כל $n$-יה המספקת את $R_{i}$ עושה זאת לערך יחיד של $i$, לכן אם ${\bar {a}}$ ו-${\bar {b}}$ נמצאים באותו מסלול תחת $Aut(M)$, הם מספקים את אותו $R_{i}$ ולכן נמצאים באותו מסלול ב-G. מבנה זה נקרא המבנה היחסי הקנוני של G.

המודל היחסי הקנוני של חבורה אוליגומורפית שופך אור נוסף על הטופולוגיה שלה. תת-חבורה G של $S_{\Omega }$ היא סגורה אם ורק אם $G=Aut(M)$ עבור מבנה M על $\Omega$. לא כל שכן, הסגור של חבורת תמורות G בטופולוגיה של $S_{\Omega }$, הוא חבורת האוטומורפיזמים של המבנה הקנוני שלה.

פיתוח הכלים של חבורות אוליגומורפיות בתורת המודלים ובטופלוגיה מובילים לתוצאות חזקות. אפיון אחד חשוב הוא גרסה של משפט Ryll-Nardzewski - מבנה בן-מנייה M הוא $\aleph _{0}$-קטגורי (כלומר מבנה מעל תורה $\aleph _{0}$-קטגורית) אם ורק אם $Aut(M)$ היא חבורה אוליגומורפית.

לקריאה נוספת

• Peter J. Camerom, “Oligomorphic Permutation Groups”, London Math. Soc. Lecture Note Series 152
• "Peter J. Camerom (1990), “Oligomorphic Permutation Groups