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

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

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

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

  • 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.

קישורים חיצוניים[עריכת קוד מקור | עריכה]