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

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

השערת ארדש-גראהם היא השערה שהוכחה כנכונה בתורת המספרים הקומבינטורית, שלפיה בכל חלוקה סופית של קבוצת המספרים הטבעיים הגדולים מ־1 יש חלק הכולל מספרים שסכום ההופכיים שלהם הוא 1. במילים אחרות, לכל צביעה של המספרים האלו במספר סופי של צבעים, יש "הצגה מונוכרומטית" של 1 כשבר מצרי (מניחים ש-1 אינו משתתף במשחק, כדי שלא לקבל את ההצגה הטריוויאלית ). את ההשערה הציעו פול ארדש ורונלד גראהם ב-1980, והוכיח אותה ארני קרוט (אנ') בשנת 2000.

למשל, בחלוקת הטבעיים למספרים זוגיים ואי־זוגיים, אפשר להציג

השאלה היא האם בכל חלוקה יש הצגה כזו לפחות עבור אחד החלקים.

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

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

ארדש כתב במהלך חייו מאמרים רבים על שברים מצריים. כמעט 20 שנה אחרי מותו, התפרסם מאמר משותף שלו עם רון גראהם ו-Steve Butler, לאחר שהאחרון השלים, גם באמצעות חישוב אינטנסיבי, פתרון של בעיה אחרת שהציבו ארדש וגראהם: האם אפשר להציג כל מספר שלם כשבר מצרי שבו המכנים הם כולם מכפלה של שלושה ראשוניים [1]. התשובה, כפי שהוכח ב-2015, חיובית [2].

לקריאה נוספת

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

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

סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0