Chapter 7

Numerical Investigation of Waring’s Problem

In this chapter, we shift the emphasis away from trying to find the shortest possible representation when we restrict to mth powers and towards finding the longest required to represent all integers, i.e. Waring’s Problem.

Lagrange proved that every positive integer can be expressed as a sum of at most four squares of positive integers, verifying a conjecture first made by Fermat. Even before this proof appeared, the conjecture had been extended by Waring to the effect that each integer can be expressed as a sum of at most 9 cubes, 19 fourth powers, and so on, and, in general, that for each exponent m there exists a minimum number g(m) such that it is possible to express every integer as a sum of at most g(m) mth powers.

The existence of g(m) for all m was proved by Hilbert in 1909. This result instigated extensive further research into obtaining the actual values of g(m). It is an easy task to show that a lower bound for g(m) is provided by the function

h(m) = 2m + [(3/2)m] - 2.

Dickson [9] showed that indeed g(3) = h(3) = 9, and it is now known that g(m) = h(m) for all but a finite number of m. However, this finite set is not known (though it is expected to be empty), and though Chen [6] proved that g(5) = h(5) = 37, for a long time the value of g(4) was unknown, its upper bound gradually being reduced over the years by various researchers. Recently, Thomas [21] brought this bound down, first to 23 and then to 22. For here, Balasubramanian [1], [2] took it down further, to 21 and then to 20. Finally, in 1986, Balasubramanian, Deshouillers and Dress [3] announced their proof that in fact g(4) = h(4) = 19.

Dickson pointed out in his proof of the fact that g(3) = 9 that the only integers which actually require 9 cubes are 23 and 239 (see [10]). Later, Linnik [16] proved that only a finite number need 8 cubes. That is, from some point on, all integers can be expressed as the sum of at most 7 cubes. This idea prompts the definition of G(m) as the minimum number of mth powers required to cover all but a finite set of the positive integers. Thus G(3) £ 7. Clearly, as an infinite number of integers require 3 squares, we also have G(2) = g(2) = 4, and Davenport [7] proved that G(4) = 16. For higher powers, the current best upper bounds were obtained by Vaughan [22] [23] [24] [25], and consist of the following:

G(5) £ 19; G(6) £ 29; G(7) £ 41; G(8) £ 57; G(9) £ 75; G(10) £ 92

It is Vaughan’s belief that the actual values for these are related to a sophisticated function and are:

G(5) = 6; G(6) = 9; G(7) = 8; G(8) = 32; G(9) = 13; G(10) = 12

We now present the results of computer searches conducted by the author in seeking to obtain empirical upper bounds for G(m) from extensive numerical evidence.

Definition: Let fm(n) denote the length of the minimal representation of the positive integer n as a sum of mth powers, so that g(m) = max (fm(n) : n e N).

Definition: Let v(m,k,n) be the counting function for fm, so that v(m,k,n) = |{p e N: p £ n, fm(p) = k}|

and is valid for all k £ g(m).

We then have G(m) = min(k : v(m,k,n) is unbounded).

Definition: Let C(m,k) = {n e N: fm(n) = k}, where, if k £ G(m), C(m,k) is an infinite set, and, if

k > G(m), then c(m,k) = |C(m,k)| = v(m,k,n).

Given the nature of fm, it is obvious that an alternative definition is as follows:

