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

 

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