4.3: The Mobius Function and the Mobius Inversion Formula - Mathematics

We start by defining the Mobius function which investigates integers in terms of their prime decomposition. We then determine the Mobius inversion formula which determines the values of the a function (f) at a given integer in terms of its summatory function.

(mu(n)=left{egin{array}{lcr} 1 mbox{if} n=1; (-1)^t mbox{if} n=p_1p_2...p_t mbox{where the} p_i mbox{are distinct primes}; 0 mbox{ otherwise}. end{array} ight .)

Note that if (n) is divisible by a power of a prime higher than one then (mu(n)=0).

In connection with the above definition, we have the following

An integer (n) is said to be square-free, if no square divides it, i.e. if there does not exist an integer (k) such that (k^2mid n).

It is immediate (prove as exercise) that the prime-number factorization of a square-free integer contains only distinct primes.

Notice that (mu(1)=1), (mu(2)=-1), (mu(3)=-1) and (mu(4)=0).

We now prove that (mu(n)) is a multiplicative function.

The Mobius function (mu(n)) is multiplicative.

Let (m) and (n) be two relatively prime integers. We have to prove that [mu(mn)=mu(m)mu(n).] If (m=n=1), then the equality holds. Also, without loss of generality, if (m=1), then the equality is also obvious. Now suppose that (m) or (n) is divisible by a power of prime higher than 1, then [mu(mn)=0=mu(m)mu(n).] What remains to prove that if (m) and (n) are square-free integers say (m=p_1p_2...p_s) where (p_1,p_2,...,p_s) are distinct primes and (n=q_1q_2...q_t) where (q_1,q_2,...,q_t). Since ((m,n)=1), then there are no common primes in the prime decomposition between (m) and (n). Thus [mu(m)=(-1)^s, mu(n)=(-1)^t mbox{and} mu(mn)=(-1)^{s+t}.]

In the following theorem, we prove that the summatory function of the Mobius function takes only the values (0) or (1).

Let (F(n)=sum_{dmid n}mu(d)), then (F(n)) satisfies [F(n)=left{egin{array}{lcr} 1 mbox{if} n=1; 0 mbox{if} n>1. end{array} ight .]

For (n=1), we have (F(1)=mu(1)=1). Let us now find (mu(p^k)) for any integer (k>0). Notice that [F(p^k)=mu(1)+mu(p)+...+mu(p^k)=1+(-1)+0+...+0=0] Thus by Theorem 36, for any integer (n=p_1^{a_1}p_2^{a_2}...p_t^{a_t}>1) we have, [F(n)=F(p_1^{a_1})F(p_2^{a_2})...F(p_t^{a_t})=0]

We now define the Mobius inversion formula. The Mobius inversion formula expresses the values of (f) in terms of its summatory function of (f).

Suppose that (f) is an arithmetic function and suppose that (F) is its summatory function, then for all positive integers (n) we have [f(n)=sum_{dmid n}mu(d)F(n/d).]

We have [egin{aligned} sum_{dmid n}mu(d)F(n/d)&=&sum_{dmid n}mu(d)sum_{emid (n/d)}f(e) &=& sum_{dmid n}sum_{emid (n/d)}mu(d)f(e)&=&sum_{emid n}sum_{dmid (n/e)}mu(d)f(e)&=&sum_{emid n}f(e)sum_{dmid (n/d)}mu(d)end{aligned}] Notice that (sum_{dmid (n/e)}mu(d)=0) unless (n/e=1) and thus (e=n). Consequently we get [sum_{emid n}f(e)sum_{dmid (n/d)}mu(d)=f(n).1=f(n).]

A good example of a Mobius inversion formula would be the inversion of (sigma(n)) and ( au(n)). These two functions are the summatory functions of (f(n)=n) and (f(n)=1) respectively. Thus we get [n=sum_{dmid n}mu(n/d)sigma(d)] and [1=sum_{dmid n}mu(n/d) au(d).]


  1. Find (mu(12)), (mu(10!)) and (mu(105)).
  2. Find the value of (mu(n)) for each integer (n) with (100leq nleq 110).
  3. Use the Mobius inversion formula and the identity (n=sum_{dmid n}phi(n/d)) to show that (phi(p^t)=p^t-p^{t-1}) where (p) is a prime and (t) is a positive integer.

Number Theory: In Context and Interactive

There is a more serious side to the panoply of new functions, though. This is our key to arithmetic functions. We will now turn to algebra again, with a goal of generalizing the Moebius result.

Subsection 23.4.1 The monoid of arithmetic functions

Definition 23.4.1 .

A is a set with multiplication (an operation) that has an identity, is associative and commutative.

You can think of a commutative monoid as an Abelian group without requiring inverses. (That means it's not necessarily a group, though it could be see Definition 8.3.3.)

Theorem 23.4.2 .

Let (A) be the set of all arithmetic functions. Then (star) turns the set (A) into a commutative monoid.


The function (I(n) ext<,>) which is equal to zero except when (n=1 ext<,>) plays the role of identity. Then one would need to prove the following three statements.

((fstar g)star h = fstar (gstar h))

We include one of the proofs. The others are similar – see Exercise 23.5.2. Note that for the second one, one can use the fact that (dc=n,ab=d) implies (abc=n ext<.>)

Can you think of other commutative monoids? What sets have an operation and an identity, but no inverse?

Subsection 23.4.2 Bringing in group structure

Let's get deeper in the algebraic structure behind the (star) operation. Remember, (fstar g) is defined by

This structure is so neat is because it actually allows us to generalize the idea behind the Moebius function!

Theorem 23.4.3 .

If (f) is an arithmetic function and (f(1) eq 0 ext<,>) then (f) has an inverse in the set (A) under the operation (star ext<.>) We call this inverse (f^<-1> ext<.>) It is given by the following recursive definition:


As in all the best theorems, there is really nothing to prove. The definitions for (n>1) are equivalent ways of representing the same thing. We can always get the next value of (f^<-1>(n)) by knowledge of (f^<-1>(d)) for (dmid n ext<,>) and that is enough for an induction proof, since we do have a formula given for (f^<-1>(1) ext<.>) (See Exercise 23.5.9)

Corollary 23.4.4 .

This can be immediately used to show that the Moebius function (mu) is (mu=u^<-1>) (and hence (u=mu^<-1>)).

Corollary 23.4.5 .

Since (omega(1)=0 ext<,>) the function (omega) has no inverse.

This is a good time to try to figure out what the inverse of (N) or (phi) is with paper and pencil. See Exercises Exercise 23.5.4 and Exercise 23.5.5.

In general, we can also say that

There is another, more theoretical, implication too, hearkening back to Section 8.3.

Corollary 23.4.6 .

The subset of (A) which consists of all arithmetic functions with (f(1) eq 0) is actually a group.

Remark 23.4.7 .

Much of this chapter is done in slightly variant ways in introductory books, at a similar level. For a higher-level but useful and readable account of the ring theory of arithmetic functions (including valuations and derivations), see [C.2.8, Chapters 3 and 4]. For good exercises see [C.4.6, Chapter 2] or [C.2.9, Chapter 2] for instance, the latter asks for identifying the idempotents of (A ext<.>)

Subsection 23.4.3 More dividends from structure

This new way of looking at things yields an immediate slew of information about arithmetic functions. The following results will yield dividends about number theory and analysis/calculus (no, we haven't forgotten that!) in the next chapter on Infinite Sums and Products.

Fact 23.4.8 .

The Moebius inversion formula that if (f=gstar u) then (g=fstar mu) can be proved concisely by

(We need no parentheses, since (star) is associative).

Fact 23.4.9 .

Conversely, if (g=fstar mu ext<,>) then

so the inversion formula is true in both directions.

Proposition 23.4.10 .

If (g) and (h) are multiplicative, then (f=gstar h) is also multiplicative.


The next result has a long proof, but most of it is following the definitions and keeping careful track of indices. See [C.2.1, Exercise 8.20] or [C.2.13, Chapter 5.3] for similar approaches.

Proposition 23.4.11 .

If (f) is multiplicative and (f(1) eq 0 ext<,>) then (f^<-1>) is also multiplicative.


This basically can be done by induction, but each step is somewhat involved so we will break this into several lemmata. Throughout, recall that the inverse is defined by

and, for (n>1 ext<,>) the condition

First, in Lemma 23.4.12 we will show that (f^<-1>(1)) behaves well.

Then, assuming as an inductive hypothesis that (f^<-1>) is multiplicative for inputs less than (mn ext<,>) with (gcd(m,n)=1 ext<,>) we will show in Lemma 23.4.13 that

Finally, in Lemma 23.4.14 we will show how to rewrite this as

which finishes the induction argument.

Lemma 23.4.12 .

Left to the reader in Exercise 23.5.10 use everything you know about (f ext<.>)

Lemma 23.4.13 .

Assume as above that (f^<-1>) is multiplicative for inputs less than (mn ext<,>) with (gcd(m,n)=1 ext<.>) Then


Assume that (m,n>1) and coprime. By the definition of inverse, we have

By assumption, every function in this expression (both (f) and (f^<-1>)) is multiplicative on the values in question, with the possible exception of (f^<-1>(mn) ext<.>)

We can use this effectively because each summand is for a divisor (xmid mn ext<,>) which we can write as (xy=mn ext<.>) Since (m) and (n) are coprime, both (x) and (y) are themselves products of coprime divisors dividing (m) and (n) respectively.

So let (x=ab) and (y=cd ext<,>) where (a,cmid m) and (b,dmid n ext<.>) Then, as everything is multiplicative, (f^<-1>(x)f(y)=f^<-1>(a)f^<-1>(b)f(c)f(d) ext<.>)

Since by the previous lemma (f(1)=1 ext<,>) we can subtract the summation from both sides of the equation whose left-hand side is zero at the beginning of this lemma's proof, yielding

Lemma 23.4.14 .

Under the same hypotheses as before, (f^<-1>(mn)=f^<-1>(m)f^<-1>(n) ext<.>)


We now write all this in terms of things we already can evaluate.

If the sum in question were summed over every (ableq mn) instead of (ab<mn ext<,>) it would easily simplify as a product:

The sum in Lemma 23.4.13 only lacks the term with (a=m,b=n ext<,>) in fact. So

Now we can plug this back into the previous characterization of (f^<-1>(mn) ext<:>)

Since (m,n>1 ext<,>) the individual sums may be rewritten as

That means we achieve the desired result

Finally, we get the following promised corollary from the beginning of the chapter, Fact 23.1.6.

Corollary 23.4.15 .

The function (mu) is multiplicative.


This follows since (u) is multiplicative (trivially) and (mu=u^<-1> ext<.>)

Möbius inversion formulas for flows of arithmetic semigroups ☆

We define a convolution-like operator which transforms functions on a space X via functions on an arithmetical semigroup S, when there is an action or flow of S on X. This operator includes the well-known classical Möbius transforms and associated inversion formulas as special cases. It is defined in a sufficiently general context so as to emphasize the universal and functorial aspects of arithmetical Möbius inversion. We give general analytic conditions guaranteeing the existence of the transform and the validity of the corresponding inversion formulas, in terms of operators on certain function spaces. A number of examples are studied that illustrate the advantages of the convolutional point of view for obtaining new inversion formulas.

Möbius inversion formulas related to the Fourier expansions of two-dimensional Apostol–Bernoulli polynomials

The two-dimensional (2D) Apostol–Bernoulli and Apostol–Euler polynomials are defined via the generating functions t e x t + y t m λ e t − 1 = ∑ n = 0 ∞ B n ( x , y λ ) t n n ! , 2 e x t + y t m λ e t + 1 = ∑ n = 0 ∞ E n ( x , y λ ) t n n ! . The Apostol–Bernoulli and Apostol–Euler polynomials are essentially the same as parametrized polynomial families, thus we may restrict to the latter.

The Fourier coefficients of x ↦ λ x B n ( x , y λ ) on [ 0 , 1 ) satisfy an arithmetical–dynamical transformation formula which makes the Fourier series amenable to a technique of generalized Möbius inversion. This yields some interesting arithmetic summation identities, among them parametrized versions of the following well-known classical formula of Davenport: ∑ k = 1 ∞ μ ( k ) k < k x >= − sin ⁡ ( 2 π x ) π ( x ∈ R ) , where μ ( n ) is the Möbius function and < x >denotes the fractional part of x. Davenport's formula is the limiting case α = 0 of − 4 π 4 π 2 − α 2 sin ⁡ ( 2 π x ) = ∑ k = 1 ∞ μ ( k ) k ⋅ sin ⁡ ( α k ( < k x >− 1 2 ) ) 2 sin ⁡ ( α 2 k ) , which is valid for − π < α ≤ π .

Decomposition spaces, incidence algebras and Möbius inversion III: The decomposition space of Möbius intervals ☆

Decomposition spaces are simplicial ∞-groupoids subject to a certain exactness condition, needed to induce a coalgebra structure on the space of arrows. Conservative ULF functors (CULF ) between decomposition spaces induce coalgebra homomorphisms. Suitable added finiteness conditions define the notion of Möbius decomposition space, a far-reaching generalisation of the notion of Möbius category of Leroux. In this paper, we show that the Lawvere–Menni Hopf algebra of Möbius intervals, which contains the universal Möbius function (but is not induced by a Möbius category), can be realised as the homotopy cardinality of a Möbius decomposition space U of all Möbius intervals, and that in a certain sense U is universal for Möbius decomposition spaces and CULF functors.

Note that the Rezk completeness condition, that (s_0: X_0 ightarrow X_1) induces an equivalence onto the subspace of equivalences, which is the usual completeness condition in the theory of Segal spaces, implies the present completeness condition for decomposition space.

Aguiar, M., Bergeron, N., Sottile, F.: Combinatorial Hopf algebras and generalized Dehn–Sommerville relations. Compos. Math. 142(1), 1–30 (2006)

Bergner, J.E., Osorno, A.M., Ozornova, V., Rovelli, M., Scheimbauer, C.I.: 2-Segal sets and the Waldhausen construction. Topol. Appl. 235, 445–484 (2018)

Carlier, L.: Incidence bicomodules, Möbius inversion, and a Rota formula for infinity adjunctions. Algebr. Geometr. Topol. 20, 169–213 (2020)

Cartier, P., and Foata, D.: Problèmes combinatoires de commutation et réarrangements. Lecture Notes in Mathematics, No. 85. Springer-Verlag, Berlin–New York, (1969)

Dyckerhoff, T., and Kapranov, M.: Higher Segal spaces I. Volume 2244 of Lecture Notes in Mathematics. Springer, (2019)

Feller, M., Garner, R., Kock, J., Proulx, M.U., Weber, M.: Every 2-Segal space is unital. Commun. Contemp. Math. 23, 2050055 (2021)

Gálvez-Carrillo, I., Kock, J., Tonks, A.: Groupoids and Faá di Bruno formulae for Green functions in bialgebras of trees. Adv. Math. 254, 79–117 (2018)

Gálvez-Carrillo, I., Kock, J., Tonks, A.: Decomposition spaces, incidence algebras and Möbius inversion I: basic theory. Adv. Math. 331, 952–1015 (2018)

Gálvez-Carrillo, I., Kock, J., Tonks, A.: Decomposition spaces, incidence algebras and Möbius inversion II: completeness, length filtration, and finiteness. Adv. Math. 333, 1242–1292 (2018)

Gálvez-Carrillo, I., Kock, J., Tonks, A.: Decomposition spaces and restriction species. Int. Math. Res. Not. 7558–7616, 2020 (2020)

Gálvez-Carrillo, I., Kock, J., and Tonks, A.: Decomposition spaces in combinatorics. Preprint, arXiv:1612.09225

Illusie, L.: Complexe cotangent et déformations II. Lecture Notes in Mathematics, vol. 283. Springer, Berlin (1972)

Joyal, A., Tierney, M.: Quasi-categories vs Segal spaces. Contemp. Math. 431, 277–326 (2007)

Kock, J.: Categorification of Hopf algebras of rooted trees. Central Eur. J. Math. 11(3), 401–422 (2013)

Kock, J., Weber, M.: Faá di Bruno for operads and internal algebras. J. Lond. Math. Soc. 99, 919–944 (2019)

Leroux, P.: Les catégories de Möbius. Cahiers de topologie et géométrie différentielle 16, 280–282 (1975)

Penney, M. D.: Simplicial spaces, lax algebras and the 2-Segal condition. Preprint, arxiv:1710.02742

Rota, G.-C.: On the foundations of combinatorial theory I. Theory of Möbius functions. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 2, 340–368 (1964)

Schmitt, W.R.: Hopf algebras of combinatorial structures. Can. J. Math. 45, 412–428 (1993)

2 Answers 2

Consider the sets of quadruples of integers $Q(n)=<(i,j,k,l) : 1leqslant i<j<k<lleqslant n>, Q(n,d)=<(i,j,k,l)in Q(n) : gcd(i,j,k,l)=d>$ for $1leqslant dleqslant n$ . Clearly we have $|Q(n)|=inom<4>,quad Q(n)=igcup_^Q(n,d),quad Q(n,d)=dQ(lfloor n/d floor,1)$ (where, for the last one, $d(i,j,k,l):=(di,dj,dk,dl)$ and $dS:=$ are assumed).

This means that if $F(n)=|Q(n,1)|$ , then $|Q(n,d)|=F(lfloor n/d floor)$ and $color^F(lfloor n/d floor)=inom<4>>quadimpliesquad F(n)=sum_^mu(d)inom<4>$ by Möbius inversion. The sum we need is $S(n)=sumlimits_^d^4 F(lfloor n/d floor)$ . To compute it, one may avoid the computation of $mu$ , using the "blue" equation above as a recurrence for $F(n)$ , and grouping terms with equal $lfloor n/d floor$ (here are my answers suggesting this too: 1, 2, 3).

On a generalization of the Möbius function from number theory

Let $omega$ be a positive real number, and define: $mathbf<1>_left(n ight)overset< extrm><=>left(-1 ight)^inom<-omega>=inom$ for all positive integers $n$ , and let: $zeta_left(s ight)overset< extrm><=>sum_^frac_left(n ight)><>>$ Since $mathbf<1>_left(1 ight)=omega>0$ , $mathbf<1>_$ possesses an inverse with respect to Dirichlet convolution, which I denote by $mu_$ , with: $sum_^fracleft(n ight)><>>=frac<1>left(s ight)>$ When $omega=1$ , $mathbf<1>_$ becomes the constant function $1$ and $mu_$ becomes the Möbius function from number theory.

To be clear, this is a reference request: I am looking to see if there has been any work done with these functions. In particular, I am interested in:

• If there is any "official name" for these functions, what is it?

• Closed-form expressions for $mu_left(n ight)$ (analogous to how the möbius function can be computed in terms of the prime factors of its inputs)

• Asymptotics/formulas for $mu_left(n ight)$ , $sum_^mu_left(k ight)$ and $sum_mu_left(d ight)$ as $n ightarrowinfty$ .

I'm making tedious progress brute-forcing the formulas by hand, but since this is only tangential to what I'm actually working on, it would be of much help if it turned out that someone had already done that drudgery for me. )

Aigner, M.: Combinatorial Theory. Springer, New York (1997)

Andrews, G.E.: The Theory of Partitions. Addison-Wesley Publishing, New York (1976)

Bender, E.A., Goldman, J.R.: On the applications of Möbius inversion in combinatorial analysis. Am. Math. Mon. 82, 789–803 (1975)

Bogart, K.: Introductory Combinatorics. Harcourt Academic Press, San Diego (2000)

Broder, A.Z.: The (r) -Stirling numbers. Discret. Math. 49, 241–259 (1984)

Comtet, L.: Advanced Combinatorics: The Art of Finite and Infinite Expansions. Springer, New York (1974)

Doubilet, P.: On the foundations of combinatorial theory VII. Symmetric functions trough the theory of distribution and occupancy. Stud. Appl. Math. 51, 377–396 (1972)

Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Addison-Wesley, New York (1994)

Kitaev, S.: Patterns in Permutations and Words, Monographs in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg, xxii+494 pp (2011)

Kuba, M., Prodinger, H.: A note on Stirling series. Integers 10, 393–406 (2010)

Merca, M.: Fast algorithm for generating ascending compositions. J. Math. Model. Algorithms 11, 89–104 (2012)

Merca, M.: Binary diagrams for storing ascending compositions. Comput. J. 56(11), 1320–1327 (2013)

Merca, M.: A convolution for complete and elementary symmetric functions. Aequat. Math. 86, 217–229 (2013)

Merca, M.: A note on the (r) -Whitney numbers of Dowling lattices. C. R. Math. Acad. Sci. Paris 351(16–17), 649–655 (2013)

Merca, M.: A new connection between (r) -Whitney numbers and Bernoulli polynomials. Integral Transforms Spec. Funct. 25(12), 937–942 (2014)

Merca, M.: Augmented monomials in terms of power sums. SpringerPlus 4, 724 (2015)

Merca, M.: New convolution for complete and elementary symmetric functions. Integral Transforms Spec. Funct. 27(12), 965–973 (2016)

Mező, I.: On the maximum of (r) -Stirling numbers. Adv. Appl. Math. 41(3), 293–306 (2008)

Mező, I.: New properties of (r) -Stirling series. Acta Math. Hung. 119, 341–358 (2008)

Rota, G.C.: On the foundations of combinatorial theory I. Theory of Möbius functions. Z. Wahrsch. Verw. Gebiete 2, 340–368 (1964)

Stanley, R.: Enumerative Combinatorics, vol. 1. Cambridge University Press, New York (2000)

Lesson Explainer: Möbius Transformations Mathematics

In this explainer, we will learn how to interpret Möbius transformation in the complex plane.

Möbius transformations form an interesting class of the transformations of the complex plane. They have a number of deep properties and connections to other areas of mathematics, such as group theory, and even have a deep connection to relativity via Lorentz transformations. In this explainer, we will introduce Möbius transformations and consider some of their basic properties including the effect they have on lines and circles in the complex plane.

Before we consider Möbius transformations, we will recap some of the basic transformations of the complex plane.

Basic Transformations of the Complex Plane

represents a translation by the vector

represents a dilation by scale factor

and a counterclockwise rotation about the origin by

These transformations have the property that they map straight lines to straight lines and circles to circles. In this explainer, we will consider a more general class of transformations that map circles and straight lines to circles and straight lines, possibly mapping a straight line to a circle and vice versa.

We will start by considering the effect of the reciprocal map

Example 1: Reciprocal Transformation

A transformation which maps the

    Find an equation for the image of


To find an equation representing the image of a particular curve under the transformation

, and then substitute this into the equations defining the particular curve then we can rearrange to get the expression.

We can now substitute this into the equation

Using the properties of the modulus, we can rewrite this as

Rearranging the equation, we get

This is the equation of a circle of radius

centered at the origin. We can represent the effect of this transformation visually as follows.

Using the properties of the argument, we can rewrite this as

This is the half-line centered at the origin which makes an angle of

with the positive real axis. We can represent the effect of this transformation visually as follows.

To find a Cartesian equation, we begin by substituting

into this equation as follows:

Multiplying the numerator and denominator by the complex conjugate of the denominator, we can rewrite the fraction as follows:

Now we can manipulate this equation to put it into a standard form. To do this, we first multiply through by

to both sides and dividing through by two gives

We can now complete the square in

This represents a circle of radius

. We can visualize the effect of this transformation on the line

Rewriting the subject of the modulus as a single fraction we have

out of the denominator, we have

We can now use the properties of the modulus to rewrite this as

This is the equation of a circle. However, to find its Cartesian equation, we need to substitute

into the equation as follows:

Squaring both sides yields

We can now use the definition of the modulus to rewrite this as

Expanding the parentheses, we get

Gathering together our like terms, we have

We now divide through by 3, which gives us

Finally, we can complete the square in

This is the equation of a circle of radius

. We can visually represent the effect of this transformation on the circle

The previous example showed that the transformation

maps some lines to circles and some circles to circles. By looking carefully at the previous example, we can piece together what the transformation is doing. The first part generalizes to tell us that the transformation maps a circle of radius

centered at the origin to a circle of radius

centered at the origin. The second part shows us that a ray from the origin gets mapped to another ray which has been reflected in the real axis. The third part shows us that lines which do not pass through the origin get mapped to circles which pass through the origin. Finally, the fourth part shows us that circles which do not pass through the origin get mapped to other circles. Putting these facts together and recalling some geometry, we can see that the transformation is a combination of inversion in the unit circle and reflection in the real axis.

We now turn our attention to the general definition of Möbius transformations.

Möbius transformations are the transformations we get by composing the following three basic types of transformation in the complex plane:

Watch the video: Arithmetic Functions Part-4. Mobius Inversion Formula (November 2021).