VOL.
II
NO. 4(1988)
643-650A NOTE ON EQUIVALENT INTERVAL COVERING SYSTEMS FOR HAUSDORFF DIMENSION ON R
C.D. CUTLER
Department
of Statistics and Actuarial Science Universityof WaterlooWaterloo,Ontario Canada N2L 3G1
(Received September 30,
1987)
ABSTRACT. The Hausdorff dimension ofasetin R isusuallydefined by consideringcountablecoveringsof thesetby generalintervals.
In
thisnote weestablish sufficient conditions under whichcoveringswhose members arerestrictedto aparticularfamily g ofintervalswillproducethesamevalue fordimension. Aresult of Bil- lingsleyisthen employedtoobtaina general techniqueforcomputingthe dimensions ofsetsdefinedbycertain types ofgeneralized expansions.A
specificexampleis included.KEY
WORDSAND
PHRASES. Hausdorffdimension,Vitalicovering,self-similar.1980AMS
SUBJECT
CLASSIICATION. 28A75,28A12.1. INTRODUCrION.
Let s_>0.
The s-outerHausdorff measure ofa set E C_ R isusuallydefinedbyH"(E
lim inf d(lj)o
d(tj)_<
where
lj
is an interval in R and d(lj)
denotes the diameter of lj.It
iseasy tosee that the value of H(E
isunchangedwhenthecoveringsof E are restrictedtolacingclosedintervals.(It
will be convenient for us to consideronlyclosed intervals in Section2.) It
iswell known that there existsaunique point s0 such thatH(E )=
fors<s
andH(E )=
0 fors>s
0. Thisvalue s iscalled the Hausdorffdimension of
E (denoted
bydim(E )).
In
actually computingthe dimension ofa set it isrcquently useful tobeabletoconsideronly coverings fromarestrictedfamilyofintervals.In [1]
Besicovitch established thatcoveringsby dyadicintervals(i.e.
inter- vals of the form [j 2 (j+ 1)2 ))
producethe samedimension forsets. Billingsley[2]
extended this resultto r-adic intervalswhere r_>2 issomepositive integer.However
in[3]
Billingsleyremarked that he knew ofnogeneralconditions on interval families which wouldguarantee preservationof thecorrectdimensionvaluefor all sets.
We
address thisproblemin Section2.2.
COVERING RESULTS.
Let
F C_ R be a closed interval.A
collection g of intervals is a Vitalicoveting of F if for each e>0 and each xeF there exists ! eg suchthat x d and d(I)<e.
If an interval collection g is aVitali covetingof F then, for each E C_ F,we candefineHs"(E
and dim(E)
byand dim
(E)
sup{aHs’(E
oo inf{a[Hs(E 0}
where usual Hausdorff dimensiondim(E
results when g istakentobe the collection of all closed intervals.We
automaticallyhavedim(E )<dim
s(E)
for any Vitali coveting g sotodemonstrate equalityweneed only show dim
(E)<dim(E ). A
property of dimension which will be useful in this is the result dim(UEt)= sup
dims(EL)
for any countable collection{EL
We
willcall g a bounded Vitalicoveting of F if, for each xeF,there existsasequence
of intervals from g(which
wewilldenoteby {lj(x)}j
such that(i)
xdj(x)
for each j(ii) d(l(x))0
d
(t +(x ))
b
(x)>o.
(iii) i
d(I (x))
We
willsaythat aboundedVitali coveringof F is open if, for each xeF,
thesequence {lj (x)}j
can be chosensothat xd(x
for each j(where lj(x
denotes the interior ofI (x)).
Theorem 2.1 deals withopenbounded Vitalicoverings.
THEOREM 2.1.
Let
g be an open bounded Vitali coveting of a closed interval F C_R. Then dims(E) dim(E
forall E C_F.PROOF.
Let
E CF. ThenwecanwriteE=U uEi,
=2 =1
where E,m {x
eEI
inf dd(I (I +l(x )) (x)) >_ 1/i
and d(I t(x )) >_ 1/m
}. To provethe theorem it issufficientto showdims(Ei _< dim(Ei).
LetO<6<l/m
bearbitraryandsuppose {Ft}t isacountable coveting ofEi
byclosed intervals with d(Ft)--<6
for each k. Without loss ofgeneralitywe canassumeFk
CF andFt flEi ,
#6. For
each k we will show that there exist four intervals from g whichcoverFt t’lE ,
andwhose diameters do not exceed
d(Ft). For
every xeFtflEi,at
there existsl(t)(x
such thatd
(lj
(k)(x ))>d (Ft)>d (lj(t)+t(x)).
WritingFt [at ,bt
then we must have[at
,x]_C/j(t)(x
orIx
,bt]_C/j()(x ).
Without loss ofgeneralitywewill assume there exists at least one xeFt
t’lE,.at forwhich[a
,x]_C./()(x
since theargumentisanalogous when beginningwith the assumption[x
,bt]_C/ ()(x). Let
Xo sup{x
eft f’lEi,at [at
,x]_C./j (t)(x)}. Now
xoFt _CF
and so there exists k’ such thatd(lt,(Xo))<_i d(F). Let
x6-_<Xo be some point in FtClEi,
such that[a t.xo-]_C/(t)(x0-)
andI ()(x
6- )lql,(x o)
#6.
Thisispossiblefrom the definition of x and theassumption xodt (x o).
If x>x
implies xFt
f3E,: thenI (t)(x 0- )ult ,(x0)
coversFi NE,
,at. If however there exists x>x
such thatxF tqE, then it follows that
[x
,btICIj (t)(x
and wedefine x inf{xFt NEi
x,btICIj (t)(x )).
We
can then find x+ _>x
with x+Ft NE,
and k" such that[x +
,bt]_CIj (t)(x + ),
d
(It ,,(x 1))_<i
d(Ft)
andIj (t)(x
+)rqlt,,(x 1)
#-
Thenrt
fqei,,. c_
lj(t)(x
6-)ult ,(x 0)ult ,,(x 1)UI (t)(x + ). Now
d
(b ()(x o- ))
d(6 ()( o- ))
d(, ()(x: ))
d
(F --<
d(lj( t)+l(x0- )) <-
andsimilarly d(F _<
i. Thus we obtain[d (I(t)(x0- ))0 +
d(lt ,(x0)) +
d(It,,(x 1)) +
d(I(t)(x + ))] _<
4io
d(F )0.
--1 =1
Hence
weconcludeinI d
(I)o <
4i inf’
d(F)0.
, !
_e,g _1F e,
d teal, -
d(t) d(F
ng
0+ weobtainHs(Ei
4iH (E, , ). s
sho dim(Ei dim(E, ,
asrequireddcomplettheprfof the theorem.
moregeneral u is the follongtheorem in wch the
n ruirement
isreled.We
11 1aund Vitalicovetingof F completeif for each xF the
uence {I (x)}
n chensothat when-ever x isan
endint
ofly (x) (if
atall)
thereests
Ig th d(I)d (I (x))
and >0 such that(i) (x-
1 if x isthelefthandendint
of1 (x) (t n
the le ndendint
of F(ii) (x +)
I ifx isthefit
dendnt
of1i (x) (but
notthefighthandendint
of F).
O2.2.
t
F acl inte of R and g ampleteund Vitalicovetingof F.en
dim
s(E)=dim(E)
forl EF.
PROF. e f
foHott
ofcorem
2.1 until diuion of x isrch.d
endint
ofI ,(x 0)
thennomfifion isrr. However
if x isc
lefthdendint
ofI ,(x0)
we
n
to add in the inteal I profided by(i)
in the deflation ofa complete coveting.We
then scltx that
ly ()(x )I . e ao
mififionmust done in theseof x if x ise
fit
dendint
ofl(,)(x ).
uentlyF OEi,
n coveredbysix inteals g, none ofwh
ete ex
d(F,).
me hth
oleorem
2.2arefisbyadeclamo
coveringswch includ ther-ac
inter- valsbut is much more emeive. the next fion we ideratque
lotaingthe dimeion ol r- raints.3. COMPUTING DIMENSION.
In [2], [3],
and[4]
Billingsleydevelopedatechniqueforcomputingthe dimensions ofsetsdefined intermsog (t, ())
of r-adicexpansions byconsideringlimitsof the form
n-.oolim
logX(l. (x))
where-
isa(suitablychosen)
dif-fuseprobabilitydistributionontheBorelsetsof
[0,1],
X represents Lebesgue measure, andI (x)
isthe r- adicinterval oflength r containing x.Thistechniquefor "r-adicsets"
arose out ofresults ofBillingsley[2,
4]
concerningthe dimensions of certainsetsobtainedfromdiscrete-timestochasticprocesses.We
willshowthat these same results, along with Theorem 2.2, can be used todevelop the analogous technique for computing dimensionsofsetsdeterminedbymoregeneralized expansions.We
begin by reviewing the nrydefinitionsandresultsfrom[2]
and[4]. Let
11,1_ be astochastic processonaprobability space(X ,r,#)
taking values inacountable, possibly finite,set S.A
subsetof X of the formc(il,i2 in)= {xCX ill(x)= il,I2(x)= i2 In(x)=
in}, where i1,i2in
are members of S, is called an n-cylinder. Assume that each "oo-cylinder" has #-measure zero i.e.#({xX II1(x)=il, I2(x)=i2 })=0
for eachsequence
il,i2Let E
beasubset of X.For
each 0<a<1 defineL(E)=
lira infla(ci)
._.o tlq_DE (c,)<
where each
c
isan n-cylinder(for
some n).
With methods similarto thoseused in the case of a-outer Hausdorff measure it can beshown that L isanouter measure on the subsets of X and for each E_CX
there exists a unique point a0,0!:_a0_<l,
suchthatL (E)
oo fora<a0
while L(E)
0 fora>ao.
Thenumber a0 iscalledthe
/-dimension
of E anddenotedbydim,(E ).
This valuegenerally dependson#,
E,
and theunderlyingstochasticprocess
It,12 (since
thecylindersare determinedbytheprocess). It
is notdifficult to showthat#(E )>0
impliesdim,(E
1 andthis fact willprove veryuseful.We
will alsoneed thefollowingresult.THEOREM
3.1. (Billingsley):Let (X ,’,#)
and 11,12 beasdefined aboveand, for each xX,
letcn (x)
denote the n-cylinder containing x. That is,cn (x)
{x’X [I t(x ’)
1l(x In (x ’) In (x)}. Let
beanotherprobabilitydistribution on(X
whichassignsmeasurezerotoeach oo-cylinder. If
{x log-(cn(x))
}
E C_ CX
,,-lim log/(c,, (x))
0(3.1)
then
dim,(E
0din(E ).
[]Billingsley’s idea wastocompute the /-dimensionof
E
by constructingsome measure.
for which/(E )>0
and(3.1)
holds,thereby obtainingdim(E
0.He
showedhow thistechnique couldbeusedtocal- culatethe usualHausdorffdimension of certain subsets of[0,1]
by identifyingeachpointwith its r-adicexpan- sion(r
chosen suitably), thesequence
of r-adicdigits comprising the stochasticprocess and an n-cylinder correspondingto an r-adic intervaloflengthr-.
Since coveringsby r-adic intervalsproduceusualHausdorff dimension, Theorem3.1 can beappliedwith suitable-
and Lebesguemeasure.We
nowextendthistech-niquetogeneralized expansions.
A
generalized expansion of a number in[0,1]
will be defined as follows.For
each n 1,2 letkn
>_2 be anintegerand choose values0<an,l< <an ._1<1,
setting an,0 0 and an,k, 1. The initial proportions a1, a1.-
determine a division of[0,1]
into the disjoint intervals[a ,
,a0,1
kl-2,
and[311_1,1 ]. We
will indicate that a point x in[0,1]
falls into the interval(i
0,1 k1-1)
bythe notation 1l(x
i. 1l(x
will be the first term in theexpansionof x(with
respecttothechoicesan ).
At the second stage eachinterval {x[I l(x )=i
isdivided into k disjointsubin- tervals determinedbythegiven proportions 32,1 32,k2_I. Thissplits[0,1]
into klk
disjointintervalswhich are most conveniently expressed in the form {x
ll(X )=i,
12(x)=j} for some choice of=0,1
k1-1
and j =0,1k2-1.
Lettingdn,,
=an,+l-an, for each n and i, wecan alternatelywrite {x I(x )=i, I2(x
)=j {x a1.i+
a2,d, <_
x<
a,i+
a=,y+ld
1,,(but
including the fight hand endpointif k1-1
and j k2-1). 12(x
will be the second term in the expansionof x.Each interval {x I
l(x
)=i,/2(x
)=j is then divided accordingtothe proportions a a.1 aa,k-l- Con- tinuingthis subdivisionprocess,
the nth stageproducesasplittingof[0,1]
into klk kn
disjointintervals{x I
l(x
)=i1,12(x
)=iIn (X)=i,,
{X a1,, -F a2,td1,, --F a3,t d2,,d1,a -I" d- tin ’n
dn
--l,t, d1,,<_
x<
a,i+
a2.,d1. -F d-an
,i.+dn
-t.,. d.i}.
e uen
1l(x ), 12(x
is the generalizedexmion
of x,tng
valu in the ctable t S{0,1 k.-l[n
1,2 }. Ifr2
isaifive
integerandk.
r, a..i =i/r for each n,then the result is the usual r-adicexmion
of x.(If
x has more than one r-adicexmion ts
methprduc theteinating
one.)
We
ll using coveringscom
of inteals lonng to the lltion g of nylindemc
(i i. )=
{x[I (x )=i I. (x)=i. generat
bythe generalizedexnsiom. (Note
that menylindem may
emp; ts
curs ifsomei
S {0,1k-1}.)
orderthat g acompete
und Vitalicovetingof
[0,1]
wendtomake the resmicfion:e
diameters of the(nonemp)
nylindems
at acontrledrate. Ifc. (x)
is the nylinder containg theint
x thend
(q +(. ))
i.
d(c. (x)) =i. d.
+d. +,(x) b(x )>0. (3.2)
It
isosytott (3.2)
impliesthe diameter of ch nylinders
to zero n and forc S to afitet.We
nowed
tothemn
result.OM3.2.
t
It(x ), 12(x
reprintthegenerizexmion
of x[0,1]
thrt
to achoiofo
a.,i, 1 k.-1, n 1,2 dsu
the rdtinginte collation g of n-cyHndefisfi
(3.2). t
definoverthe nyHnde bythe relafiom:(c (i
,ii. ))
p.(i
,ii. (3.3)
where
. (i
i,)1,
p.(i i.
0 ifone or morei k,
p.
(i i.
_,i p._(i i._)
(comistencycondition),
p(i
1,andlim p.(i
i.)
0.en een
uquelyto adiffbili
sfionthe relm
Bof[0,1],
d ifE C
/x,[0,1] Hm logp.(ll(X)J2(x) l.(x)) =0 (3.4)
then
m(E
0dim(E ). (E )>0
thendim(E
0.PROF.
s H
follow fromeorem
3.1 andeorem
2.2.It
isclrom
thecucfi of the n- cylinde(d
rcfion(3.2))
that the nylinde(n
1,2 generate the reitsof[0,1]
d that(3.3)
definadiffubili
msure thateen
uniquelytoe
relsets. Regardingthegenerzedexion
I ,12 as asthasfic thebili s ([0,1],B,X), (X sgue meure)
and notingtt (c. (x))
p.(ll(X)2(x I. (x))
wlex(. (x)) a,t=)ac= a..c=),
itfollobom
rem
3.1 that if E fisfies thehths
ofeorem
3.2 thendimx(E )= dim(E ).
Nowdimx(E
d(E
are definby vedngsbom the nylindegenerat
bythepr Id
drcfi
(3.2)
emurthe nyHndefo a:ete
und Vitalivefingof[0,1]. From eorem
2.2wecclude
dimx(E dim(E
and the resultfollo, oTheorem 3.2 canfrequentlybeappliedtoCantorsetsbuiltfromgeneralized expmions.
We
say C is a generalized Cantorset if itcanbeexpressedin the form C {x(1 t(x ),/2(x S"
whereS"
issome subset of the countableproduct ,,Xt{0,1. k,,-1}.
The simplest case occurs whenS" ,,X-tS"
whereS,,
_C{0,1 k,,-1}
is the set of "allowable" digits at the nth stage. The resultingCantor
set is called"independent" andcan be written as C {x
II,, (x)S,,
for all n}. TheusualCantor
set(minus
acountable collection of"endpoints" corresponding to somenumbers with morethanonetriadicexpansion)isanexample, resulting when k,, 3, a,,.ii/3,
andS, (0,2}
for all n.We
havethefollowingcorollary.COROLLARY
3.2.Let
C be a generalized independentCantor
set built fromgeneralized expansions whose n-cylinders satisfy(3.2). Let
s, denotethe size of the set ofallowable digitsS,,
atthent
stage.Suppose
there existsd,
suchthatd,,.i
d,, for eacheS,,.
Ifthelimitlog
(s s s )-t
lira log
dtd d.
existsandequals 0(3.5)
then
dim(C
0.PROOF. We
applyTheorem 3.2 with C7(c,, (i i. ))
in the role of(ss2 0Es)-t
and-
definedifiS
otherwise.by for all j7 correspondstochoosing uniformlyandindependently
among
the allowabledigitsateach stage, tWe
applyTheorem 3.2 tocomputethe Hausdorff dimension of a certaingeneralized "Markov"Cantor
set(i.e.
aCantor
setin which the allowable digitsat the nth stage depend onthedigit chosenat the(n-1) ’
stage).
Whiletechniquesexist intheliteratureforcalculatingthe dimemion of self-similarsets(see [5], [6], [7])
by obtainingtheso-called "similarity dimension", thefollowingsetisonlyself-similar in alimitingsense.(It
can bepartitioned as a countablyinfinite union ofsimilitudes.) For
each n takek 5,
and for n even setd,o=dn=dn,=ct
anddn,t=dn,a=a (where a>O, a>O
satisfy3a+2a 1)
whilefor n oddsetd,,,t=d,3=#
andd,0=d,2=d,4=b (where
>0, b>O satisfy2+3b 1.) We
setSt={1,3},
allowing only "1"or"3"tobeselectedatthe firststage. LettingS, (i)
denote the allowabledigitsatthe nm stage given that "i" is selected at the(n-l)
th stage, we use the rulesS(O)= {1), S(1) {0,2},
S,, (2) {1,3}, S (3) {2,4},
andSn (4) {3}. (These
rulescorrespondtothepermissiblemovesin a random walk on{0,1,2,3,4}
with reflecting barriers at 0 and4.) We
will show the resultingCantor
set C {xII (x )S
and1 (x)Sn (In_t(x))
for each n has dimension log1/3 /
logaB. Construct
aMar-
kovprobabilityrule onthe n-cylinders accordingtothe initial distribution p
t(1)
pt(3) 1/2
and transition probabilitiesp(ll0)=l, p(011)=l/3, p(211)=2/3, p(l12)=p(312)=l/2, p(213)=2/3,
p
(413) 1/3,
p(314)
1,and p(i J
0 otherwise.(This
gives p2(i ,J
Pt(i
)p (j and,induc- tively, p(i i
p,,_(i i,_Dp(4, i,,-D .)
Theresultingdistribution ./ isclearly supportedon the set C. Furthermoreit issufficienttocomputethe limit in(3.4)
over oddintegersandweobtain,foranyxC,
lim logp2
+(I t(x I2 +(x ))
lim
1o 2-t3
log
dldl(X) d2n+t,z,+t(x
loga/3+tand hence
dim(C
log1/3 /
log a# asclaimed.ACKNOWLEDGEMENI. This research was supported by the Natural Sciences and Engineering Research Council ofCanada.
[] BESICOVITCH,
A.S. Onexistenceof subsets of finitemeasureofsetsofinfinitemeasure. Indag.Math.14
(1952)
339-344.[2] BILLINGSLEY, P.
Hausdorff dimension inprobability theory, IllinoisJ.
Math. 4(1960)
187-209.[3] BILLINGSLEY, P.
ErgodicTheoryandInformation, Krieger(1978).
[4]
BILLINGSLEY,P. Hausdorff dimension inprobability theoryII,
IllinoisJ.Math.5(1961)
291-298.[5] HUTCHINSON, J.E.
Fractalsandself-similarity, IndianaUniv. Math.J.
30(1981)
713-747.[6] FALCONER, K.J.
TheHausdorff dimension ofsomefractalsandattractorsofoverlapping construction,J.
Statist. Phys.47(1987)
123-132.[7] FALCONER, K.J.
TheHausdorff dimension of self-affinefractals, preprint(1987).
Advances in Difference Equations
Special Issue on
Boundary Value Problems on Time Scales
Call for Papers
The study of dynamic equations on a time scale goes back to its founder Stefan Hilger (1988), and is a new area of still fairly theoretical exploration in mathematics. Motivating the subject is the notion that dynamic equations on time scales can build bridges between continuous and discrete mathematics; moreover, it often revels the reasons for the discrepancies between two theories.
In recent years, the study of dynamic equations has led to several important applications, for example, in the study of insect population models, neural network, heat transfer, and epidemic models. This special issue will contain new researches and survey articles on Boundary Value Problems on Time Scales. In particular, it will focus on the following topics:
•
Existence, uniqueness, and multiplicity of solutions
•
Comparison principles
•
Variational methods
•
Mathematical models
•
Biological and medical applications
•
Numerical and simulation applications
Before submission authors should carefully read over the journal’s Author Guidelines, which are located at
http://www .hindawi.com/journals/ade/guidelines.html. Authors shouldfollow the Advances in Difference Equations manuscript format described at the journal site
http://www.hindawi .com/journals/ade/. Articles published in this Special Issueshall be subject to a reduced Article Processing Charge of C200 per article. Prospective authors should submit an elec- tronic copy of their complete manuscript through the journal Manuscript Tracking System at
http://mts.hindawi.com/according to the following timetable:
Manuscript Due April 1, 2009 First Round of Reviews July 1, 2009 Publication Date October 1, 2009
Lead Guest Editor
Alberto Cabada,
Departamento de Análise Matemática, Universidade de Santiago de Compostela, 15782 Santiago de Compostela, Spain;
[email protected]Guest Editor
Victoria Otero-Espinar,
Departamento de Análise Matemática, Universidade de Santiago de Compostela, 15782 Santiago de Compostela, Spain;
Hindawi Publishing Corporation http://www.hindawi.com