HOME

TheInfoList



OR:

The Möbius function is a multiplicative function in
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and
analytic Generally speaking, analytic (from el, ἀναλυτικός, ''analytikos'') refers to the "having the ability to analyze" or "division into elements or principles". Analytic or analytical can also have the following meanings: Chemistry * ...
number theory and most often appears as part of its namesake the Möbius inversion formula. Following work of Gian-Carlo Rota in the 1960s, generalizations of the Möbius function were introduced into combinatorics, and are similarly denoted .


Definition

For any positive
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
, define as the sum of the primitive th roots of unity. It has values in depending on the factorization of into
prime factor A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s: * if is a square-free positive integer with an
even Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname) * Even (people), an ethnic group from Siberia and Russian Far East **Even language, a language spoken by the Evens * Odd and Even, a solitaire game wh ...
number of prime factors. * if is a square-free positive integer with an odd number of prime factors. * if has a squared prime factor. The Möbius function can alternatively be represented as : \mu(n) = \delta_ \lambda(n), where is the
Kronecker delta In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise: \delta_ = \begin 0 &\text i \neq j, \\ 1 & ...
, is the Liouville function, is the number of distinct prime divisors of , and is the number of prime factors of , counted with multiplicity.


Values

The values of for the first 50 positive numbers are The first 50 values of the function are plotted below: Larger values can be checked in:
Wolframalpha

the b-file of OEIS


Applications


Mathematical series

The
Dirichlet series In mathematics, a Dirichlet series is any series of the form \sum_^\infty \frac, where ''s'' is complex, and a_n is a complex sequence. It is a special case of general Dirichlet series. Dirichlet series play a variety of important roles in analy ...
that generates the Möbius function is the (multiplicative) inverse of the
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
; if is a complex number with real part larger than 1 we have :\sum_^\infty \frac=\frac. This may be seen from its
Euler product In number theory, an Euler product is an expansion of a Dirichlet series into an infinite product indexed by prime numbers. The original such product was given for the sum of all positive integers raised to a certain power as proven by Leonhard Eu ...
:\frac = \prod_= \left(1-\frac\right)\left(1-\frac\right)\left(1-\frac\right)\cdots Also: * \sum\limits_^ \frac = \frac * \sum\limits_^ \frac=-1. * \sum\limits_^ \frac=-2\gamma, where \gamma -
Euler's constant Euler's constant (sometimes also called the Euler–Mascheroni constant) is a mathematical constant usually denoted by the lowercase Greek letter gamma (). It is defined as the limiting difference between the harmonic series and the natural ...
. The Lambert series for the Möbius function is: :\sum_^\infty \frac = q, which converges for . For prime , we also have :\sum_^\infty \frac = \sum_ q^, , q, < 1.


Algebraic number theory

Gauss proved that for a prime number the sum of its primitive roots is congruent to . If denotes the
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
of order (where is necessarily a prime power), then the number of monic irreducible polynomials of degree over is given by: :N(q,n)=\frac \sum_ \mu(d)q^\frac.


Physics

