העתקת מביוס מסדר 3 ושימושים

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

העתקות מביוס מגיעות מאנליזה מרוכבת. מדובר בהעתקות מהמרוכבים לעצמם, מהצורה הבאה:

z \mapsto \frac{az+b}{cz+d}

כאשר a,b,c,d הם 4 פרמטרים מרוכבים המקיימים ad \neq bc (אחרת ההעתקה מתנוונת להעתקה קבועה). לדוגמא, הזזות (z \mapsto z+c), מתיחות (z \mapsto \lambda z) ואינוורסיה (z \mapsto \frac{1}{z}) – כולן דוגמאות להעתקות מביוס.

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

כמו שהן, ההעתקות הן חח"ע אבל לאו דווקא על. בשביל לקבל העתקות על שגם מוגדרות בכל נקודה, מרכיביםמרחיבים את המרוכבים \mathbb{C} ומוסיפים להם את "הנקודה באינסוף", \infty: \widehat{\mathbb{C}} = \mathbb{C} \cup \{ \infty \}. למרחב הזה יש מספר שמות, אנחנו נקרא לו הישר הפרוייקטיבי ונסמנו P^1(\mathbb{C}) אך יש שיקראו  לו "הספירה של רימן". אם אתם לא מכירים מושגים אלו – אל תיראו, לא נזדקק להם.
אנחנו חייבים להסביר איך ההעתקות הללו מתנהגות כשמציבים בהן את אותה "נקודה באינסוף" וב--\frac{d}{c} (בה כביכול ההעתקות לא מוגדרות). נפרק לשני מקרים:

  • אם c \neq 0 אז \infty עוברת ל-\frac{a}{c} ו--\frac{d}{c} עוברת ל-\infty.
  • אחרת, \infty עוברת לעצמה.

לדוגמא, z \mapsto \frac{1}{z} מעבירה את 0 ל-\infty ולהיפך, ו-z \mapsto \frac{z}{z+1} מעבירה את מינוס 1 ל-\infty ואת \infty ל-1.
(בסוף הפוסט נציג הסבר יפה וגיאומטרי לנקודה באינסוף, ללא פירוק למקרים.)

אנחנו לא נתעניין בהעתקות המרוכבות האלו, אלא בגרסה דיסקרטית שלהן – העתקות z \mapsto \frac{az+b}{cz+d} על הקבוצה הסופית P^1(\mathbb{F}_{p}) = \mathbb{F}_{p} \cup \{ \infty \}.

ההעתקה הספציפית שמעניינת אותנו היא:

z \mapsto \frac{1}{1-z}

נסמן העתקה זו ב-\mu. נשים לב ש-1 עובר ל-\infty וש-\infty עובר ל-0.
להעתקה זו יש תכונה מיוחדת מאוד: היא מסדר 3. כלומר, אם נפעיל את \mu שלוש פעמים נקבל את העתקת הזהות. אפשר לראות זאת ע"י חישוב:

\mu(\mu(x)) = \frac{1}{1-\mu(x)} = \frac{1-x}{1-x-1} = \frac{x-1}{x}

\mu(\mu(\mu(x))) = \frac{1}{1-\frac{x-1}{x}} = x

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

וכעת נמשיך בניסוח הבעיות:

בעיה ראשונה – הדדיות ריבועית עם q=3:

נוכיח עם ההעתקה \mu את המקרה הפרטי הבא של הדדיות ריבועית:

\left(\frac{p}{3}\right) \left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2} }

תזכורת: בחבורה הציקלית \mathbb{F}_{p}^{\times}, עבור p ראשוני אי-זוגי, יש 2 סוגים של איברים: ריבועים ולא-ריבועים (ויש מספר שווה משניהם, \frac{p-1}{2}). אפשר לראות שהריבועים הם בדיוק הגרעין של ההעתקה x \mapsto x^{\frac{p-1}{2}} \mod p.
כדי לחקור את הריבועים, נוח להשתמש ב"סימן לז'נדר": פונקציה של 2 משתנים, a (שלם) ו-p (ראשוני) שמסומנת \left(\frac{a}{p}\right) ומקבלת 3 ערכים אפשריים:

  • 1 (אם a ריבוע מודולו p),
  • -1 (אם a אינו ריבוע מודולו p),
  • ואפס (אם a מתחלק ב-p)

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

