Metric conditions on configurations of points with only finitely many solutions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T18:57:23Z http://mathoverflow.net/feeds/question/92901 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/92901/metric-conditions-on-configurations-of-points-with-only-finitely-many-solutions Metric conditions on configurations of points with only finitely many solutions Timothy Chow 2012-04-02T15:23:23Z 2012-04-20T14:31:06Z <p>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.</p> <p>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.</p> <p><b>EDIT:</b> Peter Winkler's book <i>Mathematical Mind-Benders</i> provides the following information about the origin of the aforementioned puzzle: &#8216;[It] appeared as Problem 3a (submitted by S. J. Einhown and I. J. Schoenberg) in the &#8220;Puzzle Section&#8221; of the <i>Pi Mu Epsilon Journal</i> in 1985. Later it showed up on page 1 of Nob Yoshigahara's <i>Puzzles 101</i>, where it was attributed to Dick Hess.&#8217;</p> http://mathoverflow.net/questions/92901/metric-conditions-on-configurations-of-points-with-only-finitely-many-solutions/93200#93200 Answer by Roland Bacher for Metric conditions on configurations of points with only finitely many solutions Roland Bacher 2012-04-05T08:44:02Z 2012-04-05T08:44:02Z <p>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.</p>