The Möbius function also arises in the
primon gas In mathematical physics, the primon gas or free Riemann gas is a toy model illustrating in a simple way some correspondences between number theory and ideas in quantum field theory and dynamical systems. It is a quantum field theory of a set of ...
or
free Riemann gas In mathematical physics, the primon gas or free Riemann gas is a toy model illustrating in a simple way some correspondences between number theory and ideas in quantum field theory and dynamical systems. It is a quantum field theory of a set of ...
model of
supersymmetry In a supersymmetric theory the equations for force and the equations for matter are identical. In theoretical and mathematical physics, any theory with this property has the principle of supersymmetry (SUSY). Dozens of supersymmetric theories ...
. In this theory, the fundamental particles or "primons" have energies . Under
second quantization Second quantization, also referred to as occupation number representation, is a formalism used to describe and analyze quantum many-body systems. In quantum field theory, it is known as canonical quantization, in which the fields (typically as t ...
, multiparticle excitations are considered; these are given by for any natural number . 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
boson In particle physics, a boson ( ) is a subatomic particle whose spin quantum number has an integer value (0,1,2 ...). Bosons form one of the two fundamental classes of subatomic particle, the other being fermions, which have odd half-integer spi ...
s. If they are taken as
fermion In particle physics, a fermion is a particle that follows Fermi–Dirac statistics. Generally, it has a half-odd-integer spin: spin , spin , etc. In addition, these particles obey the Pauli exclusion principle. Fermions include all quarks and ...
s, then the
Pauli exclusion principle In quantum mechanics, the Pauli exclusion principle states that two or more identical particles with half-integer spins (i.e. fermions) cannot occupy the same quantum state within a quantum system simultaneously. This principle was formula ...
excludes squares. The operator that distinguishes fermions and bosons is then none other than the Möbius function . 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 The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
. This idea underlies Alain Connes's attempted proof of the
Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in p ...
.


Properties

The Möbius function is multiplicative (i.e., ) whenever and are
coprime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
. The sum of the Möbius function over all positive divisors of (including itself and 1) is zero except when : :\sum_ \mu(d) = \begin 1 & \text n=1, \\ 0 & \text n>1. \end The equality above 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 in combinatorics are connected with the use of the Pólya enumeration theorem in combinatorial groups and combinatorial enumerations. There is a formula for calculating the Möbius function without directly knowing the factorization of its argument: :\mu(n) = \sum_ e^, i.e. is the sum of the primitive -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 :\sum_ \left\lfloor\right\rfloor \mu(k) = 1 and :\sum_ \cos\left( \right) \mu(k) = 1. The first of these is a classical result while the second was published in 2020. Similar identities hold for the Mertens function.


Proof of the formula for

Using :\mu(n) = \sum_ e^, the formula :\sum_ \mu(d)=\begin 1 & \text n=1, \\ 0 & \text n>1 \end can be seen as a consequence of the fact that the th roots of unity sum to 0, since each th root of unity is a primitive th root of unity for exactly one divisor of . However it is also possible to prove this identity from first principles. First note that it is trivially true when . Suppose then that . Then there is a bijection between the factors of for which and the subsets of the set of all prime factors of . 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 of a non-empty finite set . First, if , there is exactly one odd-cardinality subset of , namely itself, and exactly one even-cardinality subset, namely . Next, if , then divide the subsets of into two subclasses depending on whether they contain or not some fixed element in . There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset . Also, one of these two subclasses consists of all the subsets of the set , 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 -containing subsets of . 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 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 In mathematics, the prime number theorem (PNT) describes the asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by precisely quantifying t ...
.


sections

if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
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, ... . If is prime, then , but the converse is not true. The first non prime for which is . 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, ... . 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, ... .


Mertens function

In number theory another arithmetic function closely related to the Möbius function is the Mertens function, defined by :M(n) = \sum_^n \mu(k) for every natural number . This function is closely linked with the positions of zeroes of the
Riemann zeta function The Riemann zeta function or Euler–Riemann zeta function, denoted by the Greek letter (zeta), is a mathematical function of a complex variable defined as \zeta(s) = \sum_^\infty \frac = \frac + \frac + \frac + \cdots for \operatorname(s) > ...
. See the article on the
Mertens conjecture In mathematics, the Mertens conjecture is the statement that the Mertens function M(n) is bounded by \pm\sqrt. Although now disproven, it had been shown to imply the Riemann hypothesis. It was conjectured by Thomas Joannes Stieltjes, in an 1 ...
for more information about the connection between and the
Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in p ...
. From the formula :\mu(n) = \sum_ e^, it follows that the Mertens function is given by: :M(n)= -1+\sum_ e^, where is the Farey sequence of order . This formula is used in the proof of the Franel–Landau theorem.


Generalizations


Incidence algebras

In
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, every locally finite
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
(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 In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
. See the article on incidence algebras for the precise definition and several examples of these general Möbius functions.


Popovici's function

Constantin Popovici defined a generalised Möbius function to be the -fold Dirichlet convolution of the Möbius function with itself. It is thus again a multiplicative function with : \mu_k\left(p^a\right) = (-1)^a \binom \ where the binomial coefficient is taken to be zero if . The definition may be extended to complex by reading the binomial as a polynomial in .


Implementations


WOLFRAM MATHEMATICA has function MoebiusMu



geeksforgeeks
has C++, Python3, Java, C#, PHP, Javascript implementations
Rosetta Code



See also

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


Notes


Citations


Sources

* * * * * * * * * * * * * * *


External links

* {{DEFAULTSORT:Mobius Function Multiplicative functions