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 a_{i}^{m} + b_{i}^{m} 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):
7^{2} + 1^{2} = 5^{2} + 5^{2}
8^{2} + 1^{2} = 7^{2} + 4^{2}
9^{2} + 2^{2} = 7^{2} + 6^{2}
11^{2} + 2^{2} = 10^{2} + 5^{2}
11^{2} + 3^{2} = 9^{2} + 7^{2}
12^{2} + 1^{2} = 9^{2} + 8^{2}
13^{2} + 1^{2} = 11^{2} + 7^{2}
13^{2} + 4^{2} = 11^{2} + 8^{2}
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: 18^{2} + 1^{2} = 17^{2} + 6^{2} = 15^{2} + 10^{2}. Note that this solution contributes twice to P(2,2,y), and, in general, a solution for P(m,n,y) contributes at most nk+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):
33^{2} + 4^{2} = 32^{2} + 9^{2} = 31^{2} + 12^{2} = 24^{2} + 23^{2}
40^{2} + 5^{2} = 37^{2} + 16^{2} = 35^{2} + 20^{2} = 29^{2} + 28^{2}
43^{2} + 6^{2} = 42^{2} + 11^{2} = 38^{2} + 21^{2} = 34^{2} + 27^{2}
46^{2} + 3^{2} = 42^{2} + 19^{2} = 45^{2} + 10^{2} = 35^{2} + 30^{2}
47^{2} + 1^{2} = 43^{2} + 19^{2} = 41^{2} + 23^{2} = 37^{2} + 29^{2}
49^{2} + 2^{2} = 47^{2} + 14^{2} = 46^{2} + 17^{2} = 38^{2} + 31^{2}
49^{2} + 8^{2} = 47^{2} + 16^{2} = 44^{2} + 23^{2} = 41^{2} + 28^{2}
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 y^{2}. Drawing another graph, this time of p(y) against y^{2}, we obtain the approximation
p(y) » 0.115 y^{2}
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 y^{2}
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(y^{2}) 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 y^{2}
P(2,5,y) » 0.0031472 y^{2}
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 maxis 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
a^{m} + b^{m} = c^{m} + d^{m}
has no nontrivial 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
73^{2} + 14^{2} = 71^{2} + 22^{2} = 70^{2} + 25^{2} = 62^{2} + 41^{2} = 55^{2} + 50^{2}
and Q(2,6) = 74, the smallest contributing expression here being
74^{2} + 7^{2} = 73^{2} + 14^{2} = 71^{2} + 22^{2} = 70^{2} + 25^{2} = 62^{2} + 41^{2} = 55^{2} + 50^{2}
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 nonsquare 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 = y^{2} + z^{2} 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, 52k1 satisfies all the criteria, and thus
Q(2,k) £ [5^{k1} Ö 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(5^{2}.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(5^{4}.13), giving Q(2,5) £ 90.
Q(2,6) : 2.k = 12 = 3.2.2 = (2+1).(1+1).(1+1) = d(5^{2}.13.17), giving Q(2,6) £ 74.
Here, since it is obvious that Q(n,k1) < 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
436^{3} + 167^{3} = 423^{3} + 228^{3} = 414^{3} + 255^{3}
to give Q(3,3) = 436, and we have found that P(3,3,600) = 3.
Additionally, the equation 19083^{3} + 2421^{3} = 18948^{3} + 5436^{3} = 18072^{3} + 10200^{3} = 16630^{3} + 13322^{3}
implies that Q(3,4) £ 19083.
Note: For n = 4, Q(4,2) = 158 since 158^{4} + 59^{4} = 134^{4} + 133^{4} 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 a1 do
t = a^{m} + b^{m}
c = a1
* w = 1
while c >
if c = b then goto MARK endif
s = t  c^{m}
if s £ 0 then goto MARK endif
q = round()
if q^{m} ¹ 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 nontrivial 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 nontrivial solutions for n > 2 to be missed due to the gcd calculation. In other words, it is possible that the equations a^{2} + b^{2} = c^{2} + d^{2} and a^{2} + b^{2} = e^{2} + f^{2} 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 a^{2} + b^{2} = c^{2} + d^{2} = e^{2} + f^{2} 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 n1 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 nontrivial, the gcd check is not required at all.
For completeness, the solutions for Q(2,n) and n £ 24 are as follows :
n = 2: 7^{2} + 1^{2} = 5^{2} + 5^{2}
n = 3: 18^{2} + 1^{2} = 17^{2} + 6^{2} = 15^{2} + 10^{2}
n = 4: 33^{2} + 4^{2} = 32^{2} + 9^{2} = 31^{2} + 12^{2} = 24^{2} + 23^{2}
n = 6 and 5: 74^{2} + 7^{2} = 73^{2} + 14^{2} = 71^{2} + 22^{2} = 70^{2} + 25^{2} = 62^{2} + 41^{2} = 55^{2} + 50^{2}
n = 8 and 7: 165^{2} + 20^{2} = 164^{2} + 27^{2} = 160^{2} + 45^{2} = 155^{2} + 60^{2} = 144^{2} + 83^{2} = 141^{2} + 88^{2} = 132^{2} + 101^{2} = 120^{2} + 115^{2}
n = 9: 268^{2} + 1^{2} = 265^{2} + 40^{2} = 260^{2} + 65^{2} = 257^{2} + 76^{2} = 247^{2} + 104^{2} = 236^{2} + 127^{2} = 215^{2} + 160^{2} = 208^{2} + 169^{2} = 191^{2} + 188^{2}
n = 10: 371^{2} + 22^{2} = 370^{2} + 35^{2} = 365^{2} + 70^{2} = 355^{2} + 110^{2} = 350^{2} + 125^{2} = 334^{2} + 163^{2} = 317^{2} + 194^{2} = 310^{2} + 205^{2} = 301^{2} + 218^{2} = 275^{2} + 250^{2}
n = 12 and 11: 400^{2} + 15^{2} = 399^{2} + 32^{2} = 393^{2} + 76^{2} = 392^{2} + 81^{2} = 384^{2} + 113^{2} = 375^{2} + 140^{2} = 311^{2} + 252^{2} = 360^{2} + 175^{2} = 356^{2} + 183^{2} = 337^{2} + 216^{2} = 329^{2} + 228^{2} = 300^{2} + 265^{2}
n = 16, 15, 14, and 13: 895^{2} + 10^{2} = 890^{2} + 95^{2} = 886^{2} + 127^{2} = 881^{2} + 158^{2} = 874^{2} + 193^{2} = 865^{2} + 230^{2} = 862^{2} + 241^{2} = 830^{2} + 335^{2} = 815^{2} + 370^{2} = 785^{2} + 430^{2} = 769^{2} + 458^{2} = 766^{2} + 463^{2} = 722^{2} + 529^{2} = 710^{2} + 545^{2} = 703^{2} + 554^{2} = 655^{2} + 610^{2}