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_{1} to y_{j} such that y_{1} ³ y_{2} ³ .... ³ 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_{1} 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_{1} 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(np^{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}*(np^{m}) + 1 for p^{m} < n and
f_{m}*(q^{m} np^{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^{5} 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 = 10^{5} 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^{6}, 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^{7} , 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 10^{5} indicates that g*(5) £ 19. A more extensive search to 2.10^{7} 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 = 10^{5} suggests that g*(6) £ 37. A more thorough search to n = 10^{7 }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 = 10^{5} gives g*(7) £ 75. A more thorough search to n = 5*10^{7} 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*10^{7}, 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 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 :
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 