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

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

הגדרה

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

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

מכפלת זר

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

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

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

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

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

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

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

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

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

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

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

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

תכונות

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

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

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

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

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

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

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

טופולוגיה

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

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

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

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

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

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

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

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

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

לקריאה נוספת

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