Continued fractions, coding and wireless channels

Corso di Perfezionamento in Matemati a

per la Te nologia e l'Industria

A. A. 2006/07

Continued fra tions,

oding and

wireless hannels

Candidata Relatore

Laura Luzzi Prof. Stefano Marmi

Correlatore

My rst thanks go to prof. Stefano Marmi, without whom this work would

notexist,forhis energeti supportandpositiveattitude duringalltheseyears.

Most of the results in the rst part of the thesis are based on his insights; I

amalsograteful to prof. Mar eloVianaforhis pre ioussuggestionsthat were

essentialfor ompletingoneoftheproofs.

I am indebted to prof. Emanuele Viterbofor patiently explaining to me the

basi s of oding for wireless hannels and for his insightful advi e, to prof.

Jean-ClaudeBelorefor en ouragingme to beginthestudy of thefas inating

topi ofnon- ommutativealgebra,andtoGhayaRekayaforlettingmeborrow

her odeforthesimulationoftheGoldenCodetransmission hainandforher

ompetentadvi eontheinterpretationofresults.

Iam gratefulto prof. DaPrato, prof. Fagnani andprof. Profetiand to Carlo

Carminatifora eptingtobeinthe ommittee,andtoprof. Nakadafor

referee-ingmyworkandforseveralinterestingdis ussionsaboutpossibledevelopments.

I alsowish to a knowledgethe nan ialsupport from S uola Normale

Superi-ore,whi hallowedmetospendlongvisitsatPolite ni odiTorinoandTele om

Paris.

Finally,thankstoRobforhis moraland mathemati alsupportandforalways

Introdu tion 3 I  - ontinued fra tions 7 Introdu tion. . . 9 1 - ontinued fra tions 11 1.1 -expansions . . . 11 1.2 Symboli dynami s . . . 18

1.3 ThePerron-Frobeniusoperator . . . 18

1.4 Invariantmeasures . . . 20

1.5 Entropy . . . 23

2 Statisti al stability for- ontinued fra tions 25 2.1 Continuityoftheentropy . . . 25

2.2 Numeri alresults . . . 41

3 Natural Extensions 47 3.1 Fibredsystems . . . 47

3.2 Naturalextensionsfor2[ p 2 1;1) . . . 50

3.3 Naturalextensionfor= 1 r . . . 57

II Coding for wireless hannels 71 Introdu tion. . . 73

4 Codingforwireless hannels 77 4.1 Thewireless hannelmodel . . . 77

4.2 Multipleantennasystems . . . 84

5 Spa e-time odes and ontinued fra tions 87 5.1 DiagonalSpa e-TimeCodes(DAST) . . . 87

5.2 Threaded-Algebrai Spa e-TimeCodes. . . 89

6 Algebrai spa e-time blo k oded modulation 95 6.1 QuaternionAlgebras . . . 95

6.2 Spa e-time odesfromquaternion algebras . . . 97

6.5 Codingwith osets: arstexample. . . 105

6.6 Stru tureofthequotientringsofG . . . 113

6.7 Therepetition ode. . . 121

6.8 GoldenReed-SolomonCodes . . . 122

Bibliography for Part I 133

Bibliography for Part II 135

Index for Part I 137

Mathemati ianshavebeenstudying ontinuedfra tionslongbeforethemodern

theoryofdynami alsystemsemerged. Tothisday,theyremainoneofthefew

modelsforwhi h a omprehensivestatisti alanalysisisavailable,in luding

er-godi ity,invariantmeasuresandthede ayof orrelationfun tions.

Therelevan eofthismodelisnotlimitedtotheeldofdynami alsystems,but

extendstonumbertheory,informationtheoryandthetheoryofalgorithms.

Asatoolforrepresentingrealnumbers, ontinuedfra tionexpansionsareideal

to study diophantine approximation problems, they are more e onomi al in

termsoflengththanthede imalexpansion,andaren'tbasis-dependent.

However, the major drawba k of being hardly suited for omputation (even

simpleoperations like thesum andprodu tbe ome omplexin this

represen-tation)isprobablythereasonwhytheliteraturedes ribingtheappli ationsof

ontinuedfra tionstoengineeringissosparse.

Re ently there has been an in reasing interest in des ribing the behavior of

families of dynami al systems at the boundary of haoti ity (a widely known

exampleistheextensivestudyonthebifur ationsofthelogisti map). Inthis

ontext interesting phenomena of phasetransitions, self-similarity and fra tal

setsoftenarise.

