7
$\begingroup$

I'm teaching discrete math to computer scientists. This is mostly their first proof-based course. We cover a bit of number theory, and as I hate loose ends, I cover a bit of Möbius inversion. (It is required later to justify some transfer formulas for the symbolic method in combinatorics and elsewhere.)

My problem is that I haven't been able to find clear applications of arithmetic sums (sums over the divisors of $n$) more than Euclid/Euler on perfect numbers. Even less convincing uses of Möbius inversion.

$\endgroup$
11
$\begingroup$

How many binary sequences are there that have period $n$? The sequence $\ldots110110110\ldots,$ for example, has period 3.

Suppose we wanted to compute the number of binary sequences with period $6.$ There are $2^6$ binary strings of length $6,$ but not all of them, when infinitely repeated in both directions, produce a sequence with period $6$. Among the strings of length $6,$ we find examples such as $111111,$ $101010,$ and $110110,$ which produce sequences with periods $1,$ $2,$ and $3,$ rather than $6.$ We can break the set of strings of length $6$ down as follows:

  1. there are $2$ strings that give period $1$, namely $111111$ and $000000;$
  2. there are $2$ strings that give period $2$, namely $101010$ and $010101,$ the second of which is a cyclic permutation of the first;
  3. there are $6$ strings that give period $3$, namely $110110$ and its two cyclic permutations, and $100100$ and its two cyclic permutations;
  4. there are $54$ strings that give period $6,$ including $111110$ and its five cyclic permutations, $111100$ and its five cyclic permutations, $111010$ and its five cyclic permutations, and so on.

The answer to our question is therefore $9:$ there are nine classes of strings that give period $6$, each consisting of six strings that are cyclic permutations of each other, and therefore $9$ sequences of period $6.$

Here's how we could have used Möbius inversion to compute this number. Let $M(n)$ be the number of binary sequences with period $n.$ Each such binary sequence could have been produced by any of $n$ strings, which are all cyclic permutations of each other. From this observation, we have $$2^n=\sum_{d\mid n}d M(d).$$

Applying the Möbius inversion formula to this equation, we get $$nM(n)=\sum_{d\mid n}\mu(d)2^{n/d}$$ or $$M(n)=\frac{1}{n}\sum_{d\mid n}\mu(d)2^{n/d}$$ Applying this to $n=6$, we get $$M(6)=\frac{1}{6}(\mu(1)2^6+\mu(2)2^3+\mu(3)2^2+\mu(6)2^1)=\frac{1}{6}(64-8-4+2)=9.$$

$\endgroup$
  • $\begingroup$ Just the kind of example I was looking for. Thanks! I'll wait to see if others show up. $\endgroup$ – vonbrand Jun 17 '14 at 0:36
  • 2
    $\begingroup$ That's beautiful! $\endgroup$ – Ryan Reich Jun 17 '14 at 17:17
1
$\begingroup$

In the end I adopted the following beautiful result.

A string can be written as repetitions of its root, the smallest substring that it is a repeat of. I.e., "abababab" has "ab" as root. If a string is its own root, it is called primitive. Call $p_n$ the number of primitive strings of length $n$.

If the strings are written over an alphabet of $s$ symbols, there are $s^n$ strings in all. But they are all repetitions of some primitive root, whose length divides $n$: $$ s^n = \sum_{d \mid n} p_d $$ Möbius inversion gives: $$ p_n = \sum_{d \mid n} \mu(n / d) s^d $$ For example, with $s = 2$, $n = 4$ this gives $p_4 = 12$. This can also be computed by noting that primitive strings of length $1$ over $\{a, b\}$ are just $a$ and $b$ (giving rise to $aaaa$ and $bbbb$), of length $2$ the only ones are $ab$ and $ba$ (giving rise to $abab$ and $baba$). All other length $4$ strings are primitive, i.e., there are $2^4 - 4 = 12$ of them.

$\endgroup$
  • $\begingroup$ I'm still looking for further nice examples. Thanks in advance for any suggestions. $\endgroup$ – vonbrand Jun 19 '14 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.