Chapter 6

Counting Sums of Two Powers

In Chapter 1, I mentioned the idea of coincidences, which are sets of Euler representations of the same power. In general, these are few and far between except when the powers being considered are low, i.e. m = 5 or less. However, for squares, and to a lesser extent cubes, the number of coincidences is so high that it is worthwhile changing tack temporarily to consider counting solutions rather than simply listing them. As such, we have the following.

Definition: Let P(m,n,y) denote the number of coincidences of at least n different expressions of the form aim + bim for i = 1 to n, where ai and bi are positive integers less than or equal to y whose highest common factor is 1.

As a demonstration, the following is a list of those equations contributing to P(2,2,13):

72 + 12 = 52 + 52

82 + 12 = 72 + 42

92 + 22 = 72 + 62

112 + 22 = 102 + 52

112 + 32 = 92 + 72

122 + 12 = 92 + 82

132 + 12 = 112 + 72

132 + 42 = 112 + 82

Thus P(2,2,13) = 8. Now consider m = 2 and n = 2, and let p(y) = P(2,2,y). Then

p(5) = 0

p(30) = 63

p(55) = 271

p(80) = 614

p(10) = 3

p(35) = 95

p(60) = 317

p(85) = 706

p(15) = 11

p(40) = 124

p(65) = 388

p(90) = 797

p(20) = 24

p(45) = 168

p(70) = 449

p(95) = 896

p(25) = 42

p(50) = 214

p(75) = 536

p(100) = 993

 

Now consider m =2 and n = 3 and let q(y) = P(2,3,y). The earliest solution is found for y = 18: 182 + 12 = 172 + 62 = 152 + 102. Note that this solution contributes twice to P(2,2,y), and, in general, a solution for P(m,n,y) contributes at most n-k+1 solutions to P(m,k,y). We have

q(5) = 0

q(30) = 7

q(55) = 45

q(80) = 127

q(10) = 0

q(35) = 12

q(60) = 58

q(85) = 152

q(15) = 0

q(40) = 17

q(65) = 73

q(90) = 173

q(20) = 2

q(45) = 25

q(70) = 88

q(95) = 203

q(25) = 3

q(50) = 36

q(75) = 105

q(100) = 226

 

For m = 2 and n = 4, let r(y) = P(2,4,y). Then

r(10) = 0

r(60) = 13

r(20) = 0

r(70) = 23

r(30) = 0

r(80) = 35

r(40) = 2

r(90) = 53

r(50) = 7

r(100) = 72

 

We list all the equations contributing to r(50):

332 + 42 = 322 + 92 = 312 + 122 = 242 + 232

402 + 52 = 372 + 162 = 352 + 202 = 292 + 282

432 + 62 = 422 + 112 = 382 + 212 = 342 + 272

462 + 32 = 422 + 192 = 452 + 102 = 352 + 302

472 + 12 = 432 + 192 = 412 + 232 = 372 + 292

492 + 22 = 472 + 142 = 462 + 172 = 382 + 312

492 + 82 = 472 + 162 = 442 + 232 = 412 + 282

We will now analyse P(m,n,y) in more detail. It is apparent from the available data that P(m,n,y) grows exponentially relative to y, and if we plot log p(y) against log y on a graph, it appears that the best fit curve through these points is a straight line with a gradient of 2. This implies that p(y) is proportional to y2. Drawing another graph, this time of p(y) against y2, we obtain the approximation

p(y) » 0.115 y2

Substituting y for known values of p(y) shows a good correspondence, as follows.

y

actual p(y)

estimated p(y)

100

993

1150

200

4521

4600

300

10740

400

19739

500

31630

600

46394

 

700

64148

 

800

84920

 

900

108566

 

1000

135312

 

 

Proceeding analogously for q(y) = P(2,3,y) we obtain

q(y) » 0.0306 y2

which also gives a good correspondence for known values, as follows.

y

actual q(y)

estimated q(y)

100

226

 

200

1264

 

300

3286

 

400

6418

 

500

10704

 

600

16174

 

700

22890

 

800

30885

 

900

40123

 

1000

50716

 

 

From the above examination it can be conjectured that

P(2,n,y) = O(y2) for all n > 1,

i.e.

® c as n ® ¥ for some constant c.

This is backed up when the same treatment is carried through for n = 4 and n = 5 to obtain

P(2,4,y) » 0.01476 y2

P(2,5,y) » 0.0031472 y2

giving estimated P(2,4,1000) = 13813 and P(2,5,1000) = 2780.

With P(3,2,y) the log graph indicates a linear relationship between P(3,2,y) and given by

P(3,2,y) » 0.063

 

The following table exhibits the correspondence of this equation with actual values.

y

P(3,2,y)

estimated

100

27

23

200

63

64

300

116

114

400

167

169

500

228

230

600

305

295

700

382

 

800

450

 

900

542

 

1000

632

 

 

The results obtained hint that P(m,n,y) may be proportional to . We shall, without any additional theoretical justification, proceed as if this were so.

