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.
Hello!
Could you give more explanations on the second table? For instance, could you give an example on one of the calculations?
Sure. Let’s take the first line of the table, that’s for BAX. The first column corresponds to dimensions 1 and 2, which are the leftmost of the three diagrams. The A->B vector has length zero, so that dot product will be zero. The next column is from the middle diagram. In that one A->B has length exactly 2*e5 and B->X has a shorter length but somewhere in the general neighborhood of e5, and the angle will be acute because it’s two opposite points on a circle to another point on the circle, so the dot product there is listed as +e5, meaning it will be a positive value whose smallest epsilon coefficient is e5, so it will be smaller than anything whose smallest coefficient was e4 or e3 or anything else, but would be bigger than anything which was e6 if there was an e6. For dimension 5, which is the third diagram, if X is at x1 then the length of A->X is zero and if X is at x2 then the dot product will be in the neighborhood of of e4 (in fact it will be exactly 4*e4^2, but I’m being pessimistic and listing it as zero. Since for that row the largest value is e5 and it’s positive, that case must be acute.