\left(\frac{a}{p}\right) = a^{\frac{p-1}{2}} \mod p

חוק ההדדיות הריבועית הוא הקשר הבא בין סימני לז'נדר מודולו p ומודולו q:

\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \frac{q-1}{2}}

כאשר p,q ראשוניים אי-זוגיים שונים. כדי להבין יותר טוב מה זה אומר, נשים לב שיש 2 מקרים:

  • אם p \equiv 1 \mod 4 או q \equiv 1 \mod 4, אז אגף ימין הוא 1, כלומר יש פיתרון למשוואה  x^2 = p \mod q אמ"מ יש פיתרון למשוואה x^2 = q \mod p.
  • אחרת, אגף ימין הוא מינוס 1, כלומר יש פיתרון למשוואה  x^2 = p \mod q אמ"מ אין פיתרון למשוואה x^2 = q \mod p.

בעיה שנייה – מטריצה מסדר שלוש:

עבור p ראשוני, נסתכל על המטריצה הבאה: A_{i,j} = \binom{i+j}{j} עם 0 \le i,j \le p-1. מתקיים השיוויון המסתורי הבא, מודולו p:

A^3 \equiv I \mod p

למה? מסתבר שזה קשור ישירות לההעתקה \mu.
מה הקשר?! סבלנות, ינוקא.

הבעיה הראשונה

יש לנו את ההעתקה \mu, העתקה מסדר 3 – עובדה שמתקיימת בכל שדה (רציונלים, מרוכבים, שדות סופיים). אנחנו נחשוב עליה מעל \mathbb{F}_{p}.

אוקיי, מה אפשר לעשות עם העתקה מסדר סופי? אם נחשוב עליה כפרמוטציה על הישר הפרוייקטיבי, ונפרק אותה למעגלים, נגלה שאורך המעגלים מחלק את סדר ההעתקה (עובדה כללית), כלומר יש מעגלים באורך 1 (נקודות שבת) ומעגלים באורך 3. בפרט, אם נסתכל על גודל הקבוצה (שהוא p+1) מודולו 3, נקבל את מספר נקודות השבת מודולו 3.

כרגע אתם צריכים להרגיש שהקומבינטוריקה הנ"ל מקדמת אותנו לעבר איזשהו שיוויון לא-טריוויאלי. הדבר ההגיוני הבא הוא לספור את נקודות השבת ישירות. x היא נקודת שבת אמ"מ x = \frac{1}{1-x}, כלומר:

x^2 - x +1 = 0 \mod p

נשלים לריבוע (טריק סטנדרטי) ונכפיל ב-4 (בשביל הנוחות) ונקבל ששיוויון זה שקול ל-

(2x-1)^2 = -3 \mod p

  • אם -3 שארית ריבועית מודולו p, יש 2 פתרונות.
  • אם הוא לא, יש 0 פתרונות.
  • ואם p=3 אז יש פיתרון יחיד.

שלושת המקרים מתומצתים באמצעות \left( \frac{-3}{p} \right) + 1. קיבלנו:

p +1 \equiv \left( \frac{-3}{p} \right) + 1 \mod 3

נחסר 1 משני האגפים, ונשים לב שבאגף שמאל כתוב p \equiv p^{\frac{3-1}{2}} \equiv \left( \frac{p}{3} \right) \mod 3 (קריטריון אוילר). זה נותן שזוג המספרים \left( \frac{-3}{p} \right), \left( \frac{p}{3} \right) שקולים מודולו 3. בגלל שהם חיים בין מינוס 1 ל-1, הם בהכרח שווים:

\left( \frac{-3}{p} \right) = \left( \frac{p}{3} \right)

