Rotation of necklaces

Question

The number of fixed necklaces of length $n$ with $a$ types of beads is $$N(n,a)=\frac1n\sum_{d|n}\phi(d)a^{n/d}\;.$$ It is clear intuitively that the number of rotational coincidences gets proportionally negligible for the large number of beads. How to prove it? Any estimation to calculate?

Answer 1

A necklace that has no rotational symmetry is called a primitive or aperiodic necklace, or a Lyndon word (if written as a word by taking the lex-smallest rotation.) The number of primitive necklaces is given by almost the same formula as the one you give for the number of necklaces, but with Euler's $\phi$ replaced by the Mobius function $\mu$ (see Wikipedia): $$\frac{1}{n} \sum_{d |n } \mu(d) a^{n/d}.$$

Intuitively, we would expect that for large $n$ a random necklace would be almost surely be primitive, since there would have to be a large number of coincidences to find a rotational symmetry. To prove this, just take the ratio

$$\frac{\frac{1}{n} \sum_{d |n } \mu(d) a^{n/d}}{ \frac{1}{n} \sum_{d |n } \phi(d) a^{n/d}} = \frac{a^n + O(a^{n-1}) }{ a^n + O(a^{n-1}) }$$

since the highest order terms in both polynomials corresponds to $d=1$, and $\mu(d) = \phi(d) = 1$. Then the limit as $n \rightarrow \infty$ is $1$.