49
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – joro
    Dec 13, 2013 at 7:12
  • $\begingroup$ I think Hee Oh at Caltech (now at Yale) did some work on similar problems. $\endgroup$
    – Turbo
    Dec 13, 2013 at 11:32
  • $\begingroup$ ....similar problems in higher dimension. $\endgroup$
    – Turbo
    Dec 13, 2013 at 11:39
  • $\begingroup$ [Googling lattice points from origin is also an easy way to find the answer. It links to: shreevatsa.wordpress.com/2008/11/07/… $\endgroup$ Dec 14, 2013 at 3:39
  • $\begingroup$ mathworld.wolfram.com/VisiblePoint.html $\endgroup$ Apr 14, 2015 at 8:12

4 Answers 4

61
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Is there an elementary reference for this result? $\endgroup$ Dec 13, 2013 at 2:11
  • $\begingroup$ Thanks for the quick and knowledeable answer! I took the liberty of adding the question for higher dimensions. $\endgroup$ Dec 13, 2013 at 2:23
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 13, 2013 at 2:24
  • $\begingroup$ "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. $\endgroup$ Dec 13, 2013 at 9:16
  • 5
    $\begingroup$ But what percentage of the infinitely many references will be visible from the origin? $\endgroup$ Dec 13, 2013 at 9:20
21
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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