Introduction
Imagine you're a creepy stalker whose curious pastime is to observe your neighbors through your super-telescope. Your house locates at the origin $(0,0)$ in 2-D space, while your neighbors' locate at positive points with integral coordinates. We will calculate the percentage of houses that you can watch from your house, assuming that your telescope is powerful enough.
Properties of visible points
We call a point visible from the origin if the line connecting that point and the origin does not go through any other integral point in between. We will prove that
$(a,b)$ is visible $\iff gcd(a,b)=1$
The equation of the line going through $(0,0)$ and $(a,b)$ is
$y= \displaystyle \frac{b}{a}x$ $(1)$
We prove that $(a,b)$ is visible implies $gcd(a,b)=1$. On the contrary, assume that $gcd(a,b)=d>1$. Then the point $\displaystyle (\frac{a}{d},\frac{b}{d})$ is integral and solves $(1)$. Further, that point appears before $(a,b)$ on the line, so $(a,b)$ must be "blocked" by that point. We have a contradiction.
A formula for the percentage of visible points
We will calculate the percentage of points that are visible from all points on 2-D space. This percentage is equivalent to the probability that a random point $(a,b)$ has coprime $x-y$ coordinates.
Remark 1: the probability of a random integer chosen from all natural numbers divisible by a number $\alpha$ is $\displaystyle \frac{1}{\alpha}$
This probability is
$ \displaystyle \lim_{n \to \infty} \frac{\left \lfloor {\frac{n}{\alpha}} \right \rfloor}{n}=\frac{1}{\alpha}$
Return to our problem, we see that $gcd(a,b)=1$ when $a$ and $b$ are not both divisible by any prime. The probability of $a$ divisible by a prime $p$ is $\displaystyle \frac{1}{p}$ and similarly for $b$. So the probability of $a$ and $b$ both divisible by $p$ is $\displaystyle \frac{1}{p^2}$. Therefore, the probability of $a$ and $b$ not both divisible by $p$ is $1-\displaystyle \frac{1}{p^2}$.
Our desired probability that $gcd(a,b)=1$,
$P=\displaystyle \prod_{p \in \mathbb{p}} (1-\frac{1}{p^2})$
The $\zeta$ function is defined as following,
$\displaystyle \zeta(s) = \sum_{n \in \mathbb{N}} \frac{1}{n^s}$
We prove that $\displaystyle P= \frac{1}{\zeta(2)}$
First, note that $\displaystyle \frac{1}{1-p^-2}$ is the sum of infinite geometric series. So
$\displaystyle \frac{1}{P}= \prod_{p \in \mathbb{P}} (1+\frac{1}{p^2}+\frac{1}{p^4}+\frac{1}{p^6}+...) = \sum_{n \in \mathbb{N}} \frac{1}{n^2} = \zeta(2)$
Therefore,
$\displaystyle P = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}$
A calculation of the $\zeta$ function is too complicated and beyond the scope of this article.
No comments:
Post a Comment