ואחרי פישוט זה יוצא בדיוק חוק ההדדיות הריבועית עבור q = 3 (השתמשו בכפליות של סימן לז'נדר ובכך ש-\left( \frac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}). \blacksquare

מגניב ואלגנטי, לא כך?

שאלה טבעית היא: האם אפשר להכליל הוכחה זו לעוד מקרים פרטיים של חוק ההדדיות הריבועית? לפחות באופן נאיבי – לא ניתן. אנחנו זקוקים להעתקת מביוס עם מקדמים שלמים שהסדר שלה סופי, והסדרים האפשרים הם רק 1, 2, 3 ו-6. זו לא טענה טריוויאלית ובסוף הפוסט אני נותן כלים להתמודד איתה.

הבעיה השנייה

(ההוכחה הנ"ל מבוססת על מאמר של William C. Waterhouse )

נסמן ב-S את אוסף הפונקציות מהשדה \mathbb{F}_{p} לעצמו. בהינתן f \in S , אפשר להסתכל על ההעתקה הלינארית L: f \mapsto f \circ \mu, כלומר הרכבה עם \mu.

העתקה זו היא מסדר 3: אם מפעילים את L שלוש פעמים על f, מקבלים חזרה את f כי \mu מסדר 3, כמו שכבר ראינו. אנחנו נחשב את המטריצה המייצגת של L בבסיס מאוד ספציפי, אבל לפני כן – נתייחס לנקודה שטאטאנו מתחת לשטיח: הפונקציה L(f) לא מוגדרת על 1, כי \mu(1) = \infty.

מטפלים בבעיה הזו עם הטריק הבא: נרחיב כל פונקציה f על השדה \mathbb{F}_{p} לפונקציה על \mathbb{F}_{p} \cup \{ \infty \} = P^1(\mathbb{F}_{p}) באופן הבא: f(\infty) = -\sum_{x\in \mathbb{F}_{p}} f(x), כלומר סכום כל ערכי הפונקציה צריך לצאת 0. עכשיו אפשר להגדיר שהפונקציה L(f) בנקודה 1 נותנת את f(\infty).

תרגיל הבנה 1: הסבירו מדוע L(f)(\infty) = f(0).

לאחר שטיפלנו בנקודה הזו, נפנה לחישוב המטריצה המייצגת של L בבסיס מאוד ספציפי. הבסיס שנבחר הוא אוסף הפונקציות f_j(x) = x^j עבור j=0,1,\cdots, p-1. שנייה… למה זה בסיס?!
אז ככה: המימד של L הוא p כי פונקציה נקבעת לפי ערכיה על p איברי השדה, לכן כדי להראות שהאוסף הנ"ל הוא בסיס צריך להראות אי-תלות. איך מראים אי-תלות? נסתכל על המטריצה ממימד p \times p שבמקום ה-i,j שלה כתוב f_i(j)=j^i (כלומר, השורה ה-i היא ערכי הפונקציה f_i) ונבדוק את הפיכותה. זו מטריצת ונדרמונדה, שהדטרמיננטה שלה יוצאת \prod_{p>i>j\ge 0} (i-j) \mod p, ובפרט שונה מאפס. אדיר.

שאלת הבנה: מה ההבדל בין f_0 ל-f_{p-1}? הרי, מהמשפט הקטן של פרמה, ידוע ש-x^{p-1} \equiv 1 \mod p לכל x \neq 1, אז נראה ששתי הפונקציות תמיד שוות 1 (חוץ מב-\infty, שם הן -p). אז לא, יש הבדל דק, והוא ההתנהגות ב-x=0: הפונקציה f_{p-1} מתאפסת באפס והפונקציה f_0 מקבלת שם את הערך 1.

אחרי שהבנו מה המרחב שלנו ומה הבסיס שלנו, הגיע זמן לחשב את המטריצה המייצגת. הפרוצדורה פשוטה: ניקח פונקציית בסיס, f_i(x) = x^i, נפעיל עליה את ההעתקה L, ונקבל פונקציה חדשה L(f_i)(x) = (\frac{1}{1-x})^i שאנחנו רוצים להביע בבסיס שלנו. נעשה זאת בעזרת המשפט הקטן של פרמה והבינום של ניוטון:

(\frac{1}{1-x})^i = (1-x)^{p-i-1} = \sum_{j=0}^{p-i-1} x^j (-1)^j \binom{p-1-i}{j}

המניפולציות הנ"ל נכונות עבור x \neq 1. קיבלנו:

L(f_i)(x) = \sum_{j=0}^{p-1} (-1)^j \binom{p-1-j}{i} f_j(x)

לכל x\in \mathbb{F}_{p} \setminus \{1 \}.

תרגיל הבנה 2: הראו שהשיוויון הנ"ל נכון גם עבור x=1. זה לא מיידי ודורש חישוב.

מתוך המניפולציות והתרגיל, קיבלנו שהמטריצה נראית כך: A_{i,j} = (-1)^j \binom{p-1-i}{j}. נפשט את הביטוי הזה ונקבל \binom{i+j}{j} (מודולו p כמובן):

\binom{p-1-i}{j} = \frac{(p-1-i)(p-2-i)\cdots (p-i-j)}{j!} = \frac{(-1-i)(-2-i)\cdots(-i-j)}{j!} = (-1)^j \frac{(i+j)(i+j-1) \cdots (i+2)(i+1)}{j!} = (-1)^j \binom{i+j}{j}

ובגלל ש-L \circ L \circ L = id נובע A^3 = I \mod p, מש"ל. \blacksquare

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

הבטחתי להסביר איך מפרמלים באופן גיאומטרי את הנקודה באינסוף בלי לפרק למקרים.

נתחיל בלהגדיר כמו שצריך את P^1(\mathbb{C}), הישר הפרוייקטיבי (הבנייה עובדת לכל שדה, לא רק למרוכבים). נסתכל על ישרים שעוברים דרך הראשית במישור \mathbb{C}^2. התורה על רגל אחת היא שכל ישר כזה מייצג נקודה בישר הפרוייקטיבי שלנו. יש 2 סוגים של ישרים:

  • ישרים מהצורה y= cx כאשר c\in \mathbb{C} (שמייצגים את כל האיברים של \mathbb{C})
  • הישר x=0 (שמייצג את הנקודה באינסוף – הנקודה באינסוף היא בעצם ישר עם שיפוע אינסוף)

כעת אפשר להגדיר יחס שקילות \sim על המישור המנוקב \mathbb{C}^2 \setminus{0}. שתי נקודות במישור זה יחשבו שקולות אם הן נמצאות על אותו ישר.
עוד דרך לחשוב על ישרים אלו: ישר הוא בעצם תת-מרחב ממימד 1, ושתי נקודות במישור שקולות אם הן  פורשות את אותו תת-מרחב ממימד 1.

עכשיו מגיע הפאנץ': העתקת מביוס f: z \mapsto \frac{az+b}{cz+d} בעצם לוקחת את הישר בעל שיפוע z, מפעילה עליו את הטרנספורמציה הלינארית A'_{f} = \begin{bmatrix} d & c \\ b &a \end{bmatrix} ומתרגמת חזרה למספר מרוכב ע"י חישוב השיפוע של הישר המתקבל.

למה, בעצם, זה מה שקורה? אם ניקח נקודה על הישר בעל שיפוע z, לדוגמא (1,z), ונפעיל עליה את הטרנספורמציה A'_{f}, נקבל:

\begin{bmatrix} d & c \\ b& a \end{bmatrix} \begin{bmatrix} 1 \\ z \end{bmatrix} = \begin{bmatrix} d+cz \\ b+az \end{bmatrix}

וקיבלנו נקודה על ישר ששיפועו \frac{az+b}{cz+d} – ועובדה הזו לא תלויה בנקודה ההתחלתית שבחרנו על הישר (כי הכפלה במטריצה הפיכה זו העתקה לינארית הפיכה וככזו מעבירה ישרים לישרים).

(הערה טכנית: המטריצה המתבקשת היא לא המטריצה שרשמתי אלא A_{f} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}. לא מפתיע לגלות שהמטריצות A_{f}, A'_{f} קשורות זו לזו – הן צמודות, וההצמדה נעשת ע"י המטריצה R = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, מטריצה שמשמעותה הגיאומטרית היא שיקוף לפי y=x. הפעלה של R על ישר נותנת ישר ששיפועו אחד חלקי השיפוע המקורי, ולכן אפשר להגיד שמה שההעתקה f עושה זה לקחת ישר עם שיפוע z, לשקף אותו לפי y=x ולקבל ישר עם שיפוע y= \frac{1}{z}, להפעיל עליו את A_{f} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, לקבל ישר חדש ולהחזיר את אחד חלקי השיפוע שלו. ומתמטית: f = g^{-1} \circ f' \circ g כאשר g(z) = \frac{1}{z} ו-f' מייצגת את ההעתקה z \mapsto \frac{a+bz}{c+ dz}, שממומשת ע"י המטריצה A_{f} = \begin{bmatrix} a & b \\ c & d \end{bmatrix}. )

מסקנה יפה של דרך הסתכלות זו היא שאם A_{f_1} = \begin{bmatrix} a & b \\ c& d \end{bmatrix} היא המטריצה המתאימה ל-f_1(z) = \frac{az+b}{cz+d} ו-A_{f_2} = \begin{bmatrix} a' & b' \\ c'& d' \end{bmatrix} היא המטריצה המתאימה ל-f_2(z) = \frac{a' z+b' }{c'z+d' }, אז A_{f_1} \cdot A_{f_2} היא המטריצה המתאימה ל-f_1 \circ f_2 . איך רואים זאת? נסמן ב-l(z) את ההעתקה שמעבירה מספר מרוכב (או אינסוף) לישר שיפועו \frac{1}{z}. ההעתקה f_1(z) היא l^{-1} \circ A_{f_1} \circ l, והרכבה של שתיים כאלו מכפילה את המטריצות:

(l^{-1} \circ A_{f_1} \circ l) \circ (l^{-1} \circ A_{f_2} \circ l) = l^{-1} \circ A_{f_1} A_{f_2} \circ l

וזה גם מסביר למה הרכבה של העתקות מביוס היא העתקת מביוס – עובדה לא טריוויאלית כשלעצמה.

דרך הסתכלות זו היא אלגנטית כי היא חוסכת פירוק למקרים: אם מתעלמים מעניין השיקוף (ההצמדה ע"י g(z) = \frac{1}{z}), אפשר לחשוב על העתקות מביוס בתור איברים של החבורה GL_2(\mathbb{C}) (מטריצות 2 על 2 הפיכות) שפועלים על תתי-מרחבים ממימד 1 של \mathbb{C}^2, כאשר הפעולה היא כפל מטריצה בוקטור (הוקטור הוא איזשהו איבר בתת-המרחב הרלוונטי שאינו וקטור האפס).

היא גם מאוד שימושית: העתקת מביוס שמיוצגת ע"י A = \begin{bmatrix} a & b \\ c &d \end{bmatrix} היא מסדר המחלק את n אם A^n פועלת טריוויאלית על \mathbb{C}^2 / \sim, כלומר A^n לא משנה שיפוע של נקודות. זה אומר שכל וקטור הוא וקטור עצמי של A^n (כי כל וקטור בהכרח עובר מתיחה), וזה תרגיל חביב לוודא שאלו יכולות להיות רק ההעתקות הסקלריות, כלומר A^n = \lambda I.
הסיבה ש-\mu היא מסדר 3 היא שהמטריצה \begin{bmatrix} 0 & 1 \\ -1 & 1 \end{bmatrix} בחזקת 3 נותנת את מטריצת הזהות.

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

אודות Ofir Gorodetsky

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

תגובה אחת על העתקת מביוס מסדר 3 ושימושים

  1. כנדרמון הגיב:

    תכונה מעניינת שלא ציינת – המטריצה A היא מטריצה "משולשית משנית עליונה" (לא יודע אם יש לזה מושג אמיתי), כלומר, איבריה שווים ל-0 מודולו p מתחת לאלכסון המשני. קל לראות זאת מתוך הנוסחה המפורשת למקדמים בתור i+j בחר j. בנוסף, על האלכסון המשני, איבריה הם פלוס ומינוס 1 לסירוגין. מנגד, המטריצה A^2 היא משולשית משנית תחתונה – אפשר להוכיח ישירות קומבינטורית, או באמצעות הטריק של המביוס (ההפעלה של A^2 שקולה להרכבה על ריבוע ההעתקה), שהאיבר במקום ה-(i,j) במטריצה A^2 הוא z (-1)^(p-1-j) (i choose p-1-j) z, וקל לראות שזה אכן 0 מעל האלכסון המשני, וכן שעל האלכסון המשני גם איברי A^2 הינם פלוס ומינוס 1 לסירוגין.

    ורק משילוב שתי העובדות האלה על המשולשיות של A ו-A^2, ובלי להתייחס לערכיהן מעבר לאלכסון המשני, ניתן להסיק בקלות ש-A^3 חייבת להיות הזהות!

כתיבת תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s