Maximal words (reloaded)

Question

I have 3 more questions about maximal words (which are just another way of talking of necklaces).

Let W be a finite word on a two symbol alphabet {0,1}; let us say that W is maximal if it is the last item in the list of all its cyclic permutation (ordered lexicographically).

The number w(n) of maximal words of length n can be expressed with the aid of Eulers' totient function (see Minimal words of length n).

Question 1: What can be said about the asymptotics of w(n)? I expect that $lim (1/n) \log w(n) = h$ for some positive value h ...

Question 2: The bisection scheme. Let us play the following game: start with the two string list [1,0] (which are both maximal) then we put in between the string obtained concatenating them, so we obtain the list [1,10,0], we go on like this (for any two neighbouring strings S,T we put the string ST in between), obtaining in turn the lists [1,110,10,100,0], [1,1110,110,11010,10,10100,100,1000,0] ... und so weiter.

I guess (and almost can prove) that in this way you generate all (and only) primitive maximal words of any length (let us say that a maximal word is primitive if it is not the repetition of a shorter one).

Has anybody a nice proof of this?

Question 3: is there an asymptotic distribution for the lengths of primitive maximal words generated by n runs of the prvious algorithm?

Answer 1

I can answer your first question fully, and the second question only partially.

Question 1: Assuming you meant $\log_2$ in your expression, the answer is $h=1$. That is because $w(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}\geq \frac{1}{n}2^n$ by just considering the first summand, and $w(n)=\frac{1}{n}\sum_{d|n}\phi(d)2^{n/d}\leq n 2^n$ by upper-bounding the number of summands to be $n$ each at most $n2^n$.

Question 2: I'm afraid not all necklaces are generated by your method. Continue two more steps to notice the only two full-period necklaces of length $6$ you produce are $111110$ and $100000$.

Answer 2

A first hint for Question 1. The Dirichlet generating function of the sequence $w(n)$, according to the arithmetic convolution formula quoted in the link, is $$f(s):=\sum_{k=1}^\infty\frac{ w(n)}{n^s}= \frac{\zeta(s+1)}{\zeta(s)}\mathrm{Li}_{s+1}(2).$$ Asymptotics on the coefficients $w(n)$ should come from the study of $f(s)$. Maybe somebody here around has the know-how to do it quickly.