הלמה של גייל

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש

במתמטיקה, הלמה של גייל היא למה העוסקת בפיזור כללי של נקודות על פני הספירה ה-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

הלמה של גייל28233366Q25488568