Let $f(n)$ be the number of binary Lyndon words of length $n$. This sequence is given by OEIS entry A001037. Is it true that $2f(n) \ge f(n+1)$ for all positive $n$?

I have found a general formula to calculate $f(n)$: $$ f(n) = \frac{1}{n} \sum_{d \mid n} \mu(n/d) 2^d. $$ Symmetry also allows us to rewrite it another way: $$ f(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) 2^{n/d}. $$ Here $\mu(x)$ is the Möbius function, and $n$ is a positive integer (the case $n=0$ can be handled separately). It is possible to substitute these identities into the inequality above and perform some simplifications, but it does not seem to go anywhere. Any help is appreciated.

EDIT: My original formula was incorrect, I forgot the factor of $1/n$ in front of the summation.


Step 1: For $n \in \mathbb{N}_+$,$$ \frac{2^n}{n} - \frac{2^{\frac{n}{2}}}{2} \leqslant f(n) \leqslant \frac{2^n}{n} + \frac{2^{\frac{n}{6}}}{6}. \tag{1} $$

Proof: For the upper bound,$$ n f(n) = \sum_{d \mid n} μ\left( \frac{n}{d} \right) 2^d \leqslant 2^n + \sum_{\substack{d \mid n,\ d < n\\μ(n / d) = 1}} 2^d. \tag{2} $$ If $d \mid n$, $d < n$ and $μ\left( \dfrac{n}{d} \right) = 1$, then $\dfrac{n}{d}$ has at least two distinct prime divisors, which implies $\dfrac{n}{d} \geqslant 6$, i.e. $d \leqslant \dfrac{n}{6}$. Thus $(2) \leqslant 2^n + \dfrac{n}{6} 2^{\frac{n}{6}} \Rightarrow f(n) \leqslant \dfrac{2^n}{n} + \dfrac{2^{\frac{n}{6}}}{6}$.

For the lower bound,$$ n f(n) = \sum_{d \mid n} μ\left( \frac{n}{d} \right) 2^d \geqslant 2^n - \sum_{\substack{d \mid n,\ d < n\\μ(n / d) = -1}} 2^d. \tag{3} $$ If $d \mid n$, $d < n$ and $μ\left( \dfrac{n}{d} \right) = -1$, then $\dfrac{n}{d}$ has at least one prime divisor, which implies $\dfrac{n}{d} \geqslant 2$, i.e. $d \leqslant \dfrac{n}{2}$. Thus $(3) \geqslant 2^n - \dfrac{n}{2} 2^{\frac{n}{2}} \Rightarrow f(n) \geqslant \dfrac{2^n}{n} - \dfrac{2^{\frac{n}{2}}}{2}$. Therefore, (1) holds.

Step 2: $2f(n) \geqslant f(n + 1)$ holds for $n \geqslant 15$.

Proof: By (1. 1), it suffices to prove that $2 \left( \dfrac{2^n}{n} - \dfrac{2^{\frac{n}{2}}}{2} \right) \geqslant \dfrac{2^{n + 1}}{n + 1} + \dfrac{2^{\frac{n + 1}{6}}}{6}$. Because$$ 2 \left( \frac{2^n}{n} - \frac{2^{\frac{n}{2}}}{2} \right) \geqslant \frac{2^{n + 1}}{n + 1} + \frac{2^{\frac{n + 1}{6}}}{6} \Longleftrightarrow \frac{2^{n + 1}}{n(n + 1)} \geqslant 2^{\frac{n}{2}} + \frac{2^{\frac{n + 1}{6}}}{6}, $$ and $2^{\frac{n + 1}{4}} \geqslant n + 1$ for $n \geqslant 15$, then$$ \frac{2^{n + 1}}{n(n + 1)} \geqslant 2^{\frac{n + 1}{2}} = 2^{\frac{n}{2}} + (\sqrt{2} - 1) 2^{\frac{n}{2}} \geqslant 2^{\frac{n}{2}} + \frac{2^{\frac{n}{2}}}{6} \geqslant 2^{\frac{n}{2}} + \frac{2^{\frac{n + 1}{6}}}{6}. $$ Therefore, $2f(n) \geqslant f(n + 1)$ holds for $n \geqslant 15$.

Step 3: $2f(n) \geqslant f(n + 1)$ holds for $0 \leqslant n \leqslant 14$.

Proof: Looking up in A001037 verifies this.


$$f(n)=\frac{1}{n} \sum_{d | n} \mu(d) 2^{n/d} \le \frac{ 2^n + d(n)\cdot 2^{n/2} }n = \frac{ 2^n + O(\sqrt{n}\cdot 2^{n/2}) }n,$$

where $d(n)=O(\sqrt n)$ denotes the umber of divisors of $n$. We have $$2f(n)\!\!-\!\!f(n+1)\!\ge\! \frac{ 2^{n+1} + O(\sqrt{n}\cdot 2^{n/2}) }n \!-\!\frac{ 2^{n+1} + O(\sqrt{n+1}\cdot 2^{(n+1)/2}) }{n+1}\!\ge\! \frac{ 2^{n+1}}{n(n+1)}\! - \! O(2^{n/2}),$$

which tends to infinity, thus it is enough to check the first few terms, which can be done in OEIS (though I cheated a bit, because I didn't look up the constant in the $O$ notation, but it's definitely not that big).

  • $\begingroup$ Where does that first identity come from? The limiting behavior makes sense to me but I'm not sure how to derive it. $\endgroup$
    – Ryan
    Dec 3 '18 at 18:17
  • $\begingroup$ @Ryan I've added $d(n)$, I hope that explains all. $\endgroup$
    – domotorp
    Dec 3 '18 at 20:23

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.