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):

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

Now consider m =2 and n = 3 and let q(y) = P(2,3,y). The earliest solution is found for y = 18: 18² + 1² = 17² + 6² = 15² + 10². 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

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

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

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². Drawing another graph, this time of p(y) against y², we obtain the approximation

p(y) » 0.115 y²

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

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

q(y) » 0.0306 y²

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

From the above examination it can be conjectured that

P(2,n,y) = O(y²) 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²

P(2,5,y) » 0.0031472 y²

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.

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

a^m + b^m = c^m + d^m

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

73² + 14² = 71² + 22² = 70² + 25² = 62² + 41² = 55² + 50²

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

74² + 7² = 73² + 14² = 71² + 22² = 70² + 25² = 62² + 41² = 55² + 50²

The following additional results were established relatively quickly.

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 = y² + z² 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) £ [5^k-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(5².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⁴.13), giving Q(2,5) £ 90.

Q(2,6) : 2.k = 12 = 3.2.2 = (2+1).(1+1).(1+1) = d(5².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

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.

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³ + 167³ = 423³ + 228³ = 414³ + 255³

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

Additionally, the equation 19083³ + 2421³ = 18948³ + 5436³ = 18072³ + 10200³ = 16630³ + 13322³

implies that Q(3,4) £ 19083.

Note: For n = 4, Q(4,2) = 158 since 158⁴ + 59⁴ = 134⁴ + 133⁴ 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 = a^m + b^m

c = a-1

* 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 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 a² + b² = c² + d² and a² + b² = e² + f² 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² + b² = c² + d² = e² + f² 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: 7² + 1² = 5² + 5²

n = 3: 18² + 1² = 17² + 6² = 15² + 10²

n = 4: 33² + 4² = 32² + 9² = 31² + 12² = 24² + 23²

n = 6 and 5: 74² + 7² = 73² + 14² = 71² + 22² = 70² + 25² = 62² + 41² = 55² + 50²

n = 8 and 7: 165² + 20² = 164² + 27² = 160² + 45² = 155² + 60² = 144² + 83² = 141² + 88² = 132² + 101² = 120² + 115²

n = 9: 268² + 1² = 265² + 40² = 260² + 65² = 257² + 76² = 247² + 104² = 236² + 127² = 215² + 160² = 208² + 169² = 191² + 188²

n = 10: 371² + 22² = 370² + 35² = 365² + 70² = 355² + 110² = 350² + 125² = 334² + 163² = 317² + 194² = 310² + 205² = 301² + 218² = 275² + 250²

n = 12 and 11: 400² + 15² = 399² + 32² = 393² + 76² = 392² + 81² = 384² + 113² = 375² + 140² = 311² + 252² = 360² + 175² = 356² + 183² = 337² + 216² = 329² + 228² = 300² + 265²

n = 16, 15, 14, and 13: 895² + 10² = 890² + 95² = 886² + 127² = 881² + 158² = 874² + 193² = 865² + 230² = 862² + 241² = 830² + 335² = 815² + 370² = 785² + 430² = 769² + 458² = 766² + 463² = 722² + 529² = 710² + 545² = 703² + 554² = 655² + 610²

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