מעגלים ארוכים בתהליך ה-Interchange

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

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

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

1. מבוא

תהליך ה-Interchange על גרף לא-מכוון ממושקל (עם משקולות a_{i,j} = a_{j,i} \ge 0) שיסומן G=(V,E), הוא תהליך מקרי הפועל באופן הבא: בזמן t=0 מונחת גולה שונה בכל קודקוד בגרף. על כל צלע (i,j) יש שעון שמצלצל בתוחלת כל a_{i,j}^{-1} שניות, כאשר התפלגות הזמן עד הצלצול היא אקספוננציאלית. השעונים בלתי-תלויים ולמעשה מתקיימים כל התנאים על מנת שזה יהיה "תהליך פואסון".
כאשר השעון על הצלע (i,j) מצלצל, הגולות ב-2 קצות הצלע מחליפות את מקומיהן. תהליך ה-Interchange בזמן t הוא משתנה מקרי IP(t) עם ערכים ב-S_V המתאר את הפרמוטצייה של מיקומי הגולות בזמן t, שהיא מכפלה של חילופים אקראיים. בזמן t=0 מתקיים IP(t) = \text{Id}, פרמוטציית הזהות. (IP = Interchange Process.)

מסתבר שהתהליך הזה (ווריאציות שלו) הוא דבר דיי מסתורי. שאלות בסיסיות כמו: "החל מאיזו נקודת זמן סביר למצוא מעגלים מאורך מסויים בתהליך?" נותרות ללא מענה עבור מרבית המקרים. אבל יש דברים שכן מצליחים לענות עליהם.

במאמר נותנים נוסחה מפורשת לסיכוי למעגל באורך n בזמן t בתהליך ה-Interchange על גרף עם n קודקודים. נותנים בו גם חסם עליון על המרחק בין מספר המעגלים המצופה מאורך k (שהוא \frac{1}{k}) לבין תוחלת מספר המעגלים בתהליך בזמן נתון.


כדי להבין את הנוסחה שמקבלים במאמר ואת ההוכחה, נצטרך להעמיק ב-2 נושאים:

  • תורת ההצגות: תורה שממיינת את כל ההומומורפיזמים מחבורה נתונה G לחבורה לינארית GL(V).
  • הלפלסיאן של גרף: לכל גרף ממושקל לא-מכוון מוצמד אופרטור לינארי חשוב, ה"לפלסיאן", הנתון ע"י D-A, כאשר A מטריצת השכנויות הממושקלת ו-D מטריצה אלכסונית שב-(i,i) מכילה את סכום המשקולות שיוצאות מ-i. הגרעין שלו הוא הפונקציות ההרמוניות על הגרף.

לפני שנדבר על נושאים אלו, נצטט את התוצאה שנקבל בסוף, על מנת שנתרשם:

משפט 1: נסמן ב-s_n(t) את מספר המעגלים באורך n בתהליך ה-Interchange על גרף עם n קודקודים בזמן t. נסמן ב-0=\lambda_{0}\le\lambda_{1}\le\cdots\le\lambda_{n-1} את הע"ע של הלפלסיאן של הגרף הממושקל. אזי:

\text{P}(s_{n}(t)=1)=\frac{1}{n}\prod_{i=1}^{n-1}(1-e^{-\lambda_{i}t})

ונצטט תוצאה שלא נוכיח עד הסוף:

משפט 2: נסמן ב-s_k(t) את מספר המעגלים באורך k (1 \le k \le n) בתהליך ה-Interchange בזמן t. באותם סימונים כמו קודם,

|\text{E}s_{k}(t)-\frac{1}{k}|\le\frac{3^{n}}{k}e^{-\lambda_{1}t}

(תזכורת – מספר מעגלים מגודל נתון: עבור פרמוטציה אקראית שנבחרת באופן אחיד מ-S_n, תוחלת מספר המעגלים באורך k היא \frac{1}{k}.
הסבר: נסמן ב-X_k את המשתנה המקרי הסופר מעגלים באורך k בפרמוטציה אקראית כזו. מתקיים X_k = \frac{1}{k} \sum_{i=1}^{n} 1_{i\text{ is contained in a k-cycle}}. מלינאריות התוחלת, מספיק להראות שתחלת כל אינדיקטור היא \frac{1}{n}, כלומר שהסיכוי שאיבר ספציפי נמצא במעגל באורך נתון היא \frac{1}{n}. זו טענה קומבינטורית לחלוטין שאשאיר לכם.)

ממשפט 1 ניתן לחשב עבור גרפים קונקרטים כמה זמן לוקח עד שהסיכוי \text{P}(s_{n}(t)=1) קרוב משמעותית ל-\frac{1}{n}, ולראות שזמן זה קטן משמעותית מ"זמן הערבוב" של כל הגרף, כלומר: מהזמן שלוקח להתפלגות של התהליך להיות קרובה משמעותית להתפלגות האחידה על פני כל הפרמוטציות. נראה חישוב עבור היפר-קוביה \mathbb{F}_{2}^{d} לקראת סוף הפוסט.

2. תורת ההצגות

הגדרה – הצגה: הצגה של חבורה G היא הומומ' \rho:G\to GL(V) כאשר V מרחב וקטורי, לרוב מעל \mathbb{C}. בפרט, זו פעולה של החבורה על המרחב הוקטורי V, אך יש לה תכונות נוספות שנובעות מכך שהיא מודעת למבנה הוקטורי של V.

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

הגדרה – הצגה פריקה/אי-פריקה: הצגה \rho:G\to GL(V) נקראת פריקה אם קיים תת-מרחב לא טריוויאלי 0 \subset V'\subset V שהוא \rho-שמור (או \rho-אינווריאנטי), ז"א: \forall g \in G: \rho(g) V' \subseteq V'. אחרת היא נקראת אי-פריקה.

