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 yi 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 yim 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 yi must have a positive sign, and, as in Chapter 5, if there are j of these, then we label them y1 to yj such that y1 ³ y2 ³ .... ³ yj, and label the negatively signed components as yj+1 to yk such that yj+1 ³ yj+2 ³ .... ³ yk. Since we are interested in minimal length representations only, there is no overlap between the positively and negatively signed yi.

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 1m away. Thus we have g*(2) = G*(2) = 3.

For higher powers, any direct numerical investigation is complicated by the fact that y1 and yj 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 y1 and yj 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 fm(n) = { 1 if n = pm for some p

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

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

fm*(n) = 1 if n = pm for some p, and otherwise the minimum of fm*(n-pm) + 1 for pm < n and

fm*(qm -n-pm) + 2 for some n < qm < 2n, pm < qm -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*105 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:

 n v(3,5,n) 2000000 44708

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

m = 4. A quick search to n = 105 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 = 106, 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.107 , we have the following :

 n v(4,9,n) 1000000 31134 2000000 39480 3000000 44176 4000000 46485 5000000 47549 6000000 48335 7000000 49110 8000000 49360 9000000 49503 10000000 49600 11000000 49686 12000000 49765 13000000 49785 14000000 49810 15000000 49828 16000000 49839 17000000 49855 18000000 49858 19000000 49863 20000000 49866

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 105 indicates that g*(5) £ 19. A more extensive search to 2.107 provides the following to 10x accuracy.

 k c*(5,k) largest member(s) of C*(5,k) 19 2 112 & 113 18 4 80, 81, 111 & 114 17 8 48, 49, 79, 82, 110, 115, 358, 359 16 12 360 15 19 1467 14 39 1532 13 73 1533 12 133 7361 11 415 20052 10 2420 267588

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

 k c*(5,k) largest member(s) of C*(5,k) 9 17132 1591684

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

 n v(5,8,n) 1000000 164694 2000000 232453 3000000 277931 4000000 311818 5000000 340865 6000000 363851 7000000 380870 8000000 395845 9000000 411007 10000000 423666 11000000 434541 12000000 446124 13000000 454767 14000000 464570 15000000 472356 16000000 481210 17000000 489618 18000000 496644 19000000 504331 20000000 510717

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

 k c*(6,k) largest member(s) of C*(6,k) 37 2 352 & 353 36 4 288, 289, 351 & 354 35 6 355 34 8 356 33 10 357 32 13 1803 31 16 1804 30 20 1805 29 24 1806 28 29 2017 27 40 2081 26 61 6046 25 94 6110 24 130 6174 23 159 7635 22 208 22524 21 412 23320 20 679 23321 19 863 54449 18 1275 58452 17 1987 58801 16 3249 123916 15 4786 231700 14 8066 880364

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

 13 21112 2410110

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

 N v(6,12,n) 100000 12900 200000 25589 300000 35844 400000 43951 500000 51826 600000 56165 700000 61688 800000 67975 900000 73123 1000000 76030 1500000 92977 2000000 97258 2500000 101337 3000000 101634 3500000 101981 4000000 102295 4500000 102441 5000000 102565 6000000 102837 7000000 102852 8000000 102880 9000000 102907 10000000 102910

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

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

 k c*(7,k) largest member(s) of C*(7,k) 75 2 7649 & 7650 74 6 7651 73 12 7652 72 20 7653 71 32 8170 70 49 8171 69 69 8172 68 91 8173 67 110 8174 66 120 8175 65 126 8176 64 128 8177 63 128 8178 62 128 8179 61 128 8180 60 128 8181 59 128 8182 58 128 8183 57 128 8184 56 128 8185 55 128 8186 54 128 8187 53 134 23761 52 144 23889 51 162 24533 50 191 24534 49 246 24535 48 284 24536 47 342 24537 46 382 24538 45 382 24539 44 382 24540 43 389 38222 42 401 40284 41 416 40412 40 433 40542 39 461 40671 38 496 40799 37 538 40927 36 572 40928 35 612 40929 34 655 40930 33 746 40931 32 844 115885 31 999 116013 30 1285 117176 29 1737 117177 28 2168 410717 27 2943 410973 26 4515 418996 25 7900 977707 24 12173 1235026 23 19429 2023173 22 36512 2383416 21 66450 3144070 20 111544 4762437

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

 19 160363 9715403 18 238530 14075487 17 422178 17915788

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

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

 m g*(m) 8 140 9 274 10 540

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

 m G*(m) 10x G*(m) 2x 8 32 28 9 80 48 10 154 120

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

 m = 3 4 5 6 7 8 9 10 11 12 13 14 k(m) 3 3 1 1 7 1 0 1 0 1 0 1