MATHEMATICS OF COMPUTATION Volume 75, Number 254, Pages 935–940 S 0025-5718(05)01805-3 Article electronically published on December 19, 2005

THE DIOPHANTINE EQUATION x^{4} + 2y^{4} = z^{4} + 4w^{4}

ANDREAS-STEPHAN ELSENHANS AND JÖRG JAHNEL

Abstract. We show that, within the hypercube |x|, |y|, |z|, |w| ≤ 2.5·10^{6}, the Diophantine equation x^{4} +2y^{4} = z^{4} +4w^{4} admits essentially one and only one nontrivial solution, namely (±1 484 801, ±1 203 120, ±1 169 407, ±1 157 520). The investigation is based on a systematic search by computer.

1. Introduction

1.1. An algebraic curve C of genus g > 1 admits at most a finite number of ℚ-rational points. On the other hand, for genus one curves, #C(ℚ) may be zero, finite nonzero, or infinite. For genus zero curves, one automatically has #C(ℚ) = ∞ as soon as C(ℚ) ≠ ∅.

1.2. In higher dimensions, there is a conjecture, due to S. Lang, stating that if X is a variety of general type over a number field, then all but finitely many of its rational points are contained in the union of closed subvarieties which are not of general type. On the other hand, abelian varieties (as well as, e.g., elliptic and bielliptic surfaces) behave like genus one curves, i.e., #X(ℚ) may be zero, finite nonzero, or infinite. Finally, rational and ruled varieties comport in the same way as curves of genus zero in this respect.

This list does not yet exhaust the classification of algebraic surfaces, to say nothing of dimension three or higher. In particular, the following problem is still open.

Problem 1.3. Does there exist a K3 surface S over ℚ which has a finite nonzero number of ℚ-rational points, i.e., such that 0 < #S(ℚ) < ∞?

Remark 1.4. This question was posed by Sir P. Swinnerton-Dyer as Problem/ Question 6.a) in the problem session to the workshop [PT]. We are not able to give an answer to it.

\begin{matrix}c \\ ◯ \end{matrix}2005 American Mathematical Society

Reverts to public domain 28 years from publication

Received by the editor January 25, 2005.

2000 Mathematics Subject Classification. Primary 11Y50; Secondary 14G05, 14J28.

Key words and phrases. K3 surface, diagonal quartic surface, rational point, Diophantine equation, computer solution, hashing.

The first author was partially supported by a Doctoral Fellowship of the Deutsche Forschungsgemeinschaft (DFG).

The computer part of this work was executed on the Linux PCs of the Gauß Laboratory for Scientific Computing at the Göttingen Mathematisches Institut. Both authors are grateful to Professor Y. Tschinkel for the permission to use these machines as well as to the system administrators for their support.

1.5. One possible candidate for a K3 surface with the property 0 < #S(ℚ) < ∞ is given by the following

Problem. Find a third point on the projective surface S ⊂ P^{3} defined by

x^{4} + 2y^{4} = z^{4} + 4w^{4}.

Remarks 1.6. i) Problem 1.5 is also due to Sir P. Swinnerton-Dyer [PT, Problem/ Question 6.c)]. It was raised, in particular, during his talk [S-D, at the very end of the article] at the Göttingen Mathematisches Institut on June 2, 2004.

ii) x^{4} + 2y^{4} = z^{4} + 4w^{4} is a homogeneous quartic equation. It, therefore, defines a K3 surface S in P^{3}. As trivial solutions of the equation, we consider those corresponding to the ℚ-rational points (1:0:1:0) and (1:0:−1:0).

iii) Our main result is the following theorem which contains an answer to Problem 1.5.

Theorem 1.7. The diagonal quartic surface S in P^{3} defined by

(∗)  x^{4} + 2y^{4} = z^{4} + 4w^{4}

admits precisely ten ℚ-rational points which allow integral coordinates within the hypercube |x|, |y|, |z|, |w| < 2.5 · 10^{6}. These are (±1 : 0 : ±1 : 0) and (±1 484 801 : ±1 203 120:±1 169 407:±1 157 520).

Remark 1.8. This result clearly does not exclude the possibility that #S(ℚ) is actually finite. It might indicate, however, that a proof for that property is deeper than one originally hoped for.

2. Congruences

2.1. It seems natural to first try to understand the congruences

(+)  x^{4} + 2y^{4} ≡ z^{4} + 4w^{4} (mod p)

