בעיית וארינג

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

בתורת המספרים, בעיית וארינג שואלת האם לכל מספר טבעי \ k יש חסם עליון \ s על מספר החזקות ה-k-יות הנדרשות כדי להציג כל מספר טבעי. את הבעיה הציע בשנת 1770 אדוארד וארינג.

הילברט הוכיח שאכן כך הדבר בשנת 1909. על כן אפשר להגדיר פונקציה \ g(k), כך שכל מספר טבעי אפשר להציג כסכום של \ g(k) חזקות k-יות, אבל לא כסכום של פחות מכך. לדוגמה, \ g(1)=1. חישוב פשוט מראה שכדי להציג את המספר 7 דרושים 4 ריבועים, עבור 23 דרושים 9 מספרים בחזקה השלישית, וכדי להציג את 79 דרושים 19 מספרים בחזקה הרביעית. אלו הם חסמים תחתונים על \ g(k) עבור \ k=2,3,4 בהתאמה.

משפט ארבעת הריבועים של לגראנז' אומר שניתן להציג כל מספר טבעי כסכום של לכל היותר ארבעה ריבועים; מכיוון ש-7 דורש ארבעה ריבועים, הרי נובע מכך ש \ g(2)=4. ההשערה של משפט זה הוצעה בשנת 1640 על ידי פרמה.

במהלך השנים נקבעו חסמים נוספים, בשימוש בטכניקות מתוחכמות ומסובכות יותר ויותר. לדוגמה, ליוביל הראה ש \ g(4) הוא לכל היותר 53. הארדי וליטלווד הראו שכל מספר גדול מספיק הוא סכום של לכל היותר 19 מספרים בחזקה הרביעית.

ויפריך וקמפנר הראו ש \ g(3)=9 בעבודתם בין השנים 1909 עד 1912. בשנת 1986 הוכיחו בלאסוברמיאן, דרס, ודשויירז ש-\ g(4)=19. ג'נגרון הראה ש-\ g(5)=37 בשנת 1964. פילאי הוכיח ש-\ g(6)=73 בשנת 1940.

כל הערכים של \ g ידועים כיום, הודות לעבודתם של דיקסון, פילאי, רבגנדיי וניבן. הנוסחה שלהם היא: g(k)=\left\lfloor\left(\frac{3}{2}\right)^k\right\rfloor +2^k-2 לכל k\ge6, כאשר \lfloor x \rfloor הוא הערך השלם של \ x , שהוא המספר השלם הגדול ביותר שאינו עולה על \ x . הנוסח‎ה בעצם יותר מסובכת כי במקרה ש \left(\frac{3}{2}\right)^k-\left\lfloor\left(\frac{3}{2}\right)^k\right\rfloor> 1-\left (\frac{3}{4}\right )^k אז הנוסחה ל \ g(k) שונה, אמנם עד עכשיו לא מצאו אף מספר \ k\ge6 כזה, ונבדקו כל המספרים שהם קטנים מ-471600000, וידוע שיש ככל האפשר מספר סופי של יוצאי דופן כאלה.

ערכי \ g(k) הראשונים הם:

1, 4, 9, 19, 37, 73, 143, 279, 548, 1079, 2132, 4223 ,8384, 16673, 33203, 66190, 132055, ...

בעיה דומה, אבל קשה בהרבה, שואלת מהו המספר הקטן ביותר \ G(k) של חזקות-\ k הדרוש להצגת כל המספרים פרט למספר סופי של יוצאי דופן (או בניסוח שקול: המספר הקטן ביותר הדרוש כדי להציג כל מספר גדול מספיק). ברור ש-\ G(k)\leq g(k). שלא כמו בפונקציה \ g(k), מספרים בעייתיים כגון 23 או 79 אינם מסייעים בהערכה של \ G(k), והערכים המדויקים של פונקציה זו אינם ידועים (פרט ל-\ G(2)=g(2)=4 שנובע מעבודתם של לגראנז' וגאוס, שאפיינו את כל המספרים שאפשר להציג בשלושה ריבועים, ו-\ G(4)=16 שהוכח על ידי דוונפורט בשנת 1939). עבור חזקות שלישיות ידוע רק ש-\ 4\leq G(3)\leq 7 (נכון ל- 2005).

עוד פונקציה דומה נקראת \ G^{+}(k) (\ G_{1}(k) בעבודות של וולי) שהיא המספר הקטן ביותר של חזקות-\ k הדרוש להצגת כמעט כל המספרים (כלומר, שהיחס בין מספר יוצאי הדופן שקטנים מ-\ n ובין \ n יתכנס ל-0 כאשר \ n ילך ויגדל). ברור ש- \ G^{+}(k)\leq G(k). נכון ל-2006 ידוע 5 ערכים מדויקים של פונקציה זו בנוסף ל- \ G^{+}(2)=g(2)=4. הם \ G^{+}(3)=4, \ G^{+}(4)=15, \ G^{+}(8)=32, \ G^{+}(16)=64, ו-\ G^{+}(32)=128.