בעיית וארינג

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

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

במהלך שנות ה-50, הוכיח יורי ליניק את קיום $g(k)$ בכלים אלמנטריים תוך שימוש בצפיפות שנירלמן.

כל הערכים של $g$ ידועים כיום, הודות לעבודתם של דיקסון, פילאי, רבגנדיי וניבן. הנוסחה שלהם היא: $g(k)=\left\lfloor 1.5^{k}\right\rfloor +2^{k}-2$ לכל $k\geq 6$ , כאשר $\lfloor x\rfloor$ הוא הערך השלם של $x$ , שהוא המספר השלם הגדול ביותר שאינו עולה על $x$ . הנוסחה בעצם יותר מסובכת כי במקרה ש- $1.5^{k}-\left\lfloor 1.5^{k}\right\rfloor >1-0.75^{k}$ אזי הנוסחה ל- $g(k)$ שונה, אמנם עד עכשיו לא מצאו אף מספר $k\geq 6$ כזה, ונבדקו כל המספרים שהם קטנים מ-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

חזקות עד כדי סימן

וריאציה של בעיית וארינג שואלת עבור $k$ קבוע, מהו המספר $s$ הקטן ביותר כך שלכל מספר יש הצגה בצורה $\pm n_{1}^{k}\pm \cdots \pm n_{s}^{k}$ . את המספר הזה מסמנים $v(k)$ . ידוע כי $v(2)=3$ , אך הערך המדויק של הפונקציה אינו יודע בשום מקרה אחר. למשל, $4\leq v(3)\leq 5$ : כל מספר אפשר להציג כסכום של 5 חזקות שלישיות (של מספרים שלמים, לאו דווקא חיוביים), ולא ידוע האם די ב-4 חזקות.