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
    That describes the "standard" number-theoretic Moebius function, but not the combinatorial one. How does he define $\mu(k,n)$ for arbitrary $k$ and $n$, then?2011-03-04
  • 0
    @Arturo, the author states (working over the set $X_n$ of the first $n$ positive integers) 'our goal is to compute $\mu(1,n)$, from this we can compute $\mu(a,b)$ for any integers $a,b\in X_n$ by $\mu(a,b)=\mu(1,\frac{b}{a})$. Maybe my tag is wrong. Are you referring to the combinatorial one where $\mu(A,B)=(-1)^{|B|-|A|}$, for sets $A$ and $B$, or something else?2011-03-04
  • 0
    @Hobbie: I'm refering to the Moebius function of posets which I define in my answeer below.2011-03-04
  • 0
    @Arturo, sorry for the confusion, I'm still trying to get a hold on the nature of these functions. I guess I should remove the combinatorics tag?2011-03-04
  • 0
    @Hobbie: Actually, it looks like they agree in this situation. I didn't work out the non-squarefree case (it's getting late), but I'm confident it will work.2011-03-04
  • 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
    Thanks for the fast answer. For the very first part where $k\nmid n$, do we just take $\mu(1,\frac{n}{k})=0$ since $n/k$ is not an integer?2011-03-04
  • 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$.