# Probability of $k$ integers being mutually coprime

I now there is a lot of similar question, but in reality none of these answers my question or i didn't found it. It is known that the probability of $$k$$ positive integers choosen randomly is $$1/\zeta(k)$$. More formally if we say that $$\mathbb{P}_k(N)$$ is the probability that $$k$$ positive integers randomly choosen in $$\{ 1, \ldots, N \}$$ are mutually coprime. Then we have that $$\lim_{N \to \infty} \mathbb{P}_k(N) = 1/\zeta(k)$$. The proof is not hard, if we say that $$P_k(N) = \sum_{ \substack{(n_1,\ldots,n_k) = 1\\ 1 \leq n_i \leq N}} 1$$ We note that $$[N]^k = \sum_{1 \leq d \leq N} P_k(N/d)$$ hence $$P_k(N) = \sum_{1 \leq d \leq N} \mu(d)( N/d + O(1))^k$$ Then one can prove that when $$k \geq 3$$ $$P_k(N) = \frac{N^k}{\zeta(k)} + O(N^{k-1})$$ and $$P_2(N) = \frac{N^2}{\zeta(2)} + O(N \log N)$$ Hence since we have $$\mathbb{P}_k(N) = P_k(N)/N^k$$ the results follows. My question is how to adapt the prove if instead the $$k$$ integers were chosen in $$\{ -N,\ldots, -1,0,1,\ldots N \}$$, i would say that the probabilty doesn't change. But not sure how to adapt the proof. We take the convention that $$(0,\ldots,0)=0$$ and we have $$(0,n_2,\ldots,n_k) = (n_2,\ldots, n_k)$$. There is a 1-1 correspondence between $$(n_1/d,\ldots,n_k/d) = 1$$, with $$0 \leq \left| n_i \right| \leq N$$ and for which $$(n_1,\ldots,n_k)=d$$ and the $$k$$-tuples for which $$(m_1,\ldots,m_k)=1$$ with $$0 \leq \left| m_i \right| \leq N/d$$ then we would have that $$P_k(N) = \sum_{ \substack{(n_1,\ldots,n_k) = 1\\ 0 \leq \left| n_i \right| \leq N}} 1$$ similarly we have $$[2N+1]^k = \sum_{0 \leq \left| n_i \right| \leq N} 1= 1+ \sum_{ \substack{ 0 \leq \left| n_i \right| \leq N \\ \text{ not all zero }}} 1 = 1+ \sum_{ 1 \leq d \leq N} P_k(N/d)$$ Hence $$[2N+1]^k - 1 = \sum_{ 1 \leq d \leq N} P_k(N/d)$$ By Moebius inversion formula $$P_k(N) = \sum_{1 \leq d \leq N} \mu(d)( 2N/d + O(1) )^k - \sum_{1 \leq d \leq N} \mu(d)$$ and we similarly we should have $$P_k(N) = \frac{2^k N^k}{\zeta(k)} - M(N) + O(N^{k-1})$$ and $$P_2(N) = \frac{2^2 N^2}{\zeta(2)} - M(N) + O(N \log N)$$ where $$M(N)$$ is the Mertens function and in particular is an $$o(N)$$. And we should have $$\mathbb{P}_k(N) = P_k(N) / (2N+1)^k$$ and in the limit we should hence get the same results. Is this correct?

• Is with "mutually coprime" meant that there is no prime dividing all the numbers ? Jan 4, 2022 at 13:20
• Simulations with upto $20$ numbers indicate that the probabilities are correct also for the new interval $[-N,N]$ Jan 4, 2022 at 13:46
• Yes, I meant that $\gcd(a_1,\ldots,a_n)=1$, and I denoted $\gcd(a_1,\ldots,a_n)$ with $(a_1,\ldots,a_n)$
– 3m0o
Jan 4, 2022 at 13:57
• You should make your question clear in the first line, not in the middle of a long question. It is obvious how to go from $1\ldots N$ to $-N\ldots N$, the probability that $0$ is in one of the values $\to 0$ as $N\to \infty$, so you can discard it, once discarded you are just choosing some integers in $1\ldots N$ then choosing their signs, where the signs don't change the probability of being coprime. Jan 4, 2022 at 14:06

My question is how to adapt the prove if instead the k integers were chosen in {−N,…,−1,0,1,…N}, i would say that the probabilty doesn't change. But not sure how to adapt the proof.

