# Asymptotic growth of a convolution (counting n-bead 2-colour necklaces)

I'm seeking the asymptotic growth of the function $$f(n) = \frac{1}{n}\sum_{d | n} 2^d \varphi(n/d) = \frac{1}{n} \sum_{k=1}^n 2^{\gcd(n, k)} \tag{1}$$ which counts the number of necklaces made of $n$ black or white beads where turning over is not allowed (sequence A000031 in the OEIS). Here, $\varphi$ is Euler's totient function. Formula (1) for $f$ is easily established by applying Burnside's lemma to the following action of $G = \mathbf{Z}/(n)$ on the set $\{0, 1\}^G$: $$(g\cdot f)(x) = f(xg).$$

The two representations of $f$ given in (1) yield the following bounds: $$\frac{2^n}{n} \le f(n) \le \frac{2^{n+1}-2}{n} \tag{2}$$ the lower bound coming from picking $d = n$ and the upper bound by noting that $\gcd(n, k) \le k$ and summing the geometric series. I'm pretty certain that $$f(n) \sim \frac{2^n}{n} \quad (n \to \infty)\tag{3}$$ but from (2) we can only get $$1 \le \varliminf_{n \to \infty} \frac{n f(n)}{2^n}\text{ and } \varlimsup_{n \to \infty} \frac{n f(n)}{2^n} \le 2.$$

My question(s) are: is (3) true? If so, how is it proved? If not, what is the correct statement?

Looking at the upper bound: $$\sum_{k=1}^n 2^{\operatorname{gcd}(n,k)} = 2^n + \sum_{k=1}^{n-1} 2^{\operatorname{gcd}(n,k)}$$ Now, each $1\leq k\leq n-1$ which divides $n$ is at most $\frac{n}{2}$; and there will be at most $n-1$ such terms. So we get the upper bound: $$\sum_{k=1}^n 2^{\operatorname{gcd}(n,k)} \leq 2^n + (n-1)\cdot 2^{n/2} = 2^n + o(2^n)$$ which should now allow you to conclude.
• Actually, what do you mean by "there can be at most $2\sqrt{n}$ such divisors"? You are right that each proper divisor of $n$ is at most $n/2$, but that only means $2^{\gcd(n,k)} \le 2^{n/2}$ (since $\gcd(n, k)$ is a proper divisor of $n$ for $k < n$) and then the sum is bounded above by $2^n + (n-1)2^{n/2}$. How did you get $\sqrt{n}$ to appear? – Unit Oct 22 '16 at 17:26
• You are right, I made a mistake there (confusing the bound on the number of distinct elements that divide $n$ and the number of terms). But you don't need this tigher (and incorrect) bound anyway -- I'll edit my answer. – Clement C. Oct 22 '16 at 17:42