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

factorization $w = uv$ or $w = vu$ ) such that $h(v''u') = h(u''v')$ . Indeed, one has $h(v'')- h(u'') = h(u') - h(v')+ 2$ , which gives the following computation

h(v''u') = h(u''v') h(v'')- h(u'') = h(v')- h(u') h(u') - h(v')+ 2 = h(v')- h(u') h(v') -h(u') = 1

Thus if $w$ satisfies the rhythmic oddity property, proposition 1 gives $w = uv$ or $w = vu$ with $h(v) = h(u) + 2$ . Then $(u,v)$ must be an asymmetric pair. Conversely, if $w = uv$ or $w = vu$ where $h(v) = h(u)+ 2$ and $(u,v)$ being an asymmetric pair, then no cyclic shift of $w$ can be factorized into words with equal height. $[]$

3 Construction of asymmetric pairs

The following construction is inspired by Rauzy’s rules, which are used to define standard pairs in the construction of characteristic Sturmian words J. Berstel (2001). Consider two functions $a$ and $b$ from $* * A ×A$ into itself defined by

a(u,v) = (3u,3v) b(u,v) = (v,2u)

One has the following proposition.

Proposition 3 The set of asymmetric pairs is equal to the smallest set of pairs of words containing $e× A*$ and $A* × e$ which is closed under $a$ and $b$ .

Proof: Let $F$ denote the smallest set of pairs of words containing $* e× A$ and $* A × e$ closed under $a$ and $b$ , and $P$ the set of asymmetric pairs. We prove $F = P$ by double inclusion. The first inclusion is obvious, since $P$ contains $* e× A$ and $* A × e$ and is closed under $a$ and $b$ . The other inclusion is proved by induction on the integer $|u|+ |v|$ , where $(u,v)$ is an asymmetric pair and $|v|> 0$ . The first case is $' v = 2v$ . Then for each pair of prefixes $(r,s)$ of $u$ and $v$ , one has $' s = 2s$ and $' (s ,r)$ is a pair of prefixes of $' (v,u)$ . If $' h(r) = h(s )+ 1$ , then $h(s) = h(r)+ 1$ . This proves that if $(u,v)$ is an asymmetric pair, then so is $' (v ,u)$ . By induction, $' (v,u)$ belongs to $F$ , which proves that $' (u,v) = b(v ,u)$ belongs to $F$ .

The other case is $' v = 3v$ . Notice that $2$ cannot be the first symbol of $u$ , since $(u,v)$ is an asymmetric pair, which implies that $(2,3)$ cannot be a pair of prefixes of $u$ and $v$ . Thus $' u = 3u$ . Then for each pair of prefixes $(r,s)$ of $u$ and $v$ , one has $' s = 3s$ and $' r = 3r$ where $' ' (r ,s)$ is a pair of prefixes of $' ' (u ,v)$ . If $' ' h(s ) = h(r)+ 1$ , then $h(s) = h(r)+ 1$ . This proves that if $(u,v)$ is an asymmetric pair, then so is $' ' (u ,v)$ . By induction, $' ' (u ,v )$ belongs to $F$ , which proves that $' ' (u,v) = a(u ,v )$ belongs to $F$ . $[]$

Considering the free monoid $* B$ on the alphabet $B = {a,b}$ , we identify the concatenation with the composition of functions. Thus any word of $* B$ is identified with a function from $* * A × A$ into itself. It is easy to prove by induction the following properties.