Lattice points visible from the origin
[A test of LaTeXtoWordpress 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.
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^{1} 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.^{2} 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",^{3}
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:
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; % xaxis
drawarrow ((0,0)(wi1,0)) scaled u; % xaxis
drawarrow ((0,0)(0,he+1)) scaled u; % yaxis
drawarrow ((0,0)(0,he1)) scaled u; % yaxis
%  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

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. ↩

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

This famous relation, like so many of them, is also due to Euler; look up the Basel problem. ↩
Typo in the paragraph with the estimation of the probabilities. P(not both x and y divisible by p) should be 1 – 1/p^2, not 1/p^2 as typed.
Beautiful problem though.
foo
Fri, 20081107 at 16:01:31 +05:30
Thanks! Fixed. (It wasn’t a bug in the conversion; it’s there in the original source… haven’t fixed the PDF yet.)
Shreevatsa
Fri, 20081107 at 20:47:46 +05:30
Nice analysis.
I was wondering whether one can make some extension of this to the continuum. In the continuum what you would get is that the visible thing is the projective space. And the projective space obtained from ndimensions is 1 dimension less than the ambient space.
In your analysis on the lattice you see that the fraction of visible points tends to 1 as d> infinity..I wonder is this is somehow related to the fact that in the continuum (one can make sense of a limiting process of the lattice spacing going to 0) the “visible dimension” is 1 less than the ambient.
Further you can read about this related thing called the “Olber’s Paradox”. I recently did the calculations to understand it. Slightly tricky stuff.
Lastly : may be this is bit too much of optimism…but still can you think of something along these lines:
C/lattice is the torus and that is a curve (probably an elliptic curve) in CP^1. So the “visible points” set up an equivalence relation on the points of that curve (or the torus). Can you think of an geometrical interpretation of your results in this framework?
PS: Your blogs seem pretty much different from the person I knew during the undergrad!
Anirbit
Fri, 20081107 at 21:20:23 +05:30
Even without extending to “the continuum”, the visible points still constitute (two copies of) the (rational) projective space. And it is still true that the visible points are “one dimension less” than the whole space (and that each visible point “knocks out” only one dimension of points). I don’t see how to prove anything using this, though.
It *is* the case, though, that the fraction 1/zeta(d) [the "fraction of visible points" in d dimensions, also the fraction of {dth power}free numbers] is somewhat similar “in shape” to (d1)/d (see image) but I don’t know if it’s just a coincidence or whether we can prove that they are related.
I know of Olber’s paradox (hint: Asimov wrote a story (yes, *the* story) about it ;)) (and it was resolved by Poe; this is the kind of trivia that makes life worth living :P), but I thought its resolution has less to do with the distribution of stars than the finiteness of history.
I realise that C/lattice is indeed the torus, but I don’t see any equivalence relation on it.
And I have only one blog :)
Shreevatsa
Sat, 20081108 at 03:23:36 +05:30
I wasn’t talking of proving anything…just making structural observations to see what is the larger framework in which this visible points on the lattice analysis fits in.
The 2 directions seem to be:
1. through projective spaces
2. through elliptic curves
It might be interesting to try to see how the two pictures are related.
By “blogs” I didn’t mean different blog pages but different blog articles! :)
Anirbit
Sat, 20081108 at 06:09:01 +05:30
What is the Asimov story that you are referring to?
May be sometime (read: in the long run) later in life I shall read it…
Anirbit
Sat, 20081108 at 06:11:03 +05:30
Apologies for these multiple replies…but this analysis of yours seems to spark off quite a few other things:
Doesn’t this analysis of yours actually give a way numerical technique to compute the value of pi ?
May be you can try comparing the convergence rate of this to other statistical methods like needle drop on parallel lines and point throw in a circle etc.
Anirbit
Sat, 20081108 at 08:31:36 +05:30
Any calculation of probability that involves π can be used to approximate π (the “MonteCarlo” idea), but as I already mentioned in the post, “Needless to say, this is not a great way to calculate π…” — because even at N=200, there are visible differences from the true value.
There are already great ways of computing it; several Machinlike formulae, identities due to Ramanujan, Borwein’s algorithm (with variants where each iteration multiplies the number of correct digits by nine), and cool anydigityouwant “spigot” algorithms like the the Bailey–Borwein–Plouffe formula. There is no reason to use MonteCarlo methods to find π, except out of curiosity. None of them will work beyond the barrier of fixedprecision arithmetic and the variance in the probability distribution.
Shreevatsa
Sat, 20081108 at 14:26:17 +05:30
any ideas how one could generalize this to “discs of finite radius”, in place of the infinitesimally small points here…?
TrisQ
Wed, 20101215 at 14:48:00 +05:30
Interesting question; I’ll think about it… it doesn’t seem like a numbertheory problem anymore, that’s for sure. :)
S
Sat, 20101218 at 02:38:33 +05:30
I realize this is an old post and I apologize if commenting on it at this point is frowned upon but does this analysis carry over to lattices generated by any basis set?
josephpzambrano
Sun, 20130331 at 21:11:25 +05:30
Hi, sorry for the delay in replying… commenting on old posts is perfectly fine, but I may not know the answer. :) In this case, I’m not even sure I understand the question: are you asking whether, if we take the lattice generated by (say) (2,3) and (1,5), and count the number of visible lattice points, the proportion will be the same? I don’t think that’s going to be the case, though I haven’t given enough thought as to why, or what the right answer will be.
S
Sun, 20130407 at 21:29:20 +05:30
No problem at all, and yes that is what I was asking. I suppose a linear transformation taking the standard lattice into one generated by a different basis set must be an isomorphism to preserve the mentioned proportion. In which case, I wonder what happens when the mapping isn’t quite as nice.
josephpzambrano
Mon, 20130408 at 00:33:13 +05:30
You mentioned this solution isn’t yours — well, who’s is it? Can you provide a reference?
Thank you!
Tal
Tue, 20130910 at 22:25:40 +05:30
I think it’s wellknown and probably “folklore”. I’d be interested if you find a reference crediting it to a single person or persons.
S
Sat, 20130928 at 04:50:33 +05:30