modulo a prime number p. For p = 2 and 5, one finds that all primitive solutions in ℤ satisfy

a) x and z are odd,

b) y and w are even,

c) y is divisible by 5.

For other primes, it follows from the Weil conjectures, proven by P. Deligne [De], that the number of solutions to the congruence (+) is

#C_{S}(𝔽_{p}) = 1 + (p − 1)(p^{2} + p + 1 + E) = p^{3} + E(p − 1),

where E is an error-term which may be estimated by |E| ≤ 21p.

Indeed, consider the projective variety S over ℚ defined by (∗). It has good reduction at every prime p ≠ 2. Therefore, [De, Théorème (8.1)] may be applied to the reduction S_{p}. This yields #S_{p}(𝔽_{p}) = p^{2} + p + 1 + E and |E| ≤ 21p. We note that dim H^{2}(𝒮, ℝ) = 22 for every complex surface 𝒮 of type K3 [Bv, p. 98].

2.2. Another question of interest is to count the numbers of solutions to the congruences x^{4} + 2y^{4} ≡ c (mod p) and z^{4} + 4w^{4} ≡ c (mod p) for a certain c ∈ ℤ.

This means to count the 𝔽_{p}-rational points on the affine plane curves C_{c}^{l} and C_{c}^{r} defined over 𝔽_{p} by x^{4} + 2y^{4} = \overline{c} and z^{4} + 4w^{4} = \overline{c}, respectively. If p ∤ c and p ≠ 2, then these are smooth curves of genus three.

THE DIOPHANTINE EQUATION x^{4} + 2y^{4} = z^{4} + 4w^{4} 937

By the work of André Weil [We, Corollaire 3 du Théorème 13], the numbers of 𝔽_{p}-rational points on their projectivizations are given by

#\overline{C}_{c}^{l}(𝔽_{p}) = p + 1 + E_{l}  and  #\overline{C}_{c}^{r}(𝔽_{p}) = p + 1 + E_{r},

where the error-terms can be bounded by |E_{l}|, |E_{r}| ≤ 6\sqrt{p}. There may be up to four 𝔽_{p}-rational points on the infinite line. For our purposes, it suffices to note that both congruences admit a number of solutions which is close to p.

The case p|c, p ≠ 2, is slightly different, since it corresponds to the case of a reducible curve. The congruence x^{4} + ky^{4} ≡ 0 (mod p) admits only the trivial solution if (−k) is not a biquadratic residue modulo p. Otherwise, it has exactly 1 + (p − 1) gcd(p − 1, 4) solutions.

Finally, if p = 2, then #C_{0}^{l}(𝔽_{2}) = #C_{1}^{l}(𝔽_{2}) = #C_{0}^{r}(𝔽_{2}) = #C_{1}^{r}(𝔽_{2}) = 2.

Remark 2.3. The number of solutions to the congruence (+) is

#C_{S}(𝔽_{p}) = ∑_{c∈𝔽_{p}} #C_{c}^{l}(𝔽_{p}) · #C_{c}^{r}(𝔽_{p}).

Hence, the formulas just mentioned yield an elementary estimate for that count. They show once more that the dominating term is p^{3}. The estimate for the error is, however, less sharp than the one obtained via the more sophisticated methods in 2.1.

3. Naive methods

3.1. The most naive method to search for solutions of (∗) is probably the following: Start with the set

{(x, y, z, w) ∈ ℤ | 0 ≤ x, y, z, w ≤ N},

and test the equation for every quadruple.

Obviously this method requires about N^{4} steps. It can be accelerated using the congruence conditions for primitive solutions noted above.

3.2. A somewhat better method is to start with the set

{x^{4} + 2y^{4} − 4w^{4} | x, y, w ∈ ℤ, 0 ≤ x, y, w ≤ N}

and to search for fourth powers. This set has about N^{3} elements, and the algorithm takes about N^{3} steps. Again, it can be sped up by the above congruence conditions for primitive solutions. We used this approach for a trial run with N = 10^{4}.

An interesting aspect of this algorithm is the optimization by further congruences. Suppose x and y are fixed. Then about one-half or three-quarter of the values for w are not solutions to the congruence modulo a new prime. Following in this way, one can find more congruences for w and the size of the set may be reduced by a constant factor.

4. Our final algorithm

4.1. The basic idea.

4.1.1. We need to compute the intersection of two sets

