12
\$\begingroup\$

In the plane (\$\mathbb R^2\$) we can have at most five distinct points such that the distances from each point to every other point (except itself) can assume at most two distinct values.

An example of such an arrangement is a regular pentagon - the two different distances are marked with red and blue:

Challenge

Given a number \$n = 1,2,3,\ldots\$ find the size \$s_n\$ of the largest 2-distance set in \$\mathbb R^n\$.

Definitions

  • We measure the Euclidean distance \$d(a, b) = \sqrt{\sum_{i=1}^n (a_i - b_i)^2}\$.
  • A set \$S \subseteq R^n\$ is a 2-distance set if the number of distinct distances \$| \{ d(a,b) \mid a,b \in S, a \neq b\}| = 2\$.

Details

Any output format defined in is allowed.

Examples

  n =  1, 2, 3,  4,  5,  6,  7,  8
s_n =  3, 5, 6, 10, 16, 27, 29, 45

This is OEIS A027627, and these are all the terms that we know so far. Answers to this challenge are expected to be able to find any term of this sequence - given enough ressources - not just the first eight.

\$\endgroup\$
  • 3
    \$\begingroup\$ Since the question is tagged code-golf, it's implicit that the scoring criterion is shortest code in bytes. \$\endgroup\$ – Brian Minton Dec 26 '19 at 20:32
  • \$\begingroup\$ @xnor Yes in theory without all the limitations the algorithms should find the value for any term. \$\endgroup\$ – flawr Dec 26 '19 at 22:02
  • \$\begingroup\$ This is an interesting problem, and it looks like the references in OEIS have enough info to be able to solve it. Unfortunately I have no time right now. \$\endgroup\$ – Level River St Dec 28 '19 at 22:38
  • \$\begingroup\$ i do not understand specially the case n=1 or R^1 why s_1 is 3? \$\endgroup\$ – RosLuP Dec 30 '19 at 21:24
  • 1
    \$\begingroup\$ @RosLuP Consider the points \$1,2,3\$, the only possible distances are 1 and 2. \$\endgroup\$ – flawr Dec 30 '19 at 22:29
5
\$\begingroup\$

Mathematica, 220 218 bytes

For[n=1,1>0,n++,For[m=1,1>0,m++,x=Array[a,{m,n}];d=Table[(Norm[x[[i]]-x[[j]]]^2-1)*(Norm[x[[i]]-x[[j]]]^2-y)==0,{i,1,m-1},{j,i+1,m}];If[Not[CylindricalDecomposition[Flatten@{d,y>0},Flatten@{y,x}]],Break[]]];Print[m-1]]

Try it online! Un-golfed version:

For[ n = 1, 1>0, n++,
  For[ m = 1, 1>0, m++,
   x = Array[a, {m, n}];
   d = Table[(Norm[x[[i]] - x[[j]]]^2 - 1)*(Norm[x[[i]] - x[[j]]]^2 - 
         y) == 0, {i, 1, m - 1}, {j, i + 1, m}];
   If[Not[
      CylindricalDecomposition[Flatten@{d, y > 0}, Flatten@{y, x}]],
      Break[]]
  ];
  Print[m - 1]
]

In this code, we apply a key tool from real algebraic geometry. A semialgebraic set is a subset of \$\mathbb{R}^d\$ defined by polynomial equalities and inequalities. We may identify the set of 2-distance subsets of \$\mathbb{R}^n\$ of cardinality \$m\$ with a semialgebraic subset of \$\mathbb{R}^{mn+2}\$. We force one of the distances to equal 1 without loss of generality, which means our semialgebraic set is a subset of \$\mathbb{R}^{mn+1}\$. We denote the other distance (squared) by \$y\$.

For which values \$Y\subseteq\mathbb{R}\$ of \$y\$ does there exists a size-\$m\$ subset of \$\mathbb{R}^n\$ with squared distances \$\{1,y\}\$? This can be answered with the help of Tarski--Seidenberg, which says that the projection of any semialgebraic set is semialgebraic. In our case, this means there is some univariate polynomial \$p\$ and relation \$*\in\{=,<,\leq\}\$ such that \$Y=\{y\in\mathbb{R}:p(y)*0\}\$. This projection may be accomplished using cylindrical algebraic decomposition (CAD), which enjoys an implementation in Mathematica.

Given a set of polynomial equalities and inequalities, as well as an ordered list of variables, Mathematica's implementation returns either an explicit description of every point in the corresponding semialgebraic set, or False if the set is empty. In the above code, we run CAD for increasingly larger values of \$m\$ until we get False, at which point we know that \$s_n=m-1\$. Sadly, the runtime of CAD is doubly exponential in the number of variables, and so we shouldn't expect this approach to determine \$s_9\$ any time soon. In fact, a minute of runtime only gives \$s_1=3\$.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I didn't expect an answer so soon:) Thanks for all the links, I never heard about semialgebraic sets. Did you try to verify \$s_2\$ or \$s_3\$, if so, how long did it take? \$\endgroup\$ – flawr Dec 30 '19 at 22:35
  • \$\begingroup\$ (And how can you specify the input to the program? Or does it iterate over all \$n\$?) \$\endgroup\$ – flawr Dec 30 '19 at 22:43
  • \$\begingroup\$ @flawr - It's currently running for \$s_2\$. The code just iterates over all \$n\$. \$\endgroup\$ – Dustin G. Mixon Dec 30 '19 at 23:13
  • \$\begingroup\$ Both True can be 1>0 to save 2 bytes. \$\endgroup\$ – Kevin Cruijssen Jan 3 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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