We can express the probability $$q_N^{(k)}$$ that $$k$$ randomly selected integers $$\{n_1, \ldots, n_k\}$$ in the range $$[-N, N]$$ are set-wise coprime (ie. $$\mathrm{gcd}(n_1, \ldots, n_k) = 1$$) in terms of the count $$C_N^{(k)}$$ (ie. $$P_k(N)$$ in your notation) of the number of $$k$$-tuples of integers in $$[1, N]$$ that are set-wise coprime.

Then we can use the result you have already derived for the limit as $$N \rightarrow \infty$$ of the probability $$p_N^{(k)}$$ that $$k$$ randomly selected integers in the range $$[1, N]$$ are set-wise coprime , ie. : $$\begin{equation} p_{\infty}^{(k)} = \lim_{N \rightarrow \infty} p_N^{(k)} = \lim_{N \rightarrow \infty} \frac{C_N^{(k)}}{N^k} = \frac{1}{\zeta(k)}, \hspace{3em} \forall \; k \geq 2 \label{eq:p-prob} \tag{1} \end{equation}$$

to show the asymptotic probability $$q_{\infty}^{(k)}$$ is the same as in the positive integer case, ie. $$q_{\infty}^{(k)} = \lim_{N \rightarrow \infty} q_N^{(k)} = \frac{1}{\zeta(k)}.$$

Note 'set-wise coprime' for integers $$\{n_1, \ldots, n_k\}$$ in $$[-N, N]$$ is a well-defined predicate only for $$n_1, \ldots, n_k$$ not all zero (if all $$n_i$$ are zero there is no greatest common divisor, but if at least one $$n_i$$ is non-zero the set of common divisors is bounded above).

In the case of selecting $$k$$ random integers in the range $$[-N, N]$$ and determining whether they are set-wise coprime, the 'experiment' or 'trial' consists of selecting the $$k$$ random integers, then if they are all zero, rejecting them and repeating again until a not all zero set is obtained. This gives a possibility space consisting of $$(2N + 1)^k - 1$$ equally likely outcomes, namely all $$k$$-tuples $$\neq (0, \ldots, 0)$$.

Thus if $$D_N^{(k)}$$ denotes the total number of these outcomes which are set-wise coprime then : $$\begin{equation} q_N^{(k)} = \frac{D_N^{(k)}}{(2N + 1)^k - 1} \label{eq:q-prob} \tag{2} \end{equation}$$

To determine $$D_N^{(k)}$$ we can partition the set $$D$$ of set-wise coprime outcomes by gathering together all members of $$D$$ with a fixed $$+/-/0$$ pattern amongst their $$k$$ integers into a common subset $$D_{+/-/0}$$, ie. all such members have their zeros, positive terms, and negative terms at the same positions within the $$k$$-tuple. Then if subset $$D_{+/-/0}$$ has $$x \in [0, k - 1]$$ zeros then the number of $$k$$-tuples within it must equal $$C_N^{(k - x)}$$since :

1. such a $$k$$-tuple is set-wise coprime if and only if the moduli of its $$k - x$$ non-zero terms are set-wise coprime. This follows from the fact that the gcd of a list of integers is not affected by the addition or removal of zeros to the list, nor by changes of the signs of the integers.

2. there is a one-to-one correspondence between $$D_{+/-/0}$$ and the set of all set-wise coprime $$(k - x)$$-tuples in $$[1, N]$$, the mapping from the former to the latter being defined by taking the moduli of the $$(k - x)$$ non-zero members of the $$k$$-tuple, and the reverse mapping being defined by inserting zeros and by changing the signs of the integers according to the fixed +/-/0 pattern shared by the members of the set $$D_{+/-/0}$$.

Thus : $$\begin{equation} D_N^{(k)} = |D| = \sum_{ \substack{\text{all distinct} \\ \text{subsets} \\ D_{+/-/0}} } |D_{+/-/0}| = \sum_{ \substack{\text{all distinct} \\ \text{subsets} \\ D_{+/-/0}} } C_N^{(k - x)} \label{eq:summation} \tag{3} \end{equation}$$

where for each subset $$D_{+/-/0}$$, $$x$$ is the number of zeros in each of the $$k$$-tuples within $$D_{+/-/0}$$.

We now enumerate through all the possible subsets $$D_{+/-/0}$$ in the partition.

