[Math] The amount of right triangles on a finite square/rectangular lattice.

combinatorics

To preface I am not entirely sure lattice is the correct word for this but my "research" on the question makes it seem like that is a good way to phrase the question. Just to highlight my experience I am currently taking "calculus 2" and a discrete/foundations of math course but I don't mind going outside of that zone of knowledge to figure out the problem. I am not looking for a program that iterates through points finding which triangles are right and which are not.

For simplicity I will only be talking about the square lattice. The triangles in question can only have their vertices on lattice points.

What I have done so far:

  • Found the number of ways to place points. If there are $n$ points its $n \choose 3$.
  • The amount of right triangles where the right angle is aligned with rows and columns. $n (p-1)^2$. $n$ is the amount of points that could be the vertices of the right angle and each $(p-1)$ is the amount of points left to choose from.

I am not really sure what to do from here. I have had a few thoughts though. I looked to see if finding the amount of rectangles and somehow connecting it to the amount of triangles would be easier, but to get all the triangles there would be some rectangles that were partially outside the lattice. I have also thought that maybe there is someway to find all the right triangles that could not be made by other ones(in the lattice) and maybe that could lead to a way to say how many there are. There is of course "how many are not right?" question but I do not know how I would find that. I have also tried using perpendicular lines but not really sure how to apply that idea to get the amount of right triangles.

Best Answer

I think it was a mistake to look at the square case "for simplicity". The rectangular case is more approachable, because one can get a meaningul result by fixing the height $k$ and considering the dependence on width $n$. The simplest case is $n\times 2$, which yields $$4\binom{n}{2} +2(n-2) $$ right triangles. R. H. Hardin observed empirically that for every $k$ there exists $n_0$ such that the number of right triangles is a quadratic function of $n$ when $n>n_0$. (The links to relevant OEIS data: A077435 for square grid and A189814 for rectangular, were found by joriki).

This suggests some lines of investigation (I think these three are in increasing order of difficulty):

  1. Prove the existence of $n_0$ and give an estimate for it.
  2. Find a formula for the $n^2$ coefficient (as a function of $k$) and prove it.
  3. Same for the $n^1$ and $n^0$ coefficients.

In general, the problem is very hard. The $50\times 50$ case, greatly simplified by fixing one vertex of a triangle, was Euler project problem 91.

Related Question