# Reference request: probability that d numbers are coprime

The following theorem can be found in Hardy-Wright (Theorem 459), except that they state it only for $$d=2$$. Do you know of a reference where the proof of this general statement is written?

Theorem: Let $$d\ge2$$ be an integer. Let $$F$$ be a bounded subset of $$\Bbb R^d$$. For every positive real number $$r$$, denote by $$F(r)$$ the set of points $$x$$ of $$\Bbb Z^d$$ such that $$x\over r$$ belongs to $$F$$. Assume that the cardinality of $$F(r)$$ divided by $$r^d$$ converges to some non-zero limit when $$r$$ goes to infinity. Then, when $$r$$ goes to infinity, the cardinality of the set of $$(x_1,\ldots,x_d)$$'s in $$F(r)$$ such that $$\operatorname{GCD}(x_1,\ldots,x_d)=1$$ is equivalent to $$r^d/\zeta(d)$$ when $$r$$ goes to infinity.

Thank you very much for your time!

• Thank you Daniele for the editing! Apr 17, 2020 at 17:17

The proof for general $$n \geq 2$$ is the same as the $$n = 2$$ case. For simplicity we shall consider the region $$F = [1,X]^n$$ where $$X$$ is some large positive number. We put $$F_d$$ be the subset of $$F \cap \mathbb{Z}^n$$ consisting of those tuples whose coordinates are all divisible by $$d$$. Note that $$d \leq X$$, by definition.

We see that

$$\displaystyle |F_d| = \frac{X^n}{d^n} + O \left(\frac{X^{n-1}}{d^{n-1}}\right).$$

We now write $$F^\ast$$ for the subset of $$F$$ consisting of those tuples whose coordinates are co-prime. Then

\begin{align*} |F^\ast| & = \sum_{d \leq X} \mu(d) |F_d| \\ & = \sum_{d \leq X} \mu(d) \left(\frac{X^n}{d^{n}} + O \left(\frac{X^{n-1}}{d^{n-1}} \right) \right)\\ & = \prod_{p \leq X} \left(1 - \frac{1}{p^n}\right) X^n + O \left(\sum_{d \leq X} \frac{X^{n-1}}{d^{n-1}}\right) \\ & = \prod_p \left(1 - \frac{1}{p^n} \right) X^n + O \left(X^{n-1} \log X \right) \end{align*}.

To be more explicit, we consider the product

\begin{align*} \prod_{p} \left(1 - \frac{1}{p^n} \right) & = \prod_{p \leq X} \left(1 - \frac{1}{p^n} \right)\prod_{p > X} \left(1 - \frac{1}{p^n} \right) \\ & = \prod_{p \leq X} \left(1 - \frac{1}{p^n} \right) \left(\exp \left(\sum_{p > X} \log \left(1 - p^{-n} \right) \right) \right) \\ & = \prod_{p \leq X} \left(1 - \frac{1}{p^n} \right)\left(1 + O(X^{1-n})\right) \end{align*}

which justifies the first previous calculaton.

Finally, by the Euler product of the Riemann zeta function we have $$\zeta(n)^{-1} = \prod_{p} (1 - p^{-n})$$.

• Thank you very much for your time, Stanley. I agree that the same proof works. However, I am not looking for a proof but for a place where it is written so that I can refer to it in a paper: it really is a reference request rather than a mathematical question. Also, I do want the fully general statement. Your particular statement is proved here for example: arxiv.org/abs/1602.07180 Apr 17, 2020 at 17:16
• From my answer you should gain the confidence to simply say "this is proved explicitly for $n = 2$ by Hardy and Wright and the general case follows similarly". The first sentence in my answer says essentially the same thing Apr 17, 2020 at 18:28

Let $$F$$ be a bounded subset of $$\mathbb R^d$$ with $$d \geq 2$$. We define $$F_r := rF \cap \mathbb Z^d$$ for any real number $$r>0$$ and assume that the limit $$\mathcal V(F) := \lim_{r \to + \infty} \frac{|F_r|}{r^d}$$ exists (for convex subsets, this is the Lebesgue volume of $$F$$). We rewrite the proof of Theorem 459 of Hardy–Wright so that it yields the following more general result.

If $$\mathcal V(F)$$ is well-defined, then we have $$\lim_{r \rightarrow + \infty} \frac{\left| \left\{ x \in F_r, \operatorname{gcd}(x_1, \cdots, x_d) = 1 \right\} \right|}{r^d} = \frac{\mathcal V(F)}{\zeta(d)}.$$

Proof. We can and will assume that $$0 \notin F$$, which will not change any of the limits. We also fix $$N$$ such that $$F \subset [-N,N]^d$$.

For every rational $$r>0$$, let $$f(r) = \left| \left\{ x \in F_r, \operatorname{gcd}(x_1, \cdots, x_d) = 1 \right\} \right|$$. As $$0 \notin F$$, $$|F_r| = f(r)=0$$ when $$r<1/N$$ and $$f(r) \leq |F_r| \leq (2rN+1)^d \leq (3rN)^d$$ for all $$r \geq 1/N$$, so $$|F_r| \leq (3rN)^d$$ in all cases. For any point $$x$$ of $$F_r$$, there is a unique integer $$k \in \mathbb N$$ such that the gcd of the coordinates of $$x$$ is $$k$$, and then $$x/k$$ contributes to $$f(r/k)$$. Consequently (the right-hand side being in fact a finite sum) $$|F_r| = \sum_{k=1}^{+ \infty} f(r/k).$$ By Möbius inversion, we then get $$f(r) = \sum_{k=1}^{+ \infty} \mu(k) |F_{r/k}|.$$

The sum of $$\mu(k)/k^d$$ converges absolutely towards $$1/\zeta(d)$$ as $$d \geq 2$$, so $$\frac{f(r)}{r^d} - \frac{\mathcal V(F)}{\zeta(d)} = \sum_{k=1}^{+ \infty} \frac{\mu(k)}{k^d} \left( \frac{|F_{r/k}|}{(r/k)^d} - \mathcal V(F) \right).$$ Let $$\varepsilon>0$$. By definition of $$\mathcal V(F)$$, we fix $$n_0$$ such that if $$r/k \geq n_0$$, $$\left| \frac{|F_{r/k}|}{(r/k)^d} - \mathcal V(F) \right| \leq \varepsilon$$, which gives the inequality $$\sum_{k=1}^{\lfloor r/n_0 \rfloor} \frac{1}{k^d} \left| \frac{|F_{r/k}|}{(r/k)^d} - \mathcal V(F) \right| \leq \zeta(d) \varepsilon.$$

On the other hand, the bounds on $$|F_{r/k}|$$ give $$\sum_{k > \lfloor r/n_0 \rfloor} \frac{1}{k^d} \left| \frac{|F_{r/k}|}{(r/k)^d} - \mathcal V(F) \right| \leq \left((3N)^d + \mathcal V(F)\right) \times \frac{ (\lfloor r/n_0 \rfloor)^{1-d} }{d-1}.$$ Hence, for $$r$$ large enough, the absolute value of $$\left|\frac{f(r)}{r^d} - \frac{\mathcal V(F)}{\zeta(d)}\right|$$ is smaller than $$2 \zeta(d) \varepsilon$$, which proves the desired convergence. $$\blacksquare$$

Acknowledgements. This post greatly benefitted from exchanges with Samuel Le Fourn.

You can find the general idea (Möbius inversion) in he book Vinogradov, I. M. Elements of number theory Dover Publications Inc., 1954 (Ch. 2.3.d and problem 2.17). But it is written in a strange form.  