Lattice points visible from the origin

[A test of LaTeX-to-Wordpress conversion. Bugs remain, point them out. Original PDF]

Here is a problem I love. It is simple to state, and it has a solution that is not trivial, but is easy to understand. The solution also goes through some beautiful parts, so I can promise it’s worth reading :-)

[The solution is not mine. Also, the question is just an excuse for the ideas in the solution. :P]

Question. Suppose you are standing on an infinite grid in the plane. You can see infinitely in all directions, but you cannot see through grid points: a point is hidden from view if some other grid point lies in your line of sight. What fraction of the grid points can you see?

Let us first imagine that we are standing at the origin, and that the grid is that of the lattice (integer) points.

The blue points are visible; the grey points are not

We now want to examine the question of which pairs are visible from the origin. The question becomes easier if asked inversely: When is not visible? The point is not visible because the point is "in the way", and the point is not visible because the point obscures it. We see that a point is not visible precisely when there is another lattice point blocking it, which is when there is an integer pair such that . Equivalently, is not visible precisely when there is an integer dividing both and , and is visible when there is no such integer, i.e. when and have no common factor. We can now state our question differently:

For two "random" integers and , what is the probability¹ that they have no common factor?

For this to happen, it must be the case that no prime number divides both and . For a particular prime , the probability that is divisible by is , and the same for , so the probability that both are divisible by is , and so the probability that does not divide both of them is . The probability that no prime divides both and is therefore

To calculate this number, we use a beautiful relation introduced by Euler: the Euler product formula. It relates what is now called the Riemann zeta function to a certain product over the primes; of course Euler was doing this nearly a hundred years before Riemann was born.² Euler’s product formula, which marked the beginning of analytic number theory, is the following.

Consider the zeta function

for .

Euler’s insight was to observe that this sum can be written as an infinite product over the primes:

The justification for the above is the fundamental theorem of arithmetic, namely that every natural number has a unique prime factorisation — thus if we multiply out the product on the right, then every term occurs exactly once, as a product of the appropriate powers of the primes in .

Now each factor in the product is a geometric series, so we can write the relation as:

We now know how to evaluate the expression that we want: The above relation says that

and as "every child knows",³

So we have the answer to our original question:

The fraction of the lattice points that are visible from the origin is .

Let’s test it on our figure above, which shows the lattice points with coordinates in to that are visible from the origin. There are points, of which there are visible (the blue points). That’s a fraction of , while . So it’s a little higher, but it is to be expected that near the origin, a larger fraction of the points are visible. We can test it on larger and larger squares – let’s say we take the square with all coordinates in to , and count the number of visible points in that square. As the square has points, we expect that will be about for large .

And indeed it is:

Fraction of visible points for NxN squares, plotted for N≤200

Needless to say, this is not a great way to calculate , but it gives us confidence that our result is correct.

Related matters

We can ask the same question in higher dimensions: What fraction of the lattice points in 3 dimensions are visible from the origin? The above analysis shows that the answer is (; an exact expression is not known). Similarly the answer for four dimensions is which is , and in dimensions it is as . It makes sense that a larger fraction of the points are visible in higher dimensions; for a point to be obscured all its coordinates must share a common factor, so it happens more rarely in higher dimensions.

Both our use of probability and our formulation of the question are not technically valid. The problem with the former has already been mentioned. For the latter, consider this fact: there are a countable number of lattice points, and a countable number are visible, and a countable number not — all these sets are of the same cardinality! The correct statement is that the fraction (or probability) of visible points in the square with coordinates less than tends to as .

Euler’s summation formula and the zeta function are also related to astonishing results like the Möbius inversion formula…

Appendix

Figure fig:seven was generated using MetaPost; the source code is included here for (my) future reference. You can try it out at Troy Henderson’s MetaPost Previewer.

% Based on Urs Oswald's tutorial at http://www.ursoswald.ch/metapost/tutorial.html
beginfig(1)
u:=20;                    % 20 = 20bp = 20 PostScript points = 20/72 in
wi:=7;                    % width  in units u
he:=7;                    % height in units u
height:=he*u;             % height
width:=wi*u;              % width

% --- Axes ---
drawarrow ((0,0)--(wi+1,0))  scaled u;     % x-axis
drawarrow ((0,0)--(-wi-1,0)) scaled u;     % x-axis
drawarrow ((0,0)--(0,he+1))  scaled u;     % y-axis
drawarrow ((0,0)--(0,-he-1)) scaled u;     % y-axis
% --- Grid ---
for i=-wi upto wi:
  draw (-width, i*u)--(width, i*u) withcolor .7white;
endfor
for j=-he upto he:
  draw (j*u, -height)--(j*u, height) withcolor .7white;
endfor
% --- Boundary ---
draw (-width,-height) -- (width,-height) -- (width,height) -- (-width,height) -- cycle;

def gcd(expr x,y) = if y=0: abs(x) else: gcd(y,(x mod y)) fi enddef;

pickup pencircle scaled 4;
for i=-wi upto wi:
  for j=-he upto he:
    if gcd(i,j)=1:
      pickup pencircle scaled 1;
      draw (0,0)--(i,j) scaled u withcolor .7white;
      pickup pencircle scaled 4;
      draw (i,j) scaled u withcolor .8blue;
    else:
      draw (i,j) scaled u withcolor .8white;
    fi
  endfor
endfor
endfig;
end

---

1. This restatement in terms of probability is not fully justified — in fact there is no such thing as a uniform distribution on the natural numbers — but let’s do it anyway. ↩

2. Euler did it no later than 1739 (I don’t know the exact year); Riemann was born in 1826. ↩

3. This famous relation, like so many of them, is also due to Euler; look up the Basel problem. ↩