הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 1/2)

בפוסט הנוכחי נחקור פונקציה מעניינת שמאפשרת לנו, בין השאר, להכליל את משפט וילסון, הגורס כי לכל מספר ראשוני p מתקיים: (p-1)!+1 מתחלק בp.
היסטורית, המשפט נוסח ע"י וילסון ב-1770 אבל הוכח רק 3 שנים לאחר מכן ע"י לגראנז'. להיסטוריה מפורטת ומדוייקת יותר, ראו את הערך בויקיפדיה.

יש ארבעה חלקים לפוסט:

  1. הקדמה על משפט וילסון
  2. הצגת ההכללה באמצעות הפונקציה האקספוננציאלית של ארטין-הסה
  3. תורת החבורות – משפט קושי ומשפט פרובניוס
  4. פונקציות יוצרות אקספוננציאליות ולמה ההכללה נובעת ישירות ממשפט פרובניוס

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

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

נפתח בסימונים דווקא.

סימונים

p – מספר ראשוני.

v_p(n) – המספר השלם האי-שלילי היחיד המקיים p^{v_p(n)} | n ו-p^{1+v_p(n)} \nmid n. אפשר לכתוב זאת בתור p^{v_p(n)} || n. אפשר להכליל פונקציה זו באופן מוגדר היטב למספרים רציונליים (שונים מאפס): v_p(\frac {n}{m}) = v_p(n) - v_p(m). עבור 0 מגדירים לרוב v_p(0) = \infty.

p-שלם – מספר רציונלי \frac{a}{b} המקיים v_p(\frac{a}{b})\ge 0 יקרא p-שלם.
שימו לב שמספר הוא p-שלם ביחס לכל ראשוני אמ"מ הוא שלם.

\exp(x) – הפונקציה המעריכית בבסיס הטבעי, בעלת הטור  \sum_{i\ge0}\frac{x^{i}}{i!}.

[G:H] – האינדקס של תת-החבורה H בG. עבור חבורות סופיות הוא שווה למנה \frac{|G|}{|H|}.

\phi(n) – פונקציית אוילר. סופרת כמה מספרים טבעיים מתוך \{1,2,\cdots ,n\} זרים לn. היא כפלית ((n,m) = 1 \implies \phi(nm) = \phi(n)\phi(m)), ומקיימת \phi(p^k) = p^{k-1}(p-1).

(\mathbb{Z}/n\mathbb{Z})^{\times} – החבורה הכפלית של המספרים השלמים מודולו n. היא מכילה \phi(n) איברים.

a(b)a מודולו b.

——–

1. משפט וילסון – זווית אלמנטרית, הוכחות אלמנטריות והכללה טבעית

קודם כל, נציג את ההוכחה ה'שגרתית' של משפט וילסון. בגלל שמדובר בזהות מודולרית, (p-1)! \equiv -1 (p), טבעי לעבוד בחבורה הכפלית (והאבלית) (\mathbb{Z}/p\mathbb{Z})^{\times}=\{\overline{1},\overline{2},\cdots,\overline{p-1}\}.
כשעובדים בחבורה זו, אפשר לחשוב על (p-1)! מודולו p כעל מכפלת כל האיברים בחבורה. כל איבר g בחבורה שאינו מסדר 1 או 2 מתבטל עם g^{-1} (השונה מg) שמופיע גם כן במכפלה. (למעשה, \prod_{g\in G} g=\prod_{g^{2} = 1}g בכל חבורה אבלית סופית.) האיברים שנשארים הם הפתרונות של x^2 \equiv 1 (p) , כלומר שורשי הפולינום x^{2}-1=(x-1)(x+1)\in(\mathbb{Z}/p\mathbb{Z})[x] , שהם \{\overline{1},\overline{-1}\}. לכן (p-1)! = \equiv 1 \cdot (-1) \equiv -1 (p) כאשר p \neq 2 (כי אז -1 \neq 1), ואת המקרה p=2 אפשר לוודא ידנית.

שימו לב – ניצלנו בין השורות את המבנה החיבורי, ולא רק הכפלי, של השדה הסופי \mathbb{Z} / p\mathbb{Z} – זה קרה כשהשתמשנו בזה שפירוק פולינומים מעל השדה הזה הוא יחיד דבר שנובע מכך ששדה הוא בפרט תחום שלמות.

תרגילים

האיש והכופלים