{x^{4} + 2y^{4} | x, y ∈ ℤ, 0 ≤ x, y ≤ N} ∩ {z^{4} + 4w^{4} | z, w ∈ ℤ, 0 ≤ z, w ≤ N} .

Both have about N^{2} elements.

It is a standard problem in Computer Science to find the intersection of two sets which both fit into memory. Using the congruence conditions modulo 2 and 5, one can reduce the size of the first set by a factor of 20 and the size of the second set by a factor of 4.

4.2. Some details.

4.2.1. The two sets described above are too big, at least for our computers and for interesting values of N. Therefore, we introduce a prime number p_{p} which we call the page prime.

We define the sets

L_{c} := {x^{4} + 2y^{4} | x, y ∈ ℤ, 0 ≤ x, y ≤ N, x^{4} + 2y^{4} ≡ c (mod p_{p})}

and

R_{c} := {z^{4} + 4w^{4} | z, w ∈ ℤ, 0 ≤ z, w ≤ N, z^{4} + 4w^{4} ≡ c (mod p_{p})}.

This means that the intersection problem is divided into p_{p} pieces and that the sets L_{c} and R_{c} fit into the computer’s memory if p_{p} is big enough. We worked with N = 2.5 · 10^{6} and chose p_{p} = 30 011.

For every value of c, our program computes L_{c} and stores this set in a hash table. Then, it determines the elements of R_{c} and looks them up in the table. Assuming uniform hashing, the expected running-time of this algorithm is O(N^{2}).

Remark 4.2.2. An important further aspect of this approach is that the problem may be attacked in parallel on several machines. The calculations for one particular value of c are independent of the analogous calculations for another one. Thus, it is possible, say, to let c run from 0 to (p_{p} − 1)/2 on one machine and, at the same time, from (p_{p} + 1)/2 to (p_{p} − 1) on another.

4.3. Some more details.

4.3.1. The page prime. For each value of c, it is necessary to find the solutions of the congruences x^{4} + 2y^{4} ≡ c (mod p_{p}) and z^{4} + 4w^{4} ≡ c (mod p_{p}) in an efficient manner. We do this in a rather naive way by letting y (w) run from 0 to p_{p} −1. For each value of y (w), we compute x^{4} (z^{4}). Then, we extract the fourth root modulo p_{p}.

Note that the page prime fulfills p_{p} ≡ 3 (mod 4). Hence, the fourth roots of unity modulo p are just ±1 and, therefore, a fourth root modulo p_{p}, if it exists, is unique up to sign. This makes the algorithm easier to implement.

Actually, we do not execute any modular powering operation or even computation of fourth roots in the lion’s share of the running time. For more efficiency, all fourth powers and all fourth roots modulo p_{p} are computed and stored in an array during an initialization step. Thus, the main speed limitation to find all solutions to a congruence modulo p_{p} is, in fact, the time it takes to look up values stored in the machine’s main memory.

4.3.2. Hashing. We do not compute L_{c} and R_{c} directly, because this would require the use of multiprecision integers within the inner loop. Instead, we choose two other primes, the hash prime p_{h} and the control prime p_{c}, which fit into the 32-bit registers of our computers. All computations are done modulo p_{h} and p_{c}.

More precisely, for each pair (x, y) considered, the expression ((x^{4}+2y^{4}) mod p_{h}) defines its position in the hash table. In other words, we hash pairs (x, y), whereas (x, y)↦((x^{4}+2y^{4}) mod p_{h}) plays the role of the hash function. For each pair (x, y), we write two entries into the hash table, namely the value of ((x^{4} +2y^{4}) mod p_{c}) and the value of y.

In the main computation, we worked with the numbers p_{h} = 25 000 009 for the hash prime and p_{c} = 400 000 009 for the control prime.

Note that, when working with a particular value of c, there are around p_{p} pairs ((x mod p_{p}), (y mod p_{p})) which fulfill the required congruence

x^{4} + 2y^{4} ≡ c (mod p_{p}).

Therefore, approximately

p_{p} · (\frac{N/2}{p_{p}} · \frac{N/10}{p_{p}}) = \frac{N^{2}}{20p_{p}}

values will be written into the table. For our choices,

\frac{N^{2}}{20p_{p}} ≈ 10 412 849,

which means that the hash table will become approximately 41.7% filled.

