7 Clusters

During the summer of 2006 I found three 7-clusters, one of which is pictured here.

7-clusters come from problem D20 in Unsolved Problems in Number Theory. Find N points in a plane such that each pair of points is a rational distance apart, no 3 points are co-linear, and no 4 points are con-circular.

6-clusters were found in about July 1989. I worked with Landon Noll at Amdahl on a 7-cluster search. Landon was able to convince management that a 7-cluster search would be a good test of the hardware and operating systems. (This was on an IBM-360 compatible machine. Ya gotta love the days of big iron. We had 256MB of static ram.)

Anyway, we filled up memory with a table of points an integer distance away from the origin and used sophisticated algorithms to rapidly search the tables. Unfortunately, our general architecture wasn't very sophisticated, so we were doing a really good job of quickly executing an inherently slow algorithm. Still, we ended up with a reasonably large collection of 6-clusters.

In 2006, I revisited the problem. This time, I had at my disposal 'calc' which is a programming language that performs arbitrary precision arithmetic. In our cluster algorithms, we were frequently working with numbers that are about the distance between two points raised to a 4th power. This time around, we also used a number of new (to us) mathematical techniques.

In 1989 we thought we were working with pythagorean triangles, and we essentially optimized finding points that were an integer distance away from two other points. This time around we realized we were working with Heron triangles.

The first time around, when we picked up a triangle to work with and examine, we held the size of the triangle fixed and found other triangles that would attach to it. This time around when we picked a triangle, we held the ratio of sides fixed, but allowed the triangle to dilate. This allowed us to attach any two triangles together.

When testing the new algorithm, we extracted all the triangles which were used when forming 6-clusters. We then worked with this small set of triangles to look for 7-clusters and found 3. We did a more extensive search for 7-clusters. Running on a single processor (2005/2006 era x86 chip) over the course of about 100 days (if memory serves), we processed about 700 billion pairs of triangles. We found about 300 million 4-clusters. But, at the end of the day, we still had only 3 7-clusters.

The algorithm we used here is still quite inefficient. For each pair of triangles, we place them base to base and then test to see if the two points not on the base are an integer distance apart. The off-axis points are almost never (0.04%) an integer distance apart, and we move on to the next pair. In the rare cases where the points are an integer distance apart, we run through some co-linearity tests and a circularity test which throws out most of the pairs.

Heron triangles are fairly cool and have well developed math underlying them. We eventually learned (by reading more of the existing literature) that Heron triangles have Heron angles. You can't just take any angle and find a Heron triangle having that angle. Heron triangles do not contain angles of 60 degrees nor 45 degrees. Heron angles form a group: -- they are closed under addition -- you can add two heron angles together and get another heron angle.

And all this leads to a technique for generating 4-clusters instead of searching for 4-clusters. Pick a heron angle and a triangle having that heron angle. Pick a triangle containing the complementary angle. (If the chosen angle is X, then the complementary angle is 180-X.) You can take these two triangles and glue them together so that they form a 3rd heron triangle with one edge on the X-axis, and the line from the off-axis points meets the X-axis at the chosen angle. If you take a second triangle constructed in the same fashion and using the same angle of construction, and rotate it so it's off axis point is below the x-axis, then by construction you have a pair of off-axis points that are an integer distance apart.

We still have to run a search using this new technique that makes a key part of the algorithm 1,000 times faster and should make the overall algorithm nearly10 times faster.

The interesting progression here is that in 1989 we were generating 2-clusters. I optimized the code at that point to generate pythagorean triangles. In 2006, I figured out how to generate heron triangles (by gluing together pairs of pythagorean triangles). I now know how to generate heron-4-gons.

Generating a heron-5-gon that pases the con-circularity test is now strongly desirable. Without that, we are still stuck with searching through pairs of 4-gons to see if they form a 5-gon, and we can now generate very large numbers of 4-gons very quickly.