משפט הסה בהסתברות גבוהה (מיני-פוסט)

היי!

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

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

1. רקע על משפט הסה

הפעם אספר על תוצאה מגניבה שגיליתי על עקומים אליפטים. לצערי, אני לא היחיד או הראשון שגילה אותה, אבל עדיין היא לא מוכרת מספיק לקהל המתמטי. נקודת המוצא שלנו היא משפט הסה (Helmut Hasse) על מספר הנקודות על עקום אליפטי: אם E הוא עקום אליפטי המוגדר מעל שדה סופי \mathbb{F}_{q}, אז כמות הנקודות על העקום היא q+1 ועוד "שגיאה" שחסומה בערכה המוחלט מלמעלה ע"י 2 \sqrt{q}. משפט זה פורסם ב-1936.

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

y^2 = x^3+ax+b

עבור איזשהם a,b\in \mathbb{F}_{q} (למעשה, בגלל דרישת החלקות, צריך לדרוש גם 4a^3+27b^2 \neq 0).

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

  • עבור זוג נקודות אקראי (x,y) \in \mathbb{F}_{q}^2 נצפה שמשוואת ויירשטראס תתקיים בסיכוי 1 חלקי q. אפשר לחשוב על מספר הנקודות בתור משתנה מקרי שהוא סכום של q^2 אינדיקטורים של מאורעות הקורים בהסתברות 1 חלקי q. בהנחת אי-תלות (שהיא לאו דווקא הנחה נכונה…) זה משתנה בינומי Bin(q^2, \frac{1}{q}), שהתוחלת שלו היא q והשונות אסימפטוטית ל-q, כלומר נצפה שיקבל בסיכוי גבוה ערכים מסדר גודל q+O(\sqrt{q}).
  • וריאציה על הטיעון הנ"ל – לכל x\in \mathbb{F}_{q} יש בין 0 ל-2 ערכי y עבורם מתקיימת משוואת ויירשטראס. זה תלוי בסימן לז'נדר של x^3+ax+b. אם נניח שהוא מתנהג כמו משתנה אקראי המקבל את הערכים 1 ומינוס 1 בסיכוי שווה (ונזניח את המקרה שהביטוי הוא 0), נקבל אותה הערכה כמו בטיעון הקודם.

דרך גיאומטרית יותר לחשוב על המשפט היא זו: המחובר q מגיע מהמימד של היריעה שלנו (עקום הוא ממימד 1. עבור יריעות ממימד גבוה יותר מקבלים חזקה גבוהה יותר של q), המחובר 1 מגיע מהנקודה "באינסוף" – הנקודה המיוחסת של העקום, והשגיאה מגיעה מכך שעקום אליפטי הוא לא אובייקט "טריוויאלי" ושיש איזושהי סטייה מהתוחלת.

וויל (Andre Weil) הוכיח ב-1949 שבאופן כללי, מספר הנקודות על עקום אלגברי מגנוס g הוא q+1 עד כדי שגיאה שחסומה בערכה המוחלט ע"י 2g\sqrt{q}. משפט זה ידוע בתור משפט הסה-וויל. משפט הסה מתקבל אם לוקחים עקומים מגנוס 1.
מהמשפט רואים שעבור גנוס 0 אין שגיאה כלל – ואכן, בעקומים כמו y^2=ax^2+b שהם מגנוס 0 יש בדיוק q+1 נקודות (כולל הנקודה באינסוף, אם ישנה), לכל a,b כך שהעקום הנ"ל אי-פריק (עבור a=1,b=0 מקבלים עקום פריק…). זה תרגיל חביב ומלמד. ההוכחה, שלרוב עוברת דרך שינוי משתנים, מראה שבעצם עקומים מגנוס 0 איזומורפים לישר הפרוייקטיבי P^1, שעליו ספירת הנקודות היא אכן טריוויאלית.

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

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

150px-Helmut_HasseAndre Weil abel_1401441e

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

2.הוכחות פשוטות

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

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

כדאי לציין שיש מקרים מסויימים של משפט וויל ואפילו של השערת רימן מעל שדות סופיים שהיו ידועים הרבה לפני שהוכיחו את התוצאות המלאות – לדוגמא, וויל ספר במדויק ובצורה אלמנטרית נקודות על "יריעות אלכסוניות" מהצורה \sum a_i x_i^{b_i} = c.

