Chapter 8

Extending Waring’s Problem

Waring’s Problem involves finding representations of positive integers in terms of sums of powers of positive integers. As in previous chapters, the logical extension of this is to allow powers to be added or subtracted, as in equation 3.2:

x = (8.1)

Definition: Let g*(m) be the minimum value of k such that it is possible to express every positive integer in the form of equation 8.1, where each y_i is positive, and let G*(m) be the minimum needed to express all but a finite set of integers. Related definitions in Chapter 7 are similarly carried over to the extended case.

In the normal case, each of the individual components y_i^m is less than or equal to x. This restriction does not apply in the extended case. However, since x is positive, at least one of the y_i must have a positive sign, and, as in Chapter 5, if there are j of these, then we label them y₁ to y_j such that y₁ ³ y₂ ³ .... ³ y_j, and label the negatively signed components as y_j+1 to y_k such that y_j+1 ³ y_j+2 ³ .... ³ y_k. Since we are interested in minimal length representations only, there is no overlap between the positively and negatively signed y_i.

The case for m = 2 is of little interest, as every odd number can be represented as the difference between two consecutive squares, and every even number is only 1^m away. Thus we have g*(2) = G*(2) = 3.

For higher powers, any direct numerical investigation is complicated by the fact that y₁ and y_j are basically unlimited. As a starting point, it is obvious that g*(m) £ g(m) and G*(m) £ G(m). We may then consider placing sensible search bounds on y₁ and y_j in the hope of finding representations for most integers in the ranges covered, and then increase these bounds only for integers for which a representation has not already been found. An inherent problem is that any representation found may be bettered by one outwith the search limits, and so these limits must be set at a level sufficient to provide good results.

The original algorithm used for bases m = 3, 5 and 6 in Chapter 7 may be extended to consider the additional possibilities as follows:

We have, as in Chapter 7, that f_m(n) = { 1 if n = pm for some p

{ min (fm(n-p^m) + 1 : p^m < n

We now may also consider subtracting n from a larger power before using the above, i.e.

f_m*(n) = 1 if n = p^m for some p, and otherwise the minimum of f_m*(n-p^m) + 1 for p^m < n and

f_m*(q^m -n-p^m) + 2 for some n < q^m < 2n, p^m < q^m -n.

This is not exhaustive, but has the advantage of providing a predetermined limit to each calculation, although the processing overhead is substantially increased.

With this in place, we have the following results.

m = 3. A search to n = 2.85*10⁵ shows no value requiring more than 6 powers, i.e. g*(3) £ 6. The only values of n actually requiring 6 powers are 77 and 842. Thus G*(3) £ 5. For k = 5 we have the following:

At this point there is little to suggest that C*(3,5) is finite.

m = 4. A quick search to n = 10⁵ indicates that g*(4) £ 11, with the only values of n requiring 11 powers being 121, 122, 297 and 4217. With a search limit of n = 10⁶, it is apparent that only 255 values of n, the largest being 76537, require 10 powers. Thus G*(4) £ 9. For values requiring 9 powers, and a limit of n = 2.10⁷ , we have the following :

This is sufficient to give us confidence about ultimate convergence of v(4,9,n), and hence that G*(4) £ 8.

m = 5. A quick search to 10⁵ indicates that g*(5) £ 19. A more extensive search to 2.10⁷ provides the following to 10x accuracy.

Thus G*(5) £ 9. If we allow 5x accuracy, then we also have

The next table presents available data for k = 8. No inferences may be drawn.

m = 6. A brief search to n = 10⁵ suggests that g*(6) £ 37. A more thorough search to n = 10⁷ provides the following results.

Thus G*(6) £ 13. To 2x accuracy, this continues :

suggesting G*(6) £ 12. Additionally, we have the following :

This strongly suggests that v(6,12,n) approaches a limit and hence that G*(6) £ 11.

m = 7. A quick search to n = 10⁵ gives g*(7) £ 75. A more thorough search to n = 5*10⁷ provides the following data to 10x accuracy.

This implies that G*(7) £ 19. To 2x accuracy, this improves to G*(7) £ 16 using the values

The available data suggests that G*(7) is lower still.

In a similar vein, brief searches give the following limits on g*(m):

With a limit of n = 5*10⁷, we also have the following limits on G*(m):

The general formula for g(m) is 2^m + [(1.5)^m] - 2. From the data presented above, it appears that g*(m) is approximately proportional to 2^{m- 1}. In fact, if we consider g*(m) = 2g(m)+k(m) where k(m) is an error value, we have the following :

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