Citation
The Lipschitz constant of a periodic recursion

Material Information

Title:
The Lipschitz constant of a periodic recursion
Creator:
Chen, Terry S
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
vii, 24 leaves : ; 29 cm.

Subjects

Subjects / Keywords:
Recursive functions ( lcsh )
Recursive functions ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Thesis:
Thesis (M.S.)--University of Colorado at Denver, 1992. Applied mathematics
Bibliography:
Includes bibliographical references.
General Note:
Submitted in partial fulfillment of the requirements for the degree, Master of Science, Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Terry S. Chen.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
26891560 ( OCLC )
ocm26891560

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

THE LIPSCHITZ CONSTANT OF A PERIODIC RECURSION by Terry S. Chen B.S., Oklahoma State University, 1989 A thesis submitted to the Faculty of the Graduate School of the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Applied Mathematics 1992

PAGE 2

This thesis for the Master of Science degree by Terry S. Chen has been approved for the Department of Mathematics by David C. Fisher William Briggs Date

PAGE 3

Chen, Terry S. (M.S., Applied Mathematics) The Lipschitz Constant of a Periodic Recursion Thesis directed by Assistant Professor David C. Fisher A function f : --+ is Lipschitz if there exists a constant L such that lif(b)f(a)ll ::; Lllb-ail for all a and bin Given that the recursion, Xi+I =/(:vi) fori= 1, 2, 3, ... has a period p solution, we find the minimal value of L. For f E n 2: 2, the value of L is surprisingly easy to find. For f E the minimal values of L are more difficult to find. The form and content of this abstract are approved. I recommend its publication. Sign David C. Fisher .. 11

PAGE 4

To my parents Jin and Linda for their constant love and support and To Rick for his love, friendship, and invaluable sense of humour

PAGE 5

ACKNOWLEDGEMENTS I would like to thank David Fisher, Stan Payne, and Bill Briggs for giving me the opportunity to learn by sharing their time and expertise. Above all, I would like to thank Dr. Fisher for his support, guidance, immeasurable patience, and wonderful enthusiasm. IV

PAGE 6

Contents 1 The Lipschitz Constant for p = 1, 2, 3, 4, 5, 6, 7 2 2 Odd Periods 15 3 Even Periods 19 4 Summary 23 5 References 24 v

PAGE 7

List of Figures 1 2 3 4 Piecewise linear function with a period four solution LiYorke digraph .................... Digraphs for functions with a period five solution Bounds for the Lipschitz Constant . . . . . vi 5 8 10 23

PAGE 8

List of Tables 1 The maximal lower bounds Bp when p is odd 2 The maximal lower bounds Bp when p is even Vll 19 22

PAGE 9

The Lipschitz Constant for a Periodic Recursion A function f : !Rn --t !Rn is Lipschitz if there exists a constant L such that llf(b)-f(a)ll $ Lllb-all for all a, bE !Rn. Suppose the recursion, :Z:i+I = f(:vi), has a period p solution. What is the minimal value of L? To begin answering the question above, we shall first consider functions with dimension n greater than one. p-periodic solution of :Z:i+I = f( :Vi) if :z:o = :Vp and :Vi "f; :z:o for i < p. Let the set of :vi in X be referred to as the :v-iterates of a p-periodic solution under f. Note that p-periodic solutions are not unique. Theorem 0: Given f : !Rn --t !Rn and the recursion :Z:i+I = f(:vi), iff has a pperiodic solution where p;::: 2, then the Lipschitz constant L(f) is bounded below by L(f) ;::: 1. Moreover, for n > 1, this bound is exact. Proof: Given :Z:i+I = f(:vi) and using that the maximum is greater than or equal to the geometric mean, we get L > max ( llf(:v2)-f(:z:t)ll, llf(:v3)-f(:v2)11, ... !If( :vi)-f(xp)ll) ll:z:2-:Vtll ll:z:3-:z:2ll ll:z:1 Xp" ( ll:z:3-x2ll ll:z:4-x311 llx2-:z:tll) = max l!x2 :z:1ll' llx3 :z:2ll' ... ll:z:1 :z:PII > ( ll:v3-:v21! ll:v4 :v:,ll ... ll:v2 :v, II) '1n = L l!x2-xdl ll:v:l-x21! l!:z:1 xpll 1

