High School

On the Möbius function

April 11, 2015 by Sabyasachi Mukherjee. 7 comments

The Möbius function is a rather useful one, especially when dealing with multiplicative functions. But first of all, a few definitions are in order.

Definition 1: Let \(\omega(n)\) be the number of distinct prime divisors of \(n\).

Definition 2: The Möbius function, \(\mu(n)\) is defined as \((-1)^{\omega(n)}\) if \(n\) is square-free and \(0\) otherwise. (A number \(n\) is square-free if there is no prime \(p\) such that \(p^2\) divides \(n\).)

It may be a good idea to compute the following: \(\omega(n)\) and \(\mu(n)\) for \(n=64, 12, 17, 1\) to get an idea of what’s going on.

A Möbius function is an arithmetic function, i.e. a function from \(\mathbb{N}\) to \(\mathbb{C}\). Can you think of some other arithmetic functions?

Definition 3:  If \(f(n)\) is an arithmetic function not identically zero such that \(f(m)f(n)=f(mn)\) for every pair of positive integers \(m, n\) satisfying \((m,n)=1\), then \(f(n)\) is multiplicative.

Theorem 0: \(\mu(n)\) is a multiplicative function.

Proof: The proof is left to the reader.

Theorem 1: If \(f(n)\) is a multiplicative function, so is \(\displaystyle \sum_{d|n} f(d)\).

Before we jump to the proof, let us be clear on the notation. For \(n=12\), \(\displaystyle \sum_{d|n} f(d)=f(1)+f(2)+f(3)+f(4)+f(6)+f(12)\) i.e. the sum taken over the divisors of \(n\).

Proof: Consider the sets \(A= \{d :  0<d, d|n \}\) and \(B= \{d_1d_2 : d_1|m_1, d_2|m_2, (m_1,m_2)=1,m_1m_2=n\}\).

(Note that such \(m_1, m_2\) exist. Take \(m_1=1,m_2=n\)).

Now take \(d \in A\). Then \(1\cdot d\) divides \(1\cdot n\) which means that \(d \in B\) and so \(A \subset B\).

Now take \(s \in B\). So \(s\) is of the form \(d_1d_2\) where \(d_1|m_1\) and \(d_2 |m_2\) such that \((m_1,m_2)=1\) with their product \(n\). So, \(s\) divides \(m\) and hence \(B \subset A\). From these, we infer that \(A=B\).

Now, suppose that \((m,n)=1\). Then \(\displaystyle F(mn)=\sum_{d|mn} f(d)=\sum_{d_1|m,d_2|n,d_1d_2=mn}f(d_1d_2)=\sum_{d_1|m}\sum_{d_2|n} f(d_1d_2)\)

So, $$F(mn)=\sum_{d_1|m}\sum_{d_2|n}f(d_1)f(d_2)(\text{since f is multiplicative})=\sum_{d_1|m}f(d_1)\sum_{d_2|n}f(d_2).$$

Now with this theorem in hand, let us a prove a few more theorems.

 Theorem 2: \(\displaystyle \sum_{d|n} \mu(d)\) is \(0\) if \(n>1\) and \(1\) if \(n=1\).

Proof: The case \(n=1\) is trivial.

Suppose that \(n>1\).

Since \(\mu(n)\) is multiplicative, so is \(\displaystyle F(n)= \sum_{d|n} \mu(d)\). Now let us recall that \(n>1\) can be written as a product of primes, say \(\displaystyle n=p_i^{a_i}\dots p_k^{a_k}\). So, we can write \(F(n)=F(p_1^{a^1})\dots F(p_k^{a_k})\).

As \(a_i\ge 1\), \(F(p_i^{a_i})= 0\) (using the definition of \(\mu\).)That means \(F(n)=0\). The desired conclusion now follows from this discussion.

Before we now move on to a theorem which shows a connection between the Euler’s \(\varphi-\)function and the Möbius function, let us state a really important theorem, also known as the Möbius Inversion formula.

Theorem 3: If \(\displaystyle F(n)=\sum_{d|n}f(d)\) for every positive integer \(n\), then \(\displaystyle  f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})\).

Proof:  We will flesh this proof in somewhat lesser detail because we have developed most of the techniques related to his proof.

Note that \(\displaystyle \sum_{d|n}\mu(d)F(\frac{n}{d})\)

