Effective results on nonlinear ergodic averages in CAT(κ) spaces

Effective results on nonlinear ergodic averages in CAT(κ) spaces Laurent¸iu Leu¸stean1,2, Adriana Nicolae3,4 1Faculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, P.O. Box 010014, Bucharest, Romania 2Simion Stoilow Institute of Mathematics of the Romanian Academy, P. O. Box 1-764, RO-014700 Bucharest, Romania 3Department of Mathematics, Babe¸s-Bolyai University, Kog˘alniceanu 1, 400084 Cluj-Napoca, Romania 4Simion Stoilow Institute of Mathematics of the Romanian Academy, Research group of the project PD-3-0152, P. O. Box 1-764, RO-014700 Bucharest, Romania E-mails: Lauren[email protected], [email protected]cluj.ro Abstract In this paper we apply proof mining techniques to compute, in the setting of CAT(κ) spaces (with κ > 0), effective and highly uniform rates of asymptotic regularity and metastability for a nonlinear generalization of the ergodic averages, known as the Halpern iteration. In this way, we obtain a uniform quantitative version of a nonlinear extension of the classical von Neumann mean ergodic theorem. MSC: 47H25, 03F10, 47J25, 47H09. Keywords: Proof mining, nonlinear ergodic averages, CAT(κ) spaces, rates of metastabilty, Halpern iteration, asymptotic regularity. 1 Introduction In this paper we apply methods from mathematical logic to obtain a uniform quantitative version of a generalization of the classical von Neumann mean ergodic theorem, giving effective rates of metastability for the so-called Halpern iteration, a nonlinear generalization of the ergodic averages. Our results are a contribution to the line of research known as proof mining, initiated in the 50’s by Kreisel under the name of unwinding of proofs and extensively developed 1 arXiv:1305.5916v3 [math.FA] 3 Mar 2015 by Kohlenbach, beginning with the 90’s. The idea of this research direction is to extract new, effective information from mathematical proofs making use of ineffective principles. Hence, it can be related to Terence Tao’s proposal [32] of hard analysis, based on finitary arguments, instead of the infinitary ones from soft analysis. Proof mining has already been applied in approximation theory, nonlinear analysis, ergodic theory, topological dynamics and Ramsey theory. Related to these applications, general logical metatheorems were proved, having the following form: if certain statements satisfying general logical conditions (e.g. ∀∃-sentences) are proved in some formal system associated to an abstract space, then uniform finitary versions of these statements are guaranteed to hold and, furthermore, one can transform the initial proof into a quantitative one for the finitary version and, in this way, extract effective uniform bounds. We refer to Kohlenbach’s book [11] for an introduction to proof mining. Our theorems guarantee under general logical conditions such strong uniform versions of non-uniform existence statements. Moreover, they provide algorithms for actually extracting effective uniform bounds and transforming the original proof into one for the stronger uniformity result. Let us recall the Hilbert space formulation of the celebrated von Neumann mean ergodic theorem. Theorem 1.1. Let Hbe a Hilbert space and U:H→Hbe a unitary operator. Then for all x∈H, the Ces`aro mean xn=1 nPn−1 i=0 Uixconverges strongly to the projection of xonto the set of fixed points of U. If X= (X, B, µ, T) is a probability measure-preserving system, H=L2(X) and U=UT:L2(X)→L2(X), f 7→ f◦Tis the induced operator, the Ces`aro mean starting with f∈L2(X) becomes the ergodic average Anf=1 nPn−1 i=0 f◦Ti. The convergence of the ergodic averages can be arbitrarily slow, as shown by Krengel [22]. Furthermore, one cannot expect, in general, to get effective rates of convergence for the ergodic averages. Avigad, Gerhardy and Towsner [1] applied methods of computable analysis on Hilbert spaces to obtain an example of a computable Lebesgue measure-preserving transformation Ton [0,1] and a computable characteristic function χAsuch that the limit of the sequence AnχAis not a computable element of L2([0,1]), which implies that there is no computable bound on the rate of convergence of (AnχA). However, one can consider the following equivalent reformulation of the Cauchy property of (xn): ∀k∈N∀g:N→N∃N∀i, j ∈[N, N +g(N)] kxi−xjk<2−k.(1) This is known in logic as Kreisel’s [20,21] no-counterexample interpretation of the Cauchy property and it was popularized in the last years under the name of metastability by Tao [32,33]. In [33], Tao generalized the mean ergodic theorem for multiple commuting measure-preserving transformations, by deducing it from a finitary norm convergence result, expressed in terms of metastability. Recently, Walsh [34] used again metastability to show the L2-convergence of multiple polynomial ergodic averages arising from nilpotent groups of measurepreserving transformations. 2 Logical metatheorems developed by Kohlenbach [13] show that, from wide classes of mathematical proofs one can extract effective bounds on ∃Nin (1). Thus, taking ε > 0 instead of 2−k, we define a rate of metastability as a functional Φ : (0,∞)×NN→Nsatisfying ∀ε > 0∀g:N→N∃N≤Φ(ε, g)∀i, j ∈[N, N +g(N)] (kxi−xjk< ε).(2) Thus, a natural direction of research is to obtain finitary, quantitative versions of convergence statements for sequences (xn) by providing effective rates of metastability. A qualitative feature of these quantitative versions is that the rates of metastability are highly uniform and independent or have only a weak dependence on the input data. Furthermore, these quantitative versions can be thereafter generalized to new structures, obtaining as an immediate consequence the generalization of the initial (non-quantitative) Cauchy statement to these structures. The main quantitative result of this paper is obtained in this way. We refer to [15] for another example in the context of the asymptotic behaviour of nonlinear iterations. Avigad, Gerhardy and Towsner [1] computed for the first time explicit and uniform rates of metastability for the ergodic averages, by a logical analysis of Riesz’ proof of the mean ergodic theorem. Their result was generalized, with better bounds, to uniformly convex Banach spaces by Kohlenbach and the first author [14], applying proof mining methods, but this time to a proof of Garrett Birkhoff [3]. In fact, Avigad and Rute [2] realized that the computations in [16] allow one to obtain an effective bound on the number of ε-fluctuations (i.e. pairs (i, j) with i>jand kxi−xjk> ε). A very nice discussion on the different types of quantitative information (metastability, effective learnability, bounds on the number of oscillations) that can be extracted from convergence proofs is done in a recent paper by Kohlenbach and Safarik [19]. In the important paper [35], Wittmann obtained the following nonlinear generalization of the mean ergodic theorem. Theorem 1.2. [35] Let Cbe a bounded closed convex subset of a Hilbert space X,T:C→Ca nonexpansive mapping and (λn)n≥1a sequence in [0,1]. For any u∈C, define x0=u, xn+1 =λn+1u+ (1 −λn+1)Txn.(3) Assume that (λn)satisfies lim n→∞λn= 0,∞ X n=1 |λn+1 −λn|<∞and ∞ X n=1 λn=∞(4) Then for any u∈C,(xn)converges to the projection PF ix(T)uof uonto the (nonempty) set of fixed points F ix(T). One can easily see that (xn) coincides with the Ces`aro mean when Tis linear and λn=1 n+ 1. The iteration (xn) is known as the Halpern iteration, as it was 3 introduced by Halpern [9] for the special case u= 0. We refer to [17, Section 3] for a discussion on results in the literature on Halpern iterations, obtained by considering different conditions on (λn) or more general spaces. Kohlenbach’s logical metatheorem for Hilbert spaces [13] guarantees also in the case of Wittmann’s theorem that from its proof one can extract a rate of metastability Φ of (xn), uniform in the following sense: it depends only on ε and g, an upper bound on the diameter of Cand moduli on (λn), given by the quantitative version of (4). Thus, Φ is independent with respect to the starting point uof the iteration, the nonexpansive mapping T, the Hilbert space Xand depends on Conly via its diameter. Kohlenbach [12] computed such a uniform rate of metastability by a logical analysis of Wittmann’s proof. Furthermore, Kohlenbach and the first author [16,17,18] extracted rates of metastability from the proofs of two generalizations of Wittmann’s theorem given by Shioji and Takahashi [31] for a class of Banach spaces with a uniformly Gˆateaux differentiable norm and by Saejung [29] for CAT(0) spaces. Both Saejung’s and Shioji-Takahashi’s proofs use Banach limits (whose existence requires the axiom of choice), inspired by Lorentz’ seminal paper [25], introducing almost convergence. Our quantitative results were obtained by developing in [17] a method to eliminate the use of Banach limits from these proofs and get, in this way, elementary proofs to which general logical metatheorems for CAT(0) spaces [13] and for uniformly smooth Banach spaces [16] can be applied to guarantee the extractability of effective bounds. We point out that the use of Lorentz’ almost convergence (and hence, Banach limits) in nonlinear ergodic theory was introduced by Reich [27], while Bruck and Reich [7] applied Banach limits for the first time to the study of Halpern iterations (see also [8, Sections 12, 14]). Geodesic spaces provide a suitable setting for extending the notion of sectional curvature from Riemannian manifolds. An important class of geodesic spaces of bounded curvature are CAT(κ) spaces, where geodesic triangles are in some sense “thin”. Such spaces enjoy nice properties inherited from the comparison with the model spaces and proved to be relevant in various problems and aspects in geometry (see [4]). Recently, Pi¸atek [26] extended Wittmann’s result to the context of CAT(κ) spaces with κ > 0. In this paper we extract an effective and uniform rate of metastability for this generalization of Wittmann’s theorem. Our main quantitative result (Theorem 3.4) is obtained by generalizing to CAT(κ) spaces the quantitative proof for CAT(0) spaces from [17]. Thus, we apply again the general method developed in [17], together with the remark that, in fact, our logical analysis of Saejung’s proof for CAT(0) spaces results in the elimination of any contribution of Banach limits, hence even the finitary lemmas proved in [17, Section 8] are no longer needed (see [18]). Despite this simplification, the proofs we give in this paper are much more involved, since we work in the setting of CAT(κ) spaces. However, we still get a rate of metastability having a form similar to the one described in [19]. As the first step in the convergence proof is to obtain the asymptotic regularity, our first important result (Proposition 3.2) consists in the computation of a uniform rate of asymptotic regularity. 4 For the rest of the paper N={0,1,2, . . .}and Z+={1,2, . . .}. Furthermore, we consider CAT(κ)spaces with κ > 0. 2 CAT(κ)spaces Let (X, d) be a metric space. A geodesic path from xto yis a mapping c: [0, l]⊆R→Xsuch that c(0) = x, c(l) = yand d(c(t), c(t0)) = |t−t0|for every t, t0∈[0, l]. The image c([0, l]) of cforms a geodesic segment which joins xand y. Note that a geodesic segment from xto yis not necessarily unique. If no confusion arises, we use [x, y] to denote a geodesic segment joining xand y. (X, d) is called a (uniquely) geodesic space if every two points x, y ∈Xcan be joined by a (unique) geodesic path. A point z∈Xbelongs to the geodesic segment [x, y] if and only if there exists t∈[0,1] such that d(z, x) = td(x, y) and d(z, y) = (1 −t)d(x, y), and we write z= (1 −t)x+ty for simplicity. This, too, may not be unique. A subset Cof Xis convex if Ccontains any geodesic segment that joins every two points in C. A geodesic triangle ∆(x1, x2, x3) consists of three points x1, x2and x3in X(its vertices) and three geodesic segments corresponding to each pair of points (its edges). CAT(κ) spaces are defined in terms of comparisons with the model spaces Mn κ. We focus here on CAT(κ) spaces with κ > 0. We give below the precise definition and briefly describe some of their properties that play an essential role in this work. For a detailed discussion on geodesic metric spaces and, in particular, on CAT(κ) spaces, one may check, for example, [4]. The n-dimensional sphere Snis the set {x∈Rn+1 : (x|x)=1}, where (· | ·) stands for the Euclidean scalar product. Consider the mapping d:Sn×Sn→R by assigning to each (x, y)∈Sn×Snthe unique number d(x, y)∈[0, π] such that cos d(x, y)=(x|y). Then, (Sn, d) is a metric space called the spherical space. This space is also geodesic and, if d(x, y)< π, then there exists a unique geodesic segment joining xand y. Moreover, open (resp. closed) balls of radius ≤π/2 (resp. < π/2) are convex. The spherical law of cosines states that in a spherical triangle with vertices x, y, z ∈Snand γthe spherical angle between the geodesic segments [x, y] and [x, z] we have cos d(y, z) = cos d(x, y) cos d(x, z) + sin d(x, y) sin d(x, z) cos γ. Let κ > 0 and n∈N. The classical model spaces Mn κare obtained from the spherical space Snby multiplying the spherical distance with 1/√κ. These spaces inherit the geometrical properties from the spherical space. Thus, there is a unique geodesic path joining x, y ∈Mn κif and only if d(x, y)< π/√κ. Furthermore, closed balls of radius < π/(2√κ) are convex and we have a counterpart of the spherical law of cosines. We denote the diameter of Mn κby Dκ=π/√κ. For a geodesic triangle ∆=∆(x1, x2, x3), a κ-comparison triangle is a triangle ¯ ∆ = ∆(¯x1,¯x2,¯x3) in M2 κsuch that d(xi, xj) = dM2 κ(¯xi,¯xj) for i, j ∈ {1,2,3}. For κfixed, κ-comparison triangles of geodesic triangles (having perimeter less than 2Dκ) always exist and are unique up to isometry. 5 A geodesic triangle ∆ of perimeter less than 2Dκsatisfies the CAT(κ)inequality if for every κ-comparison triangle ¯ ∆ of ∆ and for every x, y ∈∆ we have d(x, y)≤dM2 κ(¯x, ¯y), where ¯x, ¯y∈¯ ∆ are the comparison points of xand y, i.e., if x= (1 −t)xi+txj then ¯x= (1 −t)¯xi+t¯xjfor i, j ∈ {1,2,3}. A metric space is called a CAT(κ)space if every two points at distance less than Dκcan be joined by a geodesic segment and every geodesic triangle having perimeter less than 2Dκsatisfies the CAT(κ) inequality. CAT(0) spaces are defined in a similar way considering the model space M2 0to be the Euclidean plane of infinite diameter. 3 Main results Let (X, d) be a geodesic space, C⊆Xa convex subset, T:C→Ca nonexpansive mapping and (λn) a sequence in [0,1]. The Halpern iteration starting at u∈Ccan be defined by x0=u, xn+1 =λn+1u+ (1 −λn+1)Txn.(5) The main purpose of our work is to prove a quantitative version of the following generalization of Wittmann’s theorem to CAT(κ) spaces, obtained recently by Pi¸atek [26]. Theorem 3.1. Let Xbe a complete CAT(κ)space, C⊆Xa bounded closed convex subset with diameter dC<Dκ 2and T:C→Ca nonexpansive mapping. Assume that (λn)satisfies (4). Then for any u∈C, the iteration (xn)starting from uconverges to the fixed point of Twhich is nearest to u. A first important result of this paper is the extraction of an effective rate of asymptotic regularity for the Halpern iteration, that is, a rate of the convergence of (d(xn, Txn)) towards 0. In order to state this result, we need to make the hypotheses (4) on (λn) quantitative. For brevity, we say that the sequence (λn) and the functions α: (0,∞)→ Z+,γ: (0,∞)→Z+and θ:Z+→Z+satisfy (*) if the following conditions hold: (i) lim n→∞λn+1 = 0 with rate of convergence α, i.e., λn+1 ≤ε, for all ε > 0 and all n≥α(ε); (ii) ∞ X n=1 |λn+1 −λn|converges with Cauchy modulus γ, i.e., γ(ε)+n X i=γ(ε)+1 |λi+1 −λi| ≤ ε, for all ε > 0 and all n∈Z+; 6 (iii) ∞ X n=1 λn+1 =∞with rate of divergence θ, i.e., θ(n) X k=1 λk+1 ≥n, for all n∈Z+. Proposition 3.2. Let Xbe a CAT(κ)space, C⊆Xa bounded convex subset, T:C→Cnonexpansive and M < Dκ 2an upper bound on the finite diameter dCof C. Assume furthermore that (λn), α, γ, θ satisfy (*). Then lim n→∞d(xn, xn+1)=0with rate of convergence ˜ Φgiven by ˜ Φ(ε, κ, M, γ, θ) = θ 1 cos(M√κ)γε 2M+ max ln 2M ε,1(6) and lim n→∞d(xn, Txn)=0with rate of convergence Φgiven by Φ(ε, κ, M, γ, θ, α) = max n˜ Φε 2, κ, M, γ, θ, α ε 2Mo.(7) Proof. See Section 5. If λn=1 n+ 1 one can easily obtain rates α, γ, θ: α(ε) = γ(ε) = 1 ε, θ(n) = exp ((n+ 1) ln 4) .(8) As an immediate consequence we get the following: Corollary 3.3. Assume that λn=1 n+ 1, n ≥1. Then lim n→∞d(xn, xn+1) = lim n→∞d(xn, Txn)=0 with a common rate of convergence Ψ(ε, κ, M) = exp  1 cos(M√κ)8M ε+ 2ln 4,(9) which is exponential in 1 ε. We point out that exponential rates of asymptotic regularity for the Halpern iteration were obtained by the first author for Banach spaces in [23] and for the so-called W-hyperbolic spaces in [24]. Kohlenbach [12] remarked that the proof in [23] can be simplified and, as a consequence, one gets quadratic rates in Banach spaces. For CAT(0) spaces, Kohlenbach and the first author provide in [17] a quantitative asymptotic regularity result for general (λn) by considering 7 instead of ∞ X n=1 λn+1 =∞the equivalent condition ∞ Y n=1 (1 −λn+1) = 0. As a corollary, one obtains again quadratic rates of asymptotic regularity. However, the method used in [17] for CAT(0) spaces does not hold for CAT(κ) spaces. The main result of the paper is the following quantitative version of Theorem 3.1, which provides an explicit uniform rate of metastability for the Halpern iteration in CAT(κ) spaces. To get such a result we apply again the general method developed by Kohlenbach and the first author in [17] for the Halpern iteration in CAT(0) spaces and applied again in [16] for uniformly smooth Banach spaces as well as in [30] for a modified Halpern iteration in CAT(0) spaces. As noticed in [18], in the end we do not need the finitary Lemmas 8.3 and 8.4 from [17], since, as a consequence of the proof mining methods applied to Saejung’s proofs, one gets a proof where no contributions of Banach limits can be traced. Theorem 3.4. Let Xbe a complete CAT(κ)space, C⊆Xa bounded closed convex subset, T:C→Cnonexpansive and M < Dκ 2an upper bound on the finite diameter dCof C. Assume furthermore that (λn), α, γ, θ satisfy (*). Then for all ε∈(0,2) and g:N→N, ∃N≤Σ(ε, g, κ, M, θ, α, γ)∀m, n ∈[N, N +g(N)] (d(xn, xm)≤ε), with N= ΘK0sin2ε√κ 4for some 1 ε0≤K0≤f f∗Bε,κ,M (0) + 1 ε0and Σ(ε, g, κ, M, θ, α, γ) = Aε,κ,M,θ,α,γ f f∗Bε,κ,M (0) + 1 ε0, where the above constants and functionals are specified in Table 1. Proof. We refer to Section 7for the proof. We point here only the main steps: (i) extract a rate of asymptotic regularity (this is done in Proposition 3.2); (ii) obtain a quantitative Browder theorem (see Proposition 6.2); (iii) define in an appropriate way an approximate fixed point sequence γt n(see (25)); (iv) apply Lemma 7.3, a quantitative lemma on sequences of real numbers. Hence, we compute a rate of metastability which is uniform in the starting point x0of the iteration and the nonexpansive mapping T. Moreover, it depends on the space Xand the set Conly via κand the diameter dCof C. The dependence on (λn) is through the rates α, γ, θ, which can be computed very easily for the natural choice λn=1 n+ 1. Furthermore, as in [16,17] as well as in other case studies in proof mining, the rate of metastability has the form described by Kohlenbach and Safarik [19]. 8 Bε,κ,M =M√κtan(M√κ) 1−cos(ε0), ε0=cos(M√κ) 36 sin2ε√κ 4, Aε,κ,M,θ,α,γ (n) = θ+ 1 cos(M√κ)(Γ(n)−1 + max {S, 1})+ 1, Γ(n) = max χ∗ i1 3sin2ε√κ 4:1 ε0≤i≤n, θ+(n) = max 1≤i≤nθ(i), S=&ln 3 sin2M√κ 4 sin2ε√κ 4!', χ∗ i(ε) = χiε 2cos(M√κ), Li=cos(M√κ)ε 4M√κ(i+ 1), χi(ε) = max θ 1 cos(M√κ)γ(Li) + max ln 1 Li,1, α(2Li), Θi(ε) = θ 1 cos(M√κ)χ∗ iε 3−1 + max {T, 1}+ 1, T=ln 3 εsin2M√κ 2,∆∗ i(ε, g) = ε 3Θi(ε)−3χ∗ i(ε 3)+3g(Θi(ε)), f(i) = max (& M√κ ∆∗ i(sin2ε√κ 4, g)', i)−i, f∗(i) = fi+1 ε0+1 ε0 and f f∗(i) = i+f∗(i). Table 1 Thus, gdoes not appear at all in the definition of the mappings Aε,κ,M,θ,α,γ and Bε,κ,M , and f f∗(i) only uses gon one argument, Θi(sin2(ε√κ/4)), which itself does not depend on g. We refer to [19] for a logical explanation of this phenomenon in terms of effective learnability and bounds on the number of mind changes. If λn=1 n+ 1, with α, γ, θ given by (8), one can easily see that (χ∗ i)iis nondecreasing. As a consequence we obtain the following: Corollary 3.5. Assume that λn=1 n+ 1 for all n≥1. Then for all ε∈(0,2) and g:N→N, ∃N≤Σ(ε, g, κ, M)∀m, n ∈[N, N +g(N)] (d(xn, xm)≤ε), 9 It follows that sin2d(y, v)√κ 2(1 −L1)≤L2sin2d(x, y)√κ 2+1 2(1 −L1−L2) +L1sin2d(y, q)√κ 2+1 2sin(d(y, q)√κ) ≤L2sin2d(x, y)√κ 2+1 2(1 −L1−L2) +L1sin2d(y, q)√κ 2+ sin d(y, q)√κ 2 ≤L2sin2d(x, y)√κ 2−1 2L2(1 −cos(d(x, v)√κ)) +L1sin2d(y, q)√κ 2+ sin d(y, q)√κ 2 by (16). Thus, sin2d(y, v)√κ 2≤L2 1−L1sin2d(x, y)√κ 2−sin2d(x, v)√κ 2 +L1 1−L1sin2d(y, q)√κ 2+ sin d(y, q)√κ 2. By assumption, we have that sin2d(x, y)√κ 2−sin2d(x, v)√κ 2≤0. Using the fact that L2 1−L1≥1 and (17), it follows that sin2d(y, v)√κ 2≤sin2d(x, y)√κ 2−sin2d(x, v)√κ 2 +1 scos(M√κ)sin2d(y, q)√κ 2+ sin d(y, q)√κ 2. 5 Effective rates of asymptotic regularity We assume the hypothesis of Proposition 3.2. As in [23,16,17], the main tool in obtaining rates of asymptotic regularity is the following quantitative lemma, which is a slight reformulation of [17, Lemma 1]. Lemma 5.1. Let (αn)n≥1be a sequence in [0,1] and (an)n≥1,(bn)n≥1be sequences in R+such that an+1 ≤(1 −αn+1)an+bnfor all n∈Z+.(19) 16 Assume that ∞ X n=1 bnis convergent with Cauchy modulus γand ∞ X n=1 αn+1 diverges with rate of divergence θ. Then, lim n→∞an= 0 with rate of convergence Σgiven by Σ(ε, P, γ, θ) = θγε 2+ max ln 2P ε,1+ 1,(20) where P > 0is an upper bound on (an). A second useful result, which is also needed in the metastability proof, is the following: Lemma 5.2. For all n≥1, let µn= 1 −sin ((1 −λn)M√κ) sin(M√κ)∈(0,1).(21) Then (i) µn≥λncos (M√κ)for all n≥1. (ii) ∞ X n=1 λn+1 =∞with rate of divergence θyields ∞ X n=1 µn+1 =∞with rate of divergence ˜ θ(n) = θ 1 cos(M√κ)n. Proof. (i) One has µn=2 sin λnM√κ 2cos (2−λn)M√κ 2 sin (M√κ)≥2 sin λnM√κ 2cos (M√κ) sin (M√κ) ≥λncos M√κ. (ii) Follows immediately from (i). Lemma 5.3. For all n∈Z+ d(xn, xn+1)≤(1 −µn+1)d(xn−1, xn) + M|λn+1 −λn|.(22) Proof. Let us denote for simplicity un=λn+1u+ (1 −λn+1)Txn−1. Then, d(xn, un) = |λn+1 −λn|d(u, Txn−1)≤M|λn+1 −λn|and d(un, xn+1)≤sin (1 −λn+1)M√κ sin M√κd(xn−1, xn) by Lemma 4.1. 17 5.1 Proof of Proposition 3.2 Let ˜ Φ, Φ be given by (6) and (7). Apply Lemma 5.1 with an=d(xn, xn−1), bn=M|λn+1 −λn|and αn=µn, and use Lemma 5.2.(ii) and the fact that ∞ X n=1 bnis convergent with Cauchy modulus ˜γ(ε) = γε Mto conclude that lim n→∞d(xn, xn+1) = 0 with rate of convergence ˜ Φ. Since d(xn, Txn)≤d(xn, xn+1) + Mλn+1 for all n≥1, it follows easily that Φ is a rate of asymptotic regularity.  6 A quantitative Browder theorem Let Xbe a complete CAT(κ) space, C⊆Xa bounded closed convex subset with diameter dC<Dκ 2and T:C→Cbe nonexpansive. A very important step in the convergence proof for Halpern iterations is the construction of a sequence of approximants converging strongly to a fixed point of T. Given t∈(0,1) and u∈C, Lemma 4.1 yields that the mapping Tu t:C→C, T u t(y) = tu + (1 −t)Ty (23) is a contraction, hence it has a unique fixed point zu t∈C. Thus, zu t=tu + (1 −t)Tzu t.(24) Pi¸atek [26] obtained the following generalization to CAT(κ) spaces of an essential result due to Browder [5,6]. Theorem 6.1. [26] In the above hypothesis, lim t→0+zu texists and is a fixed point of T. In the setting of Hilbert spaces, Browder proved the result using weak sequential compactness and a projection argument (to the set of fixed points of T). A new and elementary proof of Browder’s result was given by Halpern [9] when Cis the closed unit ball and the starting point is u= 0. Generalizations of Browder’s theorem were obtained by Reich [28] for uniformly smooth Banach spaces, Goebel and Reich [8] for the Hilbert ball and Kirk [10] for CAT(0) spaces. Kohlenbach [12] applied proof mining methods to both Browder’s original proof and the extension of Halpern’s proof to bounded closed convex Cand arbitrary u∈C, obtaining in this way quantitative versions of Browder’s theorem with uniform effective rates of metastability. As pointed out in [12, Remark 1.4], one cannot expect in general to get effective rates of convergence. Since Kirk’s 18 proof of the generalization of Browder’s theorem to CAT(0) spaces is obtained by a slight change of Halpern’s argument, Kohlenbach’s quantitative result goes through basically unchanged to CAT(0) spaces (see [17, Proposition 9.3]). In this section we obtain a quantitative version of Theorem 6.1. As a consequence of Halpern’s proof, for any nonincreasing sequence (tn) in (0,1), one gets that (zu tn) converges strongly to some point z∈C, which is a fixed point of Tif lim n→∞tn= 0. Our quantitative result gives rates of metastability for such sequences (zu tn) and this suffices for the proof of our main Theorem 3.4. Proposition 6.2. Let Xbe a complete CAT(κ)space, C⊆Xbounded closed convex with diameter dC<Dκ 2and T:C→Cbe nonexpansive. Assume that (tn)⊆(0,1) is nonincreasing. Then for every ε∈(0,1) and g:N→N, ∃K0≤K(ε, g, M)∀i, j ∈[K0, K0+g(K0)] d(zu ti, zu tj)≤ε √κ, where K(ε, g, M) = egM√κtan(M√κ) 1−cos ε(0), with dC≤M < Dκ 2and eg(n) = n+g(n). Proof. Let ε∈(0,1) and g:N→N. We assume without loss of generality that i<j, hence tj≤ti. Denote ui,j =tju+ (1 −tj)Tzu ti. Then, d(u, zu ti) = (1 −ti)d(u, T zu ti)≤(1 −tj)d(u, Tzu ti) = d(u, ui,j), so zu ti∈[u, ui,j]. It follows by Lemma 4.1 that d(zu tj, ui,j)≤d(Tzu tj, Tzu ti)≤ d(zu tj, zu ti). We can apply now Lemma 4.2 with x=u, y =zu tj, z =ui,j , w =zu tito get that d(u, zu ti)≤d(u, zu tj) and for ∆(¯u, ¯zu tj,¯ui,j ) a κ-comparison triangle of ∆(u, zu tj, ui,j), one has ∠¯zu ti(¯u, ¯zu tj)≥π/2. Since (d(u, zu tn))nis a nondecreasing sequence in [0, M], by an application of [12, Lemma 4.1], there exists K0≤ K(ε, g, M) such that ∀i, j ∈[K0, K0+g(K0)] |d(u, zu tj)−d(u, zu ti)| ≤ 1−cos ε √κtan(M√κ). Let now i<j∈[K0, K0+g(K0)]. Then, cos(d(u, zu ti)√κ)−cos(d(u, zu tj)√κ)≤sin(M√κ)1−cos ε tan(M√κ) = (1 −cos ε) cos(M√κ). Furthermore, by the cosine law and the fact that ∠¯zu ti(¯u, ¯zu tj)≥π 2, we have that cos(d(¯u, ¯zu tj)√κ)≤cos(d(¯u, ¯zu ti)√κ) cos(d(¯zu ti,¯zu tj)√κ). 19 It follows that cos(d(u, zu ti)√κ)−(1 −cos ε) cos(M√κ) ≤cos(d(u, zu tj)√κ) = cos(d(¯u, ¯zu tj)√κ) ≤cos(d(¯u, ¯zu ti)√κ) cos(d(¯zu tj,¯zu ti)√κ) ≤cos(d(u, zu ti)√κ) cos(d(zu tj, zu ti)√κ). Hence cos(d(zu tj, zu ti)√κ)≥1−(1 −cos ε)cos(M√κ) cos(d(u, zu ti)√κ)≥cos ε. Thus, d(zu tj, zu ti)√κ≤εand the proof is complete. 7 Effective rates of metastability In this section we shall prove the main result of our paper, Theorem 3.4, hence we assume that its hypotheses are satisfied. We give first some technical results that will be needed in the proof. 7.1 Some useful lemmas As in [16,17], one of the main ingredients of our proof is a sequence obtained by combining the Halpern iteration (xn) and the points zu t. However, in the setting of CAT(κ) spaces, its definition and the proofs of the necessary properties are based on the much more involved technical lemmas from Section 4. If (an) is a real sequence, we say that lim sup n→∞ an≤0 with effective rate Ψ : (0,∞)→Z+if ∀ε > 0∀n≥Ψ(ε) (an≤ε). Let us define γt n= sin2d(u, zu t)√κ 2−sin2d(u, xn+1)√κ 2.(25) Proposition 7.1. (i) For n≥1, if γt n≥0, then γt n≤an t−sin2d(xn+1, zu t)√κ 2,(26) where an=1 cos(M√κ)sin2d(xn+1, Txn+1)√κ 2+ sin d(xn+1, Txn+1)√κ 2.(27) (ii) γt n≤an tfor all n≥1. 20 (iii) lim sup n→∞ γt n≤0with effective rate Ψ(ε, κ, M, t, γ, θ, α)given by Ψ = max θ 1 cos(M√κ)γ(L) + max ln 1 L,1, α(2L),(28) where L=cos(M√κ)tε 4M√κ. (iv) For n≥1, sin2d(xn+1, zu t)√κ 2≤sin ((1 −λn+1)M√κ) sin(M√κ)sin2d(xn, zu t)√κ 2 +sin (λn+1M√κ) sin(M√κ)max{γt n,0} +sin (tM√κ) sin(M√κ)sin2M√κ 2. Proof. (i) Apply Proposition 4.7.(ii) with x=u, y =xn+1, z =Tzu t, v = zu t, s =t,q=T xn+1 and note that sin2d(u, xn+1)√κ 2−sin2d(u, zu t)√κ 2=−γt n≤0. It follows that sin2d(xn+1, zu t)√κ 2≤ −γt n+an t, hence (i). (ii) Obviously, since an t≥0. (iii) Since an≤1 cos(M√κ)d(xn+1, Txn+1)√κand, by Proposition 3.2, the sequence (d(xn, Txn)) converges to 0 with rate of convergence Φ given by (7), we get that lim sup n→∞ γt n≤0 with effective rate Ψ(ε, κ, M, t, γ, θ, α)=Φcos(M√κ)tε √κ, κ, M, γ, θ, α. (iv) By Proposition 4.5.(ii) with x=u, y =T xn, z =Tzu t, w =xn+1, v = zu t, r =λn+1 and s=t. In fact, it suffices for the proof of the main theorem to consider the case ti=1 i+ 1, i ≥0. Then (ti) converges towards 0 with rate 1 ε. We shall denote γti nwith γi n. Furthermore, zu tiwill be simply denoted by zu i. Thus, γi n= sin2d(u, zu i)√κ 2−sin2d(u, xn+1)√κ 2.(29) 21 Lemma 7.2. Assume that i, j ≥0and δ∈(0,1) are such that d(u, Tzu i)− d(u, Tzu j)≤δ √κ. Then, γi n≤γj n+ sin2M√κ 2(j+ 1) + 2 sin M√κ 2(j+ 1) + sin2δ 2+ 2 sin δ 2sin M√κ 2. Proof. We have that γi n= sin2 i i+1 d(u, Tzu i)√κ 2−sin2d(u, xn+1)√κ 2 ≤sin2d(u, Tzu i)√κ 2−sin2d(u, xn+1)√κ 2 ≤ sin d(u, Tzu j)√κ 2+ sin δ 2!2 −sin2d(u, xn+1)√κ 2 ≤sin2d(u, Tzu j)√κ 2−sin2d(u, xn+1)√κ 2+ sin2δ 2+ 2 sin δ 2sin M√κ 2. Note that sin2d(u, Tzu j)√κ 2= sin2 j j+1 d(u, Tzu j)√κ+1 j+1 d(u, Tzu j)√κ 2 ≤sin2 j j+1 d(u, Tzu j)√κ 2+ sin2M√κ 2(j+ 1) + 2 sin M√κ 2(j+ 1). Finally, let us recall the following slight reformulation of [17, Lemma 5.2]. Lemma 7.3. Let ε∈(0,2),g:N→N,L > 0,θ:Z+→Z+and ψ: (0,∞)→ Z+. Define Θ = Θ(ε, L, θ, ψ) = θψε 3−1 + max ln 3L ε,1+ 1, ∆ = ∆(ε, g, L, θ, ψ) = ε 3gε(Θ −ψ(ε/3)), where gε(n) = n+g(n+ψ(ε/3)). Assume that (i) (αn)is a sequence in [0,1] such that the series ∞ X n=1 αndiverges with rate of divergence θ; (ii) (tn)is a sequence of real numbers such that tn≤ε 3for all n≥ψε 3. Let (sn)be a bounded sequence of real numbers with upper bound Lsatisfying sn+1 ≤(1 −αn)sn+αntn+ ∆ for all n≥1.(30) Then sn≤εfor all n∈[Θ,Θ + g(Θ)]. 22 7.2 Proof of Theorem 3.4 Let ε∈(0,2) and g:N→Nbe fixed. For simplicity, we omit parameters κ, M, Φ, θ, α, β for all functionals in this proof. Let us define h: (0,1) →R+by h(δ) = sin δ 2sin δ 2+ 2 sin M√κ 2+ sin δM√κ 2sin δM√κ 2+ 2≤6δ. (31) Take ε0=cos(M√κ) 36 sin2ε√κ 4. Then, h(ε0)≤cos(M√κ) 6sin2ε√κ 4. Applying Proposition 6.2 for ti=1 i+ 1, ε0and f∗, we get the existence of K1≤K(ε0, f∗) = f f∗M√κtan(M√κ) 1−cos ε0(0) such that d(zu i, zu j)≤ε0 √κfor all i, j ∈[K1,f f∗(K1)]. Let K0=K1+1 ε0and J=K0+f(K0) = f f∗(K1). It follows that d(zu J, zu K0)≤ε0 √κ, hence d(u, Tzu J)≤d(u, Tzu K0) + d(Tzu K0, Tzu J)≤d(u, Tzu K0) + d(zu K0, zu J) ≤d(u, Tzu K0) + ε0 √κ. An application of Lemma 7.2 with i=J, j =K0and δ=ε0gives us γJ n≤γK0 n+ sin2M√κ 2(K0+ 1) + 2 sin M√κ 2(K0+ 1) + sin2ε0 2+ 2 sin ε0 2sin M√κ 2 ≤γK0 n+ sin2ε0 2+ 2 sin ε0 2sin M√κ 2+ sin2Mε0√κ 2+ 2 sin Mε0√κ 2 =γK0 n+h(ε0)≤γK0 n+cos(M√κ) 6sin2ε√κ 4. Applying now Proposition 7.1.(iv) with t=1 J+1 and recalling the definition (21) of (µn), it follows that for all n≥1, sin2d(xn+1, zu J)√κ 2≤(1 −µn+1) sin2d(xn, zu J)√κ 2 +sin(λn+1M√κ) sin(M√κ)max{γJ n,0} + sin 1 J+1 M√κ sin(M√κ)sin2M√κ 2. Since J=K0+f(K0)≥&M√κ ∆∗ K0(sin2ε√κ 4, g)'and cos(M√κ) sin(λn+1M√κ)≤sin(M√κ)−sin (1 −λn+1)M√κ, 23 it follows that sin2d(xn+1, zu J)√κ 2≤(1 −µn+1) sin2d(xn, zu J)√κ 2 +µn+1 max γJ n cos(M√κ),0+ ∆∗ K0sin2ε√κ 4, g. Letting t=1 K0+ 1 in Proposition 7.1.(iii), we get that γK0 n≤cos(M√κ) 6sin2ε√κ 4, for all n≥χ∗ K01 3sin2ε√κ 4=χK0cos(M√κ) 6sin2ε√κ 4. Thus, γJ n≤γK0 n+cos(M√κ) 6sin2ε√κ 4≤cos(M√κ) 3sin2ε√κ 4, and so, max γJ n cos(M√κ),0≤1 3sin2ε√κ 4for all n≥χ∗ K01 3sin2ε√κ 4. Furthermore, by Lemma 5.2, we have that ∞ X n=1 µn+1 =∞with rate of divergence ˜ θ(n) = θ 1 cos(M√κ)n. Hence, we can apply Lemma 7.3 with sn= sin2d(xn, zu J)√κ 2, tn= max γJ n cos(M√κ),0, αn=µn+1, ε= sin2ε√κ 4,∆=∆∗ K0sin2ε√κ 4, g, L = sin2M√κ 2. By letting N= ΘK0sin2ε√κ 4, it follows that for all n∈[N, N +g(N)], sin2d(xn, zu J)√κ 2≤sin2ε√κ 4,and so d(xn, zu J)≤ε 2. Obviously, d(xn, xm)≤εfor all m, n ∈[N, N +g(N)]. One can easily see that N≤Σ(ε, g).  Acknowledgements: Laurent¸iu Leu¸stean was supported by a grant of the Romanian National Authority for Scientific Research, CNCS - UEFISCDI, project number PN-II-ID- PCE-2011-3-0383. Adriana Nicolae was supported by a grant of the Romanian Ministry of Education, CNCS - UEFISCDI, project number PN-II-RU-PD-2012-3-0152. 24 References [1] J. Avigad, P. Gerhardy, H. Towsner, Local stability of ergodic averages, Trans. Amer. Math. Soc. 362 (2010), 261-288. [2] J. Avigad, J. Rute, Oscillation and the mean ergodic theorem for uniformly convex Banach spaces, Ergodic Theory Dynam. Systems, available on CJO2014. doi:10.1017/etds.2013.90. [3] G. Birkhoff, The mean ergodic theorem, Duke Math. J. 5 (1939), 19-20. [4] M. Bridson, A. Haefliger, Metric spaces of non-positive curvature, Springer- Verlag, Berlin, 1999. [5] F.E. Browder, Existence and approximation of solutions of nonlinear variational inequalities, Proc. Nat. Acad. Sci. U.S.A. 56 (1966), 1080-1086. [6] F.E. Browder, Convergence of approximants to fixed points of nonexpansive nonlinear mappings in Banach spaces, Arch. Rational Mech. Anal. 24 (1967), 82-90. [7] R.E. Bruck, S. Reich, Accretive operators, Banach limits, and dual ergodic theorems, Bull. Acad. Polon. Sci. 29 (1981), 585–589. [8] K. Goebel, S. Reich, Uniform convexity, hyperbolic geometry, and nonexpansive mappings, Marcel Dekker, Inc., New York and Basel, 1984. [9] B. Halpern, Fixed points of nonexpanding maps, Bull. Amer. Math. Soc. 73 (1967), 957-961. [10] W.A. Kirk, Geodesic geometry and fixed point theory, Seminar of Mathematical Analysis (Malaga/Seville, 2002/2003), Colecc. Abierta, 64, Univ. Seville Secr. Publ., Seville (2003), 195-225. [11] U. Kohlenbach, Applied Proof Theory: Proof Interpretations and their Use in Mathematics, Springer, Heidelberg-Berlin, 2008. [12] U. Kohlenbach, On quantitative versions of theorems due to F.E. Browder and R. Wittmann, Adv. Math. 226 (2011), 2764-2795. [13] U. Kohlenbach, Some logical metatheorems with applications in functional analysis, Trans. Amer. Math. Soc. 357 (2005), 89-128. [14] U. Kohlenbach, L. Leu¸stean, A quantitative mean ergodic theorem for uniformly convex Banach spaces, Ergodic Theory Dynam. Systems 29 (2009), 1907-1915. Erratum: Ergodic Theory Dynam. Systems 29 (2009), 1995. [15] U. Kohlenbach, L. Leu¸stean, Asymptotically nonexpansive mappings in uniformly convex hyperbolic spaces, J. Eur. Math. Soc. 12 (2010), 71–92. 25