A TOEPLITZ-TYPE THEOREM FOR PATHS
Let M be a Lozenge algorithm of the form s = Y μ, (η) s and let η L n k,m n+m m = 0 ' IP = P(n,k) be a path. M is called regular along IP if lim s = λ implies m*» fkl lim s ' = λ. Wimp has given sufficient conditions for M to be regular. Ρ n Here we sharpen these conditions and show that our conditions are also necessary. AMS 40AO5 65B99 A Lozenge, or Lozenge algorithm, is a map from a sequence s into a fkl countable set of sequences {s }. We consider here, as is common in numerici cal analysis, the case where the terms of s are given by. = y μ, (n) s n L . k,m n+m m=0 for n > 0 and k > 0. We shall denote this transform by M. It is also allowed that μ^ m(n) may depend on the sequence s. For example, one of the most popular and useful transforms in numerical analysis is the Levin transform given by . ,. k-6 . .. m, -1 ,k. , .. (n + m + 1) (-1) fa ,1 ( ) μ. in) = ' y ' K n+m+1 ν κ, m —^ Y ( n + m + l) "(-l)(a J ' V ) ' n+m+1' V m=0 6 = -2 or -1 and a = s s η η η-1 Supported in part by the Natural Sciences and Engineering Research Council of Canada. 106 Shawyer Let IP = F ( n , k ) be a p a t h . That i s , η = n ( j ) , k = k ( j ) with j ä 0, n(0) = k(0) = 0, n ( j + 1) ^ n ( j ) , k ( j + 1) ^ k ( j ) and e i t h e r n ( j + 1) = 1 + n ( j ) or k ( j +1) = 1 + k ( j ) (or b o t h ) . C l e a r l y n + k-*·» as j •*• . See, f o r example [1 ] , P· 3. Let { t n be any (double) sequence. I f lim t ^ j ) k ( j ) = τ , we say t h a t t , τ along ff and w r i t e lim t , = τ . n ,k 6 p n , k The t r ans fo rm M i s c a l l e d linear along IP i f k (1) lim I ν (n) = 1. Ρ m=0 k ' m To see t h i s , l e t t = s + λ . Then η η = l μ. (η) t = s ( k ) + λ I μ. (η) . tj V τη ν ' mm -η *-> V m ν ' t ( k ) m=0 " k ' m V , V ' " m=0 " k ' m V Thus lim ( t ( k ) , W ) = λ lim l μ. = λ = lim ( t s ) . _ η η τ. η _ η η ' Ρ Ρ m=0 ' η-*" The transfoiTTi Μ i s c a l l e d regular along IP for s i f lim s « = X whenever lim s = λ. Ρ η η We prove the fo l lowing improvement of theorem 5 . 2 . 1 of [ 1 ] . THEOREM 1. Suppose that M is linear along IP. Then M is regular along IP for s if both conditions (2) and (3) are satisfied. (2) There e x i s t s a cons tan t H, independent of η and k such t h a t k,m k l |μν m(n) I £ H on P . m=0 (3) I f IP i s such t h a t η -ht h e n , f o r each m, lim μ, (η) = 0. ρ K> PROOF. Since M i s l i n e a r along IP, we may assume t h a t s n 0 as η . We then w r i t e s ( k ) = I μ, (η) s m=0 k ' m n + m j k Τ μ, (η) s + y μ. (η) s L n k,m 1 n+m r . k ,n r ' n+m m=0 ' m=j+l ' A Toeplitz-Type Theorem For Paths 107 Using condition (2), we have I °2 I á H sup IsJ. i>n+j We also have '°1 ' á (.1 Κ , » 0 0 ' ) ?»P lsil· lj=0 ' ' i>n Suppose that IP is such that η ->• 00. Then we have lim sup |s.I = 0 for each j > 0. ir*» i>n+j fkl It now follows that lim s =0. Ρ n Suppose then that IP is such that η does not tend to infinity. Thus η is bounded above, and eventually constant. We then have that Ρ is such that k ». Given any positive ε, we choose j such that sup Is.I < ε. iaj Thus j er I < εΗ. i Now, £ Iyk m(n)I is a finite sum and condition (3) guarantees that each m=0 ' term of the sum tends to zero along P. Since s is a convergent sequence, we have that sup |s. | is uniformly bounded in j. Thus lim σ. =0 and so i>j 1 Ρ 1 lim S M = 0. Ρ n Wimp states in [1], p. 106, that his theorem (which is included in theorem 1 above) is "an analog of the Toeplitz limit theorem" and "holds one way for certain non-linear algorithms". We shall show below that conditions (1), (2) and (3) are, in essence, also necessary. Let s = ε = {1,1,1,...}. Then s ^ = \ μ m(n) . If M is regular n m=0 ' along Ρ for ε, then it is necessary that condition (1) be satisfied. Let s = δ·1. That is, let δ"1 = 1 if η = i and δ3 = 0 if η φ i. Then η η sCk) = K , j n TM if J * η n I 0 if j < η i fkl If M is regular along ff for δ , then we have lim s1 ' = 0. Ρ n 1 0 8 Shawyer If IP is such that η -*• <*>, then we must eventually have η > j and so there is no restriction on M. If IP is such that η -h* 00, then we must have k 00 and η bounded. If j ^ n, then we must have lim P, . = 0 . je*» fc.J-n If M is regular along IP for all δ·*, then it is necessary that condition (3) holds. Suppose now that M is regular along F for all convergent sequences. We write fkl k s = Ι μ, (η) s = F μ, .s., say . m=0 k' m n + m j =0 k'n'J J fkl Let Ν = η +k and let σ., = s . As η and k increase along Ρ , Ν does not Ν η necessarily assume every integer value. However at any stage, Ν may increase by at have by at most 2. If Ν does not take the value p, we define σ = σ We then Ρ Ρ"1 Ν σ Ν = .[0 ""j ,Ν V S a y· We have that σ^ λ whenever s^ -»· λ. By the Toeplitz limit theorem, we have that there exists a constant H, independent of N, such that Ν I k Nl 5 Η j=0 and this implies condition (2). Collecting these results, we obtain THEOREM 2. If M is regular along Ρ for all convergent sequences, then conditions (1)* (2) and (3) are necessarily satisfied. We should also like to point out that for a given lozenge M and a given fkl path P, the limit lim s = λ is the same as lim (As). = λ, where A is the Ρ n j-*» 3 sequence-to-sequence transformation whose j-th term is given by (As). = s ^ ^ = ψ μ,,.. (n(j)) s 3 η (j) k(j ),ii n(j)+m This transformation A is represented by the matrix (a. .): 1 > 3 a. . J »1 0, if i < n(j) , Pk(j))n(j)_i(n(j)), if n(j) s χ < n(j) + k(j), 0, if i > n(j) + k(j) . A Toeplitz-Type Theorem For Paths 109 This shows that for a given path, we in fact have that this complicated transform reduces to a manageable sequence-to-sequence transformation.