Möbius function


Möbius function
For the rational functions defined on the complex numbers, see Möbius transformation.

The classical Möbius function μ(n) is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832.[1][2] This classical Möbius function is a special case of a more general object in combinatorics (see below).

Contents

Definition

μ(n) is defined for all positive integers n and has its values in {−1, 0, 1} depending on the factorization of n into prime factors. It is defined as follows:

  • μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • μ(n) = 0 if n is not square-free.

An equivalent way to state this is to define the two functions

ω(n), the number of distinct primes dividing the number n and
Ω(n), the number of prime factors of n, counted with multiplicities. Clearly, ω(n) ≤ Ω(n).

Then

\mu(n)=\begin{cases} (-1)^{\omega(n)}=(-1)^{\Omega(n)} &\mbox{if }\; \omega(n) = \Omega(n)\\
0&\mbox{if }\;\omega(n) < \Omega(n).\end{cases}


This implies that μ(1) = 1. (1 has an even number of prime factors, namely zero). The value of μ(0) is undefined.

Values of μ(n) for the first 25 positive numbers (sequence A008683 in OEIS):

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, ...

The first 50 values of the function are plotted below:

The 50 first values of the function

Properties and applications

The Möbius function is multiplicative (i.e. μ(ab) = μ(aμ(b) whenever a and b are coprime). The sum over all positive divisors of n of the Möbius function is zero except when n = 1:

\sum_{d | n} \mu(d) = \begin{cases}1&\mbox{ if } n=1\\
0&\mbox{ if } n>1.\end{cases}

(A consequence of the fact that every non-empty finite set has just as many subsets with odd numbers of elements as subsets with even numbers of elements - in the same way as binomial coefficients exhibit alternating entries of odd and even power which sum symmetrically.) This leads to the important Möbius inversion formula and is the main reason why μ is of relevance in the theory of multiplicative and arithmetic functions.

Other applications of μ(n) in combinatorics are connected with the use of the Pólya enumeration theorem in combinatorial groups and combinatorial enumerations.

In number theory another arithmetic function closely related to the Möbius function is the Mertens function, defined by

M(n) = \sum_{k = 1}^n \mu(k)

for every natural number n. This function is closely linked with the positions of zeroes of the Riemann zeta function. See the article on the Mertens conjecture for more information about the connection between M(n) and the Riemann hypothesis.

The ordinary generating function for the Möbius function follows from the binomial series

(I + X) − 1

applied to triangular matrices:

\sum_{n=1}^\infty \mu(n)x^n = x - \sum_{a=2}^\infty x^{a} + \sum_{a=2}^\infty \sum_{b=2}^\infty x^{ab} - \sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty x^{abc} + \sum_{a=2}^\infty \sum_{b=2}^\infty \sum_{c=2}^\infty \sum_{d=2}^\infty x^{abcd} - ...

The Lambert series for the Möbius function is:

\sum_{n=1}^\infty \frac{\mu(n)q^n}{1-q^n} = q.

The Dirichlet series that generates the Möbius function is the (multiplicative) inverse of the Riemann zeta function

\sum_{n=1}^\infty \frac{\mu(n)}{n^s}=\frac{1}{\zeta(s)}.

This is easy to see from its Euler product

\frac{1}{\zeta(s)} = \prod_{p\in \mathbb{P}}{\left(1-\frac{1}{p^{s}}\right)}= \left(1-\frac{1}{2^{s}}\right)\left(1-\frac{1}{3^{s}}\right)\left(1-\frac{1}{5^{s}}\right)\dots.

There is a formula[3] for calculating the Möbius function without knowing the factorization of its argument:

\mu(n) = \sum_{\stackrel{1\le k \le n }{ \gcd(k,\,n)=1}} e^{2\pi i \tfrac{k}{n}},

i.e. μ(n) is the sum of the primitive nth roots of unity.

From this it follows that the Mertens function is given by:

M(n)= \sum_{a\in \mathcal{F}_n} e^{2\pi i a}   where    \mathcal{F}_n   is the Farey sequence of order n.

This formula is used in the proof of the Franel-Landau theorem.[4]

Gauss[5] proved that for a prime number p the sum of its primitive roots is congruent to μ(p − 1) (mod p).

If Fq denotes the finite field of order q (where q is necessarily a prime power), then the number N of monic irreducible polynomials of degree n over Fq is given by:[6]

N(q,n)=\frac{1}{n}\sum_{d|n} \mu(d)q^{\frac{n}{d}}.

The infinite symmetric matrix starting:

 T(n,k) = \begin{bmatrix} 1&1&1&1&1&1 \\ 1&-1&1&-1&1&-1 \\ 1&1&-2&1&1&-2 \\ 1&-1&1&-1&1&-1 \\ 1&1&1&1&-4&1 \\ 1&-1&-2&-1&1&2 \end{bmatrix}

defined by the recurrence:

 T(n,1)=1,\;T(1,k)=1,\;n \geq k: -\sum\limits_{i=1}^{k-1} T(n-i,k),\;n<k: -\sum\limits_{i=1}^{n-1} T(k-i,n)

can be used to calculate the Möbius function:[7]

 \mu(n) = \frac{1}{n} \sum\limits_{k=1}^{k=n} T(n,k) \cdot e^{2 \pi i \frac{k}{n}}

Average order

The average order of the Möbius function is zero. This statement is, in fact, equivalent to the prime number theorem.[8]

μ(n) sections

μ(n) = 0 if and only if n is divisible by a square. The first numbers with this property are (sequence A013929 in OEIS):

4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63,....

If n is prime, then μ(n) = −1, but the converse is not true. The first non prime n for which μ(n) = −1 is 30 = 2·3·5. The first such numbers with three distinct prime factors (sphenic numbers) are:

30, 42, 66, 70, 78, 102, 105, 110, 114, 130, 138, 154, 165, 170, 174, 182, 186, 190, 195, 222, … (sequence A007304 in OEIS).

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, … (sequence A046387 in OEIS).

Generalization

In combinatorics, every locally finite partially ordered set (poset) is assigned an incidence algebra. One distinguished member of this algebra is that poset's "Möbius function". The classical Möbius function treated in this article is essentially equal to the Möbius function of the set of all positive integers partially ordered by divisibility. See the article on incidence algebras for the precise definition and several examples of these general Möbius functions.

Physics

The Möbius function also arises in the primon gas or free Riemann gas model of supersymmetry. In this theory, the fundamental particles or "primons" have energies log p. Under second-quantization, multiparticle excitations are considered; these are given by log n for any natural number n. This follows from the fact that the factorization of the natural numbers into primes is unique.

In the free Riemann gas, any natural number can occur, if the primons are taken as bosons. If they are taken as fermions, then the Pauli exclusion principle excludes squares. The operator (−1)F which distinguishes fermions and bosons is then none other than the Möbius function μ(n).

The free Riemann gas has a number of other interesting connections to number theory, including the fact that the partition function is the Riemann zeta function. This idea underlies Alain Connes' attempted proof of the Riemann hypothesis.[9]

See also

Notes

  1. ^ Hardy & Wright, Notes on ch. XVI: "... μ(n) occurs implicitly in the works of Euler as early as 1748, but Möbius, in 1832, was the first to investigate its properties systematically."
  2. ^ In the Disquisitiones Arithmeticae (1801) Karl Friedrich Gauss showed that the sum of the primitive roots (mod p) is μ(p − 1), (see #Properties and applications) but he didn't make further use of the function. In particular, he didn't use Möbius inversion in the Disquisitiones.
  3. ^ Hardy & Wright 1980, (16.6.4), p. 239
  4. ^ Edwards, Ch. 12.2
  5. ^ Gauss, Disquisitiones, Art. 81
  6. ^ Jacobson 2009, §4.13
  7. ^ Mats Granvik, Is this sum equal to the Möbius function? (2011)
  8. ^ Apostol 1976, §3.9
  9. ^ J.-B. Bost and Alain Connes (1995), "Hecke Algebras, Type III factors and phase transitions with spontaneous symmetry breaking in number theory", Selecta Math. (New Series), 1 411-457.

References

The Disquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

  • Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549 
  • Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8 
  • Edwards, Harold (1974), Riemann's Zeta Function, Mineola, New York: Dover, ISBN 0-486-41740-9 
  • Hardy, G. H.; Wright, E. M. (1980), An Introduction to the Theory of Numbers (Fifth edition), Oxford: Oxford University Press, ISBN 978-0198531715 
  • Jacobson, Nathan (2009) [1985], Basic algebra I (Second ed.), Dover Publications, ISBN 978-0-486-47189-1 

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Möbius inversion formula — In mathematics, the classic Möbius inversion formula was introduced into number theory during the 19th century by August Ferdinand Möbius. Other Möbius inversion formulas are obtained when different local finite partially ordered sets replace the …   Wikipedia

  • Möbius transformation — Not to be confused with Möbius transform or Möbius function. In geometry, a Möbius transformation of the plane is a rational function of the form of one complex variable z; here the coefficients a, b, c, d are complex numbers satisfying ad − …   Wikipedia

  • Möbius transform — The Möbius transform should not be confused with Möbius transformations. In mathematics, the Möbius transform Tf of a function f defined on the positive integers is defined by where μ is the classic Möbius function. In more common usage, the… …   Wikipedia

  • Mobius Artists Group — The Mobius Artists Group is an interdisciplinary group of artists, founded in 1977 by Marilyn Arsem in Boston, Massachusetts as Mobius Theater. It is known for incorporating a wide range of visual, performing and media arts into live performance …   Wikipedia

  • Arithmetic function — In number theory, an arithmetic (or arithmetical) function is a real or complex valued function ƒ(n) defined on the set of natural numbers (i.e. positive integers) that expresses some arithmetical property of n. [1] An example of an arithmetic… …   Wikipedia

  • Mertens function — to n=10,000 Mertens function to n=10,000,000 In …   Wikipedia

  • August Ferdinand Möbius — Infobox Scientist box width = 300px name = August Möbius image size = 300px caption = August Ferdinand Möbius (1790 ndash;1868) birth date = November 17, 1790 birth place = Schulpforta, Saxony Anhalt, Germany death date = September 26, 1868 death …   Wikipedia

  • Multiplicative function — Outside number theory, the term multiplicative function is usually used for completely multiplicative functions. This article discusses number theoretic multiplicative functions. In number theory, a multiplicative function is an arithmetic… …   Wikipedia

  • Proofs involving the totient function — This page provides proofs for identities involving the totient function varphi(k) and the Möbius function mu(k).um of integers relatively prime to and less than or equal to n Claim::sum {1le kle n atop {gcd(k,n)=1 k = frac{1}{2} , varphi(n) ,… …   Wikipedia

  • Fonction De Möbius — Pour les articles homonymes, voir Moebius. August Ferdinand Möbius est le premier à étudier systématiquement la fonction qui por …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.