Editing Möbius function (section)

== Properties ==
The Möbius function is [[multiplicative function|multiplicative]] (i.e., 
<math>\mu(ab)=\mu(a)\mu(b)</math> whenever <math>a</math> and <math>b</math> are [[coprime]]).
<blockquote>'''Proof''': Given two coprime numbers <math>m \geq n</math>, we induct on <math>mn</math>. If <math>mn = 1</math>, then <math>\mu(mn) = 1 = \mu(m) \mu(n)</math>. Otherwise, <math>m > n \geq 1</math>, so

:<math display="block">\begin{align}
0 &= \sum_{d | mn} \mu(d) \\
&= \mu(mn) +  \sum_{d | mn ; d < mn} \mu(d) \\
&\stackrel{\text{induction}}{=} \mu(mn) - \mu(m)\mu(n) + \sum_{d| m; d' | n} \mu(d)\mu(d') \\
&= \mu(mn) - \mu(m)\mu(n) + \sum_{d| m} \mu(d)\sum_{d' | n}\mu(d') \\
&= \mu(mn) - \mu(m)\mu(n) + 0
\end{align}
 </math>

</blockquote>
The sum of the Möbius function over all positive divisors of <math>n</math> (including <math>n</math> itself and 1) is zero except when <math>n=1</math>:

:<math>\sum_{d\mid n} \mu(d) = 
\begin{cases}
1 & \text{if } n=1, \\
0 & \text{if } n>1.
\end{cases}</math>

The equality above leads to the important [[Möbius inversion formula]] and is the main reason why <math>\mu</math> is of relevance in the theory of multiplicative and arithmetic functions.

Other applications of <math>\mu(n)</math> in combinatorics are connected with the use of the [[Pólya enumeration theorem]] in combinatorial groups and combinatorial enumerations.

There is a formula{{sfn|Hardy|Wright|1980| loc=(16.6.4), p. 239}} for calculating the Möbius function without directly knowing the factorization of its argument:

:<math>\mu(n) = \sum_{\stackrel{1\le k \le n }{ \gcd(k,\,n)=1}} e^{2\pi i \frac{k}{n}},</math>

i.e. <math>\mu(n)</math> is the sum of the primitive <math>n</math>-th [[roots of unity]]. (However, the computational complexity of this definition is at least the same as that of the Euler product definition.)

Other identities satisfied by the Möbius function include

:<math>\sum_{k \leq n} \left\lfloor{ \frac{n}{k} }\right\rfloor \mu(k) = 1</math>

and

:<math>\sum_{jk \leq n} \sin\left( { \frac{\pi jk}{2}} \right) \mu(k) = 1</math>.

The first of these is a classical result while the second was published in 2020.{{sfn|Apostol|1976}}{{sfn|Kline|2020}} Similar identities hold for the [[Mertens function]].

=== Proof of the formula for the sum of <math>\mu</math> over divisors ===
The formula

:<math>\sum_{d \mid n} \mu(d)=
\begin{cases}
1 & \text{if } n=1, \\
0 & \text{if } n>1
\end{cases}</math>

can be written using [[Dirichlet convolution]] as:
<math>1 * \mu = \varepsilon</math>
where <math>\varepsilon</math> is the [[Dirichlet convolution#Properties|identity under the convolution]].

One way of proving this formula is by noting that the Dirichlet convolution of two [[multiplicative functions]] is again multiplicative. Thus it suffices to prove the formula for powers of primes. Indeed, for any prime 
<math>p</math> and for any <math>k>0</math>
:<math>1 * \mu (p^k) = \sum_{d \mid p^k} \mu(d)= \mu(1)+\mu(p)+\sum_{1<m<=k}\mu(p^m)=1-1+\sum0=0=\varepsilon(p^k)</math>,
while for <math>n=1</math>
:<math>1 * \mu (1) = \sum_{d \mid 1} \mu(d)= \mu(1) =1 =\varepsilon(1)</math>.

====Other proofs====
Another way of proving this formula is by using the identity

:<math>\mu(n) = \sum_{\stackrel{1\le k \le n }{\gcd(k,\,n)=1}} e^{2\pi i \frac{k}{n}},</math>

The formula above is then a consequence of the fact that the <math>n</math>th roots of unity sum to 0, since each <math>n</math>th root of unity is a primitive <math>d</math>th root of unity for exactly one divisor <math>d</math> of <math>n</math>.

However it is also possible to prove this identity from first principles. First note that it is trivially true when <math>n=1</math>. Suppose then that <math>n>1</math>. Then there is a bijection between the factors <math>d</math> of <math>n</math> for which <math>\mu(d)\neq 0</math> and the subsets of the set of all prime factors of <math>n</math>. The asserted result follows from the fact that every non-empty finite set has an equal number of odd- and even-cardinality subsets.

This last fact can be shown easily by induction on the cardinality <math>|S|</math> of a non-empty finite set <math>S</math>. First, if <math>|S|=1</math>, there is exactly one odd-cardinality subset of <math>S</math>, namely <math>S</math> itself, and exactly one even-cardinality subset, namely <math>\emptyset</math>. Next, if 
<math>|S|>1</math>, then divide the subsets of <math>S</math> into two subclasses depending on whether they contain or not some fixed element <math>x</math> in <math>S</math>. There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset <math>\{x\}</math>. Also, one of these two subclasses consists of all the subsets of the set <math>S\setminus\{x\}</math>, and therefore, by the induction hypothesis, has an equal number of odd- and even-cardinality subsets. These subsets in turn correspond bijectively to the even- and odd-cardinality <math>\{x\}</math>-containing subsets of <math>S</math>. The inductive step follows directly from these two bijections.

A related result is that the binomial coefficients exhibit alternating entries of odd and even power which sum symmetrically.

===Average order===
The [[average order of an arithmetic function|mean value (in the sense of average orders)]] of the Möbius function is zero. This statement is, in fact, equivalent to the [[prime number theorem]].{{sfn|Apostol|1976|loc=§3.9}}

===<math>\mu(n)</math> sections===
<math>\mu(n)=0</math> [[if and only if]] <math>n</math> is divisible by the square of a prime. The first numbers with this property are

:4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, ... {{OEIS|id=A013929}}.

If <math>n</math> is prime, then <math>\mu(n)=-1</math>, but the converse is not true. The first non prime <math>n</math> for which <math>\mu(n)=-1</math> is <math> 30 = 2\times 3\times 5</math>. The first such numbers with three distinct prime factors ([[sphenic number]]s) are

:30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, ... {{OEIS|id=A007304}}.

and the first such numbers with 5 distinct prime factors are

:2310, 2730, 3570, 3990, 4290, 4830, 5610, 6006, 6090, 6270, 6510, 6630, 7410, 7590, 7770, 7854, 8610, 8778, 8970, 9030, 9282, 9570, 9690, ... {{OEIS|id=A046387}}.