####################################################################
# README file for kub
# 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-25
####################################################################

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.

          Compilation with the WITH_PREFETCH option (set in
          settings_hash.h) is limited to modrn x86 processors.


COMPILATION (Version 1.0, August 2006):

To compile kub on a 64-bit LINUX/UNIX system, from the
Hashing package you need the three files below.

   hashing.c
   hashing.h    settings_hash.h

You might have to edit settings_hash.h. If you have less than 2GB
RAM then the HASH_BREITE needs to be reduced.

Further, the following eight files are necessary.

   arith.c    kub.c         post_proc_kub.c    ger.c
   arith.h    settings.h    post_proc_kub.h    sporadic_lines.h

You might want to edit settings.h.

When all the above files are copied into in the current directory,
the simple command line

        gcc -O2 hashing.c arith.c kub.c post_proc_kub.c ger.c -o kub

should compile kub.

Instead, you might prefer to use the Makefile provided. The command

        make kub

will compile kub, as well.

For this, it is important that each of the files is located at its
proper place. Depending on your system, you might have to edit the
Makefile before compilation.

We decided to provide a makefile for your comfort although kub is
a very small project which does not actually require a makefile.


INSTALLATION

To run kub, only the executable file kub is necessary. Move it to a
directory which is in the PATH variable.

Be aware that kub needs to be recompiled when settings.h is changed.


PURPOSE

We consider the Diophantine equation
     a*x**3 - b*y**3 = z**3 + v**3 + w**3    (a >= b > 0)        (*)
and search for small primitive solutions in non-negative integers.
(For symmetry reasons, it is sufficient to consider the
case a >= b.)

Up to now, a, b, x, y, z, v, and w are limited to 16 bits. 


Idea:
We hash all triples (z, v, w).
Then, we search for (x, y) in the table.

The hash function is
 (z, w)
  ---> "hash_breite leading bits of (z**3 + v**3 + w**3) mod 2**32".
The control value is (z**3 + v**3 + w**3 div 2**32) mod 2**15.


Extension: Line Detection

Search for lines on the cubic threefolds V_{a,b} defined by (*).

We count how many of the points found are contained in the obvious
lines. Here, obvious means that already two of the five summands have
a vanishing sum, e.g. v**3 + w**3 = 0.
   These obvious lines are known (over C) to form
3 * (5 over 2) = 30 cones over elliptic curves. This means, V
contains thirty singular models of ruled surfaces over elliptic
curves. Ten of the 30 cones are defined over R.
   Further, for each point found, we call the functions from
ger.c. Those test whether the point is contained in one of the
6*7 = 42 known non-obvious "sporadic" lines. These points are
counted, too.
   Finally, the code in ger.c causes the output of all points which
are "suspicious" to be contained in another, unknown, line
on V_{a,b}. This latter part of the project is a bit more technical.
Details are explained in ger.doc.


Estimated total running time for SUCHWEITE 5000 and
A_LIMIT = B_LIMIT = 100 on a Sun V20z with an Opteron 248 and
4GB RAM: 7--8 days.


TO RUN kub on the pages from low to high type
      kub low high
on the command line. All solutions within the given limit will be
found for low = 0 and high = page_prime - 1.


PUSHING THE LIMITS FOR THE VARIABLES

Is it possible to modify the kub code in order to push the limits
for the variables a, b, x, y, z, v, and w beyond 16 bits?

The answer to this question is, of course, yes.

For that, the structs nebentabellen_eintrag (variablen_links) and
variablen_rechts have to be redefined with longer integer types.
This will lead to more memory usage and might slow down the
buffering process done by the Hashing package.

Further, in post_proc one possibly needs to deal with overflow
problems.


REFERENCES

A more detailed description of the kub project may be found in the
paper

A.-S. Elsenhans and J. Jahnel: The Asymptotics of Points of Bounded
Height on Diagonal Cubic and Quartic Threefolds, Algorithmic number
theory, Lecture Notes in Computer Science 4076, Springer, Berlin
2006, 317--332