Théorème de périodicité de Fine et Wilf

Modèle:Article principal En mathématiques, en informatique théorique, et notamment en combinatoire des mots, le théorème de Fine et Wilf est un résultat classique sur les périodes d'un mot. Il est nommé ainsi d'après les mathématiciens Nathan Fine et Herbert Wilf qui l'on démontré en 1965. On le trouve aussi sous la dénomination théorème de périodicité de Fine et Wilf ou théorème de Fine et Wilf sur les mots.

Le théorème de Fine et Wilf indique la longueur maximale exacte que peut avoir un mot avec deux périodes p et q sans avoir le plus grand commun diviseur de p et q comme une période. Cette valeur est p + q - pgcd(p,q)-1.

Période

Soit $w=a_1{a}_2\cdots a_n$, avec $a_1,\dots ,a_n$ des lettres, un mot sur un alphabet $A$. Une période de $w$ est un entier $p>0$ tel que $a_{i+p}=a_i$ pour $i=1,\dots ,n-p$. Il revient au même de dire que $w$ s'écrit sous la forme $w=u^{k}v$, pour un entier positif $k$, où $u$ est un mot de longueur $p$, et $v$ est un préfixe de $u$.

Énoncés

Le théorème de Fine et Wilf peut s'énoncer de plusieurs manières équivalentes.

Premier énoncé

Voici un premier énoncé :

De plus, $p+q-\mathrm{pgcd}(p,q)$ est la plus petite valeur pour laquelle l'énoncé est vrai.

Par exemple, le mot $aaabaaa$, de longueur 7, a les périodes 4, 5 (et 6), mais n'a pas la période pgcd(4,5)=1, et sa longueur est 7<4+5-1=8. Un autre exemple est un mot de Fibonacci comme le mot $abaababaaba$ de longueur 11 qui possède les périodes 5 et 8 et pas la période 1 : il est de longueur 11<5+8-pgcd(5,8)=12. De fait, tous les mots sturmiens centraux sont des exemples où la borne de l’énoncé est atteinte.

L'énoncé peut aussi être exprimé de façon contraposée comme suit : Soit w un mot qui a deux périodes p et q, sans que pgcd(p,q) ne soit une période. Alors w est de longueur au plus p+q−pgcd(p,q)−1.

Deuxième énoncé

Le théorème peut aussi être énoncé sous la forme suivante :

Le premier énoncé implique clairement le deuxième. Réciproquement, supposons le deuxième énoncé vrai et que $w$ a deux périodes $p$ et $q$ et est de longueur au moins $p+q-\mathrm{pgcd}(p,q)$. Alors on a $w=u^{k}r=v^{h}s$ avec $|u|=p,|v|=q$, $r$ un préfixe de $u$ et $s$ un préfixe de $v$. Soit $M$ un multiple commun de $p$ et $q$ plus grand que $p,q,$ et $|w|$; alors $u^{M/p}$ et $v^{M/q}$ ont tous deux le préfixe $w$, et $u$ et $v$ sont puissance d'un mot $z$ de longueur $\mathrm{pgcd}(p,q)$, et ce nombre est une période de $w$.

Les hypothèses de l'énoncé précédent peut être affaiblies sans modification de la conclusion comme suit :

Troisième énoncé

Une autre formulation est l'énoncé original de l'article de Fine et Wilf :

Là aussi, les auteurs ajoutent que l'énoncé est faux si $p+q-\mathrm{pgcd}(p,q)$ est remplacé par une valeur plus petite.

La démonstration originale que voici a bénéficié, d'après les auteurs, d'une formulation de Ernst G. Straus. On peut supposer que les $a_n$ et $b_n$ sont des nombres réels. On peut aussi supposer que $a_n=b_n$ pour $n=0,1,\dots ,p+q-\mathrm{pgcd}(p,q)$, car si $a_n=b_n$ pour $n\ge n_0$, alors la périodicité des suites implique que $a_n=b_n$ pour tout $n$.

La périodicité des suites s’exprime par une forme particulière de leurs séries génératrices. On définit des séries formelles

$F(X)=\sum _{n\ge 0}{a}_n{X}^n$ et $G(X)=\sum _{n\ge 0}{b}_n{X}^n$.

Par la périodicité, on a

$F(X)=P(X)/(1-X^p)$ et $G(X)=Q(X)/(1-X^q)$

pour des polynômes $P(X)$ et$Q(X)$ de degré au plus $p-1$ et $q-1$. Maintenant, comme le polynôme $1-X^{\mathrm{pgcd}(p,q)}$ divise $1-X^p$ et $1-X^q$ on a

$H(X)=F(X)-G(X)=\frac{(1-X^q)P(X)-(1-X^p)Q(X)}{(1-X^p)(1-X^q)}=\frac{1-X^{\mathrm{pgcd}(p,q)}}{(1-X^p)(1-X^q)}R(X)$

pour un polynôme $R(X)$ de degré au plus $p+q-\mathrm{pgcd}(p,q)-1$. Si les $p+q-\mathrm{pgcd}(p,q)$ premiers coefficients de $H(X)=F(X)-G(X)$ sont nuls, alors le polynôme $R(X)$ est identiquement nul, donc $F=G$.

Énoncés complémentaires

L'article original de Fine et Wilf contient deux autres résultats, voisins du premier : Modèle:Théorème et Modèle:Théorème

Structure des périodes

Le théorème de Fine et Wilf répond à l'observation que toutes les périodes d'un mot ne sont pas multiples de la plus petite période, en constatant que les « grandes » périodes ne sont pas de cette forme. La structure des périodes a été étudié notamment par Guibas et Odlysko qui ont prouvé : Modèle:Énoncé

Variantes

De nombreuses variantes ont été étudiées, par exemple une extension à plus de deux périodesModèle:,, à plusieurs dimensions, et à des périodes abéliennes. Deux mots u et v sont dits commutativement équivalents s'ils contiennent chacune le même nombre d'occurrences de chaque facteur. Ainsi, aabbb, babab, bbbaa sont commutativement équivalent. Un mot w possède une période abélienne de longueur p s’il se factorise en

$w=u_1\cdots u_{n}t$,

où $u_1,\dots u_n$ sont de longueur p et commutativement équivalents, et où t est un préfixe d'un mot commutativement équivalent aux $u_i$. L’entier p est une appelé une période abélienne de w (ou période abélienne initiale). Par exemple, le mot babaaabaabb possède les périodes abéliennes 5, 7,...,11, mais pas 6 parce que baabb possède 3 occurrences de b et n'est donc pas facteur abélien de babaaa. Modèle:Énoncé

De plus, des majorations sur la longueur de w existent, mais dans le cas où p et q ne sont pas premiers entre eux, il peut ne pas avoir de majorant. Ainsi, le mot infini

aabbbabababa...

a les périodes abéliennes 4 et 6, mais n'a pas la période 2.

Bibliographie

Article original

• Modèle:Article.

Manuels

• Modèle:OuvrageModèle:Commentaire biblio SRL Modèle:Commentaire biblio SRL
• Modèle:Ouvrage Modèle:Commentaire biblio SRL
• Modèle:Ouvrage Modèle:Commentaire biblio SRL
• Modèle:Ouvrage Modèle:Commentaire biblio SRL
• Modèle:Ouvrage Modèle:Commentaire biblio SRL
• Modèle:Ouvrage Modèle:Commentaire biblio SRL

En ligne

• Modèle:Lien web.
• Modèle:Lien web.
• Modèle:Lien web.

Articles connexes

• Complexité combinatoire d'un mot
• Nombre de Fibonacci