11
$\begingroup$

Given a set of grid points arranged in an $n$ by $n$ square (in 2 dimensions):

How many distinct proper (acute or obtuse) angles can be formed having a vertex on one grid point and line segments ending on two other grid points?

For example, on a $2 \times 2$ grid you can form only $2$ distinct angles, with cosines equal to $0$ (for example $\angle (0,0)(0,1)(1,1)$) and $\frac{1}{\sqrt{2}}$.

(I find it convenient to classify the angles by their cosines, because the law of cosines lets you easily get the cosine of each angle of a triangle on the grid.)

On a $3 \times 3$ grid, by adding that layer of 5 more points, you can form an additional $8$ distinct angles, with $$\cos \alpha \in \{ \frac{1}{\sqrt{5}},\frac{2}{\sqrt{5}},\frac{3}{5},-\frac{1}{\sqrt{2}}, \frac{3}{\sqrt{10}}, \frac{1}{\sqrt{10}}, \frac{4}{5}, - \frac{1}{\sqrt{5}} \} $$ Here I have arranged these values in an order that came from the following reasoning: To make a new angle, you must make a triangle with two vertices more that $n-1$ apart in either the horizontal or the vertical direction (or both. So I start with one point at the upper left grid point, slide a second point along the opposite edge, and work my way through all combinations of on point on each of two opposite edges. For each such combination, the third point can in principle be on any of the remaining grid points.

A very crude upper limit can be estimated by saying there are $\binom{n^2}{3}$ possible triangles, thus $3 \binom{n^2}{3}\approx \frac{n^6}{2}$ angles; but of course most of those angles will duplicate each other.

By considering the ordering described above, one eliminates a number of angles that are just translations, flips, or $90^\circ$ rotations of others already counted. Here, the naive upper limit for the added angles would be $3$ for the angles in a triangle, times $\binom{n+1}{2}$ for the ways to choose the two edge vertices, divided by $2$ to account for flips about the horizontal center of the square, times $(n^2-2)$ internal points. That gives a naive upper limit of about $\frac{3n^4}{4}$ points added when the square side increases from $n-1$ to $n$, thus a naive upper limit of $$ \Bbb{A}(n) \leq \frac{3n^5}{20} $$ But that is also much too large. Some triangles are duplicates because of:

  • Much of the time, one or two of the angles in a new large triangle overlays an angle that can fit in a smaller grid.
  • Any time the third vertex of the triangle lies below the first vertex, the whole triangle can be translated upward such that the first vertex lies on a corner.
  • Symmetry that we have not yet discounted for (for example, some triangles are isosceles [although noe will be equilateral]).
  • A side of a triangle passes through a grid point, allowing an angle to have been created on a smaller grid even though the triangle at hand is large. The counting of these cases involves the totient function.
  • A triangle is similar to some other smaller triangle in some obvious way involving $45^\circ$ rotations.
  • When a side that is neither horizontal nor vertical happens to have integer length due to Pythagorean relationships, angles involving that side are usually duplicated in other triangles with a horizontal or vertical side of that length.
  • There are some numerical "coincidences" that cannot be anticipated by accounting for those other effects. This is fundamentally a number theory problem.

Although I originally suspected that the number of distinct angles grows like $n^4$, I have not been able to show this, nor get a handle on what the coefficient would be. I do know that for modest values of $n$, the growth appears to be much slower than this, perhaps as slow as $n^3$.

$\Bbb{A}(4)$ Appears to be $2 + 8 + 18 = 28$. I'm pretty sure that pattern breaks down by $\Bbb{A}(5)$.

Any progress or solution on this would be appreciated.

Added after a few days:

I have tightened the upper limit: Since any triangle touching the right and left sides can be translated and possibly flipped so that it has one vertex on the upper left corner and one on the right side, and since among those triangles the ones with the third vertex above the line joining the sides replicate triangles with the third vertex below that line, the upper limit, ignoring symmetries, coincidences, and so forth, is just $\frac{3n^2}{16}$ new angles for layer $n$. Thus $$ \Bbb{A}(n) \leq \frac{3n^4}{16} $$

I did an automated computation of $\Bbb{A}(n)$ for $n \leq 100$ and observe that $$ \Bbb{A}(n) \leq \frac{n^4}{8} $$ and that it appears to approach that limit.

The numbers in the sequence for $n = 2$ through $10$ are $$ \begin{array}{ll} 2 & 2 \\ 3 & 10 \\ 4 & 28 \\ 5 & 66 \\ 6 & 154 \\ 7 & 269 \\ 8 & 473 \\ 9 & 781 \\ 10 & 1156 \end{array} $$ I want to submit this as a new sequence in OEIS, but I won't until somebody else has confirmed my results by their own calculation, at least for ten more values of $n$. To be confident that this is a confirmation, I am not displaying the number of angles for all further values of $n$, but I will say that $\Bbb{A}(21) = 23640$, $\Bbb{A}(50) = 759308$, and $\Bbb{A}(100) = 12335703$,.

To increase the chances of somebody providing the verification I need,,

I am offering a bounty for even the values of $\Bbb{A}(n)$ from $10 < n < 21$.

Agreement in those ten numbers will tell me that my program was correct, and I will submit this to the Online Encyclopaedia of Integer Sequences.

Of course, any substantial theoretical work toward an actual understanding of the sequece would also earn the bounty!

$\endgroup$
1
+50
$\begingroup$

Below are the values I obtain. (I include all possible values of $\cos$ including $1$ and $-1$). Hence, to compare with yours subtract $2$ from $N$ except for the first one where you just subtract $1$. And add my name when you add to OEIS.

\begin{array} C n & N\\ 2 & 3\\ 3 & 12\\ 4 & 30\\ 5 & 68\\ 6 & 156\\ 7 & 271\\ 8 & 475\\ 9 & 783\\ 10 & 1158\\ 11 & 1691\\ 12 & 2539\\ 13 & 3232\\ 14 & 4637\\ 15 & 6014\\ 16 & 7641\\ 17 & 9757\\ 18 & 12878\\ 19 & 15297\\ 20 & 19535\\ 21 & 23642\\ 22 & 27937\\ 23 & 32994\\ \end{array}

$\endgroup$
  • 1
    $\begingroup$ Perhaps someone may have found "And add my name when you add to OEIS." crude or would expect this answer to be a comment. $\endgroup$ – punctured dusk Nov 25 '14 at 7:50
  • $\begingroup$ Well, I am not the one who down-voted it. And now that I think of it, crediting the validation is the right thing to do if OEIS has a slot for that credit. However, there is an off-by-3 error on the last one: My answer is 32995, not 32992. Did your program compute float values for equality, in which case you might have created some roundoff issues causing some identical angles to look different? $\endgroup$ – Mark Fischler Nov 25 '14 at 16:23
  • $\begingroup$ Yes, by storing the cosines as a std::set of doubles (64-bit floats), I was able to observe a discrepancy of 3 angles at $n=23$, and indeed a discrepancy of a total of 42 angles going up to $n=30$. I will see if I can verify that two different square roots are equal to 16 decimal places, to verify this was the cause of the different answer you gave for $n=23$. $\endgroup$ – Mark Fischler Nov 25 '14 at 17:27
  • $\begingroup$ Well, it turns out that the error was on my part: In inserting a fraction representing $cos^2 \theta$ into s std::set of such fractions, I specified a < operator that worked by cross-multiplying the two fractions. This works fine until the numerators and denominators are big enough that overflow causes a violation of ordering transitivity; at that point, the insert() function does the wrong thing when traversing its red-black tree, occasionally failing to find that a value is already present. Using longer ints solves this and gets your answer for $n=23$. I will be submitting this to OIS. $\endgroup$ – Mark Fischler Nov 25 '14 at 21:36
  • $\begingroup$ @MarkFischler OK. Let me know once you submit it to OEIS. Also, give me the bounty. $\endgroup$ – Adhvaitha Nov 25 '14 at 23:19

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.