This site is supported by donations to The OEIS Foundation.

Möbius function

From OeisWiki
Jump to: navigation, search
The Möbius function, named after August Ferdinand Möbius (where Möbius is sometimes transliterated, without the diacritic, as Mœbius,[1] Moebius or Mobius), denoted
μ (n)
, tells whether a positive integer is squarefree, and if so, whether it has an odd or even number of prime factors. Thus
where
ω (n)
is the number of distinct prime factors of
n
,
Ω (n)
is the number of prime factors (with repetition) of
n
. Note that
n
is squarefree if and only if
Ω (n) = ω (n)
. Exploiting the fact that the value of
( − 1)k
alternates between  + 1 and  − 1, depending on the parity of
k
(see A033999 for
( − 1)n, n   ≥   0
), we can condense the definition into

and using the Iverson bracket, we can further condense the definition into

(When
Ω (n) > ω (n)
, the Iverson bracket is 0 and there is no need to evaluate
( − 1)ω (n)
, this being referred to as short-circuit evaluation.) As we no longer consider 1 a prime number (as was the case in August Ferdinand Möbius’s time[2]), the number 1 has an even number of prime factors, namely zero, and therefore
μ (1) = 1
. This simplifies certain identities as we shall see later on. For more values of the Möbius function, see A008683.

Table of Möbius function related values

Möbius function related values

n

Ω (n), ω (n)
Möbius
μ (n)


A008683
μ (n) =  − 1
: A030059
μ (n) = 0
: A013929
μ (n) = +1
: A030229
Mertens
M (n) :=
n

i  = 1
μ (i )


A002321
1 0, 0 1 1
2 1, 1 –1 0
3 1, 1 –1 –1
4 2, 1 0 –1
5 1, 1 –1 –2
6 2, 2 1 –1
7 1, 1 –1 –2
8 3, 1 0 –2
9 2, 1 0 –2
10 2, 2 1 –1
11 1, 1 –1 –2
12 3, 2 0 –2
13 1, 1 –1 –3
14 2, 2 1 –2
15 2, 2 1 –1
16 4, 1 0 –1
17 1, 1 –1 –2
18 3, 2 0 –2
19 1, 1 –1 –3
20 3, 2 0 –3
21 2, 2 1 –2
22 2, 2 1 –1
23 1, 1 –1 –2
24 4, 2 0 –2
25 2, 1 0 –2
26 2, 2 1 –1
27 3, 1 0 –1
28 3, 2 0 –1
29 1, 1 –1 –2
30 3, 3 –1 –3
31 1, 1 –1 –4
32 5, 1 0 –4

The value is available in PARI/GP as “moebius(n)” and as “MoebiusMu[n]” in Mathematica.

Asymptotic behavior

The summatory quadratfrei function is defined as

where
| μ (n) |
is the quadratfrei function, the characteristic function of squarefree numbers.

The asymptotic density of squarefree numbers corresponds to the probability that two randomly chosen integers are coprime

where
pn
is the
n
th prime number, and
ζ (s)
is the Riemann zeta function.

The asymptotic density of squarefree numbers with an odd number of prime factors is equal to the the asymptotic density of squarefree numbers with an even number of prime factors, i.e.

where
[·]
is the Iverson bracket.

The graph of the Mertens function (the Mertens function being the summatory Möbius function) seems to indicate an average negative bias for the Mertens function, which would mean that there is a bias (eerily similar to the Chebyshev bias) in favor of the squarefree numbers with an odd number of prime factors over the squarefree numbers with an even number of prime factors. The existence or not of such a bias, if small enough, would have no effect on the asymptotic behavior.

Partial sums of the Möbius function

The partial sums of the Möbius function give the Mertens function

With the exception of
n = 1
, we find that, given the set of divisors of
n
,
{d1, ..., dτ (n)}
, where
τ (n)
is the number of divisors of
n
, then[3]

Dirichlet generating function

Since the inverse of the Riemann zeta function is given by the Dirichlet series with the Möbius function as Dirichlet character (Dirichlet generating sequence)

we have that the Dirichlet generating function of the Möbius function is the inverse of the Riemann zeta function

Properties

where
ζ (s)
is the Riemann zeta function and
χprime(n)
is the characteristic function of prime numbers.
where
q(n) :=
| μ (n) |
is the quadratfrei function.

Möbius inversion

The Möbius function is used to define the Möbius transform (or Möbius inversion) of a sequence

Sequences

A030059
μ (n) =  − 1
: Numbers that are the product of an odd number of distinct primes.
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 30, 31, 37, 41, 42, 43, 47, 53, 59, 61, 66, 67, 70, 71, 73, 78, 79, 83, 89, 97, 101, 102, 103, 105, 107, 109, 110, 113, 114, 127, 130, 131, 137, 138, 139, 149, 151, 154, ...}
A013929
μ (n) = 0
: Numbers that are not squarefree. Numbers that are divisible by a square greater than 1. The complement of A005117.
{4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, 64, 68, 72, 75, 76, 80, 81, 84, 88, 90, 92, 96, 98, 99, 100, 104, 108, 112, 116, 117, 120, 121, 124, 125, 126, 128, ...}
A030229
μ (n) =  + 1
: Numbers that are the product of an even number of distinct primes.
{1, 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, 106, 111, 115, 118, 119, 122, 123, 129, 133, 134, 141, 142, 143, 145, 146, 155, 158, ...}
A008683 Moebius (or Mobius) function
μ (n)
.
{1, –1, –1, 0, –1, 1, –1, 0, 0, 1, –1, 0, –1, 1, 1, 0, –1, 0, –1, 0, 1, 1, –1, 0, 0, 1, 0, 0, –1, –1, –1, 0, 1, 1, 1, 0, –1, 1, 1, 0, –1, –1, –1, 0, 0, 1, –1, 0, 0, 0, 1, 0, –1, 0, 1, 0, 1, 1, –1, 0, –1, 1, 0, 0, 1, –1, –1, ...}
A002321 Mertens function:
1  ≤  k  ≤  n

1  ≤  k  ≤  n
μ (k)
, where
μ (k)
is Möbius function (A008683).
{1, 0, –1, –1, –2, –1, –2, –2, –2, –1, –2, –2, –3, –2, –1, –1, –2, –2, –3, –3, –2, –1, –2, –2, –2, –1, –1, –1, –2, –3, –4, –4, –3, –2, –1, –1, –2, –1, 0, 0, –1, –2, –3, –3, –3, –2, –3, –3, –3, –3, –2, –2, –3, –3, ...}

See also

Notes

  1. Typographic ligatureWikipedia.org.
  2. He lived from 1790 to 1868, according to http://www.gap-system.org/~history/Biographies/Mobius.html
  3. Thomas Koshy, Elementary Number Theory with Applications. Harcourt Academic Press (2002): p. 384, Theorem 8.17