FOURUTLES DENA

A
IER N

ANNALESS
L’IN TIT

DE

L’INSTITUT FOURIER
Boris ADAMCZEWSKI
Symbolic discrepancy and self-similar dynamics
Tome 54, no 7 (2004), p. 2201-2234.
<http://aif.cedram.org/item?id=AIF_2004__54_7_2201_0>© Association des Annales de l’institut Fourier, 2004, tous droits
réservés.
L’accès aux articles de la revue « Annales de l’institut Fourier »(http://aif.cedram.org/), implique l’accord avec les conditions
générales d’utilisation (http://aif.cedram.org/legal/). Toute reproduction en tout ou partie cet article sous quelque forme que cesoit pour tout usage autre que l’utilisation à fin strictement personnelle du copiste est constitutive d’une infraction pénale. Toutecopie ou impression de ce fichier doit contenir la présente mention
de copyright.

cedramArticle mis en ligne dans le cadre duCentre de diffusion des revues académiques de mathématiques
http://www.cedram.org/

2201-SYMBOLIC DISCREPANCY AND
SELF-SIMILAR DYNAMICS

by Boris ADAMCZEWSKI

1. Introduction.
In this paper, we introduce two functions of discrepancy, one associated with symbolic sequences and the other with subshifts (respectively
defined in (1) and (2)). We mainly deal with the asymptotic behaviourof these two functions, focusing on sequences obtained as fixed points
of primitive substitutions and on subshifts arising from them. Such sequences naturally appear as soon as one studies dynamical systems with aself-similar structure (that is, the induced system on some subset is topologically conjugate to the original one). This is in particular the case for
one-dimensional toral quadratic rotations (see for instance [1]) and interval
exchanges with parameters lying in the same quadratic field [3]. This work
is motivated by questions arising at once from Diophantine approximationand ergodic theory and shares some links with [2], [22], [23], [8],[15].

We first recall the definition of discrepancy on a finite set. Let A
be a finite set. Endowed with the discrete topology, ,,4 is a compact set.
Let us consider a probability measure p on A. A sequence u(Un)nEN
which takes its values in ,A is said uniformly distributed with respect to themeasure p if=

where Xfal denotes the characteristic function of the set {a}. Then, we

Keywords: Discrepancy - Substitutions - Subshifts - Bouded remainder sets - Selfsimilar dynamics.
Math. classification: llK38 - 37A30 - 37A45 - 37BlO - 68R15.

2202

define the discrepancy function AN (A, u) of the sequence u by

These definitions, given for a finite set, come directly from the moreclassical notions of uniform distribution modulo 1 and discrepancy for real
sequences. Some generalizations to topological, compact or quasi-compact
groups could also be found in the literature. Two important references on
this subject are the books of L. Kuipers and H. Niederreiter [17] and of
M. Drmota and R.F. Tichy [7].

With any symbolic sequence u defined over a finite set, one can also
associate the dynamical system (O(u), T), where 0(u) is the closure of theorbit of u under the classical shift transformation T. This leads us to ask
the following questions: what could be a (natural) version of discrepancy
on such a symbolic space? How far is such a system from having an ideal

distribution?
Let u be a symbolic sequence, x(O(u), T) the subshift arisingfrom u, and p a shift invariant measure for u. Then, we define thediscrepancy function of the dynamical system x (with respect to p) by=

where [w] denotes the cylinder associated with the word w. This definition
is really close to the classical one given in the case of the torus, since wejust have replaced intervals by cylinders. Moreover, if (X, T, A) denotes auniquely ergodic dynamical system and f a continuous function on X, thenuniformly. The discrepancy function introduced above measures the uniform
speed of convergence of Birkhoff ’sums with a restriction to a class of very
regular continuous functions (i.e., characteristic functions of cylinders).
Since cylinders form a natural basis of the topology for the space O( u), we
can interpret DN (x) as a measure of unique ergodicity for subshifts having
this property. Note that it can be easily deduced from a classical result
generally attributed to Curtis, Lyndon and Hedlund (see for instance [18]),
arethat the order of magnitude of the functions ON (u) and2203

topological invariants (i.e., preserved by a topological isomorphism between
two subshifts).

This article is organized as follows. In Section 2, we present our
results (mainly, Theorem 1 and Theorem 3). We discuss spectral propertiesof primitive substitutive subshifts in Section 3. The main tool for proving
Theorem 1 is introduced in Section 4. Finally, Section 5 and Section 6 arerespectively devoted to the proof of Theorem 1 and Theorem 3.

2. Definitions and main results.
2.1. Symbolic sequences.

A finite and nonempty set
is called alphabet. The length of a finite
word cJ, denoted bylwl, is the number of letters it is built from. The
empty word, E, is the unique word of length 0. We denote by ,A.* the set offinite words on ,~4 and by A N the set of sequences on A. Let u =bea symbolic sequence defined over the alphabet A. A factor of u is a finite
word of the formithe set of all
j. We denote by
uj, 0
the factors of the sequence u,
is called the language of u. If w is a
finite word and a a letter, then Iwla is the number of occurrences of theletter a in cJ.
2.2. Substitutions.

Endowed with concatenation, the set ,~4* is a free monoid with unit
element e. A map from A. to A* B f El can be extended by concatenation
to an endomorphism of the free monoid ,,4.* and then to a map from ,A.~
into itself. A substitution a on the alphabet .,4 is such a morphism satisfying(i) there exists a E .A such that a is the first letter of a( a);(ii) for all
endowed with the product ofThen,converges inthe discrete topologies on A, to a sequence u. This sequence is a fixed pointof a, i.e., a (u) = u. Given a substitution a defined on A
f 1, 2,..., d},is called the incidence matrix associatedthe matrix M~ _with a. A substitution is primitive if there exists a power of its incidence
matrix for which all the entries are positive. To a fixed point of a primitive
substitution u we associate a natural probability measure tc on A, themeasure of a letter a E A being given by the value of its frequency in u,that is, p(a) = limn-o(the existence of frequencies isfor instance proved in [21]).
=2204
2.3. Spectrum of a primitive substitution.

The Perron-Frobenius theorem implies that the incidence matrix ofprimitive substitution admits a simple real eigenvalue greater than themodulus of all the others eigenvalues (see for instance [21]). This eigenvalue
is greater than one and is called the Perron eigenvalue of the substitution.
We order the spectrum SMa of the incidence matrix associated with aprimitive substitution o- as follows:awhere 0 is the Perron eigenvalue of a, d’ is the number of distinct eigenvalues
andwhere aj denotes the multiplicity of the eigenvalue 0j in the minimal

polynomial of Ma . Furthermore, if|0i| = |0k= 1, ai ak , 01 is not a rootof unity and 0k is a root of unity, then ik. With these conditions, theandarewell-defineda2quantities 0, ~82 ~](whereas several choice for the=value of 02 can sometimes be done).

