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?

• A request - It would be easier to understand your questions if you used the standard convention of $0 < 1$ and looked at lex-minimal words under rotation. The aperiodic such words are called the Lyndon words. Sep 27, 2010 at 10:11
• As for question 2 - you are producing the Farey words, not the Lyndon words. For example, you never produce 1100. Sep 27, 2010 at 10:34
• @Sam Nead I did not use the word "Lyndon words" because, when the finite word case is considered, the usual definition of order does not coincide with the order I am interested in. "Farey words" sounds great! In fact I got this algorithm out of a problem concerning continued fractions. Do you have some reading to suggest? Sep 27, 2010 at 10:53

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$.
• You perhaps will be interested in Duval's CAT algorithm for producing all Lyndon words with length $n$ or less. See the paper "Average cost of Duval's algorithm for generating Lyndon words" by Berstel and Pocchiola. Sep 27, 2010 at 10:38
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.