Imparité rythmique

Condition suffisante.  Chaque suffixe de longueur $l + 1 = (2l + 1) - l$ a une hauteur égale à $2h - (h - 2) = h + 2$ ou $2h - (h - 1) = h + 1$. Pour tout entier $i$ le préfixe de longueur $l + 1$ du mot conjugué $\delta^i(m)$ est égal au suffixe de longueur $l + 1$ du mot conjugué $\delta^{i + l + 1}(m)$. Ainsi les préfixes de longueur $l$ ont une hauteur inférieure à $h$ et les préfixes de longueur $l + 1$ ont une hauteur supérieure à $h$. Il n'existe donc aucun préfixe de hauteur $h$ et le mot rythmique $m$ est impair.

Condition nécessaire.  Commençons par établir deux propriétés intermédiaires satisfaites lorsque le mot $m$ est impair. Notons $L$ la longueur de $m$.

(1) Soient deux entiers $\lambda$ et $n$ tels que $0 \leq \lambda < L$ et $0 \leq n$. Si le préfixe de longueur $\lambda$ du mot $\delta^n(m)$ a une hauteur égale à $h - 1$ ou $h-2$ alors le préfixe de longueur $\lambda$ du mot $\delta^{n+1}(m)$ a une hauteur égale à $h - 1$ ou $h - 2$.

Preuve de (1).  Posons $m' = \delta^n(m) = x_0 x_1 \ldots x_{L-1}$. Le préfixe $p'$ de longueur $\lambda$ du mot $m'$ est égal à $x_0 x_1 \ldots x_{\lambda - 1}$. Le mot $m'' = \delta^{n+1}(m)$ est égal à $x_1 x_2 \ldots x_{L-1} x_0$ et son préfixe $p''$ de longueur $\lambda$ est égal à $x_1 x_2 \ldots x_{\lambda - 1} x_\lambda$. La hauteur $h'$ du préfixe $p'$ et la hauteur $h''$ du préfixe $p''$ sont reliés par l'égalité $h'' = h' - x_0 + x_\lambda$. Puisque chacune des valeurs $x_0$ et $x_\lambda$ est égale à 2 ou 3, la valeur de $-x_0 + x_\lambda$ est égale à -1, 0 ou 1. Il s'ensuit, puisque la valeur de $h'$ est égale à $h - 2$ ou $h - 1$, que $h''$ est égal à $h - 3$, $h - 2$, $h - 1$ ou $h$. La valeur $h$ est exclue car, le mot $m''$ étant impair, son préfixe $p''$ ne peut être de hauteur égale à $h$. Pour que $h''$ soit égal à $h - 3$ il faut que les termes $h'$ et $-x_0 + x_\lambda$ de l'égalité $h'' = h' + (-x_0 + x_\lambda)$ soient tels que $h' = h - 2$ et $-x_0 + x_\lambda = -1$. La dernière égalité est réalisée seulement si $x_0 = 3$ et $x_\lambda = 2$. Mais alors le préfixe $p = x_0 x_1 \ldots x_{\lambda - 1} x_\lambda$ a pour hauteur $h' + x_\lambda = h$, ce qui est interdit. Il ne reste donc que les valeurs permises $h - 1$ et $h - 2$ pour $h''$.

(2) Le mot $m$ admet un préfixe $p$ de hauteur égale à $h - 1$ ou $h -2$.

Preuve de (2).  Posons $m = x_0 x_1 \ldots x_{L-1}$. Les hauteurs des préfixes successifs de $m$ croissent de 0 à $2h$ lorsque la longueur croît de 0 à $L$. Soit $\lambda$ l'entier maximal tel que le préfixe $m' = x_0 x_1 \ldots x_{\lambda - 1}$ soit de hauteur $h'$ inférieure à $h$. Le préfixe $m''$ obtenu en ajoutant $x_\lambda$ à la fin de $m'$ est de hauteur $h'' > h$. On a donc $x_\lambda = h'' - h' > h - h' > 0$. Il s'ensuit que $h - h'= 1$ ou $h - h'= 2$ puisque $x_\lambda = 2$ ou $x_\lambda = 3$.

Fin de la preuve de la condition nécessaire. Soit $\lambda$ la longueur du préfixe $p$ défini dans la propriété (2). La propriété (1) entraine que le préfixe de longueur $\lambda$ de tout mot conjugué de $m$ a une hauteur égale à $h - 1$ ou $h-2$. Considérons le mot concaténé $m' = m p$, de longueur $L + \lambda$, et le préfixe $q$ de longueur $2 \lambda$ du mot $m'$. Le préfixe $q$ est la concaténation du préfixe $p$ avec le préfixe de longueur $\lambda$ du mot $\delta^\lambda(m)$. Puisque chacun de ces préfixes a une hauteur égale à $h - 1$ ou $h - 2$ le mot $q$ a une hauteur $H$ telle que

(3) $2h - 4 \leq H \leq 2h - 2$.

Notons pour la suite que si l'égalité $H = 2h - 4$ est réalisée alors $p$ est de hauteur $h - 2$.

Cas 1 :  $L \leq 2 \lambda$. Alors $m$, qui est de longueur $L$, est un préfixe de $q$, qui est de longueur $2 \lambda$. Il s'ensuit que la hauteur de $m$ est au plus égale à celle de $q$, soit $2h \leq H$, qui contredit (3).

Cas 2 : $2 \lambda \leq L - 2$. Alors $q$ est un préfixe de $m$. En outre puisque la différence des longueurs de $m$ et $q$ est au moins égale à 2, les deux derniers termes de $m$, soit $x_{L-2}$ et $x_{L-1}$, ne sont pas dans $q$. La hauteur de $q$ est donc telle que

(4) $H \leq 2h - x_{L-2} - x_{L-1} \leq 2h - 4$.

Compte tenu de (3) il vient $H = 2h - 4$. L'égalité $H = 2h - 4$ est réalisée dans (3) seulement si la hauteur du préfixe $p$ est égale à $h - 2$. L'égalité $H = 2h - 4$ est réalisée dans (4) seulement si $x_{L-2} = x_{L-1} = 2$. Mais alors $x_{L-1} p$, qui est un préfixe de $\delta^{-1}(m)$, a une hauteur égale à $h$, ce qui est interdit pour le mot impair $m$. Les cas 1 et 2 étant exclus il vient $2 \lambda = L - 1$, ce qui achève la preuve de la condition nécessaire.