253 Kragujevac J.Math.30(2007)253–262.
ITERATIVE OPERATORS FOR F AREY TREE
Ljubiˇs a Koci´c1,Liljana Stefanovska2and
Sonja Gegovska-Zajkova3
1Faculty of Electronic Engineering,University of Niˇs,Serbia
(e-mail:kocic@elfak.ni.ac.yu)
2Faculty of Technology and Metallurgy,SS Cyril and Methodius University,
Skopje,R.Macedonia
(e-mail:f.ukim.edu.mk)
3Faculty of Electrical Engineering,SS Cyril and Methodius University,
Skopje,R.Macedonia
(e-mail:szajkova@etf.ukim.edu.mk)
(Received October18,2006)
Abstract.The existence of an operator that maps rational number1/2into the array of Farey tree is proven.It is shown that this operator can be represented by combinatorial compositions of two simple real functions:f:[0,1]→[1/2,1],which is(0,1)-rational and σ:[0,1]→[0,1],which is linear.Then,another operator,mapping rational r∈(0,1)into the branch of the Farey tree emanating from the node characterized by r is described.
1.INTRODUCTION
The Farey tree is a collection of sets(called levels)F T={T0,T1,T2,...},where T0={r1=1/2}is called root of the tree.The n-th level T n={r2n,...r2n+1−1},
n=0,1,2,...,is the decreasing sequence of rationals r j∈(0,1),like T1={r2=
254
2/3,r3=1/3},T2={r4=3/4,r5=3/5,r6=2/5,r7=1/4},....One can identify FT with the infinite binary graph whi
ch set of vertices is isomorphic with Q[0,1], the set of rationals from the segment[0,1].In set-theoretic notation,Farey tree is collection of sets
F T={{1/2},{1/3,2/3},{1/4,2/5,3/5,3/4},(1)
{1/5,2/7,3/8,3/7,4/7,5/8,5/7,4/5},
{1/6,2/9,3/11,3/10,4/11,5/13,5/12,4/9,5/9,
7/12,8/13,7/11,7/10,8/11,7/9,5/6},...}.
Farey tree(1)plays an important role in Chaos Theory.For ex.,it contains all quasi-periodic routes to chaos.In fact,if a dynamic system contains two periodic oscillators with different frequencies,f1and f2,(f1<f2),the regime in the system tries to preserve the state where the ratio f1/f2is the simplest rational number,say 1.Then,f1:f2=1:1which is called optimal resonance or1:1mode-locking regime.If this is not possible,the system”jumps”to the”reserve”mode-locking state,f1/f2=1/2.If,by some reason,this state is not possible,the system passes to the next simple mode-locking possibility,f1/f2=2/3(or f1/f2=1/3),and so on,along the Farey tree.Among others,Farey tree contains the quickest route,so called golden route to chaos,the sequence of ratios of consecutive Fibonacci numbers converging to famous golden meanφ=(
√5−1)/2.
Let a0,...,a k denote coefficients in continuous fraction expansion(partial quo-tients)of a rational number r
r=[a0,a1,...,a k]=1
a0+
1
a1+
...
+
1
a k
,a i∈N,a k≥2.(2)tm2007
Using expansion(2),Cvitanovi´c[1]gave the following formal definition of the Farey tree level:
Definition1.The n-th Farey tree level T n is the monotonically increasing se-quence of2n continued fractions[a0,a1,...,a k]whose entries a i≥1,i=0,1,...,k−
1,a k≥2,add up to n+2.
255
For example,
T 2={[4],[2,2],[1,1,2],[1,3]}={1/4,2/5,3/5,3/4},
T 3={[5],[3,2],[2,1,2],[2,3],[1,1,3],[1,1,1,2],[1,2,2],[1,4]}
={1/5,2/7,3/8,3/7,4/7,5/8,5/7,4/5},
etc.
The Farey tree can be split into two sub-trees ([2],[3]).One of them,denoted by F T 0(”0-subtree”)has the root in 1/3and contains all rationals from the open interval (0,1/2);Another,F T 1(”1-subtree”)has t
he root in 2/3and contains all rationals from (1/2,1).It is proved in [3]that elements of F T 0have continued fractions of the form [a 0,a 1,...,a k ],a 0≥2,while elements from F T 1have the form
[a 0,a 1,...,a k ],a 0=1.The k -th level of F T i will be denoted by T i k ,i =0,1,and it
represents ”i -half”if of the level T k .
2.FAREY TREE OPERATOR
Lemma 1.If in (2)all a k ∈N ,and k ≥1,then r ∈(0,1).Proof.Consider partial ”sum”s j =1a k −j +···+1a k (0≤j ≤k ).Obviously,s 0=1/a k ∈(0,1)for all a k ≥2and s 0=1for a k =1.Then,s 1=1/(a k −1+1/a k )∈
(0,1),and by induction s j ∈(0,1).Thus,s k =r ∈(0,1),except if k =0(and a 0=1)which is excluded by supposition.2Lemma 2.The simplest difeomorphism
[a 0,...,a k ]→[1,a 0,...,a k ],a k ∈N ,is given by
f :x →11+x ,(3)
and it maps [0,1]to [1,1].
256
Proof.The proof follows by definition[1,a0,...,a k]=
1
1+[a0,...,a k]
and by
Lemma1,x=[a0,...,a k]∈(0,1).2 Lemma3.The simplest difeomorphism
[a0,a1,...,a k]→[a0+1,a1,...,a k]
is given by
g:x→
x
1+x
,
(4)
and it maps[0,1]to[0,1
2
].
Proof.Let x=[a0,...,a k]∈(0,1].Then
[1+a0,a1,...,a k]=
1
1+a0+ 1a1+...+1a k =
1
1+1
[a0,...,a k]
=f 1x ,
where f is given by(3).Setting g(x)=f(1/x)for x=0gives(4).2 Note that composition g◦f−1yields(g◦f−1)(x)=g(f−1(x))=1−x.Denote
σ(x)=1−x.Then,byσ=g◦f−1,it follows g(x)=(σ◦f)(x).Let˜Q[0,1]
denotes partition set of Q[0,1].Consider the following four set valued operators ˜Q[0,1]→˜Q[0,1]:
F1={σ◦f,f},
北京青年报网站
F2={σ◦f◦σ,f},
F3={σ◦f◦σ,f◦σ},
F4={σ◦f,f◦σ}.
(5)
Note that mappings in(5)have the form F={ϕ,ψ}.Hereϕ:[0,1]→[0,1/2]is one of two functions:(σ◦f)(x)=x/(x+1)or(σ◦f◦σ)(x)=(x−1)/(x−2).On the other side,ψ:[0,1]→[1/2,0]is ether f(x)=1/(x+1)or(f◦σ)(x)=1/(
2−x).Also, the inverse operators to(5)can easily be established provided that the conventions F i(∅)=∅,and
F i({r1,...,r k})={ϕ(r1),...,ϕ(r k),ψ(r1),...,ψ(r k)},(6) are adopted.Namely,F−1i(∅)=∅,andpamam
F−1i({s1,...,s k,s k+1,...,s2k})=
{ϕ−1(s1),...,ϕ−1(s k),ψ−1(s k+1),...,ψ−1(s2k)}.(7)
257
Theorem1.Neighbor levels of FT map one to another by any of the operators(5) or their inverses.More precisely,F i(T n)=T n+1and F−1i(T n+1)=T n,n=0,1,....
Proof.Consider the operator F1.Suppose that r k=[a0,...,a k]∈T n.By definition,and convention(6),F1({r k})={g(r k),f(r k)},and by use Lemma2and
3we conclude that
F1({r k})=F1({[a0,...,a k]})={g([a0,...,a k]),f([a0,...,a k])}
声音导引系统={[a0+1,a1,...,a k],[1,a0,...,a k]}. Then,F1({r k})={r p,r q},and by Definition1,r p,r q∈T n+1.Since any of2n rationals from T n has one-to-one unique expansion in continued fraction,the operator F1applying on them produces2n expansions that define exactly2n+1new rationals from the upper level T n+1.Since the mappingσjust reverse the ,F2(x)= {g(1−x),f(x)},F3(x)={g(1−x),f(1−x)}and F4(x)={g(x),f(1−x)},we conclude that F i(T n)=T n+1(n=0,1,...)for i=2,3and4.The inverse mapping F−11(7)maps T n+1→T n.The similar reasoning applies to other F i’s from(5).2 The immediate consequence of Theorem1is that(F i◦F j)(T n)=T n+2,for any i,j∈{1,2,3,4}.This leads to the main result of this note.
Theorem2.Let G be any composition of mappings in(5)
G m=F i
1◦F i2◦···◦F i m i j∈{1,2,3,4},m∈N.(8) Then,
G m({1/2})=T m.(9)
Proof.Now,note that difeomorphism f given by(3)is bijective mapping of the level T n−1onto T1n”1-half”of the level T n.For any r=[a0,a1,...,a k]∈T n−1,a i≥1,i=0,1,...,k−1,a k≥2,and by Definition1, a i=n+
1. Also,f(r)=[1,a0,a1,...,a k],with the sum of partial quotients1+ a i=n+2. Therefore,f(r)∈T n.Further,thefirst partial quotient of f(r)is1making it the member of the”1-subtree”or f(r)∈T1n.Similar reasoning may be applied on g given
258
by(4),which maps T n−1onto T0n bijectively.Suppose that r∈T n−1.Then,by Definition1,r=[a0,a1,...,a k],where a i≥1,i=1,2,...,k−1,a k≥2,and a i=n+1.Since g(r)=g([a0,a1,...,a k])=[a0+1,a1,...,a k],then the sum of partial quotients is1+ a i=n+2,so g(r)∈T n.Further,thefirst coefficient in the continued fraction expansion of g(r)is≥2,which guarantees that g(r)belongs to the”0-subtree”.This gives g(r)∈T0n.
By similar argument and in the previous proof,we have
(F i◦F j)(T n−1)=T n+1,
语言
转换for any i,j∈{1,2,3,4},and therefore
G2(T0)=(F i◦F j)(T0)=(F i◦F j)({1/2})=T2.甲午中日战争教案
Thus,(9)follows by induction.2 Definition2.The operator r→H m(r),given by
H m(r)=
m
n=1G n({r}),r∈Q[0,1](10)
will be called partial Farey tree operator.
The following two statements are consequences of Theorem2:
Corollary1.If in(10)m→∞,the Farey tree(without root)is obtained as an image of a single rational number,r=1/2.Namely,
H∞(1/2)=
∞
n=1G n({1/2})=F T\{1/2}.
By using F(n)to denote n-th auto-iteration of the operator F,with usual conven-tion that F(0)is identity,we may state a short definition of the Farey tree,given as Corollary of Theorem2.
Corollary2.F T=
∞
n=1F(n)({1/2}),where F∈{F1,F2,F3,F4}.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议