PAGE 10

For n > 1, let f : lRn --+ lRn be a 2Tr fp rotation in the :z:1 :z:2 plane. In this case, the ratio of any two sides of this figure, as defined by the Lipschitz condition and the recursion :z:i+ 1 = f(z;), is equal to 1. Therefore, we have shown the bound L ;:::: 1 is exact. 0 From Theorem 0 we see that the bound holds for the one-dimensional case; however, this particular bound is not necessarily the best bound for n = 1. Surprisingly, finding the best lower bound on L when n = 1 is more complex than the answer for the lower bound when n > 1. Hence, for the remainder of this paper we address the one-dimensional case by finding the exact lower bounds for Lover lR. Definition 2: Let C be the set of Lipschitz functions on !R. For all f E C, let L(f) be the Lipschitz constant of f. Given :z:0 E !R, for all i ;:::: 0, recursively define Zi+t = f(zi) Let Bp = inf L(f), where Rp C with period p. JERp In the next section of the paper 1 we find Bp for periods one through seven. By doing this, the conclusion of the paper, which contains general results for the even and odd periods in one-dimension, should be readily understandable. 1 The Lipschitz Constant for p == 1, 2, 3, 4, 5, 6, 7 Finding B1 and B2 are relatively trivial. Consider the following two theorems. Theorem 1: Let f : lR--+ lR be a Lipschitz function. If the recursion Zi+t = f( :z:i) has a 1-periodic solution for some x0 then the Lipschitz constant off is at least 2

PAGE 11

zero. Furthermore, this bound is sharp. Proof: By definition of a function, for all f : !R ---+ !R, L(f) 2:: 0. This establishes the lower bound. In order to show exactness, consider the function f( x) = 0. Then, x0 = 0 is a period one solution and B1 = 0. D Theorem 2: Let f : R ---+ !R be a Lipschitz function. If the recursion Xi+l = f( Xi) has a 2-periodic solution for some m0 then the Lipschitz constant off is at least one. Furthermore, this bound is sharp. Proof: If f is a function with a period two solution, then there exists x0 :/:-XI with mo = f(xt) and IDI = f(mo). Then To show that the lower bound is exact, we consider Xi+I = f(xi) with f(x) = -x. Then x0 = 1 and xi = -1 is a period two solution. Hence, B2 = in L(f) = 1 !ElR2 and the bound is exact. 0 Finding the minimal Lipschitz constant for functions with period three so-lutions becomes slightly more involved. We approach this problem as a linear algebra exercise. Before proceeding let us review the Perron Frobenius Theorem [4], which we use in finding B3 Perron Frobenius Theorem: If A is an irreducible nonnegative matrix then A has a positive real eigenvalue A with the following properties: 1. A is a simple root of the characteristic equation of A. 3

PAGE 12

