Imparité Rythmique

Soit $2h$ la hauteur du mot $m$.

Condition nécessaire. On sait par le lemme que la longueur de $m$ est impaire, soit $2l + 1$. Le lemme implique que chaque mot $m_i$ de la forme $x_i x_{i+1} \ldots x_{i+l-1}$, $0 \leq i < 2l + 1$, a une hauteur $h_i$ égale à $h - 1$ ou $h - 2$. Lorsque $h_i = h - 2$ on a $x_{i-1} = x_{i+l} = 3$ sinon l'un des mots $m_i$ précédé de $x_{i-1}$ ou suivi de $x_{i+l}$ serait de hauteur $h$, ce qui est interdit. Montrons que l'ensemble $P$ des paires $p_i = \{i-1, i+l\}$ définies pour les mots $m_i$ tels que $h_i = h-2$ est un $l$-appariement de $m$. Puisque $(i - 1) - (i + l) = -l - 1 = l  mod 2l + 1$ il suffit de montrer que $P$ est une partition du sous-ensemble d'indices $\{i : 0 \leq i < 2l + 1, x_i = 3\}$. Pour cela il reste à établir deux propriétés.

(1) Si $p_i = \{i-1, i+l\}$ et $p_j = \{j-1, j+l\}$ sont des paires non disjointes appartenant à $P$, alors ces paires sont égales. C'est évident si $i -1 = j - 1$ ou $i + l = j + l$. Supposons que $j - 1 = i + l$. On a $m_i = x_i x_{i+1} \ldots x_{i+l-1}$ et $m_j = m_{i+l+1} = x_{i+l+1} x_{i+l+2} \ldots x_{i + 2l}$. La concaténation $m_i x_{i+l} m_j$ est égale au mot $\delta^i(m)$. Il s'ensuit $2h = h_i + x_{i+1} + h_j = h - 2 + x_{i+l} + h - 2$, qui est impossible puisque $x_{i+l} \leq 3$. Il est aussi impossible par symétrie que $i - 1 = j + l$. Il ne reste donc que les deux premiers cas et la propriété (1) est démontrée.

(2) Tout indice $k$ tel que $x_k = 3$ est couvert par une paire $p_i$ appartenant à $P$. Considérons les mots $m_{k-l} = x_{k-l} x_{k-l + 1} \ldots x_{k-1}$, $x_k$ et $m_{k+1} = x_{k+1} x_{k+2} \ldots x_{k+l}$. Le mot $\delta^{k-l}(m)$ est égal à la concaténation $m_{k-l} x_k m_{k+1}$. Il s'ensuit que $2h = h_{k-l} + x_k + h_{k+1} = h_{k-l} + h_{k+1} + 3$. Puisque chacune des hauteurs $h_{k-l}$ et $h_{k+1}$ est égale à $h - 1$ ou $h - 2$ l'égalité précédente implique $h_{k-l} = 2$ ou $h_{k+1} = 2$. Dans le premier cas $x_k$ est couvert par la paire $ p_{k-l}$ et dans le second cas $x_k$ est couvert par la paire $p_{k+1}$. Ainsi la propriété (2) est démontrée ainsi que la condition nécessaire.

Condition suffisante.  Nous allons montrer que si le mot $m$ satisfait les conditions du théorème alors il satisfait aussi les conditions du lemme. La condition d'imparité sur la longueur de $m$ étant commune il reste à établir que, pour tout mot conjugué $\delta^i(m) = y_0 y_1 \ldots y_{2l}$, le préfixe $p = y_0 y_1 \ldots y_{l-1}$ a une hauteur égale à $h - 1$ ou $h - 2$. Posons $s = y_l y_{l+1} \ldots y_{2l}$, $a = |\{i : 0 \leq i < l, x_i = 3\}|$ et $b = |\{i : l \leq i \leq 2l, x_i = 3\}|$. La hauteur de $m$ est égale à $2(2l + 1) + a + b $ et la hauteur de $p$ est égale à $2l + a$. Il s'ensuit, en notant $h(p)$ la hauteur de $p$, que

(1) $h(p) = h - 1 \Longleftrightarrow a = b$ et

(2) $h(p) = h - 2 \Longleftrightarrow a = b - 2$.

Cas 1. Chaque paire du $l$-appariement contient un indice $i$ de $p$ tel que $x_i = 3$ et un indice $j$ de $s$ tel que $x_j = 3$. On a donc $a = b$ et il vient $h(p) = h - 1$ d'après (1).

Cas 2. Il existe une paire $\pi$ du $l$-appariement incluse dans $\{0, 1, \ldots, l - 1\}$ ou dans $\{l, l + 1, \ldots, 2l\}$. La première inclusion est impossible car on ne peut pas trouver deux indices de différence égale à $l$ dans l'ensemble $\{0, 1, \ldots, l - 1\}$. La seconde inclusion peut avoir lieu, mais alors on a nécessairement $\pi = \{l, 2l\}$. Toute autre paire du $l$-appariement contient un indice $i$ de $p$ tel que $x_i = 3$ et un indice $j$ de $s$ tel que $x_j = 3$. On a donc $a = b - 2$ et ceci implique $h(p) = h - 2$ d'après (2). La condition suffisante est donc prouvée.