What fraction of the integer lattice can be seen from the origin?
Asked 9 years, 1 month ago
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$).
mg.metric-geometry
discrete-geometry
euclidean-lattices
Joseph O'Rourke
asked Dec 13, 2013 at 1:59
Joseph O'RourkeJoseph O'Rourke
$\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
$\begingroup$ I think Hee Oh at Caltech (now at Yale) did some work on similar problems. $\endgroup$
– Turbo
$\begingroup$ ....similar problems in higher dimension. $\endgroup$
$\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$
– Benjamin Dickman
$\begingroup$ mathworld.wolfram.com/VisiblePoint.html $\endgroup$
– Alexey Ustinov
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.)
122 silver badges33 bronze badges
Pete L. ClarkPete L. Clark
$\begingroup$ Is there an elementary reference for this result? $\endgroup$
– Felix Goldberg
$\begingroup$ Thanks for the quick and knowledeable answer! I took the liberty of adding the question for higher dimensions. $\endgroup$
– Joseph O'Rourke
$\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$
– Pete L. Clark
$\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$
– Marc van Leeuwen
$\begingroup$ But what percentage of the infinitely many references will be visible from the origin? $\endgroup$
– Gerry Myerson
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".
answered Dec 13, 2013 at 17:46
Alexandre EremenkoAlexandre Eremenko
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$.
CampelloCampello
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)}.$$
answered Mar 18, 2021 at 0:05
FavstFavst
Geometric / physical / probabilistic interpretations of Riemann zeta($n>1$)?
Are infinite planar graphs still 4-colorable?
What is the probability that two numbers are relatively prime?
Arbitrarily long composite anti-diagonals?
Visibility interpretation of Riemann zeta zeros on the critical line?
Visibility in a growing orchard
Solutions to phi(x) phi(y) = constant
Efficient visibility blockers in Polya's orchard problem
Can we find lattice polyhedra with faces of area 1,2,3,...?
A random variation on Polya's orchard problem
What is the spinor genus of the Leech lattice?
Can we count the number of integer lattice points in this case?
What does the image of the integer lattice under a norm look like?