May 4, 2007

Integral Heptagons

It isn't hard to find three points such that the distance between each pair of points is an integer. Three points defining a right triangle with sides 3, 4, and 5 represent one such example. Triangles characterized by Pythagorean triples and many other triangles exhibit such integral relationships.

It's not so clear that there are sets of four points in which the distance between each pair is an integer, but there are. It's even less clear for five, six, seven, or more points.

The problem of finding sets of points with all mutual distances integers has intrigued many mathematicians, including Abram Besicovitch (1891–1970) and Paul Erdős (1913–1996). Erdős originally asked for five points in the plane, no three on a line, no four on a circle with the distance between each pair of points an integer.

When that problem was solved, six points became the target. There proved to be infinite families of such point sets.

Now, the seven-point case has been solved. Using an exhaustive computer search, Tobias Kreisel and Sascha Kurz of the University of Bayreuth found a integral heptagon, in which no three points lie on a line and no four points lie on a circle. In fact, they came up with two examples.

The following table gives the distances between the pairs of points in the smallest possible integral heptagon. For a diagram of this heptagon, see Ed Pegg's current Math Games column.

In each case, you can also look the smallest possible diameter, d, where the diameter is the largest occurring distance in a point set. For four points, d = 8; for five points, d = 73, and for six points, d = 174. The new results show that, for seven points, d = 22,270.

The new target? Are there eight points in the plane, no three on a line, no four on a circle with pairwise integral distances?

References:

Brass, P., W. Moser, and J. Pach. 2005. Research Problems in Discrete Geometry. New York: Springer.

Guy, R.K. 1994. Unsolved Problems in Number Theory, 2nd. ed. New York: Springer.

Kreisel, T., and S. Kurz. Preprint. There are integral heptagons, no three points on a line, no four on a circle.