Given a primitive substitution a, one can define its substitution oforder 2, denoted by a2 (see Section 6 for a precise construction). It is provedin [21] that such a substitution is primitive too and shares the same Perron
eigenvalue. Following (3), we can thus define the quantities ~92,2 ~ and a2,2,
associated with the spectrum of
2.4. Landau symbols.

Let f and g be two real positive functions. We recall the definition ofsome Landauof=symbols:

O(g) if exists C &#x3E; 0, such that f (x)Cg(x), for all x E R+,

The following notation will be used in the most of our results. We willwrite

if bothandThough such a relation does of course not imply that f - g, we willconsider, with a slight abuse of language, that the order of magnitude of
the function f is g, as soon as the relation f(0 n Q) (g) is satisfied.
=2205
2.5. Main results.

Following these definitions, a fixed point of a primitive substitution
is uniformly distributed with respect to its natural probability measure.

Our main result is a precise estimate of the discrepancy for such sequences.
We show how it is in part ruled by the spectrum of the incidence matrix
associated with the substitution. We prove that in most of cases (moreprecisely for cases (i), (ii) and (iii) of Theorem 1) the order of magnitudeof the discrepancy just depends on the incidence matrix. In these cases,
the asymptotic behaviour of the discrepancy is thus not modified by any
permutation of the letters in the definition of the substitution. However,
Theorem 1 could not be reduced to a result on primitive matrices sincecase (iv) really depends on the substitution. For instance, the two following
substitutions a and T respectively defined by:andshare the same incidence matrix but have a different discrepancy. Moreprecisely, the fixed point of a (generated by the letter 1) has a boundeddiscrepancy function, whereas the order of magnitude of the discrepancy
associated with the one of T is log N. Since we can associate to a primitive
substitition a natural probability measure p as in Section 2.2, we will writein the following ON (u) instead of AN (A, u) for the discrepancy of a fixed
point u of a primitive substitution.
Let u =
be a fixed point of a primitive
THEOREM 1.
substitution a defined over the alphabet A, 0, 02 and a2 defined as in
Section 2.3, ~ the natural probability measure associated with u (defined
as in Section 2.2) and-denotes the characteristic function of the set fal. Then, theholds:
followingwhere

is bounded;(i) if 1021 1, then(ii) if 1021 &#x3E; 1, then A N (u) = (o n 0) ((log N)a2 N(loge 1(21));(iii) if (92 ~=1

not a root of unity, then2206(iv) if~2! 1 and 82 is a root of unity, theneither A,,.,, =,4 0 and
=

or

and

where the complex number(which just depends on the pair (a, u)) isdefined in Section 5.4 and could explicitly be computed.
We derive from Theorem 1 the following characterization of fixed
points of primitive substitutions having an almost perfect distribution(that is, with a bounded discrepancy).

COROLLARY 2. A fixed point u of a primitive substitution a hasbounded discrepancy function ON (u) if and only if one of the following
holds:a(ii) ~82= 1, ~x2=

0, 02 is a root of unity and Aa,u=0.

Next, we consider dynamical systems arising from primitive substitutions, which are well-known to be uniquely ergodic subshifts (see [19]). We
prove an analogous of Theorem 1, for the discrepancy of these systems, withrespect to their unique invariant measure. The main interest of Theorem 3
is that it gives a uniform information with respect to all the factors, whereas
Theorem 1 just deals with letters. Theorem 3 is obtained via Theorem 1
together with the use of the notion of derived sequences introduced in [10].
However, Theorem 3 is far from being a simple by-product of Theorem 1.
THEOREM 3. Let u be a fixed point of a primitive substitution a,0, 02,2 and a2,2 defined as in Section 2.3, X (O(u),T,p) the dynamicalsystem arising from u, and=Then, the following holds:(i) if102,21 1, then DN(X) is bounded;(ii) if ~82,2 ~ &#x3E; 1, then .
(iii) if ~2,2!= 1 and 02,2 is not a root of unity, then

2207(iv) i£102,21=

1 and O2,2 is a root of unity, thenandIn particular, it follows that such dynamical systems are uniformly
well distributed with respect to their unique ergodic measure, that is:

COROLLARY 4. Let u be a fixed point of a primitive substitution a,x = (O(u),T,p) the dynamical system arising from u, then we have thattends to 0 uniformly in

Our method provides explicit constants for all the bounds given in
Theorem 1 and 3. In case (iv) of Theorem 1, it is even possible to computethe quantity

Most of the arguments to prove it are exposed in [2]. The quantities 02,2 anda2,2 could probably be replaced respectively by 82 and a2 in Theorem 3, but
at this point this can just be proved in the case where82&#x3E; 1. Theorem 1
and 3 are respectively proved in Section 5 and 6.

3. An application to spectral theory.
We first discuss how our results can be used to obtain a spectral
information for primitive substitutive subshits and thus for their measuretheoretic isomorphic dynamical systems.
Let x(X, B, p, T) be an ergodic dynamical system. For any B E L3
and x E X, we consider=

