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