משפט משקה (Maschke): במציין 0, אם 0 \subset V'\subset V תת-מרחב \rho-שמור אז קיים תת-מרחב 0 \subset V''\subset V שהוא \rho-שמור כך ש-V=V'\bigoplus V''. מסקנה מיידית היא שכל הצגה מתפרקת לסכום ישר של הצגות אי-פריקות! על כן מספיק לחקור הצגות אלו.

דוגמאות: לכל חבורה סופית G קיימת ההצגה הרגולרית-משמאל \rho_{\text{reg}}:G\to GL(\mathbb{C}^{G}), המוגדרת ע"י \rho_{\text{reg}}(g)e_{h}=e_{gh}. אם G לא טריוויאלית, מדובר בהצגה פריקה, ומסתבר שאם עובדים מעל המרוכבים מקבלים שכל הצגה אי-פריקה של G מופיעה בהצגה זו! כמו כן, תמיד קיימת ההצגה הטריוויאלית \rho_{\text{triv}}:G\to\mathbb{C}^{\times} המוגדרת בתור \forall g\in G:\rho_{\text{triv}}(g):=1.

הגדרה – קרקטר: קרקטר של הצגה \rho הוא הפונקציה המרוכבת \chi_{\rho}(g):=\text{Tr}(\rho(g)). בגלל שעקבה אינווריאנטית להצמדות, נובע ש-\chi_{\rho} קבועה על מחלקות צמידות של G. לפונקציה כזו קוראים "פונקציית מחלקה" (class function).

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

מסקנה חשובה: כל פונקציית מחלקה אפשר לכתוב כצירוף לינארי של קרקטרים של הצגות אי-פריקות

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

לא נוכיח טענות ומסקנות אלו, כי אנחנו לא צריכים אותן – נשתמש רק במסקנה האחרונה בתור מוטיבציה לחישוב שנעשה בהמשך.

דוגמא: נסתכל על G=\mathbb{Z}/n\mathbb{Z}. היא בפרט אבלית ולכן מספר מחלקות הצמידות שווה לסדר שלה, |G|. מצד שני, יש לנו n הצגות חד-מימדיות ובפרט אי-פריקות: \rho_{k}(x)=e^{\frac{2\pi i}{n}kx}, לכל 1\le k\le n, ששוות לקרקטר שלהן (למעשה, כל הצגה מתקבלת מסכום ישר של כאלו). לבטא פונקציה f:G\to\mathbb{C} כקומבינציה לינארית של קרקטרים אלו זה בדיוק מה שידוע בתור התמרת פורייה סופית:

f(a)=\frac{1}{n}\sum_{k=0}^{n-1}\hat{f}(k)\rho_{k}(a),\hat{f}(a)=\sum_{k=0}^{n-1}f(k)\rho_{-k}(a)

המקדמים המתקבלים ידועים בתור "מקדמי פורייה", ומקיימים:

\hat{f_{1}}(a)\hat{f_{2}}(a)=\widehat{f_{1}*f_{2}}(a)

זו אכן אינטואיציה טובה לתורת ההצגות – הכללה של התמרת פורייה לחבורות לא אבליות, ודוגמא לכך היא התכונה הבאה.

תכונה – קונבולוציה לכפל: אם f:G\to\mathbb{C} פונקציה ו-\rho:G\to GL(V) הצגה, אז \rho(f):=\sum_{g\in G}f(g)\rho(g) ביטוי שהופך קונבולוציה לכפל, כלומר \rho(f_{1}*f_{2})=\rho(f_{1})\rho(f_{2}) כאשר \forall g\in G,(f_{1}*f_{2})(g):=\sum_{xy=g}f_{1}(x)f_{2}(y). זו תכונה שימושית במיוחד בהסתברות, כי קונבולוציה מופיעה באופן טבעי לדוגמא כשסוכמים משתנים מקריים בלתי-תלויים. נשתמש בה בהמשך.

דרך נוספת וחשובה לתאר תכונה זו: נציג פונקציה f:G\to\mathbb{C} בתור וקטור \sum_{g\in G}f(g)e_{g} במרחב הוקטורי \mathbb{C}^{G}. אפשר להגדיר כפל במרחב וקטורי זה באופן טבעי: e_{g}\times e_{h}=e_{gh} (ההגדרה הכללית נובעת מבי-לינאריות הכפל). כעת, כפל וקטורים במרחב זה מתאים לקונבולציה של הפונקציות המתאימות! המרחב הוקטורי \mathbb{C}^{G} עם פעולת כפל זו נקרא "אלגברת החבורה G" (שמעתי גם את השם "אלגברת קונבולוציה") ויסומן \mathbb{C}G. איבר היחידה ביחס לכפל הוא e_{\text{1}_{G}} (כלומר, פונקציית האינדיקטור של איבר היחידה של החבורה). ההצגה \rho:G\to GL(V) משרה הומומורפיזם \mathbb{C}G\to\text{End}(V) ע"י \sum_{g\in G}a_{g}e_{g}\mapsto\sum_{g\in G}a_{g}\rho(g).
העובדה שזה הומומורפיזם בעצם אומרת ש-\rho מתרגמת קונבולוציה של פונקציות על G (דבר קשה) לכפל מטריצות (קל). הומומורפיזם זה שימושי מאוד ויופיע בהמשך.

3. הלפלסיאן

הגדרה – הילוך שיכור רציף: בהינתן גרף ממושקל לא-מכוון G (עם משקולות a_{i,j} \ge 0), הילוך שיכור רציף עליו מוגדר להיות התהליך הבא: על כל אחת מהצלעות יש שעון שמצלצל בממוצע תוך a_{i,j}^{-1} שניות, כאשר הזמן עד הצלצול מתפלג אקספוננציאלית. אם השיכור בקודקוד i, הוא מתקדם אל עבר הקודקוד שהשעון בין i אליו צלצל ראשון.

