Mobius function

Mobius function $\mu (n)$ ${\ displaystyle \ mu (n)}$ $\ mu (n)$ - The multiplicative arithmetic function used in number theory and combinatorics is named after the German mathematician Mobius , who first considered it in 1831 .

Content

Definition

$\mu (n)$ ${\ displaystyle \ mu (n)}$ defined for all natural numbers $n$ ${\ displaystyle n}$ and takes values ${-1,\;0,\;1}$ ${\ displaystyle {-1, \; 0, \; 1}}$ depending on the nature of the decomposition of the number $n$ ${\ displaystyle n}$ to simple factors:

$\mu (n)=1$ ${\ displaystyle \ mu (n) = 1}$ , if a $n$ ${\ displaystyle n}$ free of squares (i.e. no prime is divisible by square) and decomposition $n$ ${\ displaystyle n}$ prime factors consists of an even number of factors;
$\mu (n)=-1$ ${\ displaystyle \ mu (n) = - 1}$ , if a $n$ ${\ displaystyle n}$ square free and decomposition $n$ ${\ displaystyle n}$ prime factors consists of an odd number of factors;
$\mu (n)=0$ ${\ displaystyle \ mu (n) = 0}$ , if a $n$ ${\ displaystyle n}$ not free from squares.

By definition, they also $\mu (1)=1$ ${\ displaystyle \ mu (1) = 1}$ .

Properties and Applications

The Mobius function is multiplicative: for any coprime numbers $a$ ${\ displaystyle a}$ and $b$ ${\ displaystyle b}$ equality holds $\mu (ab)=\mu (a)\mu (b)$ ${\ displaystyle \ mu (ab) = \ mu (a) \ mu (b)}$ .

The sum of the values of the Mobius function for all divisors of an integer $n$ ${\ displaystyle n}$ not equal to unity is equal to zero

\sum _{d|n}\mu (d)={\begin{cases}1,&n=1,\\0,&n>1.\end{cases}}

{\ displaystyle \ sum _ {d | n} \ mu (d) = {\ begin {cases} 1, & n = 1, \\ 0, & n> 1. \ end {cases}}}

This, in particular, follows from the fact that for any nonempty finite set, the number of different subsets consisting of an odd number of elements is equal to the number of different subsets consisting of an even number of elements, a fact also used in the proof of the Mobius formula for inversion .

$\sum \limits _{k=1}^{n}\mu (k)\left[{\frac {n}{k}}\right]=1.$ ${\ displaystyle \ sum \ limits _ {k = 1} ^ {n} \ mu (k) \ left [{\ frac {n} {k}} \ right] = 1.}$

$\sum \limits _{k=1}^{\infty }{\frac {\mu (kn)}{k}}=0,$ ${\ displaystyle \ sum \ limits _ {k = 1} ^ {\ infty} {\ frac {\ mu (kn)} {k}} = 0,}$ where n is a positive integer.

$\sum \limits _{k=1}^{\infty }{\frac {\mu (k)\ln k}{k}}=-1.$ ${\ displaystyle \ sum \ limits _ {k = 1} ^ {\ infty} {\ frac {\ mu (k) \ ln k} {k}} = - 1.}$

The Mobius function is closely related to the Riemann zeta function . So, through the Mobius function, the coefficients of the Dirichlet series of a function that is multiplicatively inverse for the Riemann zeta function are expressed

\sum \limits _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}={\frac {1}{\zeta (s)}}

{\ displaystyle \ sum \ limits _ {n = 1} ^ {\ infty} {\ frac {\ mu (n)} {n ^ {s}}} = {\ frac {1} {\ zeta (s)} }}

.

The series absolutely converges at ${\rm {Re}}\,s>1$ ${\ displaystyle {\ rm {Re}} \, s> 1}$ on the line ${\rm {Re}}\,s=1$ ${\ displaystyle {\ rm {Re}} \, s = 1}$ converges conditionally in the region $1/2<{\rm {Re}}\,s<1$ ${\ displaystyle 1/2 <{\ rm {Re}} \, s <1}$ the statement on conditional convergence of the series is equivalent to the Riemann hypothesis , ${\rm {Re}}\,s<1/2$ ${\ displaystyle {\ rm {Re}} \, s <1/2}$ the series obviously does not converge, even conditionally.

