בעיית וארינג – הבדלי גרסאות

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

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

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

במהלך השנים נקבעו חסמים נוספים, בשימוש בטכניקות מתוחכמות ומסובכות יותר ויותר. לדוגמה, [[ג'וזף ליוביל|ליוביל]] הראה ש-( <math>\ g(4)</math> הוא לכל היותר 53. [[גודפרי הרולד הארדי|הארדי]] ו[[ג'ון אדנזור ליטלווד|ליטלווד]] הראו שכל מספר גדול מספיק הוא סכום של לכל היותר 19 מספרים בחזקה הרביעית. בשנת [[1986]] הוכיחו ש <math>\ g(4)=19</math>.

כלחושבים שכל הערכים של g ידועים כיום, תודת לעבודתם של דיקסון, פילאי, רבגנדיי וניבן. הנוסחה שלהם היא:

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

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

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

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