Problem set 3: Möbius function

Suppose a function \(f:\mathbb{N}\to\mathbb{R}\) satisfies

\[ \sum_{d\mid n}f(d)= \begin{cases} 1, & n=1,\\ 0, & n\neq 1. \end{cases} \]

Is it necessarily true that

\[ f(n)=\mu(n) \]

for every \(n\in\mathbb{N}\)?

Let

  • \(\tau(n)\) denote the number of positive divisors of \(n\);
  • \(\sigma(n)\) denote the sum of all positive divisors of \(n\).

Evaluate the following sums.

(a)

\[ \sum_{d\mid n}\sigma(d)\mu\left(\frac{n}{d}\right). \]

(b)

\[ \sum_{d\mid n}\tau(d)\mu\left(\frac{n}{d}\right). \]

For every positive integer \(n\geq 1\), evaluate the sum

\[ \sum_{d\mid n}\mu(d)\ln(d). \]

Let \(\varphi(n)\) denote Euler’s totient function.

(a) Prove Gauss’s identity:

\[ \sum_{d\mid n}\varphi(d)=n. \]

(b) Prove that

\[ \sum_{d\mid n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}. \]

(c) Using the previous result, derive Euler’s formula

\[ \varphi(n) = n\left(1-\frac{1}{p_1}\right) \cdots \left(1-\frac{1}{p_s}\right), \]

where \(p_1,\ldots,p_s\) are the distinct prime divisors of \(n\).

1 Cyclic Sequences

Let

\[ X=\{b_1,\ldots,b_k\} \]

be an alphabet consisting of \(k\) symbols, and let \(n\in\mathbb{N}\).

Denote by \(T_k(n)\) the number of distinct cyclic sequences of length \(n\) over the alphabet \(X\).

Two sequences are considered equivalent if one can be obtained from the other by a cyclic rotation.

Find \(T_k(n)\) for

\[ n=3,4,5,6,9. \]

Express your answers in terms of \(k\).

Prove the following formulas for the number of cyclic sequences.

(a)

\[ T_k(n) = \sum_{m\mid n} \frac{1}{m} \sum_{d\mid m} \mu(d)k^{m/d}. \]

(b)

\[ T_k(n) = \frac{1}{n} \sum_{d\mid n} \varphi(d)k^{n/d}. \]

Find the number of distinct cyclic binary sequences of length

\[ 2^n. \]

That is, count the cyclic sequences of length \(2^n\) over the alphabet

\[ X=\{0,1\}. \]

How many distinct cyclic sequences of length 10 can be formed using the alphabet

\[ X=\{A,B,C,D,E\} \]

such that exactly four distinct letters appear in each sequence?

Find the number of distinct cyclic sequences of length 9 over the alphabet

\[ X=\{A,B,C,D,E,F\} \]

in which at most two distinct symbols appear.

Consider cyclic sequences of length 6 over the alphabet

\[ X=\{A,B,C,D,E,F,G\}. \]

How many distinct cyclic sequences satisfy both of the following conditions?

  1. Their period is not equal to 6.
  2. They contain exactly two distinct symbols.