3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Amazing! So obvious. Before accepting, I'll wait to see if anyone has a more refined asymptotic. $\endgroup$ – Unit Oct 22 '16 at 4:23
  • 1
    $\begingroup$ 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? $\endgroup$ – Unit Oct 22 '16 at 17:26
  • $\begingroup$ 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. $\endgroup$ – Clement C. Oct 22 '16 at 17:42

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.