בעיית וארינג

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

בתורת המספרים, בעיית וארינג, שהוצעה בשנת 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$ .