דוגמא: בהינתן גרף G כנ"ל עם n קודקודים, תהליך ה-Interchange עליו הוא הילוך שיכור רציף על גרף שקודקודיו הם איברי S_n, וקודקוד \pi מחובר ל-(i,j) \pi לכל i \neq j, כאשר משקל הצלע הוא a_{i,j} ונגזר ממשקולות G. בכל רגע נתון יש תחרות בין \binom{n}{2} משתנים אקספוננציאלים כדי להכריע איזה חילוף נבצע על הפרמוטציה, כלומר איזה צעד יעשה השיכור בגרף שקודקודיו S_n.
אם נצטמצם למסלול של גולה ספציפית בתהליך ה-Interchange נקבל גם הילוך שיכור.

הגדרה – לפלסיאן: יהי G=(V,E) גרף סופי לא-מכוון וממושקל. הלפלסיאן מוגדר להיות המטריצה \Delta_{G}=D-A כאשר A היא מטריצת השכנויות הממושקלת ו-D היא מטריצה אלכסונית שבמקום ה-(i,i) מכילה את סכום המשקולות היוצאות מקודקוד i.

ל-\Delta_{G} תכונות רבות: ראשית, היא לכסינה כי היא סימטרית ממשית. 0 הוא ע"ע כי הוקטור שכולו אחדות הוא ו"ע של 0. זה הע"ע הקטן ביותר שלה, כי ניתן להראות שהיא מוגדרת אי-שלילית: אם נגדיר את M להיות מטריצה E \times V כך ש-M_{\{i<j\},v}=\sqrt{a_{i,j}}(1_{v=i}-1_{v=j}), אז \Delta_{G}=M^{T}M. בנוסף, אם הגרף קשיר, הריבוי של 0 הוא 1.

את הלפלסיאן של תהליך ה-Interchange על G נסמן ב-"\Delta_{IP}". איך \Delta_{IP} פועל על e_{\pi}? באמצעות e_{\pi}\mapsto\sum_{i<j}a_{i,j}(e_{\pi}-e_{(i,j)\pi}). אם נגדיר \Delta'_{IP}=\sum_{i<j}a_{i,j}\cdot(e_{\text{id}}-e_{(i,j)})\in\mathbb{C}S_{n}, נקבל מהחישוב האחרון שההעתקה הלינארית x\mapsto\Delta'_{IP}x על \mathbb{C}S_{n} (כאשר \Delta'_{IP}x זה כפל באלגברה!) מיוצגת ע"י \Delta_{IP} (שימו לב: ממש לא כל העתקה לינארית \mathbb{C}S_{n}\to\mathbb{C}S_{n} מיוצגת ע"י כפל באיבר מ-\mathbb{\mathbb{C}}S_{n}\Delta_{IP} היא מיוחדת במובן הזה). חישוב זהה מראה שתחת ההצגה הרגולרית, \rho_{\text{reg}}(\Delta'_{IP})=\Delta_{IP}.