\(\displaystyle =\sum_{d|n}\mu(d)\sum_{k|(n/d)} f(k)= \sum_{dk|n}\mu(d)f(k)=\sum_{dk|n}\mu(k)f(d)\).

Can the reader now complete the proof? (Hint: Use Theorem 2).

Theorem 4: \(\displaystyle \varphi(n)= n\sum_{d|n} \frac{\mu(d)}{d}.\)

Proof:  To write the proof, we use a lemma.

Lemma: \(\displaystyle \sum_{d|n} \varphi(d)=n\).

Proof of the lemma: Note that for \(n=1\), this is true. Suppose that \(n>1\). Then \(\displaystyle n=p_1^{a_1}\dots p_k^{a_k}\) for some primes \(p_1,\dots, p_k\). As \(\varphi(n)\) is multiplicative, so is \(\displaystyle  F(n)= \sum_{d|n} \varphi(d)\)

That means \(\displaystyle F(n)=\prod_{i=1}^k F(p_i^{a_i})\). A quick calculation reveals that \(F(p_i^{a_i})=p_i^{a_i}\) which gives \(F(n)=n\).

We can now use this lemma and  the Möbius Inversion formula to finish off the proof.

Here as some other problems on multiplicative functions.

Problem 1:  \(\displaystyle \frac{1}{\varphi(n)}=\frac{1}{n}\sum_{d|n}\frac{\mu(d)^2}{\varphi(d)}\).


Problem 2:  For each positive integer \(n\), \(\displaystyle \mu(n)\mu(n+1)\mu(n+2)\mu(n+3) = 0\).


Problem 3: \(\displaystyle \sum_{d|n}|\mu(d)| = 2^{\omega(n)}\).

Dealing with Risk

December 15, 2014 by nomen. 1 comments

Dealing With Risk

Consider a small company which uses a million dollar machine as an essential part of its operations. Suppose that there is a 10% chance that the machine will break down and need replacement in a given year. If the machine breaks down and the company replaces it, they can continue their operations for the rest of the year. If they machine breaks down and the company is unable to pay for a replacement, the company will have to cease its operations permanently. What is the probability that the company will have to cease its operations permanently?

To be fair, this is not really a question about mathematics. It is a question about business and risk. A business must find a strategy that minimizes its costs and maximizes its income, even in the face of uncertainty. Of course, the company will receive no income if its machine breaks down. So the company must balance the possibility of a break down with the certain costs to protect itself from a break down.

A Particularly Ineffective Strategy

The company might have heard of the expected value principle, an axiom of actuarial science that tells us the economic value of a random variable amount of money is the expectation of the variable, and decide to put $100,000 in a savings account to protect against the loss of the machine. This strategy is too naive. Obviously, the $100,000 isn’t going to pay for a replacement machine when the old one breaks down. So in any given year, the company faces a 10% chance of having to cease its operations.  Worse yet, since the money the company saved offers no protection, it was used non-productively.

A Slightly Better Strategy

The company might have realized that, as stated, the number of years until the machine has its first break down is a geometric random variable \(N\), whose probability mass function is given by:

