11
$\begingroup$

There is an old puzzle, which I believe I learned from Nob Yoshigahara, that asks for all configurations of four (distinct) points in the plane such that the six pairwise distances assume only two distinct values. (In other words, there exist two distinct positive reals $a$ and $b$ such that the distance between any two of the four points is either $a$ or $b$.) Two configurations are considered equivalent if one can be obtained from the other by a dilation followed by a rigid motion. What makes this a good puzzle is that there are only finitely many solutions. MO readers may enjoy finding all solutions.

My question is, given $n$, $d$, and $k$, is there an efficient algorithm to determine whether there are only finitely many configurations of $n$ distinct points in $\mathbb{R}^d$ such that the $\binom{n}{2}$ distances between them assume only $k$ distinct values? Of course, I'm using the same notion of equivalence as stated above.

EDIT: Peter Winkler's book Mathematical Mind-Benders provides the following information about the origin of the aforementioned puzzle: ‘[It] appeared as Problem 3a (submitted by S. J. Einhown and I. J. Schoenberg) in the “Puzzle Section” of the Pi Mu Epsilon Journal in 1985. Later it showed up on page 1 of Nob Yoshigahara's Puzzles 101, where it was attributed to Dick Hess.’

$\endgroup$
1
  • 1
    $\begingroup$ There was a talk at the JMM just a couple of days ago, about finding all $12$- and $13$-point configurations in the plane with just six different distances. It seems that these problems can be quite hard. The general problem goes by the name, the Erdõs distance problem, and there's a book about it, see en.wikipedia.org/wiki/The_Erd%C5%91s_Distance_Problem $\endgroup$ Jan 7 at 19:51

1 Answer 1

3
$\begingroup$

Not an answer but a reformulation: Such a configuration gives rise to a set of $n$ points on a large $d$-dimensional sphere forming only $k$ different pairwise angles. Indeed, add a very large last coordinate $\rho$ and make a suitable perturbation (always possible since all non-zero determinants are roughly linear in $\rho$ and you need only a perturbation of order $1/\rho^2$). Considering the Gram matrix formed by scalar products of these $n$ points, we get a symmetric positive definite matrix $G$ of rank $d+1$ with coefficients in a set with $k$ elements. Subtracting $\lambda I_n$ from $G$ where $\lambda$ is the minimal eigenvalue of $G$, the problem is equivalent to the problem of determining all positive definite matrices of rank $\leq d$ with constant diagonal and off-diagonal coefficients in a finite set with $k$ elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.