An interesting math question is: for a given number of dimensions, how many different points can be placed in that many dimensions such that the angle formed by every triplet of them is acute? This paper shows a dramatic new result which makes an explicit construction of (2^{1/2})^{d} which is about 1.41^{d}. I’ve managed to improve this to (6^{1/5})^{d}, which is about 1.43^{d}.
Those of you not familiar with it already should read about dot products before proceeding. The important points for this result are: If the dot product is positive the angle is acute. The dot product across multiple dimensions is the sum of the products for each of the dimensions individually, and if one of the vector lengths in a dot product is very small then the dot product is very small as well.
My result is based on a recurrence which adds five dimensions and multiplies the number of points by six. It’s done like so:
Some explanation for this diagram is in order. The points a, b, c, p, q, and r all correspond to the same old point. The leftmost picture is the first and second new dimensions, the middle one the third and fourth, and the right one the fifth. The value ε_{1} is very small compared to all values which previously appeared and all normal functions on them. The value ε_{2} is very small compared to ε_{1} and this continues to ε_{5}. (Just pretend I drew those as epsilons instead of es. My diagramming skills are limited.)
A more numeric way of defining the values for the new dimensions is as follows:
point | 1 | 2 | 3 | 4 | 5 |
a | cos(θ_{1}) * ε_{1} | sin(θ_{1}) * ε_{1} | cos(θ_{3}) * ε_{5} | sin(θ_{3}) * ε_{5} | ε_{4} |
b | cos(θ_{1}) * ε_{1} | sin(θ_{1}) * ε_{1} | -cos(θ_{3}) * ε_{5} | -sin(θ_{3}) * ε_{5} | -ε_{4} |
c | cos(θ_{1}) * ε_{1} * (1-ε_{3}) | sin(θ_{1}) * ε_{1} * (1-ε_{3}) | cos(θ_{2}) * ε_{2} | sin(θ_{2}) * ε_{2} | 0 |
p | -cos(θ_{1}) * ε_{1} | -sin(θ_{1}) * ε_{1} | cos(θ_{5}) * ε_{5} | sin(θ_{5}) * ε_{5} | ε_{4} |
q | -cos(θ_{1}) * ε_{1} | -sin(θ_{1}) * ε_{1} | -cos(θ_{5}) * ε_{5} | -sin(θ_{5}) * ε_{5} | -ε_{4} |
r | -cos(θ_{1}) * ε_{1} * (1-ε_{3}) | -sin(θ_{1}) * ε_{1} * (1-ε_{3}) | cos(θ_{4}) * ε_{2} | sin(θ_{4}) * ε_{2} | 0 |
Those thetas are all angles. Their exact values don’t matter much, but they need to not be too close to each other compared to ε. Also θ_{2} and θ_{4} need to be between 0 and π/2 and not too close to the ends of that range.
Each triplet of points either all correspond to different old points, or two correspond to the same old point and another one to a second, or all three correspond to the same old point. In the case where all three correspond to different old points, their angle will be acute because the positions have only gotten changed by epsilon. The other cases can be straightforwardly enumerated. Because there are only two types of points there are only two cases for the singular external point to consider, labelled x and y in the diagram above. Because the last value of x can be positive or negative there are two positions labelled for it.
To check if each angle is acute, the dot product is calculated and checked to see if it’s positive. Rather than calculate these values exactly, it’s sufficient to check what the smallest epsilon each value is multiplied by and whether it’s positive or possibly negative. If the sum of the different dimensions is a positive larger epsilon (that is, one with a smaller subscript) then the dot product is positive and the angle is acute. Because many of the cases are very similar they can be consolidated down, so multiple endpoints are listed in some of the cases of the chart of all cases below. In cases where a value in one set of dimensions overwhelms all values which come after it, those values are skipped.
vertex | end point | end point | 1 & 2 | 3 & 4 | 5 |
a | b | x | 0 | ε_{5} | 0 |
a | b | y | 0 | -ε_{5} | ε_{4} |
a | c | x | ε_{3} | -ε_{5} | |
a | c | y | ε_{3} | ε_{2} | |
a | pqr | xy | ε_{1} | ||
c | ab | x | -ε_{3} | ε_{2} | |
c | ab | y | -ε_{3} | ε_{2} | |
c | pqr | xy | ε_{1} | ||
a | b | cr | 0 | -ε_{5} | ε_{4} |
a | b | pq | 0 | ε_{5} | 0 |
a | c | pq | ε_{3} | -ε_{5} | |
a | pqr | pqr | ε_{1} | ||
c | abpq | bpq | -ε_{3} | -ε_{2} | |
c | abpq | r | -ε_{3} | -ε_{2} |
Note that the extra restrictions on θ_{2} and θ_{4} are important in the CAY case (where A is the vertex).
In case you’re wondering how I came up with this: I can’t visualize in five dimensions any better than you can, but I’m pretty good at visualizing in three, so I worked out a 3 dimensions to 3 points recurrence which almost works. That’s dimensions three through five here. I put one of the recurrences from the previous work for dimensions one and two and moved the c and r points ‘down’ in the first two dimensions to fix the case which was broken, specifically CAX.
I’m quite certain this result can be improved on, although it’s hard for my poor little human brain to work out the more complicated cases. My guess is that it trends towards the absolute maximum of the n^{th} root of n, which is at e (that’s the root of the natural log, not a miswritten epsilon). I conjecture that this is tight, so no matter how small ε is, (e^{1/e} – ε)^{d} < acute(d) < (e^{1/e} + ε)^{d} for sufficiently large d.