fm(n) = { 1 if n = pm for some p

{ min (fm(n - pm) + 1 : pm < n

since a representation of n in mth powers must include representations of numbers smaller than n by exactly one mth power. This alternative definition provides us with an easily implemented computer algorithm which is extremely fast, especially for m > 4, but at the expense of requiring to store all previous values of fm up to n -1.

As our main interest is in obtaining experimental upper bounds for G(m), we can use this algorithm to accumulate the values of v(m,k,n) as n is pushed as high as possible, noting the trends, hopefully towards convergence. This provides us with the following information:

For m = 3: g(3) = 9, and with a search limit of n £ 1.2x108 we can say with confidence that

c(3,9) = 2 with C(3,9) = {23,239}

c(3,8) = 15 with largest member of C(3,8) being 454

c(3,7) = 121 with largest member of C(3,7) being 8042, and

c(3,6) = 3922 with largest member of C(3,6) being 1290740.

Indeed, Bohman and Froberg [4] use their earlier results, which include periodic samples of fm(n) for much higher values of n, to conjecture that C(3,5) is also finite, approximately 1.12x108, and thus that G(3) = 4. For completeness we present the following table.

 n (millions) v(3,5,n) 10 1736822 20 2909987 30 3902533 40 4785526 50 5592798 60 6341660 70 7043148 80 7706251 90 8336669 100 8938227 110 9514720 120 10069354

For m = 5: g(5) = 37, with a search limit n £ 1.2x108 and an accuracy of 10 (i.e. no change between the values of v(m,k,n) and v(m,k,10n) we have:

 k c(5,k) Running Total largest member 37 1 1 223 36 2 3 222 35 3 6 221 34 4 10 220 33 5 15 219 32 7 22 466 31 9 31 465 30 10 41 464 29 11 52 463 28 14 66 952 27 22 88 2999 26 38 126 6123 25 64 190 7138 24 107 297 7738 23 173 470 10768 22 259 729 14914 21 368 1097 22625 20 513 1610 30220 19 737 2347 32016 18 1134 3481 87918 17 1925 5406 98604 16 3592 8998 312389 15 7207 16205 470348 14 15980 32185 786159 13 38107 70292 2103306 12 105744 176036 6293040

and hence that G(5) £ 11. The running total of c(m,k) is kept as a guarantee of correctness. If we continue the above table to 2x accuracy we also have

 11 444523 620559 51033617

giving G(5) £ 10. Additionally the table of values

 n (million) v(5,10,n) 10 2017109 20 2771794 30 3153446 40 3362850 50 3480645 60 3556936 70 3603557 80 3634624 90 3656539 100 3671278 110 3682368 120 3691104

suggests, though tentatively, that G(5) may in fact be less than 10.

Note that the largest member of C(m,k) is often obtained by adding 1m to the largest member of C(m,k-1), and this is most likely when k is large. Henceforth, we will only list largest members of C(m,k) in the tables when this is not the case.

For m = 6: g(6) = 73, and with a search limit of n £ 1.2x108 and 10x accuracy we have:

 k c(6,k) Running Total Largest member 73 1 1 703 72 2 3 71 3 6 70 4 10 69 5 15 68 6 21 67 7 28 66 8 36 65 9 45 64 10 55

{there are now 11 consecutive values from k = 63 down to k = 53 with common value

{c(6,k) = 11, the largest member of C(6,k) decrementing. We continue from k=53.

 53 11 176 683 52 12 188 3594 51 14 202 50 19 221 4796 49 27 248 48 37 285 8441 47 49 334 46 63 397 45 79 476 8697 44 97 573 43 116 689 12342 42 138 827 16310 41 162 989 40 187 1176 39 216 1392 20409 38 251 1643 39938 37 296 1939 36 354 2293 86143 35 432 2725 34 545 3270 121267 33 720 3990 121329 32 983 4973 123967 31 1350 6323 234692 30 1850 8173 29 2526 10699 270068 28 3439 14138 27 4665 18803 518804 26 6316 25119 898469 25 8663 33782 1414564 24 12269 46051 1941845 23 18494 64545 3137703 22 31200 95745 6590417 21 60163 155908 9939377

and hence that G(6) £ 20. Continuing this table for an accuracy of 2x we have

 20 125755 281663 15521582 19 266785 548448 32052907

giving G(6) £ 18. Additionally, the table of values

 n (million) v(6,17,n) v(6,18,n) 10 855404 501592 20 1141618 565006 30 1234934 573028 40 1257406 573451 50 1265147 573473 60 1269657 573481 70 1273296 573484 80 1275285 573487 90 1276916 573488 100 1277629 573488 110 1278119 573488 120 1278359 573488

strongly suggests that G(6) £ 17, and possibly lower still.

For the above considered values of m, it is unlikely that G(m) is much less than the bounds given. However, the larger m gets, the fewer the powers that are available for consideration for any given n. In particular, with a search limit for n £ 1.2x108, there are only fourteen 7th powers, ten 8th powers and eight 9th powers. Results obtained, therefore, must be considered as limited. We have, with a search limit of n £ 1.2x108 and an accuracy of 10x, that

G(7) £ 33; G(8) £ 60; G(9) £ 128

We are thus encouraged to look for an alternative algorithm which may be used to extend the search limit considerably, perhaps by sacrificing speed in favour of memory requirements.

Consider that, as has been mentioned, the minimal representation for n is usually directly obtained from that of n -1 by adding 1m, with increasing likelihood as m increases, and in this case we have fm(n) = fm(n -1) + 1. We can use this fact to our advantage as follows, where it is assumed that we already know that n is not an mth power.

Given a particular n, let us assume that we have stored every previous value of fm(k) where

k < n and such that fm(k) £ fm(k -1), i.e. the exceptional cases, there being r of these, where r is "considerably" less than n. For convenience we refer to the set of exceptional cases as the non-jump set Rm, and we let rm(n) be the number of k e Rm such that k < n.

Still using the alternative definition of fm(n), we require to calculate fm(n-pm) for each p such that pm < n. We do this by locating the largest k e Rm such that k £ n-pm, in which case we have

fm(n-pm) = fm(k) + [(n-pm) - k],

i.e. fm(k) plus the "jump", i.e. the number of mth powers of 1, between k and n-pm. Again, if at any time we have fm(n) £ 2, we can assume equality.

The most obvious way of locating the correct value of k between 1 and rm(n) is by a linear search. However, this results in a prohibitive execution time for the amended algorithm for any reasonably large limit, and in practice, as the stored sequence is monotonically increasing, it is more appropriate to use a binary search technique. With this in place, the amended algorithm will execute roughly 100 times slower than the original to the same limit, thus what once took minutes will now take hours. However, the benefits will become apparent shortly.

The same computer which allowed storage of 1.2x108 values of fm can store 4.5x107 members of Rm, noting that we must now store both k and fm(k). Unfortunately, for small m, rm(n) is sufficiently large in comparison to n that we cannot improve on the original algorithm, and significant benefits are achieved only when m is large enough that non-jumps are rare. This occurs for m > 6. A guide to the performance of the amended algorithm is as follows.

 For m = 7, n = 106, r7(n) = 85917 n = 107, r7(n) = 1659610 n = 108, r7(n) = 28074245 n = 1.5x108, r7(n) = 44278091 For m = 8, n = 106, r8(n) = 41901 n = 107, r8(n) = 699420 n = 2x107, r8(n) = 1700394 n = 2.5x107, r8(n) = 2289191 n = 108, r8(n) = 14729653 n = 2x108, r8(n) = 33643957 n = 2.5x108, r8(n) = 43235625 For m = 9, n = 106, r9(n) = 8846 n =107, r9(n) = 505181 n =2x107, r9(n) =1168768 n =3x107, r9(n) =1865445 n =4x107, r9(n) =2589065 n =108, r9(n) = 6366874 n =2x108, r9(n) =14063176 n =3x108, r9(n) =23362855 n =4x108, r9(n) =34090513 n =4.5x108, r9(n) = 39647090

For m = 7, G(7) = 143, and with a search limit of n £ 1.5x108 and 10x accuracy we have:

 k c(7,k) Running Total Largest member 143 1 1 2175 142 2 3 141 3 6 140 4 10 139 5 15 138 6 21 137 7 28 136 8 36 135 9 45 134 10 55 133 12 67 4351 132 14 81 131 16 97 130 18 115 129 20 135 128 22 157 127 24 181 126 25 206 125 26 232 124 27 259 123 29 288 6527 122 31 319 121 33 352 120 35 387 119 37 424 118 39 463 117 41 504 116 42 546 115 43 589 114 44 633 113 46 679 8703 112 48 727 111 50 777 110 52 829 109 54 883 108 56 939 107 58 997 106 59 1056 105 61 1117 15253 104 64 1181 103 68 1249 102 72 1321 101 76 1397 100 80 1477 99 84 1561 98 88 1649 97 94 1743 16288 96 100 1843 95 107 1950 94 114 2064 93 121 2185 92 128 2313 91 135 2448 90 142 2590 89 149 2739 16299 88 155 2894 87 160 3054 86 163 3217 85 165 3382 84 166 3548 83 167 3715 82 168 3883 81 169 4052 80 171 4223 31619 79 174 4397 78 177 4574 77 182 4756 76 189 4945 75 198 5143 74 210 5353 33791 73 225 5578 72 242 5820 71 260 6080 70 278 6358 69 296 6654 68 313 6967 67 330 7297 80771 66 349 7646 65 371 8017 64 398 8415 80779 63 432 8847 62 473 9320 61 520 9840 60 577 10417 84604 59 645 11062 58 730 11792 111915 57 836 12628 158888 56 965 13593 175270 55 1114 14707 54 1287 15994 264311 53 1492 17486 312951 52 1742 19228 345138 51 2054 21282 50 2438 23720 703195 49 2917 26637 48 3538 30175 891634 47 4371 34546 1010822 46 5486 40032 1171822 45 6949 46981 1444817 44 8842 55823 1445197 43 11272 67095 1646753 42 14326 81421 2461307 41 18056 99477 2770216 40 22578 122055 3035495 39 28183 150238 4057060 38 35301 185539 4866984 37 44602 230141 6142323 36 57142 287283 6977755 35 74397 361680 8718067 34 97934 459614 9930770

and hence that G(7) £ 33. If we are willing to allow an accuracy of just 2, then this list continues:

 33 129608 589222 18641617 32 171924 761146 24137560 31 228757 989903 28640976 30 306877 1296780 34991627 29 421193 1717973 39958290 28 601523 2319496 64195986 27 894459 3213955 70390062

 n (mill) v(7,24,n) v(7,25,n) v(7,26,n) 10 784289 740077 667469 20 1614900 1337905 1042058 30 2237846 1724807 1245904 40 2694624 1956901 1340229 50 2865896 2007511 1350591 60 2983588 2031365 1353196 70 3050010 2042378 1354181 80 3078230 2045129 1354300 90 3090993 2045978 1354320 100 3102156 2046631 1354335 110 3107024 2046803 1354336 120 3108875 2046842 1354337 130 3110439 2046868 1354337 140 3111535 2046885 1354337 150 3112045 2046888 1354337

suggests that G(7) £ 25 and probably much lower.

For m = 8: g(8) = 279, and with a search limit of n £ 2.5x108 and 10x accuracy we have

 k c(8,k) Running Total Largest member 279 1 1 6399 278 2 3 277 3 6 276 4 10 275 5 15 274 6 21 273 7 28 272 8 36 271 9 45 270 10 55 269 11 66 268 12 78 267 13 91 266 14 105 265 15 120 264 16 136 263 17 153 262 18 171 261 19 190 260 20 210 259 21 231 258 22 253 257 23 276 256 24 300

{there are now 45 consecutive values from k = 255 down to k = 211 with common value

{c(8,k) = 25, the largest member of C(8,k) decrementing. We continue from k = 211

 211 25 1425 6331 210 26 1451 12960 209 27 1478 208 28 1506 207 29 1535 206 30 1565 205 31 1596 204 32 1628 203 33 1661 202 34 1695 201 35 1730 200 36 1766 199 37 1803 198 38 1841 197 39 1880 196 40 1920 195 41 1961 194 42 2003 193 43 2046 192 44 2090 191 45 2135 190 46 2181 189 47 2228 188 48 2276 187 49 2325 186 50 2375

{there are now 33 consecutive values from k = 185 down to k = 153 with common value

{c(8,k) = 51, the largest member of C(8,k) decrementing. We continue from k = 153.

 153 51 4058 12903 152 52 4110 65382 151 54 4164 150 57 4221 149 62 4283 130984 148 70 4353 147 81 4434 146 96 4530 145 115 4645 144 136 4781 143 159 4940 142 184 5124 141 210 5334 140 236 5570 139 262 5832 138 288 6120 137 315 6435 196507 136 343 6778 135 372 7150 134 403 7553 133 436 7989 132 471 8460 131 508 8968 130 547 9515 129 587 10102 128 629 10731 127 673 11404 126 718 12122 125 764 12886 124 811 13697 123 857 14554 122 901 15455 121 943 16398 120 982 17380 119 1019 18398 393094 118 1056 19455 117 1094 20549 116 1133 21682 115 1175 22857 114 1222 24079 113 1275 25354 112 1333 26687 111 1397 28084 521606 110 1469 29553 109 1549 31102 108 1636 32738 107 1730 34468 106 1831 36299 105 1938 38237 104 2051 40288 103 2170 42458 102 2297 44755 587132 101 2433 47188 100 2576 49764 99 2725 52489 98 2881 55370 97 3043 58413 96 3210 61623 95 3384 65007 589684 94 3568 68575 93 3762 72337 92 3967 76304 91 4183 80487 783750 90 4410 84897 89 4647 89544 849254 88 4895 94439 87 5153 99592 86 5425 105017 976465 85 5716 110733 1564999 84 6027 116760 83 6359 123119 82 6716 129835 81 7102 136937 1565000 80 7525 144462 1633127 79 8000 152462 2069605 78 8544 161006 77 9175 170181 2459462 76 9909 180090 3113536 75 10766 190856 74 11769 202625 3632168 73 12938 215563 5180712 72 14297 229860 5311781 71 15890 245750 70 17786 263536 69 20089 283625 5317318 68 22922 306547 5645069 67 26388 332935 5953609 66 30572 363507 6210907 65 35532 399039 64 41355 440394 7324680 63 48140 488534 9004812 62 56000 544534 10957613 61 65022 609556 10990412 60 75264 684820 12440111 59 86838 771658 16885770 58 99966 871624 57 114983 986607 17200330 56 132488 1119095 18235496

and hence that G(8) £ 55. If we are willing to allow an accuracy of just 2, then this list continues:

 55 153383 1272478 33590122 54 178904 1451382 39276776 53 210644 1662026 44485416 52 250573 1912599 51 301235 2213834 54706088 50 366173 2580007 95532007

 n (mill) v(4,47,n) v(4,48,n) v(8,49,n) 25 588499 502301 424106 50 695991 557654 449618 75 708932 560883 450231 100 716877 562556 450459 125 718158 562714 450469 150 718470 562741 450470 175 718612 562748 450470 200 718746 562754 450470 225 718829 562754 450470 250 718832 562754 450470

suggests that G(8) £ 48 and probably much lower.

For m = 9: g(9) = 548, and with a search limit of n £ 4.5x108 and 10x accuracy we have

 k c(9,k) Running Total Largest member 548 1 1 19455 547 2 3 546 3 6 545 4 10 544 5 15 543 6 21 542 7 28 541 8 36 540 9 45 539 10 55 538 11 66 537 12 78 536 13 91 535 14 105 534 15 120 533 16 136 532 17 153 531 18 171 530 19 190 529 20 210 528 21 231 527 22 253 526 23 276 525 24 300 524 25 325 523 26 351 522 27 378 521 28 406 520 29 435 519 30 465 518 31 496 517 32 528 516 33 561 515 34 595 514 35 630 513 36 666 512 37 703

{there are now 178 consecutive values from k = 511 down to k = 334 with common value

{c(9,k) = 38, the largest member of C(9,k) decrementing. We continue from k = 334.

 334 38 7467 19241 333 39 7506 255424 332 41 7547 331 44 7591 330 48 7639 329 53 7692 328 59 7751 327 66 7817 326 74 7891 325 83 7974 324 93 8067 323 104 8171 322 116 8287 321 128 8415 320 140 8555 319 152 8707 318 164 8871 317 176 9047 316 188 9235 315 200 9435 314 213 9468 275334 313 227 9875 312 242 10117 311 258 10375 310 275 10650 309 294 10944 281478 308 315 11259 307 337 11596 306 360 11956 305 384 12340 304 409 12749 303 435 13184 302 462 13646 301 489 14135 300 516 14651 299 543 15194 298 570 15764 297 596 16360 296 621 16981 295 645 17626 294 668 18294 293 690 18984 292 711 19695 291 731 20426 290 750 21176 289 768 21944 288 785 22729 287 801 23530 286 816 24346 285 830 25176 284 843 26019 283 856 26875 282 869 27744 281 882 28626 280 895 29521 279 908 30429 278 921 31350 277 934 32284 276 947 33231 275 959 34190 274 970 35160 273 980 36140 272 989 37129 271 997 38126 270 1004 39130 269 1010 40140 268 1015 41155 267 1019 42174 266 1022 43196 265 1024 44220

{there are now 44 consecutive values from k = 264 down to k = 221 with common value

{c(9k) = 1025, the largest member of C(9,k) decrementing. We continue from k = 221.

 221 1025 89320 281390 220 1026 90346 511424 219 1028 91374 218 1031 92405 217 1035 93440 216 1040 94480 215 1047 95527 517568 214 1056 96583 213 1067 97650 212 1080 98730 211 1095 99825 210 1112 100937 209 1131 102068 208 1152 103220 543622 207 1176 104396 1035697 206 1203 105599 205 1233 106832 204 1266 108098 203 1300 109398 202 1337 110735 1041841 201 1379 112114 200 1426 113540 199 1478 115018 198 1535 116553 197 1597 118150 196 1664 119814 195 1737 121551 1067895 194 1818 123369 1559970 193 1907 125276 192 2003 127279 191 2107 129386 190 2218 131604 189 2336 133940 1566114 188 2461 136401 187 2592 138993 186 2729 141722 185 2872 144594 184 3021 147615 183 3176 150791 182 3337 154128 1592168 181 3505 157633 2084243 180 3680 161313 179 3861 165174 178 4048 169222 177 4241 173463 2097542 176 4442 177905 2104695 175 4654 182559 2111848 174 4879 187438 173 5119 192557 172 5375 197932 171 5647 203579 170 5935 209514 169 6239 215753 2116441 168 6559 222312 167 6894 229206 166 7243 236449 165 7606 244055 164 7982 252037 163 8368 260405 162 8760 269165 161 9153 278318 160 9542 287860 159 9923 297783 4050648 158 10295 308078 4057801 157 10661 318739 4064954 156 11027 329766 155 11400 341166 5996614 154 11787 352953 153 12195 365148 152 12631 377779 151 13101 390880 5996629 150 13609 404489 149 14160 418649 148 14761 433410 147 15420 448830 7851320 146 16145 464975 145 16943 481918 144 17818 499736 143 18772 518508 7942567 142 19804 538312 141 20914 559226 140 22105 581331 9895688 139 23384 604715 138 24764 629479 137 26261 655740 9928910 136 27896 683636 11729682 135 29691 713327 134 31663 744990 11882026 133 33824 778814 132 36179 814993 131 38726 853719 130 41463 895182 129 44380 939562 128 47467 987029 13734690 127 50708 1037737 13833099 126 54081 1091818 125 57566 1149384 19685315 124 61144 1210528 123 64796 1275324 122 68522 1343846 121 72328 1416174 120 76234 1492408 20065576 119 80264 1572672 118 84441 1657113 20262425 117 88784 1745897 116 93312 1839209 115 98035 1937244 26120776 114 102970 2040214 28072877 113 108129 2148343 112 113516 2261859 111 119123 2380982 110 124941 2505923 28073895 109 130964 2636887 108 137173 2774060 39792637 107 143558 2917618 39910754 106 150123 3067741 105 156884 3224625 104 163857 3388482 103 171045 3559527 40172898 102 178451 3737978 40291015 101 186100 3924078 41607981 100 194036 4118114 99 202311 4320425

and hence that G(9) £ 98. If we are willing to allow an accuracy of just 2, then this list continues:

 98 210991 4531416 49590969 97 220192 4751608 49709086 96 230092 4981700 59276841 95 240936 5222636 63183088 94 253042 5475678 93 266764 5742442 92 282452 6024894 76238446 91 300413 6325307 92302806 90 320901 6646208 89 344177 6990385 114579879 88 370518 7360903 128867236 87 400257 7761160 86 433804 8194964 85 471641 8666605 132614091 84 514284 9180889 83 562211 9743100 209571889 82 615894 10358994 81 675879 11034873 80 742876 11777749 79 817811 12595560 211522454 78 901904 13497464 212203715