What are the odds of a triangle, if vertices are picked at random from an $m\times n$ square grid?

Question

In an $m\times n $ square grid (assume $m,n >2$), three distinct points are picked randomly. What are the odds they make a non-degenerate triangle? In the limit the odds go to one.

This is related to Sylvester's 4-point problem, but I'm interested in the same problem on a discrete grid. The limit is 25/36 ~ 0.694444. On a 21x21 grid the odds of a quadrilateral are 1053055398/1554599970 ~ 0.67738. The odds of a triangle for a grid might solve this question.

EDIT: The square case is A000938. A table of values has been made.

Answer 1

Let the stepsize be $(p,q)$, where $p$ and $q$ are coprime. Suppose ${p\over q}\gt {m\over n}$, so the steps reach from one $n$-side to the other. The number of consecutive 3 in a row is $(m-2p)(n-2q)$, the number of 3 points chosen from 4 in a row is another $2(m-3p)(n-3q)$, then 3 out of 5 another $3(m-4p)(n-4q)$ until one of the factors goes negative. If $m =kp+a$ where $0\le a\lt p$, and $n \ge kq$, the sum is $$\sum_{i=2}^k (i-1)(m-ip)(n-iq)\\ =mn{k\choose2}-2(mq+np){k+1\choose3} +pq(k^3-k)(3k+2)/12$$
On average, $k\approx \frac mp-\frac12$. To two leading orders, this is $$m^3n/2p^2-m^2n/p\\ -(m^4q+m^3np)/3p^3+(mq+np)m^2/2p^2\\ +m^4q/4p^3-m^3q/3p^2$$ $=m^3/12p^3(2pn-mq)-m^2n/2p+m^3q/6p^2$. It is to be divided by $mn\choose3$ to give a probability of $${1\over p^2n^2}-{mq\over2p^3n^3}-{3\over mn^2p}+ {q\over n^3p^2}$$

On average, a fraction $6/\pi^2$ of the $q$-numbers from 1 to $pn/m$ are coprime to $p$. Summed over q, I get
$${9\over 2\pi^2 pnm}-{15\over\pi^2m^2n}$$
This is doubled to take into account steps in the direction $(p,-q)$, then summed over $p$ from 1 to $m/2$.
$${9\log m\over \pi^2mn}-{15\over2\pi^2mn}$$ Lastly sum over those $p,q$ on the other side of the diagonal,, to get
$$9\log mn-15\over \pi^2mn$$

Answer 2

Here's what I have found out so far:

In a grid of $n \times m$ points, let's denote the number of triangles by $t(n,m)$ and the number of sets of $3$ collinear points by $c(n,m)$, then their sum is the number of sets containing $3$ points in that grid, so $$t(n,m)+c(n,m)=\binom{n\cdot m}{3}$$ I found it easier to focus on the values of $c(n,m)$, and my first attempt was to create a recursive formula using the following strategy:

$3$ collinear points in an $(n+1)\times m$-grid can be contained in the "upper" or the "lower" $n \times m$-grid, or their "outer" points must be contained in the first respectively the last row. For this, if we count $c(n,m)$ twice, we have double-counted the $c(n-1,m)$ collinear $3$-sets completely contained in the intersecting $(n-1) \times m$ grid which we have to subtract. For the number of collinear $3$-sets with points in the first an last row, there are $m$ vertical line segments with $n-1$ inner points each, and there are $\binom{m}{2}$ non-vertical southwest-to-northeast lines (that we have to count twice to also count southeast-to-northwest) that might or might not have inner points in the grid. The number of inner points in such a line segment depends on the vertical and horizontal distances and their $\gcd$, it evaluates to $\gcd(\Delta x,\Delta y)-1$, where the $-1$ excludes the endpoint of the line segment (we only want to count the "inner" points). There are $m-k$ such line segments with horizontal distance $k$ (where $1 \le k \le m-1$), all with vertical distance $n$, so the resulting recursive formula is: $$\begin{align} c(n+1,m) &= 2c(n,m)-c(n-1,m)+m(n-1)+2\sum_{k=1}^{m-1}(m-k)(\gcd(n,k)-1)\\ &= 2c(n,m)-c(n-1,m)+m(n-1)-m(m-1)+2\sum_{k=1}^{m-1}(m-k)\gcd(n,k)\\ &= 2c(n,m)-c(n-1,m)+m(n-m)+2\sum_{k=1}^{m-1}(m-k)\gcd(n,k) \end{align}$$ For a positive integer $m$, knowing that $c(0,m)=0$ and $c(1,m)=\binom{m}{3}$, we can calculate the values of $c(n,m)$, which is (if we store the intermediate values in an array) more efficient than counting brute force.

Another attempt resulted in an explicit formula which unfortunately contains a double-sum with $\gcd$'s:

In the grid of size $n \times m$ we find $n\binom{m}{3}$ vertical and $m\binom{n}{3}$ horizontal $3$-sets of collinear points. As above, we have to add twice the number of non-horizontal southwest-to-northeast collinear $3$-sets. We can count these summing them up by their possible $\Delta x$-$\Delta y$ combinations counting the inner points using a $\gcd$-formula like in the first attempt:

$$\begin{align} c(n,m) &= n\binom{m}{3}+m\binom{n}{3}+2\sum_{k=1}^{m-1}\sum_{l=1}^{n-1}(m-k)(n-l)(\gcd(k,l)-1)\\ &= n\binom{m}{3}+m\binom{n}{3}-2\binom{n}{2}\binom{m}{2}+2\sum_{k=1}^{m-1}\sum_{l=1}^{n-1}(m-k)(n-l)\gcd(k,l) \end{align}$$ Maybe someone can find a way to eliminate the $\gcd$'s from one of the formulas.