Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

Proof: Let $w (- D$ and $f (w) = a$ . First, we prove that $a$ and its shift $d(a)$ are images of words that are cyclic shifts of one another. There are two cases $' a = aa$ and $' a = ba$ depending on the first symbol of $a$ . We put $' ' ' (u ,v ) = a (e,e)$ .

In the first case, $' ' ' d(a)(e,e) = aa(e,e) = (3u ,3v)$ . Proposition 5 gives $' ' ' ' ' a a(e,e) = a (3,3) = a (e,e).(3,3) = (u3,v 3)$ . Thus $' ' ' aa = f(3u3v )$ and $' ' ' a a = f(u 3v 3)$ are images of cyclic shifts of one another.

In the second case, $' ' ' ba (e,e) = (v ,2u )$ . Since $|a| b$ is odd, $' |a |b$ is even, so that proposition 5 gives $' ' ' ' ' d(a)(e,e) = ab(e,e) = a(e,2) = a (e,e).(e,2) = (u ,v2)$ . As before, $' ' ' ba = f(v2u )$ and $' ' ' a b = f(u v2)$ are images of cyclic shifts of one another.

For the converse part, the difficulty is that $a(w)$ not necessarily belongs to $D$ for all $w (- D$ . We can prove that for $w (- D$ and $r > 0$ being the least integer such that $r a (w) (- D$ , the images of $w$ and $r a (w) (- D$ are cyclic shifts of one another. The proof is a little long though straightforward and we leave it to the interested reader. $[]$

Example 3 Note that proposition 7 is only true for words such that $' |f(w)| b = |f(w )| b$ is odd. If $' |f(w)| b = |f(w )| b$ is even, the proposition is false. Indeed, one has

bba(e,e) = bb(3,3) = b(3,23) = (23,23) bab(e,e) = ba(e,2) = b(3,32) = (32,23),

so that $bba = f(2323)$ , $bab = f(3223)$ , but $2323$ and $3223$ are not cyclic shifts of one another. On the contrary, one has

bbba(e,e) = b(23,23) = (23,223) bbab(e,e) = b(32,23) = (23,232),

so that $bbba = f(23223)$ , $bbab = f(32232)$ , and $23223$ and $32232$ are cyclic shifts of one another.

The problem in the computation of words satisfying the rhythmic oddity property is that cyclic shifts of one another are considered as the same solution, since they correspond to rhythmic patterns repeated as a loop.

The conjugacy relation on words is the equivalence between words being cyclic shifts of one another, and the classes of conjugate elements are the orbits of the permutation $d$ . Lyndon words are minimal elements in the conjugacy classes regarding the lexicographic order, with the additional condition that they are primitive (words of length $n$ , which have exactly $n$ different cyclic shifts).

They can be computed efficiently in a recursive way thanks to the fact that Lyndon words not reduced to a single letter can be factorized into shorter Lyndon words $lm$ such that $l < m$ for the lexicographic order Lothaire (1983). For instance, the Lyndon word $aababb$ can be factorized into $(aab)(abb)$ .

Lyndon words provide a powerful tool for enumerating repetitive musical structures. It is sometimes convenient to replace $A*$ by a smaller set $f(A*)$ with an ad hoc mapping $f$ . The enumeration of words satisfying the rhythmic oddity property illustrates the same method, which relies on the following simple set theoretic proposition.