At ${\rm {Re}}\,s>1$ ${\ displaystyle {\ rm {Re}} \, s> 1}$ the following formula is also valid:

\sum \limits _{n=1}^{\infty }{\frac {|\mu (n)|}{n^{s}}}={\frac {\zeta (s)}{\zeta (2s)}}

{\ displaystyle \ sum \ limits _ {n = 1} ^ {\ infty} {\ frac {| \ mu (n) |} {n ^ {s}}} = {\ frac {\ zeta (s)} { \ zeta (2s)}}}

$\sum \limits _{n=1}^{\infty }{\frac {\mu (pn)}{n^{s}}}={\frac {p^{s}}{(1-p^{s})\zeta (s)}},$ ${\ displaystyle \ sum \ limits _ {n = 1} ^ {\ infty} {\ frac {\ mu (pn)} {n ^ {s}}} = {\ frac {p ^ {s}} {(1 -p ^ {s}) \ zeta (s)}},}$ where p is a prime number.

The Mobius function is related to the Mertens function , which is also closely related to the problem of the zeros of the Riemann zeta function

M(n)=\sum _{k=1}^{n}\mu (k).

{\ displaystyle M (n) = \ sum _ {k = 1} ^ {n} \ mu (k).}

The asymptotic relations are valid:

{\frac {1}{x}}\sum \limits _{n\leq x}\mu (n)=o(1)

{\ displaystyle {\ frac {1} {x}} \ sum \ limits _ {n \ leq x} \ mu (n) = o (1)}

at

x\rightarrow \infty

{\ displaystyle x \ rightarrow \ infty}

{\frac {1}{x}}\sum \limits _{n\leq x}|\mu (n)|={\frac {1}{\zeta (2)}}+O({\frac {1}{\sqrt {x}}})

{\ displaystyle {\ frac {1} {x}} \ sum \ limits _ {n \ leq x} | \ mu (n) | = {\ frac {1} {\ zeta (2)}} + O ({ \ frac {1} {\ sqrt {x}}})}

,

from which it follows that there is an asymptotic density of the distribution of values of the Mobius function. The linear density of the set of its zeros is $1-1/\zeta (2)=0,3920729$ ${\ displaystyle 1-1 / \ zeta (2) = 0.3920729}$ , and the density of many units (or minus units) $1/2\zeta (2)=0,30396355$ ${\ displaystyle 1/2 \ zeta (2) = 0.30396355}$ . Probabilistic approaches to the study of the Mobius function are based on this fact.

Mobius appeal

The first formula of the Mobius appeal

For arithmetic functions $f$ ${\ displaystyle f}$ and $g$ ${\ displaystyle g}$ ,

g(n)=\sum _{d\,\mid \,n}f(d)

{\ displaystyle g (n) = \ sum _ {d \, \ mid \, n} f (d)}

if and only if

f(n)=\sum _{d\,\mid \,n}\mu (d)g(n/d)

{\ displaystyle f (n) = \ sum _ {d \, \ mid \, n} \ mu (d) g (n / d)}

.

The second formula of the Mobius

For real-valued functions $f(x)$ ${\ displaystyle f (x)}$ and $g(x)$ ${\ displaystyle g (x)}$ defined at $x\geqslant 1$ ${\ displaystyle x \ geqslant 1}$ ,

g(x)=\sum _{n\leqslant x}f\left({\frac {x}{n}}\right)

{\ displaystyle g (x) = \ sum _ {n \ leqslant x} f \ left ({\ frac {x} {n}} \ right)}

if and only if

f(x)=\sum _{n\leqslant x}\mu (n)g\left({\frac {x}{n}}\right)

{\ displaystyle f (x) = \ sum _ {n \ leqslant x} \ mu (n) g \ left ({\ frac {x} {n}} \ right)}

.