ז'וזף-לואי לגראנז' (1736 – 1813), המתמטיקאי הצרפתי שבאמת הוכיח את משפט וילסון.

1. תרגיל מודרך – הכללת משפט וילסון:

א. חשבו את \sum_{g \in G} g עבור חבורה אבלית חיבורית G=\oplus_{i=1}^{k}\mathbb{Z}/m_{i}\mathbb{Z}. (זכרו שכל חבורה אבלית חיבורית איזומורפית לסכום ישר מהצורה הנ"ל.)
(רמז: צריך להסתכל על איברים מסדר 2, ובסוף התשובה תלויה רק בהאם יש בדיוק m_i זוגי אחד)

ב. הוכיחו את הגרסה הבאה של משפט השאריות הסיני: אם \prod_{i=1}^{k} p_i^{a_i} הוא הפירוק של n לחזקות של ראשוניים שונים, אז

(\mathbb{Z} / n\mathbb{Z})^{\times} \cong \prod_{i=1}^{k} (\mathbb{Z} / p_{i}^{a_i} \mathbb{Z} )^{\times}

כאשר האיזומורפיזם נתון ע"י x \mapsto (x(p_1^{a_1}),x(p_2^{a_2}),\cdots,x(p_k^{a_k})).

ג. (גאוס) חשבו את \prod_{g\in(\mathbb{Z}/n\mathbb{Z})^{\times}}g\text{ mod }n. אפשר להשתמש בטענה הבאה:
אם p ראשוני אי-זוגי, אז (\mathbb{Z} / p^{k} \mathbb{Z})^{\times} חבורה ציקלית מגודל \phi(p^k) = (p-1)p^{k-1}.
בנוסף, (\mathbb{Z} / 2^k \mathbb{Z})^{\times} איזומורפית ל-\begin{cases}    \mathbb{Z}/1\mathbb{Z} & \text{if }k=1\\  \mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2^{k-2}\mathbb{Z} & \text{if }k>1\end{cases} , כלומר, ציקלית אמ"מ k \le 2.

2. קריטריון ראשוניות

הראו שעבור n \ge 5 יש שני מקרים –  אם n פריק אז (n-1)! מתחלק ב-n, ואם n ראשוני אז (n-1)! שווה מינוס 1 מודולו n.

זה נותן קריטריון ראשוניות/פריקות לא מאוד יעיל.

3. זהות פולינומיאלית

הוכיחו בעזרת המשפט הקטן של פרמה את הזהות הפולינומיאלית x^{p-1} - 1 = \prod_{i=1}^{p-1} (x-i) (מודולו p), וע"י השוואת מקדם חופשי הוכיחו את משפט וילסון.

4. הוכחה קומבינטורית

א. נניח וחבורה סופית G פועלת על קבוצה סופית S משמאל, כלומר לכל g \in G יש פונקציה f_g מS לעצמה, כך ש-f_g \circ f_h = f_{gh} ו-f_{\text{id}} היא הזהות. בדר"כ במקום לכתוב f_g(s) כותבים פשוט g s.

נגדיר את המסלול (orbit) של s\in S בתור Gs = \{gs | g \in G \}. הראו שהיחס x \sim y אמ"מ x \in Gy הוא יחס שקילות על S, והסיקו מכך שאפשר לכתוב את S כאיחוד זר של מסלולים. הראו שגודלו של מסלול מחלק את הסדר של G.

ב. הסתכלו על קבוצת הפרמוטציות הציקליות של \mathbb{Z}/p\mathbb{Z}, כלומר פרמוטציות שמבנה המעגלים שלהן מורכב ממעגל יחיד. \mathbb{Z}/p\mathbb{Z} פועלת עליהן ע"י (c\pi)(x)=c+\pi(x-c), כלומר הצמדה ע"י x \to x-c.

  • מה הגדלים האפשרים של המסלולים?
  • כמה מסלולים מגודל 1 (נק' שבת) יש?
  • מה הקשר בין מספר נקודות השבת לגודל הקבוצה מודולו p? (רמז: יש שיוויון. למה?)

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

5. הוכחה נוספת של לגראנז'

אחת ההוכחות המקוריות של לגראנז', שמוזכרת בתזה האלמנטרית הזו: הוכיחו, קומבינטורית או אלגברית, את הזהות הבאה:

\forall a \in \mathbb{C}: n! = \sum_{i=0}^{n} (a-i)^n \binom{n}{i} (-1)^i

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

2. הפונקציה האקספוננציאלית של ארטין-הסה – טורי חזקות בשירות תורת המספרים

כעת נכתוב את משפט וילסון בצורה קצת אחרת, שאולי תראה קצת מאולצת אבל תתבהר בקרוב.
נחלק את (p-1)! + 1 בp!, ונקבל את השבר \frac{1}{p} + \frac{1}{p!}. בגלל שp! = p (p-1)! מתחלק פעם אחת בלבד ב-p (v_p(p!) = 1), כאשר כותבים את המספר הרציונלי הזה בתור שבר מצומצם \frac{a}{b}, מתקיים שה-p שמחלק את המכנה המשותף p! הצטמצם עם המונה (שהתחלק ב-p ממשפט וילסון), כלומר b לא מתחלק בp.
זה בדיוק אומר ש\frac{1}{p!} + \frac{1}{p} הוא p-שלם!
הערה: יתכן שa מתחלק ב-p, ובמקרה הנדיר הזה, p יקרא "ראשוני-וילסון". לדוגמא: \frac{1}{5}+\frac{1}{5!}=\frac{25}{120}=\frac{5}{24}, ולכן 5 הוא ראשוני-וילסון.

כעת נציג הכללה קטנה – מדובר בבעיה מתוך מבחן (משנה זו) בתורת המספרים במחנה של הנבחרת הישראלית במתמטיקה (זו השאלה הראשונה ש'המצאתי' לתחרות מסוג זה):

הוכיחו שאם p ראשוני גדול משתיים, וכותבים את \frac{1}{(2p)!}+\frac{1}{2p^{2}}+\frac{1}{p\cdot p!} בתור שבר מצומצם מהצורה \frac{a}{b}, אז p \nmid b.

שימו לב לדימיון לשבר \frac{1}{p!} + \frac{1}{p}. נסו ידכם בהוכחה – אפשר להוכיח זאת ישירות: לכתוב את המספר הרציונלי כשבר עם מכנה משותף (2p)!, שמתחלק בדיוק פעמיים בp. לכן צריך להראות שהמונה מתחלק לפחות פעמיים ב-p. פותחים סוגריים במונה ועובדים מודולו p^2. מקבלים, מודולו p^2, שהמונה שווה ל-((p-1)! +1)^2 (שבבירור מתחלק ב-p^2 ממשפט וילסון), ועוד (p-1)! p \sum_{i=1}^{p-1} i (שגם מתחלק ב-p^2 כי הסכום \sum_{i=1}^{p-1} i מתחלק ב-p עבור p אי-זוגי). השלימו את הפרטים!

מאיפה מגיעים 2 השברים שהצגנו בינתיים? שניהם מקדמים של הטור הפורמלי הבא:

E_{p}(x)=\exp(\sum_{i\ge 0}\frac{x^{p^{i}}}{p^{i}}) = \exp(x + \frac{x^p}{p} + \cdots )

משפט וילסון מתקבל מתוך המקדם של x^p והשאלה האחרונה מהמקדם של x^{2p} (פתחו סוגריים והיווכחו). אפשר לכתוב מקדמים גבוהים יותר מפורשות (אם כי זה הולך ומסתבך, הולך ומסתבך). כל מקדמי הטור הזה הם p-שלמים, ובטענה זו נתרכז בשאר הפוסט.

הטור הזה נקרא Artin-Hasse Exponential (על שם 2 האלגבראיסטים שחקרו אותו), והוא בעל שימושים בשדות מקומיים ומבנים אלגבריים אחרים.

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

גאון מודרני

אמיל ארטין (1898 – 1962). אחת הדמויות המרכזיות במתמטיקה של המאה הקודמת.

3. חבורות – משפט קושי ומשפט פרובניוס

משפט קושי

נתחיל בלדבר על משפט קושי, ממנו נקבל הוכחה נוספת למשפט וילסון (רביעית להיום!).

משפט קושי: אם G חבורה סופית ו-p מחלק את הסדר שלה, אז קיים איבר g \in G מסדר p.

משפט זה הוא ניסיון לכיוון ההפוך של משפט לגראנז', שאומר בין השאר שסדר של איבר מחלק את סדר החבורה.
אי אפשר לקבל תוצאה יותר טובה מבחינת משפט בכיוון ההפוך: לכל מספר טבעי k>1, החבורה (\mathbb{Z}/p\mathbb{Z})^{k} היא מסדר p^k אבל אין בה איברים מסדר p^i, עבור 1 < i < k. עם זאת, משפטי סילו נותנים מידע מעניין מאוד על גדלים של תתי-חבורות של G (אם p^k | |G| אז יש תת-חבורה בגודל p^i לכל 0 \le i \le k). אפשר לנסח את המידע הזה בצורה הבאה:

p | |G| אמ"מ קיים איבר מסדר p

p^k | |G| אמ"מ קיימת תת-חבורה מסדר p^k (עבור k=1 מקבלים שקיים איבר מסדר p)

למשפט קושי יש שימושים רבים, ביניהם – אפיון החבורות מסדר pq כאשר p,q ראשוניים שונים. לעוד דוגמאות עיינו במאמר הזה.

אני אציג הוכחה פשוטה ומקסימה למשפט קושי. יש לו גם הוכחה סטנדרטית, שהיא יחסית טבעית אך מסורבלת – יש בה מושגים פחות בסיסיים מאלו המופיעים בהוכחה שאציג, והיא הגיעה 100 שנים לפני ההוכחה המפושטת, של ג'יימס מק'קיי. ההוכחה של קושי תופיעה בתרגילים, ורצוי לעבור עליה (היא מהווה הכנה טובה למשפט פרובניוס שיופיע בהמשך).

למה: אם x_1 x_2 \cdots x_n = 1 אז  x_{i}x_{i+1}\cdots x_{n}x_{1}\cdots x_{i-1}=1. הוכחה: תכפלו את השיוויון הראשון משמאל ב(x_1 x_2 \cdots x_{i-1})^{-1} ומימין בx_{1}\cdots x_{i-1}. \blacksquare

הוכחת משפט קושי: תהי G חבורה מסדר המתחלק בp. נספור בשתי דרכים שונות את מספר הפתרונות למשוואה x_1 x_2 \cdots x_p = 1 בG. החבורה \mathbb{Z} / p \mathbb{Z} פועלת על קבוצת הפתרונות באמצעות סיבוב, כלומר a(x_{1}\cdots x_{p})=(x_{1+a}\cdots x_{p}x_{1}\cdots x_{a}). גודל מסלול חייב לחלק את גודל החבורה, כלומר את p. על כן יש 2 סוגים של מסלולים: מגודל p (לא מעניינים כ"כ) ומגודל 1, המתאימים לפתרונות המקיימים x_{1}=x_{2}=\cdots=x_{p}. זה בדיוק מספר הפתרונות ל-x^p = 1, כלומר מספר האיברים מסדר p בדיוק, ועוד 1 (איבר היחידה). קיבלנו שגודל קבוצת הפתרונות מודולו p הוא 1 + מספר האיברים מסדר p.

מצד שני, כל בחירה של x_1, x_2, \cdots, x_{p-1} קובעת את x_p בצורה אחת ויחידה (x_{p}=(x_{1}\cdots x_{p-1})^{-1}), כלומר הקבוצה היא מגודל |G|^{p-1}=0(p). סה"כ, מספר האיברים מסדר p שווה ל-1 מודולו p, ובפרט אינו 0. \blacksquare

נשים לב שקיבלנו על הדרך תוצאה אלגנטית שתעסיק אותנו עוד בהמשך:

מספר הפתרונות לx^ p = 1 מתחלק בp (כאשר p | |G|).

קבלת משפט וילסון בעזרת חבורת הסימטריה

נראה מה קורה כשמפעילים אותה על חבורת הסימטריה S_p. מספר הפתרונות למשוואה x^p = 1 הוא (p-1)! + 1: פרמוטציות שהן מעגל ופרמוטציית היחידה. לפי משפט קושי, ביטוי זה מתחלק בp וקיבלנו את משפט וילסון!

תרגיל מודרך – ההוכחה המקורית של משפט קושי

א. ראשית הוכיחו אותו עבור חבורה אבלית. (מותר להשתמש במשפט המבנה של חבורות אבליות סופיות.)

ב. נגדיר את Z(G) להיות קבוצת איברי G המתחלפים עם כל איברי G. הוכיחו שזו תת-חבורה אבלית של G.

ג. נגדיר את Z_x להיות קבוצת איברי G המתחלפים עם x. הוכיחו שזו תת-חבורה ושהיא מכילה את <x>:=\{x^{i}|i\in\mathbb{Z}\}.

ד. נסתכל על הפעולה הבאה של G על G: gx = g^{-1} x g, כלומר פעולת הצמדה. האיברים במסלול של x הם האיברים הצמודים לו. הראו ש-|Gx|=|G|/|Z_{x}|. הראו שהפעולה מוגדרת היטב גם כאשר היא לא על כל G אלא רק על G \setminus Z(G).

ה. כעת נוכיח את משפט קושי באינדוקציה על גודל החבורה. אנחנו רוצים להראות שלכל n טבעי, אם |G| = np אז קיים איבר מסדר p בG.
עבור n=1 הטענה נכונה כי החבורה בהכרח איזומורפית ל\mathbb{Z}/p\mathbb{Z} (כל איבר שהוא לא איבר היחידה הוא מסדר p ולכן יוצר).
נניח כי הטענה נכונה לכל חבורה מגודל pk עבור k \le n. כעת תהי G חבורה מסדר p(n+1), ונרצה להוכיח את הטענה עבורה. יש 3 מקרים:

אם היא אבלית, סיימנו. אחרת, S = G \setminus Z(G) קבוצה לא ריקה.

אם קיים x\in S כך שp||Z_{x}|, אז סיימנו כי Z_x תת-חבורה של G, מסדר המתחלק בp וקטן מp(n+1).

המקרה הנותר הוא שלכל x \in S מתקיים p\nmid|Z_{x}|. נסתכל על S. נשים לב שG פועלת על S בעזרת הצמדה. לכן אפשר להציג את S כאיחוד זר של מסלולים. המסלול של x הוא מגודל \frac{|G|}{|Z_x|}, ולכן, p||G|,p\nmid|Z_{x}|\implies p| \frac{|G|}{|Z_x|} = |Gx|, ולכן |S| = |G| - |Z(G)| מתחלק ב-p, ומכאן Z(G) תת-חבורה מסדר המתחלק ב-p והיא אבלית, וסיימנו.

משפט פרובניוס

את משפט קושי אפשר להכליל באופן משמעותי בכיוון הבא: בהוכחה שמנו לב שמספר הפתרונות ל-x^p = 1  (איברים מסדר המחלק את p) הוא כפולה של p. מסתבר שבאופן כללי,

משפט פרובניוס: אם n | |G|, אז מספר הפתרונות ל-x^n = 1 הוא כפולה של n

נסמן את מספר הפתרונות הזה בתור f_n(G). (הפונקציה מוגדרת גם אם n \nmid |G|.) נעקוב אחר הוכחה אלמנטרית של משפט פרובניוס המבוססת על ההרצאה הזו – לא פירטתי כל שלב, אז מלאו את הפרטים החסרים:

למה א': יהי g \in G מסדר m \cdot n כאשר (n,m) = 1. הוכיחו שקיים לg פירוק אחד ויחיד מהצורה g = xy = yx כאשר ord(x) | n, ord(y) | m. (רמז: נסו x,y שהם חזקות של g.) הוכיחו שפירוק זה מקיים דרישה חזקה יותר: ord(x) = n, ord(y) = m.

למה ב': יהי p|n, ונסמן ב-q = p^{v_p(n)} את חזקת p המקיימת q||n. מספר הפתרונות ל-x^n = 1 שווה \sum_{t^{n/q}=1}f_{q}(Z_{t}) (רמז: סיפרו כל פיתרון לx^n = 1 בתור זוג (t,s) כך ש-st=ts,ord(s)|q,ord(t)|\frac{n}{q}).

אם נסמן ב-T קבוצת נציגים של \{ t \in G | t^{n/q} = 1 \} לפי יחס שקילות של צמידות, נקבל:

f_{n}(G)=\sum_{t\in T}[G:Z_{t}]f_{q}(Z_{t})

למה ג': אם p^k | |G|, וH תת-חבורה של G המקיימת את משפט פרובניוס לכל n שהוא חזקה של p, אז p^{k}|[G:H]f_{p^{k}}(H). (רמז: [G:H] = \frac{|G|}{|H|} )

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

למה ד': מספר האיברים מסדר n בדיוק ב-G הוא כפולה של \phi(n). (רמז: ord(x)=n\implies(\forall i:(i,n)=1\leftrightarrow ord(x^{i})=n) )

מכאן אפשר להסיק משהו מגניב – אם משפט פרובניוס נכון בחבורה מסויימת G עבור p^k | |G| כאשר k>1, אז הוא נכון גם לp^{k-1}:

f_{p^{k-1}} (G) = f_{p^k} (G) - \#\text{elements of order }p^k

הראנו עכשיו שהמחוסר מתחלק ב\phi(p^k) שמתחלק בp^{k-1}. לכן אגף שמאל הוא הפרש 2 מספרים המתחלקים בp^{k-1}, כלומר מתחלק גם הוא בp^{k-1}.

למה ה': יהי p ראשוני. נרצה להוכיח את משפט פרובניוס עבור חזקות של ראשוני p. לפי האבחנה האחרונה, דיי להוכיח זאת עבור החזקות ה'מקסמיליות': q = p^{v_p(n)} || n = |G|.

נעשה זאת באינדוקציה על n. עבור n=1 וכל n שזר לp, הטענה טריוויאלית (כי אז q = 1). נניח שהטענה נכונה לכל חבורה מגודל n \le k. תהי חבורה מגודל k+1 (המתחלק ב-p). לפי למה ב' (עם q= p^{v_p(G)}):

|G| = f_{|G|} (G) = \sum_{t \in T} [ G : Z_t ] f_q(Z_t) = \sum_{t \in T \cap Z(G)} [G:Z_t] f_q(Z_t) + \sum_{t \in T \setminus Z(G)} [G:Z_t] f_q(Z_t)

בסכום השני באגף ימין, מתקיים |Z_t| < |G|, ואפשר להשתמש בהנחת האינדוקציה ובלמה ג' כדי להסיק שהוא מתחלק בq = p^{v_p (G)}. בנוסף, גם אגף שמאל מתחלק בq.

אנחנו מסיקים שהסכום הראשון מתחלק בq. לכל מחובר בו מתקיים Z_t = G ולכן הסכום שווה ל|T \cap Z(G)| f_q(G). הקבוצה T \cap Z(G) היא תת-חבורה של Z(G), המורכבת רק מאיברים שהסדר שלהם מחלק את \frac{n}{q}, ובפרט זר לp, וממשפט קושי נובע שגודלה של תת-החבורה לא מתחלק בp. על כן, f_q(G) מתחלק בq, כמו שרצינו.

למה ו' ואחרונה: סיום. נניח ש-n מחלק את G. לכל חזקת ראשוני q המחלקת את n מתקיים (לפי למה ב'): f_{n}(G)=\sum_{t\in T}[G:Z_{t}]f_{q}(Z_t). לפי למה ה' ולמה ג', כל אחד מהמחוברים מתחלק בq. זה נכון לכל q||n, לכן n|f_{n}(G), מש"ל. \blacksquare

אז ראינו שמשפט פרובניוס עבור n=p נותן מידע על המקדם של x^p בE_p. איך באופן כללי אני מסיק מתוך משפט פרובניוס מידע על שאר המקדמים?

4. פונקציות יוצרות אקספוננציאליות ואבי כל הפאנצ'ים

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

בהרבה סיטואציות קומבינטוריות יש לנו פונקציה מגניבה F_{S} (למעשה, פונקטור…) שמתאימה לכל קבוצה סופית A אוסף מבנים קומבינטוריים מסוג מסויים עליה (שיקרא S).
לדוגמא:

  • כל הפרמוטציות על A
  • כל העצים עם קבוצת קודקודים A
  • ועוד…

דרישה טבעית היא שהפונקציה F_S תכבד איזומורפיזמים בין 2 קבוצות: אם A \cong B אז F_{S}(A)\cong F_{S}(B) באופן טבעי. מכאן נובע שהגודל |F_{S}(A)| הוא פונקציה של |A| בלבד. לדוגמא, עבור פרמוטציות מתקיים |F_S(A)| = |A|!.

נסמן ב-a_n^S את |F_{S}(A)| עבור |A|=n. ניסיון של אנשי קומבינטוריקה מראה שכדאי להסתכל על טור החזקות הפורמלי f_{S}(x)=\sum_{n\ge0}\frac{a_{n}^{S}}{n!}x^{n}, שנקרא "הפונקציה היוצרת האקספוננציאלית של S". חשוב לציין, לכל הדואגים: כל ההתעסקות עם טורים בחלק זה תהיה פורמלית.

שאלת חימום: הראו שהפונקציות היוצרת האקספוננציאלית של פונקציית הפרמוטציות היא \frac{1}{1-x}.

מה קורה כשמכפילים 2 פונקציות כאלו? מקבלים מעין קונבולוציה שניתן לה משמעות קומבינטורית מעניינת:

f_{S_{1}}(x)f_{S_{2}}(x)=\sum_{i\ge 0, j\ge 0} \frac{a_{i}^{S_1}}{i!} x^i \frac{a_{j}^{S_2}}{j!} x^j = \sum_{n \ge 0}\frac{\sum_{i+j=n}\binom{n}{i}a_{i}^{S_{1}}a_{j}^{S_{2}}}{n!}x^{n}

מה הביטוי המוזר במונה? "קונובולוציה בינומית" של 2 הסדרות של S_1 ו-S_2. מה היא סופרת? את מספר הדרכים לחלק קבוצה בגודל n לשני חלקים, על חלק אחד לשים מבנה מסוג S_1 ועל השני מבנה מסוג S_2. מבנה המכפלה הזה מסומן S_1 \times S_2, ובעצם קיבלנו שf_{S_1} \times f_{S_2} = f_{S_1 \times S_2}. פורמלית,

F_{S_1 \times S_2}(A) = \coprod_{B \coprod C = A} F_{S_1}(B) \times F_{S_2}(C)

(הסימון \coprod מסמל איחוד זר.) ומה קורה כשמכפילים 3 פונקציות או יותר? דבר דומה: במונה יהיה מספר הדרכים לחלק קבוצה בגודל n לk חלקים, ולשים על החלק הi מבנה מסוג S_i.

כעת נניח F_S(\varnothing) = \varnothing, כלומר f_s(0)=0. איך נראה המקדם של \frac{x^n}{n!} ב-\frac{1}{k!}f_{S}^{k}(x)? המונה סופר את מספר הדרכים לחלק קבוצה לk תתי-קבוצות, ועל כל אחת לתת-מבנה מסוג S. החלוקה בk! נובעת מכך שלא משנה הסדר (מי הראשונה ומי השנייה וכו'), ואנחנו לא רוצים לספור יותר מפעם אחת כל מבנה. לכן:

\sum_{k \ge 0} \frac{1}{k!} f_{S}^{k} = \exp(f_{S})

היא הפונקציה היוצרת האקספוננציאלית של מספר הדרכים השונות לחלק את A (קבוצה בגודל n) לאיחוד זר של קבוצות לא ריקות ועל כל אחת לשים מבנה מסוג S. הסכום האינסופי הפורמלי מוגדר היטב כי f_S(0) = 0, וכדי לחשב את n המקדמים הראשונים צריך את n המחוברים הראשונים בלבד (שאר המחוברים מתחלקים בx^n).

נסתכל כעת על E_p וננסה להבין מה היא סופרת. \sum_{k \ge 0} \frac{x^{p^k}}{p^k} = \sum_{k \ge 0} \frac{x^{p^k}}{(p^k)!} (p^k - 1)! היא הפונקציה היוצרת האקספוננציאלית של פרמוטציות מעגליות מגודל p^k על קבוצה A. לכן המקדם של \frac{x^n}{n!} ב-E_p יהיה מספר הדרכים לחלק קבוצה מגודל n לתתי-קבוצות מגודל חזקה של p, ועל כל אחת לשים פרמוטציה מעגלית, כלומר מספר הפרמוטציות על קבוצה בגודל n המורכבות ממעגלים שגודלם חזקות p. זה בדיוק מספר האיברים בS_n מסדר שהוא חזקה של p (סדר של פרמוטציה שווה ל-LCM של אורכי מעגליה). אם q= p^{v_p(n!)} היא החזקה המקסימלית של p המחלקת את n, אז זה למעשה מספר הפתרונות למשוואה x^q = 1 בחבורה. ממשפט פרובניוס לגבי החבורה S_n, v_{p}(|\{x\in G|x^{q}=1\}|)\ge v_{p}(q)=v_{p}(n!), כלומר המקדמים של E_p הם p-שלמים, מש"ל.

תרגיל 7: הוכיחו קומבינטורית כי \exp( -\ln( 1-x))=\frac{1}{1-x} (בלי חישובים!)

תרגיל 8: נניח ו-P היא קבוצת ראשוניים. נסמן ב\mathbb{N}_{P} את קבוצת הטבעיים שהגורמים הראשוניים שלהם מוכלים ב-P. הוכיחו שהמקדמים של \exp_{P}(x) = \exp(\sum_{n \in \mathbb{N}_{P}} \frac{x^n}{n}) הם p-שלמים לכל p \in P. מה קורה כש-P היא קבוצת כל הראשוניים?

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

שאלות? אם יש, אז בתגובות. אל תתביישו.

על החתום,
אופיר

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

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

אודות Ofir Gorodetsky

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

6 תגובות על הקסם של הפונקציה האקספוננציאלית של ארטין-הסה (חלק 1/2)

  1. TornMoon הגיב:

    אני לא יודעת בקשר לפונקציה האקספוננציאלית, אבל אתה מקסים 3> ~

  2. אמוץ אופנהיים הגיב:

    אני יודע שעד המקדם של p בחזקת 3 אפשר להראות באופן אלמנטרי שכל המקדמים הם p-שלמים.
    האם אפשר להראות לכל מקדם שהוא p-שלם בצורה פשוטה(ע"י עשיית מכנה משותף )?

    • gorofir הגיב:

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

  3. דורון הגיב:

    הוכחה יפהפיה. עד הרגע האחרון לא הבנתי מה הקשר בין משפט פורבניוס (שבמקרה הכרתי מהספר של מרשל הול) למעריך הזה. אהבתי את הפירוש הקומבינטורי למעריך של פונקציה יוצרת. תודה רבה!
    הערות\תובנות:
    את 1ד אפשר לעשות בלי לדעת את המבנה המדויק של (Z/p^kZ)* – שכמובן טוב להכיר לידע כללי – די לדעת כמה שרשים יש לפולינום (x-1)(x+1) מודולו p^k. אם p>2 אז רק אחד משני הגורמים יכול להתחלק בp ואז הפתרונות הם רק +-1, וגם p=2^k לא קשה מדי לחשב השרשים במפורש. זה טוב לעצלנים שלא זוכרים איך עושים את 1ג 🙂
    4ב בהגדרת הפעולה צריך להיות כתוב באגף שמאל x+c ולא סתם x (הפעולה "מזיזה" גם את הקלט ולא רק את הפלט)
    5 שגיאת דפוס – הסכום צריך להיות עד n ולא עד a. מצאתי פתרון יפה עם הכלה הפרדה, שעובד על a שלם גדול מ n, אבל כמובן נובעת הנכונות לכל מספר a, אפילו מרוכב (אפשר להוריד את ההגבלה a>=n בשאלה – אני מניח ששמת בכוונה כדי להתמקד במקרה הזה).

    • gorofir הגיב:

      תודה, אני שמח לשמוע. עם זאת, בפוסט ההמשך יש גישה טבעית יותר לבעיה (אם רוצים להוכיח שמספרים הם p-שלמים נשמח שכדאי לעבוד עם p-אדים).
      בספר Enumerative Combinatorics Vol II של Richard Stanely עושים דברים מאוד מרשימים עם פונקציות יוצרות אקספוננציאליות, עונים על שאלות קשוחות שקשורות לS_n.
      אני מחפש עוד שימושים למשפט פרובניוס – אם אתה מגלה כאלו הייתי רוצה לדעת.
      לגבי ההערות:
      1ד – קיצור דרך מגניב. שיניתי את 1ג לאופציונאלי P:
      4ב – שנינו טעינו, זו הצמדה: pi(x-c)+c או pi(x+c)-c.
      5 – נכון, תיקנתי. למעשה לא ברור לי למה כתבתי את ההגבלה – הרי כיוונתי להוכחה של גזירה דיסקרטית שאין צורך להגביל בה את a. ההוכחה עם הכלה-הפרדה היא טבעית, ובעצם מזכירה את התופעה שהוזכרה בפוסט המקורי על גזירה דיסקרטית: אפשר לקבל זהויות ע"י סיפור או ע"י גזירה.

      גיליתי כמה typos בחלק האחרון של הפוסט, מקווה שהוא היה ברור בכל מקרה.

  4. דורון הגיב:

    זה השימוש הראשון של משפט פורבניוס שאני נתקל בו, אם אמצא משהו אספר לך.
    שכחתי לכתוב קודם: אחרי המשפט "למעשה, 2 השברים שהוצגו בפוסט הם מקדמים של טור פורמלי:" מוגדר E_p, והסכום צריך להיות מ0 ולא מ1 (כך שהביטוי הראשון בסכום הוא x)

כתיבת תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s