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).

Période 

Soit , avec  des lettres, un mot sur un alphabet . Une période de  est un entier  tel que  pour . Il revient au même de dire que  s'écrit sous la forme , pour un entier positif , où  est un mot de longueur , et  est un préfixe de .

É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,  est la plus petite valeur pour laquelle l'énoncé est vrai.

Par exemple, le mot , 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  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  a deux périodes  et  et est de longueur au moins . Alors on a  avec ,  un préfixe de  et  un préfixe de . Soit  un multiple commun de  et  plus grand que  et ; alors  et  ont tous deux le préfixe , et  et  sont puissance d'un mot  de longueur , et ce nombre est une période de .

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  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  et  sont des nombres réels. On peut aussi supposer que  pour , 
car si  pour , alors la périodicité des suites implique que  pour tout .

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
 et .
Par la périodicité, on a
 et 
pour des polynômes  et de degré au plus  et .
Maintenant, comme le polynôme  divise  et  on a 

pour un polynôme  de degré au plus .
Si les  premiers coefficients de  sont nuls, alors le polynôme  est identiquement nul, donc .

Énoncés complémentaires 
L'article original de Fine et Wilf contient deux autres résultats, voisins du premier :

et

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é :

Variantes 
De nombreuses variantes ont été étudiées, par exemple une extension à plus de deux périodes, à 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 
, 
où  sont de longueur p et commutativement équivalents, et où t est un préfixe d'un mot commutativement équivalent aux . 
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.

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

Bibliographie 
 Article original
 .
 Manuels
  
  
  
  
   
  
En ligne
 .
 .
 .

Articles connexes 
 Complexité combinatoire d'un mot
 Nombre de Fibonacci

Fine et Wilf
Fine et Wilf
Fine et Wilf
Fine et Wilf