By Birkhoff’s ergodic theorem, for any B E ,~3 and almost all x E X ,2208

when N tends to infinity. A set B is called a bounded remainder set for T
if
is bounded on a set of measure one. For an irrational rotationon the one-dimensional torus, H. Kesten (more precisely, the "if" part isdue to E. Hecke in 1922) gives the following characterization of boundedremainder sets which are intervals.
THEOREM 5 (see Kesten [16]). - Let T be a translation on T by anirrational a. Then, an interval I is a bounded remainder set for T if andonly if its length belongs to Za mod 1.

sen

In 1973, H. Fiirstenberg, H. Keynes and L. Shapiro (see also K. Peter[20] and G. Halász [14]) proved the following strong generalisation of

Kesten’s theorem making relevant the notion of discrepancy in ergodic

theory.
THEOREM 6 (see Fiirstenberg and al. [13]). - Let (X,B,M,T) be an
ergodic dynamical system. If a subset B of B is a bounded remainder set
is an eigenvalue for T. Moreover, if
for the transformation T, thene21rir is an eigenvalue for T, there exists a bounded remainder set B E L3
such thatr.
=

In the symbolic framework, intervals could naturally be replaced bycylinders. Therefore, we can translate the previous problematic by: given asubshift, does there exist cylinders which are bounded remainder sets? Our
study answers partially this question in the case of primitive substitutive
subshifts. In particular, we obtain that, for a substitution satisfying the
1 (for instance the Fibonacci or Tribonacci subshifts), allcondition 02,2
arethe cylinders
bounded remainder sets. Theorem 3 proves even that inthis case there exists a uniform bound.

a

In view of Theorem 6, we can easily translate such results to provide
simple condition of non-weak mixing for primitive substitutive subshifts.

THEOREM 7. Let u be a fixed point of a primitive substitution aand x be the associated subshift. If AN (U) is bounded, that is, if one of
the following holds

is a root of unity and .

then, X is not ureakly mixing.

2209
In

particular, we recover that the subshift arising from a Pisot

type substitution (that is, the Perron eigenvalue is a Pisot number andthe characteristic polynomial is irreducible) is never weakly mixing. This
result, mentioned in [24], derives from one of B. Solomyak [26] but we do
not require in Theorem 7 the irreducibility of the characteristic polynomialof the incidence matrix, contrary to the assumption done in [26]. Moreover,since the sets considered are cylinders, one expects to be able to compute
their measures. Corollary 2 and Theorem 3 provide thus a concrete way
to obtain eigenvalues for a primitive substitutive subshift. In the case of
the Fibonacci and Tribonacci subshifts, all the eigenvalues can be foundby proving that any cylinder corresponds to a bounded remainder set andusing the fact that the eigenvalues form an additive group. More precisely,
we can deduce from our study that the discrepancy functionisbounded for these two subshifts. Such a result is probably also true for
all Pisot type substitutions.

4. Notation and preliminary results.
In this section, we introduce the main tool that we will have to use
for our study together with some preliminary results.
4.1. The