Definition: Let c(m,n) = lim (y® ¥ )

Hence c(3,2) = 0.063.

For m = 4 we must turn to the previously published results of Lander, Parkin & Selfridge, which give all the equations leading to the calculation of P(4,2,15000) = 45. Applying the treatment we obtain a very rough estimate that

P(4,2,y) » 0.0028 y.

We now have

c(2,2) = 0.115, c(3,2) = 0.063, c(4,2) = 0.0028.

A graph of c(m,2) against n is a very vague object, being of only 3 points, but a smooth curve passing through these points seems to be slightly convex and cuts the m-axis at about the value 4.7. I put this forward as a rough justification that c(5,2), indeed c(m,2) for all m ³ 5, does not exist, and consequently that the equation

am + bm = cm + dm

has no non-trivial solutions in positive integers for m ³ 5.

Let us now consider the smallest contributing solution for particular values of m and n.

Definition: Let Q(m,n) be the smallest y such that P(m,n,y) ¹ 0.

We have Q(2,2) = 7, Q(2,3) = 18 and Q(2,4) = 33. Also, Q(2,5) = 73, the smallest contributing expression being

732 + 142 = 712 + 222 = 702 + 252 = 622 + 412 = 552 + 502

and Q(2,6) = 74, the smallest contributing expression here being

742 + 72 = 732 + 142 = 712 + 222 = 702 + 252 = 622 + 412 = 552 + 502

The following additional results were established relatively quickly.

n

Q(2,n)

7

164

8

165

9

268

10

371

11

399

12

400

 

Let us consider the problem of finding Q(n,k). In the following treatment, much of the theory can be found in the book "The Theory of Numbers" by Hardy & Wright.

Suppose that t is a non-square positive integer, and let r(t) denote the number of representations of t as the sum of two integer squares, this being a standard definition. Then r(t) = 8.r’(t) where r’(t) is the number of distinct representations in positive integers. Suppose that t is odd and that t = u.v where (u,v) = 1 and

u is the product of the highest powers of all primes p dividing t such that p º 1 mod 4, and

v is the product of the highest powers of all primes q dividing t such that q º 3 mod 4.

Then it is known (from H & W) that r(t) = 4.d(u) if v is a square, and zero otherwise, where d is the usual divisor function. That is, r’(t) = if v is a square.

Now suppose that t = y2 + z2 where y ³ z > 0. Clearly y is bounded above by [Ö t]. If t is also an integer such that r’(t) = k, then [Ö t] is an upper bound for Q(2,k).

Clearly, as will be seen, for any k we can obtain an odd integer t such that u = t, v = 1 and

d(u) = d(t) = 2.k, and deduce that Q(2,k) £ [Ö t].

For any k, 52k-1 satisfies all the criteria, and thus

Q(2,k) £ [5k-1 Ö 5] for all k ³ 1.

Thus, for example, Q(2,3) £ 55. But we also have that

2.k = 6 = 3.2 = (2+1).(1+1) = d(52.13)

and so we obtain Q(2,3) £ 18, which is a significant improvement. In fact, as we have seen, it is known that Q(2,3) = 18.

We can proceed similarly for all other k, e.g.

Q(2,4) : 2.k = 8 = 2.2.2 = (1+1).(1+1).(1+1) = d(5.13.17), giving Q(2,4) £ 33.

Q(2,5) : 2.k = 10 = 5.2 = (4+1).(1+1) = d(54.13), giving Q(2,5) £ 90.

Q(2,6) : 2.k = 12 = 3.2.2 = (2+1).(1+1).(1+1) = d(52.13.17), giving Q(2,6) £ 74.

Here, since it is obvious that Q(n,k-1) < Q(n,k), we actually have Q(2,5) £ 73. Proceeding to higher values we have

k

Q(2,k) limit

7

(450)

8

179

9

268

10

371

11

(11267)

12

400

13

(56336)

14

(1858)

15

(1340)

16

1088

17

(1408418)

18

1443

19

(7042092)

20

2001

21

(6700)

22

(46456)

23

(176052308)

24

2434

 

where a number is bracketed if there is a number below it that is smaller.

Thus, for example, Q(2,13) < Q(2,14) < Q(2,15) < Q(2,16) £ 1088. The theory provides the existence of Q(2,n) for all m ³ 2 and provides an algorithm which gives very good upper bounds, as will be seen from the next table, which presents the actual values obtained by me in 1987 using a CRAY computer situated at the University of London Computer Centre.

k

Q(2,k)

k

Q(2,k)

k

Q(2,k)

k

Q(2,k)

2

7

8

165

14

886

20

2000

3

18

9

268

15

890

21

2417

4

33

10

371

16

895

22

2426

5

73

11

399

17

1437

23

2433

6

74

12

400

18

1443

24

2434

7

164

13

881

19

1996

 

 

 

This shows that the theoretical upper bound is exact for k = 9, 10, 12, 18 and 24 and only one out for k = 20.