$$ \newcommand{\P}[1]{\mathbf{P}\!\left[#1\right]} \P{N = n} = (1 – p)^{n-1} p, $$

where, in this case, \(p = 10\%\).

The company might decide to save $100,000 at the start of every year, until they have saved enough money to replace the machine. Observe that the company will not have saved enough money until the 10th year. That is to say, they will face a 10% risk of having to cease operations permanently, every year, for the first nine years of operation. After that, they will have a 0% risk of having to cease operations. Since \(N\), the number of years until the first break down, has a known probability distribution, we can compute

$$ \begin{align} \P{N \leq 9} &= 1 – (1 – p)^9 \\ &= 1 – 0.9^9 \\ &\approx 0.613 \end{align} $$

That is to say, there is approximately a 61.3% chance that the first break down will occur in the first nine years of operation, which would put the company out of business.

This strategy is wasteful even if the company manages to beat the odds. By the tenth year, the company will have saved up a million dollars which could be put to use productively.

How Insurance Works

At its most fundamental level, insurance is a system for reducing the adverse effects of random events. Insurance does not eliminate risks, but it transfers the financial burden of a loss to an insurance company, in exchange for a certain sequence of payments from the customer. By pooling together a large number of these risks, an insurance company is able to increase the “predictability” of its losses. Analyzing the process by which pooling works essentially requires a central limit theorem, which tells us that the sum of large numbers of random variables (with finite variance) converges in distribution to a normal random variable. By modelling its pool in this way, an insurance company is able to budget for losses much more efficiently than any one of its consumers could by themselves.

So, let’s suppose that there are 1000 small companies in the pool, and each face the same risk of a breakdown, with the same distribution of losses. Then the total expected losses are one hundred million, since we expect that 10% of the machines will break down. Using the central limit theorem, we see that the losses the insurance company will face are approximately normally distributed, with a mean of one hundred million, and a standard deviation of about 9.5 million dollars.

This means that if the insurance company collects approximately 109.5 million dollars in premiums in a year, then there is about a 84% chance that they will be able to pay for every loss that year. If they collect approximately 119 million dollars in premiums, then there is about a 97.6% chance that they can pay for every loss that year. If they collect approximately 128 million dollars in premiums, there is more than a 99% chance that they can pay for every loss.

Calculating the risk each individual company now faces is involved, but we can make some observations. For a company to close in the current year:

  • its machine would have to break down
  • at least 128 other machines would have to break down before before it

It is clear that the latter event will be rare, especially when compared to the risk the company originally faced in a year.  Indeed, we will demonstrate that the probability that any one company closes is less than 1%.

We will do this by using the law of total probability. Let \(F\) be the event that the company fails.  Then

$$ \begin{align} \P{F} &= \P{F|N \leq 128}\P{N\leq 128} + \P{F|N > 128}\P{N> 128} \\ &= 0\cdot \P{N\leq 128} + \P{F|N > 128}\P{N > 128}\\ &= \P{F|N > 128}\P{N > 128}\\ \end{align} $$

Notice that the argument so far agrees with the observations made above. In fact, it was informed by the observations.

Now we must compute \(\P{F|N > 128}\P{N > 128}\). This is not straight-forward, and in fact, we do not have enough information to do it without making additional assumptions. The issue is that we do not have any idea how failures are distributed in time. For example, it seems intuitively plausible that a machine in a factory with poor maintenance would fail before a machine in a factory with good maintenance.

We will assume that if there are \(N\) break downs, all \(N!\) orders in which they can occur are equally likely. We can make some observations. First, 128 out of \(N\) companies will get paid. The rest are out of luck. In particular, the probability that our company gets paid is \(\frac{128}{N}\). The probability that our company doesn’t get paid is \(\frac{N – 128}{N}\).

So, using the law of total probability again, we compute:

$$ \begin{align} \P{F|N > 128}\P{N > 128} &= \sum_{n=128}^\infty \P{F|N = n}\P{N = n} \\ &= \sum_{n=128}^\infty \frac{n – 128}{n} f_N(n) \\ &= \sum_{n=128}^\infty \frac{n – 128}{n} F_N(n) – F_N(n+1) \end{align} $$

which is approximately equal to 0.00003915. Again, this number represents the approximate probability that any given company will fail because its machine breaks down in any given year. This is a vast improvement over the situation where there was a 10% chance of failure. To put it in perspective, the distribution of the number of years until the company fails is geometric, with \(p = 0.00003915\), so that the average number of years until a specific company fails is 25.5 thousand years.

This sort of insurance represents a benefit to society in a variety of ways. Insurance lowers the amount of money a business has to raise to protect itself from failure. And so insurance frees capital for more productive purposes.

This model presents property insurance at its most basic level. Real insurance companies have operating costs, and have to follow federal and state regulations for how much they collect in premiums and how they manage the pool of risk. Real policies might have deductibles and other stipulations to fine-tune the amount of risk that gets transferred. Real insurance customers have preferences about how they want to spend their money. The insurance business is what happens when these complex factors meet the basic risk transfer model. An actuary’s job is to understand this basic model and all the fiddly exceptions, laws, and business practices in order to make insurance companies possible and profitable.

Where to find out more:

An actuary must achieve mastery of several topics, including basic and intermediate probability and statistics. If you want to learn more, check out Be An Actuary or talk to a math, business, or finance professor.

Adapted with permission from Poisson Labs.