Here is the amount $\sum _{n\leqslant x}$ ${\ displaystyle \ sum _ {n \ leqslant x}}$ interpreted as $\sum _{n=1}^{\lfloor x\rfloor }$ ${\ displaystyle \ sum _ {n = 1} ^ {\ lfloor x \ rfloor}}$ .

Generalized Mobius function

Despite the seeming unnaturalness of the definition of a Mobius function, its nature can become clear when considering a class of functions with similar invertibility properties introduced on arbitrary partially ordered sets .

Let some partially ordered set be given with a comparison relation $\prec$ ${\ displaystyle \ prec}$ . We assume that $a\preccurlyeq b\iff a\prec b\lor a=b$ ${\ displaystyle a \ preccurlyeq b \ iff a \ prec b \ lor a = b}$ .

Definition

The generalized Mobius function is recursively determined by the relation.

{\mu _{A}^{*}}(a,b)={\begin{cases}1,&a=b\\-\sum \limits _{a\preccurlyeq z\prec b}{{\mu _{A}^{*}}(a,z)},&a\prec b\\0,&b\prec a\end{cases}}

{\ displaystyle {\ mu _ {A} ^ {*}} (a, b) = {\ begin {cases} 1, & a = b \\ - \ sum \ limits _ {a \ preccurlyeq z \ prec b} { {\ mu _ {A} ^ {*}} (a, z)}, & a \ prec b \\ 0, & b \ prec a \ end {cases}}}

Appeal Formula

Let the functions g and f take real values on the set $A$ ${\ displaystyle A}$ and the condition is satisfied $g(x)=\sum \limits _{y\preccurlyeq x}{f(y)}$ ${\ displaystyle g (x) = \ sum \ limits _ {y \ preccurlyeq x} {f (y)}}$ .

Then $f(x)=\sum \limits _{y\preccurlyeq x}{{\mu _{A}^{*}}(y,x)g(y)}$ ${\ displaystyle f (x) = \ sum \ limits _ {y \ preccurlyeq x} {{\ mu _ {A} ^ {*}} (y, x) g (y)}}$

Relationship with the classical Mobius function

If you take as $A$ ${\ displaystyle A}$ many natural numbers, taking as an attitude $a\prec b$ ${\ displaystyle a \ prec b}$ the attitude $a\mid b\land a\not =b$ ${\ displaystyle a \ mid b \ land a \ not = b}$ then we get ${\mu _{\mathbb {N} }^{*}}(a,b)=\mu \left({\frac {b}{a}}\right)$ ${\ displaystyle {\ mu _ {\ mathbb {N}} ^ {*}} (a, b) = \ mu \ left ({\ frac {b} {a}} \ right)}$ where $\mu$ ${\ displaystyle \ mu}$ is the classical Mobius function.

This, in particular, means that $\mu (n)={\mu _{\mathbb {N} }^{*}}(1,n)$ ${\ displaystyle \ mu (n) = {\ mu _ {\ mathbb {N}} ^ {*}} (1, n)}$ , and then the definition of the classical Mobius function follows by induction from the definition of a generalized function and identity $\sum \limits _{k=1}^{n}{(-1)^{k}C_{n}^{k}}=0$ ${\ displaystyle \ sum \ limits _ {k = 1} ^ {n} {(- 1) ^ {k} C_ {n} ^ {k}} = 0}$ since summation over all divisors of a number not divisible by a full square can be considered as summation over the Boolean of its prime factors multiplied in each element of the Boolean.

Literature

Vinogradov I.M. Fundamentals of number theory. - 9th ed. - M. , 1981.
Hall M. Combinatorics = Combinatorial Theory. - M .: Mir, 1970 .-- 424 p.

Links

MIPT lecture hall. Raigorodsky A.M. - Fundamentals of combinatorics and number theory. Lecture No. 5 , 2013.
MIPT lecture hall. Raigorodsky A.M. - Fundamentals of combinatorics and number theory. Lecture No. 6 , 2013.
The generalized Mobius formula

Mobius function

Content

Definition

Properties and Applications

Mobius appeal

The first formula of the Mobius appeal

The second formula of the Mobius

Generalized Mobius function

Definition

Appeal Formula

Relationship with the classical Mobius function

See also

Literature

Links

More articles: