Maximum number of points attaining acute angles in $\mathbb{R}^n$

Question

In $\mathbb{R}^n$ consider three points $v_i$. Here at $v_2$ the angle $\angle v_1v_2v_3$ is acute if it is strictly smaller then $\frac{\pi}{2}$.

Note that in $\mathbb{R}^2$, one can find three points such that

all angles are acute.

For example, an equilateral triangle.

But there are no $4$ point satisfying such property.

Taking a regular tetrahedron in $\mathbb{R}^3$, we have $4$ points satisfying such a property.

Hence can we conclude that the maximum number of points in $\mathbb{R}^n$ with the above angle property is equal to or smaller than $n+1$?

Is this right ? Thank you in advance.

Answer 1

We will say that a set on $N$ points has the Acute Angle Configuration (AAC) if all the angles that can be formed with 3 points among them are acute;

First of all, here is a very readable reference that brings additional information to the reference given by @Théophile: Sets of points determining only acute angles and some related colouring problems by David Bevan:

oro.open.ac.uk/33661/1/Acute.pdf

with the very interesting arrays that can be found in page 9 and that I reproduce here:

On my side, I have written the following Matlab program that makes random searches in $\mathbb{R}^D$ for $N$ AAC points.

clear all;
N=5;D=3;
b=nchoosek(N,3);%total number of triangles
I=nchoosek(1:N,3);
G=0;
Ns=10000;
for k=1:Ns;
  P=rand(N,D);
  T=[];
  for p=1:b 
     J=I(p,:);
     A=P(J(1),:);B=P(J(2),:);C=P(J(3),:);%triangle
     U=A-B;V=B-C;W=C-A; % its vectorialized sides
     T=[T,-U*W',-U*V',-V*W']; % dot products of these vectors
  end;
  if all(T>0) 
     P
     G=G+1;
  end;
end;
G/Ns %percentage of hits (successes)

For example, finding 5 AAC points in $\mathbb{R^3}$ has necessitated a rather long execution time, meaning that such a configuration "at the limit" is exceptional:

$$\begin{array}{lll} (0.6842, \ \ & 0.2992, \ \ & 0.7554)\\ (0.2169, \ \ & 0.0480, \ \ & 0.2551)\\ (0.6766, \ \ & 0.1850, \ \ & 0.1968)\\ (0.2088, \ \ & 0.3158, \ \ & 0.7579)\\ (0.4731, \ \ & 0.8037, \ \ & 0.0771) \end{array}$$

To my own surprise, I have, with this program, found almost instantly a solution with $N=6$ and $D=5$ which is:

$$\begin{array}{lll} 0, & \ 0, & \ 1, & 0, & \ 0 \\ 1, & \ 1, & \ 0, & \ 0, & \ 1\\ 1, & \ 1, & \ 1, & \ 1, & \ 0\\ 1, & \ 0, & \ 0, & \ 1, & \ 1\\ 0, & \ 1, & \ 0, & \ 1, & \ 0 \\ 0, & \ 1, & \ 1, & \ 1, & \ 1 \end{array}$$

For example, for $\mathbb{R}^D=\mathbb{R}^{11}$, the Matlab program finds the following $N=12$ AAC points, proving that $\kappa(11) \geq 12$.

$$\begin{array}{rrrrrrrrrrr} (836, \ \ 807, \ \ 929, \ \ 118, \ \ 242, \ \ 354, \ \ 125,\ \ 178, \ \ 310, \ \ 631, \ \ 2)\\ (73, \ \ 687, \ \ 470, \ \ 40, \ \ 163, \ \ 466, \ \ 782, \ \ 788, \ \ 493, \ \ 314, \ \ 777) \\ (248, \ \ 279, \ \ 666, \ \ 485, \ \ 574, \ \ 477, \ \ 883, \ \ 663, \ \ 24, \ \ 270, \ \ 299) \\ (738, \ \ 742, \ \ 563, \ \ 869, \ \ 304, \ \ 786, \ \ 517, \ \ 855, \ \ 586, \ \ 871, \ \ 28) \\ (982, \ \ 823, \ \ 731, \ \ 297, \ \ 880, \ \ 936, \ \ 355, \ \ 672, \ \ 779, \ \ 796, \ \ 76) \\ (335, \ \ 395, \ \ 900, \ \ 148, \ \ 527, \ \ 240, \ \ 981, \ \ 727, \ \ 923, \ \ 97, \ \ 655) \\ (283, \ \ 663, \ \ 937, \ \ 309, \ \ 617, \ \ 812, \ \ 247, \ \ 478, \ \ 896, \ \ 729, \ \ 866) \\ (604, \ \ 466, \ \ 248, \ \ 349, \ \ 754, \ \ 834, \ \ 862, \ \ 937, \ \ 531, \ \ 75, \ \ 582) \\ (410, \ \ 750, \ \ 299, \ \ 145, \ \ 483, \ \ 147, \ \ 176, \ \ 890, \ \ 749, \ \ 584, \ \ 56) \\ (973, \ \ 155, \ \ 541, \ \ 567, \ \ 102, \ \ 452, \ \ 471, \ \ 327 , \ \ 458, \ \ 832, \ \ 406) \\ (807, \ \ 575, \ \ 745, \ \ 158, \ \ 719, \ \ 881, \ \ 489, \ \ 960, \ \ 7, \ \ 836, \ \ 583) \\ (348, \ \ 181, \ \ 22, \ \ 207, \ \ 540, \ \ 773, \ \ 193, \ \ 90, \ \ 856, \ \ 837, \ \ 441). \end{array}$$

Answer 2

I don't think it's reasonable to make such a conjecture based on two examples (and in fact there is a set of $5$ points in $\Bbb R^3$, so the tetrahedron is not a maximal example).

An article by Erdős and Füredi called The Greatest Angle Among $n$ Points in the $d$-Dimensional Euclidean Space shows that there is a set of at least $1.15^d$ points in $\Bbb R^d$ satisfying the given property.

Answer 3

An arxiv.org preprint by D. Zakharov proves that in $\mathbb{R}^n$ there is a set of at least $\sqrt{2}^{n+1.64}$ points, and a follow-up proves that there is a set of at least $\left(\frac{1+\sqrt 5}{2}\right)^n$ points.

Answer 4

There have been significant advances in this problem: math.stackexchange.com/questions/2363546/tight-acute-sets