טבעי לשאול: האם יש קשר בין \Delta_{IP} ל-\Delta_{G}? בהמשך נראה שתחת ההצגה הטבעית, \rho_{\text{nat}}(\Delta'_{IP})=\Delta_{G}. כלומר, \Delta'_{IP} מייצג העתקה לינארית על מרחב ממימד n!, ותחת ההצגה הטבעית מקבלים את הלפלסיאן של הגרף המקורי.

כעת נוכיח טענה חיונית שתבהיר למה הלפלסיאן הוא מושג כה שימושי:

טענה: בהינתן הילוך שיכור רציף על גרף G, ווקטור הסתברויות התחלתי \vec{v}, ההתפלגות של ההילוך בזמן t היא \vec{v}^T e^{-t\Delta_{G}}. (זה לא צריך להפתיע אותנו כי התכונה (\vec{v}^T e^{-t\Delta_{G}})e^{-s\Delta_{G}}=\vec{v}^T e^{-(t+s)\Delta_{G}} מייצגת את חוסר הזיכרון של משתנה אקספוננציאלי.)

הוכחה: נסמן ב-f_{i}(t) את הסיכוי להגיע ל-i תוך t שניות (\vec{f} הוא וקטור באורך n:=|V|). איך יראה התהליך כעבור שבריר זמן dt? אם הוא היה במיקום i, ההסתברות שהפעמון על (i,j) יצלצל בשבריר זה היא 1-e^{-a_{i,j}dt}=a_{i,j}dt+O(dt^{2}). לעומת זאת, ההסתברות שאף אחד מהפעמונים הרלוונטים לא יצלצל היא \prod_{j\neq i}(1-a_{i,j}dt+O(dt^{2}))=1-\sum_{j\neq i}a_{i,j}dt+O(dt^{2}). נסמן d_{i}:=\sum_{j\neq i}a_{i,j} ונוכל להביע את מה שקיבלנו בתור:

f_{i}(t+dt)=f_{i}(t)\cdot(1-d_{i}dt)+\sum_{j\neq i}f_{j} a_{j,i}(t)dt+O(dt^{2})

מה שנותן את המשוואה הדיפרנציאלית הבאה, הנתונה בכתיב וקטורי: \vec{f}'(t)^T=\vec{f}(t)^T (-D+A). פתרון מד"ר זה הוא \vec{f}(0)^T e^{t(A-D)}, לדוגמא ממשפט היחידות. (סוף הוכחה 1)

בתהליך ה-Interchange, סכום המשקולות היוצא מקודקוד לא תלוי בקודקוד, והמטריצה D יוצאת סקלרית: D=dI. גרף כזה נקרא רגולרי, ויש הוכחה נוספת לטענה האחרונה שמשתמשת בתכונה זו: נסמן ב-P(t) את מטריצת המעבר שבמקום ה-i,j שלה כתוב הסיכוי להגיע מ-i ל-j ב-t שניות. הוקטור שאנחנו מחפשים יהיה \vec{v}^T P(t). כעת נשתמש בנוסחת ההסתברות השלמה:

\begin{aligned} P_{i,j}(t) &= \sum_{k\ge0}P(\text{Finished at j after t seconds} \mid k\text{ steps, started at i})P(\text{started at i, }k\text{ steps in }t\text{ seconds}) \\ &=\sum_{k\ge0}((\frac{A}{d})^{k})_{i,j}(\frac{(td)^{k}}{k!}e^{-td}) = (e^{t(A-dI)})_{i,j}=(e^{-t\Delta_{G}})_{i,j} \end{aligned}

כאשר השתמשנו בכך שמספר הצלצולים בקטע באורך t מתפלג פואסונית עם תוחלת td (תכונה של תהליך פואסון), ובכך שבהינתן כמות הצעדים שהיו אפשר להניח שהתהליך התנהג כמו הילוך מקרי דיסקרטי עם מטריצת מעבר \frac{A}{d}\blacksquare

הערה: כאשר הלפלסיאן סימטרי (כמו במקרה שלנו), לא משנה מאיזה כיוון כופלים את e^{-t\Delta_G } בוקטור ההסתברויות ההתחלתי (מלבד כך שבמקרה אחד נקבל וקטור שורה ובמקרה השני וקטור עמודה).

4. חישוב פונקציית מחלקה

נסמן ב-\alpha:S_{n}\to\mathbb{C} את פונקציית האינדיקטור של פרמוטציות שהן מעגל אחד גדול באורך n. זו פונקציית מחלקה, כי היא תלויה רק במבנה המעגלים של הקלט שלה. על כן אפשר, תיאורטית, לכתוב אותה כקומבינציה לינארית של קרקטרים של הצגות אי-פריקות.
מתוצאה שהזכרנו ולא הוכחנו, אוטומטית אפשר לכתוב \alpha = \sum_{\rho} \langle \alpha, \chi_{\rho} \rangle \chi_{\rho}, כאשר הסכום הוא על פני כל ההצגות האי-פריקות של S_n (כי הקרקטרים שלהן הם בסיס אורתונורמלי למרחב פונקציות המחלקה). ההצגות האי-פריקות של S_n מקוטלגות לחלוטין והקרקטרים שלהן מחושבים (תודות לפרובניוס), ויש דרכים חכמות לחשב את המכפלות הפנימיות שהמופיעות בסכום (כך עושים במאמר), אבל אנו נתחמק מהתורה הזו כי מתברר שבשביל משפט 1 לא צריך הרבה מעבר להצגה הטבעית של S_n, אותה נגדיר מיד.

הגדרה – ההצגה הטבעית: ההצגה הטבעית של S_n היא ההומומ' \rho_{\text{nat}}:S_{n}\to\mathbb{C}^{n} הנתון ע"י \rho_{\text{nat}}(\pi)e_{i}=e_{\pi(i)}. זו הצגה פריקה, כי V:=\{\sum a_{i}e_{i}\mid\sum a_{i}=0\} ו-U:=\text{Span}\{\sum e_{i}\} תתי-מרחבים \rho_{\text{nat}}-שמורים לא טריוויאלים המקיימים \mathbb{C}^{n}=V\bigoplus U.
מסתבר שההצגה \rho_{\text{nat}}|_{V} כבר אי-פריקה (תרגיל מלמד), ומימדה n-1. היא נקראת ההצגה הסטנדרטית של S_n ונסמנה \rho_{\text{std}}.

חישוב קרקטר: בגלל ש-\chi_{\rho_{\text{nat}}}(\pi)=\#\text{Fixed points of }\pi ו-\chi_{\rho_{\text{nat}}|_{U}}(\pi)=1, מתקיים: \chi_{\text{std}}(\pi)=(\#\text{Fixed points of }\pi)-1.

תזכורת על חזקה חיצונית: בהינתן מרחב וקטורי סוף מימדי V מעל \mathbb{C}, החזקה החיצונית ה-k-ית של V היא מרחב וקטורי מעל \mathbb{C}, המסומן \wedge^k V, ונפרש ע"י הוקטורים \{v_{1}\wedge v_{2}\wedge\cdots\wedge v_{k}\mid v_{i}\in V\} מודולו 3 סוגי יחסים:

  • כפל בסקלר: a(v_{1}\wedge\cdots\wedge v_{k})=v_{1}\wedge\cdots\wedge\underbrace{(av_{i})}_{i\text{'th position}}\wedge\cdots\wedge v_{k} לכל i ולכל a \in \mathbb{C}.
  • (מולטי-)לינאריות: v_{1}\wedge\cdots\wedge(v_{i}+v'_{i})\wedge\cdots\wedge v_{k}=(v_{1}\wedge\cdots\wedge v_{i}\wedge\cdots\wedge v_{k})+(v_{1}\wedge\cdots\wedge v'_{i}\wedge\cdots\wedge v_{k})
  • אנטי-סימטריות: v_{1}\wedge\cdots\wedge\underbrace{v_{i}}_{i\text{'th position}}\wedge\cdots\wedge\underbrace{v_{j}}_{j'\text{th position}}\wedge\cdots\wedge v_{k}=(-1)\cdot(v_{1}\wedge\cdots\wedge\underbrace{v_{j}}_{i\text{'th position}}\wedge\cdots\wedge\underbrace{v_{i}}_{j'\text{th position}}\wedge\cdots\wedge v_{k}). תכונה זאת שקולה לכך שאם בוקטור v_1 \wedge v_2 \wedge \cdots \wedge v_k יש חזרה (v_i = v_j), אז הוא שווה לאפס.

אפשר לחשוב על חזקה חיצונית בתור חזקה טנזורית V^{\otimes k} מודולו אנטי-סימטריות. אם \{b_{i}\}_{i=1}^{d} בסיס ל-V אז \{b_{i_{1}}\wedge b_{i_{2}}\wedge\cdots\wedge b_{i_{d}}\}_{i_{1}<i_{2}<\cdots<i_{d}} בסיס ל-\wedge^{k}V. על כן מימד \wedge^{k}V הוא \binom{d}{k}.
לכל העתקה לינארית A: V\to V יש העתקה מושרית \wedge^{k}A:\wedge^{k}V\to\wedge^{k}V הנתונה ע"י v_{1}\wedge v_{2}\wedge\cdots\wedge v_{k}\mapsto Av_{1}\wedge Av_{2}\wedge\cdots\wedge Av_{k}.

חזקות חיצוניות של \rho_{\text{std}}: החזקה החיצונית ה-k-ית של הצגה \rho היא ההומומ' המקיים: (\wedge^{k}\rho)(\pi):=\wedge^{k}(\rho(\pi)). איך נראה הקרקטר \chi_{\wedge^{k}\rho_{\text{std}}}? באופן כללי, אם A לכסינה והע"ע שלה הם \{\lambda_{i}\}_{i}, אז \text{Tr}(\wedge^{k}A) הוא הפולינום הסימטרי ה-k-י בהם, לדוגמא: \text{Tr}(\wedge^{2}A)=\sum_{i<j}\lambda_{i}\lambda_{j}.
מעל \mathbb{C}, תמונה של הצגה היא תמיד לכסינה (אם G חבורה סופית ו-\rho:G\to GL(\mathbb{C}^{n}) הצגה, נובע ש-\rho(g) מתאפסת ע"י הפולינום הספרבילי x^{|G|}-1, ולכן הפולינום המינימלי של \rho(g) מתפרק לגורמים לינאריים שונים), ולכן אפשר להשתמש בכלל הנ"ל.
נסתכל על הפונקציה f:=\frac{1}{n}\sum_{k=0}^{n}(-1)^{k}\chi_{\wedge^{k}\rho_{\text{std}}} (כאשר \wedge^{0} \rho_{\text{std}} מוגדרת להיות ההצגה הטריוויאלית). אם נחשב אותה על \pi\in S_{n} כך ש-\rho_{\text{std}}(\pi) בעלת ע"ע \lambda_{i}, נקבל f(\pi)=\frac{1}{n}(1-\sum\lambda_{i}+\sum\lambda_{i}\lambda_{j}\mp\cdots)=\frac{1}{n}\prod(1-\lambda_{i}).

  • במקרה ש-\pi\neq\text{n-cycle}, ביטוי זה מתאפס, כי ל-\rho_{\text{std}}(\pi) ע"ע 1: אם (c_{1},\cdots,c_{L_{1}}) ו-(d_{1},\cdots,d_{L_{2}}) שני מעגלים זרים של \pi, אז \sum e_{c_{i}}+(-\frac{L_{1}}{L_{2}})\sum e_{d_{j}} וקטור עצמי של ע"ע 1.
  • במקרה ש-\pi=\text{n-cycle}, ביטוי זה שווה 1 : הע"ע המתאימים הם השורשים של x^{n}-1 (הפולינום האופייני של \rho_{\text{nat}}(\pi)) לא כולל 1, ואז \prod(1-\lambda_{i})=\prod_{k=1}^{n-1}(1-e^{k\frac{2\pi i}{n}})=\frac{x^{n}-1}{x-1}|_{x=1}=n.

מסקנה: מצאנו את \alpha כקומבינציה לינארית של קרקטרים – \alpha = f!

5. איך הכל מתחבר?

אנחנו רוצים לחשב את:

\text{P}(s_{n}(t)=1)=\text{E}s_{n}(t)=\frac{1}{n}\sum_{k=1}^{n}(-1)^{k-1}k\text{E}\chi_{\wedge^{k}\rho_{\text{nat}}}(IP(t))

ראינו כי ההתפלגות של התהליך בזמן t נתונה ע"י הוקטור e^{-t\Delta_{IP}}. עובדה זו תיתן את הלמה הבאה:

למה: \text{E}\chi_{\rho}(IP(t))=\text{Tr}(e^{-t\rho(\Delta'_{IP})})הסבר:

  • ראשית, נשים לב שהקואורדינטה ה-\pi של e^{-\Delta_{IP}} e_{\text{Id}} (חישוב של מטריצות) שווה לקואורדינטה ה-\pi של e^{-t\Delta'_{IP}} (חישוב ב-\mathbb{C}S_{n}, כלומר e^{-t\Delta'_{IP}} = \sum \frac{(-t)^k}{k!} \underbrace{\Delta'_{IP} \cdots \Delta'_{IP}}_{\text{k times}}): ההעתקה x\mapsto \Delta_{IP}^{'} x ב-\mathbb{C}S_{n} מיוצגת ע"י המטריצה \Delta_{IP}. לכן ההעתקה x\mapsto(\Delta_{IP}^{'})^{k}x יוצאת \Delta_{IP}^{k}, ו-x\mapsto e^{-t\Delta'_{IP}}x יוצאת e^{-t\Delta{}_{IP}}. נפעיל על e_{\text{Id}} את 2 ההעתקות השקולות: מצד אחד נקבל e^{-t\Delta_{IP}}e_{\text{Id}}, מצד שני נקבל e^{-\Delta'_{IP}}e_{\text{Id}}=e^{-\Delta'_{IP}}, לכן הוקטורים e^{-\Delta_{IP}}e_{\text{Id}} ו-e^{-t\Delta'_{IP}} שווים.
  • שנית, בגלל שאת ההצגה \rho אפשר להגדיר על כל וקטור/פונקציה ב-\mathbb{C}S_n (בלינאריות), אפשר לכתוב כעת: \text{E}\chi_{\rho}(IP(t))=\sum_{\pi\in S_{n}}e^{-t\Delta'_{IP}}(\pi)\chi_{\rho}(\pi)=\text{Tr}(\rho(e^{-t\Delta'_{IP}})).
  • מתקיים \rho(e^{D})=e^{\rho(D)} עבור D\in\mathbb{C}S_{n} (בהנחה שיש התכנסות): אם נכתוב e^{D}=\sum_{k\ge0}\frac{D^{k}}{k!}, אז מספיק להוכיח \rho(D^{k})=\rho(D)^{k} וזה נובע מכך שקונבולוציה של פונקציות הופכת לכפל מטריצות. לכן \text{Tr}(\rho(e^{-t\Delta'_{IP}}))=\text{Tr}(e^{-t\rho(\Delta'_{IP})})\blacksquare

אם נסמן ב-\{\lambda_{\rho, i}\}_i את הע"ע של \rho(\Delta'_{IP}), נקבל מהלמה: \text{E}\chi_{\rho}(IP)=\sum_{i}e^{-t\lambda_{\rho,i}}. חישוב הע"עים הללו עבור רוב ההצגות הוא משימה קשה, אבל מתקיים הנס (לא פחות) הבא:

טענה: הע"ע \lambda_{\wedge^{k}\rho_{\text{std}},i} הם כל הסכומים החלקיים של k ע"ע שונים של \Delta_{G} (לא כולל \lambda_{0} = 0).

בהינתן הטענה, סיימנו: הסיכוי יוצא \frac{1}{n}\prod_{i=1}^{n-1}(1-e^{-\lambda_{i}t}) מפתיחת סוגריים. לפני הוכחת הטענה, אתן לכם לנסות את תרגיל החימום הבא:

תרגיל: הוכיחו כי \text{E}s_{1}(t) =\sum_{i=0}^{n-1} e^{-t \lambda_i} = 1 + \sum_{i=1}^{n-1} e^{-t \lambda_i} – כלומר יש נוסחה מפורשת גם לתוחלת מספר נקודות השבת (מעגלים באורך 1) של פרמוטציה בתהליך ה-Interchange.

הוכחת הטענה: המקרה k=0 ברור כי \rho_{\text{triv}}(\Delta'_{IP})=0. המקרה k=1 נובע מכך שנראה עכשיו ש-\rho_{\text{nat}}(\Delta'_{IP})=\Delta_{G}:

\rho_{\text{nat}}(\Delta'_{IP})e_{k}=\sum_{i<j}a_{i,j}(e_{k}-e_{(i,j)(k)})=\sum_{i\neq k}a_{i,k}(e_{k}-e_{i})=(\sum_{i\neq k}a_{i,k})e_{k}-\sum a_{i,k}e_{i}

(הסימון (i,j)(k) מייצג את ערך הפרמוטציה (i,j) על האיבר k.) כלומר ההעתקה \rho_{\text{nat}}(\Delta'_{IP}) פועלת בדיוק כמו \Delta_{G}. לאחר שמצטמצמים למרחב ה-(n-1)-מימדי של ההצגה הסטנדרטית V\subset\mathbb{C}^{n} מקבלים ש-\rho_{\text{std}}(\Delta'_{IP}) פועלת בדיוק כמו \Delta_{G}\mid_{V} (המשמעות מבחינת ע"עים היא שמוציאים את הע"ע \lambda_{0}=0 של ההצגה הטריוויאלית).

עבור k>1 החישוב ארוך יותר – מוזמנים לנסות בעצמכם, לא מבטיח שההוכחה שלי היא האלגנטית ביותר. נסמן ב-T_{i,j} את ההעתקה הלינארית ששולחת את e_k ל-e_{(i,j)k}, מצומצמת ל-V (היא אכן V-אינווריאנטית). ההעתקה הלינארית L^{(k)}:=\wedge^{k}\rho_{\text{std}}(\Delta) נתונה ע"י:

L^{(k)}(v_{1}\wedge\cdots\wedge v_{k}):=\sum_{i<j}a_{ij}((v_{1}\wedge\cdots\wedge v_{k})-(T_{(ij)}v_{1}\wedge\cdots\wedge T_{(i,j)}v_{k}))

נראה שאם u_{1},\cdots,u_{k} ו"ע שונים של L^{(1)}=\Delta_{G} \mid_{V} (עם ע"ע \lambda_i), אז u_{1}\wedge\cdots\wedge u_{k} ו"ע של L^{(k)}, עם ע"ע \sum\lambda_{i}. זה מספיק כדי לסיים את הטענה.
נסתכל על L^{(k)}(u_{1}\wedge\cdots\wedge u_{k}) בתור סכום טלסקופי:

\begin{aligned} L^{(k)}(u_{1}\wedge\cdots\wedge u_{k}) &= \sum_{i<j}a_{i,j}((u_{1}\wedge\cdots\wedge u_{k})-(T_{i,j}u_{1}\wedge\cdots\wedge T_{i,j}u_{k})) \\ &= \sum_{i<j}a_{i,j}((u_{1}\wedge\cdots\wedge u_{k})-(T_{i,j}u_{1}\wedge u_{2}\wedge\cdots\wedge u_{k})) + \\ & \cdots + \sum_{i<j}a_{i,j}((T_{i,j}u_{1}\wedge\cdots\wedge T_{i,j}u_{k-1}\wedge u_{k})-(T_{i,j}u_{1}\wedge\cdots\wedge T_{i,j}u_{k})) \end{aligned}

נסמן ב-v_r את הוקטור ה-r-י בסכום. מאוד מתבקש להגיד v_{r}=\lambda_{r}u_{1}\wedge\cdots\wedge u_{k}. עבור r=1 זה בבירור נכון, כי:

\begin{aligned} v_{1}&=\sum_{i<j}a_{i,j}((u_{1}\wedge\cdots\wedge u_{k})-(T_{i,j}u_{1}\wedge u_{2}\wedge\cdots\wedge u_{k})) \\&=(\sum_{i<j}a_{i,j}(u_{1}-T_{i,j}u_{1}))\wedge u_{2}\wedge\cdots\wedge u_{k}=\lambda_{1}u_{1}\wedge u_{2}\wedge\cdots\wedge u_{k} \end{aligned}

מסתבר שזה נכון גם עבור r>1, כי עוד שנייה נראה ש-

(*) \begin{aligned} v_{r}&=\sum_{i<j}a_{i,j}((u_{1}\wedge\cdots\wedge u_{r-1}\wedge u_{r}\wedge\cdots\wedge u_{k})-(u_{1}\wedge\cdots\wedge u_{r-1}\wedge T_{i,j}u_{r}\wedge u_{r+1}\wedge\cdots\wedge u_{k})) \end{aligned}

ואז:

\begin{aligned} v_{r} &= u_{1}\wedge\cdots\wedge u_{r-1}\wedge(\sum_{i<j}a_{i,j}u_{r}-T_{i,j}u_{r})\wedge u_{r+1}\wedge\cdots\wedge u_{k} \\ &= u_{1}\wedge\cdots\wedge u_{r-1}\wedge\lambda_{r}u_{r}\wedge u_{r+1}\wedge\cdots\wedge u_{k} \\ &= \lambda_{r}u_{1}\wedge\cdots\wedge u_{k} \end{aligned}

נותר להסביר את (*). מספיק להראות שיוויון בין המחוברים המתאימים:

(T_{i,j}u_{1}\wedge\cdots\wedge T_{i,j}u_{r-1}\wedge u_{r}\wedge\cdots\wedge u_{k})-(T_{i,j}u_{1}\wedge\cdots\wedge T_{i,j}u_{r}\wedge u_{r+1}\wedge\cdots\wedge u_{k})=(u_{1}\wedge\cdots\wedge u_{r-1}\wedge u_{r}\wedge\cdots\wedge u_{k})-(u_{1}\wedge\cdots\wedge u_{r-1}\wedge T_{i,j}u_{r}\wedge u_{r+1}\wedge\cdots\wedge u_{k})

לאחר העברת אגפים, זה נהיה:

T_{i,j}u_{1}\wedge\cdots\wedge T_{i,j}u_{r-1}\wedge((I-T_{i,j})u_{r})\wedge u_{r+1}\wedge\cdots\wedge u_{k}=u_{1}\wedge\cdots\wedge u_{r-1}\wedge((I-T_{i,j})u_{r})\wedge u_{r+1}\wedge\cdots\wedge u_{k}

נכתוב T_{i,j}u_{r}=(T_{i.j}-I)u_{r}+u_{r}, נשתמש במולטיליניאריות ובכך של-T_{i,j}-I תמונה ממימד 1 (ולכן אם יש וקטור a_1 \wedge a_2 \wedge \cdots \wedge a_k ששתיים מהקואורדינטות שלו הן תמונות של T_{i,j}-I, זה וקטור האפס), ונקבל את השיוויון. \blacksquare

6. דוגמא – היפר-קוביה

נסתכל על היפר-קוביה ממימד d, כלומר גרף G שקודקודיו \mathbb{F}_{2}^{d} ויש צלע בין כל זוג קודקודים שנבדלים בדיוק בקואורדינטה אחת. המשקולות על כל הצלעות הן 1. ידוע כי זמן הערבוב של תהליך ה-Interchange בגרף זה הוא \Omega(d).
מצד שני, אנחנו נראה מיד שזמן הערבוב של מספר המעגלים באורך 2^d הוא \theta(\log d), כאשר יש התנהגות מאוד חדה סביב t=\frac{\log d}{2} (מה שאנשי הסתברות אוהבים לכנות "מעבר פאזה").

הנוסחה ממשפט 1, 2^{-d}\prod(1-e^{-t\lambda}), דורשת חישוב ערכים עצמיים של הלפלסיאן. במקרה של היפר-קוביה זה קל יחסית: הלפלסיאן נתון ע"י dI-A, כאשר A מטריצת השכנויות. הספקטרום של הלפלסיאן במקרה זה הוא d פחות הספקטרום של A. אם נניח שהמטריצות והוקטורים מאונדקסים ע"י איברי \mathbb{F}_{2}^{d}, קל להיווכח שהו"ע הם f_{y}(x)=(-1)^{\langle y,x\rangle} ("פונקציות Walsh"), כי:

\begin{aligned} (Af_{y})_{i} &= \sum_{j}A_{i,j}(-1)^{\langle y,j\rangle}=\sum_{k=1}^{d}(-1)^{\langle y,i\oplus e_{k}\rangle} =\\ &(-1)^{\langle y,i\rangle}\sum_{k=1}^{d}(-1)^{\langle y,e_{k}\rangle}=f_{y}(i)\cdot(\#\{k:y_{k}=0\}-\#\{k:y_{k}=1\}) \end{aligned}

על כן הספקטרום מורכב מ-\{2k\}_{k=0}^{d}, כאשר 2k מופיע בריבוי \binom{d}{k}. ממשפט 1, ההסתברות למעגל בגודל 2^d בזמן t היא \text{P}=2^{-d}\prod_{k=1}^{d}(1-e^{-2tk})^{\binom{d}{k}}. אם נסתכל בזמן t=\frac{1-\varepsilon}{2}\log d, נגלה שהיא קטנה משמעותית מ-2^{-d}.
כדי להיווכח בכך, נסתכל רק על התרומה של הגורם המתאים ל-K=\lfloor\frac{d^{\varepsilon}}{2}\rfloor:

\begin{aligned} \text{P} &\le (1-e^{-K(1-\varepsilon)\log d})^{\binom{d}{K}}\underbrace{\le}_{1-x\le e^{-x}}\exp(-\binom{d}{K}d^{K(\varepsilon-1)})\underbrace{\le}_{\binom{a}{b}\ge(\frac{a}{b})^{b}}\exp(-(\frac{d^{\varepsilon}}{K})^{K}) \\ &\le \exp(-2^{K})=\exp(-\exp(\theta(d^{\varepsilon})))=o(2^{-d}) \end{aligned}

מצד שני, אם נסתכל על הזמן t=\frac{1+\varepsilon}{2}\log d, נגלה שההסתברות היא:

\begin{aligned} \text{P} &= 2^{-d}\exp(\sum_{k=1}^{d}\binom{d}{k}\ln(1-d^{-(1+\varepsilon)k}))\underbrace{=}_{\ln(1-x)=O(x)}2^{-d}\exp(\sum_{k=1}^{d}\binom{d}{k}O(d^{-(1+\varepsilon)k})) \\ & \underbrace{=}_{\binom{d}{k}\le d^{k}} 2^{-d}\exp(O(d^{-\varepsilon}))=2^{-d}(1+O(d^{-\varepsilon})) \end{aligned}

עוד מקרה מעניין הוא הגרף השלם G=K_n (כלומר, כל המשקולות הן 1). זמן הערבוב שלו ידוע להיות \theta (\frac{\log n}{n}). ומתי ההסתברות למעגל באורך n קרובה ל-\frac{1}{n}?

תרגיל: הראו שבמקרה של הגרף השלם על n קודקודים, |\text{E}s_n(t) - \frac{1}{n} | \le \frac{\lambda}{n} מתקיים החל מ-t \ge C_{\lambda} \frac{\ln n}{n}, כלומר בערך כשהתהליך כולו מתערבב.

7. האם אפשר בלי הצגות אי-פריקות?

הסמינר עבר בפני סטודנטים שלרובם לא היה רקע בהצגות, לכן תהיתי האם אפשר לנסח את ההוכחה הנ"ל בלי להשתמש בהצגה הסטנדרטית, כלומר: בלי לפרק את ההצגה הטבעית לשתי הצגות אי-פריקות. התשובה היא כן, וכך עשיתי – בגלל ש-\wedge^k (V \bigoplus U) \simeq \wedge^k V \bigoplus \wedge^{k-1} V כאשר U תת-מרחב ממימד 1, הנוסחאות נהיות:

\alpha=\frac{1}{n}\sum_{k=1}^{n}(-1)^{k-1}k \chi_{\wedge^{k}\rho_{\text{nat}}}

ובטענה השנייה של סעיף 5 בפוסט לא מדלגים על הע"ע \lambda_0=0 של הלפלסיאן. אתן לכם להשלים את הפרטים.

8. מה הלאה?

מה קורה עם מעגלים קצרים מ-n? מסתבר שעל אף ש-f_{k}(\pi):=\#k\text{-cycles in }\pi פונקציית מחלקה, הע"ע של \rho(\Delta_{IP}^{'}) עבור ההצגות הרלוונטיות כבר לא ניתנים להבעה בעזרת הע"ע של \Delta_{G} בלבד (כלומר הנס שקורה ב-k=1,n כבר לא חוזר על עצמו), אבל כן אפשר לחסום אותם על-ידם, ולכן מקבלים אי-שיוויון במשפט 2.

ביתר פירוט: במאמר מצליחים לרשום f_{k}=\frac{1}{k}\sum_{\rho}a_{\rho}\chi_{\rho} כאשר המקדמים a_{\rho} יצאו -1, 0, 1 (בין השאר, הקרקטר הטריוויאלי מופיע בסכום עם מקדם 1), וסכום המימדים של ההצגות המשתתפות בסכום יוצא לכל היותר 3^n. הע"ע הרלוונטים (כלומר, של \rho(\Delta'_{IP}), לפי הטענה הראשונה בסעיף 5 בפוסט) חסומים מלמטה ע"י הערך העצמי \lambda_1 של \Delta_G. חסם זה לא טריוויאלי כלל, ושקול להשערה של Aldous שהוכחה ב-2010.
ההשערה אומרת ש-\lambda_1 של הלפלסיאן של G (\Delta_G) גדול/שווה מ-\lambda_1 של הלפלסיאן של תהליך ה-Interchange, כלומר  של \Delta_{IP}.
בואו ננסה לפרש השערה זו. הע"ע של \Delta_{IP} הם הע"ע של המטריצה \rho_{\text{reg}}(\Delta_{IP}'), ומשפט ידוע אומר שההצגה הרגולרית מתפרקת לסכום ישר בו משתתפת בין השאר ההצגה הטבעית, לכן בין הע"ע של \rho_{\text{reg}}(\Delta_{IP}') נמצאים הע"ע של \rho_{\text{nat}}(\Delta_{IP}')=\Delta_{G}. ההשערה בעצם אומרת שהע"ע הכי קטן של \rho_{\text{nat}}(\Delta_{IP}') (לא כולל 0) מגיע מההצגה הטבעית, כלומר הוא \lambda_{1} של \Delta_G. בפרט, לכל הצגה \rho של S_n, כל הע"עים (לא כולל 0) של \rho(\Delta_{IP}') גדולים/שווים \lambda_{1}.
ל-\lambda_1 קוראים “Spectral Gap”, או: "פער ספקטרלי", והוא מכתיב את קצב ההתכנסות של הילוך מקרי על הגרף שממנו הוא מגיע – זה מושג שאי-אפשר להפריז בחשיבותו.

תופעה שכדאי לשים לב אליה היא זו: כשמציגים פונקציית מחלקה כללית f כסכום של קרקטרים, בנוסחה ל-\text{E}f יופיעו מחוברים כסכום מימדי ההצגות המשתתפות. בחבורת הסימטריה, להצגה ממוצעת יש מימד מסדר גודל \sqrt{n!}, אבל בפונקציות הספציפיות שעניינו אותנו המימדים היו קטנים באופן יוצא דופן – סכומם היה מעריכי ב-n (ספציפית, 2^n או 3^n).

אסיים בשורה משמחת – עבור הגרף השלם (המקרה שכל המשקולות a_{i,j} הם 1) ניתן לחשב מפורשות את הע"עים הנדרשים לחישוב תוחלת מספר המעגלים מאורך k, עבור k<n. בעזרת החישוב ניתן להוכיח מחדש, ובאלגנטיות, מספר תוצאות בנוגע לתהליך ה-Interchange. ראו מאמר בנושא.

בוקר,
אופיר

מודעות פרסומת

אודות Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
פוסט זה פורסם בקטגוריה כללי. אפשר להגיע ישירות לפוסט זה עם קישור ישיר.

תגובה אחת על מעגלים ארוכים בתהליך ה-Interchange

  1. משתמש אנונימי (לא מזוהה) הגיב:

    ה

כתיבת תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s