הלמה של גייל

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

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

הוכחה

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

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

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

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

28233366הלמה של גייל