השערת ארדש-גראהם

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

בתורת המספרים הקומבינטורית השערת ארדש-גראהם אומרת שאם הקבוצה {...,2,3} ‎ תחולק למספר סופי של תת קבוצות, אז ישנה לפחות תת קבוצה אחת, כך שניתן לייצג את 1 כשבר מצרי באמצעות האיברים שלה. במילים אחרות, עבור כל r > 0 ועבור כל r-צביעה של המספרים הטבעיים הגדולים מ-1, קיימת תת-קבוצה מונוכרומטית סופית, S, של המספרים האלה, כך שמתקיים

.

ביתר פירוט, פול ארדש ורונלד גראהם שיערו שעבור r גדול מספיק, האיבר הגדול ביותר של S חסום מלמעלה על ידי b^r, כש-b הוא קבוע כלשהו, בלתי-תלוי ב-r. כדי שהתנאי הזה יתקיים, ידוע היה שעל b להיות לפחות e.

המתמטיקאי והפרופסור ארני קרוט (Ernie Croot) הוכיח את ההשערה במסגרת תזת הדוקטורט שלו. מאוחר יותר, בזמן שהיה פוסט-דוק בברקלי פרסם את ההוכחה ב-Annals of Mathematics. הערך שקרוט נתן לקבוע b הוא עצום, .

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

[עריכה] קישורים חיצוניים

• עמוד הבית של ארני קרוט.
• ההוכחה של קרוט ב-Annals of Mathematics.

[עריכה] לקריאה נוספת

• Croot, Ernest S., III (2000). "Unit Fractions". Ph.D. thesis. University of Georgia, Athens.
• Erdős, Paul and Graham, Ronald L. (1980). "Old and new problems and results in combinatorial number theory". L'Enseignement Mathématique 28: 30–44.