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

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}$.