Mathématiques - Théorème de Fine-Wilf

Théorème de Fine-Wilf
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: jadis

Bonjour.
Dans un exercice qui a pour but de démontrer le théorème de Fine et Wilf, on me demande de montrer que si U est un mot de longueur a+b-1 qui est à la fois a-périodique et b-périodique (et que a et b sont premiers entre eux), on a:
$\forall i, 1 \leq i \leq a+b-2;u_{{x_{{i}}}}=u_{{x_{{i+1}}}}$ où pour $1 \leq i \leq a+b-1$ ,on définit ${x_{{i}}}$ comme le représentant de $ia (mod a+b)$ tel que $1 \leq ia \leq a+b-1$ .

Je ne sais pas si ça peut m'aider mais j'ai déjà constater que $u_{{a-1}}=u_{{b-1}}$ et également que "a barre" et "b barre" sont générateurs de Z/(a+b)Z.

J'ai oublié de préciser que dans la question précédente, j'ai prouvé que la suite ${(ia)_{1 \leq i \leq a+b-1}}$ d'éléments de Z/(a+b)Z prend une fois et une seule fois chaque valeur non nulle.

Merci d'avance pour votre d'aide.

Posted by: jadis

Je me suis mal exprimé?

Posted by: Blueberry

Bonjour,

dans ton énoncé, ce ne serait pas plutôt $x_i$ un représentant de $ia\;mod (a+b-1)$ tel que $1\le x_i \le a+b-1$ ?

Posted by: jadis

non c'est bien mod a+b... mais dans l'inégalité je me suis effectivement trompé, c'est ia... et non i.
Je corrige tout de suite

Posted by: jadis

Etant donné que ça n'a pas l'air d'emballer grand monde, je vais reprendre l'exercice depuis le début.

Citation:

Un mot U de longueur n est une suite ${u_{1}}{u_{2}}...{u_{n}}$ de lettres. On dit qu'il est k-périodique si pour tout i tel que $1 \leq i \leq n-k$ on a ${u_{i}}={u_{i+k}}$ .

Citation:

a)Montrer que si un mot de longueur 4 est à la fois 2-périodique et 3-périodique, il est constant, cad que toutes ses lettres sont égales.

Le mot est 2-périodique donc $\forall i, 1 \leq i \leq 4-2=2,{u_{i}}={u_{i+2}}$ .
donc ${u_{1}}={u_{3}}$ et ${u_{2}}={u_{4}}$ .
Le mot est 3-périodique donc $\forall i, 1 \leq i \leq 4-3=1,{u_{i}}={u_{i+3}}$ .
donc ${u_{1}}={u_{4}}$ .

Donc ${u_{1}}={u_{2}}={u_{3}}={u_{4}}$ .

Donc le mot est constant.

Citation:

b)Soient a et b deux entiers premiers entre eux. Montrer que la suite ${(ia)_{1 \leq i \leq a+b-1}}$ d'éléments de ${\mathbb Z}/(a+b){\mathbb Z}$ prend une fois et une seule chaque valeur non nulle. Pour $1 \leq i \leq a+b-1$ ,on définit ${x_{{i}}}$ comme le représentant de $ia (mod a+b)$ tel que $1 \leq ia \leq a+b-1$ .

Montrons tout d'abord que a et a+b sont premiers entre eux:

Soit d=pgcd(a,a+b)
$\bullet$ On a: d|a et d|(a+b) donc $\forall (m,n) \in {\mathbb Z}^2,d|(am+(a+b)n))$
$\bullet$ On prend m=-1 et n=1
On a d|((a+b)-a)
cad d|b.
$\bullet$ d|a et d|b donc d|pgcd(a,b)=1
donc a et a+b sont premiers entre eux.

On en déduit directement que $\bar{a}$ est générateur du groupe cyclique ${\mathbb Z}/(a+b){\mathbb Z}$ .

Démonstration de la question posée:

La suite ${(ia)_{1 \leq i \leq a+b-1}}$ est une suite d'éléments de ${\mathbb Z}/(a+b){\mathbb Z}$ et possède exactement a+b-1 éléments.

Comme $\bar{a}$ est générateur de ${\mathbb Z}/(a+b){\mathbb Z}$ , ${(ia)_{1 \leq i \leq a+b-1}}$ possède tous les éléments non nuls de ${\mathbb Z}/(a+b){\mathbb Z}$ (puisque a et b sont premiers entre eux donc $a \neq 0$ , et on a $1 \leq i \leq a+b-1$ ).

Pour résumer, la suite possède exactement a+b-1 éléments et possède chaque éléments compris entre 1 et a+b-1 (inclus) donc cette suite prend bien une fois et une seule chaque valeur non nulle de ${\mathbb Z}/(a+b){\mathbb Z}$ .

Citation:

