#7: The Visible Grid Point Problem

A link to this article in pdf format: [pdf]

Here is a difficult probability question:

Suppose you are standing on an infinitely large square grid at the point (0,0), and suppose that you can see infinitely far but cannot see through grid points. Given a random grid point z = (x,y), where x and y are integers, what is the chance you can see z?

As far as I know, there is no “easy” way to solve this problem. We could try picking random pairs of points and testing a large number of them, and could even write a computer program to do this, testing perhaps billions and billions of cases. But even then, we would not know what the exact answer is supposed to be.

Solution

In any case, the solution to the question is the elegant

\displaystyle\frac{6}{\pi^2},

which is approximately 0.608….

Two methods of solving this problem are given below. They both use the following result:

Lemma 1

The point z = (x,y) is visible if and only if gcd(x,y) = 1, where gcd(x,y) is the greatest common divisor of x and y.

Proof. Let d = gcd(x,y). If d > 1, then let x’ = x/d and y’ = y/d. The line between (0,0) and (x,y) intersects the lattice point (x’,y’), so (x,y) is not visible.

Conversely, if d = 1, then suppose there is a point (x’,y’) on the line between (0,0) to (x,y). Let r = x’/x = y’/y, and note that 0 < r < 1. Write r in lowest term fraction r = s/t where gcd(s,t) = 1. Since 0 < r < 1, it must be that t > 1. This gives the equations sx = tx’ and sy = ty’, which implies, based on gcd(s,t) = 1, that x and y are both divisible by t, which contradicts gcd(x,y) = 1.

Notation

If gcd(m,n) = 1, we say that m and n are relatively prime. Let φ(n) denote the Euler totient function, which counts the number of elements less than or equal to n which are relatively prime to n.

For example, φ(4) = 2 as the gcd(1,4) = 1 and gcd(3,4) = 1. On the other hand, gcd(0,4) = 4, gcd(2,4) = 2, and gcd(4,4) = 4. The pictures below illustrate this example.

visible_lattice_0 visible_lattice_1 visible_lattice_2 visible_lattice_3 visible_lattice_4

Method 1: Prime Factors

This method uses the fact that two numbers are relatively prime if and only if they share no common prime factor.

So for a random point z = (x,y), the chance that x and y are relatively prime is the chance that they share no common prime factor. For each prime p, the chance that a random integer n is divisible by p is 1/p, so the chance that both are divisible by p is 1/p². Thus, the chance that not both are divisible by p is 1 – 1/p².

The chance that x and y share no common prime factor is the chance they do not share each prime, multiplied out for each prime, or

\displaystyle Prob = \prod_p \left(1 - \frac{1}{p^2}\right)

where the product ranges over all primes p.

To calculate this value, note that inverting each term gives a geometric series for each prime p, that is,

\displaystyle\frac{1}{1 - \frac{1}{p^2}} = 1 + \frac{1}{p^2} + \frac{1}{(p^2)^2} + \cdots.

Since each positive integer n is uniquely represented as the product of primes, this implies that each term in the final product of series is 1/n² for some unique n, and furthermore, since this product contains every prime power, we have all the positive numbers n. Hence the inverse of the probability is actually

\displaystyle\frac{1}{Prob} = \prod_p \left(\frac{1}{1 - \frac{1}{p^2}}\right) = \sum_{n=1}^{\infty} \frac{1}{n^2}

where the second equality is a case of the Euler product formula.

The Riemann zeta function ζ(s) is defined for s > 1 by

\displaystyle\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s},

so that

\displaystyle\frac{1}{Prob} = \zeta(2).

Since ζ(2) = π²/6, this implies

\displaystyle Prob = \frac{6}{\pi^2}.

This method has the advantage that it is relatively short, but it is not geometrically intuitive.

Method 2: Geometry and Limits

The second method is initially geometric, but still involves number theory. The strategy is to consider ever-larger squares around the origin point (0,0) and consider the probability of visible grid points within each square and see what value that probability converges to.

Let Sr be the square from -r to r in both coordinates. Let N(r) denote the number of grid points in Sr and N'(r) denote the number of grid points in Sr which are also visible from the origin. Then

\displaystyle Prob = \lim_{r \to \infty} \frac{N'(r)}{N(r)}.

The following diagram is due to Apostol (see references). The shaded region consists of the points in the form (x,y) where 2 ≤ x ≤ r and 1 ≤ y ≤ x.

visible_lattice_apostol

For r = 1, all 8 points around (0,0) are visible. For r ≥ 2, N'(r) is 8 (the closest 8 points) plus 8 times the number of visible points in the shaded region. This is because the infinite grid is symmetric with respect to reflection across axes and diagonals (think UK flag), so all 8 sub-parts will have the same result.

To compute the number of visible points in the shaded region we sum the number of points in the form (x,y) for each x in 2 ≤ x ≤ r. But a point of the form (x,y) is visible if and only if x and y are relatively prime, which means for each x, the contribution to the number of visible points in the shaded region is φ(x). Thus the number of points in the shaded region is

\displaystyle\sum_{n=2}^r \varphi(n)

so that

\displaystyle N'(r) = 8 + 8 \sum_{n=2}^r \varphi(n) = 8\sum_{n=1}^r \varphi(n)

as φ(1) = 1.

Now we use the big-O notation to compare the growth rates of functions. We say that f(x) = O(g(x)) if there exist two constants x0 and M such that for all x ≥ x0, f(x) ≤ Mg(x).

There is a theorem of analytic number theory that states for x > 1,

\displaystyle\sum_{n \leq x} \varphi(n) = \frac{3}{\pi^2}x^2 + O(x \log x),

which implies N'(r) = 24r²/π² + O(r log r). Since N(r) is just the number of points in a square, it is given by N(r) = 4r² + O(r). Then we have the ratio

\displaystyle \frac{N'(r)}{N(r)} = \frac{\frac{24r^2}{\pi^2} + O(r \log r)}{4r^2 + O(r)} = \frac{\frac{6}{\pi^2} + O\left(\frac{\log r}{r}\right)}{1 + O\left(\frac{1}{r}\right)}

which leads to the result

\displaystyle Prob = \lim_{r\to\infty} \frac{N'(r)}{N(r)} = \frac{6}{\pi^2}.

References

 (Note: Comments are disabled for this post due to spam.)

Advertisements