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) = 2^m + [(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 f_m(n) denote the length of the minimal representation of the positive integer n as a sum of mth powers, so that g(m) = max (f_m(n) : n e N).

Definition: Let v(m,k,n) be the counting function for f_m, so that v(m,k,n) = |{p e N: p £ n, f_m(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: f_m(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 f_m, it is obvious that an alternative definition is as follows:

f_m(n) = { 1 if n = p^m for some p

{ min (f_m(n - p^m) + 1 : p^m < 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 f_m 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.2x10⁸ 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 f_m(n) for much higher values of n, to conjecture that C(3,5) is also finite, approximately 1.12x10⁸, and thus that G(3) = 4. For completeness we present the following table.

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

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

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

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 1^m 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.2x10⁸ and 10x accuracy we have:

{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.

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

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

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.2x10⁸, 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.2x10⁸ 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 1^m, with increasing likelihood as m increases, and in this case we have f_m(n) = f_m(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 f_m(k) where

k < n and such that f_m(k) £ f_m(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 R_m, and we let r_m(n) be the number of k e R_m such that k < n.

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

f_m(n-p^m) = f_m(k) + [(n-p^m) - k],

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

The most obvious way of locating the correct value of k between 1 and r_m(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.2x10⁸ values of f_m can store 4.5x10⁷ members of R_m, noting that we must now store both k and f_m(k). Unfortunately, for small m, r_m(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, G(7) = 143, and with a search limit of n £ 1.5x108 and 10x accuracy we have:

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

Additionally, the table of values

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

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

{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

{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.

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

Additionally, the table of values

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

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

{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.

{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.

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

Additionally, the table of values

suggests that G(9) £ 69. Examination of values for k even lower shows a similar trend, though the deceleration effect takes longer to manifest, and it is quite probable that G(9) may be less than 60. The current experimental limit of 4.5x10⁸ is therefore good, but not quite good enough. A limit of 5x10⁸ may well be possible given current resources. Ideally a limit of 2x10⁹ may provide the real answers.

For m = 10, the weight of data to be processed is considerable. However, with available resources we can reach a limit on n of 5x10⁸. This suggests that G(10) £ 209 to 10x accuracy and G(10) £ 153 to 2x accuracy. As with the m = 9 case, the data indicates that G(10) is in fact much lower than this, but the search limit would have to be pushed much higher before evidence of this is convincing.

URL : www.glasgowg43.freeserve.co.uk/chapter7.htm