A further result of Hardy & Wright proves the analogous statement for cubes, , i.e. that Q(3,n) exists for all n ³ 2, although in this case the mathematics is more complicated and there is no convenient method for obtaining upper bounds in this case. However, Leech [15] found the solution

4363 + 1673 = 4233 + 2283 = 4143 + 2553

to give Q(3,3) = 436, and we have found that P(3,3,600) = 3.

Additionally, the equation 190833 + 24213 = 189483 + 54363 = 180723 + 102003 = 166303 + 133223

implies that Q(3,4) £ 19083.

Note: For n = 4, Q(4,2) = 158 since 1584 + 594 = 1344 + 1334 is the smallest such equation.

 

The standard algorithm used to locate and count equations contributing to P(m,2,y) is as follows, where, initially, lines marked with an asterisk or a dollar should be ignored and z is the accumulated count.

z = 0 (or as required if not starting from 1)

$ n = 2 (or as required)

for a between amin and amax do

for b between 1 and a-1 do

t = am + bm

c = a-1

* w = 1

while c >

if c = b then goto MARK endif

s = t - cm

if s £ 0 then goto MARK endif

q = round()

if qm ¹ s then goto MARK endif

if gcd(a,b,c,q) = 1 then

* increment w

* if w = n then

display a, b, c, q (optional)

increment z

$ increment n

c = 0

* endif

endif

MARK: decrement c

endwhile

endfor

endfor

display z

The three uses of the ‘goto’ jump are used to proceed to the next iteration of the while loop prematurely when conditions arise that obviously will not lead to a solution. Also, once a single non-trivial solution is found for a particular a and b, there is no need to continue, and so the loop variable is reset to ensure that the while loop terminates immediately.

In order to find solutions for larger n, an additional variable w may be used as in the above lines marked with an asterisk. There is one disadvantage here in that it is possible for non-trivial solutions for n > 2 to be missed due to the gcd calculation. In other words, it is possible that the equations a2 + b2 = c2 + d2 and a2 + b2 = e2 + f2 may separately have greatest common divisors in excess of 1, so that they do not contribute to P(2,2,y), but considered as a single triple solution a2 + b2 = c2 + d2 = e2 + f2 do have a greatest common divisor of 1 and so contribute to P(2,3,y). This does not happen often, but in order to ensure that such solutions for n > 2 are included, it is advisable to remove the gcd check and store the elements of the solution temporarily, only performing a gcd check after a possible solution has been found. In terms of the algorithm, the entire "if gcd" section should be replaced by the following :

increment w

if w < n then

store current pair

else (if w = n then)

if gcd of all n pairs = 1 then

display all n pairs (optional)

increment z

c = 0

else

decrement w (i.e. keep the first n-1 pairs)

endif

endif

The algorithm may also be modified to find Q(m,n) for a range of n by including n as a variable rather than a fixed value and incrementing every time that the ‘w = n’ condition is satisifed, as in the above lines marked with a dollar. Since the first solution for a particular n must be non-trivial, the gcd check is not required at all.

For completeness, the solutions for Q(2,n) and n £ 24 are as follows :

n = 2: 72 + 12 = 52 + 52

n = 3: 182 + 12 = 172 + 62 = 152 + 102

n = 4: 332 + 42 = 322 + 92 = 312 + 122 = 242 + 232

n = 6 and 5: 742 + 72 = 732 + 142 = 712 + 222 = 702 + 252 = 622 + 412 = 552 + 502

n = 8 and 7: 1652 + 202 = 1642 + 272 = 1602 + 452 = 1552 + 602 = 1442 + 832 = 1412 + 882 = 1322 + 1012 = 1202 + 1152

n = 9: 2682 + 12 = 2652 + 402 = 2602 + 652 = 2572 + 762 = 2472 + 1042 = 2362 + 1272 = 2152 + 1602 = 2082 + 1692 = 1912 + 1882

n = 10: 3712 + 222 = 3702 + 352 = 3652 + 702 = 3552 + 1102 = 3502 + 1252 = 3342 + 1632 = 3172 + 1942 = 3102 + 2052 = 3012 + 2182 = 2752 + 2502

n = 12 and 11: 4002 + 152 = 3992 + 322 = 3932 + 762 = 3922 + 812 = 3842 + 1132 = 3752 + 1402 = 3112 + 2522 = 3602 + 1752 = 3562 + 1832 = 3372 + 2162 = 3292 + 2282 = 3002 + 2652

n = 16, 15, 14, and 13: 8952 + 102 = 8902 + 952 = 8862 + 1272 = 8812 + 1582 = 8742 + 1932 = 8652 + 2302 = 8622 + 2412 = 8302 + 3352 = 8152 + 3702 = 7852 + 4302 = 7692 + 4582 = 7662 + 4632 = 7222 + 5292 = 7102 + 5452 = 7032 + 5542 = 6552 + 6102

 

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