Suites réductibles et reproductibles 

Suites réductibles et reproductibles 

Automates sigma-polynomiaux agissant sur des suites pério diques 5.1.1 Les suites périodiques et automates Ons’intéresse aux suites périodiques à valeurs dans ZN, où ZN = Z/NZ. Les résul tats de cette partie se généralisent à tout groupe abélien fini (A,+). Définition 102 (Suite-périodique). Soit i Z, x(i) = x(i+ ),i.e x = x. 1, une suite x est dite-périodique si pour tout Onnote CN l’ensemble des suites-périodiques et à valeurs dans ZN. Ondéfinit à présent la fonction donnant la période minimale d’une suite : Définition 103 (La fonction période).

On définit la fonction : ZZ N x N (x) := min avec la convention usuelle min := . 1/ x =x Si x est-périodique alors (x) : n’est pas forcément la période minimale. On peut donc dire que CN = x ZZ N/ (x) .Quandondésigne la période minimale (x), on dira que la période de x est ou que x est de période . On définit l’ensemble des suites de période par PN := x ZZ N/ (x) = .BienévidemmentPN CN. Propriété 11.

Soit x et y ZZ N périodiques. (x +y)PPCM( (x), (y)). Si (x) et (y)sont premiers entre eux alors (x+y) = (x). (y) 102 Démonstration. Soit m := PPCM( (x), (y)) = min — xetydeuxsuites dans ZZ N. 1/ (x) et (y) .Doncilexistek1 et k2 entiers tels que m = k1 (x) = k2 (y), et m (x +y) = m(x)+ m(y) =x =y = k1 (x)x + =x+y. Donc (x+y)PPCM( (x), (y)). k2 (y)y — Supposonsàprésentque (x)et (y)soientpremiersentre eux. Soit p 1telque p soit diviseur premier de (x) (y). On constate que p divise (x) ou (y) mais pas les deux, et que := (x) (y) p est multiple de (x) ou (y) mais pas les deux.

On ne peut pas avoir x qui soit-périodique et y qui le soit aussi et vice versa. On peut ainsi trouver i Z tel que x(i+ ) x(i) = 0mais y(i+ ) y(i)= 0 Donc (x+y) = min s N/ s(x+y) = PPCM( (x), (y)) = (x) (y), puisque (x) et (y) sont premiers entre eux. Propriété 12. Soit F Z[ ] et Démonstration. Soit x 1. Si x CN,alors F(x) CN. CN, on remarque simplement que comme F et commutent il =x vient F(x) = F (x) = F (x) = F(x), donc F(x) CN.

Une propriété naturelle découle directement de la propriété 12. Propriété 13. Si x est une suite périodique, alors En particulier la suite Fn(x) F(x) (x). est une suite décroissante pour la relation de divisibilité. nN Nous étudierons l’évolution de la période sous l’action des automates et dans la section 5.3. 

Deux sous groupes importants

Les suites réductibles et reproductibles Nousallons voir à présent deux sous groupes fondamentaux de ZZ N pour cette partie : Définition 104 (Réductibilité). Soit F Z[ ]. Une suite x ZZ N est dite F-réductible si il existe n Ntel que Fn(x) = 0. L’ensemble des suites F-réductibles est noté RedF := ker(Fn), nN 103 et l’ensemble des suites F-réductibles et-périodiques est noté RedF(CN) := CN RedF. Ondéfinit le le temps de réductibilité d’une suite x par tred(x) := min t 0/Ft(x) = 0 .

Onremarque que pour tout t trep(x) on a aussi Ft(x) = 0. Définition105(Reproductibilité). Soit F Z[ ].Unesuite x ZZ N estdite F-reproductible si il existe n 1 tel que Fn(x) = x. L’ensemble des suites reproductibles est noté RepF := ker(Fn id), nN et l’ensemble des suites reproductibles et-périodiques est noté RepF(CN) := CN RepF. Ondéfinit le le temps de reproductibilité d’une suite x par trep(x) := min t 1/Ft(x) = x . Onremarque que pour tout t multiple de trep(x) on a aussi Ft(x) = x. Remarque106.

Pourtout F Z[ ]ettout N,lesensemblesCN,RepF(CN)etRedF(CN) sont des sous-groupes de ZZ N stables par F. RedF est un sous groupe de ZZ N stable par F étant une union croissante des sous groupes ker(Fn) qui sont stables par F. De même RepF est un sous groupe de ZZ N stable par F étant une union croissante des sous groupes ker(Fn! id) qui sont aussi stables par F. Proposition 107. Démonstration. Soit x tout t RedF(CN) \RepF(CN) = RedF \RepF = 0 . RedF \RepF. La réductibilité de x entraîne que Ft(x) = 0 pour tred (x), et la reproducibilité entraîne que Ft(x) = x pour tout t multiple de trep (x). En prenant t à la fois supérieur à tred (x) et multiple de trep (x), on obtient Ft(x) = x =0.