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

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.

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

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

Voici un premier énoncé :

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

Par exemple, le mot ${\displaystyle 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 ${\displaystyle 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.

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

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

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

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

Là aussi, les auteurs ajoutent que l'énoncé est faux si ${\displaystyle 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 ${\displaystyle a_{n}}$ et ${\displaystyle b_{n}}$ sont des nombres réels. On peut aussi supposer que ${\displaystyle a_{n}=b_{n}}$ pour ${\displaystyle n=0,1,\ldots ,p+q-\operatorname {pgcd} (p,q)}$, car si ${\displaystyle a_{n}=b_{n}}$ pour ${\displaystyle n\geq n_{0}}$, alors la périodicité des suites implique que ${\displaystyle a_{n}=b_{n}}$ pour tout ${\displaystyle 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

${\displaystyle F(X)=\sum _{n\geq 0}a_{n}X^{n}\ }$ et ${\displaystyle \ G(X)=\sum _{n\geq 0}b_{n}X^{n}}$.

Par la périodicité, on a

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

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

${\displaystyle 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 ${\displaystyle R(X)}$ de degré au plus ${\displaystyle p+q-\operatorname {pgcd} (p,q)-1}$. Si les ${\displaystyle p+q-\operatorname {pgcd} (p,q)}$ premiers coefficients de ${\displaystyle H(X)=F(X)-G(X)}$ sont nuls, alors le polynôme ${\displaystyle R(X)}$ est identiquement nul, donc ${\displaystyle F=G}$.

L'article original de Fine et Wilf contient deux autres résultats, voisins du premier :

et

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.

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

${\displaystyle w=u_{1}\cdots u_{n}t}$,

où ${\displaystyle 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 ${\displaystyle 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|≥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.

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.

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

• Portail de l'informatique théorique
• Portail des mathématiques