The rst part of my resear h on erns - ontinued fra tions for  2 [0;1℄, a

one-parameterfamilyofintervalmaps givingrisetoawhole lassof ontinued

fra tionexpansions. Justasthe lassi al ontinuedfra tions anbe viewedas

ana eleration of theEu lidean division algorithm, - ontinued fra tions are

obtainedimposing the onditionthat the remainderin the Eu lidean division

shouldbelongtotheinterval[ 1;).

Thisallowstogainawiderperspe tive,bridgingthegapbetweenGauss's

lassi- al ontinuedfra tionalgorithm(=1)andtheexpansionbasedonthenearest

integer approximation(=1=2),whi hhasafaster onvergen eand ahigher

entropy;andmoreinterestingly,betweenthelatterandtheby-ex ess algorithm

(=0),whosepropertiesaremarkedlydierent: itisslower,anddoesn'tadmit

aniteinvariantdensity, duetothepresen eofaparaboli xedpoint.

It is then natural to investigate how this transition o urs, in parti ular by

studying the statisti al stability of the family of the invariant densities as a

fun tion oftheparameter. Inx2.1weprovethat thisfamilyis infa t

onti-nuousin theL 1

norm.

om-ofthe orrespondingalgorithm 1

andto therateof information reationofthe

systemregardedasaninformationsour e[3℄[14℄.

Unfortunately, in thegeneral asethere existsnopurely me hani alalgorithm

forndingtheinvariantdensity;ageneralapproa h,introdu edbyRohlin[19℄

andknownastheNaturalExtensionmethod,involvesndingatwo-dimensional

transformationT ofwhi htheinitialmapT isafa tor,andasuitabledomain

where T is invertible. Thedensity of T is then derived from thedensity ofT

simplybyproje tingontherst oordinate.

Oneofmymainresultsistheexpressionofthenaturalextensionsforallvalues

oftheparameterinthesequen e 

1

n

. Theshapeofthedomainofthenatural

extensionsin this aseismu hmore omplexthanexpe ted,andthedensityis

givenbyalongre ursiveformula.

Moreover, theresult onL 1

- ontinuityof the densitiesenablesus to answerin

the aÆrmative to a onje ture of Cassa [6℄ stating that the entropy vanishes

when!0.

Our numeri al study of the entropy map also reveals a surprisingly ri h

self-similar stru ture, resembling adevil's stair ase, whi h is still unexplained. In

parti ular, ontrarilytoourexpe tationstheentropydoesn'tseemtobe

mono-toni inanyneighborhood oftheorigin 2

. Numeri aleviden ealsosuggeststhe

existen e of ountably many phase transitions or dis ontinuities of h 0

(), in

additiontotheknowndis ontinuitywhenisequaltotheGoldennumber.

These ond part ofthe thesiswasoriginally on eived in lose relationto the

rst,andstemmedfromthestudyofsomere entappli ationsof ontinued

fra -tionsto thedesignofspa e-time odesforwireless hannels.

Thewidediusionofwireless ommuni ationshasledtoagrowingdemandfor

anin reasein the apa ityand reliabilityof digitaltransmissionsystemsover

fading hannels.

Thepresen eoffadingee ts, thatisunpredi tableperturbationsand

attenua-tionsofthesignaldepending ontheenvironment, ausesa onsiderablelossin

the apa ityofthese hannels ompared tothe lassi alAdditiveWhite

Gaus-sianNoisemodel. Theuseof odingtogetherwithmultipletransmitandre eive

antennas angreatlyredu ethislosswithoutrequiringanyin reaseinthetotal

transmittedpower. Even though fading hinders transmission, its randomness

an be seen as an advantage, and its negative ee ts an be redu ed by

in- reasingthenumber ofindependent transmit-re eive pathsordiversity ofthe

system.

In a MIMO setting with M transmit antennas and N re eive antennas, an

information message u is en oded in an M T matrix or spa e-time blo k

B(u)=(b

ij

),whereb

ij

isthesignalemittedbyantennaiattimej 2f1;:::;Tg,

andT is thedurationofthesignal.

Themaximumrate oftransmissionthat anbea hievedusingspa e-timeblo ks

isofmin(M;N)symbolsper hanneluse; thediversityisequalto MR ,where

R istheminimumrankofthe matri esB(u), and oughtto bemaximized. In

the aseoffulldiversity,thedominanttermintheunionboundestimateforthe

errorprobabilityisthe oding gain
1 M ,where
=min u det(B(u)B(u) H ). 1

Morepre isely,for2(0;1℄theaveragelengthofthe ontinuedfra tionexpansionofa

rationalnumber p

q

ish()logq;when=0the omplexityisoftheorderoflog 2

q,see[23℄.

In[10℄ and[11℄, theproblem ofmaximizing the odinggainfora lass of

full-rankMIMO odes alled Threaded Algebrai Spa e-Time Codes or\TAST"is

shownto berelatedto thediophantineapproximationof omplexnumbersby

algebrai numbers. Someboundsfor the ode performan e arederivedfrom a

generalizationof Liouville's Theorem. Inparti ular, nding suitablealgebrai

numberswhi hhavetheworstorderofapproximationbyrationals,thatis,su h

thattheelementsintheir ontinuedfra tionexpansionsaresmall,isthekeyto

optimizingthe odedesign.

Thisrelationisnotassurprisingasitmightappearatarstglan e: in fa t,

\It is an interesting approa h to see the design of spa e-time

en- odingassear hingirrationalnumbersthe\furthest"fromrational

approximations. Ontheotherhand,thede odingpro essis

equiva-lenttosear hingrationalintegersthe losestto irrationalnumbers;

and both, en oding andde oding, anbeapproa hedby the same

algorithm(SphereDe oder)ofsear hingnonzeroshort ve torsina

givenlatti e."[10℄

Anotherappli ation, des ribedin [21℄,involvesdierential diagonal spa e-time

oding,adesigninwhi htheinformationbitsareen odedinthephase

differen- esbetweenonetransmittedsymbolandthenext. Inthe2-antenna ase, ode

optimization turns out to be equivalent to nding an integeru su h that the

ontinuedfra tionexpansionof u

L

hasthesmallestpossibleelements,whereLis

the ardinalityofthesignalset. Inparti ular,quotientsofFibona inumbers,

whi h approximate the Golden number and have ontinued fra tion elements

allequalto1,areagood hoi e.

BothTAST odesanddiagonalspa e-time odesa hievefulldiversity;however,

diagonal designs do not make full use of the antenna apa ity; in fa t, the

transmitantennasareonlyusedtoensuremaximumdiversity,whiletherateof

transmissionislow,onlyonesymbolper hanneluse.

TAST odes representan improvement overdiagonal odes, be ause theyare

full-rate; however,the majorshort omingof these odesis that theminimum

determinant vanishes as the size of the signal set or\ onstellation" grows to

innity.

Anewtypeofdesigns,basedonsuitablesubsetsofdivisionalgebras,solvesthis

problem: in fa t theminimum determinant, orrespondingto theminimumof

theredu ednormin amaximalorder,isstable.

Inthe22 ase,oneofthebests hemesknownuptodateisBelore,Rekaya

and Viterbo'sGolden Code G (2005), adesign based ona quaternion algebra

ontainingtheeldQ(i;), whereistheGoldennumber. This odeisfull-rate

andfull-rank, and its ubi shaping is onvenientforenergy eÆ ien y reasons

andmakesthede odingpro essfaster.

Itispossibletobuild longer,22Lblo k odesusingtheGoldenCodeasthe

base alphabet; in parti ular, the stru ture of its ideals and quotients an be

exploitedtoin reasetheminimumdeterminant,whi h anbewrittenasasum

involvingthedeterminantsof thesmallerblo ks, andmixed termsoftheform

e X i X j 2 F , where X ! e X is an involution, and kk F

is the Frobenius norm.

Thus the des riptionof thelatti e stru ture isnot suÆ ientto obtain agood

Inx6.5,we onsiderblo k odesbasedonthe osetsofaleftidealofGofindex

4. Inthissimple ase,theestimatesofthemixedtermsintheexpressionofthe

minimumdeterminant anbe arriedoutinfulldetail,atleastforshort odes.

When onsideringidealsofgreaterindex,however,theapproa hbasedondire t

omputation of the odeword weights be omes impra ti al. Using two-sided

idealsitispossibletoobtainglobalestimates,astheyareinvariantwithrespe t

to involution and multipli ation. Moreover, it is preferable to hoose ideals

whoseindex isapowerof two,sin ebinarypartition s hemesaresimplerand

bettersuitedto digitaldatastorage.

Inx6.6.2,wedes ribethestru tureofthetwo-sidedidealsofGwhoseindexisa

poweroftwoandoftherespe tivequotients,whi hturnouttobematrixrings

overF 2 n+uF 2 n,whereu 2

=0. Thisstru ture anbeexploiteddire tlytobuild

simplelifts ofrepetition odeson thequotient. The simulationresultsforthe

transmission hain using these odes show that theyperform betterthan the

un oded aseand onrmtheexpe tationsbasedontheestimatesofthemixed

terms.

Inx6.8,weintrodu esomedesignswhi himprovetheperforman eoftheGolden

Code in the slow-fading setting. When the hannel hanges so slowly that it

anbe onsidered onstantforlongtimelapses,theergodi ityassumptionmust

bedroppedandthediversityofthesystemisredu ed,leadingtoaperforman e

loss.

To ompensateforthisloss,we ombineamodulations hemeforthequotient

ring G=2G with an error- orre ting ode (a shortened Reed-Solomon ode) to

in reasetheminimum Hammingweightof the ode. Performan e simulations

showthatin the4-QAM ase, orrespondingto asinglesignalpointper oset,

these odesa hievearemarkablegainwithrespe ttotheun odedGoldenCode

at the same spe tral eÆ ien y, that is at the same bit-rate per hannel use.

These odes anbeextendedto the aseof16-QAMmodulationwithmultiple

points per oset, although the gain in this ase is somewhat smaller, being

Introdu tion

Let2[0;1℄. Wewill onsidertheone-parameterfamilyofmapsT

 :I  !I  , whereI  =[ 1;℄;denedby T  (x)=     1 x         1 x     +1   (1)

These dynami al systems generalize the Gauss map ( = 1) and the nearest

integer ontinued fra tion map ( = 1

2

); they were introdu ed by H. Nakada

[16℄. For all  2 (0;1℄ these maps are expanding, and even though in

gen-eral they aren't Markovian nor have nite range stru ture, it an be shown

that theyadmit aunique absolutely ontinuousinvariantprobabilitymeasure

d

 =

(x)dx(foradetailedproofinthisparti ular asesee forexample[3℄).

Nakada omputedtheinvariantdensities

 for

1

2

1byndinganexpli it

representationof theirnaturalextensions. The maps

turn outto be

pie e-wisenite sumsof linearfra tional fun tions. The ase p

2 1 1

2 was

laterstudied by Moussa, Cassaand Marmi[15℄ fora slightly dierentversion

ofthemaps, that isM

(x):[0;max(;1 )℄![0;max(;1 )℄ dened as

follows: M  (x)=     1 x  1 x +1      (2)

Noti ethatforagiven,M

 isafa torofT  : in fa tT  Æh=hÆM  ,where

h:x7!jxjistheabsolutevalue. Sin eallthe orrespondingresultsforthemaps

M

anbederivedthroughthissemi onjuga y,inthefollowingparagraphswe

willfo usonthemapsT

 .

Cassa found the invariant density for p

2 1    1

2

using an alternative

methodto thenaturalextension,whi hinvolves ountingthepoles ofa

mero-morphi fun tion[6℄;likethenaturalextension,thismethoddoesn'tprovidean

algorithmtondthedensity,butonlyameanstoverifythata ertain andidate

isvalid. Inx3.2,wein ludethenaturalextensionforthemapsT

forthis ase.

It an be shown [8℄ that the Kolmogorov-Sinai entropy with respe t to the

uniqueabsolutely ontinuousinvariantmeasure

 oftheT  isgivenbyRohlin's formula: h(T  )= Z   1 logjT 0  (x)j d  (x)

A tually, Rohlin's formula applies also to the M

 , and h(T  ) =h(M  ). For p

2 11,theentropy anbe omputedexpli itlyfromtheexpressionof

theinvariantdensities[16℄,[15℄:

h(T  )= (  2 6log (1+) forg<1  2 6logG for p 2 1g (3)

Inparti ular, theentropy is onstantwhen p

2 1g andits derivative

hasadis ontinuity(phase transition)in =g.

The ase =0requires a separatedis ussion; in fa t, due to thepresen e of

it is invariantwith respe t to the innitemeasure d 0 = dx 1+x . Thereforethe entropyofT 0

anonlybedenedinKrengel'ssense,thatisuptomultipli ation

bya onstant(seeThaler[22℄forastudyofthegeneralone-dimensional ase).

FollowingThaler,foranysubsetAof[0;1℄with0<

0

(A)<1we andene

h(T 0 ; 0 )+ 0 (A)h((T 0 ) A ) whereh((T 0 ) A

)isthe entropyofthe rstreturnmap ofT

0

onA withrespe t

to thenormalizedindu ed measure 

A =

0

0(A)

. This quantity iswell-dened

sin etheprodu th(T

0 ;

0

)doesn'tdependonthe hoi e ofA,andithasbeen

omputed exa tly: h(T 0 ; 0 ) =  2 3log2

[23℄. Sin e this is a nite value, for a

sequen e A

k

of subsets whose Lebesgue measure tends to 1 we would have

h((T 0 ) A k ) =  2 (3log2) 0 (A k )

! 0. In this restri ted sense we an say that \the

entropy of T

0

is 0". Expression (3) suggests the notion that the dynami al

systemsT

are somehowrelated and havea ommonorigin; a tually for 1

2 

gtheirnaturalextensionsareallisomorphi . Infa t,C.Kraaikampproved

thatforthese valuesofthenaturalextensions areinvertibleBernoullishifts,

and sohavingthe sameentropyis asuÆ ient onditionfor isomorphism[12℄.

Moreover, are entresult by R. Natsui [17℄ showsthat the naturalextensions

oftheFareymapsasso iatedtotheT

areallisomorphi when 1

2

1.

It is well-known that the maps T

1 and T

0

des end from the geodesi ow on

theunittangentbundleofthemodularsurfa ePSL(2;Z)nPSL(2;R)[21℄,[10℄.

Indeedwe anrepresentthis owasasuspension owoverthenaturalextension

ofthesemapsanddedu einthiswaytheinvariantprobabilitymeasuresfromthe

normalizedHaarmeasureonPSL(2;Z)nPSL(2;R). Itisnaturalto onje ture

that the same happens for allthe maps T

; 2 [0;1℄. If this were true, one

ould(atleastinprin iple)applyAbramov'sformulato omputetheentropies

h()fromtheentropyofthegeodesi ow.

Wenowsummarizebrie ythe ontentsofthevariousse tionsofPartI.

Inx1, weintrodu e- ontinuedfra tionexpansionsand theirbasi properties,

andremarkingthatfor2 

1

2 ;1

,thesequen eof- onvergen e anbeseenas

ana elerationofthesequen eofstandard(Gauss) onvergents. Wealsore all

howtheexa tness(andthereforeergodi ity)ofthesystemfollowsfromthefa t

thatthe ylindersetsgeneratetheBorel-algebra[16℄. Finally,weremarkhow

Rohlin'sformulafortheentropyholdsin this ase.

Inx2.1weprovethattheentropyh()ofT

is ontinuousin when2(0;1℄

andthath()!0as!0,asithadbeen onje turedbyCassa[6℄. Thisresult

followsfromthefa t thattheinvariantdensitiesarea ontinuousfamilyinthe

L 1

norm with respe t to , and is based on auniform versionof the

Lasota-YorkeinequalityforthePerron-FrobeniusoperatorofT

,followingM.Viana's

approa h[24℄;in theuniform ase,however,afurtherdiÆ ultyarisesfromthe

existen eof arbitrarily small ylinders ontainingthe endpoints, requiring ad

ho estimates.

Inx2.2weanalysetheresultsofnumeri alsimulationsfortheentropyobtained

throughBirkhosums,whi h suggestthat theentropyfun tionhasa omplex

self-similarstru ture.

Inx3.1,thenotionofnaturalextension isintrodu ed,followingS hweiger[20℄.

Finally,inx3.3we omputethenaturalextensionandtheinvariantdensitiesof

theT

forthesequen e  = 1 r .

 - ontinued fra tions

Inthis hapterweintrodu eafamilyofpie ewisemonotoni mapsoftheinterval

whi h generalize theGauss map, and giveriseto a lass of ontinued fra tion

approximations.

1.1  -expansions

For 2[0;1℄,letI

=[ 1;). Considerthemaps T

 :I  !I  dened as follows[16℄: T  (x)=     1 x         1 x       ; where[x℄ 

+[x+1 ℄. It is onvenienttoassumethatT

(0)=0.

Remark 1.1. When=1,T

is theGauss map; for= 1

2

, itisthe nearest

integer ontinuedfra tionmap.

–0.4

–0.2

0

0.2

0.4

–0.4

–0.2

0.2

0.4

–0.2

0

0.2

0.4

0.6

–0.2

0.2

0.4

0.6

analsobeobtainedbyinterse tingtheunionofthesequen e

of hyperbolae   1   n

–1

0

1

–1

1

Figure1.2: ThegraphofthemapTisobtainedbyinterse tingafamilyofhyperbolae

withthesquare[ 1; 1℄[;℄.

1.2). Bymoving thesquarealong thediagonal,weobtainthewhole familyof

- ontinuedfra tion maps.

Themaps T

are relatedto thefollowingsymboli dynami s: forxed, and

x6=0,let 8 > < > : a(x)=     1 x     +1   ; "(x)=sign(x);

anddenea(0)=1,"(0)=1.

Foranyx2I  ,letx 0 =x; x n =T n  (x), whenn1,and ( a n =a(x n 1 ); " n ="(x n 1 )

Thus we obtain indu tively a ontinued fra tion expansion asso iated to T

 : 8n1, x= " 1 a 1 + " 2 a 2 + " 3 . . . + " n a n +x n

Forthesakeofsimpli ity,wewilldenotethisexpressionby

Theresultingexpansionisinnite,oftheform[(" 1 ;a 1 );(" 2 ;a 2 );:::;(" n ;a n );:::℄

whenx is irrational; when x is rational,theexpansion isnite with lengthn,

wherenistheminimumindexsu hthat x

n =0.

Bytrun ating theexpansionto the n-th step,weobtainthe - onvergents of

x,that istheredu edfra tion

p n q n =[(" 1 ;a 1 );(" 2 ;a 2 );:::;(" n ;a n )℄= " 1 a 1 + " 2 . . . + " n a n ;

withthe onventionthat p

1 =1; q 1 =0; p 0 =0; q 0 =1.

Remark1.2. Weobserveon eandforallthatthesequen esfa

n g,f" n g,fx n g, fp n g,fq n

gareafun tion oftheparameterandthestartingpointx. Wewill

omitthisdependen e unlessne essary,inorder tosimplifynotation.

The following re ursive relations among the onvergents are easily proved by

indu tion: p n =a n p n 1 +" n p n 2 q n =a n q n 1 +" n q n 2 (1.1) Observethat p n+1 q n q n+1 p n = " n (p n q n 1 q n p n 1 )

andso,sin ep

0 q 1 q 1 q 0 = p 1 = " 1 , p n q n+1 p n+1 q n =" 1 " 2


" n ( 1) n 1 ; jp n q n+1 p n+1 q n j=1 (1.2)

Then,alwaysbyindu tion,wend

x= p n +x n p n 1 q n +x n q n 1 (1.3)

for n 0. In fa t,the basis of the indu tion is trivially p0+x0p 1 q 0 +x 0 q 1 = x 0 1 , and

supposing that the relation (1.3) holds for some n  0, using the re ursive

formulas(1.1)andtherelationx

n+1 = " n+1 xn a n+1 ,weget x= p n (1 " n+1 a n+1 x n )+" n+1 x n p n+1 q n (1 " n+1 a n+1 x n )+" n+1 x n q n+1 = p n x n+1 +p n+1 q n x n+1 +q n+1 Now onsider  n =jq n x p n j (1.4)

There are three usefulalternativeexpression for this quantity: rst, from the

relations(1.3)and(1.2),wend  n =     x n (q n p n 1 p n q n 1 ) q n +x n q n 1     = jx n j q n +x n q n 1 (1.5)

Fromequation(1.3),we anderive

x n =  p n xq n p xq  ;

sowehave  n =      n Y i=0 x i      (1.6)

Butequations(1.5)and(1.6)alsoimply

 n =  n+1 jx n+1 j = 1 q n+1 +x n+1 q n (1.7)

From(1:7),weobtainanestimateoftherateof onvergen eofthe p n q n to x: if x n 0, 1 q n (q n+1 +q n ) <     x p n q n     =  n q n = 1 q n (q n+1 +x n+1 q n ) < 1 q n q n+1 (1.8) whileforx n <0, 1 q n q n+1 <     x p n q n     < 1 q n (q n+1 (1 )q n ) < 1 q n q n+1 (1.9) When2  1 2 ;1

,the- onvergentsturnouttobeasubsequen eofthestandard

ontinuedfra tion onvergents[4℄. In thissense, - ontinued fra tions anbe

seenasan\a eleration"of1- ontinuedfra tions:

Lemma 1.3. Fix 2  1 2 ;1

. Let x 2 RnQ, and denote by P

n

Qn

the standard

ontinuedfra tion onvergents ofx,andby pn

q

n

its- onvergents. Then

p n q n = P k(n) Q k(n) ; wherek 

:N!N isdenedindu tivelyas follows:

k  ( 1)= 1; k  (n+1)= ( k  (n)+1 if " n+1 =1 k  (n)+2 if " n+1 = 1. Moreover, ifk  (n+1)=k  (n)+2wehave q k  (n+1) =q k (n) +2 =q k  (n)+1 +q k  (n) : When2 0; 1 2

,thislemmadoesn'tholdanylonger,andsequen esoftheform

n p n j q n j ;:::; p n j +k q n j +k o ,su hthat p n j +i q n j +i

isnotastandard onvergentfori=0;:::;k,

appear. These orrespond to sequen es of length k of digits \(2; 1)", alled

desingularizationsequen es.

Now suppose that we know the standard ontinued fra tion expansion x =

(w 1 ;w 2 ;w 3

;:::)ofanirrationalnumber,andwewanttoderiveits-expansion

x=[(" 1 ;a 1 );(" 2 ;a 2 );(" 3 ;a 3

);:::℄. Wedonotknowwhetherthere existsa

on- iseformulaexpressingthisrelation;however,itisnothardtodenea

step-by-stepalgorithmto passfrom oneexpansionto theother.

nota-Lemma1.4. Fix2  0; 1 2

,andletx2[ 1;)beanirrational numberwith

standard ontinuedfra tionexpansionx=w

0 +(w 1 ;w 2 ;:::), w 0 2f0; 1g. Let P n Q n

be the standard onvergentsof x, and pn

q

n

its- onvergents.

Then thereexisttwosubsequen esfn

j gandfn k gsu hthat p nj q nj = P nk Q nk

Morepre isely,wedene thefollowingalgorithm:

1.5(One step of-expansion). 1. First step:

 Ifx 2(0;), thendene " 1 =1andjx 0 j=x =(w 1 ;w 2 ;:::). Obvi-ously p 0 q0 = P0 Q0 =0.  Ifx2[ 1;0), dene " 1 = 1and jx 0 j= x. Wedistinguishtwo ases: - Ifw 1

=1,usingthewell-knownidentity

1 1 b+y = 1 1+ 1 b 1+y forb2and y2(0;1),wend x=(w 2 +1;w 3 ;:::). - Ifw 1

>1,fromtheidentity

1 1 n+ 1 b =((1;2);( 1;2);:::;( 1;2) | {z } n 1 ; 1 b+1 ); b1 we get a 1 = ::: = a w1 1 = 2," 2 = ::: = " w1 = 1, jx w1 1 j = (w 2 +1;w 3 ;:::); p i qi = i i+1 fori=1;:::;w 1 1,and p w 1 1 q w1 1 = w 1 w 1 +1 =1 1 w 1 = P 1 Q 1 2. Indu tive step:

Nowsupposethatwehavefoundtherstndigitsofthe-expansion,su h

that pn qn = P k Qk forsomek0: x= " 1 a 1 + " 2 a 2 + . . . + " n a n +" n+1 jx n j ; su hthat jx n j=(w (n) k +1 ;w k +2 ;w k +3 ;:::)2(0;1 ); w (n) k +1 2fw k +1 ;w k +1 +1g Then  IfT(jx n j )<,wehave " n+2 =1; a n+1 =w (n) k +1 ; p n+1 q = P k +1 Q ; jx n+1 j=(w k +2 ;w k +3 ;:::) (1.10)

 IfT(jx n j ), " n+2 = 1; a n+1 =w (n) k +1 +1; ifw k +2 =1 " n+2 =


=" n+w k +3 = 1; a n+1 =w (n) k +1 +1; a n+2 =


=a n+w k +2 =2 ifw k +2 2; p n+i q n+i = iP k +1 +P k iQ k +1 +Q k 81iw k +2 1; p n+w k +2 q n+w k +2 = P k +2 Q k +2 ;   x n+w k +2   =(w k +3 +1;w k +4 ;:::) (1.11)

Proof. Itis learthatequations(1.10)and(1.11)implytheexisten eofthetwo

identi alsequen es p n j q n j , Pn k Q n k

byindu tion, wherethe basisof theindu tion is

givenbytherststepinthealgorithm.

Wehavea n+1 = h   1 x n    +1  i ,andso a n+1 =w (n) k +1 ,w (n) k +1 + 1 w k +2 + 1 w k +3 +


+1 <w (n) k +1 +1,T(jx n j)<

Clearly in this ase "

n+2

= 1, and the remainder j x

n+1 j is equal to T(jx n j); otherwisewehavea n+1 =w (n) k +1 +1and" n+2 = 1.

Observethat sin ethe re ursive relationsdening the p

i

and the q

i

havethe

sameform,itissuÆ ientto provethestatementsaboveforthep

i .

WhenT(jx

n

j)<,wedistinguishtwo ases:

 If " n+1 = 1, by indu tive hypothesis pn 1 qn 1 = P k 1 Q k 1 , and w (n) k +1 = w k +1 . Then p n+1 =a n+1 p n +" n+1 p n 1 =w (n) k +1 P k +P k 1 =P k +1  If" n+1 = 1,w (n) k +1 =w k +1

+1,againbyindu tivehypothesis

P k 1 Q k 1 = p n w (n) k q n w (n) k ; p n 1 =p (n w (n) k )+(w (n) k 1) =(w (n) k 1)P k 1 +P k 2 =P k P k 1 ; )p n+1 =(w k +1 +1)P k P k +P k 1 =w k +1 P k +P k 1 =P k +1 WhenT(jx n j),     1 x n     =w (n) k +1 +1 0 B B  1 1 w k +2 + 1 w k +3 +


1 C C A = =a n+1  1 1 w +T 2 (j x j)  =a n+1 jx n+1 j

Thenifw k +2 2,wehave    1 xn+1   =1+ 1 wk +2 1+T 2 (jxnj) ,andsin e 1 1 w k +2 1+T 2 (x n ) > 1 w k +2 +T 2 (x n ) ; wend a n+2 =     1 x n+1     +1   =2; " n+3 = 1;

andsoon: itiseasyto provebyindu tionthat for1iw

k +2 1,     1 x n+i     =1+ 1 w k +2 i+T 2 (jx n j) 1+)a n+i+1 =2; " n+i+2 = 1; upto     1 x n+w k +2     =1+ 1 T 2 (jx n j) =1+w k +3 + 1 w k +4 +

whi histruealsowhenw

k +2 =1. In on lusion, jx n j=[(w (n) k +1 +1; );(2; )(2; );:::;(2; ) | {z } w k +2 1 ;   x n+wk +2   ℄ (1.12)

Againwedistinguishtwo ases:

 If"

n+1

=1,thenbyindu tivehypothesisw (n) k +1 =w k +1 ; pn 1 q n 1 = Pk 1 Q k 1 . p n+1 =a n+1 p n +" n+1 p n 1 =(w k +1 +1)P k +P k +1 =P k +1 +P k  If" n+1 = 1,thenw (n) k +1 =w k +1 +1, p n 1 =p (n w (n) k )+(w (n) k 1) =(w (n) k 1)P k 1 +P k 2 =P k P k 1 ; p n+1 =(w k +1 +2)P k +P k P k 1 =(w k +1 +1)P k +P k 1 =P k +1 +P k

Soin both aseswehavep

n+1 =P k +1 +P k ,and p n+2 =a n+2 p n +" n+2 p n =2(P k +1 +P k ) P k =2P k +1 +P k

Byindu tionwe anprovethat for1iw

k +2 1, p n+i =iP k +1 +P k ; upto p n+w k +2 =w k +2 P k +1 +P k =P k +2 ;

1.2 Symboli dynami s

1.6(Cylindersofrank1). Let2(0;1℄. ThemapT

ispie ewisemonotoni

andpie ewiseanalyti onthe ountablepartitionP =fI + j g jj min [fI j g jj 0 min , where j min =   1    +1   ,j 0 min = h   1 1     +1  i

andthe elementsof P are

alled ylindersof rank 1:

I + j +  1 j+ ; 1 j 1+  ; j2[j min +1;1); I + jmin +  1 j min + ;  ; I j +  1 j 1+ ; 1 j+  ; j2[j 0 min +1;1); I j 0 min +   1; 1 j 0 min +  T 

ismonotoneonea h ylinderandwehave

 T  (x)= 1 x j; x2I + j ; j2N\[j min ;1) T  (x)= 1 x j; x2I j ; j2N\[j 0 min ;1)

We also nd that for  2 (0;1), T

 is expanding, that is jT 0  (x)j > 1 almost everywhere 1

: infa t forallx2I

 , 1 jT 0  (x)j =(1 )<1 (1.13)

1.7(Cylinders ofrank n;full ylinders). LetP (n) = W n 1 i=0 T i  (P)bethe

indu edpartition inmonotoni ityintervalsofT n  . Ea h ylinderI (n)  2P (n) is

uniquelydeterminedbythesequen e

((j 0 ();" 0 ());:::;(j n 1 ();" n 1 ())

su h that for allx 2 I (n)  ; T i  (x) 2 I " i () j i () . On ea h ylinder T n  is aMobius mapT n  (x)= ax+b x+d , where  a b d 

2GL(2;Z). We willsaythat a ylinder

I (n)  2P isfull ifT n  (I (n)  )=I  .

1.3 The Perron-Frobenius operator

1.8 (Perron-Frobenius operator). LetV

 :T n  (I (n)  )!I (n)  bethe inverse bran hes of T n  , and P T 

the Perron-Frobenius operator asso iated with T

 .

Thenforevery'2L 1 (I  ), (P n T  ')(x)= X I (n)  2P n '(V  (x)) j(T n  ) 0 ( V  (x)) j  T n  (I (n)  ) (x) (1.14) OnI (n) 

wehavethefollowingbound:

sup I (n)  1   (T n  ) 0 (x)   =sup I (n)  1   T 0  T n 1  (x)



T 0  (x)    (n)   n ; (1.15) 1

Theonlyvalueofinwhi hjT 0

(x)j=1foranypointisa tuallytheGaussmapT1,with

where (n)  + j0()


 jn 1()

. Re allthat forf

1 ;:::;f n 2BV, Var(f 1


f n ) n X k =1 Var(f k ) Y i6=k supjf i j (i) and onsequently Var I (n)  1   ( T n  ) 0 (x)   =Var I (n)  1   T 0  T n 1  (x)



T 0  (T  (x))
T 0  (x)   n (n) 

Finally,westatethefollowingboundeddistortionproperty,thatwearegoingto

useseveraltimesin thesequel:

Proposition 1.9 (Bounded distortion). 8 > 0, 9C

1 su h that 8n  1, 8I (n)  2P (n) ;8x;y2I (n)  ,     (T n  ) 0 (y) (T n  ) 0 (x)     C 1

Moreover, for allmeasurableset BI

,for allfull ylinders I (n)  2P (n) , m(V  (B)) m(B)m(I (n)  ) C 1 ;

wheremdenotes the Lebesguemeasure.

Theproofofthis statementfollowsastandardargument:

Proof. Observethat9k>0su hthat8I " j 2P;8x;y2I " j ,     T 0  (x) T 0  (y) 1     kjT  (x) T  (y)j Infa t,ifx;y2I " j; ,then     T 0  (x) T 0  (y) 1     1 jT  (x) T  (y)j =     y 2 x 2 1     jxyj jx yj     y x    jx+yj4 Letn1; I (n)  2P (n) ,x;y2I (n)  . Dene=sup    1 T 0    =(1 ) 2 : then log     (T n  ) 0 (y) (T n  ) 0 (x)     = n 1 X i=0 log     T 0  (T i  (y)) T 0  (T i  (x)      n 1 X i=0     T 0  (T i  (y)) T 0  (T i  (x)) 1      4 n 1 X i=0   T i+1  (y) T i+1  (x)   =4 n X i=1   T i  (y) T i  (x)    4 n X  n i jT n  (y) T n  (x)j4 1 X  i = 4 1 (1 ) 2 =C 2 (1.16)

Then    (T n  ) 0 (y) (T n  ) 0 (x)    e C 2 =C 1 . LetI (n)  bea full ylinder: T n  (I (n)  )=I  . Now

onsideranymeasurableset B:

m(B) m(I  ) = R V  (B) j(T n  ) 0 (y)jdy R I (n)  j(T n  ) 0 (x)jdx  m(V  (B)) sup y2I (n)  j(T n  ) 0 (y)j m(I (n)  ) inf x2I (n)  j(T n  ) 0 (x)j C 1 m(V  (B)) m(I (n)  ) )m(V  (B))m(B) m(I (n)  ) C 1 (1.17)

whi h on ludes theproof.

1.4 Invariant measures

SuÆ ient onditionsfor the existen e of absolutely ontinuous invariant

mea-sures(a. .i.m.) forexpandingmapshavebeenextensivelystudiedin the

litera-ture. Adesirablepropertyinmost asesistheMarkov property:

1.10 (Markov map). Let I be an interval, P a ountable partition of I,

T : I ! I su h that the restri tion of T to ea h interval of the partition is

monotoni and C 2

. T is alled aMarkov map if theset I  + S n1 T n (P)is nite.

Infa t,afolklore theoremstatesthat

Theorem 1.11. If T : I ! I is Markov and expanding, then there exists a

uniqueinvariantprobability measurefor f absolutely ontinuouswithrespe tto

theLebesguemeasure.

Unfortunately,theMarkov onditionisnotsatisedbythemapsT

ex eptfor

asetof measure0in theparameter. Infa t

T  (P)=f[ 1;℄;[T  (1 );℄;[T  ();℄g Theunion S n1 T n 

(P)isnite onlyinthefollowing ases:

a) 9n;m 2 N su h that T n  () = 0;T m 

(1 ) = 0;whi h happens if and

onlyifisrational; b) thesequen esfT i  ()g i2N efT i  (1 )g i2N

areperiodi ,thatisis

alge-brai ofdegree2.

However,it anbeproved[3℄thatforall2(0;1℄themapsT

admitaunique

absolutely ontinuousinvariantprobabilitymeasure 

, whosedensity

 isof

bounded variation(and thereforebounded). The prooffollowsamoregeneral

framework,see thestudybyA. Broise[5℄:

Theorem 1.12 (Bourdon, Daireaux, Vallee). Consider an interval map

T :I !I whi h ismonotone andC 2

on ea h interval of a ountable partition

P of I. LetI (n)



denote the open ylindersof rank n,and V



the lo al inverse

ofT on I (n)

a) (Expansivity) sup j sup x2T(Ij)   V 0 j (x)   1 b) (Strongexpansivity) 9n 0

,9 <1su hthat sup

I (n 0 )  sup x2T n 0 (I (n 0 )  )   V 0  (x)   < ) 9 >0su hthat8I j 2P; 8x2T(I j ),   V 00 j (x)      V 0 j (x)   d) (Quasi-Markov) 8n, inf I (n)  2P n m  T n  I (n)  

>0, where m denotes the

Lebesguemeasure.

Then T admitsan invariantdensity ofboundedvariation.

Wehavealreadyseeninequation(1.13)thatthemapsT

areexpandingforall

2 [0;1℄,and stronglyexpanding for2(0;1℄(a tually, we antaken

0 =1

for2 (0;1), and n

0

=2for =1, see alsoequation (1.15)). Condition ( )

holdsforall,and anbe he keddire tly.

Condition(d)followstriviallyfromthefa tthatsin eT

(P)isnite (a tually

ithasatmostfourelements),T n

 (P

(n)

)isalsoniteforea hn,andthelengthof

itsintervalsmustbebounded frombelow. However,thereisnouniformbound

inornforthesemeasures,aswewillseeinthesequel.

We also remark that apriori the invariant density might be dis ontinuous in

everypointofthepartition S n T n  (P)[3℄.

Theuniquenessofthea. .i.m. isa onsequen eoftheergodi ityofthesystem:

1.13(Ergodi system). Ameasure-preservingdynami alsystem(X;A;T;)

isergodi ifforeverymeasurable set A2Asu hthat T 1

(A)=A, (A)=0

or1.

1.14 (Exa t endomorphism). A surje tive measure-preserving dynami al

system(X;A;T;)issaidtobeexa t if

1 \ n=0 T n (A)=fX;;g (mod 0) (1.18)

Inparti ular,everyinvariantsetistrivialand sothesystemisalsoergodi .

Foraproofofthefollowing lassi altheorem, seeforexample[7℄:

Theorem1.15. Consideradynami al system(X;T;A)andtwomeasures

1 ,



2

on(X;A) whi h areinvariant for T. If both (X;T;A;

1

)and(X;T;A;

2 )

areergodi , theneither

1 = 2 ,or 1 and 2

are singularwith respe ttoea h

other.

Be auseoftheprevioustheorem,ifT

isexa titadmitsatmostone invariant

densityabsolutely ontinuouswithrespe ttotheLebesguemeasure. Weremark

howeverthatthere is aninnitenumberof singularinvariantmeasures forT

( onsiderforexampleanylinear ombinationofDira deltasinthexedpoints

ofT

 ).

Lemma1.16 (Exa tness). For all2[0;1℄, the dynami al system(T

 ;

 )

TheproofofthisLemmafor2  1 2 ;1 

wasgivenbyH.Nakada([16℄,Theorem

2)andhisargument anbeadaptedtoour asewithslight hanges. 2 Let! i =(j i ;" i

)forbrevity. The ru ialpropertythatweneedinordertoprove

Lemma1.16isthefollowing:

Proposition 1.17. The familyof the ylinder sets I (n)  =(! 1 ;:::;! n )2P (n) su hthatT n  (I (n)  )=I 

generatesthe Borelsets.

Proof of Proposition 1.17. Considerthesets

E n =f(! 1 ;:::;! n )jT  (! 1 )6=I  ;T 2  (! 1 ;! 2 )6=I  ;:::;T n  (! 1 ;:::;! n )6=I  g and let M n = m  S I (n)  2En I (n)  

. Consider the orbits of the endpoints with

respe ttoT  : =(a 1 ;a 2 ;a 3 ;:::);  1=(b 1 ;b 2 ;b 3 ;:::) ThenE 1 =f(a 1 );(b 1 )g,and E n =f(! 1 ;:::;! n )2P (n) j(! 2 ;:::;! n )2E n 1 and! 1 =a 1 orb 1 g [f(a 1 ;a 2 ;:::;a n );(b 1 ;b 2 ;:::;b n )g Infa tif! 1 = 2fa 1 ;b 1 g,wewouldhaveT  (! 1 )=I  ;moreover,if(! 2 ;:::;! n )6= (a 2 ;:::;a n ), themonotoni ityof T  on(a 1

)impliesthat either (!

2 ;:::;! n )\ T  (a 1 ) = ?, or (! 2 ;:::;! n ) T  (a 1

). In this last ase T n  (a 1 ;! 2 ;:::;! n ) = T n 1  (! 2 ;:::;! n ). Soweget M n ((1 ) 2 + 2 )M n 1 +m((a 1 ;:::;a n )[(b 1 ;:::;b n )); and sin e(1 ) 2 + 2 < 1and m(w 1 ;:::;w n ) vanishesas n! 1, we have M n !0asn!1,thatis,E=fxj8n; T n  (I (n)  (x))6=I 

ghasLebesgue

mea-sure0,whereI (n)



(x)isthe ylinderinP (n)

ontainingx. Then,re allingthatT

isnon-singular,m(T n

(E))isalso0foralln0,andsom( S n T n  (E))=0.

Thatis,foralmostallxthereisasubsequen efn

i gsu hthatT ni (I ni  (x))=I 

foralli2N. Thenforalmost allx,8U openneighborhoodof xwe anndn

andafull ylinderx2I (n)

 U.

Proof of Lemma 1.16. Wehavejust provedthat thefull ylindersgenerate

theBorelsets. ThenasuÆ ientand ne essary onditionfor exa tness,due to

Rohlin [19℄, isthe following: 9C >0su h that 8n; 8I (n)



full ylinderof rank

n,8XI (n)  ,   (T n  (X))C   (X)   (I (n)  ) (1.19)

Were allthat theT

satisfythe boundeddistortion property: Then,re alling

that thedensityof 

withrespe tto theLebesgue measure isbounded from

aboveandfrombelowby onstants,wegetforsome onstantC,

  (V  (B)) 1 C   (B)  (I (n)  );

thatis,Rohlin's hara terization(1.19).

2

1.5 Entropy

Knowingthe invariantdensities allowsto omputethe entropy of the system.

Webrie yre alltherelevantdenitions:

1.18 (Entropy of a partition). Let (X;A;) be a probability spa e,  =

fX

1 ;:::;X

n

g anite measurable partition of X, that is X

i 2 A 8i2 N and X = F n i=1 X i (mod0). H()= P n i=1 (X i )+log(X i

) is alled the entropy

ofthepartition . 1.19. Given 1 ;:::; k partitionsofX,andX 1 2 1 ;:::;X k 2 k ,wedenoteby W k i=1  i thepartitionfX 1 \


\X k

g;givenT :X !X measurable,wedenote

byT 1 ()thepartitionfT 1 (X i );X i 2g.

1.20(Kolmogorov-Sinai entropy). Let(X;A;;T)beameasurable

dyna-mi alsystem,  aninvariant probability measure forT,  anite partition of

X. Thequantity H  (T)= lim n!1 1 n H n 1 _ i=0 T i  !

is alledtheentropy ofT with respe tto. H(T)=sup

 H



(T),wherethesup

istakenoverallnitepartitions ofX,is alledtheKolmogorov-Sinai entropy

ofT.

A dynami al system's entropy and information are deeply related, as an be

seenfrom thefollowing

Theorem1.21(Shannon,Breiman,M Millan). Let(X;A;;T)bea

mea-surable and ergodi dynami al system,  anite partition ofX. Given x2X,

let  n (x) be the element of W n 1 i=1 T i

 whi h ontains x. Then for -almost

everyx2X, H  (T)= lim n!1 1 n log( n (x))

Supposing the initial point x to be unknown to us, we may be interested in

thequantityofinformationprovidedtousbysomeinitialsegmentofthe

sym-boli dynami sofx. If =fX

1 ;


X

k

g,knowingtheset n

(x)isequivalentto

knowing(for -almost everyx) theindi es j

0 ;:::;j n 1 2f1;:::;kgsu h that T i (x)2X j i

. Intuitively, thesmaller( n

(x)) is,thebetterwehave\lo ated"

thepointxinourspa e,andthemoreinformationwehaveobtained. This

or-respondsto thesystemhavinghigh entropy. TheShannon-Breiman-M Millan

Theoremthenstatesthattheentropywithrespe ttoapartitionrepresentsthe

\averageinformationprodu tionrate"oftheinputobtainedwiththepartition

.

The- ontinuedfra tionmapsbelongtoa lassofintervaltransformationsfor

whi hanexpli itformulafortheentropyisavailable:

1.22(AFUmap). LetI beaninterval,T :I !I whi hispie ewiseC 2

with

respe tto a ountable partition P of I in subintervalsfI

j g

j1

, andsu h that

thefollowing onditionshold:

a) Adler's ondition: 9K>0; jT 00 (x)j 0 2 <K8x2I;

b) Finite range: #fT(I j ); j1g<1; ) Uniformexpansivity: 9: jT 0 (x)j>18x2I ThemapsT 

areAFU:wehaveseenthattheyareuniformlyexpandingin(2.1);

moreoverthey learlyhaveniterange,and j T 00  (x) j (T 0  (x)) 2 = 2 jxj 3 x 4 =2jxj<2.

Theorem1.23(Rohlin'sformula). LetI beaninterval,T :I !I anAFU

map,d=(x)dxthea. .i.m. for T. Then theKolmogorov-Sinai entropyofT

isgiven by h  (T)= Z I logjT 0 (x)jd(x)

For Rohlin's original proof we refer thereader to [19℄, while the proof in the

aseofAFU maps anbefoundin [8℄.

Remark1.24. Weremarkthatthealgorithmintrodu edintheproofofLemma

1.4toextra ttwoidenti alsubsequen es p n j q n j = P n k Q n k

fromthe1- onvergentsand

- onvergentsrespe tively ouldbeusedto omputetheentropyh()ofT

 . In

fa tBirkho'sergodi theoremimpliesthat

h()= lim n!1 1 n n X i=0 log   T i  (x)   = lim n!1 1 n log n 1 ; where n

istheprodu tdenedinequation(1.4). Theestimates(1.8)and(1.9)

implythat 1 (1+)q n < n 1 < 1 q n

Butsin elim

n!1 1 n log( q n )=lim n!1 1 n log(q n

)forevery onstant >0,

h()= lim n!1 1 n logq n

Inparti ular,evenwithoutknowingallthevaluesofthe- onvergents pn

qn ,the

entropyh() ouldbeapproximatedsimplywiththelimit 1 n k logQ n k ,requiring

Statisti al stability for

 - ontinued fra tions

Intheprevious hapterwehavedes ribedthedynami alpropertiesofthesystem

(I

 ;T

) for axed value of theparameter . We now wish to understand to

what extentthese propertiesremain stable whenvaries; in asense,wewish

tostudythebehaviorofthesystemunder deterministi perturbations.

Severalnotionsforthestabilityofadynami alsystemhavebeenintrodu ed. In

the aseofsmoothsystems,stru tural stability requires that theorbitsshould

bepreservedupto homeomorphism;however,this notionistoostrong forour

ase.

WewilladoptthepointofviewofAlvesandViana[2℄,andwewill allafamily

ofintervalmaps f(I;

t )g

t2R

statisti ally stable ifthe SRBmeasures 

t ofthe

maps

t

are ontinuousintwith respe ttotheL 1

norm.

Itmaybe onvenienttoassumethatthemapsf

t

garealldenedonthesame

interval;upto onjugation,atleastlo ally,themapsT

analwaysberes aled

toasuitablexedinterval.

2.1 Continuity of the entropy

WewilldenotetheentropyofT

byh(). Themaingoalofthepresentse tion

isthefollowing

Theorem2.1. Thefun tion !h()is ontinuousin (0;1℄,and

lim

!0 +

h()=0

Sin einthe ase p

2 1theentropyhasbeen omputedexa tlybyNakada

[16℄ and Marmi, Moussa, Cassa [15℄, we an restri t our study to the ase

0< p

2 1.

To prove ontinuityweadopt thefollowingapproa h: by means of auniform

Lasota-Yorke-typeinequalityforthePerron-Frobeniusoperator,weprovethat

the variations of the invariant densities are equibounded as varies in some

–0.8

–0.6

–0.4

–0.2

0.2

–0.8

–0.6

–0.4

–0.2

0.2

Figure 2.1: GraphofthemapT

when=0:2

arisingfrom thefa t that the ylinders ontainingthe endpoints and  1

anbe arbitrarily small. After translating the maps so that their interval of

denition does not depend on around  , we provethe L 1

- ontinuityof the

invariantdensities

usingHelly'sTheorem(Lemma2.5). Thenthe ontinuity

oftheentropyfollowsfromRohlin's formula.

2.1.1 Uniformly bounded variation of the invariant

densi-ties

Let2(0; p

2 1℄and "<bexed, and hoose2[ ";+"℄. Inthis

ase,re allingthedenitionsin x1.2,wehavej 0 min =2,andforx2I  j , 1 jT 0  (x)j  j <1; (2.1) where =(1 +") 2 ;  j = 1 (j 1+ ") 2 ; j>2;  2 = (2.2)

depend only on  and ". Moreover, we have that Var

I  j    1 T 0  (x)      j 8 2 [ ";+"℄.

Aswehaveseeninx1.4,forall2(0;1℄themapsT

admitauniqueabsolutely

ontinuous invariantprobability measure 

, whose density 

is of bounded

variation(andthereforebounded). Inaddition,aresultofR.Zweimullerentails

that

isboundedfrom below(see[25℄,Lemma 7):

82(0; p

Proposition2.2. 82(0; p

2 1℄,

 

isofboundedvariation,and9",9K>0

su hthatfor all2[ ";+"℄,Var(

 )<K.

Themain resultweneedin ordertoproveProposition2.2isthefollowing

Lemma 2.3 (Uniform version of the Lasota-Yorke inequality). Let 

be xed. Then there exist 

0 < 1, C ;K 0 > 0 su h that 8n, 8' 2 BV(I), 82[ ";+"℄, Var I  P n T  '
C( 0 ) n Var'+K 0 Z I j'jdx (2.4)

AssumingLemma 2.3 theProposition thenfollowseasily. Indeedit is enough

tore allthattheCesarosums

 n = 1 n n 1 X j=0 P j T  1 ofthesequen efP j T 1g j2N

onvergealmosteverywheretotheinvariantdensity



 of T

. Both the variations and the L 1 norms of the f n g are uniformly bounded: Var n  1 n n 1 X j=0 Var  P j T 1   1 n n 1 X j=0 K 0 m(I  )=K 0 8n Z I   n dx= 1 n n 1 X j=0 Z I  P j T 1dx=m(I   )=1 8n) sup I  j n jVar I  n + 1 m(I  ) K 0 +1 8n; whereK 0

isthe onstantwefoundinLemma2.3. ThenwealsohaveVar

  K 0 ; supj  jK 0

+1,whi h on ludes theproofofProposition2.2.

Proof of Lemma 2.3. Wehave

Var P n T '
 X  Var T n  (I (n)  ) '(V  (x)) j(T n  ) 0 ( V  (x))j +2 sup T n  (I (n)  )     '(V  (x)) (T n  ) 0 ( V  (x))     ! = = X  Var I (n)  '(y) j(T n  ) 0 (y)j +2sup I (n)      '( y) (T n  ) 0 (y)     ! (2.5)

For the last equality, observethat sin e V

 : T n  (I (n)  )! I (n)  is a homeomor-phism,Var T n  (I (n)  )  ' j(T n  ) 0 j ÆV   =Var I (n)  ' j(T n  ) 0 j

. Thersttermin expression

(2.5) an beestimatedusing(i):

X  Var I (n)  '(y) j(T n  ) 0 (y)j  X  Var I (n)  'sup I (n)  1 j(T n  ) 0 (y)j +Var I (n)  1 j(T n  ) 0 (y)j sup I (n)  j'j !   X   (n)  Var I (n)  '+n (n)  sup I (n) j'j !

For these ond term,we have2 P  sup I (n)     '(y) (T n  ) 0 (y)   2 P   (n)  sup I (n)  j'(y)j.

In on lusion,fromequation(2.5)weget

Var P n T '
(x) n Var I '+ X  (n+2) (n)  sup I (n)  j'j (2.6)

Wewanttogiveanestimateofthesuminequation(2.6);re allthatfor'2BV,

sup I (n)  j'jVar I (n)  '+ 1 m(I (n)  ) Z I (n)  j'jdx (ii)

However,equation(ii) doesn'tprovideaglobal bound independent from  for

tworeasons. Intherstpla e,thelengthsoftheintervalsI (n)



arenotbounded

from below when the indi es j

i

() grow to innity. Furthermore, a diÆ ulty

that arisesonlyin the aseofuniform ontinuityand that wasnotdealt with

inreferen e [24℄is thatthe measuresofthe ylindersofrankn ontainingthe

endpointsand 1arenot uniformlyboundedfrombelowin,andrequire

a arefulhandling.

Toover ometherstdiÆ ulty, following[24℄,wesplitthesumintotwoparts:

forn xed,letk besu h that

X j>k  j   n 2 2n 1 (2.7)

Sin edoesn't depend on, neitherdoesk. Dene theset of\intervalswith

bounded itineraries" G(n)=fI (n)  2P n j max(j 0 ();:::;j n 1 ())kg (2.8)

Togetridofthemeasuresofthe ylinders ontainingtheendpoints,we ombine

them with full ylinders; the measures of the latter an be estimated using

Lagrange'sTheorem,sin ethederivativesareboundedunderthehypothesisof

boundeditineraries. When ombiningintervals,wehaveto onsiderthesumof

the orresponding  (n)

v

and makesure that itis smallerthan 1. This requires

additional arewhenI (n)



3 1.

Remark2.4. Letr=r()besu hthat

v r+1 <v r ; where v r = 1 2 + 1 2 r 1+ 4 r (2.9)

( learlyrisboundedbyr( ) + 1inasmallneighborhoodof). ThenT i  ( 1)= (i+1) 1 1 i 2 I 2 for i = 0;:::;r 1 and T r  ( 1) 2= I 2

. Thus any

ylin-der with more than r onse utive digits \(2; )" is empty, and the ylinder

((2; );:::;(2; ))ofrankrmaybearbitrarilysmallwhenvaries. The

ylin-der(j

min

;+) anbearbitrarilysmalltoo.

Considerthefun tion  : G(n) !G(n) whi h maps everynonempty ylinder

I (n)  inI (n) 

inthefollowingway:

b. If9isu hthat ((j i ();" i ());:::;(j i+r ();" i+r ()))=((2; );(2; );:::;(2; )); then((j i ();" i ());:::;(j i+r ();" i+r ()))=((2; );:::;(2; );(3; )); . Otherwise,(j i ();" i ())=(j i ();" i ()).

Wewanttoshowthat thereexists Æ

n

>0,depending onlyon, su h thatfor

all2(G(n)), m()Æ

n

. Forthis purpose,wegrouptogetherthesequen es

of onse utivedigits(2; ),andobtainanewalphabetA=A

1 [A 2 ,where A 1 =f(3; );:::;(k; )g[f(j min +1;+);:::;(k;+)g A 2 =f(2; );((2; );(2; ));:::;((2; );:::;(2; )) | {z } r 1 g

Then ea h  2 (G(n)) an be seen as a sequen e in A 0 s = f(a 1 ;:::;a s ) 2 A s ja i 2A 2 )a i+1 2A 1 gforsomens n r . Let f T 

betherstreturnmap

onA 1 restri tedto(G(n)): e T(x)=T  (x) forx2(a)2A 1 ; e T(x)=T i  (x) if9i:x2((2; );:::;(2; )) | {z } i ;x2=((2; );:::;(2; )) | {z } i+1 Let e V a

betheinversebran hof e

T relativeto the ylinder(a). Observethat

8(a 1 ;:::;a s )2A 0s ; e T s (a 1 ;:::;a s )= e T(a s ) (2.10)

This anbeprovedbyindu tion ons: when s=1it istrivial;supposing that

theproperty(2.10)holdsforallsequen esoflengths,wehave

e T s+1 (a 1 ;:::;a s+1 )= e T s+1  (a 1 ;:::;a s )\ e V a1


e V as (a s+1 )  = = e T( e T s (a 1 ;:::;a s )\(a s+1 )) sin e e T s isinje tiveon(a 1 ;:::;a s );thisisequalto e T( e T(a s )\(a s+1 ))byindu tive hypothesis.  Ifa s+1 2A 2 ,wehavea s 2A 1 and e T(a s )=I: then e T s+1 (a 1 ;:::;a s+1 )= e T(a s+1 ).  Ifa s+1 2A 1 , e T(a s )(a s+1

). Infa tforalli=0;:::;r 1,

T i  ((2; );:::;(2; ) | {z } i )=T i  h  1;V i (2; ) ()   = =[T i  ( 1);)  1 2+ ;   [ a2A (a)  1 3 ;0  (2.11)

Equation (2.10) provides a lower bound on the measures of the intervals in (G(n)): 1 3 m( e T(a s ))=m( e T s (a 1 ;:::;a s ))m(a 1 ;:::;a s )sup   ( e T s ) 0    ; and M() +  max  (k++") 2 ;(2++") 2r()  sup    e T 0   

inaneighborhoodof . ThusforallI (n)  2(G(n)), Æ n + 1 3M() n m(I (n)  )

Returningtothesumin equation(2.6), anddening I (n)  = S fI (n)  j(I (n)  )= I (n)  g,wend: X I (n)  2G(n)  (n)  sup I (n)  j'j !  X I (n)  2(G(n)) sup I (n)  j'j 0 B  X (I (n)  )=I (n)   (n)  1 C A Wewant to estimate  0 = sup (G(n)) P (I (n)  )=I (n)   (n) 

: ea h sum anbe omputed

distributivelyasaprodu tof at mostn fa tors 0

i

, ea h of whi h orresponds

tooneofthe asesa),b), ) thatwehavelistedin thedenitionof:

 Inthe asea),wehave 0 i = jmin + jmin+1 2(+") 2 < 1 2 (remarkthat j min 3when p 2 1).  In the aseb),  0 i = r 2 + r 1 2  3 =(1 ) 2(r 1)  (1 ) 2 + 1 (2+) 2  < 0:9. In fa t, when  > 1 5 we have (1 ) 2 + 1 (2+) 2 < 9 10 ; otherwise, (1 ) 2 + 1 (2+) 2 < 5 4 ;andfor r+1 ,wehaver 1 1  2 + 2,and (1 ) 2(r 1) =  1  2 1+  2(r 1)  1 (1+) 2(r 1)  1 1+2(r 1)   1+ 3 3 4 2 < 3 5  Inthe ase ), 0 i = j i .

(The onstants in the previous dis ussion are far from optimal, but they are

suÆ ientforourpurposes.)

Then 0 max   n ; 9 10
n r ( )+1  = ~  n <1. Notethat ~

onlydependsonand

noton.

We annally ompleteourestimateforthesumoverI (n)  2G(n):  0 X I (n)  2(G(n)) sup I (n)  j'j ~  n X I (n)  2(G(n)) 0  Var I (n)  j'j+ 1 m(I (n)  ) Z I (n)  ' 1 A   ~  n 0 B Var'+ X I (n) 2(G(n)) 1 m(I (n)  ) Z I (n)  ' 1 C A  ~  n Var'+ ~  n Æ n k'k 1 (2.12)

Ontheotherhand,forthesumoverI (n)

 =

2G(n)wehavethefollowingestimate:

X I (n)  = 2G(n) (n+2) (n)  sup I (n)  j 'j !  sup I j'j X j>k n 1 X l=0 X j l ()=maxfj 0 ();:::;j n 1 ()g=j (n+2) j0()


 jn 1() (2.13)

whereinthethird sumofexpression(2.13)wetakeltobethesmallestinteger

thatrealizesthemaximum,toavoid ountingthesamesequen estwi e. Observe

thatwhenwetakethesumoverj

0

();:::;j

n 1

(),sin ewearenottakinginto

a ountthesigns"

i

(),wearea tually ountingatmost2 n distin tsequen es. X (j 0 ();:::;j n 1 ()) j l ()=j  j 0 ()


 j n 1 ()   j 0  2 X (j0();:::;jl 1();jl+1();:::;jn 1())  j0()


 jn 1() 1 A   j 0 B  2 n 1 Y i=0 i6=l j X ji=2 4 ji 1 C A  j 2 2n 1 sin e P 1 2  j   2 6 2. Therefore X I (n)  = 2G(n) (n+2) (n)  sup I (n)  j'j ! sup I j'j X j>k n 1 X l=0 (n+2) j 2 2n 1  sup I j'jn(n+2)2 2n 1 X j>k  j sup I j'jn(n+2) n

whereinthelastinequalitywehaveusedthehypothesis(2.7)onk.

In on lusion,Var I  (P n T ')isbounded by ~  n  (n 2 +3n+3)Var I '+(n+2)  1 Æ n +n  k'k 1 

andwere allthatwehave hosenÆ

n and

~

sothat theydonotdependon.

Chooseany 

2( ~

;1),andletK>0;N 2N besu hthat

8n1; (n 2 +3n+3) ~  n K   n and 8nN; K   n  1 2 LetL(n)=(n+2)  1 Æ n +n    n , ^ K= max 1nN

L(n). Foranyn, we anperform

theEu lidean divisionn=qN+rforsomeq0and0r<N. Then

Var I P N T '
K   N Var I '+ ^ Kk'k 1 (2.14)

Moregenerally,we anshowbyindu tiononqthat Var I   P qN T  '  (K N ) q Var I  '+C(q) ^ Kk'k 1 (2.15) whereC(q)=1+ 1 2 +


+ 1 2 q 1

<2forallq. Infa t if(2.15)istrueforsome

q,re allingthat thePerron-Frobeniusoperator P

T  preservestheL 1 norm,we get Var I   P (q+1)N T '  (K   N ) q Var I  P N T  '
+C(q) ^ K P N T  ' 1  (K   N ) q+1 Var I  '+  C(q)+ 1 2 q  ^ Kk'k 1 dx (K   N ) q+1 Var I '+C(q+1) ^ Kk'k 1 dx For0r<N,Var P r T  '
K   r Var'+ ^ Kk'k 1 . Ingeneral,forn=qN+r, weobtain Var I  P n T  '
(K   N ) q Var I  P r T  '
+C(q) ^ Kk'k 1  (K   N ) q K   r Var I  '+ ^ K (K   N ) q +C(q)
k'k 1  K 2 q   r Var I  '+3 ^ Kk'k 1 Nowtake 0 max  1 2 1 N ;    ,sothat   r 2 q ( 0 ) r ( 0 ) Nq =( 0 ) n . This on ludes

theproofof Lemma2.3.

2.1.2 L 1

ontinuity of the densities 

and ontinuity of

the entropy

Let 2(0; p

2 1℄bexed. Tostudy theL 1

- ontinuitypropertyof the

den-sities

(andthe ontinuityoftheentropyh())itis onvenientto workwith

measures supported on thesame interval. Thus weres alethe maps T

 with

inaneighborhoodof  totheinterval[ 1;℄ byapplying thetranslation

    . LetA ; =    ÆT  Æ 1   

bethenewmaps:

A ; (x)=     1 x +         1 x +     +1   +  (2.16) LetJ  j =I  j

+ bethetranslatedversionsoftheintervalsoftheoriginal

partition,and ~  (x) =Æ 1   

(x) =(x +) theinvariant densitiesfor

A

;

. Clearly thebounds forthesupand thevariationof

are stillvalidfor

~   . Lemma2.5. Let2(0; p

2 1℄bexed,andlet"begiven byProposition2.2.

Then iff

n

g[ ";+"℄ isamonotonesequen e onvergingto , wehave

~   n L 1 !~   .

Proof. Sin e supj~

n

jK,Var~

n

K 8n,we anapplythefollowing

theo-rem:

Theorem 2.6 (Helly's Theorem). Let f

n

1. supj n jK 1 8n, 2. Var n K 2 8n

Then there exists a subsequen e 

nk

and a fun tion  2 BV(I) su h that

 n k L 1 !, n k

!almost everywhere, and

supjjK

1

; VarK

2

Thus we anndasubsequen ef~

n

k

g onvergingintheL 1

normandalmost

everywhere to some fun tion 

1

su h that supj

1

j  K, Var

1

 K. We

wantto showthat

1 =~

 

: weobservethatitissuÆ ienttoshowthat 

1 is

aninvariant density forA

  =A   ; =T  

, and then usethe uniqueness ofthe

invariantdensity. Tosimplify notations,wewill write

k for nk ,~ k for~ n k , andA k forA n k ; .

Ourgoal is to show that 8B  I

  , R  B (A   (x)) 1 (x)dx = R  B (x) 1 (x)dx.

Observethatevery

B (x)belongstoL 1 (I  

)and so anbeapproximated

arbi-trarilywellby ompa tlysupportedC 1

fun tionswithrespe ttotheL 1

norm.

ThenitwillbesuÆ ienttoprovethat8'2C 1

with ompa tsupport ontained

inI   ,     Z '( A   (x)) 1 (x)dx Z '(x) 1 (x)dx     =0 (2.17) Observethat   R '(A   (x)) 1 (x)dx R '(x) 1 (x)dx   I 1 +I 2 +I 3 ,withI 1 ,I 2 ,I 3 givenbelow: I 1 =     Z '(A   (x)) 1 (x)dx Z '(A   (x))~ k (x)dx     k'k 1 k~ k  1 k L 1 I 3 =     Z '(A k (x))~ k (x)dx Z '(x) 1 (x)dx     = =     Z '(x)~ k (x)dx Z '(x) 1 (x)dx     k'k 1 k~ k  1 k L 1

whi h vanish as k ! 1. Finally, I

2 = R j'(A   (x)) '(A k (x))j~ k (x)dx is bounded byK R j'(A k (x)) '(A  

(x))jdx,andweneedtoshowthat

Z j'(A k (x)) '(A   (x))jdx!0whenk!1 (2.18)

Re all that for x 2 J

j; k = h 1 j 1+ k +  k ; 1 j+ k +  k  , A k (x) = 1 x + k j+  k ,andforx2J j; = h 1 j 1+ ; 1 j+  ,A   (x)= 1 x j.

Wewill examinein detailthe ase

k

<8k,x< 

k

;theother ases an

be dealtwith in asimilar way. Inthis ase,0< 1 j+ k 1 j+ <  k , and if j< 1 p    k =N(k),then 1 j 1+k + 1 j+ <  k   1 j 2 < k  andso 1 j 1+ k +  k < 1 j+ < 1 j+ k +  k (2.19) I N(k ) = S jN(k ) J j; k

ontainstheset inwhi h ondition(2.19)isn't satised,

and itsmeasure m(I

N(k ) )= P 1 j=N(k )    1 (j 1+k)(j+k)    vanisheswhen k !1.

Given" 00

>0, hoose 

k su hthat m(I

N(  k) )<" 00 ,andletk  k. Dene  j =  1 j 1+ k +  k ; 1 j+  ;  j =  1 j+ ; 1 j+ k +  k  when2<jN(  k); and  2 =    1; 1 2+ k 

Thenwe ansplittheintegral(2.18)inthreeparts inthefollowingway:

Z     1 j'(A k (x)) '(A   (x))jdx Z I N(  k) j'(A k (x)) '(A   (x))jdx+ + N(  k ) X j=3 Z  j j'(A k (x)) '(A   (x))jdx ! + N(  k ) X j=2 Z  j j'(A k (x)) '(A   (x))jdx !

The rst integral in this expression is bounded by 2" 00

k'k

1

. Moreover, the

measuresofthesets

j

tenduniformlyto0whenk!1:

m( j )j  k j+ j  k j (j+)(j + k ) C 1 (  k ) ) N(  k) X j=3 Z  j j'(A k (x)) '(A   (x))jdxN(  k)2k'k 1 C 1 (  k ) Finally, m( j ) C2 j 2 +j  k j C3 j 2 when k  k; j <N(  k), andforx 2 j , x 1 j+ andx + k < 1 j+ k ,therefore jA k (x) A   (x)j=     1 x + 1 x + k  + k      j  k j+ j  k j jx(x + k )j j  k j(1+(j+1) 2 ) (2.20) Sin e 'is C 1

on a ompa t interval, it is also lips hitzian for someLips hitz

onstantL ' ,and N(  k ) X j=2 Z  j j'(A k (x)) '(A   (x))jdx N(  k ) X j=2 m( j )L ' jA k (x) A   (x)j  N(  k ) X j=2 C 3 (1+(j+1) 2 ) j 2 L ' j  k jC 4 N(  k)j  k jC 4 p j  k j

whenkislarge. Thisestablishesthe laimthatthethirdintegralvanisheswhen

x< 

k

. Inthe asex> 

k

wehavesimilarestimates: forj< 1 p j  k j , wehave 1 j+ < 1 j+ k +  k < 1 j 1+

andwe andenetheintervals

+ j =  1 j+ +  k ; 1 j 1+  ; Æ + j =  1 j 1+ ; 1 j 1+ +  k 

Wehavem(Æ + j )C 5 j  k j, m( + j ) C 5 j 2 ,and jA k (x) A   (x)jC 7 j 2 j k  j forx2 + j

Finally, weleaveitto thereaderto he kthatthe ase<

k

anbetreated

insameway. Thuswe an on ludethat (2.18)holds.

Therefore we have shown that 

1 = ~

 

. This is also true if we extra t a

onverging sub-subsequen e from any subsequen e of ~

 n , and so ~  n ! ~   both in L 1

and almost everywhere for n ! 1. This ompletes the proof of

Lemma2.5.

The L 1

- ontinuity of the map 7! 

is suÆ ient to provethat the entropy

map 7!h() is also ontinuous. This is a hievedby applying thefollowing

lemma(foraproofseeforexample[1℄)toRohlin's formula.

Lemma2.7. Letf n gbeasequen eoffun tionsin L 1 (I)su hthat 1. k n k 1 K 8n, 2.  n L 1 !for some2L 1 (I)

Then forany 2L 1 (I), Z ( n )!0

ApplyingRohlin's Formulafortheentropy,wegetforany2[ ";+"℄

h()= Z   1 log 1 (x +) 2 ~   (x)dx=2 Z   1 jlogjx +jj~  (x)dx Considerasequen ef n g!. Then jh( ) h( n )j2 Z     1   logjx + n j~ n (x) logjxj~   (x)   dx 2 Z     1   logjx + n j(~ n (x) ~   (x))   dx+ + Z     1   ( logjx + n j logjxj )~   (x)   dx 

These ondintegralisboundedby2(K

0 +1) R     1 jlogjx + n j logjxj jdx

andvanisheswhenn!1be auseofthe ontinuityoftranslationin L 1 . Ifwe take~ n = ~  n , ~=~  

, (x) = j logjxjj in Lemma 2.7, we nd that therst

integralalsotendsto0.

2.1.3 Behavior of the density and entropy when  !0

Inthis se tionwewill provethat theentropyhasa limitas!0 +

and that

lim

!0

+h()=0.

The ontinuity of the entropy on the interval (0; p

2 1℄ followed from the

L 1

- ontinuity of the densities. The vanishing of the entropy as  ! 0 is a

onsequen eof the fa t that the densities onvergeto the Dira delta at the

Proposition 2.8. When ! 0, the invariant measures ~

of the translated

mapsA

;0

:[ 1;0℄![ 1;0℄ onvergeinthesense ofdistributionstotheDira

deltain 1.

FromthepreviousPropositionthevanishingoftheentropyfollowseasily:

Corollary 2.9. Let h() be the metri entropy of the map T

with respe t to

the absolutely ontinuousinvariant probability measure 

. Then h()!0as

!0.

Proof of the Corollary. We omputetheentropyoftheT

 throughRohlin's formula: h()=2 Z   1 jlogjxj jd  (2.21) Observethat8E( 1 ;0℄,  (E)= 1 C()   (E) C0 C() m(E). Thereforeif  is thedensityof  ,  < C0 C() in ( 1 ;0℄. Given", let k

besu h that jlogjxj j<

" for x 2 [ 1;

k

℄, and hoose  small su h that  1 <

k ,   ([ k ;℄) = ~   ([~ k ;0℄)<"and C 0 C() <". Then h() Z k  1 jlogjxj jd  + Z 1 k jlogjxjjd  + Z  1 j logjxjj  dx jlogj k jj+     log 1 3       ([ k ; 1 ℄)+ C 0 C() klogj xjk 1 !0

whi h on ludes theproof.

ToproveProposition2.8weadoptthefollowingstrategy: weintrodu ethejump

transformationsG

of themapsT

overthe ylinder(2; ),whose derivatives

arestri tlyboundedawayfrom1evenwhen!0;we anthenprovethattheir

densities d

dx

are bounded from above and from below by uniform onstants.

Usingthe relationbetween 

and theindu edmeasure 

, we on ludethat

for any measurable set B su h that 1 2= B, ~

(B) = 

(B+) ! 0when

!0.

Proof of Proposition 2.8. Given v

r+1   < v r as in equation (2.9), and 0jr,let L 0 =I  n(2; ); L j =[ j+1 ; j )=((2; );:::;(2; ) | {z } j )n((2; );:::;(2; ) | {z } j+1 ) for1jr. Thus I  = S 0jr L j

(mod 0). It iseasytoprovebyindu tion

that forrj 1; j =V j 1 (2; )  1 2+  = 1+ 1 j+ 1 1+ , that is, j j+1 < j  j 1 j ,while 0 =; r+1 = 1. Let G  j Lj =T j+1  j Lj

be the jump transformation asso iatedto the returntime (x) =j+1 ()

ThenaresultofR.Zweimuller([26℄, Theorem1.1)guaranteesthat G  admits aninvariantmeasure   

su hthatforallmeasurableE,

  (E)= 1 C() 0  X n0   f >ng\T n  (E)
1 A (2.22)

whereC()isasuitablenormalization onstant. A tuallyfromequation(2.22)

itfollowsthat  (I  )=  (f >0g)C()  (I 

)isnite,andsoby hoosing

asuitableC()we antake

 (I

)=1. Wewillprovethefollowing:

Lemma2.10. Thereexists ~>0su hthatfor0<<,~ thedensities

 of



are bounded from aboveand from below by onstantsthat do notdepend

on: 9C 0 s.t. C 1 0   C 0 .

Proof of Lemma 2.10. Inordertoprovethat

isboundedfromabove,we

an pro eed as in Lemma 2.3, and show that 9C 0

su h that for all , 8' 2

L 1 (I  ),Var I P n G '<C 0

. Sin etheoutlineoftheproofis verysimilar tothat

ofLemma 2.3, wewill onlylistthepassages wherethe estimatesaredierent,

andemphasizehowin this aseallthe onstants anbe hosenuniformin.

The ylindersofrank1forG

areoftheform

I k ;" j =(j;k;")+((2; );:::;(2; ) | {z } j ;(k;")); 0jr;

sotheyarealso ylindersforT

,although ofdierentrank. OnI k ;" j ; j 1we have     1 G 0  (x)     =(T j  (x)


T  (x)x) 2  k j = 4 (j+2) 2 (k 1) 2  1 (k 1) 2  1 4 ;     1 G 0  (x)      1 9j 2 (k+1) 2 ; whileonI k ;" 0 ,    1 G 0  (x)   =x 2 < 1 (k 1) 2  1 4 ,andso=sup    1 G 0    < 1 4 forall. LettingQ= S r j=0 fI k ;" j g,and (n)  =sup I (n)     1 (G n  ) 0  

,we anobtaintheanalogue

ofequation(2.6)forthemapsG

 : Var P n G  '
(x) n Var I  '+ X I (n)  2Q (n) (n+2) (n)  sup I (n)  j'j;

andsimilarlyto(2.7),we an hoosehsu hthat P ih 1 i 2   n 2 4n 2

,andtheset

ofintervalswithbounded itineraries

G(n)=fI (n)  =((j 0 ;k 0 ;" 0 );:::;(j n 1 ;k n 1 ;" n 1 ))2Q n j max(j 0 ;:::;j n 1 )h; max(k 0 ;:::;k n 1 )hg

Againwe andeneafun tion:G(n)!G(n)thatmapsevery ylinderI (n)  = ((j 0 ;k 0 ;" 0 );:::;(j n 1 ;k n 1 ;" n 1 ))toI (n)  =((j 0 0 ;k 0 0 ;" 0 0 );:::;(j 0 n 1 ;k 0 n 1 ;" 0 n 1 ))

a. If(j i ;k i ;" i )=(j;j min

;+); j<r 1forsomei,then(j 0 i ;k 0 i ;" 0 i )=(j;j min + 1;+); b. If for somei, (j i ;k i ;" i ) = (r;k;") with (k;") 6= (j min ;+);(j min +1;+), then(j 0 i ;k 0 i ;" 0 i )=(r 1;k;"); . If(j i ;k i ;" i )2f(r;j min ;+);(r;j min +1;+);(r 1;j min ;+)g,then (j 0 i ;k 0 i ;" 0 i )=(r 1;j min +1;+); d. Otherwise,(j 0 i ;k 0 i ;" 0 i )=(j i ;k i ;" i ).

With this denition, the ylindersin (G(n)) areall full, be ause aswe have

seeninequation (2.11),for0ir 1,

T i  ((2; );:::;(2; ) | {z } i )  1 2+ ;   [ (k ;");k 3 I " k Then8I (n)  2(G(n)), 1m(I (n)  ) sup (G(n)) j(G n  ) 0 j=m(I (n)  )(9h 4 ) n )m(I (n)  ) 1 Æ n = 1 (9h 4 ) n ;

whi h doesn't depend on . Again we need to estimate the supremum over

I (n)  2 (G(n))of thesums P (I (n)  )=I (n)   (n) 

, ea h ofwhi h isthe produ t ofn

terms 0

i

,that orrespondtooneofthe asesa),b), )d)welistedpreviously:

 Inthe asea),  0 i = j min j + j min +1 j  1 (jmin 1) 2 + 1 j 2 min  1 2 (observethat for< p 2 1,j min 3).  In the ase b),  0 i =  k r + k r 1  4 (k 1) 2  1 (r+1) 2 + 1 (r+2) 2   1 2 when <v 2 ;  Inthe ase ), 0 i = jmin r + jmin r 1 + jmin+1 r + jmin+1 r 1 <4  1 (j min 1) 2 + 1 j 2 min  1 (r+1) 2 + 1 (r+2) 2  < 1 2 for<v 2 ;  Inthe ased), 0 i <= 1 4 . Then 0  ~ = 1 2

,andasin equation(2.12),wendfor<v

2 , X I (n)  2G(n)  (n)  sup I (n)  j'j !  0 X I (n)  2(G(n)) sup I (n)  j'j ~  n Var'+ ~  n Æ n k'k 1

Forthesum overintervalswithunbounded itineraries wepro eed in asimilar

wayto(2.13): X I (n)  = 2G(n)  (n)   X ih n 1 X l=0 0 B B  X j l ()=i+1= max(j 0 ();:::;j n 1 ())  k0() j0()


 kn 1() jn 1() + + X kl()=i= max(k0();:::;kn 1())  k 0 () j 0 ()


 k n 1 () j n 1 () 1 C C A  X ih n 1 X l=0 4 i 2 0 B 2 X I k ;" j 2Q  (n)  1 C A n 1