הכללה של IMO 1995/6 ומשפט Wolstenholme (חלק 1/2)

פורסם בתאריך 19 באוגוסט 2015 מאת Ofir Gorodetsky

שלום קוראים,

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

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

0. הבעיה

הבעיה שאעסוק בה היא הבעיה השישית והאחרונה (כלומר, הקשה ביותר) בתחרות המתמטיקה הבינלאומית (International Mathematical Olympiad, או בקיצור: IMO) ה-36. היא התקיימה בטורונטו, קנדה ב-1996. מתוך 412 משתתפים, 34 פתרו את הבעיה (לשם השוואה, הבעיה השנייה ברמת הקושי שלה, שהייתה באותה שנה הבעיה השנייה מבחינה כרונולוגית, נפתרה ע"י 90 מתמודדים).

למי שלא מכיר, ה-IMO היא תחרות יוקרתית במתמטיקה המיועדת לנוער (יש הגבלת גיל) ומתקיימת מדי שנה. כל מדינה רשאית לשלוח עד 6 נציגים, שמתחרים במשך יומיים באופן אישי בפיתרון 6 שאלות: 3 שאלות ביום הראשון, ו-3 שאלות ביום השני, כאשר הזמן המוקצב בכל יום הוא 4.5 שעות. השאלות בכל יום מסודרות בסדר קושי עולה (או כך לפחות אמור להיות; בפועל לא תמיד קורה). כל משתתף מקבל ציון על פתרונותיו, כאשר הציון המקסימלי האפשרי הוא 42: כל שאלה שווה עד 7 נקודות. על אף הקושי הרב של הבעיות, הן הניסוח והן הפיתרון משתמשים בידע תיכוני בלבד – למרות שידע על-תיכוני לא יכול להזיק, בלשון המעטה.
(למקרה שאתם תוהים, אני כמובן לא השתתפתי באותו IMO; הייתי בן 4.5. מבינים? הייתי כ"כ צעיר שעוד ספרתי את הגיל שלי בחצאים.)

ניגש לבעיה:

יהי p ראשוני אי-זוגי. כמה תתי-קבוצות של \{1,2,\cdots, 2p\} יש, כך שמספר האיברים בקבוצה הוא p וסכום האיברים בקבוצה מתחלק ב-p?

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

פורסם בקטגוריה אלמנטרי, סדרה, קומבינטוריקה, תורת המספרים | 2 תגובות

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

פורסם בתאריך 14 באוגוסט 2015 מאת Ofir Gorodetsky

היי!

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

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

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, שעליו ספירת הנקודות היא אכן טריוויאלית.
להמשיך לקרוא ←

פורסם בקטגוריה כללי | עם התגים , , | 4 תגובות

הנס של המקדמים הבינומים

פורסם בתאריך 17 במאי 2015 מאת Ofir Gorodetsky

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

0. מבוא

המקדמים הבינומים \binom{n}{k} הם מספרים שלמים. מצד אחד, זה ברור – הם סופרים, בהגדרה, בכמה דרכים ניתן לבחור k איברים מתוך קבוצה בגודל n (או בניסוח שקול: כמה תתי-קבוצות מגודל k יש לקבוצה בגודל n).
מצד שני, זה נס שהם שלמים. למה זה נס? כי אפשר לתת נוסחה למקדמים הללו, ובמבט ראשון לא ברור בכלל מהנוסחה שהם שלמים. הנוסחה היא:

\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k(k-1) \cdots 1}

למי שלא זוכר מהיכן מגיעה הנוסחה, אזכיר: אגף שמאל סופר תתי-קבוצות בגודל k. אגף ימין סופר אותן באופן הלא-ישיר הבא: נסדר את כל איברי הקבוצה, n במספר, בשורה. יש לכך n! דרכים. את תת-הקבוצה נבנה ע"י כך שניקח את k האיברים הימניים בשורה. הבעיה: יש "יתירות", אנחנו סופרים כל תת-קבוצה פעמים רבות. ספציפית, כל תת-קבוצה נספרת בדיוק k! \times (n-k)! פעמים (אפשר "לבלגן" את k האיברים הימניים ואת (n-k) האיברים השמאליים), מכאן החלוקה. \blacksquare

בפוסט הזה אסביר איך אפשר לראות ישירות מהנוסחה (בלי ההקשר הקומבינטורי) שהמקדמים הללו למעשה שלמים, ואיך זה קשור לחידה הבאה:

חידה: הראו שמכפלה של 100 מספרי פיבונאצ'י עוקבים מתחלקת במכפלה של 100 מספרי פיבונאצ'י הראשונים, כלומר: F_1 F_2 \cdots F_{100} \mid F_{n+1} F_{n+2} \cdots F_{n+100}.

להמשיך לקרוא ←

פורסם בקטגוריה חפירה, קומבינטוריקה, תורת המספרים | תגובה אחת