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

השערת ארדש-גראהם היא השערה שהוכחה כנכונה בתורת המספרים הקומבינטורית, שלפיה בכל חלוקה סופית של קבוצת המספרים $\ 2,3,4,\cdots$ (המספרים הטבעיים הגדולים מ-1), יש חלק הכולל מספרים שסכום ההופכיים שלהם הוא 1. במילים אחרות, לכל צביעה של המספרים האלו במספר סופי של צבעים, יש "הצגה מונוכרומטית" של 1 כשבר מצרי (מניחים ש-1 אינו משתתף במשחק, כדי שלא לקבל את ההצגה הטריוויאלית $\ 1={\frac {1}{1}}$). את ההשערה הציעו פול ארדש ורונלד גראהם ב-1980, והוכיח אותה ארני קרוט בשנת 2000.

לדוגמה, בחלוקת הטבעיים למספרים זוגיים ואי-זוגיים, אפשר להציג את 1 גם כסכום $\ {\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{12}}$, וגם כסכום $\ {\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{9}}+{\frac {1}{15}}+{\frac {1}{21}}+{\frac {1}{27}}+{\frac {1}{35}}+{\frac {1}{63}}+{\frac {1}{105}}+{\frac {1}{135}}$. השאלה היא האם בכל חלוקה יש הצגה כזו לפחות עבור אחד החלקים.

ארדש וגראהם שיערו בנוסף שקיים קבוע b כך שאם מספר הצבעים r גדול מספיק, אז המכנה הגדול ביותר שבו נעשה שימוש בהצגה, קטן מ-$\ b^{r}$. כדי שהתנאי הזה יתקיים, ידוע שעל b להיות לפחות e. קרוט הוכיח שהטענה הזו נכונה עבור $b\geq e^{167000}$.

תוצאתו של קרוט נובעת כמסקנה ממשפט כללי יותר, שלפיו יש הצגה של 1 באמצעות שברים מצריים שהמכנים שלהם נבחרים מקבוצה C של מספרים חלקים בקטעים מהצורה $\displaystyle [X,X^{1+\delta }]$, בתנאי ש-C גדולה מספיק כך שסכום ההופכיים של המספרים שם הוא לפחות 6. השערת ארדש-גראהם נובעת מהמשפט הזה, אם מראים שלכל r, ניתן למצוא קטע מהצורה הזו כך שסכום ההופכיים של כל המספרים החלקים הוא לפחות 6r, משום שאז יש בכל צביעה ב-r צבעים חלק אחד שסכום ההופכיים עבורו הוא לפחות 6.

ארדש כתב במהלך חייו מאמרים רבים על שברים מצריים. כמעט עשרים שנה אחרי מותו, התפרסם מאמר משותף שלו עם רון גראהם ו-Steve Butler, לאחר שהאחרון השלים, גם באמצעות חישוב אינטנסיבי, פתרון של בעיה אחרת שהציבו ארדש וגראהם: האם אפשר להציג כל מספר שלם כשבר מצרי שבו המכנים הם כולם מכפלה של שלושה ראשוניים New Erdős Paper Solves Egyptian Fraction Problem, Simons Foundation, ‏2015-12-09 (באנגלית אמריקאית). התשובה, כפי שהוכח ב-2015, חיובית [1].

ראו גם

• משפט מירסקי-ניומן קובע שבכל חלוקה של השלמים לאיחוד זר של סדרות אריתמטיות מוכרח ההפרש הגדול ביותר להופיע יותר מפעם אחת.
• השערת הרצוג-שונהיים מכלילה את הבעיה שביסוד משפט מירסקי-ניומן לחבורה (סופית) כלשהי.

לקריאה נוספת

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

קישורים חיצוניים

• עמוד הבית של ארני קרוט
• ההוכחה של קרוט ב-"Annals of Mathematics"
• ארדש, פול וגראהם, רונלד, בעיות ותוצאות ישנות וחדשות בתורת המספרים הקומבינטורית (עמ' 128), שם מקורי: Old and New Problems and Results in combinatorial Number Theory, ‏1980 (באנגלית)

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

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