Why $\sum\frac{\mu(h)\mu(k)}{hk}\gcd(h,k)=\prod\limits_{p\le x}\left(1-\frac1p\right)$, where the sum enumerates the pairs $(h,k)$ of primes below $x$

161 Views Asked by At

Why is the following equality true ?

$$\sum\limits_{h,k\atop p|hk\implies p\le X}\frac{\mu(h)\mu(k)}{h\cdot k}(h,k)=\prod\limits_{p\le X}\left(1-\frac1p\right)$$

The notation $p|hk\implies p\le X$ means that $h,k$ are composed of primes below $X$ and $(h,k)$ is the gcd of the numbers

Maybe it is related to euler-phi function ?

2

There are 2 best solutions below

2
On BEST ANSWER

Incomplete answer. It is related to Euler's $\phi$ function because $$\frac{\phi(n)}{n}=\sum\limits_{d \mid n}\frac{\mu(d)}{d} \tag{1}$$ Now, if $n=\prod\limits_{p\leq X}p$ (aka primorial) then $$\frac{\phi(n)}{n}=\prod\limits_{p\leq X}\left(1-\frac{1}{p}\right)$$ and $(1)$ becomes $$ \prod\limits_{p\leq X}\left(1-\frac{1}{p}\right)=\sum\limits_{d \space \mid \prod\limits_{p\leq X}p}\frac{\mu(d)}{d} \tag{2}$$ Now, $\mu(d)$ is multiplicative, which means that if $d=h\cdot k$ and $\gcd(h,k)=1$ then $\frac{\mu(d)}{d}=\frac{\mu(h\cdot k)}{h\cdot k}=\frac{\mu(h)\mu(k)}{h\cdot k}=\frac{\mu(h)\mu(k)}{h\cdot k}\gcd(h,k)$.

However, if $d=h\cdot k$ and $\gcd(h,k)=t>1$ then $t^2 \mid d$ and from the definition $\mu(d)=0$.

0
On

Firstly, we establish correspondence from terms in left side to that in right side.

Consider only those prime $\le X$ first,


This is just an example.

Case 1: for if {$p\mid \mid h_1$ and $p\mid\mid k_1$} $\implies$ $\frac{\mu(h_1)\mu(k_1)}{h_1\cdot k_1}(h_1,k_1) \rightarrow \frac{\mu(\frac{h_1}{p})\mu(\frac{k_1}{p})}{p \cdot \frac{h_1}{p} \cdot \frac{k_1}{p}}(h_1/p,k_1/p) $

Case 2: for if {$p\mid \mid h_2$ and $p\nmid k_2$}, $\implies$ $\frac{\mu(h_2)\mu(k_2)}{h_2\cdot k_2}(h_2,k_2) \rightarrow -\frac{\mu(\frac{h_2}{p})\mu(k_2)}{p\cdot \frac{h_2}{p} \cdot k}(h_2/p,k_2) $

For the above two cases (in fact,they are three cases by symmetry) , when $\frac{h_1}{p} = \frac{h_2}{p} $ and also $\frac{k_1}{p} = k_2$

then they contribute same value but different sign, overall they contribute $-\frac{\mu(\frac{h_2}{p})\mu(k_2)}{p\cdot \frac{h_2}{p} \cdot k_2}(h_2/p,k_2) $

To clarify, notice that even for pair $(h,k)=(\frac{h_1}{p},\frac{k_1}{p})$, it doesn't contribute $-\frac{\mu(\frac{h_1}{p})\mu(\frac{k_1}{p})}{p\cdot \frac{h_1}{p} \cdot \frac{k_1}{p}}(h_1/p,k_1/p) $, but instead $\frac{\mu(\frac{h_1}{p})\mu(\frac{k_1}{p})}{ \frac{h_1}{p} \cdot \frac{k_1}{p}}(h_1/p,k_1/p) $


Reducing the other terms further with this step, we get $$\sum\limits_{d \space \mid \prod\limits_{p\leq X}p}\frac{\mu(d)}{d} \tag{2}$$ because we can find a correspondence from terms on left side of equality to that in $(2)$.

The proof is as follows, for each h,k,

rewritten in terms of prime factorisation,

$h=\prod\limits_{p_i\leq X}\left(p_i^{\alpha (i) }\right)$

$k=\prod\limits_{p_i\leq X}\left(p_i^{\beta (i) }\right)$

where $\alpha (i),\beta (i)$ are elements in set ${ (0,1) }$.

If $\alpha (i)=1,\beta (i)=1,0$, let $g$ be number of all prime factors $h,k$ corporately have, and $p_{a_1},p_{a_2},...,p_{a_q}$ be their common factors. And $g_2$ be number of all prime factors of $h,k$ counting multiplicity.

Terms on the left side are reduced to $(-1)^{g_2-2q} \cdot \frac{1}{p_{a_1}p_{a_2}...p_{a_g}} $

This new term is contributed by all $(h,k)$ sharing in total, factors $p_{a_1},p_{a_2},...,p_{a_q}$.

Since only signs of this kind of them differ from one another, we need to consider sign only.

Now consider $(1+(-1)+(-1))^g$, in this generating function, the two $(-1)$ indicates cases which a prime factor $p_i$ is only present in either $h$ or $k$,

the (+1) in generating function refers to the case a prime factor $p_i$ present in both $h$ and $k$.

It is easy to know that there are $3^{g}$ such pair of $(h,k)$.

So repeating what is stated above, the sign depends on $(-1)^{g_2-q}$, or simply $(g_2-q)$, this quantity is also number of primes present on both $h$, $k$.

Each term originated from the generating function are in one-to-one correspondence to $(h,k)$ pair, say for $(h,k)=(p_{a_1}\cdot p_{a_2}\cdot ...\cdot p_{a_q} \cdot (r_1 $number of distinct primes)$,p_{a_1}\cdot p_{a_2}\cdot ...\cdot p_{a_q} \cdot(r_2 $number of distinct primes)),

this refers to $\underbrace{[(-1)\cdot (-1)\cdots (-1)}_{r_1\text{ times}}]\underbrace{[(-1)\cdot (-1)\cdots (-1)}_{r_2\text{ times}}]\underbrace{[(+1)\cdot (+1)\cdots (+1)}_{q\text{ times}}]$,

hence the generating function give values of $(-1)^{g}$ for this group of pairs having in total $p_{a_1},p_{a_2},...,p_{a_q},(r_1+r_2 $numbers of distinct prime factors).

It should be noted that $g=q+r_1+r_2$. Also, $g_2=g+q=2q+r_1+r_2$.


With the above preliminaries, we know that the left side of equality is just $\sum\limits_{d \space \mid \prod\limits_{p\leq X}p}\frac{\mu(d)}{d} \tag{2}$.