What fraction of the integer lattice can be seen from the origin?

Question

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:
   
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$:
   
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$).

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

Here is an elementary argument using Euler products. I'm not sure if the initial probability part is rigorous, but it's a heuristic argument at least. The probability of a prime $p$ dividing a positive integer is $\frac{1}{p}$. Then the probability of $p$ dividing all entries of a $d$-tuple of positive integers is $\frac{1}{p^d}$. A $d$-tuple has $\gcd$ equal to $1$ if and only if no prime divides all of the elements. So the probability of a $d$-tuple of positive integers being coprime is $$\prod_{p\text{ prime}}{\left(1-\frac{1}{p^d}\right)}.$$ By the formula for an infinite geometric series, $$\frac{1}{1-\frac{1}{p^d}}=\sum_{k=0}^{\infty}{\frac{1}{p^{kd}}},$$ so the above product is equal to $$\left[\prod_{p\text{ prime}}{\left(1+\frac{1}{p^{d}}+\frac{1}{p^{2d}}+\frac{1}{p^{3d}}+\cdots\right)}\right]^{-1}=\left[\sum_{n=1}^{\infty}{\frac{1}{n^d}}\right]^{-1}=\frac{1}{\zeta(d)}.$$