3
$\begingroup$

Why does $\mu(k,n)=\mu(1,\frac{n}{k})$, where $\mu$ is the Möbius function and $k$ and $n$ are integers.

I'm reading about the Möbius function on a poset of integers ordered by divisibility. The author uses this fact several times, but I don't see why it's so obvious. What exactly is this equality saying? Thanks.

Edit: The author computes $\mu(1,n)$ as $\mu(1,n)=1$ if $n=1$, $\mu(1,n)=(-1)^k$ if $n$ is the product of $k$ distinct primes, and $\mu(1,n)=0$ otherwise.

  • 0
    @Arturo, interesting, thanks for your efforts. It's starting to make more sense.2011-03-04

2 Answers 2

5

Note. This assumed that both $\mu$s were the Moebius function on a poset. Now the OP notes that $\mu(1,n)$ is being defined by $\mu(n)$, the usual Moebius function on the natural numbers. I have vague memories of having dealt with the poset Moebius function before, but I don't think I ever saw that for the natural numbers ordered by divisibility, the two agree; see below.

The Moebius function on a poset is defined by: $\mu(x,y) = \left\{\begin{array}{ll} 1 & \mbox{if $x=y$,}\\ -\sum\limits_{x\leq z\lt y} \mu(x,z) & \mbox{if $x\lt y$,}\\ 0 & \mbox{otherwise.} \end{array}\right.$ Here you are ordering the natural numbers by divisibility (you say integers, but they don't form a poset since divisibility is not antisymmetric, so either you are taking equivalence classes, or are workng on the naturals).

If $k$ does not divide $n$, then both sides are $0$ and there is nothing to do. (I'm assuming that for non-integer rationals $q$, $\mu(1,q)$ is defined to be $0$ by fiat). So assume that $k|n$. Then writing $n=kd$, the assertion is equivalent to showing that for all natural numbers $k$ and $d$, $\mu(k,kd) = \mu(1,d).$

Fix $k$. We prove this by strong induction on $d$. It holds if $d=1$, since $\mu(k,k) = 1 =\mu(1,1)$.

Assume the result holds for all $d$, $1\leq d \lt n$, and you want to show that it is true for $d=n$. We have: \begin{align*} \mu(k,kn) &= -\sum_{j=1}^{n-1}\mu(k,kj)\\ &= -\sum_{j=1}^{n-1}\mu(1,j) &\qquad&\mbox{(by the induction hypothesis)}\\ &= \mu(1,n). \end{align*} Thus, $\mu(k,kn) = \mu(1,n)$ for all positive integers $n$ (on the positive integers ordered by divisibility).


Does the above definition agree with the usual Moebius function for integers, described in the original post? Yes.

First, consider the case in which $d$ is squarefree. $\mu(1,1)=1$ by the definition given. Assume that if $d$ is a product of fewer than $k$ distinct primes, then $\mu(1,d) = (-1)^r$, where $r$ is the number of distinct primes that divide $d$. If $d$ is the product of exactly $k$ distinct primes, then we have \begin{align*} \mu(1,d) &= -\sum_{m|d, m\neq d} \mu(1,m)\\ &= -\left(1 - \binom{k}{1} + \binom{k}{2} -\binom{k}{3}+\cdots+(-1)^{k-1}\binom{k}{k-1}\right)\\ &= -\left( (1-1)^k - \binom{k}{k}(-1)^k\right)&&\mbox{(binomial expansion)}\\ &= -(-1)^{k+1} = (-1)^{k+2} = (-1)^k. \end{align*} The second equality comes from the following consideration: the value of $\mu(1,m)$ on the proper divisors of $d$ only depends on the number of primes that divide them; there are $\binom{k}{1}$ divisors that are prime, $\binom{k}{2}$ that are products of two primes, etc.

So $\mu(1,d) = \mu(d)$ for the squarefree integers $d$.

Now assume that $n$ is not square free, not equal to $1$. If $d=p^2$ is the square of a prime, then $\mu(1,d) = -\mu(1,1) -\mu(1,p) = -1+1 = 0.$ Now assume that for any $m\lt d$, $\mu(1,m)=\mu(m)$ (the usual arithmetic Moebius function), and that $d$ is divisible by the square of a prime $p$. If $m$ is a proper divisors of $\frac{d}{p^2}$, then $\mu(1,p^2m)=0$ by induction. So we only need to worry about the divisors of $\frac{d}{p}$. And we have: $\mu(1,d) = -\sum_{m|\frac{d}{p}}\mu(1,m) = \left(-\sum_{m|\frac{d}{p},m\neq\frac{d}{p}} \mu(1,m)\right) - \mu\left(1,\frac{d}{p}\right) = \mu\left(1,\frac{d}{p}\right) - \mu\left(1,\frac{d}{p}\right) = 0.$ So the two definitions agree on the natural numbers ordered by divisibility.

  • 0
    @Hobbie: I would assume so, but I haven't worked out yet if this definition agrees with the usual Moebius one for $\mu(1,n)$.2011-03-04
3

I think the more conceptual way to see that this holds is that the Möbius function $\mu(x,y)$ only depends on the structure of the poset $[x,y] = \{ z \; : \; x \leq z \leq y\}$.

So it suffices to show that when the natural numbers are ordered by divisibility and k divides n, then the posets $[k,n]$ and $[1,\frac n k]$ are isomorphic. To see this, use the isomorphism $z \mapsto \frac z k$.