Solution to Problem #9

Bojan Basic of Novi Sad (Serbia), Philippe Fondanaiche of Paris (France), and Christian Bau made contributions to this problem. Here is Christian Bau's approach followed by Bojan Basic's remarks.

Solution: n = 3 is trivial (equilateral triangle); assume n >= 4. For d = 1, 2, 3 etc. 
we try to find n points at integer distances with no distance greater than d. Assume 
that point 1 is at (0, 0) and point 2 is at (0, d). All the other points must be at an 
integer distance from these two points. So for all integers a, b such that a + b > d 
and a <= d, b <= d, find the two points that are at a distance a from (0, 0) and at 
a distance b from (0, d). These points meet the two equations:

     x^2 + y^2 = a^2
     x^2 + (d - y)^2 = b^2

We find easily that y = (d^2 + a^2 - b^2) / 2d and x = +/- sqrt (a^2 - y^2). For 
fixed d, there are roughly (d^2 / 2) combinations of distances a and b to consider 
and roughly d^2 points at integer distances <= d away from the first two points. 
For n <= 10, we can easily do an exhaustive search to find all pairs of these points 
that are at an integer distance from each other, then all triples, sets of four 
points and so on. This search finds:

     d (4) = 4; p3 = (1.45237, 1.375), p4 = (-1.93649, 3.5)
     d (5) = d (6) = 8; p3, p4 = (2.59808, 4 +/- 2.5), p5, p6 = (-4.33013, 4 +/- 1.5)
     d (7) = 33, p3, p4 = (9.68246, 16.5 +/- 14), p5, p6 = (-13.5554, 16.5 +/- 8), 
                 p7 = (17.4284, 16.5)
     d (8) = d (9) = 56, p3, p4 = (-18.1865, 28 +/- 17.5), p5, p6 = (30.3109, 28 +/- 10.5), 
                         p7 = (15.8359, 2.28571), p8 = (-24.125, 30.6429), p9 = (20.4135, 51.0714)
     d (10) = 105, p3, p4 = (42.4352, 52.5 +/- 28), p5, p6 = (-48.4974, 52.5 +/- 24.5), 
                   p7 = (10.8872, 1.57143), p8 = (-36.7442, 13.0714), p9 = (49.4872, 42.1429), 
                   p10 = (-52.5801, 66.7857).

For larger n, the exhaustive search compares any of about d^2 points with any other of 
those points and checks whether the distance is an integer; this takes about d^4 operations, 
which is fine for n = 10, d(n) = 105, but doesn't work well for much larger values. The 
search can be made significantly faster: Instead of checking whether the distance of two 
points is an integer, we check for the necessary condition that the distance it is the 
square root of a rational number: For any (a, b), the point at distance a from (0, 0) 
and distance b from (0, d) is at (x, y), where y is a rational number and x is the square 
root of a rational number. If we take two points (x1 = sqrt (s1), y1) and (x2 = sqrt (s2), y2), 
then we need (x1 - x2)^2 to be rational, which is the case if 2 (x1 * x2) is rational or 
s1 * s2 is the square of a rational number.

Given a, b, we find x = +/- sqrt (4a^2 d^2 - (d^2 + a^2 - b^2)^2) / 2d. The quotient 2d 
is independent of a and b. Define f (a, b) = d^2 + a^2 - b^2, g (a, b) = 
(2ad)^2 - f (a, b)^2. The distance between the points for two different distances (a, b) 
is the square root of a rational number if and only if the product of the two values 
g (a, b) is a square. Define h (a, b) = g (a, b) divided by its largest square factor. 
Then the distance between two points is the square root of a rational number only if the 
two values h (a, b) are the same.

So here is a faster algorithm to find d (n):

Assume n >= 4. Iterate for d = 1, 2, 3 and so on until a solution is found. For each 
d: For a = 1 to d and for b = d - a + 1 to d calculate f (a, b) = d^2 + a^2 - b^2, 
g (a, b) = (2ad)^2 - f (a, b)^2, then h (a, b) = g (a, b) divided by its largest square 
factor. Sort by the value of h (a, b) and find all sets of pairs (a, b) where the value 
of h (a, b) is the same. For each of those sets perform an exhaustive search for sets 
of n-2 points at integer distances <= d. For each set found add the points (0, 0) and 
(0, d) and check that no three points in a set are on the same line. In that case a 
solution has been found.

Bojan Basic points out that the is a research problem that is still open. So far it is known that there exist constants c1 and c2 such that

c1n < d(n) < n c2log(log(n)))

by [1] and [2], respectively. Exact values of d(n) are known only for 1 ≤ n ≤ 9:

1, 1, 1, 4, 8, 8, 33, 56, 56

In an unpublished note [4] S. Kurz and A. Wassermann claim to have the exact values of d(n) determined up to n = 36:

105, 105, 105, 532, 532, 735, 735, 735, 735, 1995, 1995, 1995, 1995, 1995, 1995, 9555, 9555, 9555, 10672, 13975, 13975, 13975, 13975, 13975, 13975, 13975, 13975.

The picture below (reproduced from [2]) shows configurations for n = 3, 4, 6, 7, and 9

References

  1. J. Solymosi, Note on integral distances, Discrete Comput. Geom. 30 (2003), 337–342.
  2. H. Harborth, A. Kemnitz, and M. Möller, An upper bound for the minimum diameter of integral point sets, Discrete Comput. Geom. 9 (1993), 427–432.
  3. The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/~njas/sequences/A096872.
  4. S. Kurz and A. Wassermann, On the Minimum Diameter of Plane Integral Point Sets, http://arxiv.org/pdf/0804.1307.




Back to the Archives
Back to the Math Department Homepage.