אם אתם מתעניינים בנושא, אפשר למצוא דוגמאות כאלה ב-2 ספרים קריאים מאוד: "A Classical Introduction to Modern Number Theory" של Ireland & Rosen (פרק 11), או בספר היפה "Equations over Finite Fields: An Elementary Approach" של Schmidt, שמכיל גם את התוצאות של סטפנוב.

3. Sato-Tate

אפשר, כמו תמיד במתמטיקה, לשאול שאלות עדינות יותר: ניקח עקום אליפטי E מהצורה y^2=x^3+ax+b, המוגדר מעל הרציונליים הפעם. חוץ ממספר סופי של ראשוניים, אם נעשה רדוקציה לעקום מודולו ראשוני p, נקבל שוב עקום אליפטי (הראשוניים הבעייתים הם אלו שמחלקים את המכנים של a,b ואלו המחלקים את הדיסקרימיננטה 4a^3+27b^2). על כן, ממשפט הסה, מספר הנקודות על העקום החדש, שיסומן E_p, הוא p+1-2\sqrt{p} \varepsilon_p, כאשר \varepsilon_p הוא מספר ממשי הקטן/שווה 1 בערכו המוחלט. אפשר לכתוב אותו בתור \cos \theta_p, עבור זווית בין 0 ל-\pi.

השערת Sato-Tate חוזה מה תהיה ההתפלגות הגבולית של \{\theta_p\}_{p=2,3,5,\cdots}. ספציפית, היא חוזה ש:

