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

השערת ארדש-גראהם היא השערה שהוכחה כנכונה בתורת המספרים הקומבינטורית, שלפיה בכל חלוקה סופית של קבוצת המספרים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 2,3,4,\cdots} (המספרים הטבעיים הגדולים מ-1), יש חלק הכולל מספרים שסכום ההופכיים שלהם הוא 1. במילים אחרות, לכל צביעה של המספרים האלו במספר סופי של צבעים, יש "הצגה מונוכרומטית" של 1 כשבר מצרי (מניחים ש-1 אינו משתתף במשחק, כדי שלא לקבל את ההצגה הטריוויאלית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 1 = \frac{1}{1}} ). את ההשערה הציעו פול ארדש ורונלד גראהם ב-1980, והוכיח אותה ארני קרוט בשנת 2000.

לדוגמה, בחלוקת הטבעיים למספרים זוגיים ואי-זוגיים, אפשר להציג את 1 גם כסכום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{12}} , וגם כסכום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \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 גדול מספיק, אז המכנה הגדול ביותר שבו נעשה שימוש בהצגה, קטן מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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השערת ארדש-גראהם