4
$\begingroup$

It is extremely well-known that the probability of any two random integers being relatively prime is $\zeta(2)^{-1}$ (see here).

From An Introduction to Analytic Number Theory by Apostol, the proof involves counting lattice points and finding the limit $$\lim_{r\to\infty}\frac{N'(r)}{N(r)}$$ where $N(r)$ is the number of lattice points in the square governed by $|x|\le r$ and $|y|\le r$, and $N'(r)$ is the number of lattice points visible from the origin.

For some background, the term "visible" is defined as follows:

Two lattice points $P$ and $Q$ are said to be visible if the line joining the two does not go through any other lattice points.

Now what if $n\neq2$; that is,

What is the limit of the probability that $n$ integers chosen at random in the interval $[1,N]$ are coprime as $N\to\infty$ with $n>2$?


Let's consider the simplest case: $n=3$. We imitate the proof for when $n=2$.

Firstly, an extension to Thm 3.8 can be easily proven.

Theorem: Two lattice points $(a_1,\cdots,a_n)$ and $(b_1,\cdots,b_n)$ are visible iff $a_1-b_1$, $a_2-b_2$ up to $a_n-b_n$ are relatively prime.

The $24$ lattice points nearest the origin are all visible from the origin - there are $24$ points "surrounding" the origin of unit distance. By symmetry, we see that $N'(r)$ is equal to $24$, plus $24$ times the number of visible points in the region $$\{(x,y,z):2\le x\le r, ???\}$$ We cannot use $1\le y\le x$ since the gradient of the line joining the origin and $(r,r,r)$ is no longer $1$. Of course, we can try to use this, but I feel that this makes it more complicated than it should be.


So how should I continue? Is there an alternative method? And what would be the general approach for large $n$, ie. is there an expression (in terms of $n$) that finds the probability that $n$ integers chosen at random are coprime?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

This is an heuristic argument for getting the correct probabilities.
Let us clarify that from now on the meaning of random integer is "consider what happens for random elements of $[1,N]$ picked according to a uniform distribution, then let $N\to +\infty$".
For a fixed prime $p$ and three random integers $a,b,c$, the probability that $p$ does not divide more than one element among $\{a,b,c\}$ is $\left(\frac{p-1}{p}\right)^3 + \frac{3(p-1)^2}{p^3}$. It follows that the probability that three random integers are mutually coprime is

$$ \prod_{p}\left(1-\frac{3p-2}{p^3}\right)\approx 28.67\% $$ and similarly the probability that four random integers are mutually coprime is $$ \prod_{p}\frac{(p-1)^3(p+3)}{p^4}\approx 11.48\% $$ and the probability that five random integers are mutually coprime is $$ \prod_{p}\frac{(p-1)^4(p+4)}{p^5}\approx 4.09\% $$ etcetera. Asymptotically, the probability that $m$ random integers are mutually coprime behaves like $K e^{-J m}$ for some positive constants $J,K$.

$\endgroup$
4
  • 2
    $\begingroup$ Your heuristic argument is proven in the paper of Laszlo Toth: "The probability that k positive integers are pairwise relatively prime", Fibonacci Quarterly (2002) 40 (1), 13-18. See fq.math.ca/Scanned/40-1/toth.pdf for an online copy. $\endgroup$ Mar 21, 2018 at 20:33
  • $\begingroup$ @MichaelLugo: truth to be told, I knew that such heuristic argument can be turned into a rigorous proof, but I was too lazy too really carry on the estimation of remainders of truncated Dirichlet series. However I wasn't aware of Toth's paper, so thanks for the valuable contribution. $\endgroup$ Mar 21, 2018 at 20:38
  • $\begingroup$ I was too lazy to even come up with the heuristic! $\endgroup$ Mar 22, 2018 at 13:17
  • $\begingroup$ @MichaelLugo, I wouldn't say the limit itself is the main point of Toth's paper as the qualitative asymptotic is quite elementary. The error estimate he obtains is certainly what makes the work worthy of publication. $\endgroup$
    – zoidberg
    Jan 10, 2019 at 7:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .