The Lumber Room

"Consign them to dust and damp by way of preserving them"

Lattice points visible from the origin

with 15 comments

[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

The blue points are visible; the grey points are not


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

For two "random" integers x and y, what is the probability1 that they have no common factor?

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

\displaystyle \prod_p\left({1-\frac1{p^2}}\right)

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

\displaystyle \zeta(s) = \sum_{n\ge1}{\frac1{n^s}} = \frac1{1^s} + \frac1{2^s} + \frac1{3^s} + \frac1{4^s} + \dots for s>1.

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

\displaystyle  \zeta(s) = \sum_{n\ge1}{\frac1{n^s}} = \prod_p\left(1 + \frac1{p^s} +  \frac1{p^{2s}} + \frac1{p^{3s}} + \dots\right)

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 \frac1{n^s} occurs exactly once, as a product of the appropriate powers of the primes in n.

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

\displaystyle   \zeta(s)=\sum_{n\ge1}{\frac1{n^s}} = \prod_p{\frac1{1-\frac1{p^s}}}

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

\displaystyle   \prod_p\left(1-\frac1{p^2}\right) = \frac1{\zeta(2)}

and as "every child knows",3

\displaystyle   \zeta(2) = \sum_{n\ge1}{\frac1{n^2}} = \frac{\pi^2}{6} .

So we have the answer to our original question:

The fraction of the lattice points that are visible from the origin is 6/{\pi^2}.

Let’s test it on our figure above, which shows the lattice points with coordinates in -7 to 7 that are visible from the origin. There are 225 points, of which there are 144 visible (the blue points). That’s a fraction of 144/225 = 0.64, while 6/\pi^2 \approx 0.608. 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 -N to N, and count the number V(N) of visible points in that square. As the square has (2N+1)^2 points, we expect that V(N)/(2N+1)^2 will be about 6/\pi^2 for large N.

And indeed it is:

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

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

Needless to say, this is not a great way to calculate \pi, 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 1/\zeta(3) (\approx 0.83; an exact expression is not known). Similarly the answer for four dimensions is 1/\zeta(4) which is 90/\pi^4 \approx 0.92, and in d dimensions it is 1/\zeta(d) \to 1 as d \to \infty. 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 N tends to 6/\pi^2 as N \to \infty.

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.

About these ads

Written by S

Fri, 2008-11-07 at 15:00:30 +05:30

Posted in public

Tagged with , ,

15 Responses

Subscribe to comments with RSS.

  1. 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, 2008-11-07 at 16:01:31 +05:30

  2. 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, 2008-11-07 at 20:47:46 +05:30

  3. 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 n-dimensions 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 frame-work?

    PS: Your blogs seem pretty much different from the person I knew during the undergrad!

    Anirbit

    Fri, 2008-11-07 at 21:20:23 +05:30

  4. 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 (d-1)/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, 2008-11-08 at 03:23:36 +05:30

  5. 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, 2008-11-08 at 06:09:01 +05:30

  6. 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, 2008-11-08 at 06:11:03 +05:30

  7. 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, 2008-11-08 at 08:31:36 +05:30

  8. Any calculation of probability that involves π can be used to approximate π (the “Monte-Carlo” 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 Machin-like formulae, identities due to Ramanujan, Borwein’s algorithm (with variants where each iteration multiplies the number of correct digits by nine), and cool any-digit-you-want “spigot” algorithms like the the Bailey–Borwein–Plouffe formula. There is no reason to use Monte-Carlo methods to find π, except out of curiosity. None of them will work beyond the barrier of fixed-precision arithmetic and the variance in the probability distribution.

    Shreevatsa

    Sat, 2008-11-08 at 14:26:17 +05:30

  9. any ideas how one could generalize this to “discs of finite radius”, in place of the infinitesimally small points here…?

    TrisQ

    Wed, 2010-12-15 at 14:48:00 +05:30

    • Interesting question; I’ll think about it… it doesn’t seem like a number-theory problem anymore, that’s for sure. :-)

      S

      Sat, 2010-12-18 at 02:38:33 +05:30

  10. 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, 2013-03-31 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, 2013-04-07 at 21:29:20 +05:30

  11. 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, 2013-04-08 at 00:33:13 +05:30

  12. You mentioned this solution isn’t yours — well, who’s is it? Can you provide a reference?
    Thank you!

    Tal

    Tue, 2013-09-10 at 22:25:40 +05:30

    • I think it’s well-known and probably “folklore”. I’d be interested if you find a reference crediting it to a single person or persons.

      S

      Sat, 2013-09-28 at 04:50:33 +05:30


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 75 other followers