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

Article principal : combinatoire des mots.

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},\ldots ,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,\ldots ,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é :

Théorème — Soit $w$ un mot qui possède deux périodes $p$ et $q$ . Si $|w|\geq p+q-\operatorname {pgcd} (p,q)$ , alors $\operatorname {pgcd} (p,q)$ est une période de $w$ .

De plus, $p+q-\operatorname {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 :

Théorème — Soient $u$ et $v$ deux mots, et supposons que les mots $u^{h}$ et $v^{k}$ , pour des entiers positifs $h$ et $k$ , ont un préfixe commun de longueur $|u|+|v|-\operatorname {pgcd} (|u|,|v|)$ . Alors $u$ et $v$ sont puissances d'un mot $z$ de longueur $\operatorname {pgcd} (|u|,|v|)$ .

Le premier énoncé implique clairement le deuxième. Réciproquement^[1], supposons le deuxième énoncé vrai et que $w$ a deux périodes $p$ et $q$ et est de longueur au moins $p+q-\operatorname {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 $\operatorname {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 :

Théorème (variante) — Soient $u$ et $v$ deux mots, et supposons qu'il existe deux mots de $u\{u,v\}^{*}$ et $v\{u,v\}^{*}$ qui ont un préfixe commun de longueur $|u|+|v|-\operatorname {pgcd} (|u|,|v|)$ . Alors $u$ et $v$ sont puissances d'un mot $z$ de longueur $\operatorname {pgcd} (|u|,|v|)$ .

Troisième énoncé

Une autre formulation est l'énoncé original de l'article de Fine et Wilf^[2] :

Théorème (énoncé original) — Soient $(a_{n})_{n\geq 0}$ et $(b_{n})_{n\geq 0}$ deux suites périodiques, respectivement de période $p$ et $q$ . Si $a_{n}=b_{n}$ pour $p+q-\operatorname {pgcd} (p,q)$ entiers consécutifs, alors $a_{n}=b_{n}$ pour tout $n$ .

Là aussi, les auteurs ajoutent que l'énoncé est faux si $p+q-\operatorname {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,\ldots ,p+q-\operatorname {pgcd} (p,q)$ , car si $a_{n}=b_{n}$ pour $n\geq 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\geq 0}a_{n}X^{n}\

et

\ G(X)=\sum _{n\geq 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^{\operatorname {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^{\operatorname {pgcd} (p,q)}}{(1-X^{p})(1-X^{q})}}R(X)

pour un polynôme $R(X)$ de degré au plus $p+q-\operatorname {pgcd} (p,q)-1$ . Si les $p+q-\operatorname {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 :

Théorème — Soient f(x) et g(x) deux fonctions périodiques continues de périodes a et b respectivement, où a/b est un nombre rationnel de la forme a/b=p/q avec p et q premiers entre eux. Si f(x)=g(x) sur un intervalle de longueur a+b-b/q, alors f=g. Le résultat est faux si a+b-b/q est remplacé par une valeur plus petite.

et

Théorème — Soient f(x) et g(x) deux fonctions périodiques continues de périodes a et b respectivement, où a/b est un nombre irrationnel. Si f(x)=g(x) sur un intervalle de longueur a+b, alors f=g. Le résultat est faux si a+b est remplacé par une valeur plus petite.

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é^[3] :

Pour tout mot w, il existe un mot v de même longueur sur un alphabet binaire qui a le même ensemble de périodes.

Variantes

De nombreuses variantes ont été étudiées, par exemple une extension à plus de deux périodes^[4]^,^[5], à plusieurs dimensions^[6], et à des périodes abéliennes^[7]. 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},\ldots 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.

Soient $p, q >1$ deux entiers premiers entre eux. Si un mot $w$ possède deux périodes abéliennes $p$ et $q$ avec $| w |\geq pq$ , alors $w$ est puissance d’une lettre..

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.

Notes et références

↑ Ziosilvio, « Fine and Wilf’s theorem on words », sur planetmath.org, 2013.
↑ Fine et Wilf 1965.
↑ Voir par exemple Carton 2008, Th. 1.12.
↑ Gabriella Castelli, Filippo Mignosi et Antonio Restivo, « Fine and Wilf’s theorem for three periods and a generalization of Sturmian words », Theoretical Computer Science, vol. 218,‎ 1999, p. 83-94.
↑ R. Tijdeman et L. Zamboni, « Fine and Wilf words for any periods », Indag. Math N.S., vol. 14, n^o 1,‎ 2003, p. 135-147.
↑ Filippo Mignosi, Antonio Restivo et Pedro V. Silva, « On Fine and Wilf’s theorem for bidimensional words », Theoretical Computer Science, vol. 292,‎ 2003, p. 245–262.
↑ Juhani Karhumäki, Svetlana Puzynina et Aleksi Saarela, « Fine and Wilf's theorem for k-abelian periods », Int. J. Found. Comput. Sci., World Scientific, vol. 24, n^o 7,‎ novembre 2013, p. 1135-1152 (ISSN 0129-0541, DOI 10.1142/s0129054113400352, résumé).

Bibliographie

Article original

Nathan J. Fine et Herbert S. Wilf, « Uniqueness theorems for periodic functions », Proceedings of the American Mathematical Society, American Mathematical Society (AMS), vol. 16, n^o 1,‎ 1^er janvier 1965, p. 109-109 (ISSN 0002-9939, DOI 10.1090/s0002-9939-1965-0174934-9, lire en ligne).

Manuels

M. Lothaire, Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. « Encyclopedia of Mathematics and its Applications » (n^o 17), 1983, 238 p. (ISBN 978-0-201-13516-9, présentation en ligne) — Une seconde édition révisée est parue chez Cambridge University Press, dans la collection Cambridge Mathematical Library, en 1997, (ISBN 978-0-521-59924-5) — Prop.1.3.5, page 10
M. Lothaire, Algebraic combinatorics on words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2002, 504 p. (ISBN 978-0-521-81220-7, MR 1905123, lire en ligne) — Th. 8.1.4, page 272
(en) Jean-Paul Allouche et Jeffrey O. Shallit, Automatic sequences : Theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3, MR 1997038, zbMATH 1086.11015) — Th. 1.5.6
Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009, 240 p. (ISBN 978-0-521-86572-2 et 0521865727) — Th. 2.3.5
Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, présentation en ligne) — Th. 1.11
(en) Béla Bollobás, The Art of Mathematics : Coffee Time in Memphis, Cambridge, Cambridge University Press, 2006, 386 p. (ISBN 978-0-521-69395-0 et 0521693950) — Problèmes 314 et 315

En ligne

Ziosilvio, « Fine and Wilf’s theorem on words », sur planetmath.org, 2013.
uncuhd, « The Fine-Wilf Theorem », Uniformly at random, sur Blog at wordpress.com, 2009.
Thierry Lecrocq, « Combinatoire des mots », Mastère 1, Université de Rouen.

Articles connexes

[1] Ziosilvio, « Fine and Wilf’s theorem on words », sur planetmath.org, 2013.

[2] Fine et Wilf 1965.

[3] Voir par exemple Carton 2008, Th. 1.12.

[4] Gabriella Castelli, Filippo Mignosi et Antonio Restivo, « Fine and Wilf’s theorem for three periods and a generalization of Sturmian words », Theoretical Computer Science, vol. 218,‎ 1999, p. 83-94.

[5] R. Tijdeman et L. Zamboni, « Fine and Wilf words for any periods », Indag. Math N.S., vol. 14, n^o 1,‎ 2003, p. 135-147.

[6] Filippo Mignosi, Antonio Restivo et Pedro V. Silva, « On Fine and Wilf’s theorem for bidimensional words », Theoretical Computer Science, vol. 292,‎ 2003, p. 245–262.

[7] Juhani Karhumäki, Svetlana Puzynina et Aleksi Saarela, « Fine and Wilf's theorem for k-abelian periods », Int. J. Found. Comput. Sci., World Scientific, vol. 24, n^o 7,‎ novembre 2013, p. 1135-1152 (ISSN 0129-0541, DOI 10.1142/s0129054113400352, résumé).

[1]

[2]

[3]

[4]

[5]

[6]

[7]