On number of coprimes in a bounded interval - II

40 Views Asked by At

If you pick $k$-tuples of integers then you can be guaranteed that they are coprime with probability $\frac1{\zeta(k)}$.

However if you fix $a\in\Bbb N$ and pick $k$-tuple in $[0,a]$ what is the probability that they will be coprime?

For $k=2$ it was answered in On number of coprimes in a bounded interval - I.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $N_k(a)$ denote the number of $k$ tuples in $[0,a]$ that are coprime, then by definition, we have

\begin{aligned} \lfloor a\rfloor^k &=\sum_{\substack{1\le i\le k\\1\le n_i\le a}}1=\sum_{1\le d\le a}\underbrace{\sum_{\substack{1\le i\le k\\1\le n_i\le a\\(n_1,n_2,\dots,n_k)=d}}1}_{n_i=m_id} \\ &=\sum_{1\le d\le a}\sum_{\substack{1\le i\le k\\1\le m_i\le a/d\\(m_1,m_2,\dots,m_k)=1}}1=\sum_{1\le d\le a}N_k\left(\frac ad\right). \end{aligned}

Now, by the Möbius inversion formula for general convolutions, we know that for $k\ge2$,

\begin{aligned} N_k(a) &=\sum_{1\le d\le a}\mu(d)\left\lfloor\frac ad\right\rfloor^k=a^k\sum_{1\le d\le a}{\mu(d)\over d^k}+O\left\{a^{k-1}\sum_{1\le d\le a}{1\over d^{k-1}}\right\} \\ &={a^k\over\zeta(k)}+O\left\{a^k\int_a^\infty{\mathrm du\over u^k}\right\}+O\left\{a^{k-1}\sum_{1\le d\le a}\frac1d\right\}. \end{aligned}

Finally, simplifying the integral gives

$$ N_k(a)={a^k\over\zeta(k)}+O(a^{k-1}\log a), $$

Thus, if $P(a,k)$ denote the probability you are asking, then for $k\ge2$, as $a\to+\infty$,

$$ P(a,k)={N_k(a)\over\lfloor a\rfloor^k}={1\over\zeta(k)}+O(a^{1-k}\log a), $$

where the O constant depends on neither $a$ nor $k$.

P.S. The log factor in the error term can be removed when $k\ge3$.