Consider all $$D_{+/-/0}$$ with $$x = 0$$. We have $$2^k$$ possible $$+/-$$ patterns thus giving $$2^k$$ distinct subsets $$D_{+/-/0}$$, each of size $$C_N^{(k)}$$, thus contributing a total count to the summation (\ref{eq:summation}) of $$\binom{k}{0} \cdot 2^k \cdot C_N^{(k)}$$.

Consider all $$D_{+/-/0}$$ with $$x = 1$$. We have $$\binom{k}{1}$$ possible locations for the zero, each one with $$2^{k - 1}$$ possible $$+/-$$ patterns, thus giving $$\binom{k}{1} \cdot 2^{k - 1}$$ distinct subsets $$D_{+/-/0}$$, each of size $$C_N^{(k - 1)}$$, thus contributing a total count to the summation (\ref{eq:summation}) of $$\binom{k}{1} \cdot 2^{k - 1} \cdot C_N^{(k - 1)}$$.

Similarly for $$x = 2$$ the total contribution to summation (\ref{eq:summation}) is $$\binom{k}{2} \cdot 2^{k - 2} \cdot C_N^{(k - 2)}$$.

And continuing this process :

Consider all $$D_{+/-/0}$$ with $$x = k - 2$$. We have $$\binom{k}{k - 2}$$ possible locations for the $$k - 2$$ zeros, each one with $$2^2$$ possible $$+/-$$ patterns, thus giving $$\binom{k}{k - 2} \cdot 2^2$$ distinct subsets $$D_{+/-/0}$$, each of size $$C_N^{(2)}$$, thus contributing a total count to the summation (\ref{eq:summation}) of $$\binom{k}{k - 2} \cdot 2^2 \cdot C_N^{(2)}$$.

And finally, consider all $$D_{+/-/0}$$ with $$x = k - 1$$. We have $$\binom{k}{k - 1}$$ possible locations for the $$k - 1$$ zeros, each one with $$2$$ possible $$+/-$$ patterns, thus giving $$\binom{k}{k - 1} \cdot 2$$ distinct subsets $$D_{+/-/0}$$, each of size $$C_N^{(1)}$$, thus contributing a total count to the summation (\ref{eq:summation}) of $$\binom{k}{k - 1} \cdot 2 \cdot C_N^{(1)}$$.

The case $$x = k$$ does not arise as the $$k$$-tuple with all zeros is excluded from the possibility space.

We could have $$k = 1$$ and in this case $$C_N^{(k)}$$ is still well-defined, and since $$\mathrm{gcd} (n_1) = n_1$$ for any $$n_1 \in \mathbb{Z^+}$$ we have $$C_N^{(1)} = 1, \; \forall N$$.

Now we can write, $$\forall \; k \geq 1$$ : $$D_N^{(k)} = 2^k \binom{k}{0} C_N^{(k)} + 2^{k - 1} \binom{k}{1} C_N^{(k - 1)} + \cdots + 2^2 \binom{k}{k - 2} C_N^{(2)} + 2 \binom{k}{k - 1} C_N^{(1)}$$

from which using (\ref{eq:q-prob}) we obtain $$\forall k \geq 1$$ : $$\begin{eqnarray*} q_N^{(k)} & = & \frac{1}{(2N + 1)^k - 1} \cdot (2N)^k \biggl[ \binom{k}{0} \frac{C_N^{(k)}}{N^k} + \frac{1}{2N} \binom{k}{1} \frac{C_N^{(k - 1)}}{N^{k - 1}} + \cdots \\ & & \cdots + \frac{1}{(2N)^{k - 2}} \binom{k}{k - 2} \frac{C_N^{(2)}}{N^2} + \frac{1}{(2N)^{k - 1}} \binom{k}{k - 1} \frac{C_N^{(1)}}{N} \biggr] \end{eqnarray*}$$

But, from (\ref{eq:p-prob}) we have : $$\lim_{N \rightarrow \infty} \frac{C_N^{(s)}}{N^s} = \frac{1}{\zeta(s)} \hspace{3em} \mbox{for } s = 2, \ldots, k$$

and $$C_N^{(1)} = 1, \; \forall N$$, so that for $$k \geq 2$$ : $$\lim_{N \rightarrow \infty} q_N^{(k)} = \frac{1}{\zeta(s)}.$$

When $$k = 1$$, we have $$q_N^{(1)} = D_N^{(1)} / 2N = 2 / 2N = 1 / N \rightarrow 0 \text{ as } N \rightarrow \infty$$.