uNIVERSITÉ DI AIX - MARSEaLE fi - LUMINY
THÈSE
présentée
pour l'obtention du
DOCTORAT DE MATHÉMATIQUES
(3 e CYCLE)
soutenue par
Théodore
TAPSOBA
le 1er octobre 1987, devant le Jury :
Président:
Gérard RAUZY
Examinateurs:
Pierre LIARDET
Christian SAMllEL
Monsieur RAUZY, professeur à l'Université d'Aix-Marseille II m'a fait l'honneur de diriger mes
travaux de recherche et par les nombreux conseils qu'il n'a cessé de me prodiguer et sa totale
disponibilité, a toujours montré à mon égard une bienveillante attention. Au delà des remerciements
d'usage, je tiens à lui exprimer ici ma très profonde gratitude et ma respectueuse reconnaissance.
Monsieur LIARDET, professeur à l'Université d'Aix-Marseille 1 a bien voulu s'intéresser à
mon travail et n'a ménagé ni ses suggestions et ses conseils ni son temps. Qu'il trouve ici
l'expression de toute ma gratitude.
Je remercie particulièrement Monsieur SAMUEL, maître de conférence à l'Université
d'Aix-Marseille II qui a bien voulu porter son attention sur cette thèse et accepter de participer au
jury d'examen.
Je remercie également Monsieur SMADJA de J'Université d'Aix-Marseille II pour les
indications en informatique qu'il m'a donné.
Je remercie enfm Madame LIARDET qui a mené à bien la réalisation matérielle de ce mémoire.
: ~.;.
TABLE DES MATIÈRES
RESUME
(i)
1· INTRODUCfION
1.- Mots infinis
1
2.- Définitions et notations
3
3.- Résultats
6
ll.- MINlMALITE
1.- Système symbolique d'un mot infini
8
2.- Mots minimaux
8
lll- COMPLEXITE DU LANGAGE
1.- Le Théorème d'unicité
12
2.- Commutation
15
3.- Majoration des facteurs puissances
17
4.- Démonstration du Théorème 1 pour deux lettres
20
5.- Démonstration du Théorème 1 dans le cas
général
22
IV.- CALCUL AUTOMATIQUE
1.- Automates
26
2.- Etude des Fn(n)
27
3.- Fin de la démonstration du Théorème 3
30
4.- Complexité polynômiale
31
v.- EXEMPLES
1.- Suite de Morse
32
2.- Suite de Rudin-Shapiro
34
•
,01
.. -. '.>
VI.- UN EXEMPLE NON MINIMAL
36
BmLIOGRAPHIE
40
THÈSE de 3e Cycle
na.thémattque
par Théodore TAPSOBA
RÉSUMÉ
Soit a
un alphabet d'un nombre fini de lettres 1,2,... ,q. Une suite finie m:==
m1mZ .. ,mk de k lettres dans a est appelée mot (fini) sur a de longueur 1 m 1 :== k.
L'ensemble a* de ces mots est regardé comme le monoïde libre engendré sur a. Un mot infini
u :== uOu u u
l Z 3'" sur a
est une suite
u: IN ~ a ; l'ensemble des mots infinis est noté a 00 •
L'ensemble rt(a) :== aoou a* est muni de la distance ultramétrique habituelle qui fait de rt(a)
un espace compact (avec a* sous-ensemble dense). Soit S le shift s'ur a oo qui consiste à effacer
la première lettre. Pour un mot infini u donné, la fermeture Ku de l'ensemble {Sku ; k E IN } est
invariante par S. Le couple (S, KU> est appelé système symbolique associé à u. Un mot fini m :==
m1ffiz...mk est ditfacteur d'un mot u (fini ou pas) s'il existe r tel que
L'ensemble des facteurs de u de longueur k est noté Fk(u). La suite k ~ card(Fk(u» donne une
bonne indication sur la complexité du langage de u ainsi que, dans une large mesure, du système
dynamique qui lui est associé.
Une substitution f sur a est une application f: a ~ a* que l'on prolonge de
manière naturelle en une application continue de n(a) , encore notée f et définie par
La substitution est dite uniforme de module p si p == 1 f(a) 1 pour tout a E a . Les mots infinis
engendrés par itérations d'une substitution sur a
est une méthode simple pour construire des
suites intéressantes pour leurs régularités. Par exemple, sur les lettres 1 , 2 , la substitution s
donnée par
(ii)
s(l) :== 121
, s(2):== 212 ,
conduit au mot périodique x:== 12121212... (et au mot périodique x' obtenu en échangeant les
lettres) . Par contre la substitution cr donnée par
cr(l) :== 12 , cr(2):== 21 ,
conduit au mot infmi
~ : = 2112122112...
et au mot ~'obtenu par échange des lettres qui ne sont pas périodiques. Le mot ~ est point fixe
de cr, en ce sens que
les 2k premiers termes de ~ étant donnés par le k-ième itéré crk(2) de 2 par cr. Le mot infini
~ correspond à la célèbre suite de Morse (1921) qui a fait l'objet de nombreux travaux et suscité
des investigations plus générales (suites de Morse généralisées de M. Keane (1968), systèmes
symboliques associés (J. Martin (1970, 1973) et plus systématiquement M. Queffelec (Thèse,
1984». Un mot infini u point fixe d'une substitution uniforme est encore dit automatique. On sait
en effet d'après A. Cobham (1972) qu'un tel mot est reconnu par un automate Fmi .
Soit u un mot infini, point fixe d'une substitution uniforme f sur l'alphabet a . Dans
ce travail, nous étudions la suite des entiers p(u,n):== card(Fk(u».On a évidemment p(u,n) ~
(Card(a»D. A. Cobham a montré en 1972 qu'il existe une constante C (== C(u» telle que p(u,n)
~ Cn et N. Bleuzen-Guernalec (1986) a précisé la constante C en la majorant par p(Card(a»2.
Notre objectif principal est de démontrer l'existence d'un automate donnant la suite n ~ p(u,n+ 1)
- p(u,n) à partir de l'écriture de n en base p , ceci dans le cas où u est une suite minimale (i.e.
le système (S, Ku) est minimal) et f injective sur a.
Après l'introduction nous rappelons dans la partie II quelques propriétés des mots infmis u
".' ._ .
. . '_'"
" ~l;: .•
minimaux obtenus par substitutions f. Nous donnons un critère effectif de minimalité: On se libère
(iii)
ici de la condition restrictive lim k:oo 1 fc(a) 1 = +00 pour tout a E a , habituellement faite. Lorsque
u est minimal, la fonction p(v,.) est indépendante de v E Ku et cette propriété caractérise la
minimalité de u.
La Partie III est consacrée à la démonstration du théorème suivant:
Théorème .- Soit
u point fixe de La substitution uniforme
f de moduLe
p. On suppose
f
injective et u minimaLe mais pas périodique. ALors iL existe une constante Lü ne dépendant que
de p telle que pour tout facteur
M de
u iL existe
A, B et C, facteurs de
u, teLs que:
M = Bf(A)C, IBI < p , ICI < p
Le tripLet
(A,B,C) étant unique.
La démonstration se fait tout d'abord pour un alphabet à deux lettres. C'est le cas essentiel que
nous obtenons après une évaluation explicite du nombre maximum de facteurs successifs d'un
même mot de deux lettres apparaissant dans u. On trouve un résultat analogue dans J. Martin
(1970) et notamment pour les substitutions non nécessairement uniformes (1973), mais la
démonstration dans ce cas général n'est pas correcte et nous donnons un contre-exemple. Notre
méthode donne un meilleur résultat en fournissant explicitement la longueur du mot à lire pour avoir
l'unicité.
La partie IV traite du calcul automatique des p(n) :=p(u,n) . On montre que la suite q(n) :=
p(n+l) - p(n) ne prend qu'un nombre fini de valeurs. Nous pécisons ce résultat sous la forme
suivante :
Théorème.- Il existe un p-automate teL que q(n) soit La sortie de L'automate Lorsqu'iL Lit L'entier
n écrit en base p.
La suite de Morse et la suite de Rudin-Shapiro sont examinées en particulier dans la partie
(iv)
suivante. Rappelons que la suite de Rudin-Shapiro , qui compte modulo 2 le nombre de "Il"
dans l'écriture des entiers en base 2, est aussi l'image par un morphisme littéral d'un point fixe de
la substitution suivante t sur un alphabet à 4 lettres:
t(l) = 12 ,
t(2) = 13 ,
t(3) = 42 ,
't(4) = 43
Nous terminons en montrant que le caractère minimal de la suite est une condition suffisante mais
non nécessaire. Un exemple simple est fourni par la substitution f sur trois lettres 1, 2,3 donnée
par :
f(l) = 121 , f(2) = 232 , f(3) = 323.
: . ~
. '
'.' ~:'..;':;;)c;i:;;f~
COMOPIUEXITJÉ DlE SUlITIF..S A1lITOMA1fnQ1UJES
1. - INTRODUCTION
1.- 1. MOTS INFINIS.
Une suite finie m:= (mO,m 1, ...,11\\) dans un ensemble fini a de symboles (ou
lettres) sera vue le plus souvent comme un mot (fini) mOm ...11\\ sur l'alphabet a et par
1
extension, une suite u: IN ~ a sera vue comme un mot infini u:= uOu ~u3'" Une méthode
l
simple pour construire de tels mots est de procéder par itérations d'une substitution . Chaque lettre
d'un mot m est remplacée par un mot et ainsi de suite. On obtient ainsi des mots infinis dont les
régularités ont retenues en premier lieu l'attention [1,8,16]. Par exemple, sur les symboles 1 ,2,
la substitution s donnée par
s(l) := 121 , s(2):= 212,
conduit au mot périodique x :=12121212... (et au mot périodique x' obtenu en échangeant des
symboles 1,2 entre eux) par itération de s puisque sk(l) est fonné de la répétition successive
ek - fois du mot 12 suivi de 1. Un calcul simple montre d'ailleurs que 2 ek + 1 = 3k , d'où'
ek = 3k-1 + 3k-2 + ... + 3 + 1 . Par contre la substitution 0 donnée par
o(l) := 12 , 0(2):= 21 ,
conduit au mot infmi
~ : = 2112122112...
(et au mot ~'obtenu par échange les lettres). Le mot ~ est point fixe de 0, en ce sens que
~ = o(~o) O(~l) oùl:z) o(~) o(~) ...
les 2k premiers termes de ~ étant donnés par le k-ième itéré ok(2) de 2 par o. Le mot infini
~ n'est pas périodique; il correspond à la célèbre suite de Morse [11] qui a fait l'objet de nombreux
travaux et suscité des investigations plus générales, notamment dans [2,3,7,8,13,14,15]. Une des
'-,-
'. ~ ...
".~- ,', ' .
•
- . " " 1
:"
' . .
' •• ,
..::::: ::~ >~\\:'..;' ,;.~;~;.~:;;.~:k"::~f;J~~f;;.~~~i:ik'/:~ /i;I;;"~k;f;~ ':~"~~:- .,;:;;:~.7tif;,i[(iN~~t5~~~~t;~\\\\~;:'\\:i:;2:it:'2:/.i:K
2
propriétés les plus étonnantes du langage de Jl, découverte par Morse et Hedlund en 1938 [6] est
qu'aucun mot
Jl Jl +
+2k lu dans Jl n'est de la forme (al a
n
n
l ... Jln
2... ak)(a l a2... ak)a l . La
réciproque de cette propriété, à savoir les mots qui n'ont pas de sous-mots de la forme (al ~...
ale)(a l ~... ak)al sont lus dans Il, a été établie par Gottschalk et Hedlund [4].
Lorsqu'un mot infini u est point fixe d'une substitution uniforme sur un ensemble fmi
de symboles on le dit encore automatique . On sait en effet [3] qu'un tel mot est reconnu par un
automate fini. Par exemple pour la suite de Morse, l'automate déterminé par les deux états i, s, le
graphe orienté suivant
et la fonction de sortie 't: {i , s } --t {1 ,2} donnée par 't(i) = 2, 'tes) = 1 reconnait la suite de
Morse. Précisons la signification de ceci. Les arcs indexés par les chiffres 0 et 1 correspondent à
des instructions 1 et Il : l'instruction la est l'identité sur l'ensemble des états et Il représente
0
l'échange entre les deux états. Si maintenant l'entiers
n est représenté en base deux par la
suite de ses chiffres
eleek_l ...e
(n = 2k~ + .., + 2 el + e
O
o ), alors
~ = 't(I
e (l.. ... (L (i» ...».
le
k~f
'(f
Sous cette forme on reconnaît une autre définition classique de Il, en introduisant la somme des
chiffres en base deux. Classiquement, avec les notations précédentes, la suite de Morse est
caractérisée par :
Jl = 2 ~ ~ + ~-l +...+ e
n
o E 21N .
::.- "--:~.-,
~ .'
~,'
_.~"
3
1-2. NOTATIONS ET DÉFINITIONS.
Espaces de mots.- Dans toute la suite a désigne un ensemble fini de q symboles appelés
lettres. L'ensemble a est appelé alphabet et nous fixons a:= {1,2,... ,q}. Soit a* le monoide
libre engendré par a. Un élément m de a* est donc un produit fini m = m ...m
1
k d'éléments
de a
et que l'on regarde àlors comme un mot sur l'alphabet a. Le nombre k de lettres pour
écrire m est appelé longueur de m et se note 1ID 1. L'élément neutre de a* est le mot vide, on
•
le note /\\. Par définition, 1 /\\ 1 = °et on pose
a k := {m E a* ; 1 ID 1 = k }.
L'ensemble des mots infinis sur a (= a IN ) est noté a 00 • Soit a une lettre de a. On note
simplement a* pour l'ensemble {a}* des mots finis formés de la seule lettre a. Le mot infini
formé par la lettre a est noté a(oo) ou simplement aoo . Plus généralement, la lettre a peut être
remplacée par un mot m et définir ainsi l'ensemble m* et le mot infini mOO
Ce mot est dit
•
périodique, de période m. D'autre part, nous définissons par récurrence les mots m(k) en posant
m(O) = /\\ et m(k) = m(k-l)m pour k E IN*.
Soit maintenant l'ensemble n(a) = a* u a oo • Un mot fini
m:= 1110...11'\\-1 dans
a* est dit préfixe d'un mot
u:= Uo u1... uk_1... de n (a), si mi = ui pour tout i = 0,
1,... ,k-1. Si u est fini avec li:= Uou1 ...ue_1 et 1 u 1 ~ 1 ml, alors le mot m est dit suffue de u
si mi = ui pour tout i = ~-k, ~-k-l,... ,~-l . D'une manière générale, pour tout mot m de a*, on
note s(m) (resp. p(m)) un suffixe (resp. un préfixe) de m. Plus précisément, ~(m) (resp. Pk(m))
désigne le suffixe (resp. le préfixe) de m de longueur k (:S; Iml). Un préfixe et un sufftxe de m
sont dits stricts s'ils sont distincts de m.On note ma* (resp. a*m ) l'ensemble des mots finis de
préfixe m (resp. de suffixe m). Plus généralement, si A et B sont des parties de a* on note
AB l'ensemble des mots a~ tels que ex E A et ~ E B.
Introduisons une topologie sur n (a). Soient u, v des mots distincts dans n (a) et
4
posons
w(u,v)
Max { 1 ml; mE a* et m préfixe commun de u et v}.
L'application
d : n(a) xtt(a) ~n(a)
définie par d(u,v):= 2 - ro(u,v) si u"#- v
et d(u,v):= 0 si u = v est une distance sur n(a).
L'espace métrique ainsi obtenu est compact; a oo est un sous-espace compact et a* est un sous-
espace discret dense de n(a) .
Substitution.- On apelle substitution une application f: a ~ a* . Cette application se prolonge
de manière naturelle en morphisme
a* ~ a* de monoïde puis en une application de l'espace
tt(a) sur lui-même, encore notée f, et définie sur a oo par
f(uOu1···uk···) = f(uJf(u1) .. .f(uk) ..·
On obtient ainsi une application continue puisque pour tout
u, v
de n(a) on a de manière
évidente :
(1)
d(f(u),f(v)) $ d(u,v)
Notons que tout morphisme de monoïde f: a* ~ a* est déterminé par sa restriction sur a,
restriction que l'on appelle aussi substitution f sur
a. Selon la terminologie de Cobham [3],
une substitution (ou le morphisme qu'elle définit) est dite uniforme de module
p si p = 1 f(a) 1
pour toutes les lettres de l'alphabet. Un morphisme uniforme de module 1 est appelé morphisme
littéral. Une substitution f sur a
est dite :
- croissante, si pour toutes les lettres a de a on a 1 f(a) 1 ~ 2 ;
- non effaçante, si pour toutes les lettres a de a on a f(a) *- 1\\ •
Supposons qu'il existe une lettre a telle que f(a) = aA où A est un mot non vide et
soit Pa l'ensemble des mots finis ou infinis de préfixe a. Il est clair que fcPa) C Pa et que Pa
est compact. Le morphisme f est en fait une contraction sur Pa' la formule (1) donnant ici :
(2)
Vu, V E Pa : d(f(u),f(v)) $ 2 -lAI d(u,v) .
5
En particulier, f possède un point fixe c dans Pa donné par la limite :
c = Lim
fX(a) = Lim aAf(A)t2(A)...fX(A).
k~oo
k~oo
Facteurs.- Soit u un mot dans n(a). Un mot
m:= mOm l ... ms dans a* est dit
facteur
de
u:= uOu ~
l
... s'il existe un rang k tel que
mi = uk + i pour tout i = O,I,...,s.
(en particulier, on a
1 m 1 + k
~ 1 u 1 ). Si m est facteur de u, on note simplement m 1 u . La
relation (. 1.) est une relation d'ordre sur a* . L'ensemble des facteurs de u est noté F(u) et
l'ensemble des mots de longueur n qui sont facteurs de u est noté Fn(u). On pose maintenant
p(u,n) := Card(Fn(u)) .
Si aucune confusion n'est possible l'entier p(u,n) sera noté simplement pen). D'autre part nous
désignons par
Fn(k)(u) l'ensemble des facteurs de u
de longueur n
qui sont prolongeables à
droite de k manières différentes, c'est-à-dire:
Fn(k)(u) := { mE a*, 1 ml = n et Card{a E a; ma 1 u } = k } .
s'il n'y a pas d'ambiguïté, les ensembles Fn(u) et Fn(k)(u) seront notés respectivement Fn et
Fn(k). Nous avons par définition:
Fn(u)
U
Fn(k)(u) ,
~l
l'union étant disjointe.
Ret1lll1Y[Ul!S :
1) Soit m un facteur de u. Si m est prolongeable à droite de k manières différentes, alors tout
suffixe s de m est prolongeable à droite de k manières différentes au moins, ces k manières se
faisant avec les mêmes lettres que pour m.
2) Il découle de la remarque 1) que si aucun facteur de u de longueur donnée n n'est pas
prolongeable de k manières différentes, alors aucun facteur de u de longueur supérieure à n ne
peut être prolongeable de k manière au plus.
3) Si u est point fIxe d'une substitution f, alors toute image par f d'un facteur de u est aussi un
: .~ ';;::.
6
facteur de u. La réciproque est fausse en général si on ne fait pas d'hypothèses sur f.
1.. 3. RÉSULTATS.
Soit u un mot infini, point fixe d'une substitution uniforme f sur l'alphabet a . Dans
ce travail, nous étudions la suite des entiers p(u,n):= card(Fk(u».On a évidemment
p(u,n) ~ (Card(a»D.
A. Cobham a montré (1972 [3]) qu'il existe une constante C ( = C(u» telle que
p(u,n) ~ Cn
et N. Bleuzen-Guemalec (1986 [2]) a précisé la constante C en la majorant par p(Card(a»2.
Notre objectif principal est de démontrer l'existence d'un automate donnant la suite
n ~ p(u,n+ 1) - p( u,n)
à partir de l'écriture de n en base p, ceci dans le cas où u est un mot infini minimal (i.e. le
système dynamique (S, Ku) associé à u est minimal, cf. 11.- 1 ).
Dans la partie II nous donnons quelques propriétés des mots infinis u minimaux obtenus par
substitutions f. Nous donnons un critère effectif de minimalité. On peut se libérer de la condition
restrictive lim k:oo 1 tx(a) 1 = +00 pour tout a E a , habituellement faite [10,13]. Lorsque u est
minimal, la fonction p(v,.) est indépendante de v E Ku et cette propriété caractérise la minimalité
de u.
La Partie ID est consacrée à la démonstration du théorème suivant:
Théorème .- Soit
u point fixe de la substitution uniforme f de module
p. On suppose
f
injective et
u minimale mais pas périodique. Alors il existe une constante
L o telle que pour
tout facteur M de u ,lafactorisation M = Bf(A)C avec
IBI < p , ICI < p et A facteur de
u, est unique.
La démonstration se fait tout d'abord pour un alphabet à deux lettres. C'est le cas essentiel que
7
nous obtenons après une évaluation explicite du nombre maximum d'itérations successives des
mots de deux lettres. On trouve un résultat analogue dans J. Martin (1970) [9] et notamment pour
les substitutions non nécessairement uniformes (1973)[10], mais la démonstration dans ce cas
général n'est pas correcte et nous donnerons un contre-exemple. Notre méthode, qui ne s'applique
qu'aux subtitutions uniformes, conduit à un meilleur résultat en fournissant explicitement la
longueur du mot à lire pour avoir l'unicité.
La partie N traite du calcul automatique des p(n);= p(u,n) . la suite q(n):= p(n+l) - pen) ne
prend qu'un nombre fini de valeurs et nous pécisons ce résultat sous la forme suivante :
Théorème.- La suite n -7 q(n) est reconnaissable par une
p - automate.
La suite de Morse et la suite de Rudin-Shapiro sont examinées en détail dans la partie suivante.
Rappelons que la suite de Rudin-Shapiro , qui compte modulo 2 le nombre de "11" dans l'écriture
des entiers en base 2, est aussi l'image par un morphisme littéral d'un point fixe de la substitution
suivante 't sur un alphabet à 4 lettres:
't(l)=12
,
't(2) = 13
,
't(3)=42 ,
't(4) =43 .
Nous terminerons en montrant que le caractère minimal de la suite est une condition suffisante mais
non nécessaire.
[.
i
II.- MINIMALITÉ
II.- 1. SYSTEME SYMBOLIQUE D'UN MOT INFINl
Soit S : a 00 ~ a 00 l'application shift qui consiste à effacer la première lettre:
S(aOal~ooo) == al~~o.o ;
S est une application continue sur a 00 , partie compacte de n(a) Le couple (S, a 00) est appelé
0
shift symbolique (plein)
sur a
Un système symbolique, sur l'ensemble des symboles a, est
0
un sous-shift de (S, a 00), défini par une partie compacte K de a 00 stable par S. On le note
(S,K)o Un tel système est dit minimal si les seules parties fennées F de K stables par S sont
l'ensemble vide 0 et K 0
Soit u dans a 00 et notons Ku
l'orbite fennée de
u sous l'action de S c'est-à-dire
l'adhérence dans
a OO de l'ensemble {Sk(u); k E IN }o On a S(Ku) c Ku Le mot infini u est
0
ainsi associé au système symbolique Ku :== (S, Ku)'
II.-2. MOTS MINIMAUX.
Critères de nùnimalité.
Définition. - Un mot infini u sur l'alphabet a est dit minimal si le système symbolique associé
]Gu est minimal.
La caractérisation suivante est classique [4] :
Théorème A .- Le mot u est minimal si et seulement si pour toutfacteur m de u, il existe un
entier ~ ( == ~(m)) tel que :
(1)
V k E IN , ml ukuk+l ...uk+e .
. ,'
"
9
La condition (1) du théorème A exprime que tout mot du langage de u apparaît dans u avec
des lacunes bornées (par e). Lorsque u est point fixe d'une substitution f il est intéressant de
donner un critère de minimalité en fonction de f (cf. [13]).
Théorème B.- Soit
u point fLXe de la substitution f sur ['alphabet a. On suppose u E la00,
1 f(l) 1 ~ 2 et que toutes les lettres de
a soient dans u. Alors les propriétés suivantes sont)
équivalentes :
(i)
u est minimal et
Limk: 1 tk(a) 1 = +00 pour toutes les lettres a de a.
oo
(ii)
3 L ($; card(a) ) , V a E a,
1 1 tL(a)
(iii) Va E a, 3 k(a) E lN* , 1 1 tk(a)(a) .
Démonstration.- L'implication (i) => (iii) résulte directement du Théorème A. Supposons (iii)
et soit L:= Max {k(a); a E a}. Puisque f(l) E 1a*, on a i l fS(a) pour tout s ~ k(a). Reste
donc à montrer que L $; card(a) pour obtenir (ii). Définissons les ensembles
as = {a E a ; k(a) $; s }.
TI est clair que si pour une lettre a, on a k(a) = s, alors il existe des lettres distinctes bl'b2,...,bs_1
telles que k(b ) = s - i et b
i
i 1 f(a). On a donc dans ce cas
s $; card(as) $; card(a) et en
Supposons (1,.1,.) et soit m un facteur de u. Alors il existe e tel que m 1 ~(l) et comme
~(tL(u» = u , on a ~(1) 1 f~ + L(u ) pour tout indice n. Le mot m apparaît donc dans u avec
n
des lacunes bornées par
(Max{1 f(a) 1 ; a E a}y + L - 1 ml. Par ailleurs 1 fic + L(a) 1 ~ 1 fk(l) 1
pour toute lettre a et tout entier
k ~ 0 . Les hypothèses faites sur f et u impliquent donc
Lorsque a = {1,2} , on a un critère de minimalité très simple:
- .
.~
10
Théorèmé c.- Soit u un mot infini pointfue d'une substitution
f sur
a = {l,2} tel que 1
soit préfixe de u et u i; 100 •
(1,) Supposons
f croissante, alors:
u minimal <=> f(2) e: 2* .
(1,1,) Supposons
1 f(1) 1 ~ 2 et
f(2) = 2 , alors:
u minimal <=>
f(1) E 1a*1 .
Démonstration.
(1,): Si le mot u est minimal, n'étant pas formé que de 1, il admet les facteurs rc(2). Donc si
f(2) E 2*, le mot 2 apparaît dans u avec des lacunes arbitrairement grandes, contrairement au
théorème A . Réciproquement si f(2) e: 2*, alors 1 1 f(2) et la minimalité résulte du théorème B.
(1,1,): Si
2
est suffixe de
f(1)
alors on peut écrire
f(l) === 1A12(b) avec b ~ 1 etplus
généralement
rc(l) = 1Ak12(kb). Cette forme s'obtient par récurrence puisque rc+ 1(1) =
(lA 12(b))f(A )(1 A 12(b))2(kb).
k
Ainsi les mots 28 , s
~
~ 0 , sont tous facteurs de u qui n'est~èl.~'nc-pa Mi'f\\i:male. Supposons
.
â'.,··/
,\\~
.~ /_-
-?
maintenant que 1 soit suffixe de f(l). Posons
r:= 1 f(l) 1..~L<r moAt 2(T-l)sn'e@.pasfacteurde
E
r.~.l C M
&n
f(l) et s'il n'est pas facteur d'un mot m, il n'est pas facteu~t..Jd~.~ résulte que 1
\\,"°t;.~.,.~
apparaît dans u avec des lacunes bornées par r -1 . Par suite \\'l\\t<1~)s ~pparat~~~ussi dans u avec
~'
des lacunes bornées et donc u est minimale.
".,. ,....;.
m.- COMPLEXITE DU LANGAGE
Ill. 1.- LE THEOREME D'UNICITE.
Dans la suite f désigne une substitution telle que f(l) E la* et 1 f(l) 1 :?: 2 . Alors f
admet un seul point fixe dans la
noté u . Sauf mention explicite du contraire, on supposera f
00
uniforme de module p et le mot infini u minimaL avec toutes les lettres de a apparaissant dans
u.
Soit m un facteur de u. li peut se factoriser sous la forme
(1)
m == Bf(A)C
avec les conditions:
(2)
B suffixe strict d'un mot f(b), C préfixe strict d'un mot f(c) et bAc facteur de u.
Définition.- Un facteur m de u est dit mot rythmé sur l'alphabet a s'il n'existe qu'un seul
triplet (A,B,C) vérifiant (1) et (2) .
On se propose de démontrer que tout facteur de u assez long est un mot rythmé. Ce résultat
est énoncé dans [9] dans le cas de deux lettres. Nous donnerons ici une démonstration utilisant
une méthode différente avec une information précise sur la longueur minimale du mot m pour que
celui-ci soit rythmé. Le résultat est ensuite étendu au cas d'un alphabet à plus de deux lettres.
On trouve aussi chez Martin [10] l'énoncé du même théorème dans le cas des suites de
longueurs non constantes sur un alphabet à deux lettres. Cette généralisation est fausse comme le
montre la proposition suivante :
PROPOSITION 1 .- Supposons f une substitution non uniforme sur a == {l,2} , f(2) préfixe
... :::.. ~.~:1~};j'"
:,:',:,~::;'~~i;l,~f;;~lf;~;;~t,i~~{~
12
de f( 1) et
u point fixe minimal non périodique de
f. Alors il existe une infinité de facteurs
m de u tels que :
m2 1 u et
f(m2) n'est pas rythmé.
Démonstration.- En effet on a f(m2) = f(m)f(2) = f(m)p(f(l )). Il suffit donc de démontrer
cf
l'existence d'une infinité de mots m tels que
m2 et ml soient des facteurs de u . Soit w un
préfixe de u. Par minimalIté de u ,il existe k tel que w soit aussi préfixe de Sku (= ukuk+ ...).
1
Comme u n'est pas périodique, on a
U"# Sku
et il existe donc un mot w' tel que ww'l et
ww'2 soient préfixes pour u ou Sku . Le mot
m = ww'2
satisfait aux conditions de la
proposition.
li suffit donc pour obtenir un contre-exemple de choisir f vérifiant les hypothèses de la
proposition 1 avec des conditions assurant la minimalité de u (par exemple, f croissante, f(1) E
1(;1.* et 1 1 f(2)) . On peut cependant espérer que sous certaines conditions peu restrictives sur f (et
u), les facteurs de longueurs assez grandes soient rythmés.
THEOREME 1.- Soit
f une substitution uniforme de module p ~ 2 injective sur l'alphabet
(;1. = {1,2, ... , q}. On suppose u E 1(;1.* et u minimale mais pas périodique. Alors il existe La
= Lo(p,q) (:S p( p3 + p2 + p + 1) pour un alphabet à deux lettres) tel que toutfacteur
m de u
de longueur plus gande que L o soit un mot rythmé.
Avant de démontrer ce théorème, il est intéressant de remarquer la propriété générale suivante:
PROPOSITION 2.- Soit u un mot infini pointfue d'une substitution uniforme f de module p
( u n'est pas ici supposé minimal) . Supposons f injective sur a. S'il existe unfacteur R de
u rythmé et de longueur
~ p alors tout facteur de
u dont
R est un facteur, est aussi un
13
mot rythmé.
Démonstration. Soit m un facteur de u dont R est facteur. La factorisation de u par bloc de p
lettres, i.e. u = f(u o)f(u )f(u
l
z)f(u3) ... donne une factorisation de R lu dans m. Celle-ci étant
unique, elle détermine alors un préfixe B d'un mot de f(a) , de longueur 1 B 1 < p et tel que si R
= uk uk+! uk+Z'" uk+T' alors k + 1 B 1 est un multiple de p. La position de u k + 1BI dans R, et
par suite dans m, fournit une factorisation de m induite par celle de u ,mais celle-ci ne dépend
pas de la lecture de m dans u. Soit
cette factorisation unique où les mots mi sont dans f(a.) et les mots 1t, 0 ont des longueurs
strictement inférieures à p . Le caractère injectif de f donne la factorisation rythmée de m.
•
Notons que si f est injective et u mot infini laissé fixe par f, alors la relation feu) = u
détermine une factorisation de u en facteur de longueur p. Appelons cette factorisation canonique.
Dire qu'un facteur de u est rythmé sur a. signifie que la factorisation canonique de u induit sur
m une seule factorisation, quel que soit les diverses positions de m dans u .
Illustrons la proposition 2 et le théorème 1 par un exemple:
Le mot de Morse. Soit 0 la substitution sur {l, 2} définie par 0(1) = 12 et 0'(2) = 21 . cr est
injective. Le mot de Morse envisagé dans l'introduction, est le point fixe ~ de a de préfixe 2
(cf. LI). On observe facilement que les seuls mots rythmés dans ~ de longueur 3 sont 221,
122, 112, 211, les autres ne sont pas rythmés (121, 212) ou ne sont pas des facteurs (222, 111).
Soit m un mot de longueur 4. Supposons qu'il n'admette pas de facteurs rythmés de longueur 3.
Alors 121 ou 212 sont les seuls facteurs possibles de longueur 3 de sorte que m = 1212 ou fi
.-".'
..'
',:;?d,\\;;;,~,j~';é·;:~~;è:~ :;:~:~t<';:rJ:ilÙ;,§;~y~::J~~~ ".';',,:\\".:":\\~:,j;:~i;:\\;~i,~: ,,~,·.i
14
=2121. On vérifie directement que ces deux mots sont des facteurs de \\.1. Supposons m =1212
= H(2)2 . Etant facteur de J..l le mot 2H(2)21 = f(222) est aussi facteur de Il et ne provient que
de l'image par f
de 222. Par suite le mot 222 est lui aussi un facteur de Il, ce qui est faux.
Ainsi 1212 est rythmé de même que 2121. Les autres facteurs de Il de longueur 4 contiennent
nécessairement l'un des quatre mots rythmés de 10ngeur 3. Finalement on a montré :
PROPOSITION 3 .- Dans le mot de Morse tout facteur de longueur supérieure ou égale à
4 est
rythmé et la valeur 4 est optimale.
Remarque: La constante La du théorème 1 vaut 32 dans le cas de la suite de Morse. Mais la
démonstration donne en fait un procédé calculatoire simple qui dans la pratique fournit une
constante plus faible (cf. Théorème 2).
m2.- COMMUTATION.
Soient m et u des mots dans a* . On dit que u est un commutant de fi s'il est à la fois
préfixe et suffixe de fi. li existe donc v et v' dans a* tel que m = uv = v'u . Les deux lemmes
suivants décrivent la stucture des mots ayant des commutants identiques.
LEMME 1.- Soient m, u ,v des mots de l'alphabet
a tels que
fi =
uv = vu , et soit
d := ( 1u l ,Iv 1) le pgcd des longueurs de u et
v. Alors
m = p(r) où p est le préfue de
m de longueur
d et
r = 1 fi 1/ d .
Démonstration. - Commençons par démontrer que pour k = [ 1fi 1/ 1 v Il on a m = p(v)v(k) =
vp(v)v(k·l) où pey) est le préfixe de
v de longueur \\ m \\ - k.\\ vi. Cette décomposition est
15
évidente si 1 u 1 :s:: 1 v 1 car alors u = pey) et k = 1 . Supposons 1 u 1 > 1 vi· De uv = vu on déduit
u = vu', d'où
vu'v = vvu' et par suite u'v = vu' . Par récurrence, on se ramène donc au cas où
u = v(k)u" avec 1 u" 1 :s:: 1 v 1 et u"v = vu" de sorte que u" = pcv) et m a la forme requise.
Le lemme est évident si 1 u 1 = 1 vi, ou si l'un des mots u, v est une lettre. Supposons le
lemme vrai pour les mots m tels que 1 m 1 < K . Soit maintenant un mot m = uv = vu de
longueur K . On peut supposer 1 u 1 > 1 v 1 et par le raisonnement précedent, on peut écrire m =
p(v)v(k) = vp(v)v(k-l). Alors le mot m' = p(v)v (= vp(v» est de longeur 1 m' 1 < K et de plus
( 1 u 1 ,Iv 1 ) = ( 1 vi, 1 pcv) 1 ) = d d'où par hypothèse de récurrence, m' = n(r') avec r' = 1 m' 1 / d
et n préfixe de v. Il existe donc s et t entiers tels que pcv) = n(sd) et v = n(td). Par suite
m = n(sd + ktd).
LEMME 2.- Soient m, m', u , v et v' des mots dans
a* tels que
m = uv = v'u ,
m' = uv' = vu et
1 ml
= 1 m' 1 .
Alors m = m' , v = v' et m E p* où p est le préfue de m de longueur (\\ u 1 ,Iv \\ ).
Démonstration.- Le lemme est évident si 1 u 1 ~ 1 v 1 ( = 1 v' 1 ) car dans ce cas v et v' sont tous
les deux préfixes de u et de même longueur. Ils sont donc égaux, et le lemme 1 s'applique.
Supposons
1u 1 <1
_
v 1. Posons v = v1u et v' = v' A
lU. lors u v 1U = v'1UU
V'lU
et
u v'l = vlu . On se ramène donc au cas précédent avec 1 vI 1 =
1 v 1 -
1 u 1 . Par récurrence on obtient pour
k = [ 1 v 1 / 1 u 1 ] :
v = vku(k)
et
v' = v'ku(k) ,
avec
uVk = v'ku
et
uV'k = vku . Mais 1 u 1 ~ 1 vk 1 , d'où vk = v'k et le lemme 2 résulte
maintenant directement du lemme 1.
".'
16
ID.3.- MAJORATION DES FACTEURS PUISSANCES.
Mots périodiques.- Soit u point fixe d'une subtitution f de module p sur un alphabet CI- et
supposons que toute les lettres de CI- apparaissent dans u. Il est clair que si u est purement
périodique, de mot période de longueur pV alors tous les mots f V(a) , a E a, sont identiques.
Réciproquement, s'il existe v tel que tous les mots f V(a) , a E a, soient identiques, alors f v(1)
est un mot période de u de longueur pv
Si aucune puissance de p n'est période de u la propriété précédente est alors mise en défaut.
Par exemple la substitution suivante:
f(l) = 121 , f(2) = 212
qui a pour point fixe (12)00, vérifie fc(1) i' fc(2) pour tout entier k. Cette propriété est
évidemment conservée dans le cas où u n'est pas périodique sur un alphabet à deux lettres; elle
traduit le caractère injectif de f. En d'autres termes:
LEMME 3. - Soit
f une substitution uniforme sur
CI- = {l, 2} de pointfue
u
dans
la*,
non périodique. ALors fc(1) i' fc(2) pour tout entier k et pour tous mots m, m' dans a*
ona
f(m) = f(m') => m = m'
Définition.- Pour tout mot fini ou infini u et pour tout mot fini m non vide sur l'alphabet a , on
pose
Lu(m) = Sup {k; mCk) \\ u }.
Majoration de Lu(m) .- Nous étudions seulement Lu(m) lorsque m est une lettre ou un mot de
deux lettres distinctes.
17
LEMME 4 .- Soit u un mot minimal non périodique, point fue d'une substitution uniforme f de
module p sur
a (= {l, 2}). Alors Lu(1) et Lu(2) (resp. Lu(l2) et Lu(21)) sont majorés
par
p2 + P (resp. par
p3 + p2 + P ) .
Démonstration .- Nous supposons u dans 1a* et comme u est minimal on a
f(l) ~ 1* et
f(2) ~ 2* (Théorème C). Nous distinguons deux cas, suivant que f(2) est ou n'est pas dans 1* .
Premier cas: Supposons f(2) ~ 1* , alors pour tout i E A on a Lu(i) < 2p ( ~ p2 + p ). En
effet, dans le cas contraire, il existe une lettre j telle que Lu(j) ~ 2p et Pp) est un facteur de u.
Le morphisme f étant de module p l'un des mots f(l), f(2) est facteur de Pp) . Comme f(l) ~
1* mais f(1) E 1a* et f(2) ~ 2*, on obtient f(2) = 1(p) contrairement à l'hypothèse.
Montrons maintenant que pour tout mot ij E a 2 tel que i #- j on a Lu(ij) < 2 p2 + P (~
p3 + p2 + p ). Supposons que pour un choix de ij on ait Lu(ij) ~ 2p2 + p . Le mot (ij)2; + p
est alors facteur de u et se décompose sous la forme s(f(a))f(b ) ...f(b
1
2p )p(f(c)), avec bk E a
pour k E {l, ... ,2p} et
a, b dans a. u {I\\}. Si P est pair, alors f(bk) = (ij)P/2 ou f(bk) =
(ji)P/2 pour tout k et par le lemme 3 on a bl= b2 = ... = b2p ce qui est contraire à Lu(b) < 2p
pour toute lettre b de a. Si p est impair, nous avons maintenant soit f(b2.k_I) = (ij)(P-I)~
et f(b
)
_ )
)
2k
=
(ji)<p-l)/2j, soit f(b 2k
=
(ji)<p-I)l2j et f(b
=
(ij)<p-I)/2i ,pour 1 ~ k $ p.
l
2k
Dans tous les cas, on a f(l) = (12)(P-I)I2(1) et f(2) = (21)<P- I)I2(2) . Mais alors u est périodique,
ce qui est exclu.
Deuxième cas: Supposons f(2) E 1*. Comme f(l) E 1a*, la lettre 2 n'apparaît que dans f(1)
et par suite LU<2) < p .
Montrons que L u(1) < p2 + p . Dans le cas contraire, 1(ft + p) est un facteur de li et sa
décomposition sous la forme s(f(a))f(bl) ...f(bp)p(f(c)) donne f(b k) E 1* pour k = 1, ..., p.
Par suite bl = .., = b = 2 ce qui contredit l'inégalité L (2) < p .
p
u
18
Examinons maintenant le cas de ij E a 2, i"# j et supposons L/ij) ~ p3 + p2 + p. Alors,
comme précédemment, il existe un facteur m de u de longueur p2 + P tel que f(m) E (ij)* ou
f(m) E Ui)*. Par hypothèse, la lettre 1 est préfixe de f(1) et de f(2) , d'où f(m) E (12)*.
2
Alors p est pair, f(1) = (l2)(p/2) et
m = 1(p '1- p) ce qui contredit la majoration déjà obtenue
pour Lu(i).
.
. ,",
. . ,- ~ ": .
. ~.'.
19
m.- 4. DÉMONSTRATION DU THÉORÈME 1 POUR DEUX LETTRES.
Soit f une substitution uniforme de module p ~ 2 sur l'alphabet a = { 1 , 2} et
soit u un point fixe minimal non périodique de f.
Soit m un facteur de u tel que 1 m 1 ~ Lo et supposons m non rythmé. Il existe alors deux
factorisations distinctes
Bf(A)C et
B'f(A')C' de m vérifiant les conditions données par (2).
On peut supposer 1 CI*- 1 C' 1 . En effet, dans le cas contraire, on a C = C' puis nécessairement
1 B 1 = 1 B' 1 , donc
B = B'. D'où f(A) = f(A') et par le lemme 3, A = A' . On peut donc choisir
1 C 1 < 1 C' 1 et poser
C' = XoC , 1 Xo 1 = r , 0 < r < p - 1.
Posons maintenant
A
=
a
A'
' a '
ak··· l '
:= a e'"
l
on a
Bf(ak) .. .f(a 1) = B'f(a'e)...f(a'1)X ' k - 1 ~ ~ ~ k ,
O
B et B' étant suffixes de f(b) et f(b') respectivement, Xo préfixe de f(a'o)' de telle sorte que
les mots bak...a 1 et b'a'e...a'l a'o soient des facteurs de u. Posons ak+ = b et a'e+l = b' .
1
Ecrivons
On obtient ainsi
et de proche en proche, pour i = 1, ... , k on peut écrire :
(3)
f(a.) = uv. , f(a'.) = V'·V.
f(a. 1) = U 1V'. l
1
1
1
1
1
l '
I+
I+
1
avec 1 Di 1 = 1 U'i 1 = r et 1 Vi 1 = 1 V\\ 1 = p - r .
Par choix de Lo ' on a k ~ p3 + p2 + p . Le mot A n'est donc pas facteur d'un mot dans
l'ensemble 1*u2*u(l2)*. D'autre part, écrivons A = WW' avec 1 W 1 = [kl2] . Comme on a
p ~ 2, les mots W et W' sont de longueur plus grande que pZ + p et par le Lemme 4 il
contiennent les lettre 1 et 2. Si le mot 21 n'est pas facteur de W ,alors West facteur d'un
20
mot de l'ensemble 1*2* et par suite le mot 21 est facteur de W' . De même si le mot 12 n'est
pas facteur de W, il est certainement facteur de W'. D'autre part si les mots Il et 22 ne sont pas
facteurs de A, alors celui-ci est facteur d'un mot dans (12)*, ce qui est contraire au Lemme 4.
En définitive, on a deux cas possibles:
{I2, 21, Il} c f (A) ou {12, 21, 22} c f (A).
2
2
Posons f(l):= UV et f(2):= U'V' avec 1 U 1 = 1 U' 1 = r. D'après (3), l'ensemble E = {VU',
V'U,VU} ou l'ensemble E' = {VU', V'U, V'U'} est contenu dans
{UV, U'V'}. L'hypothèse
f(l) E la.* qui distingue la lettre 1 de la lettre 2 n'étant pas utilisé par la suite, on peut se
contenter d'étudier le cas où
E c {UV, U'V'}. Si E se réduit à un seul élément, alors V = V' ,
U = U' et par suite f( 1) = f(2) . Le mot u est alors périodique, contradiction. Ainsi E n'est formé
que de deux élements. Si U = U', alors E = {VU, V'U} ce qui donne UV = VU et UV' == V'U
ou bien UV = V'U et UV' = VU. Le Lemme 1 dans le premier cas et le Lemme 2 dans le second
donne
la contradiction
f( 1) = f(2). Si
V = V', le même
raisonnement donne la même
contradiction.
Nous pouvons donc maintenant supposer U ~ U' et V ~ V'. Alors l'ensemble E est formé de
trois éléments distints, ce qui est impossible.
~\\N~ 1311-:-1
./~;j)\\
o (-~=::1 0/
La démonstration précédente montre que si A est un faotetrrœ ~conte
. ~tJes mots 12, 21,
"; ~
.;,Q./!
\\
t.;.-"
'-<.:)
et l'un des mots Il ou 22, alors le facteur f(A) est rythmé. Rés~h1ql;!~r:n~~e{\\
THEOREME 2 .- Soit f une substitution uniforme de module p sur {l, 2} et admettant un
point fue minimal u non périodique et soit Li le plus petit entier
e tel que tout facteur de u
de longueur
~ e contienne les mots 12,21 et l'un des mots Il ou 22. Alors les facteurs
de
u de longueur
~ pCL + 1) sont rythmés.
i
Remarques: 1) Si on ne fait pas l'hypothèse que u est minimale, l'existence de Li implique la
"'.- .' .,'
minimalité d'après le Théorème B .
2) Dans le cas de la suite de Morse, un calcul direct donne LI = 5 . En effet, 1212 et 2121 sont
des facteurs du mot de Morse et les mots 12121 et 21212 n'en sont pas. Dans ce cas la constante
p(L I + 1) (= 12) est bien meilleure que La ( = 32).
m.-s. DEMONSTRATION DU THEOREME 1 DANS LE CAS GENERAL.
Indication sur la démonstration.
Soit f substitution uniforme de module p ~ 2 sur l'alphabet a = {l, 2, ... , q}, avec q ~
3 et supposons f injective et qu'elle admette un point fixe u minimal non périodique. Nous allons
montrer qu'il existe une constante H = H(p,q) telle que s'il existe un facteur m de u non rythmé
et de longueur plus grande que H, alors il existe un entier d diviseur de p et une substitution F
uniforme de module p sur un alphabet p
tel que
p
c ad , card(p) $ q - 1 et F(u) = u en
regardant u comme un mot infini sur l'alphabet p . De plus le mot m peut se lire comme un
élément de p* et on montre qu'il n'est pas rythmé sur l'alphabet p. Sa longueur sur cet alphabet
est 1 mil d . Donc si 1 m 1 ~ (p/2)La(p, q-l) ,on en tire une contradiction.
Le cas d'un alphabet à deux lettres revenait essentiellement à montrer que l'existence d'un mot
non rythmé assez long impliquait l'égalité f(1) = f(2). En d'autres termes, la substitution f pouvait
se voir comme étant définie sur un alphabet à une lettre. Nous allons suivre cette idée en deux
étapes, en commençant par généraliser le Lemme 2.
étape 1.
LEMME 4.- Soient
tn un ensemble de rrwts de même longueur p sur un alphabet a. Soit
u:= p/m) (resp. V:= sp_r(m)) l'ensemble des préfues ( resp. suffues) de longueur r (resp.
de longueur p - r) des mots de m . On suppose de plus que
(4)
.' :< ~'. . .
..: ~..-
, -o'···
',. ~,:,,:,
22
Soient
d:= pgcd (p, r)
et
p l'ensemble des préfixes de longeur d des mots de tn.
Alors
tn c p*.
Démonstration. Quitte à échanger les rôles de U
et v
on peut supposer r :5 p - r . Soit
v
un mot dans v. Il existe mE tn
et
u E U
tel que m = uv et comme v est préfixe d'un
mot ml de tn, il existe u' dans U
tel que ml = vu', et d'après (4) il existe u dans U
i
et VI dans V
telsque ml = vu'= u1v l. On peut alors écrire v = ulw1 etparsuite m =
UUlW I. En d'autres termes, tn c UUW1(=UW I) où w 1 est l'ensemble des suffixes
de longueur p - 2r des mots de tn. Soit W k-l l'ensemble des suffixes de longueur p - la
(~O) des mots de tn. Supposons maintenant tn c UkW k_1 pour un entier k tel que p ~
(k + 1)r. Alors, de V
= Pp_r(tn) on déduit comme précédemment V c ukw k . La relation
tn c v' entraîne tn c U(k+I)W k et par suite v c U(k+I)Wk+1 . Itérons le procédé
jusqu'à t = [p/r] . Tout mot m de tn s'écrivant sous les formes uv et v'u' respectivement
dans uv et vu avec v = u(t-l)w t-l ' on a :
(5)
les ui ' u'i dans U et w, w' dans 'w t-l . En particulier utw = w'U't . Si P = tr ,alors W t-l
est vide et le lemme est démontré. Dans le cas contraire, soit tn' = s't(tn) pour 't = P - (t - l)r,
u' = U et
v' = W t-l . Par hypothèses sur U et V on a s't_r(tn ') = s't_r(tn) = s't_r(v) = v'
et par suite (5) donne aussi P't-r(tn') = v'. D'autre part U = s/tn) = sr(tn') = sr(V) et par
(5) sr(V) = Pr(tn'). Au total :
u' = p/tn') = sr(tn') et v' = s't_r(tn') = P't_r(tn') .
Nous sommes ainsi ramenés au cas précédent avec 't au lieu de p et 't - r au lieu de r, le pgcd
restant inchangé. On voit donc que si lemme est démontré pour tn', alors "' et v' sont dans
p* (notation du lemme) et par suite tn est aussi dans p*. Le lemme est évident pour p = 2d et
s'il est vrai pour les multiples 2d, 3d,... , kd, alors le raisonnement précédent montre qu'il est
encore vrai pour p = (k + l)d. Le lemme est donc établi par récurrence sur les multiples de p.
•
23
étape 2.
Les hypothèses et notations sont celles du Théorème 1. Soit
~ = ~(p,q) une constante
telle que pour tout facteur m de u on ait
m
~ ~
F (m)
(u) .
1
1
: : : : )
2
= F2
Cette constante peut être choisie au mieux en fonction de f mais dans tous les cas la valeur 2p2q-l
convient. En effet, si m 1 u et 1 m 1 ~ 2p2q -1, alors m possède un facteur de la fonne [2q(a).
Désignons par ~(a) l'ensemble des facteurs de longueur deux apparaissant dans l'un des mots
f(a), ... , tx(a) . Si ~+l(a) = s.(a) cela signifie que pour tout uv E s.(a) on a Fluv) c ~(a). Il
en résulte donc que ~+n(a) = s.(a) pour tout n ~ 0 et cette égalité à lieu dès que k ~ card( a 2) =
q2.
Choisissons maintenant H = p(H2 + 1) et supposons que u admette un facteur m non
rythmé de longueur ~ H . Alors m admet deux factorisations distinctes
(6)
m = Bf(A)C = B'f(A')C'
vérifiant les conditions données par (2). Comme dans le cas de la démonstration pour deux lettres
(cf. llI.-4), on peut écrire en adoptant les mêmes notations:
avec k - 1 ~ e ~ k et
Bf(ak)··.f(a l) = B'f(a'e)···f(a't)Xo '
où B et B' sont suffixes de f(b) et f(b') respectivement, Xo préfixe de f(a'o) de longueur r
et les mots
bak... a l et b'a'e...a't a'o facteurs de u .Posons b = ak+l' b'= a'e+l . On a encore
les relations (3) , à savoir :
(3)
pour 1 ~ i ~ k ,avec 1 Vi 1 = 1 U'i 1 = r et 1 Vi 1 = 1 V\\ 1 = p - r .
Soit tn = f(a) , U = Pr(tn) et V = sp_ltn). Par choix de H, on a k ~ ~ . Les mots
ak...a l et a'k...a'l contiennent toutes les lettres de a, d'où sr(tn) = u grâce aux relations (3).
D'autre part le mot ak+l"'~ contient aussi toutes les lettres de l'alphabet et (3) donne donc
Pp_r(m) == v. D'après le Lemme 4 on a
m
c p* pour p == Pd(m) == sd(m)
avec d == pgcd(p,r) .
Supposons card(p) == card(a-). Alors les images f(a)
sont déterminées par leurs préfixes
(ou suffixes) de longueur d et il existe des bijections
~: a ~"' , y: a- ~ v et ~': a ~ u. ,
"1: a- ~v telles que
Va E a, f(a) == ~(a))'(a) == "I(a)~'(a).
Si le mot de deux lettres a'a est facteur de A, alors les relations (3) donnent ~'(a') == ~(a) d'où
a == ~-l~'(a') . Posons 6 = ~-l~', alors 6 est une bijection dans a
et
bA == b6(b)...6k(b).
Toutes les lettres étant dans A, la bijection 6 est d'ordre q. D'autre part, tous les facteurs de
longeur deux de u étant dans
A, ils sont nécessairement de la forme
a6(a) , d'où u ==
16(1)62(1) ... c'est-à-dire u == 8k(u ) . La suite est donc périodique (de période q), contradiction.
k
O
Supposons card(p) < card(a). Désignons par '!' le plongement canonique de p* dans
a* que l'on prolonge à t'Lep) ,Comme f(a) == m
c p*, on peut regarder les mots de t'L(m)
comme des mots de n(p) ; notons <p: t'L(m) ~ t'L(P) cette identification et finalement notons
par f l'aplication de t'L(a) dans t'L(m) induite par la substitution f. Soit F:== <pofo,!, et U ==
<p(f(u)). Par construction U est la suite u après regroupement par mots successifs de d lettres,
c'est-à-dire
Un == Und" ,u(n+l)d-l '
et par construction F est une substitution uniforme de module p sur l'alphabet p
et le mot
infini U de poo est point fixe de F. Le caractère minimal de U résulte du Théorème A.
Fin de la dé11UJnstratïon.
Montrons que le mot m vérifiant (6) peut se voir comme un facteur de U . En effet les mots
B et B' sont des suffixes de mots de m
,de longueurs multiples de d et
C, C' sont des
préfixes de mots de m , également de longeurs multiples de d.
'2. 5'
Maintenant notons que les factorisations de m s'obtiennent à partir de la factorisation de u en
blocs successifs de p lettres données par la relation u = f(u) . En çonsidérant U et F , la ou les
factorisations de m se déduisent de la factorisation de U en blocs de pd lettres:
U = [(uo'" ud-l)··· (ud(P-I)-I'" udp _l)] [(udp " .ud(p+I)_I)'" (ud(2P_I)" 'l!up-l)]'"
chaque bloc pouvant se voir comme produit de p facteurs de mots dans p (de d lettres) ou
comme produit de d facteurs de mots dans tn
(de p lettres). TI en résulte que la factorisation
Bf(A)C entraîne une factorisation de m sous la forme BB1F(A1)C1C avec BI = f(P) (resp. CI
= f(y)) où P (resp. y) est préfixe (resp. suffixe) de
A. De même la factorisation B'f(A')C'
donne une factorisation de m de la forme
B'f(W)F(A'I)f(y')C'. En particulier, si m est rythmé
sur l'alphabet p ,alors 1 Bf(P) 1 = 1B'f(W) 1 d'où 1 B 1 - 1 B' 1 est multiple de
p ce qui est
exclu. le mot m n'est donc pas rythmé sur l'alphabet p et sa longueur en tant que mot sur p
est au moins 21 m Il p ~ 2H!p.
Choisissons maintenant Lo(p,q) = p2(q+l) pour q ~ 3 (la valeur pour q = 2 est plus grande
que celle déja obtenue). Comme H(p,q):::; 2p2q+1 si 1 m 1 ~ Lo(p,q), on a 1 m 1 ~ H et 21 m Il p
~ 2p2q+1 ~ Lo(p,q') pour tout q' = 2, ... , q-l. Si le théorème est démontré dans le cas
d'alphabets d'au plus q-l lettres alors tout mot m de longueur supérieure à Lo(p,q) est rythmé
dans u sur l'alphabet a . Ceci termine la démonstration et donne une valeur pour la constante
IV.- CALCUL AUTüMATIQUE
IV.l.-AUTOMATES.
Définition.- Un g- automate est un quadruplet (S, 9 ,l, i) où
S := {sI"'" Sd}
est un ensemble fini appelé espace des états , i est un état donné appelé état initial ,
9 : = {O,l, ... , g-l},
avec g ~ 2, est un ensemble ordonné fini appelé alphabet ou ensemble des entrées , enfin 1
est un ensemble d'applications 10,,,,, 19-1 de S dans S (appelées instructions ).
A tout entier n correspond un mot el" .eo dans g* donné par le développement de n en
base g:
_
l
n - elg + .. , + el g + eo.
On associe alors à n une sortie définie par :
Définition.- Soit E un ensemble fini. Une suite q: IN -7 E est dite g-reconnaissable s'il existe
un g-automate (S, g, l ,s) et un application 't: S -7 E tels que
q(n) = 't 0 1 (n) .
Nous allons démontrer le théorème suivant:
THEOREME 3 .- Soit f une substitution uniforme de module p, sur l'alphabet a, injective et
admettant un point fzxe
u minimal, non périodique. Soit pen) le nombre de facteurs de u de
longueur n et soit q(n) = pen + 1) - pen) . Alors la suite n -7 q(n) :
.~,: .....
.' " ,~,
"
.-
27
(i.) ne prend qu'un nombrefini de valeurs;
(i.i.) est p-reconnaissable par un autOmate.
IV.2.- ETUDE DES Fn(u).
L'évaluation de q(.) se fera par récurrence sur la longueur n des facteurs de u. Avec les
notations de l'introduction et en notant simplement le cardinal d'un ensemble fini par 1 E 1 (au
risque de confondre avec la longueur d'un mot) on a :
Soit Lo la constante du Théorème 1 et soit
E:= U{Fn(k); 1 SnSLo}
Nous allons étudier les ensembles Fn(k) ,pour n > Lo' par une méthode récursive.
DécOIDpü<;ition des entiers.
Notations.- Soit X une partie de a. On pose
Â.x := Max{ s; 3 mE aS, V x EX, m = Ps(f(x)}
et
p(X,n) := Min {k E IN ; k ~ (n - Â.x)/p } = p.
LEMME 5 .- Les éléments de Fn(k), pour n > Lo sont factorisés en suffixes de longueur
(n - Â.x) des images des éléments de Fp(k~) et préfues qui sont les plus grands facteurs préfixes
commun aux images des éléments d'un sous-ensemble X de a de cardinal (k + e) ,e ~ 0, tel
28
que k=card{p\\+l(f(a)); aEX}.
Démonstration. Soit B facteur de u de longueur > Lü' D'après le Théorème 2, B admet une
factorisation unique B = Blf(A) B
avec 1Bi 1 < p, BI et B
respectivement dans 8 et P,
2
2
où 8 (resp. P ) est l'ensemble des suffixes (resp. préfixe) de longueur au plus p, des mots dans
f(a).
Le mot B dans Fn(k) signifie qu'il existe k lettres distincte al"'" a telles que
k
\\:j i E {l, ... ,k}; B/(A) B a
E F.
2 j
Chacun des B a
est préfixe commun
2 i est donc dans P , ce qui implique non seulement que B2
aux images d'au moins k lettres de a, mais qu'il en est le plus grand. Désignons alors par X le
sous-ensemble de a formé par ces lettres; on a card(X) ~ k et nous noterons card(X) = k + e, e
~O .
Le mot B dans FD(k) signifie aussi que
card{ PIB , + l (f(a)) ; a EX} = k.
2
Comme par ailleurs
1 B 1 = n = 1 BI 1 + pl A 1 + Àx ,
en posant 1 A 1 = p et 1 B 11 = r , on obtient:
n-À =
x
pp+r (O~r<p).
Deux cas sont à distinguer:
Premier cas: r > O.
Soit a le nombre de lettres a telles que BI soit suffixe de f(a). Alors :
B E FD(k) <=> ::J {al"'" au} ca; aiA E Fp(k~) .
Deuxième cas: r = O.
On a maintenant B = f(A)B
et
2
BE FD(k)
<=> AE Fp-l(k~)·
. ' - ... ;
.:
. . ~
... ,...
29
Nous écrirons alors n - À =
x
pp
pep - 1) + P ,pour "unifonniser".
La décomposition de n sous l'unique forme n - Àx = pp + r ,avec cette fois-ci
0 < r S p,
démontre le Lemme 5.
Soient Cl' C
dans F
2
p+l(he) ; par construction, ils donnerons deux mots différents de
F (k) si sp(CI)::I:- sp(C ) ou dans le cas contraire, si le plus grand suffixe commun à f(PI (Cl» et
n
2
f(PI (C » est de longueur strictement inférieur à r. li vient donc:
2
1 Fn(k)1 = I~~Ii card {sr(f(a»; a = PI(C) , C E Fp+I(k+~) et sp(C) = Ci}.
L'entier q(n) est donc parfaitement détenniné dès que q(p+ 1) et r sont connus. Si (P+ 1) est
superieur à Lü ,le Lemme 5 peut lui être appliqué. Ainsi de suite, nous déduisons la première
partie du Théorème 3, puisque pour tout n> Lü q(n) sera dans l'ensemble Q (parfaitement défini
au préalable) des valeurs prises par q(n) pour les n inférieurs à Lü .
o
En désl!gnant par or
l'application de Q dans Q qui à q(p+ 1) fait correspondre q(n)
lorsque n - Âx = pp + r (0 < r S p) on a alors le résultat suivant
LEMME 6. Pour tout n> Lü ,il existe un p automate (dont un programme formel indique
ci-dessous) qui donne la valeur de q(n) à partir de la décomposition de n sous laforme n - À.x
= pp + r (0 < r S p).
n : = n initiais
°:=Application identité dans Q .
t--~---------Tant que n > ~ ,faire
{
(n - Âx)p-l si entier,
p
[(n - À-X)p-l] + 1 sinon
r
n - pp + p + 1
°
n
p
JU
q(ninitial) = cr(q(n)) .
IV.3.- FIN DE LA DEMONSTRATION DU THEOREME 3.
Une légère transformation du programme fonnel du Lemme 6 nous donne le Lemme 7 suivant
qui termine la démonstration de la seconde partie du Théorème 3.
LEMME.-7 : Pour tout n > (ho' il existe un p-automate (dont on a un programme mm! formel
ci-dessous) qui donne la valeur de q(n) à partir de l'écriture de n en base p .
n : = n initiaIs
cr: = Application identité dans Q .
retenue: = 0
t - - - - - - - - - - - T a n t que (n + retenue) > ~ ,faire
m
[np-Il
s
n - [np-Il
Si (retenue + s - À) > 0 :
r
retenue + s - À
retenue
1
Sinon
r
retenue + s - À + p
retenue
o
cr
n
m
31
q(ninilial) := a(q(n)) .
IV.- COMPLEXITE POLYNOMIALE.
Le Théorème 3 donne:
PROPOSITION.- Pour toute suite minimale non périodique, pointfue d'une substitution uniforme
injective, pen) est de fonne polynomiale si et seulement si q(n) est une constante. De plus, le
polynôme est de degré au plus égal à un et son tenne de degré un est la constante q(n).
Démonstation. Supposons pen) = ~nk + ... + al + a o ' alors
k
q(n) = al + L aie (n + l)i - ni).
1=0
Comme q(n) prend un nombre fini de valeurs, on a
ai = a ,pour 2 ~ i ~ k . Ainsi q(n) = al
et p(n)=ao+ aln .
. :'
: ......: ' .. ::," . ..
."
',:.
32
v.- EXEMPLES
V.l.- SUITE DE MORSE
Soit ~ la suite de Morse donnée dans l'introduction. On a vu que les mots de longueur ~ 4
sont rythmés et un dénombrement direct donne q(l) = q(2) = 2 et q(3) = 4 .
Notons que fI (1) et f 1(2) n'ont ni suffixe commun, ni préfixe commun; ainsi pour n > 4 ,
q(n) = IF (2)1 = IF + (2)1 où 2(p+l) +r = n et r = 1 ou 2. Donc al = a = identité dans Q.
n
p 1
2
Pour tout n ~ 4, il existe un seul entier k tel que
2k+l<n~2k+2
Nous distinguons deux cas :
Premier cas:
2k+l + 2k < n ~ 2k+2 .
Nous avons alors 3 < n2-k ~ 4
donc 4 = n2-k SI n2-k est entier et 4 = [n2-k] + 1 sinon
et par suite q(n) = q(4) = 2.
Deuxieme cas:
2k+ l < n ~ 2k+l + 2k
Nous avons maintenant 2 < n2-k ~ 3 et un raisonnement analogue au cas précédent donne
q(n) = q(3) = 4 .
Dans tous les cas, en remarquant que 3.2-2 < 1 ~ 4.2-2 ; 3.2-1 < 2 ~ 4.2-1 et 3.20 < 4 ~
4.20 ,' on obtient en définitive q(n) = 2 pour tou entier n pour lequel il existe un entier relatif k
tel que: 3.2k < n ~ 4.2k et q(n) = 4 sinon.
Montrons à présent comment est obtenu q(n) à partir de l'écriture de n en base 2 .Soit n =
n 2s+... +n .2 + no' avec n
= 1 . Supposons q(n) = 2. Alors il existe k E
s
l
s # a ; on a donc ns
Z , tel que 3.2k < n ~ 4.2k , c'est - à - dire :
33
Si n
1
2
-
== 1 , alors k == s-1 et n
2s- + n _ 2s- +...+ n
s 1
_
S 1
s 2
o"# 0 , donc il existe i, 0 ~ i ~ s-2,
tel que ni == 1.
Si n _ == 0 ; nous avons maintenent k == s-2 et pour tout i, 2 ~ i ~ s-2, on a ni == 0 .
s 1
Dans tous les cas, q(n) == 2 si ns-l = 1 et s'il existe i < s-1 tel que ni == 1, ou SI
pour tout i < s , ni = 0 ; autrement q(n) = 4 . Le diagramme résume ce calcul:
non
oui
non
non
q(n) = 2
q(n) = 4
q(n) = 2
q(n) = 4
34
Fin
V.2.- SUITE DE RUDIN-SHAPIRO
La suite de Rudin-Shapiro compte les tt Il tt molulo 2 dans l'écriture de n en base 2 . Elle
est reconnaissable par l'automate suivant:
1
1
o
~)-~:~
O~--<I!.<~S~3-J'---~~ 0
o
1
Soit u le point fixe de la substitution 't associée à l'automate ci-dessus (cf. 1. 3) et de préfixe
1 . Ici les ensembles S et P sont disjoints, par conséquent, les facteurs de deux lettres sont
rythmés. Alors pour tout n
F (4) = F (3) = 0
n
n
donc
q(n)
IFn(2)1 = Li card { sr ('t(a) ; a = Pl (C), C ~ Fp+l (2) et sp (C) = Ci}'
Soit {C, C} c Fp+l(2) tel que sp(C) = sp(C') = Cl . On a toujours
s2 ('t(Pl(C))) #- s2('t(PI(C),
donc pour r = 2 , IFn(2)1 = IFp+ 1(2)1 et
a est l'identité.
2
D'autre part on a sl('t(Pl(C))) ~ sl('t(Pl(C))), En effet dans le cas contraire, le couple
(PI(C), (Pl (C)) vaut (1,3) ou (2,4); C = ICI ou C = 2C l et C' = 3Cl ou C' = 4Cl .
Alors 1 et 3 (resp. 2 et 4) se prolongent par une même lèttre, ce qui n'est pas le cas. Donc al
est l'identité.
Ainsi, q(l) = 4 et pour n ~ 2 , q(n) = 8 . Le calcul automatique est donné par le diagramme
suivant:
35
Introduire
les nj
non
oui
non
::3 ni' i < 0 ?
q(n) =
q(n)
4
= 8
~', ~ ~'';
., '{i';~~$k~;iii~'
- ~ ........
VI.- UN EXEMPLE NON MINIMAL
Soit u le point fixe dans
la* de la substitution f
définie sur l'alphabet a =
3
{l,2,3} par f3(1) = 121, f3(2) = 232, fl3) = 323. La suite u est reconnaissable par l'automate
(S,a,I,i) donné par le graphe orienté suivant:
1
0,2
0,2
1
0,2
sI (=i)
1
avec l'application
't: S -7 a
donnée par 't(sk) = k . Remarquons que l'on a la propriété
arithmétique suivante: l'entier n ne contient pas de chiffre l dans son écriture en base trois si et
seulement si un = 1.
Quel que soit l'entier k , 1 ne figure pas dans f k(2). Donc u n'est pas minimale d'après le
3
Théorème B. Montrons ce pendant que q(n) prend un nombre fini de valeurs et qu'il existe un
3-automate tel que q(n) en est la sortie lorsqu'on entre l'écriture de n en base trois.
Il suffit évidemment de montrer que le Lemme 5 (pour La = 1 par exemple) est vérifié.
Déterminons donc
Fn(k) pour k = 2 ou 3 . Fn(3) = 0 car u ne contient aucun terme a(2) ,
a = 1,2 ou 3 , et pour toute partie X de {1,2,3} , on a
card X > 1 :::::> Â. = °.
On est donc ramené à montrer que les éléments de F (2) sont les suffIxes de longueur n des
n
images des éléments de Fp+ (2) où p =nl3 si n est un multiple de 3 et p = [rat3] + 1 sinon.
1
Soit
aq+1aq+2 ... aq+n
dans
Fn(2) ; alors, il existe {xl'x2} dans {l,2,3} tel que
aq+1aq+2...aq+nxi soit dans Fn+1 ' pour tout i E [1,2]. Ainsi, il existe A dans F et j dans
{O,1,2} tels que f3(A) = aq_j aq_j+1 ...aq+1 ...aq+D ; autrement, on aurait aq+n_1 aq+ ou a
préfixe
D
q+D
commun aux images de deux lettres différentes, contradiction. Les lettres x 1 et x2 sont donc
respectivement préfixe des images de deux lettres différentes t et z . At et Az sont alors dans
F
+
(2) .
1A1 1 ' donc a E F 1A1
Par ailleurs, n < \\f3(A)\\ ~ n+3, donc lAI = (n/3) + 1 SI n est un multiple de 3 et lAI =
[n/3] + 1 sinon.
Réciproquement, soit a1~...apap+1 dans Fp+1(2) ; il existe alors {x1,x2} dans {l,2,3} tel
que a1~... ap+1xi soit dans Fp+2p' pour i = 1,2. Ainsi, f3(a1~.. ·ap+1x1) et f3(a1~...ap+lpx2)
2
sont dans F3(p+1)+3' Comme P1(fix1»;;t:. P1(f3 (x2», f(a 1a2...ap+1) E F3(p+1/ ) . Il en est de
même pour tout suffixe de ce mot et a fortiori pour les suffixes dont la longueur n est comprise
entre 3p et 3(p+ 1) , borne inférieure incluse.
p = nl3
si n est multiple de 3
3p ~ n < 3 (p+ 1) ~
{
p = [n/3] + 1 si n n'est pas multiple de 3
Le suffixe de longueur n prolongeable de deux manières est donc suffixe de l'image du mot
a1~...ap+1 de Fp+1(2). On a
q(n) = IF (2)1 = Li card {sr(f
D
3(a»
; a = P1(C) , C E Fp+1(2) et sp(C) = CJ.
Soit {C,C'} c Fp+l(2) tel que sp(C) = sp(C') = Cl; pour r = 1,2 ou 3 on a sr(f3(P1(C») ;;t:.
sr (f3(Pl(Cm donc IFD(2)1 = IFp+1 (2)\\ et O'r est l'identité. Ainsi
q(1) = 1 et pour tout n ~ 2 , q(n) = 2.
D'où le diagramme suivant:
Introduire
les l1ï.
non
oui
non
OUI
q(n) = 2
q(n) = 1
Les conclusions du Théorème 3 restent donc vraies bien que ~ ne soit pas minimale; la
minimalité n'est donc pas une condition nécessaire.
Notons que les suites périodiques vérifient également les conclusions du Théorème 3 , puisque
pour de telles suites pen) est constant à partir d'un certain rang.
Problème:
Comment caractériser les suites pour lesquelles les conclusions du Théorème 3 sont vraies?
40
BillLIOGRAPHIE
1.- ARSON S. : Démonstration de l'existence de suites asymétriques infinies.
MAT. Sb. 44 (1937): 769-777.
2.- BLEUZEN-GUERNALEC N. : Suites points fixes de transductions uniformes.
CRAS, Paris, T. 300, Série I, n° 3 (1985) : 85-88.
3.- COBHAM A. : Uniform Tag Sequences.
Mathematical Systems Theory 6 (1972) : 164-192.
4.- GOTTSCHALK W.H. and HEDLUND G.A. : Topological dynamics.
Am. Math. Soc. Colloq. Publ. Vol 36. Providence R.I. (1968).
5.- GOTTSCHALK W.H. and HEDLUND G.A. : A Characterization of the Morse Minimal Set
Proc. Am. Math. Society 15 (1964): 70-74.
6.- HEDLUND G.A. and MORSE M. : Symbolic Dynamics.
American J. Math.,60,(1938) : 815-866.
7.- KEANE M. : Generalized. Morse sequences.
Z. Wahrscheinlichk.eitstheorie Verw. Gebiete,10(1968) : 335-353.
8.- WTHAIRE : Combinatorics on words.
Addison Wesley Reading MA (1982): chapter 12.
9.- MARTIN J.c. : Substitution minimal flows.
Amer. J. Math 93 (1971) : 503-526.
10.- MARTIN J.c. : Minimal flows arising from substitutions of non-constant length.
Math. Systems Th. 7 n° 1 (1973) : 73-82.
11.- MORSE M. : Recurrent geodesic on a surface of negative curvature.
Trans. Amer. Math Soc. 22 (1921): 84-100.
12.- PANSIOT J.J. : A propos d'une conjecture de F. Dejeun sur les répétitions dans 1\\
. .~. '.-' .
.' . .
..:; .
.. .
..<~:-);i~~!~;·~~".:;· .."
. ' .
. '
41
(A paraître dans Discrete Applied Mathematics).
13.- QUEFFELEC M.:Contribution à l'étude Spectrale de suites arithmétiques
Paris-Nord Thèse d'Etat, 1984.
14.- RAUZY G. : Suites à termes dans un alphabet fini.
Séminaire de théorie des nombres. Bordeaux exposé n° 25 (1982-1983) : 1-16.
15.- RAUZY G. : Des mots en Arithmétique.
Journée Algorithmes et Complexités. Avignon 1973.
16.- THUE A. : Über unendliche Zeichenreihen.
.~.
~~~.'
:.. ..;"';:}
r' '
,
l(êSlHlh::- :
. .
,
On monLre que
f:i;-,Iif.::e
u nlL Tt ).111a~. ~~
par
uniforme,
tout mot· llJ,., clmes '-\\ et '.le l()ngllé:~ur as.,;ez, l.ongue admet HW" Liict'.Jl:.î.-
Sa.tiOll unique.
Ce résultat pe.ëlliet de n~con;::aitre par Ull automôte n __~ p(,,+i)··'P(-.:l) 0'..\\
"-