c) Montrer que si U est un mot de longueur a+b-1 qui est à la fois a-périodique et b-périodique, on a $\forall i, 1 \leq i \leq a+b-2;u_{{x_{{i}}}}=u_{{x_{{i+1}}}}$ .
En déduire que U est constant.

Première partie:

JE BLOQUE....

Deuxième partie:

On déduit de la question précédente que $\forall i, 1 \leq i \leq a+b-1;1 \leq x_{i} \leq a+b-1$ donc $\forall i, 1 \leq i \leq a+b-2;u_{i}=u_{i+1}$ .
Toutes les lettres sont égales donc U est constant.

Citation:

d)Démontrer le théorème de Fine et Wilf: Soient a et b deux entiers naturels, et d leur pgcd. Si U est un mot a-périodique et b-périodique de longueur au moins a+b-d, alors u est d-périodique.

Prenons une lettre toutes les d lettres dans U (une lettre sur d). On a alors d mots de longueur a/d +b/d -1 constants d'après la question précédente, ce qui signifie que U est d-périodique puisqu'on a pris une lettre sur d.

Posted by: jadis

Merci Ted!
Je vais essayer de reprendre ton idée qui a l'air excellente!

Maintenant, il ne reste plus qu'à voir si cette égalité à un sens...

Posted by: Ted

J'espere que personne n'a vu ma remarque précédente qui était fausse.
J'avais en fait presque la reponse mais faute de temps je n'ai pas le temps de corriger completement.
Voila l'idée principale je pense:
en fait entre uxi et ux(i+1) il y a un certain nombre d'elements, mais ce nombre est toujours un multiple de a et (c'est la l'astuce..) ceci est vrai que uxi soit placé avant ou apres ux(i+1) dans le mot!

comme il sont separé d'un multiple de a ils sont egaux par la periodicité.
Pour la suite, comme les uxi parcourent toutes les lettres le resultat est immediat comme tu l'a vu.
Pour le theoreme je n'ai pas regarder
Si l'explication ne suffit pas j'y revinedrait peut etre d'ici la fin du week end s'il le faut.

Posted by: jadis

Oula... Ca se complique.
J'ai bien compris la deuxième partie, du fait de la bijection.
Mais je ne vois pas pourquoi il y a un nombre d'éléments multiple de a entre ${x_{{i}}}$ et ${x_{{i+1}}}$ ...
Prenons le cas où $b \lt a$ , on "sort du mot", non?
Ou alors il y a un truc que je ne comprends pas...

Posted by: Ted

ouai en voulant aller trop vite j'ai surement dit une autre betise. Pour etre sur j'vais tout faire a la main:
d'abord faut bien comprendre que la classe de ai, que je noterai [ia] est un ensemble; et xi ,un de ses representants est lui un element de cet ensemble.
alors on écrit:

xi appartient à [ia]={ ia+k(a+b) pour tout k dans z}
de meme
xi+1 appartient à [(i+1)a]={(i+1)a + k'(b+a) k' dans z}

Grace a la question precedente on sait que xi est unique.
Autrement dit il existe un unique ki (car il dépend quand meme de la valeur de i) tel que xi=ia +ki(b+a). Meme chose pour Ki+1 unique pour xi+1.

Or on sait que xi est un indice entre 1 et b+a-1, donc en reprenant l'ecriture precedente

1<= ia +ki(b+a) <= b+a-1
ce qui donne apres bricolage:

(1-ia)/(b+a) <= ki <= (b+a-ia-1)/(b+a)

de meme

(1-a(i+1))/(a+b) <= ki+1 <= (b-ai-1)/(a+b)

en soustrayant,

-1< (-b)/(b+a) <= ki - ki+1 <= 1 +(a-2)/(b+a) <2

donc la difference ki-ki+1 est un entier entre -1 et 2 exclus... Pas trop le choix si ce n'est 0 et 1.

Maintenant si on fait la difference entre xi et xi+1,

xi-xi+1= (a+b) (ki-ki+1) -a

Voyons ce que donne les 2 cas:

si ki-ki+1=0, la difference entre les indices xi et xi+1 est de -a et par periodicité sur a uxi=uxi+1

si ki-ki+1=0, la difference vaut b (xi+1 est alors avant xi dans le mot...) et par la periodicité sur b uxi=uxi+1

Par ailleurs en y regardant de plus pres ta justification de la deuxieme partie est pas tres claire.
Il faut bien remarquer que les indices xi ne sont pas rangés dans un ordre précis, on ne peut donc pas ecrire xi=i ou xi=ai.
On remarque juste que si uxi=uxi+1 pour tout i alors tout les uxi sont égaux comme les xi parcourent tout les indices de 1 à b+a-1 (grace à la bijection) on peut conclure rigoureusement que tout les ui sont égaux

Posted by: jadis

Merci Ted, j'ai bien compris ta méthode.
Mais j'avoue que je n'y aurai jamais pensé...