Probability of $k$ integers being mutually coprime

Question

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?

Answer 1

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$.