Metric conditions on configurations of points with only finitely many solutions

2012-04-02T15:23:23Z

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.’

Answer by Roland Bacher for Metric conditions on configurations of points with only finitely many solutions

2012-04-05T08:44:02Z

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.

Metric conditions on configurations of points with only finitely many solutions - MathOverflow

Metric conditions on configurations of points with only finitely many solutions

Answer by Roland Bacher for Metric conditions on configurations of points with only finitely many solutions