S( (N) functions.

In order to estimate the discrepancy of a symbolic sequence u, it isuseful to associate a "weight" with each letter of A. Then, the study ofthe discrepancy takes the following formulation: what is the number ofoccurences of each letter in a given prefix of u‘? We already used this ideain [2] for particular sequences, and we propose now to give a more generalstatement of this fact. The properties of (S£(N))NEN* were investigated,in particular for some sequences related to the distribution of digits inarithmetical sequences, in [4], [5], [6], [8], [9], [23].
DEFINITION 8.
Let udefined over the alphabet A
and N C N*, then we define-=~ ’’’ be= {l,2,...,d}.

asymbolic sequenceCCd

If f =

2210

Just as, if cJ E A*, we define

be a sequence defined over
the alphabet .4= {1,2,...,~} and such that each letter a of ,A admits aC (Cd denote the frequencies
positive frequency p(a) in u. Let A
vector of u. Then, for 1 i d - l, vve introduce the vectors fi E C~,
defined by
DEFINITION 9. Let u==

PROPOSITION 10. - The two following assertions are equivalent:

In (i), the constant in the 0 just depends on z.c and in (ii), it depends onu and f.

Proof. Since

the previous definition implies

and the fact that the fi form a basis of the vectorial spaceends theproof.
PROPOSITION 11. The two following assertions are equivalent:

Proof. - It comes directly from (5).
For any word w E ~4*, let us introduce the vector

Then, for a substitution a devined over ,,4 we have

D

2211

where Met denotes the incidence matrix of a. For fixed i and j in A, thesatisfies a linear reccurence whose coefficients aresequence
those of the minimal polynomial of M~ . Following Section 2.3, there exist
and Ai,j such that for every n E N,
complex numbers

Let us notice that Equations (6) and (7) imply that, for each letter j,
the vector (Ai,j)iEA is an eigenvector of M~ associated with its Perron
eigenvalue 8. There thus exists a complex number Ei such that Ai,j ~~ ~(i) .
Then, for any vector f(/(z))~=i,2,...,d ~ Cd lying in the orthogonal
vectorial space spanned by J1, it follows:==

Since for k &#x3E; 2, 1021 2::

where the constant in the 0 just depends on j, if we assume f and a fixed.
Then, for every word cv E

if we assume f and a fixed.
where the constant in the 0 just depends on
In order to make the following more friendly readable, we introduce thefollowing notation

where w=úJlúJ2 ... cJm is a word defined over A and f a vector lying in theorthogonal vectorial space spanned by p. It thus implies

2212
4.2. Numeration systems associated with substitutions.

We present now the key tool for proving Theorem 1. These generalized
numeration systems associated with substitutions have been introduced
simultaneously by J-M. Dumont and A. Thomas [8], and G. Rauzy [23].
DEFINITION 12. - Let a be a substitution and let us assume thatu is a fixed point for at generated by the letter 1. The subset of A*
composed by the proper prefixes of the image by a of the letters will bedenoted by Pref ~ . The pre fcx automaton associated with the pairis defined in the following way:~

,A is the set of states,~

Pref ~ is the set of labels,

there is a transition from the state i to the state j labelled by the(possibly empty) word m if m j is a prefix~

Figure 1. Example of a prefix automaton in the case of thesubstitution 1 H 13, 2 - 13223, 3 H 1323.

DEFINITION 13.
An admissible labelled path C in theautomaton associated with a pair (a,u) will be denoted by-

prefixn - 1. The positivefor 0 j n and Ei E Pref ~ for 0 j
integer n is the length of the path. The set composed by the admissiblelabelled paths of length n will be denoted by C~ .

with ii E

The main theorem concerning the prefix automaton is the following.

,

THEOREM 14 (see Dumont and Thomas [8], Rauzy [23]). Let u bea fixed point generated by the letter 1 of a substitution a, then uje have:2213(i) for every positive integer N, there exists a unique admissible pathof length nN in the prefix automaton associated with the pair (a,u),
starting from 1 and labelled by the sequence (En, E1 ,E~,, ~, ), such that
where UN denotes the prefix of u of thelength N and such that Eo # E.
...

,(ii) Conversely, to any such a path, there corresponds a unique prefixof u, given by the above formula.
(iii) Moreover,
The remaining of the paper is now devoted to the proofs of the main
results.

5. Proof of Theorem 1.
This section is devoted to the proof of Theorem 1. Most of theupper and lower bounds are respectively stated in Section 5.1 and 5.2.
The essential difficulties appear when ~92 ~]1 and this case is treated in
Section 5.3.
=

5.1. First upper bounds.

We apply Theorem 14 in order to obtain upper bounds for thediscrepancy of fixed point of primitive substitutions.
PROPOSITION 15. Let u be a fixed point of a primitive substitution,then:if82( 1, thenif ~82 ~ &#x3E; 1, then. if ~2) = 1, then~is bounded,.

where the constants in the 0 just depend on u.
Proof. Equality (9) together with the fact that the words Ei in
Theorem 14 lie in a finite set imply, and thus

where nN is defined as in Theorem 14. One can notice that assertion (iii)of Theorem 14 implies in view of Equality (7) that2214

We thus deduce

Then, we have to distinguish three cases, depending on the modulus of theeigenvalue 82, and using (11), it follows that
then
then
then

where the constants in the 0 just depend on u and f. Proposition 10 allows
us to conclude.
D
5.2. First lower bounds.

We want now to show the pertinency of Proposition 15. Hence, weare going to construct a sequence of prefixes of u with the worst possible
distribution. Following Proposition 11, we know that it is sufficient to
exhibit a vector f E C~d, f 1 p, and an increasing sequence of integers,
such that the sequence
takes "high" values, in asense that we will have, of course, to make clear.
Let us first recall the following classical result of linear algebra.
LEMMA 16. - Let M be a d x d complex matrix and let us denotethe spectrum of M, wheremean the distinct
eigenvalues of M and the ai their multiplicity in the minimal polynomialof M. Let r be a positive integer and 0 a non-zero eigenvalue of Mr, thenthe multiplicity of 0 in the minimal polynomial of M~’ is equal to the
maximumsuch thatof f ai

82 = 8, 1 i d’ ~ .

If we apply the previous lemma to the incidence matrix associatedwith the primitive substitution ~, we obtain the following.

COROLLARY 17.

-

Let k beapositive integer. Let us denotethe spectrum of ak,iUordered as in 2.3. Then, the following holds:

by f 0’; 2sothat the 0’

are

and
In view of Corollary 17, we can thus freely consider any power of awhithout changing the conditions which appear in Theorem 1. We are now
ready to prove the following.

2215

PROPOSITION 18. - Let u be a fixed point of a primitive substitution,then if1021 &#x3E; 1, then

Proof. If j is a fixed element of ,~4 and 2kd’, then thedefined in (7) are eigenvectors associated with the
eigenvalue 0k (or eventually zero vectors). That follows directly from
Equations (6) and (7), and from the fact that the sequences
form a free familly of the vectorial space spanned by complex sequences.
Moreover, there exists at least one letter jo such that the vector0 )iE.a
is a non-zero vector, because otherwise this would provide a polynomial P
of degree less than the one of the minimal polynomial associated with M
and such that P(M)
0. Let us consider the following vectorial subspace
vectors(.À;’J2=

of Cd:(.À;’J2

is a non-zero vector, it is an eigenvector associated withSince
0
the eigenvalue 82 and it thus does not lie in E. Hence,

There thus exists a vector fo=

E cd such that f o E

andf0 x (a2,x2) iea
oie .

Because of the primitivity of a and Corollary 17, we can assume
without restriction that all the entries of the incidence matrix associatedwith a are greater or equal than two, which implies:othe prefix automaton associated with a is strongly connected, thatis to say, for any pair (i, j ) E ,A.2, the path (i, j ) is admissible.
~

for any pair (i, j) E .A.2, the letter j has at least one occurence in aproper prefix ofin which the letter jo
In particular, there exists a proper prefix
occurs. Let us denote by wlw2
· wr-lwr, wr - jo, such a proper prefix.
...

Then, we distinguish two cases:oeither

o or

2216

with wr = jo. In any case, there exists m E {r 2013 1, r} satisfying

We have

where the constant in the 0 just depends on w (for a fixed pair (a, f o ) ) . Thisimplies thatf~(?7~~~). Since u begins with 1, úJ is a prefix of
let
u and
too.
Then,
=

and there exists a positive constant C such that:which ends the proof

It follows thatin view of Proposition 11.

05.3. The critical case.

Proposition 15 and 18 give the right order of magnitude of
if~2! ~ 1. When1021 1, we just obtain that the extreme irregularities lie
between (log N)‘~2 and (log N) 12+1. In particular, we are a priori not able
1 and a2
0. The following
to say if A N (u) is bounded or not when82 ~section is precisely devoted to the understanding of these critical cases.
We will show that the knowledge of the incidence matrix associated withthe substitution is not always sufficient to solve this problem. However, we
provide an algorithmic way of answering it in the contentious cases.
===

5.3.1. Case (iii) of Theorem 1. - The following proposition statesthat the discrepancy is maximal (in view of Proposition 15) when 02 is nota root of unity.

2217

If 1021PROPOSITION 19. Let u be a fixed point of a primitive substitution.
1 and 92 is not a root of unity, then=

Proof. Let u be a fixed point of a primitive substitution a and let
that1021] = 1 and e2 is not a root of unity. There thus exists areal q, q g Q, such that82.
us assume=

We recall that the primitivity of a allows us to assume without
restriction that all the entries of M are greater than or equal to two (seeCorollary 17). As in the first part of the proof of Proposition 18, we canprove the existence of:
9avectorfo E cd and a letter jo such that fo c E1-

and

where
proper prefix ofdefinition of Ffo,2,a2 (w)).
o aw, such that

Ffo,2,1"2 (W) y~- 0 (see (10) for aThis implies that

where the constant in the 0 just depends on w.
Let us consider a positive integer N. Following Theorem 14, there
exists a unique admissible path in the prefix automaton associated withthe pair (a, u), beginning with 1 and labelled by (Eo, E1, ... ,EnN ),such thatWe thus have

The fact that the prefixes Ei lie in a finite set (Pref ~ ) implies

where the constant in the 0 just depend on u. There thus exists a positive
number C independent of N, such that:

2218

The next step consists in exhibiting a sequence (Cj)jEN of arbitrarily
large admissible paths in the prefix automaton associated with the pairand((1, u), starting from the state 1, labelled by (Eo, E1, ... ,such that

where the integers Nj are given byThen, Equation (13) and Proposition 11 will allow us to conclude that
because the assertion (iii) in Theorem 14 ensures

=

that

=

0(1).

Since w is a proper prefix of ~(1), there exists a letter jo such thata prefixisThe labelled pathis thus admissible.
wjo
Let us denote by
the sequence of states defined as follows:
and more generally let
be the firstji is the first letter

Hence, for every positive integer k, the labelled path

letterbeing finite,that~is admissible. The set A
find two positive integers l~o and
1~1 &#x3E; ko, such
Then, we have to distinguish two cases:

we caneither iko - 1,
1.

We first assume that

1, as it is represented on Figure 2.

Figure 2. CaseLet us consider a real 6, 7r &#x3E; 6 &#x3E; 0 and V a subset of C defined by

2219

Then, there exists a positive number c such that for any positive integer N

Let a be an irrational number and I an interval of the one-dimensional
then there exists a positive integer m such thattorus

as it is for instance proved in [25]. The irrationality of 1 ensures, in viewof (15), the existence of a sequence of integers (nk)kEN and of an integer msatisfying
and,,In particular, Inequality (14) implies

For any positive integer j, let us denote by Cj the labelled path of length nj
defined in the following way:

This labelled path is admissible in the prefix automaton associated with thepair (a, u). Moreover(E) 0 and we can deduce from Equation (13)and assertion (ii) in Theorem 14 the existence of an integer Nj satisfying=

Therefore, Inequality (16) implies that2220

and since (iii) in Theorem 14 ensures that]nj -0 (1), we

havewhere M is positive and does not depend on j. Hence, the sequence oflabelled paths
provides an increasing sequence of integers
such that

Since ON (2t) =has already been proved in Proposition 15,
this ends the proof in the case j~o1.
=

Figure 3. Case1.

The case jko =I 1 (see Figure 3), is similar but a little bit more
technical. It can be dealt by using, instead of (15), the fact that for any
irrational a any interval I of T there exists a positive integer m satisfying
and5.4. Case (iv) of Theorem 1.

We begin this section with a definition of the complex number A,,,,is strongly
used in Theorem 1 and Corollary 2. The meaning of
connected with the notion, introduced in [2], of elementary loops in theprefix automaton.
DEFINITION 20. - Let a be a substitution and let us suppose that u
is a fixed point for a generated by the letter 1. We call elementaryin the...,loop any admissible labelled paththeassociatedwiththeautomaton
satisfying
followingpair(o,,u),
prefixconditions:2221

We will denote by
the set composed by all the elementary loops inthe prefix automaton associated with the pair (a, u).
Remark 21. - Since
Let a beaand Prefa are finite sets,primitive substitution definedu) is finite too.
over

the

alphabet,,4. - ~ l, 2, ... , d~ and such that e2 is a root of unity. This implies (seeSection 2.3) that all the eigenvalues of M~ whose modulus equals one andwhose multiplicity equals a2 are roots of unity. Then, let no be the l.c.m.
of the orders of these eigenvalues (considered as roots of unity).
Let u be a fixed point for a generated by the letter 1. The sequence u isthus also a fixed point generated by the letter 1 for ono. For any admissiblelabelled path C(( io, iI, Eo), ... , (in- i , in , En- i ) ) , in the prefix automaton
associated with the pair (ana, u), we introduce=

where
is defined following Equality (10). For any vector f E Cd,
we introduce the quantity

Then, we can define a complex number, denoted bypair (r, u), byjust dependingon thewhere vectors fi are defined as in (4).
We are now ready to state the following proposition.
PROPOSITION 22.
Let u be a fixedsubstitution a. If 02 is a root of unity, then-9

point of the primitive

either A,,,, 54 0 and2

or Aa,u = 0 and
In order to prove Proposition 22, we first need the two following
results.

2222

LEMMA 23. - Let C be a positive number. Then, for any sequenceof complexe numbers
C for any positiveak
satisfying
wehave
integer m,

I 2:::=0 I

the constant in the 0 just depending on C.

Proof. It comes directly from a classical Abel summation.

D

LEMMA 24. Let u be a fixed point of a primitive substitution and f
be a vector in Cd such that f 1 ~. Then, there exists a constant C &#x3E; 0 suchthat for any admissible labelled path C in the prefix automaton associatedwith the pair ( ,u), one can find (B1,B2, ...
possibly equal
to zero, satisfying

defined following Equality (17).

whereProof. Let us reason by induction on the length n of the path. Letmeans an admissible= maxf Ff 2,12 (C)thendefinitionof C we haveofsmallerthanortopath length
equal d,byus consider C

which shows that the proposition is satisfied for nd.

Now, let n E N, n &#x3E; d, and let us assume that the proposition issatisfied for any admissible path of length k, k n. If

is an admissible labelled path of length n, then there exists (.~, h)in f 0, 1, 2,..., nl2, lh, such that if ih since the cardinality of isequal to d. Let us denote by h’ the minimum of ~m ; m &#x3E; I, suchthat
It follows that (~,...,z~) is an elementary loop andis an admissible labelled
induction hypothesis
the
n.
to
than
or
of
smallerThus,
equalpath length
=

=

2223

implies that there exists (Bi, B2, ... ,eventually equal to zero,such thatBut

and thus if ,it follows that

concluding the proof.

0

Proof of Proposition 22. - We can assume 92=

1 without restriction.

We first assume that
0. Let f be a vector in C~ such thatf L p and N be a positive integer. Following Theorem 14, there exists

such that

The fact that the Ei lie in the finite set Prefer implies that

where the constant in the 0 just depends on u. We thus have to show that

Lemma 24 implies the existence of a positive C andinsuch thatsince by definition

But if2224

then Ff,2,a2 (B) = 0 for any B E

which gives

Since C does not depend on the path C and thus on the integer N, Lemma 23
implies that

where the constant in the 0 does not depend
Following Proposition 18, we obtain that
because nN = log N + 0(1).

Now, let us assumeon

the choice of N.

(o n O)((logN)01522)

0. There thus exists a vector fj, defined as
0. Let us denote byin (4), such that

an element

satisfying ~F~2,c~(~)!
Since the prefix automaton is strongly connected, there exists anadmissible labelled path starting from the state 1 and ending in io.
Let Co(~-1~0~-1)) be such a path,
1. For every positive integer 1~, we introduce thewithand aofollowing labelled path
=

=

...,

=

This path ofsatisfies

length -I- kp is thus admissible, begins with 1 andc. Following the proposition (ii) in Theorem 14, there
exists a positive integer N~ such that

Moreover, following Equality (12), we have kp implies that

Finally,
Proposition 11 and 18.

whichwhich ends the proof in view of2225

Proof of Theorem 1.
and 22.

-

It comes directly from Propositions 15, 18, 19
0

6. Proof of Theorem 3.
The goal of this section is to prove Theorem 3. We proceed as follows;
first generalize Theorem 1 (see Proposition 28) and next we have to
study the discrepancy of the derivative sequences associated with a fixed
point of a primitive substitution (see Lemma 31 and 32) in order to founduniform bounds in Proposition 28. Then a finitude argument due to [12](Theorem 30) will allow us to conclude the proof.
weDiscrepancy functions associated with a symbolic sequence.
We give here a generalization of Theorem 1. The discrepancy function
associated with a symbolic sequence ic measures the speed of convergenceof the vector

towards the frequencies vector of the sequence u. We want now to introduce
a similar notion but with words playing the role of letters. Let u be asymbolic sequence defined over the alphabet A. Then, we can define, forany positive integer n, a discrepancy function of order n for u, in thefollowing way:wherelulw denotes the number of occurrences of the word w in the word u.
In view of the previous study,
We obtain in particular( u) =
it is quite natural to ask if we can estimate the growth order of these
discrepancy functions in the case of fixed points of primitive substitutions.
In particular, is it possible to obtain such an information in terms of theincidence matrix associated with the substitution?
In order to answer this question, we recall now a useful construction
which can be found in [21]. Let a be a primitive substitution defined over thealphabet ,,4 and u an associated fixed point. For any positive integer ~, A£
where Pu is the complexity function
denotes the alphabet {1, 2,...,
towich associatesof u. We can thus consider a map 8£ from2226

with each factor of length its order of occurrence in u. If i denotes aletter of the alphabet At, we can conversely associate with i a uniqueword
E £i( u) since ei is one-to-one. If
wow,
=

...

then, we define the substitution of order I for a by

So defined,-

We recall now some results about the previous construction.
PROPOSITION 25 (see Queff6lec [21]). - For every positive integer .~,the substitution of order f for a subtitution a admits the sequence
as a fixed point. Moreover,means
Ulthen the sequenceis composed by all the factors of length .~ of u
without repetition and in the same order as in u, that is to say,=

We can already notice that if

thenThis implies in particular the following corollary.

COROLLARY 26. - The order of magnitude of the discrepancy functionof order f for u is the same as that of the discrepancy function (of order 1)of Ut.
PROPOSITION 27 (see Queffélec [21]). - If a is a primitive substitution
then for every positive integer f, the substitution ag is primitive too andits incidence matrix Mg has the same Perron eigenvalue as the one of a.
&#x3E; 2, are those of M2 with perhaps in addition the
The eigenvalues
ifeigenvalue 0. Moreover, P2 is the minimal polynomial of M2, then there
where Pg means the minimal
exists an integer m such that Pg-

polynomial of ME.

2227

Following Equation (2.3), we can notethe spectrum of the incidence matrix associated with at. Proposition 27
means theimplies that Of = 0,02,2 and af,2 a2,2, wherein the minimal polynomial of Mg . In view of Corollary 26
multiplicity ofand Proposition 27, we can state the following result.
==

PROPOSITION 28. Let u be a fixed point of a primitive substitution a. Then, for every integer 1 &#x3E; 2, we have:is bounded;(i) if82, 2 ~ 1, then(ii) if ( 82, 2 ~ &#x3E; 1, then A(’) (u) - (o n(iii) if I82,2I 1 and 82,2 is not a root of unity, then

182,21);=(iv) if 102,21=

1 and 82,2 is a root of unity, thenandMoreover, in the case where 02,2 is a root of unity, then:9either for all

. or

J

there exists an integer m &#x3E; 2 such that, for,and forFor proving Proposition 28, we need the following lemma.
LEMMA 29.
be a positive integer, u an infinite sequence
defined over the alphabet A and suppose that there exists a function .f such
that
Then, we have-

Lemma 29 points out the fact that the order of magnitude of thediscrepancy functions(u) associated with a symbolic sequence u could
not decrease with respect to .~.

Proof of Proposition 28.
Equalities (i), (ii), (iii) and (iv) comefrom
directly
Corollary 26, Proposition 27 and Theorem 1. Then, the last0
point of Proposition 28 is a consequence of Lemma 29.
-

2228

Discrepancy for derivative sequences.
The different constants obtained for ON in Proposition 28 depend apriori on .~. To state Theorem 3 the next step is to prove that one can founduniform constants in Proposition 28. Our approach consists in exhibitingsome connections between the discrepancy of a linearly reccurent sequenceand the one of its derivative sequences and then to use a finitude argument
given in [12] (Theorem 30). Then, the last step will be to show that one candeal with any sequence v E 0(u) insted of the sequence u itself.
We recall the main definitions and results that are given in [12]concerning the notion of return words. Let u be a uniformly recurrent
sequence over the alphabet ,,4 and let u be a nonempty factor of u.
A return word to u of u is a factor(= UiUi+1 ... Uk-1) of u suchthat i and are two consecutive occurrences of u. If j denotes the firstcan be written in a uniqueoccurrence of u in u, the sequencebe the set of
way as a concatenation of return words to u. Let
return words to u in u. Then Ti (u) =Wi ..., where wi E
The fact that u is uniformly recurrent implies thatis a finite set.
fromto the finite
We can therefore consider a bijectivefor
returnwords
set ~1, 2, ... ,Au,u, where, definiteness, theis the firstare ordered according to their first occurrence (i.e.,
return word LUO,
is the first Wi which is different from wo , andso on). The derivative sequence of u on u is the sequence with values in theq&#x3E;~~(1)P~,~(2)alphabet

given byTo such a sequence we can associate a morphism 8u,u fromdefined by

We obtain

=

to A*

The morphism 8u,u is called the returnmorphism to u of u.
An important point is that one can characterize primitive substitutive
sequences in terms of derivative sequences.

THEOREM 30 (see Durand [12]). Let u be a uniformly recurrent
sequence. Then, the set Der(u) of its derivative sequences, is finite if andonly if u is a primitive substitutive sequence.

2229

Now, if WI, w2, ... , Wk denote some factors of u, we define thequantities

Let u be a K-linearly reccurent sequence, w be a factor of u and v be
the derivative sequence of u on w. Then, the sequence v is also linearlyrecurrent (with another constant) and this implies that any letter in v has afrequency. It thus exists a natural probability measure v for v (in the senseof Section 2.2). We will thus write
instead offor the
v.
of
with
the
to
discrepancy
sequence v
respect

Then, we can state the following.
LEMMA 31. Let u be a K-linearly reccurent sequence, w be a factorof u and v be the derivative sequence of u on w. Then, there exists a
constant C such that

where wl , w2 , ... ,wr denote the return words of u to w.
LEMMA 32. - Let v be a derivative sequence of a K-LR sequence u.
Then, there exists a constant Cv such that for any factor w of u satisfying
Dw (u) = v the following holds:

Proof of Lemma 31.
Let w be a factor of the sequence u andv = Dw (u) be the derivative sequence of u on w. Let j denote the firstoccurrence of W in u and r the cardinality of the set
The invariant
measures associated with u and v are respectivly denoted by A and v(we refer the reader to [11] for a proof of the unique ergodicity of a linearlyrecurrent subshift). We will write 0 instead of 8u,w.
-

where T denotes the usual shift.
We thus obtain that 8(v) =With any integer m, we can associate an integer n such that

2230

Since u is K-LR, we have that j
a return word

Km. Moreover, we have by definition ofThenwhich implies
follows that forfor

It thus

Let us now consider the following d x d real matrix:

where

It thus follows that

By a simple computation one can check that M is invertible if and only ifThisimplies the existence, forinteger nr, of coefficentsjsuch that for any integer m there exists an

Km satisfying

every

1

2231
and therefore the existence of a positive number C satisfying

concluding the proof.

0

Proof of Lemma 32. - We keep here the notation of the previous
defined byproof. Let us introduce the vector fw=

By definition of a derivative sequence, we are allowed to claim that

where i denotes the first occurence of w in the sequence u and m and n are
defined as above (we recall in particular that m n Km) . By definitionnu ([w]) = o(n), and thusof the measure u, we have

In view of Equality (8), we obtain that f~, 1 ~C’, where it’(l/(~2~))i=1,...,ris the frequencies vector of the sequence v. As we have already noticed,
the familly of vectors ( f ~ ), 1 k r - l, defined by
=

if

else,
is a basis of the vectorial subspace (p’) ’. There thus exist coefficientssuch that
Since it is K-LR, one(~i,..., ~-1) E
has lwl - ~,(~wJ)
K (see [11]). It follows that 0p([w]) K2 andK2. The fact that
thus

impliesI

Moreover, by linearity we haveand it thus follows

K2 , there exists a constant Cv, which does not depend on
hence the proof.
0
the choice of w, and such that

2232
Let u be a fixed point of a primitive
Proof of Theorem 3.
substitution o- and JY = (0(t~),r,~) the dynamical system arisingfrom u. In order to fix the ideas, we assume that102,21 &#x3E; 1 and wenote f (N) - (log N) a2,2 Nlogg102,2 1. Then, Proposition 28 implies thatand that for any word w E ,C(u),DN(X)
O(f (N)).
It remains to prove thatO ( f (N) ) . If wl , w2, ... ,wd, denote thereturn words of u to w, we thus deduce that there exists 01 &#x3E; 0 such that
-

.

=

=

Now let v be the derivative sequence of u on w. Lemma 31 thus implies theexistence of C2 &#x3E; 0 satisfying AN (V)C2 f (N), because f is a sublinear
for all x, y) and hence
function (that is,with C3 &#x3E; 0 since, following Theorem 30, Der(u) is a finite set. Therefore,
Lemma 32 implies

for some C4 &#x3E; 0.

and j be the first occurrence of the word
in u (such an occurrence always exists by minimality). Since u
Wo ...
is linearly reccurent, there exists K &#x3E; 0 (just depending on u), suchthat j KN. Then, we have
Let w

_

where C5 neither depends on w nor on w, since f is increasing and sublinear.
Finally, we obtain thatO( f (N)), which achieves the proof since
the other cases could be dealt exactly in the same way.
0=

Acknowledgments. - I would like to thank Val6rie Berth6, Nicolas
B6daride, Pierre Liardet and Christian Mauduit for useful discussions andcomments during the preparation of this paper. The author is also gratefulto the anonymous referee for valuable suggestions.

2233

BIBLIOGRAPHY[1]

B. ADAMCZEWSKI, Codages de rotations etJ. Théor. Nombres Bordeaux, 14 (2002), 351-386.

[2]

B. ADAMCZEWSKI, Répartitions des suites (n03B1)n~N et substitutions, Acta Arith.,
112 (2004), 1-22.

[3]

M.D. BOSHERNITZAN, C.R. CARROLL, An extension of Lagrange’s theorem tointerval exchange transformations over quadratic fields, J. Anal. Math., 72 (1997),
21-44.

[4]

J. BRILLHART, P. ERDÖS, P. MORTON, On sums of Rudin-Shapiro coefficients II,
Pacific J. Math., 107 (1983), 39-69.

[5]J. COQUET, A summation formula related to the binary digits, Invent. Math., 73[6]F.M. DEKKING, On the distribution of digits in arithmetic sequences, in Seminaron number theory, 1982-1983 (Talence, 1982/1983), exp. n° 32, 12, Université
Bordeaux I, Talence, 1983.

[7]

M. DRMOTA, R.F. TICHY, Sequences, discrepancies and applications, SpringerVerlag, Berlin, 1997.
J.-M. DUMONT, A. THOMAS., Systèmes de numération et fonctions fractales
relatifs aux substitutions, Theoret. Comput. Sci., 65 (1989), 153-169.
J.-M. DUMONT, A. THOMAS, Digital sum problems and substitutions on a finite
alphabet, J. Number Theory, 39 (1991), 351-366.
F. DURAND, A characterization of substitutive sequences using return words,
Discrete Math., 179 (1998), 89-101.
F. DURAND, Linearly recurrent subshifts have a finite number of non-periodic
subshift factors, Ergodic Theory Dynam. Systems, 20 (2000), 1061-1078.
F. DURAND, Combinatorial and dynamical study of substitutions around thetheorem of cobham, in Dynamics and Randomness, Nonlinear Phenomena andComplex Systems, p. 53-94, Kluwer Acad. Publications, 2002.
H. FURSTENBERG, H. KEYNES, L. SHAPIRO, Prime flows in topologicaldynamics, Israel J. Math., 14 (1973), 26201438.
G. HALÁSZ, Remarks on the remainder in Birkhoff’s ergodic theorem, Acta Math.
Acad. Sci. Hungar., 28 (1976), 389-395.
C. HOLTON, L.Q. ZAMBONI, Geometric realizations of substitutions, Bull. Soc.

phénomènes d’autosimilarité,(1983), 107-115.

[8]
[9]

[10]
[11]
[12]

[13]
[14]
[15]

Math. France, 126 (1998), 149-179.

[16]

H. KESTEN, On a conjecture of Erdös and Szüsz related to uniform distribution
mod 1, Acta Arith., 12 (1966/1967), 193-212.

[17]

L. KUIPERS, H. NIEDERREITER, Uniform distribution of sequences, Pure andApplied Mathematics, Wiley-Interscience, New York, 1974.

[18]

D. LIND,

[19]
[20]

B. MARCUS, An introduction to symbolic dynamics and coding,Cambridge University Press, Cambridge, 1995.
P. MICHEL, Stricte ergodicité d’ensembles minimaux de substitution, C. R. Acad.
Sci. Paris Sér. A, 278 (1974), 811-813.
K. PETERSEN, On a series of cosecants related to a problem in ergodic theory,
Compos. Math., 26 (1973), 313-317.

2234

[21]

M. QUEFFÉLEC., Substitution dynamical systems - Spectral
Notes in Mathematics 1294, Springer-Verlag, Berlin, 1987.

[22]

G. RAUZY, Nombres algébriques et substitutions, Bull. Soc. Math. France, 110[23]

G. RAUZY, Sequences defined by iterated morphisms, in Sequences (Naples/Positano, 1988), p. 275-286, Springer, New York, 1990.

[24]

A. SIEGEL, Représentation géométrique, combinatoire et arithmétique dessystèmes substitutifs de type Pisot, Thèse de doctorat de l’Université de la Méditerranée, 2000.

[25]

N.B. SLATER, Gaps and steps for the sequence n03B8 mod 1, Proc.
Philos. Soc., 63 (1967), 1115-1123.

[26]

B. SOLOMYAK, On the spectral theory of adic transformations, in Representation
theory and dynamical systems, p. 217-230, Amer. Math. Soc., Providence, RI,

analysis, Lecture(1982),147-178.

Cambridge

1992.

Manuscrit reCu le 2 octobre 2003,
revise le 9janvier 2004,
accepté le 30 mars 2004.
Boris ADAMCZEWSKI,
Université Lyon I, Bat. BraconnierInstitut G6rard Desargues, CNRS
21 avenue Claude Bernard69622 Villeurbanne Cedex (France).

Boris.Adamczewski@igd.univ-lyonl.fr