Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the integer lattice points in the positive quadrant $Q$ of $\mathbb{Z}^2$. Say that a point $(x,y)$ of $Q$ is visible from the origin if the segment from $(0,0)$ to $(x,y) \in Q$ passes through no other point of $Q$. So points block visibility, and the only points visible from the origin are those with a clear line of sight:
   LatticeVisib8Grid
Let $\nu(n)$ be the ratio of the number of points visible within the square with corner $(n,n)$ to $n^2$. For example, for $n=8$, $43$ of the $64$ points are visible, so $\nu(n) = 43/64 \approx 0.67$.

Q: What is $\lim_{n \to \infty} \nu(n)$?

It appears to be approaching $\approx 0.614$:
   LatticeVisib80Plot
The question bears some similarity to Polya's Orchard Problem (T.T. Allen, "Polya's orchard problem," The American Mathematical Monthly 93(2): 98-104 (1986). Jstor link), but I cannot see my question is answered in that literature.

One could ask the same question for $\mathbb{Z}^d$.


Answered by Pete Clark: the limit is $\frac{1}{\zeta(d)}$. Thus in higher dimensions, almost all the lattice points are visible (because $\zeta(d)$ approaches $1$).

share|improve this question
1  
Related to OEIS: oeis.org/A059743 A059743 Number of points of norm^2 <= n^2 in the square lattice that are visible from the origin. –  joro Dec 13 '13 at 7:12
    
I think Hee Oh at Caltech (now at Yale) did some work on similar problems. –  J.A Dec 13 '13 at 11:32
    
....similar problems in higher dimension. –  J.A Dec 13 '13 at 11:39
    
[Googling lattice points from origin is also an easy way to find the answer. It links to: shreevatsa.wordpress.com/2008/11/07/… –  Benjamin Dickman Dec 14 '13 at 3:39
add comment

3 Answers

up vote 45 down vote accepted

The limiting ratio is $\frac{1}{\zeta(2)} = \frac{6}{\pi^2}= 0.6079271018540266286632767792\ldots$

The question is easily seen to be equivalent to "What is the probability that two integers are relatively prime?" This old chestnut of elementary number theory has been addressed before on this site: see here. The idea is incredibly simple and appealing: we consider the events "$a$ and $b$ are both divisible by $p$" -- as $p$ runs over all primes -- as independent and use the Euler product for $\zeta(2)$. It is not completely obvious how to make this reasoning rigorous, but it can be and has been done in any number of ways. The linked to answer contains one of them.

Since the OP is highly involved in discrete geometry I wanted to mention a more general result: if $n \geq 2$ and $\Omega \subset \mathbb{R}^n$ is a bounded, Jordan measurable region, then the number of primitive (= visible from the origin) lattice points in the dilate $r\Omega$ of $\Omega$ is asymptotic to $\left(\frac{\operatorname{Vol} \Omega}{\zeta(n)} \right) r^n$. For $n =2$ this is proved for instance in $\S$ 24.10 (of the sixth edition, but I don't think that matters) of Hardy and Wright's An Introduction to the Theory of Numbers. It is stated in $\S$ 7.3 of these notes and placed there in a more general context: namely it is related to the celebrated Minkowski-Hlawka Theorem. (The proof was left to two students in the graduate seminar I was then running. They presented a proof, but I didn't get around to incorporating their arguments into the writeup. Anyway the transition from the two-dimensional case is straightforward.)

share|improve this answer
    
Is there an elementary reference for this result? –  Felix Goldberg Dec 13 '13 at 2:11
    
Thanks for the quick and knowledeable answer! I took the liberty of adding the question for higher dimensions. –  Joseph O'Rourke Dec 13 '13 at 2:23
2  
I added a reference to Hardy and Wright. In fact this is (clearly) equivalent to a previous MO question, which I referenced above; a short, rigorous proof is given there. But the truth is that this is a familiar question from undergraduate number theory, so if you google "primitive lattice point" "visible lattice point" or "probability that two integers are relatively prime" you'll find infinitely many references. The citations given in my answer are really for a somewhat more general theorem in discrete geometry that I think the OP (a discrete geometer) will be interested in. –  Pete L. Clark Dec 13 '13 at 2:24
    
"you'll find infinitely many references" suggests the follow-up question of describing the asymptotics of the number found as function of the invested search effort. –  Marc van Leeuwen Dec 13 '13 at 9:16
4  
But what percentage of the infinitely many references will be visible from the origin? –  Gerry Myerson Dec 13 '13 at 9:20
add comment

Another way to obtain this $6/\pi^2$ is this. By symmetry it is enough to count the points in the part of the first quadrant with $m\geq n$. Let us consider the row $(m,k), 0\leq k\leq m$. The number of points in this row visible from the origin is the Euler "totient function" $\phi(m)$. So the total number of such points is approximately $8(\phi(1)+\ldots+\phi(m))$. Using the asymptotics $$\phi(1)+\ldots+\phi(m)\sim 3m^2/\pi^2$$ we obtain the result. The asymptotics is due to Arnold Walfisz, and the reference can be found on Wikipedia, "Euler's totient function".

share|improve this answer
add comment

The two-dimensional version of this question was already asked (although in a different language) here.

In fact, besides the generalization to measurable sets mentioned by Pete, this result can be generalized in the following way. A set of $k$ points $x_1,\ldots,x_k$ in $\mathbb{Z}^n$ is said to be primitive if the open paralellotope $\left\{ \alpha_1 x_1 + \ldots \alpha_k x_k : 0 < \alpha_i < 1 \right\}$ contains no integer point. The "probability" that a set of $d$ points is primitive equals to $$\frac{1}{\zeta(n) \zeta(n-1) \ldots \zeta(n-k+1)},$$ as shown, for example, in this paper.

One way of formalizing the notion of "probability" is to define it for the restriction of $\mathbb{Z}^n$ to some ball of radius $R$ and let $R \to \infty$, as done in this paper . This is sometimes called the "natural density" of $\mathbb{Z}^n$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.