הלמה של גייל

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

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

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

הוכחה

נוכיח טענה שקולה: קיימות קבוצה של נקודות {x1,,x2k+n} ב-n+1 כך שבכל חצי מרחב n+1 ממדי שמוגדר על ידי על-מישור העובר דרך הראשית (תת מרחב וקטורי ממעלה n) יש לפחות k נקודות מהקבוצה. אפשר לתרגם טענה זו ללמה של גייל על ידי הטלה של n+1 על ספירת היחידה Sn באמצעות קרניים היוצאת מהראשית (דרך כל נקודה במרחב מעבירים קרן היוצאת מהראשית והנקודה מועתקת לנקודת החיתוך של הקרן עם הספירה).

נבנה את הנקודות x1,,x2k+n. נסתכל על עקום המומנטים ה-n ממדי משוכן בעל-מישור בגובה 1: γ(t)=(1,t,t2,,tn). נגדיר: xi=(1)iγ(i) (למעשה יכולנו לבחור כל 2n+k נקודות שונות על העקום). יהי h על-מישור העובר דרך הראשית. אנו צריכים להוכיח שבכל צד שלו יש k נקודות לפחות.

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

נסמן את קבוצת n הנקודות החיתוך ב-Aon ואת קבוצת 2k נקודות A שלא נמצאות על h ב-Aoff. נצבע את נקודות Aoff באופן הבא: נקודה γ(i) תהיה שחורה אם i זוגי והנקודה נמצאת מימין ל-h, או אם i אי-זוגי והנקודה נמצאת משמאל ל-h. בהתאמה נקודה היא לבנה אם i זוגי והנקודה משמאל ל-h, או אם i אי-זוגי והנקודה מימין ל-h. נבחין כי שתי נקודות סמוכות ב-Aoff הן בצבעים שונים: אם בין a1,a2Aoff סמוכות יש מספר זוגי של נקודות מ-Aon, אז הן באותו הצד ועם זוגיות שונה, ולכן צבעים שונים. ואם מפרידים ביניהן מספר אי-זוגי של נקודות מ-Aon הן בצדדים שונים ומאותה זוגיות ולכן בצבעים שונים.

מכיוון שהצבע מתחלף בין שתי נקודות סמוכות, יש בדיוק k נקודות שחורות ובדיוק k נקודות לבנות. אם γ(i) נקודה שחורה, אז או שהיא מימין ל-h ו-i זוגי ולכן xi=γ(i) מימין ל-h. או שהיא משמאל ל-h ו-i אי-זוגי ולכן xi=γ(i) מימין ל-h. קיבלנו שכל הנקודות השחורות מתאימות ל-xi מימין ל-h, ובאופן דומה כל הנקודות הלבנות מתאימות ל-xi משמאל ל-h, ולכן יש בדיוק k נקודות מבין {x1,,x2k+n} בכל צד של h. נזכור שהזזנו את h באופן שהחסיר נקודות מהצדדים, ולכן יש לפחות k נקודות בכל צד של h המקורית.

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

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