MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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. – Sam Nead Sep 27 '10 at 10:11
As for question 2 - you are producing the Farey words, not the Lyndon words. For example, you never produce 1100. – Sam Nead Sep 27 '10 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? – ccarminat Sep 27 '10 at 10:53
up vote 3 down vote accepted

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$.

share|cite|improve this answer
Your are right on both issues. I was wandering if one can modify the algorithm to generate all possible primitive maximal words: probably one should consider concatenation between an item of the list and any 'smaller' item (where 'smaller' is referred to the order we get considering these finite words as periods of infinite words which are ordered with the usual lexicographic ordering). – ccarminat Sep 27 '10 at 10:25
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. – Sam Nead Sep 27 '10 at 10:38
Another paper which might be of interest to you is "On the Generation of Aperiodic and Periodic Necklaces via T-augmentation" by Gulliver, Makwakwa, and Speidel. – Moshe Schwartz Sep 27 '10 at 11:13

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.