Möbius function

The Möbius function is defined by{{sfn|Abramowitz|Stegun|1972|p=826}}

:$$\backslash mu(n)\; =$$

\begin{cases}

1 & \text{if } n = 1 \\

(-1)^k & \text{if } n \text{ is the product of } k \text{ distinct primes} \\

0 & \text{if } n \text{ is divisible by a square} > 1

\end{cases}

The Möbius function can alternatively be represented as

: $\backslash mu(n)\; =\; \backslash delta\_\{\backslash omega(n)\backslash Omega(n)\}\; \backslash lambda(n),$

where $\backslash delta\_\{ij\}$ is the Kronecker delta, $\backslash lambda(n)$ is the Liouville function,

$\backslash omega(n)$ is the number of distinct prime divisors of $n$, and $\backslash Omega(n)$ is the number of prime factors of $n$, counted with multiplicity.

Another characterization by Carl Friedrich Gauss is the sum of all primitive roots.{{Cite web |last=Weisstein |first=Eric W. |title=Möbius Function |url=https://mathworld.wolfram.com/MoebiusFunction.html |access-date=2024-10-01 |website=mathworld.wolfram.com |language=en}}

The values of $\backslash mu(n)$ for the first 50 positive numbers are

The first 50 values of the function are plotted below:

File:Moebius mu.svg

Larger values can be checked in:

• [https://www.wolframalpha.com/input/?i=MoebiusMu+123 Wolframalpha]
• [https://oeis.org/A008683/b008683.txt the b-file of OEIS]

The Dirichlet series that generates the Möbius function is the (multiplicative) inverse of the Riemann zeta function; if $s$ is a complex number with real part larger than 1 we have

:$\backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\{\backslash mu(n)\}\{n^s\}=\backslash frac\{1\}\{\backslash zeta(s)\}.$

This may be seen from its Euler product

:$\backslash frac\{1\}\{\backslash zeta(s)\}\; =\; \backslash prod\_\{p\; \backslash text\{\; prime\}\}\{\backslash left(1-\backslash frac\{1\}\{p^s\}\backslash right)\}=\; \backslash left(1-\backslash frac\{1\}\{2^s\}\backslash right)\backslash left(1-\backslash frac\{1\}\{3^s\}\backslash right)\backslash left(1-\backslash frac\{1\}\{5^s\}\backslash right)\backslash cdots$

Also:

• $\backslash sum\backslash limits\_\{n=1\}^\{\backslash infty\}\; \backslash frac$

  \mu(n)

  {n^{s}} = \frac{\zeta(s)}{\zeta(2s)};
• $\backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\{\backslash mu(n)\}\{n\}=0;$
• $\backslash sum\backslash limits\_\{n=1\}^\{\backslash infty\}\; \backslash frac\{\backslash mu(n)\backslash ln\; n\}\{n\}=-1;$
• $\backslash sum\backslash limits\_\{n=1\}^\{\backslash infty\}\; \backslash frac\{\backslash mu(n)\backslash ln^\{2\}\; n\}\{n\}=-2\backslash gamma,$ where $\backslash gamma$ is Euler's constant.

The Lambert series for the Möbius function is

:$\backslash sum\_\{n=1\}^\backslash infty\; \backslash frac\{\backslash mu(n)q^n\}\{1-q^n\}\; =\; q,$

which converges for . For prime $\backslash alpha\backslash geq\; 2$, we also have

:

Gauss{{sfn|Gauss|1986|loc=Art. 81}} proved that for a prime number $p$ the sum of its primitive roots is congruent to $\backslash mu(p-1)\; \backslash mod\; p$.

If $\backslash mathbb\{F\}\_q$ 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 $\backslash mathbb\{F\}\_q$ is given by{{sfn|Jacobson|2009|loc=§4.13}}

:$N(q,n)=\backslash frac\{1\}\{n\}\; \backslash sum\_\{d\backslash mid\; n\}\; \backslash mu(d)q^\backslash frac\{n\}\{d\}.$

The Möbius function is used in the Möbius inversion formula.

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 $\backslash log(p)$. Under second quantization, multiparticle excitations are considered; these are given by $\backslash 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$ that distinguishes fermions and bosons is then none other than the Möbius function $\backslash mu(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's attempted proof of the Riemann hypothesis.{{sfn|Bost|Connes|1995|pp=411–457}}

The Möbius function is multiplicative (i.e.,

$\backslash mu(ab)=\backslash mu(a)\backslash mu(b)$ whenever $a$ and $b$ are coprime).

Proof: Given two coprime numbers $m\; \backslash geq\; n$, we induct on $mn$. If $mn\; =\; 1$, then $\backslash mu(mn)\; =\; 1\; =\; \backslash mu(m)\; \backslash mu(n)$. Otherwise, $m\; >\; n\; \backslash geq\; 1$, so

:$$\backslash 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}

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

:$\backslash sum\_\{d\backslash mid\; n\}\; \backslash mu(d)\; =$

\begin{cases}

1 & \text{if } n=1, \\

0 & \text{if } n>1.

\end{cases}

The equality above leads to the important Möbius inversion formula and is the main reason why $\backslash mu$ is of relevance in the theory of multiplicative and arithmetic functions.

Other applications of $\backslash mu(n)$ 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:

:$\backslash mu(n)\; =\; \backslash sum\_\{\backslash stackrel\{1\backslash le\; k\; \backslash le\; n\; \}\{\; \backslash gcd(k,\backslash ,n)=1\}\}\; e^\{2\backslash pi\; i\; \backslash frac\{k\}\{n\}\},$

i.e. $\backslash mu(n)$ is the sum of the primitive $n$-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

:$\backslash sum\_\{k\; \backslash leq\; n\}\; \backslash left\backslash lfloor\{\; \backslash frac\{n\}\{k\}\; \}\backslash right\backslash rfloor\; \backslash mu(k)\; =\; 1$

and

:$\backslash sum\_\{jk\; \backslash leq\; n\}\; \backslash sin\backslash left(\; \{\; \backslash frac\{\backslash pi\; jk\}\{2\}\}\; \backslash right)\; \backslash mu(k)\; =\; 1$.

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.

The formula

:$\backslash sum\_\{d\; \backslash mid\; n\}\; \backslash mu(d)=$

\begin{cases}

1 & \text{if } n=1, \\

0 & \text{if } n>1

\end{cases}

can be written using Dirichlet convolution as:

$1\; *\; \backslash mu\; =\; \backslash varepsilon$

where $\backslash varepsilon$ is the 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

$p$ and for any $k>0$

:

while for $n=1$

:$1\; *\; \backslash mu\; (1)\; =\; \backslash sum\_\{d\; \backslash mid\; 1\}\; \backslash mu(d)=\; \backslash mu(1)\; =1\; =\backslash varepsilon(1)$.

Another way of proving this formula is by using the identity

:$\backslash mu(n)\; =\; \backslash sum\_\{\backslash stackrel\{1\backslash le\; k\; \backslash le\; n\; \}\{\backslash gcd(k,\backslash ,n)=1\}\}\; e^\{2\backslash pi\; i\; \backslash frac\{k\}\{n\}\},$

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

However it is also possible to prove this identity from first principles. First note that it is trivially true when $n=1$. Suppose then that $n>1$. Then there is a bijection between the factors $d$ of $n$ for which $\backslash mu(d)\backslash neq\; 0$ and the subsets of the set of all prime factors of $n$. 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 $|S|$ of a non-empty finite set $S$. First, if $|S|=1$, there is exactly one odd-cardinality subset of $S$, namely $S$ itself, and exactly one even-cardinality subset, namely $\backslash emptyset$. Next, if

$|S|>1$, then divide the subsets of $S$ into two subclasses depending on whether they contain or not some fixed element $x$ in $S$. There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset $\backslash \{x\backslash \}$. Also, one of these two subclasses consists of all the subsets of the set $S\backslash setminus\backslash \{x\backslash \}$, 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 $\backslash \{x\backslash \}$-containing subsets of $S$. 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.

The 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}}

$\backslash mu(n)=0$ if and only if $n$ 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 $n$ is prime, then $\backslash mu(n)=-1$, but the converse is not true. The first non prime $n$ for which $\backslash mu(n)=-1$ is $30\; =\; 2\backslash times\; 3\backslash times\; 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, ... {{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}}.

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

:$M(n)\; =\; \backslash sum\_\{k\; =\; 1\}^n\; \backslash mu(k)$

for every natural number {{mvar|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.

From the formula

:$\backslash mu(n)\; =\; \backslash sum\_\{\backslash stackrel\{1\backslash le\; k\; \backslash le\; n\; \}\{\; \backslash gcd(k,n)=1\}\}\; e^\{2\backslash pi\; i\; \backslash frac\{k\}\{n\}\},$

it follows that the Mertens function is given by

:$M(n)=\; -1+\backslash sum\_\{a\backslash in\; \backslash mathcal\{F\}\_n\}\; e^\{2\backslash pi\; i\; a\},$

where $\backslash mathcal\{F\}\_n$ is the Farey sequence of order $n$.

This formula is used in the proof of the Franel–Landau theorem.{{sfn|Edwards|1974|loc=Ch. 12.2}}

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.

Constantin Popovici{{sfn|Popovici|1963|pp=493–499}} defined a generalised Möbius function

$\backslash mu\_k=\backslash mu\; *\; \backslash cdots\; *\; \backslash mu$ to be the $k$-fold Dirichlet convolution of the Möbius function with itself. It is thus again a multiplicative function with

:$\backslash mu\_k\backslash left(p^a\backslash right)\; =\; (-1)^a\; \backslash binom\{k\}\{a\}\; \backslash$

where the binomial coefficient is taken to be zero if $a>k$. The definition may be extended to complex $k$ by reading the binomial as a polynomial in $k$.{{sfn|Sándor|Crstici|2004|p=107}}

• [https://functions.wolfram.com/NumberTheoryFunctions/MoebiusMu/ Mathematica]
• [https://maxima.sourceforge.io/docs/manual/maxima_singlepage.html#index-moebius Maxima]
• [https://www.geeksforgeeks.org/program-mobius-function/ geeksforgeeks] C++, Python3, Java, C#, PHP, JavaScript
• [https://rosettacode.org/wiki/M%C3%B6bius_function Rosetta Code]
• [https://doc.sagemath.org/html/en/reference/rings%20standard/sage/arith/misc.html?highlight=moebius Sage]

{{Div col}}

• Liouville function
• Mertens function
• Ramanujan's sum
• Sphenic number

{{Div col end}}

{{notelist-lr}}

{{Reflist}}

{{refbegin|35em}}

• {{Cite book |last1=Abramowitz |first1=Milton |title=Handbook of mathematical functions: with formulas, graphs and mathematical tables [conference under the auspices of the National science foundation and the Massachusetts institute of technology] |last2=Stegun |first2=Irene A. |date=1972 |publisher=Dover |isbn=978-0-486-61272-0 |series=Dover books on advanced mathematics |location=New York |orig-year=1964}}
• {{Cite book |last=Apostol |first=Tom M. |author-link=Tom M. Apostol |title=Introduction to analytic number theory |publisher=Springer-Verlag |year=1976 |isbn=978-0-387-90163-3 |series=Undergraduate Texts in Mathematics |location=New York; Heidelberg |mr=0434929 |zbl=0335.10001}}
• {{Cite journal |last1=Bost |first1=J.-B. |last2=Connes |first2=Alain |year=1995 |title=Hecke Algebras, Type III factors and phase transitions with spontaneous symmetry breaking in number theory |url=https://cds.cern.ch/record/283504 |journal=Selecta Mathematica |series=New Series |volume=1 |issue=3 |pages=411–457 |doi=10.1007/BF01589495 |s2cid=116418599}}
• {{Cite journal |last1=Deléglise |first1=Marc |last2=Rivat |first2=Joël |year=1996 |title=Computing the summation of the Möbius function |url=https://projecteuclid.org/euclid.em/1047565447 |journal=Experimental Mathematics |volume=5 |issue=4 |pages=291–295 |doi=10.1080/10586458.1996.10504594 |s2cid=574146}}
• {{Cite book |last=Edwards |first=Harold |author-link=Harold Edwards (mathematician) |title=Riemann's Zeta Function |date=1974 |publisher=Dover Publications |isbn=0-486-41740-9 |location=Mineola, New York}}
• {{Cite book |last=Gauss |first=Carl Friedrich |author-link=Carl Friedrich Gauss |title=Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) |publisher=Chelsea |year=1965 |isbn=0-8284-0191-8 |edition=2nd |location=New York |translator-last=Maser |translator-first=H.}}
• {{Cite book |last=Gauss |first=Carl Friedrich |author-link=Carl Friedrich Gauss |title=Disquisitiones Arithemeticae |publisher=Springer |year=1986 |isbn=0-387-96254-9 |edition=corrected 2nd |location=New York |translator-last=Clarke |translator-first=Arthur A.}}
• {{Cite book |last1=Hardy |first1=G. H. |author-link1=G. H. Hardy |url=https://archive.org/details/introductiontoth00hard |title=An Introduction to the Theory of Numbers |last2=Wright |first2=E. M. |author-link2=E. M. Wright |date=1980 |publisher=Oxford University Press |isbn=978-0-19-853171-5 |edition=5th |location=Oxford |url-access=registration |via=Internet Archive |orig-year=First edition published 1938 }}
• {{Cite journal |last=Kline |first=Jeffery |year=2020 |title=Unital Sums of the Möbius and Mertens Functions |url=https://cs.uwaterloo.ca/journals/JIS/VOL23/Kline/kline4.pdf |journal=Journal of Integer Sequences |volume=23 |issue=8 |pages=1–17}}
• {{Cite book |last=Jacobson |first=Nathan |author-link=Nathan Jacobson |title=Basic algebra I |publisher=Dover Publications |year=2009 |isbn=978-0-486-47189-1 |edition=2nd |orig-year=First published 1985}}
• {{springer| title = Möbius function

| last = Klimov | first = N. I.

| id = m/m064280

}}

• {{Cite journal |last=Möbius |first=A. F. |author-link=August Ferdinand Möbius |year=1832 |title=Über eine besondere Art von Umkehrung der Reihen |url=https://www.digizeitschriften.de/en/dms/img/?PID=GDZPPN002138654 |journal=Journal für die reine und angewandte Mathematik |volume=9 |pages=105–123}}
• {{Cite web |last=Pegg |first=Ed Jr |author-link=Ed Pegg Jr. |date=2003 |title=The Möbius function (and squarefree numbers) |url=http://www.mathpuzzle.com/MAA/02-Mobius%20Function/mathgames_11_03_03.html |website=Ed Pegg's Math Games |mode=cs2}}
• {{Cite journal |last=Popovici |first=Constantin P. |year=1963 |title=A generalization of the Möbius function |journal=Studii şi Cercetări Matematice |volume=14 |pages=493–499 |mr=0181602}}
• {{Cite book |last1=Sándor |first1=Jozsef |title=Handbook of number theory II |last2=Crstici |first2=Borislav |publisher=Kluwer Academic |year=2004 |isbn=1-4020-2546-7 |location=Dordrecht |zbl=1079.11001}}
• {{Cite book |title=Handbook of number theory I |publisher=Springer-Verlag |year=2006 |isbn=1-4020-4215-9 |editor-last=Sándor |editor-first=József |location=Dordrecht |pages=187–226 |zbl=1151.11300 |editor-last2=Mitrinović |editor-first2=Dragoslav S. |editor-last3=Crstici |editor-first3=Borislav}}

{{refend}}

• {{mathworld|urlname= MoebiusFunction|title=Möbius function}}

{{DEFAULTSORT:Mobius Function}}

Category:Multiplicative functions