As for many other rules, there is an exception to this one. If c = 0, then approximately 1 + (p_{p} − 1) gcd(p_{p} − 1, 4) pairs ((x mod p_{p}), (y mod p_{p})) may satisfy the congruence

x^{4} + 2y^{4} ≡ 0 (mod p_{p}).

As p_{p} ≡ 3 (mod 4), this is not more than 2p_{p} − 1, and the hash table will be filled by not more than about 83.3%.

In order to resolve collisions within the hash table, we use an open addressing method. We are not particularly afraid of clustering and choose linear probing. We feel free to use open addressing as, thanks to the Weil conjectures, we have a priori estimates available for the load factor.

4.3.3. Miscellanea. The program makes frequent use of fourth powers modulo p_{h} and p_{c}. Again, we compute these data in the initialization part of our program and store them in arrays, once and for all.

Test versions of the program were written in Delphi. The final version was written in C. It took about 130 hours of CPU time on a 3.00 GHz Pentium 4 processor with 512 kByte cache memory. The main computation was executed in parallel on two machines during the very first days of December 2004.

4.4. Post-processing. Instead of looking for solutions of x^{4} + 2y^{4} = z^{4} + 4w^{4}, our algorithm searches, in fact, for solutions to the corresponding simultaneous congruences modulo p_{p} and p_{c} which, in addition, fulfill that ((x^{4} + 2y^{4}) mod p_{h}) and ((z^{4} + 4w^{4}) mod p_{h}) are “almost equal”.

To this modified problem, we found approximately 3800 solutions such that (y, w) ≠ (0, 0). These congruence solutions were checked by an exact computation using O. Forster’s [Fo] Pascal-style multi-precision interpreter language ARIBAS.

Among the congruence solutions, exact equality occurs only once. This solution is as follows.

==> 1484801**4 + 2 * 1203120**4.
-: 90509_10498_47564_80468_99201
==> 1169407**4 + 4 * 1157520**4.
-: 90509_10498_47564_80468_99201

References

[Bv] Beauville, A.: Complex algebraic surfaces, London Mathematical Society Lecture Note Series 68, Cambridge University Press, Cambridge 1983. MR0732439 (85a:14024)

[Be] Bernstein, D. J.: Enumerating solutions to p(a) + q(b) = r(c) + s(d), Math. Comp. 70 (2001) 389–394. MR1709145 (2001f:11203)

[CLR] Cormen, T., Leiserson, C., and Rivest, R.: Introduction to algorithms, MIT Press and McGraw-Hill, Cambridge and New York 1990. MR1066870 (91i:68001)

[De] Deligne, P.: La conjecture de Weil I, Publ. Math. IHES 43 (1974) 273–307. MR0340258 (49:5013)

[Fo] Forster, O.: Algorithmische Zahlentheorie, Vieweg, Braunschweig 1996.

[PT] Poonen, B. and Tschinkel, Y. (eds.): Arithmetic of higher-dimensional algebraic varieties, Proceedings of the Workshop on Rational and Integral Points of Higher-Dimensional Varieties held in Palo Alto, CA, December 11–20, 2002, Birkhäuser, Progress in Mathematics 226, Boston 2004. MR2028897 (2004h:11001)

[Se] Sedgewick, R.: Algorithms, Addison-Wesley, Reading 1983. MR0784432 (86k:68037)

[Sm] Smart, N. P.: The algorithmic resolution of Diophantine equations, London Mathematical Society Student Texts 41, Cambridge University Press, Cambridge 1998. MR1689189 (2000c:11208)

[S-D] Swinnerton-Dyer, Sir P.: Rational points on fibered surfaces, in: Tschinkel, Y. (ed.):

Mathematisches Institut, Seminars 2004, Universitätsverlag, Göttingen 2004, 103–109.

[We] Weil, A.: Sur les courbes algébriques et les variétés qui s’en déduisent, Actualités Sci. Ind. 1041, Hermann et Cie., Paris 1948. MR0027151 (10:262c)

Mathematisches Institut der Universität Göttingen, Bunsenstraße 3–5, D-37073 Göttingen, Germany

   E-mail address: elsenhan@wwwuser.gwdg.de

Mathematisches Institut der Universität Göttingen, Bunsenstraße 3–5, D-37073 Göttingen, Germany

   E-mail address: ~jjahnel@wwwuser.gwdg.de
   URL: http://wwwuser.gwdg.de/~jjahnel