Visible lattice points, Geometric Probability

Problem 52.1

Let $N$ be a large integer. Choose two integers $m, n$ independently and uniformly from $\{1, 2, \ldots, N\}$ . As $N \to \infty$ , what is the probability that $\gcd(m, n) = 1$ ?

Solution. Let $P_N = \mathbb{P}(\gcd(m,n) = 1)$ for the uniform distribution on $\{1, \ldots, N\}^2$ . For each prime $p$ , let $A_p = \{(m,n) : p \mid m \text{ and } p \mid n\}$ . As $N \to \infty$ , $\mathbb{P}(A_p) \to 1/p^2$ .

Two integers are coprime iff no prime divides both. The events $\{A_p\}$ across primes $p$ are “essentially independent” in the large- $N$ limit: the joint probability $\mathbb{P}(A_{p_1} \cap \cdots \cap A_{p_k})$ is the probability that $p_1 p_2 \cdots p_k$ divides both $m$ and $n$ , which tends to $1/(p_1 \cdots p_k)^2$ , matching the product of individual probabilities.

To justify passing from finitely many primes to all primes, first retain only primes $p\leq M$ . Their joint divisibility probabilities converge as stated. Uniformly in $N$ , the probability that a prime $p>M$ divides all 2 sampled integers is at most $p^{-2}$ , so the union bound makes the omitted probability at most $\sum_{m>M}m^{-2}$ , which tends to $0$ as $M\to\infty$ .

Hence in the limit, $P_\infty = \prod_p \left(1 - \frac{1}{p^2}\right).$ This Euler product is the reciprocal of $\zeta(2) = \sum_{n \geq 1} n^{-2}$ , and Euler’s classical evaluation gives $\zeta(2) = \pi^2/6$ . Therefore $\boxed{P_\infty = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \approx 0.6079.} \qedhere$

Geometric interpretation. Lattice points $(m, n)$ with $\gcd(m, n) = 1$ are exactly those visible from the origin: the line segment from $(0,0)$ to $(m,n)$ passes through no other lattice point. Hence $6/\pi^2$ is the asymptotic fraction of the integer grid visible from the origin. The appearance of $\pi$ in a lattice-counting problem is one of the oldest and most striking examples of a bridge between number theory and geometry.

Lattice points in the grid \{1, \ldots, 10\}^2 . Points visible from the origin (filled rose) are exactly those with coprime coordinates; hidden points (open grey) are behind visible ones on the line through the origin. Asymptotically, the visible fraction is 6/\pi^2 . — Lattice points in the grid $\{1, \ldots, 10\}^2$ . Points visible from the origin (filled rose) are exactly those with coprime coordinates; hidden points (open grey) are behind visible ones on the line through the origin. Asymptotically, the visible fraction is $6/\pi^2$ .

import numpy as np
Nmax, N = 10**4, 10**6
m = np.random.randint(1, Nmax+1, N)
n = np.random.randint(1, Nmax+1, N)
p = (np.gcd(m, n) == 1).mean()
print(f"sim: {p:.5f}   exact: {6/np.pi**2:.5f}")
# sim: 0.60811   exact: 0.60793