Need help with Möbius function

167 Views Asked by At

Suppose I need to find total subset of numbers of length $K$ in range $1$ to $N$ such that their $\gcd$ is $g$. How can I utilize Möbius function for that.

So approach is we can choose $K$ numbers out of $N/g$ numbers such that their gcd is multiple of $g$. But now we have to remove sets which have other multiples other than $g$.

1

There are 1 best solutions below

1
On BEST ANSWER

Informal solution

There are $\binom{\lfloor N/g\rfloor}k$ subsets of $\{g,2g,3g,\dots\}\cap \{1,2,\dots,N\}$ of size $k$. These all have a gcd which is a multiple of $g$. From these, we must subtract the sets whose gcd strictly more than $g$. For each prime such that $pg\le N$, we therefore must subtract $\binom{\lfloor N/(pg)\rfloor}k$. However, sets whose gcd is a multiple of $pqg$ for distinct primes $p\neq q$ have been subtracted twice, so these must be added back in, and so on.

The result is $$ \sum_{d=1}^{\lfloor N/(gk)\rfloor}\mu(d)\binom{\lfloor N/(dg)\rfloor}k.\tag{$*$} $$


Formal solution

Let $f(n)$ be the number of subsets of size $k$ whose gcd is equal to $n$. Let $h(n)$ be the number of subsets whose gcd is a multiple of $n$. Then $$ h(n) = \sum_{n|k}f(k) $$ This is not quite the setup we need to apply Mobius inversion; we want $k$ to range over the divisors of $n$, but here it ranges over multiples of $n$. To fix this, note that $f(k)$ is zero unless $k$ is a divisor of $N!$. Therefore, we can reindex the summation by $j:=N!/k$, and we get $$ h(n)=\sum_{j\mid (N!/n)}f(N!/j) $$ Now, substituting $N!/n$ for $n$, we get $$ h(N!/n)=\sum_{j|n}f(N!/j) $$ We can now apply Mobius inversion to $h(N!/n)$ and $f(N!/n)$, and we get $$ f(N!/n)=\sum_{j|n}\mu(j)h(jN!/n) $$ Finally, substituting $N!/n$ for $n$, we get $$ f(n)=\sum_{j|(N!/n)}\mu(j)h(jn) $$ This, coupled with $h(n)=\binom{\lfloor N/n\rfloor}{k}$, proves $(*)$.