Maximal 2-distance Sets

Question

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

Answer 1

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\$.