בעיית וארינג

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

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

הילברט הוכיח שאכן כך הדבר בשנת 1909. הוא הגדיר פונקציה \ g(k) אשר לכל מספר טבעי \ k נותנת \ g(k)=s. יש לשים לב ש \ 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.

שפות אחרות