2. >. is associated with a positive eigenvector y. 3. If a is any other eigenvalue of A, then>. jaj. Lemma 0: Let A be a nonnegative and irreducible matrix, and let p be an eigenvalue of A. If Ar ::; Lr for some r > 0, then L p. Proof: Since p is an eigenvalue of A, then Ar = pr ::; Lr. This implies L p. For the value of B3 we have the following theorem. Theorem 3: Let f : ...__. be a Lipschitz function. If the recursion :Ci+l = f( Xi) has a 3-periodic solution for some a:0 then the Lipschitz constant off is at least 1 +2 J5. Furthermore, this bound is sharp. Proof: To find B 3 for :Ci+l = f(a:i), without loss of generality assume a:2 < :co < a:1 is a period three solution. Define r1 = a:1 :co and r2 = :co a:2. condition then gives: lf(a:I)-f(a:o)l ::; L!a:1-:col => !a:2-a:t[::; Lja:1-:col => (r1 + r2) ::; Lr1 lf(a:o)-/(a:2)l ::; Lla:o-a:2! => la:1-:col ::; Lla:o-a:2! => r1 ::; Lr2 We may now form a matrix A 3 using the last set of inequalities given by the Lipschitz conditions above. We then have Lr 2 A 3 r with A 3 = [ Solving the characteristic equation Det(>. 3JA3) = >.l AJ -1 = 0, we get the eigenvalue >.3 = (1 + JS)/2. Note that A 3 has all nonnegative entries and A 3 is irreducible. Therefore, by the Perron Frobenius Theorem, ..\3 is the largest real positive eigenvalue of A3 Combining this fact with Lemma 0, we obtain 4

PAGE 13

the lower bound L 2::: {1 + VS)/2. Consider the equation :Ci+I = f(:ci) with f(:c) = 1l:z:l{1 + VS)/2. If :co = 0, then :c1 = 1, :c2 = (1 VS)/2, and :c3 = 0 gives a period three solution for f(:c ). Therefore, B3 = inf L(f) = (1 + v'5)/2, /E'!R.3 and the bound is exact. D :Ill= -1 + z0 = 1e :llJ = -1f(zo) = -1 + e Figure 1: Piecewise linear function with a period four solution Theorem 4: Let f : --+ be a Lipschitz function. If the recursion :Ci+l = f(:ci), has a 4-periodic solution, then the Lipschitz constant off is at least one. Furthermore, this bound is sharp. Proof: Given c: E {0, 1), let fE E R4 be the piecewise linear function in Figure 1. 5

PAGE 14

Then, the largest value for the slope of the function is = llf(zt)-f(zo)ll = l/(1 _e). Hence, B4 = inf L(f) ::; lim = lim 1/(1 e) = 1. From the argument /ER4 oo-+O above, we obtain the upper bound B4 ::; 1. By Theorem 0, the lower bound B4 ;::: 1 is obtained. Combining these two bounds, we get B4 = 1. 0 To define the minimal Lipschitz constant for functions with a period five so-lution, we enlist the aid of Sharkovsky's Theorem[6). This particular theorem dates back to 1964, when the Ukrainian mathematician A. N. Sharkovsky provided an answer to the question "When does period h imply period k?" Though Sharkovsky's proof is far from elegant, the theorem itself is very elegant. For a complete proof to Sharkovsky's Theorem, the reader is advised to reference the graph theoretic proof given by Ho and Morris [3]. Sharkovsky's Theorem: A continuous function f: lR -+ lR which has a point of period h, must also have a point of period k precisely when h precedes k in the following ordering: 3, 5, 7, ... 6, 10, 14, ... 12, 20, 28, ... 24, 40, 56, ... 4, 2,1 of all positive integers. Examining the sequence of numbers in Sharkovsky's Theorem, several interesting observations may be noted. For instance, we may see that period h implies period 1 for all h. We may also observe that a continuous function f: lR -+ lR must have an infinite number of periodic points if f has a periodic point not equal 6

PAGE 15

to a power of 2. And, if a function f has a period of 3, then it has points of all periods. In other words, period 3 implies period k for all k. From Sharkovsky's Theorem, we have the following corollary. Proof: By Sharkovsky's Theorem, if h precedes k in the ordering, then the set of functions with a period h solution is contained within the set of functions with a period k solution. This implies that the minimal Lipschitz value for functions with a period h solution is greater than or equal to the minimal Lipschitz value for functions with a period k solution. Thus, we have Bh = inf L(f) inf L{f) = Bk. o !ERh Along with Sharkovsky's Theorem, we also use Corollary 1, the linear algebra approach used for finding B3 and some ideas from the work of Straffin [7] to find To summarize Straffin's work, let f : --+ be a continuous function, and let X = { zl! Zp-1! zp, . ,} be a p-periodic solution of f. Let be the smallest number among the under f. Let i1 i2 ip be the perm utation of {1, 2, ... p} with z;1 < Zi2 < < z;P. Marking these points on a real number line divides the line into (p-1) bounded. intervals. Label these intervals /11/ 2 ,Ip-l Starting from the left, let Si and ti be the endpoints of the interval Ii. Then, there is a direction from/; to Ii if Ii C [f(s;), f(ti)]. A digraph is then 7

PAGE 16

formed by using vertices corresponding to the intervals, with the vertices also labeled as /1 ,12 lp_1 So, if there exists direction from the intervals Ji to Ij, then drawing a directed arc from the vertices Ii to I; in the digraph results in a p-periodic digraph of f. We shall refer to the p-periodic digraph as the Straffin digraph of X. Lemma 1: (Straffin )Let X= {:v0 :v1 ... :vp_1 } be a period p solution of :vi+l = /(:vi) If the Straffin digraph of X has a nonrepetitious cycle of period k, then :Vi+I = f( :Vi) has a period k solution. A cycle is nonrepetitious if it does not consist entirely of a cycle of smaller length repeated several times. The proof to Lemma 1 may be found in [2]. The reader is encouraged to reference Straffin's well-written paper to clarify the ideas discussed above. Figure 2: LiYorke digraph By Straffin's results, a function with a digraph or subdigraph shown in Figure 2 would have periods of all lengths k > 0 since nonrepetitive cycles of lengths k may be found in the digraph. This is achieved by adding repetitions of the one cycle, thus obtaining nonrepetitive cycles of even and odd length. As a note of interest, in 1975, Li and Yorke [5] published a theorem (independent of Sharkovsky's Theorem) which states that a continuous function of period 3 has 8

PAGE 17

points of all periods, i.e., period 3 => period k for all k. Understandably, the particular digraph in Figure 2 is referred to as the LiYorke Digraph. As described by the construction above, for p = 5, there exists twelve (p!/(2p)) possible digraphs (see Figure 3). (Note: Given an ordering for the x-iterates, the reverse ordering and cyclic shifts of the ordering produce the same digraph. Hence, there exists (p! / (2p)) possible digraphs.) In Figure 3, all the digraphs except (k) and (1) contain the Li-Yorke digraph as a subgraph; however, (k) contains a 3-cycle. Digraph (1) is the only one without a period three cycle. Therefore, as stated in Sharkovsky's Theorem, we may conclude that period five does not imply period three. Further, if we have a period five solution and do not have a period three solution, then we must have a period five solution that has the ordering of (1). We shall now find the minimal Lipschitz constant for p = 5 using the linear algebra techniques introduced previously. Theorem 5: Let f : !R -+ !R be a Lipschitz function. If the recursion :Ci+l = f( :Ci) has a 5-periodic solution for some :c 0 then the Lipschitz constant off is at least As, where As 1.51288. Furthermore, this bound is sharp. Proof: Let :Ci+l = f(:ci) have a 5-periodic solution. If the solution has an ordering shown in digraphs (a) through (k), then :Ci+l = f(:ci) also has a 3-periodic solution. Hence, the Lipschitz constant of f would be greater than or equal to B3 If the 5-periodic solution has the ordering shown in digraph (1), then 9

PAGE 18

(a) :V3 < :v2 < :vo < :V4 <:vi (b) :V3 < :v2 < :vo <:vi < :V4 (c) :v2 < :v4 < :vo < :v3 <:vi 14 14 13 (g) :v4 < :v2 < :vo < :v3 < :v1 (h) :v2 < :v4 < :vo < :vi < :v3 (i) :v3 < :v4 < :vo < :v1 < :v2 13 14 14 (j) :V4 < :v3 < :vo < :v1 < :v2 (k) :v2 < :V3 < :vo < :V4 < :v1 (1) :V4 < :v2 < :Vo < :v1 < :V3 Figure 3: Digraphs for functions with a period five solution 10

PAGE 19

:Z:4 < :z:2 < :z:o < :z:1 < :z:3 is a 5-periodic solution. Therefore, we shall define then gives: IJ(:z:2)-f(:z:4)1 ::; L/:z:2-:z:4i :::::? 1/{:z:o)-/(:z:2)l ::; L/:z:o-:z:2/ :::::? 1/(:z:t)-ft:z:o)l ::; L/:z:1 :z:ol :::::? if(:z:3)/(:z:1)!::; Lj:z:3-:z:1! :::::? l:z:3-:z:ol::; Ll:z:2-:z:4l :::::? /:z:1-:z:3/ ::; L/:z:o-:zJ2/ :::::? /:zJ2-:z:1/::; L/:z:1-:z:o/ :::::? /:z:4-:z:2/ ::; L/:zJJ-:z:1/ :::::? r3 + r1 ::; Lr4 r3 ::; Lr2 r 1 + r2 ::; Lr1 r4 ::; Lr3 From the last set of inequalities obtained from the Lipschitz conditions, we get Lr Asr with A,= !] As for A3 As also has all nonnegative entries and is irreducible. Solving the characteristic equation Det(Asl -.As) = As1 = 0, we have the eigenvalue As :::::::: 1.51288. Since Asr = Asr, by the Perron-Frobenius Theorem and Lemma 0, we see that L As. Let :zJo = 0. Given the equation Zi+I = /(:lli) where f(:zJ) = 1 -/:zJ/As, we have the following: :co= 0 :zJ1 =/(:co) = 1 :c2 = f(:r:I) = 1As :llJ = j(:zJ2) = 1 +As As2 :z:4 = f(:z:J) = 1As-As2 + As3 :zJs = /(:zJ4) = 1As+ .As2 + .As3 -As 4 = 0. Since :z:0 = :zJ5 we have a period five solution. Therefore, Bs = inf L(f) = As. /ErRs Hence, the bound is exact. D 11

PAGE 20

To find the value of B6 we introduce the following lemmas which pertain to all results in the paper thus far. Lemma 2 :Given that = and = then L(r) < (L(f))s. In this case, r is defined to be a composite function with itself s times. Proof: The proof will be by induction on s. For s = 1 we have L(jl) =:; L(/)1 For the induction hypothesis, assume L(fs-l) =:; (L(f))s-l is true. Then =5 (L(f)t-11/(x)f(y)i =5 (L(f)Yix-Yi Using the argument above and the definition of Lipschitz, we then have L(r) =sup (lr(x)r(Y)i) =5 sup ((L(f))s lxYi) = (L(f)y. D lxYi lxYi k 2-1< Lemma 3: Let p = 2 r. Then, Bp Br for r > 1. Proof: Let g = Since f is p-periodic, then g is r-periodic. Using this observation and Lemma 2, then Theorem 6: Let f : ---+ be a Lipschitz function. If the recursion Xi+ 1 = f( Xi) has a 6-periodic solution for some xu, then the Lipschitz constant off is at least where 1.61803. Furthermore, this bound is sharp. 12

PAGE 21

Proof: By Lemma 3, we get B6 Bi12, which establishes the lower Given :Ci+1 = f( :Ci) where f( :c) = 1 I, we have the following: :co= 0 = f(:co) = 1 = j(:c1) = 1= J(:c2) = 1 + B3 = f(:c3) = 1Bi12 + B3 :cs = f(:c4) = 1+ B3 + :cs = f(:cs) = 1+ B3 Bj + B:/2 From the above, the last equation factors into :cs = ( -Bi12 + 1)(BiB3-1) which equals zero. Since = we have a period six solution; therefore, the bound is exact. 0 For functions with a solution of period 7, we introduce a lemma which is an important result to odd periodic solutions. Lemma 4: If :Ci+l = f(:ci) has an odd period p solution and no lower order odd periodic solutions greater than 1, then :Ci+l = f(:ci) has a period p solution, :co,:cl,,:cp-1, with :cp-1 < :Cp-3 < ... <:co< < < ... < :cp-2 The proof of this lemma may be found in [2). Theorem 7: Let f : !R --+ !R be a Lipschitz function. If the recursion :Ci+l = f( :ci) has a 7-periodic solution for some then the Lipschitz constant off is at least A71 where A7 1.46577. Furthermore, this bound is sharp. Proof: Let :Ci+l = f(:ci) have a 7-periodic solution. Iff has a 3-periodic solution, 13

PAGE 22

then the Lipschitz constant off would be greater than or equal to B3 Iff has a 5-periodic solution but no 3-periodic solution, then the Lipschitz constant of f would be greater than or equal to B5 If f does not have a 3-periodic or a 5-periodic solution, then by Lemma 4, :z:6 < x 4 < :z:2 < x0 < :z:1 < :z:3 < :z:5 is a 7-periodic solution. :v2 :z:4 r5 = :z:5 and r6 = :z:4 :z:s. The Lipschitz condition then gives: 1/(:z: l:zJs-:val :::; Ll:z:4-:ll61 => r1 + r3 + rs :::; Lrs IJ(:z:2)-/(:IJ4)1 :::; Ll:v2-:IJ41 => l:z:3-:zJsl :s; Ll:z:2-:z:4l ::::::> rs :s; Lr4 1/(:zJo)J(x2)l :::; Ll:zJo-x2l => l:z:1-:z:3l :s; Ll:vo-:z:2l ::::::> r3 :s; Lr2 1/(:llt)-/(:zJo)l :::; Ll:zJt :zJol ::::::> I:IJ2-:lltl :s; Ll:v1-:z:ol ::::::> r1 + r2 :::; Lrt 1/(:IJJ)/(:llt)l :::; LI:IJJ-:IJ1i ::::::> l:v4-x2l :::; Ll:v3 :Vtl ::::::> r4 :::; Lr3 1/(:zJs)/(:llJ)I :::; Ll:zJs-:IJ31 ::::::> l:z:s-:z:4l :::; Ll:vs-:v3i ::::::> rs :::; Lrs From the end result of the Lipschitz conditions, we have Lr 2:: A7r with 1 1 0 0 0 0 0 0 1 0 0 0 As= 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 As for A3 and As, A7 also has all nonnegative entries and is irreducible. Solving the characteristic equation Det(..\7 / -A7 ) = = 0, we get ..\7 1.46577. By the Perron-Frobenius Theorem and Lemma 0, we produce the lower bound L 2:: ..\7 Let :z:0 = 0. Given the equation :z:;+1 = /(:vi) where /(:v) = 1l:vl..\7, we have 14

PAGE 23

the following: :co= 0 :c1 =/(:co)= 1 :c2 = /(:ct) = 1Ar :c3 = /(:c2) = 1 + Ar-Ar2 :c4 = f(:cJ) = 1Ar-Ar2 + Ar3 :cs = f(:c4) = 1Ar + Ar2 + A7 3 -A/ :cs = f(:cs) = 1Ar + Al-Al-Ar4 + A7 5 :cr = /(:cs) = 1Ar +_Al-Ar3 + Ar4 + Ar5 -A7 6 = 0. Since :c0 = :c7 we have a period seven solution. As for B3 and B5 we see B7 = inf L(f) = A7 Hence, the bound is exact. 0 !El'R1 2 Odd Periods For this section, assume p > 1 is an odd number. Recall, by Lemma 4, that if :Ci+I = has a period p solution but no lower order odd period solutions, then there is a period p solution of :Ci+I = f(:c;) whose members are in a certain order. This allows us to consider only one (out of p!f2p) ordering. With this in mind, let us now consider the general odd case, beginning with the following lemma: Lemma 5: Let :c1 :c2 ... :Cp be a periodic solution of :Ci+I = f(:c;). Let r and f be (p -1 )-vectors with: ifi = 1 andfi = { j(:c2)-f(:ct) ifi = 1 ifi > 1, (-1)'(/(:ci+I)-/(:ci-d) ifi > 1. 15

PAGE 24

Then if i = 1 ifi=p-1 otherwise { r1 + r2 if i = 1 } = r1 + r3 + + rp-4 -rp-2 if i = p-1 = (Apr)i D ri+I otherwise. Lemma 6: Let Pp(t) = tP -2tP-2 1, and let tp be the largest root of Pp(t). Then 1. Det(tiAp) = Pp(t)j(t + 1) 2. lim Pp(t) = oo !-.oo 5. t3 > ts > t7 > ... > t. 16

PAGE 25

Proof: 1. Cofactor expansion along the bottom row of ti Ap results in submatrices with only one nonzero permutation. Then: (p-5)/2 Det(tl-Ap) = (t-1)tP-2 -1-t(t-1) L t2i i=O = (t1)tp-:i1-(t-1)(t)-(t-1)t3 -(t-1)tP-4 = (t-1)tP-2 -1-(t-1)(t)(1 + t 2 + ... + tP-5 ) tp-J1 = (t-1)tP-2 -1-(t--1-tP-2tP-2 -1 -t+1 2. Note that p > 1. Hence, the limit follows. 3. Since Pp( .J2) = -1 then there exists a tp > v'21 with f(t) = 0 by (2) and the Intermediate Value Theorem. 5. Since Pp_2(tp_2 ) = 0, then the proof follows from (2), (4), and the Intermediate Value Theorem. 6. By definition, Pp(tp) = 0 implies 1 = 0. Dividing both sides of this equation by and solving for tv, we get tv = .;2 + (By (3), note that tp > .J2.) We may now see that as p -+ oo, tp -+ .J2. D 17

PAGE 26

Theorem 8: B, = t,. In other words, if Xi+ I = f( xi) has a period p solution, then L(f) t, and this is exact. Table 1 gives B, for p = 3, 5, 7, 9, 11, 13, 15. Proof: Suppose Xi+l = /(xi) has a period q solution where q < p and q = 3, 5, ... ,p-2. By induction, and using Corollary 1, we have L(f) Bq = tq > t,. Otherwise, Lemma 4 gives that either Xi+l = f(xi) has a period p solution with Xp-I < x,_3 < < xo < xi < x3 < < Xp-2 Then r is a positive vector. Forming the matrix A, from the Lipschitz conditions, A, is nonnegative and irreducible. Therefore, the Perron Frobenius Theorem shows us that t, is the largest eigenvalue of A,; it also promises a positive vector y such that yT A, = t,yr. Using this fact and Lemma 5, we have Since y and r are positive vectors, yT r > 0. Simplifying gives L tv. Consider fv(x) = 1t,ixl. Then L(f) = t,. If Xo = 0, Xi+I = fv(xi) implies XI = 1, and fori E Z[2,p], Xi = -Pi(tv)ft,, where Pi(t) = ti-2ti-2 + ( -1)i. Since x, = x0 this is a period p solution. So Bv = t,. 0 NOTE: The period p solution given above is unstable. In particular, if x0 = 0 is off from zero by a sufficiently small e > 0, then the solution becomes chaotic. Corollary 2: Let f be Lipschitz. If Xi+I = f(xi) has an odd period solution, then L(f) > J2. Proof: By condition (3} of Lemma 6, t, > J2. By condition (6) of Lemma 6, 18

PAGE 27

lim tp = .J2. Therefore, we may see that L(f) > tp > .J2. D p--+00 Period BP 3 1.61803399 5 1.51287640 7 1.46557123 9 1.44131548 11 1.4284227 13 1.42157334 15 1.41798197 17 1.41612620 19 1.41517853 00 v'2 Table 1: The maximal lower bounds Bp when pis odd 3 Even Periods For this section, assume p 2:: 2 is an even number. Table 2 gives the minimal Lipschitz constant off when p is even. To discuss the general solution of the minimal Lipschitz constant off when pis even, we shall consider two cases. For the first case, we investigate Bp when p = 2k, k = 1, 2, 3, .... In the second case we evaluate Bp when p = 2r k, r > 1. Theorem 9: Let p = 2\ k = 1, 2, 3, ... 1 and let f : !R ---+ !R be a Lipschitz function. If the recursion :ei+1 = f( zi) has a p-periodic solution for some :e0 then the Lipschitz constant off is at least one. Furthermore, this bound is sharp. 19

PAGE 28

PROOF: By Corollary 1 and Theorem 2, we know This establishes the lower bound B21< 1. To show that the bound is exact, we use Lemma 3 to obtain Combining these relationships with the inequality above, we easily come to the conclusion that B3 2i -+ 1. Note that B21< 1 and ::; B3 2i for all j and k. By a sandwiching argument, B21< = 1. D For p = 2kr, r > 1, Lemma 3 establishes the lower bound. The bound for p = 2kr can be shown to be exact by considering fp(:c) = 1 l:cl, where a period p solution exists. Theorem 10 shows that these statements are always true. Lemma 7: Let g : lR -+ lR be a Lipschitz function, where g( :c) = 1 A I :c I For a: > 0, if the recursion :ci+1 = f(:ci) has a p-periodic solution, then h(:c) = o:-AI:cl does also. PROOF: Let :Cn+l = g(:cn), and let Yn = O::Cn. Then Theorem 10: Let 1 < A < 2. If a::n+l = 1 Aa::n has a p-periodic solution, then a::n+ 1 = 1 VAa::n has a 2p-periodic solution. 20

PAGE 29

PROOF: Let /(z) = 1v'Xi:cl. Let g(:c) = f o f(:c) = 1 v1 + Ai:cl for l:cl :s; .JX1. Let :Cn+I = g(:cn) with :co = 0. By induction, prove that l:z:il :s; .JX1 for all i: The base case for i = 0 is trivial. For i > 0, assume l:z:i+II :s; .JX1. Then, = (v'>: -1)(;\ -1) :s; vx -1. Due to the absolute value, we must also show that :Z:i :2: .JX -1. Therefore, for i > 0, :Z:i :2: 1v'X+ Alzi-11 The smallest value :Vi-I is equal to is zero. Therefore, :Vi :2: 1 ;\. Hence, we have shown l:cil :s; JX1. D Consider the example: Let /(a:) = 1y;x;l:z: I, where ;\3 = 1 +2 J5 1.618. Then, :z:o = 0 :Z:4 0.007926 zs -0.002156 Z12 0.005183 :Z:16 0.001332 :1:20 0.006231 :Z:24 = 0. .:z:l = 1 :z:s 0.991583 :Cg 0.997711 :Z:lJ 0.994495 :Z:17 0.998585 :1:21 0.993383 :z:2 -0.061997 :z:s -0.053059 :ClQ -0.59566 :CJ4 -0.056151 :c1s -0.060495 :z:22 -0.054970 :Z:J 0.934159 :Z:7 0.943652 :z:u 0.936741 :c1s 0.940367 Z19 0.935755 :Z:2J 0.941622 By the a:iterates listed above, /(a:) has a period 24 solution. Now, given g(:z:o) = /8(:z:o) = f(:v7) = :t:a g(:va) = JB(a:a) = /(:z:Is) = :t:1s g(:z:Is = JB(:cJs) = /(:c23) = :t:24 =:co. 21

PAGE 30

We can see that g = f8 cohtains a 3-periodic solution. If we also define h = r' il from the table of :z:-iterates we can see that h contains a 6-periodic solution. !I Period i\ 4 6 8 10 12 14 16 18 20 00 \I il 1 1 1.27201965 1 1.22999041 :::::: 1.12783849 1.21060780 1 1.20054 799 1.10904932 J[11 for p = 2k 111 for p = 2kr,r > 1 and odd !I Table 2: The lower bounds Bp when p is even 22

PAGE 31

4 Summary B4sB24 B2 = B4 = B8 = = 1 Figure 4: Bounds for the Lipschitz Constant B J-2 1.618 The major results of this paper are summarized as follows: Let f : --t be a Lipschitz function on the real line with constant L so that for some :z:0 the recursion :z:;+l = /(:z:;) has a period p solution (:z:p = :z:0). Let Bp be the largest number such that L 2: Bp for all such f. Then, for even p = 2kr where p =I 2\ k = 1, 2, 3, ... Bp = Br 2-". For even p = 2k, Bp = 1. tP-2tP-2 -1 For odd p, Bp is the largest root of Pp( t) = Furthermore, there t+l exists a function f with Lipschitz constant Bp such that the recursion :z:;+1 = f(:z:i) has a p-periodic solution. 23

PAGE 32

5 References 1. Fisher, David C., private communication. 2. Fisher, D., R. Lee, and E. Knowles, "Iff Has Lipschitz Constant Less than 2.17008, Then :Z:i+l = :Z:i + f(:z:i) Has No Odd Periodic Solutions," Journal of Mathematical Analysis and Applications, 160 (1991) 459-467. 3. Ho, C.W., and C. Morris, "A Graph Theoretic Proof of Sharkovsky's The orem on the Periodic Points of Continuous Functions," Pacific Journal of Mathematics, 96 {1981) 361-370. 4. Leon, S., Linear Algebra with Applications, 2nd Ed. Macmillan Publishing Co. (1980) 295. 5. Li, T.-Y., and J. York, "Period Three Implies Chaos," Amer. Math. Monthly, 16 (1964) 985-992. 6. Sharkovsky, A.N., "Coexistence of Cycles of a Continuous Mapping of the Real Line into Itself," Ukrainskii Matematiceskii Zurnal, 16 (1964) 61-71. 7. Straflin, P.D., "Periodic Points of Continuous Functions," Mathematics Magazine, 51 (1978) 99-105. 24