3
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sam Nead
    Sep 27, 2010 at 10:11
  • $\begingroup$ As for question 2 - you are producing the Farey words, not the Lyndon words. For example, you never produce 1100. $\endgroup$
    – Sam Nead
    Sep 27, 2010 at 10:34
  • $\begingroup$ @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? $\endgroup$
    – ccarminat
    Sep 27, 2010 at 10:53

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – ccarminat
    Sep 27, 2010 at 10:25
  • $\begingroup$ 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. $\endgroup$
    – Sam Nead
    Sep 27, 2010 at 10:38
  • $\begingroup$ 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. $\endgroup$ Sep 27, 2010 at 11:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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