הלמה של גייל

במתמטיקה, הלמה של גייל היא למה העוסקת בפיזור כללי של נקודות על פני הספירה ה-n-ממדית. הלמה קובעת שלכל <math>n</math> ו-<math>k</math> טבעיים קיימת קבוצה בת <math>2k+n</math> נקודות על פני הספירה כך שכל המיספירה פתוחה בספירה מכילה לפחות <math>k</math> נקודות מהקבוצה. הלמה הוכחה על ידי דייוויד גייל (David Gale) ב-1956.

קל לראות שזוהי התוצאה הטובה ביותר שבגדר האפשר. לכל <math>n</math> נקודות בספירה יש מעגל גדול <math>n-1</math> ממדי שעובר דרך כולן, והוא מחלק את הספירה לשתי המיספרות בנות <math>k</math> נקודות לכל היותר.

==הוכחה==
נוכיח טענה שקולה: קיימות קבוצה של נקודות <math>\{x_1,\ldots,x_{2k+n}\}</math> ב-<math>\mathbb{R}^{n+1}</math> כך שבכל חצי מרחב <math>n+1</math> ממדי שמוגדר על ידי על-מישור העובר דרך הראשית (תת מרחב וקטורי ממעלה <math>n</math>) יש לפחות <math>k</math> נקודות מהקבוצה. אפשר לתרגם טענה זו ללמה של גייל על ידי הטלה של <math>\mathbb{R}^{n+1}</math> על ספירת היחידה <math>S^n</math> באמצעות קרניים היוצאת מהראשית (דרך כל נקודה במרחב מעבירים קרן היוצאת מהראשית והנקודה מועתקת לנקודת החיתוך של הקרן עם הספירה).

נבנה את הנקודות <math>x_1,\ldots,x_{2k+n}</math>. נסתכל על עקום המומנטים ה-<math>n</math> ממדי משוכן בעל-מישור בגובה 1: <math>\gamma(t) = (1,t,t^2,\ldots,t^n)</math>. נגדיר: <math>x_i = (-1)^i\gamma(i)</math> (למעשה יכולנו לבחור כל <math>2n+k</math> נקודות שונות על העקום). יהי <math>h</math> על-מישור העובר דרך הראשית. אנו צריכים להוכיח שבכל צד שלו יש <math>k</math> נקודות לפחות.

החיתוך בין <math>h</math> לעל-מישור <math>(1,t_1,\ldots,t_n)</math> הוא על-מישור <math>n-1</math> ממדי. על-מישור זה חותך את עקום המומנטים ב-<math>n</math> נקודות לכל היותר (ראו בערך עקום המומנטים). מכאן ש-<math>h</math> חותך את <math>\gamma</math> ב-<math>n</math> נקודות לכל היותר. אם החיתוך לא מכיל בדיוק <math>n</math> נקודות מתוך <math>A = \{\gamma(1),\ldots,\gamma(2k+n)\}</math> נזיז את <math>h</math> כך שזה אכן יהיה. נעשה זאת כך: נתייחס אל נקודות החיתוך שכבר יש לנו עם <math>A</math> כציר ונסובב את <math>h</math> ביחס אליו עד ש-<math>h</math> יפגוש נקודה נוספת של <math>A</math>. נחזור על התהליך הזה שוב ושוב עד ש-<math>h</math> יחתוך את <math>\gamma</math> בדיוק <math>n</math> נקודות. מכיוון שבכל שלב שמרנו על נקודות החיתוך ולקחנו את האיבר הראשון של <math>A</math> שפגשנו, בשום שלב לא העברנו נקודות של <math>A</math> מצד אחד של <math>h</math> לצד השני. לכן מספר הנקודות בכל צד של העל מישור יכל רק לרדת. כמו כן מכיוון שיש <math>n</math> נקודות חיתוך, בהכרח <math>\gamma</math> עובר מצד אחד של <math>h</math> לצד השני בכל נקודת חיתוך. 

נסמן את קבוצת <math>n</math> הנקודות החיתוך ב-<math>A_{\text{on}}</math> ואת קבוצת <math>2k</math> נקודות <math>A</math> שלא נמצאות על <math>h</math> ב-<math>A_{\text{off}}</math>. נצבע את נקודות <math>A_{\text{off}}</math> באופן הבא: נקודה <math>\gamma(i)</math> תהיה שחורה אם <math>i</math> זוגי והנקודה נמצאת מימין ל-<math>h</math>, או אם <math>i</math> אי-זוגי והנקודה נמצאת משמאל ל-<math>h</math>. בהתאמה נקודה היא לבנה אם <math>i</math> זוגי והנקודה משמאל ל-<math>h</math>, או אם <math>i</math> אי-זוגי והנקודה מימין ל-<math>h</math>. נבחין כי שתי נקודות סמוכות ב-<math>A_{\text{off}}</math> הן בצבעים שונים: אם בין <math>a_1,a_2\in A_{\text{off}}</math> סמוכות יש מספר זוגי של נקודות מ-<math>A_{\text{on}}</math>, אז הן באותו הצד ועם זוגיות שונה, ולכן צבעים שונים. ואם מפרידים ביניהן מספר אי-זוגי של נקודות מ-<math>A_{\text{on}}</math> הן בצדדים שונים ומאותה זוגיות ולכן בצבעים שונים.

מכיוון שהצבע מתחלף בין שתי נקודות סמוכות, יש בדיוק <math>k</math> נקודות שחורות ובדיוק <math>k</math> נקודות לבנות. אם <math>\gamma(i)</math> נקודה שחורה, אז או שהיא מימין ל-<math>h</math> ו-<math>i</math> זוגי ולכן <math>x_i=\gamma(i)</math> מימין ל-<math>h</math>. או שהיא משמאל ל-<math>h</math> ו-<math>i</math> אי-זוגי ולכן <math>x_i=-\gamma(i)</math> מימין ל-<math>h</math>. קיבלנו שכל הנקודות השחורות מתאימות ל-<math>x_i</math> מימין ל-<math>h</math>, ובאופן דומה כל הנקודות הלבנות מתאימות ל-<math>x_i</math> משמאל ל-<math>h</math>, ולכן יש בדיוק <math>k</math> נקודות מבין <math>\{x_1,\ldots,x_{2k+n}\}</math> בכל צד של <math>h</math>. נזכור שהזזנו את <math>h</math> באופן שהחסיר נקודות מהצדדים, ולכן יש לפחות <math>k</math> נקודות בכל צד של <math>h</math> המקורית.

גייל
קטגוריה:הוכחות