##################################################################### # README file for swd # Authors: Andreas-Stephan Elsenhans and Joerg Jahnel # Email: elsenhan@uni-math.gwdg.de, jahnel@uni-math.gwdg.de # Web: http://www.gwdg.de/jahnel # Date: 2006-08-23 ##################################################################### BE ALERT: This code ASSUMES that a "long int" is a 64-bit integer. On 32-bit machines it is highly unlikely to run properly. BE WARNED: This code searches for solutions of Sir Peter Swinnerton-Dyer's Diophantine equation x**4 + 2 y**4 = z**4 + 4 w**4. It is an implementation of the hashing algorithm described in [1] and [2]. It contains, however, many optimizations for the particular case. (See the section on improvements, below, for details.) This implies, in particular, that the code is "monolithic". There is no strict separation into functions manipulating the hash table and functions generating the data. If you want to search for solutions of another Diophantine equation then it is probably a bad idea to use swd as a starting point. We suggest to use the Hashing package instead. COMPILATION (Version 1.0, August 2006): To compile swd on a 64-bit LINUX/UNIX system, it is important that GMP is installed on your system. This particular release was tested with GMP Version 4.1.3. Further, the following five files are needed. swd_case1.c swd_case2.c common.h settings.h gmp_headers.h . It is necessary to edit gmp_headers.h. swd needs to know the exact place where in your system the two include files gmp-impl.h and longlong.h from the GMP package are located. You might also want to edit settings.h. When all the above files (and no other .c-files) are copied into the current directory, the simple command lines gcc -O2 -lgmp swd_case1.c -o swd_case1 and gcc -O2 -lgmp swd_case2.c -o swd_case2 will compile the two cases of swd. You may also compile swd with the command make or make all . We decided to provide a makefile for your comfort although swd is a very small project which does not actually require a makefile. INSTALLATION To run swd, only the executable files swd_case1 and swd_case2 are necessary. Move them to a directory which is in the PATH variable. Be aware that swd_case1 and swd_case2 need to be recompiled when settings.h is changed. PURPOSE We consider the Diophantine equation x**4 + 2 y**4 = z**4 + 4 w**4 and search for small primitive solutions in non-negative integers. Small means that |x|, |y|, |z|, |w| < SUCHWEITE. We IGNORE the obvious solution (1:0:1:0). Without restriction, we assume w and y are even, x and z are odd. Further, one automatically has 5|y. There are two cases, 5|x or 5|w. Case 1: 5|w. Idea: Rewrite the equation as 2 y**4 - 4 w**4 = z**4 - x**4 . Because of 5|w and 5|y, we have 625|(z**4 - x**4). We hash all pairs (z,x) such that 5 \not| z, 5 \not| x, z and x both odd, z**4 = x**4 mod 625, (and x <> z). Then, we search (w,y) such that 10|w and 10|y in the table. The hash function is (z,x) --> "hash_breite leading bits of (z**4 - x**4) mod 2**32". The control value is (z**4 - x**4 mod 2**63) div 2**32. Case 2: 5|x. Idea: Because of 5|x and 5|y, we have 625|(z**4 + 4 w**4). We hash all pairs (z,w) such that 5 \not| z, 5 \not| w, z odd, w even, and z**4 = - 4 w**4 mod 625. Then, we search for (x,y) such that x = 5 mod 10 and 10|y in the table. The hash function is (z, w) ---> "hash_breite leading bits of (z**4 + 4 w**4) mod 2**32". The control value is (z**4 + 4 w**4 mod 2**63) div 2**32. IMPROVEMENTS incorporated: I. (Improvements concerning the hash machinery) i) Following an idea of Andreas-Stephan Elsenhans, the hash table is not built up and read in a chaotic manner. Instead, the right hand sides and the left hand sides are pre-sorted into several buffers. ii) In the hash table, we store control values, only. There is no analogue of the nebentabelle expected by the Hashing package. No direct information about the pair (z, x) (or (z, w)) is stored in the writing step. This saves about one half of the memory and reduces the running time considerably. However, the post_processing becomes significantly more complicated. If a coincidence is detected then (z, x) (respectively (z, w)) needs to be reconstructed. iii) For better fitting into cache memory, the buffers for reading contain nothing but the value on the left hand side. Again, this makes the post_processing more complicated. If a coincidence is detected then the build-up of the buffers needs to be simulated in order to reconstruct (y, w) (or (x, y)). II. (Congruence conditions) i) In Case 1, we always have 32 | (-4 w**4 + 2 y**4). However, 32 | (z**4 - x**4) ==> x = \pmz (mod 8). We write only if x = \pmz (mod 8). ii) (Case 1) As 3 | (-4 w**4 + 2 y**4) ==> 81 | (-4 w**4 + 2 y**4), we write only if 3 \not| (z**4 - x**4) or 81 | (z**4 - x**4). (Case 2) As 3 | (z**4 + 4 w**4) ==> 81 | (z**4 + 4 w**4), we read only if 3 \not| (x**4 + 2 y**4) or 81 | (x**4 + 2 y**4). TO RUN swd_casei on the pages from low to high type swd_casei low high on the command line. All solutions within the given limit will be found for a = low and high = page_prime - 1. Estimated total running time for search bound 100 million on a Sun V20z with an Opteron 248 and 4GB RAM: Approximately 56 days (Case 1), 50 days (Case 2). RESULT swd finds the following solution. ==> 1484801**4 + 2 * 1203120**4. -: 90509_10498_47564_80468_99201 ==> 1169407**4 + 4 * 1157520**4. -: 90509_10498_47564_80468_99201 Up to changes of sign and up to scalar multiples, this is the only non-obvious solution of Sir Peter Swinnerton-Dyer's Diophantine equation up to SUCHWEITE 10**8. It is also the only non-obvious solution known. REFERENCES A more detailed description of the swd project may be found in the two papers [1] A.-S. Elsenhans and J. Jahnel: The Diophantine Equation x**4 + 2 y**4 = z**4 + 4 w**4---An investigation by computer for |x|, |y|, |z|, |w| < 2.5 * 10**6, Math. Comp. 75(2006)935-940 and [2] A.-S. Elsenhans and J. Jahnel: The Diophantine Equation x**4 + 2 y**4 = z**4 + 4 w**4---A number of improvements, Preprint.