\lim_{N\to\infty}\frac{\#\{p\leq N:\alpha\leq \theta_p \leq \beta\}} {\#\{p\leq N\}}=\frac{2}{\pi} \int_{\alpha}^{\beta} \sin^2 \theta \, d\theta

להתפלגות זו נקרא "התפלגות Sato-Tate".
חשוב לציין שיש משפחה של עקומים אליפטים שידוע שעבורה ההשערה נופלת ("עקומי CM"). מאמינים שהיא נופלת רק עבור משפחה זו, ואתעלם מקיומה בינתיים.
למיטב הבנתי, ב-2008 הוכחו את ההשערה עבור משפחה רחבה של עקומים, אבל ההשערה הכללית עדיין פתוחה.

4. מה אני רוצה בכלל לספר לכם

אני רוצה להציג לכם טיעון שנותן את משפט הסה ואת השערת Sato-Tate, "בממוצע". למה הכוונה?

לכל a,b \in \mathbb{F}_{q}, נסמן ב-N_{a,b} את מספר הנקודות על העקום האליפטי המגיע מהמשוואה y^2=x^3+ax+b. אני טוען שאפשר לחשב באופן אלמנטרי את ה"תוחלת" של N_{a,b} וגם את ה"שונות", כאשר חושבים a,b כמספרים אקראיים בשדה הסופי \mathbb{F}_{q}. מהחישוב הזה, ובעזרת אי-שיוויון צ'בישב, נקבל שמשפט הסה נכון עבור לפחות 3/4 מהזוגות האפשריים. זו בעצם השיטה ההסתברותית בשירות האלגברה.

מה הקשר ל-Sato-Tate? עם כלים נוספים אפשר לחשב גם מומנטים גבוהים יותר של N_{a,b}, ולהשוות למומנטים של ההתפלגות המופיעה בהשערת Sato-Tate – ולקבל הסכמה!! זה לא מוכיח את השערת Sato-Tate, כי בהשערה מקבעים עקום אליפטי ו"משחקים" עם המציין, וכאן אנחנו מקבעים את המציין ומשחקים עם העקום. אבל זה מעניין ומחזק את אמונתנו בהשערה.

5. הפרטים המלוכלכים

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

הרעיון מאחורי החישובים שאציג הוא פשוט מאוד: שינוי סדר סכימה. איך נחשב את תוחלת מספר הנקודות על y^2=x^3+ax+b? במקום לשאול עבור זוג (a,b) כמה נקודות יש על העקום, אשאל: עבור נקודה (x_0,y_0), כמה זוגות (a,b) יש כך שהעקום המתאים מכיל את הנקודה? זו שאלה קלה יותר, כי בהינתן (x_0,y_0), המשוואה y_0^2=x_0^3+ax_0+b נהיית אפינית ב-a,b. על כן מספר הפתרונות הוא q בדיוק, והתוחלת יוצאת q \cdot q^2 / q^2 = q. (אני לא מחשיב כאן את הנקודה באינסוף במכוון, בשביל הפשטות, אבל היא מעלה את התוחלת ל-q+1.)

התוחלת הייתה קלה, ובפרט נובע שהמשתנה המקרי \cos \theta_{a,b} (המגיע מנרמול דומה לזה שעושים בהשערת Sato-Tate) הוא בעל תוחלת 0. זה עקבי עם כך שהתוחלת של \cos X עבור משתנה מקרי X בעל התפלגות Sato-Tate גם יוצאת 0:

\frac{2}{\pi} \int_{0}^{\pi} \cos \theta \sin^2 \theta d\theta = 0

(ודאו!)
ומה לגבי השונות? היא קשה יותר. אבל לא הרבה יותר. יש לנו תוחלת, ולכן בשביל חישוב שונות מספיק לדעת את המומנט השני (E(X-EX)^2 = EX^2 - (EX)^2). במקרה שלנו, חישוב המומנט השני שקול לספירת זוגות (x_0,y_0), (x_1,y_1) עם משקולת ששווה למספר העקומים שמכילים את 2 הנקודות בו-זמנית (את הסכום הזה צריך לחלק ב-q^2, גודל מרחב ההסתברות). זו אמירה שדורשת כמה רגעים של עיכול: עשיתי כאן צעד, והצעד הוא שינוי סדר סכימה (הסכום הרגיל הוא על עקומים, ואני עברתי לסכימה על זוגות נקודות).

אני עובר על זוגות סדורים של נקודות (x_0,y_0),(x_1,y_1), ויש כאן 2 מקרים:

מקרה א: המקרה המנוון שבו 2 הנקודות שוות (x_0=x_1, y_0=y_1). זה חישוב שזהה לחישוב שעשינו עבור התוחלת, הסכום יוצא q \cdot q^2, ואחרי חלוקה בגודל מרחב ההסתברות מקבלים q.

מקרה ב: נותר המקרה הלא מנוון. כשמציבים ב-y^2=x^3+ax+b זוג נקודות שונות (x_0,y_0),(x_1,y_1) מקבלים זוג משוואות אפיניות ב-a,b:

ax_0 + b = y_0^2 - x_0^3

ax_1 + b = y_1^2 - x_1^3

אם המשוואות בלתי-תלויות (המקרה ה"גנרי"), יש פיתרון יחיד. זה קורה כאשר x_0 \neq x_1. המקרה הזה תורם לשונות \frac{1}{q^2} (q^4-q^3) = q^2-q (החלוקה ב-q^2 מגיעה מגודל מרחב ההסתברות, הביטוי q^4-q^3 מגיע מחישוב מספר זוגות סדורים עם קואורדינטת x שונה).
אם המשוואות תלויות, כלומר x_0 = x_1, אז יש 0 או q פתרונות. צריך לספור מתי יש q פתרונות, וזה קורה כאשר המשוואות מזדהות, כלומר כאשר מתקיים השיוויון הבא:

y_0^2 - x_0^3 = y_1^2 - x_1^3.

אבל בגלל ש-x_0 = x_1, זה שקול לשיוויון y_0^2 = y_1^2, או: y_0 = \pm y_1. המקרה y_0 = y_1 נפסל (כי אנחנו עוברים על זוגות של נקודות שונות), לכן יש q פתרונות אמ"מ x_0=x_1, y_0=-y_1, y_0 \neq y_1. יש q(q-1) זוגות (x_0,y_0), (x_1, y_1) שמקיימים תנאים אלו, והם תורמים \frac{1}{q^2} (q \cdot q(q-1)) = q-1 לשונות.

עכשיו צריך לסכום את 2 המקרים (המנוון והלא מנוון) ולחסר את התוחלת בריבוע: q+(q^2-q)+(q-1)-q^2. מקבלים q-1. כלומר כמות הנקודות N_{a,b} על העקום האקראי y^2=x^3+ax+b היא q בתוחלת, עם סטיית תקן \sqrt{q-1}. העקומים המקיימים את משפט הסה הם אלו עבורם מספר הנקודות סוטה בלכל היותר 2 סטיות תקן מהתוחלת, ואי-שיוויון צ'בישב מבטיח שזה קורה עבור לפחות 3/4 מהעקומים:

\Pr(|X-\mu|\geq 2\sigma) \leq \frac{1}{2^2}

העניין המכריע בחישובים האלה היה העובדה שהעקום האקראי y^2=x^3+ax+b תלוי אפינית בפרמטרים a,b.

נחזור ל-Sato-Tate. מחישוב השונות נובע שהמשתנה המקרי \cos \theta_{a,b} (המגיע מנרמול דומה לזה שעושים בהשערת Sato-Tate) הוא בעל שונות \frac{1}{4} - \frac{1}{4p}, ונחשוב עליה פשוט בתור \frac{1}{4} (לגיטימי עבור p גדול…). זה עקבי עם כך שהשונות של \cos X עבור משתנה מקרי X בעל התפלגות Sato-Tate גם יוצאת \frac{1}{4}:

\frac{2}{\pi} \int_{0}^{\pi} \cos^2 \theta \sin^2 \theta d\theta = \frac{1}{4}

(ודאו!)

6. ומה לגבי המומנטים הגבוהים?

Birch, מהשערת Birch ו-Swinnerton-Dyer, פרסם ב-1968 מאמר בו הוא מחשב את המומנטים הגבוהים ומשווה למומנטים המצופים מ-Sato-Tate. החישובים משתמשים בתורה של תבניות ריבועיות – קריאה מעניינת אך לא טריוויאלית. הוא מצטט גם את Mordell, שחישב את המומנטים הראשונים עוד ב-1933. שימו לב – זה לפני משפט הסה!

המאמר של Mordell הפתיע אותי מאוד, בעיקר בתוצאות שהוא מצטט – לדוגמא, יש עקומים אליפטים מסוימים שעבורם ידעו את משפט הסה כבר ב-1832! בנוסף, Davenport הוכיח ב-1931 שכמות הנקודות על עקום אליפטי מודולו p היא p +O(p^{3/4}). על זה לא ידעתי כלל, אבל בדיעבד זה לא צריך להפתיע: הייתה השתלשלות אירועים דומה מאוד עם סכומי קלוסטרמן, שקודם הוכיחו עבורם חסם בסגנון של דוונפורט, ואח"כ משפט וויל שיפר את החסם משמעותית.

לקח שעתיים וחצי ברוטו, אבל עשיתי הפסקה של שעה.

זהו וביי,
אופיר

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

אודות Ofir Gorodetsky

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

4 תגובות על משפט הסה בהסתברות גבוהה (מיני-פוסט)

  1. Asaf הגיב:

    ראשית אני אציין שהפוסט יפה ומעניין מאוד.

    יש לי שאלה על ההוכחה.
    אתה בעצם מגריל מספרים בשדה Z/pZ, אבל כעקרון פונקציית זטא סופרת נקודות לכל p, ולכן ההגרלה של המספרים אקראית מתוך השדה לא מתאימה להגרלה של עקום מקרי (אפשר לתת מידה סבירה על מרחב העקומים דרך ה-moduli space שלהם, זה בסגנון העבודות של בהרגאבה).

    • Ofir Gorodetsky הגיב:

      היי אסף,

      תודה על התגובה (והמחמאה :)).
      אני לא מבין כ"כ ב-moduli spaces, לצערי, ולא בטוח איזו משמעות גיאומטרית אפשר לתת למרחב ההסתברות שהגדרתי.
      מה שכן, יש הרבה עבודות לאחרונה שחוקרות סטטיסטיקה של מה שנקרא "Hyperelliptic ensemble" – אתה לוקח בתור מרחב ההסתברות את כל העקומים מהצורה y^2=g(x) מעל F_q כאשר g פולינום מתוקן ונטול ריבועים ממעלה d.
      חוקרים לדוגמא את המומנטים של פונקציות-L של קרקטרים ממשיים מודולו g (שקשורות לפונקציית זטא של העקום y^2=g(x) ). אני לא בטוח איך השאלות הללו צצו היסטורית, אבל הדבר הסופר-מעניין הוא שהתשובות על הבעיות שמופיעות שם מגיעות מ-random matrix theory. מה שאומר – הרבה בעיות פתוחות.

      מאמר בנושא:
      http://www.ihes.fr/~jcandrade/papers/1.pdf

  2. עמיר הגיב:

    איזו הוכחה מקסימה!
    תודה על הפוסט.

להשאיר תגובה

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

הלוגו של WordPress.com

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

תמונת Twitter

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

תמונת Facebook

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

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

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

מתחבר ל-%s