betaFeedback

WorksMathematics

Graded-Edge Rakotch Contractions in Generalized Metric Spaces with Weighted Graphs

Abstract

We introduce the notion of graded-edge Rakotch contraction mappings on a generalized metric space with a weighted graph. We prove that the successive iterate of every starting point converge uniformly to a common limit, which is the unique fixed point. We derive an explicit iteration-complexity bound and, under a relaxed triangle inequality, a geometric rate whose constant is the graph invariant. Finally, we illustrate the theory on an explicit real graded contraction that realizes the interior optimum, on a quadratic integral equation, and on finite weighted digraphs.

Introduction

Banach’s contraction principle [2] has led to a vast amount of literature, of which we mention only the parts directly relevant here. Rakotch [9] replaced the constant Lipschitz factor by a decreasing comparison function φ\varphi subject to φ(t)<1\varphi(t) < 1 for t>0t > 0, and thereby obtained a strictly larger class of mappings retaining the conclusion of Banach’s theorem; the point of the relaxation is precisely that φ(0)\varphi(0) is allowed to equal 1, so that a Rakotch contraction need not be Lipschitz with a constant smaller than one. A second line of development concerns spaces whose distance function satisfies only a relaxed triangle inequality d(x,z)≤M(d(x,y)+d(y,z))d(x,z) \le M(d(x,y) + d(y,z)) for a constant M≥1M \ge1. Such spaces, the bb-metric spaces of Bakhtin [1] and Czerwik [6], form a proper generalization of metric spaces, the case M=1M = 1, and support their own extensive fixed point theory. A standard instance is the snowflake d(x,y)=∣x−y∣pd(x,y) = |x-y|^p with p>1p > 1 on the real line, for which M=2p−1M = 2^{p-1} and the ordinary triangle inequality fails.

Motivated by such examples, Reich and Zaslavski [11] introduced generalized metric spaces, in which the inequality d(x,z)≤Md(x,y)+Md(y,z)d(x,z) \le M d(x,y) + M d(y,z) is taken as an axiom, and proved a Rakotch-type fixed point theorem. In the recent paper [12] they went further in two directions: First, they replaced the relaxed triangle inequality by a purely qualitative ε\varepsilon–δ\delta condition, so that no numerical constant is available at all. Second, they endowed the space with a graph GG and required the contractive estimate to hold only along the edges of GG, the two points of an arbitrary pair being connected instead by a GG-chain of length at most a fixed integer n0n_0. This last device goes back to Jachymski [7], whose theorem unified the classical contraction principle with its ordered-space variants due to Ran and Reurings [10] and Nieto and Rodríguez-López [8]; Beg et al. [3] see also Bojor [5] and Beg and Butt [4].

In [12] the graph enters twice: once through the edge-preservation requirement, and once through the connectivity hypothesis (P3). The contractive estimate itself, however, is governed by a single scalar comparison function φ\varphi, so that the graph contributes no quantitative information beyond the combinatorial bound n0n_0. We propose to let the graph carry the contraction data as well. Concretely, we attach to each edge a grade w(e)∈(0,1]w(e) \in(0,1], we let Eα={e∈E(G):w(e)≥α}E_\alpha= \{e \in E(G) : w(e) \ge\alpha\} denote the associated level cuts, and we ask that the mapping contract with comparison function φα\varphi_\alpha on EαE_\alpha, where α↦φα\alpha\mapsto\varphi_\alpha is pointwise non-increasing.

Substituting φ:=φα0\varphi:= \varphi_{\alpha_0} with α0=inf⁡ew(e)\alpha_0 = \inf_e w(e) restores the ungraded hypothesis, so that the qualitative conclusions cannot change. What makes the refinement substantive is that the two roles of the graph now move in opposite directions. Raising α\alpha improves the contraction factor but deletes edges, so that the chain-length invariant N(α):=sup⁡x,y∈KρGα(x,y)N(\alpha) := \sup_{x,y \in K} \rho_{G_\alpha}(x,y) increases. Every convergence estimate we prove therefore depends on α\alpha through two competing terms and must be optimized over the threshold. In Example 6.11 we exhibit an explicit space, mapping and grading for which the optimal threshold is interior, and for which the ungraded choice α0\alpha_0 is strictly worse than the graded optimum by a factor that persists as the tolerance tends to zero. We believe this example and not the definition itself as justification of the framework.

The second observation is related to the origin of the grading. It does not need to be provided as additional information: it is already contained in any edge-contractive mapping. Defining c(x,y)c(x,y) to be the supremum of the orbital ratios d(Tn+1x,Tn+1y)/d(Tnx,Tny)d(T^{n+1}x,T^{n+1}y)/d(T^n x,T^n y) and putting w:=1−cw := 1-c produces a grade which automatically satisfies the monotonicity axiom, and which normalizes the comparison family to φα≡1−α\varphi_\alpha\equiv1-\alpha (Proposition 3.4). The graded theory is therefore not an additional hypothesis imposed on TT, but a decomposition of the information TT already carries.

Our contributions are the following.

  1. We introduce graded-edge Rakotch contractions (Definitions 3.1 and 3.2) over the qualitative framework of [12], retaining the possible asymmetry of dd and treating GG as a directed graph throughout, and we show that the grading always exists canonically (Proposition 3.4).

  1. We make the chaining step of [12] constructive by exhibiting an explicit modulus ηm\eta_m obtained by iterating the modulus of the ε\varepsilon–δ\delta triangle condition (Lemma 4.3).

  1. We prove a global uniform convergence theorem (Theorem 5.2) which contains [12 Theorem 2] as the case w≡1w \equiv1, and we close a gap in [12 Theorem 2], whose statement asserts the convergence of the Picard iterates but not the fixed point property of the limit (Theorem 5.5).

  1. We derive an explicit iteration-complexity bound (Theorem 6.1) and, under a relaxed triangle inequality, a geometric rate whose constant is the graph invariant N(α)MN(α)−1N(\alpha)M^{N(\alpha)-1} (Theorem 6.4); we optimize over α\alpha (Corollary 6.10) and settle the resulting trade-off explicitly (Example 6.11).

  1. We illustrate the theory on an explicit real graded contraction that realizes the interior optimum, on a quadratic integral equation, and on finite weighted digraphs (Section 7).

Preliminaries

The space

Throughout, XX is a nonempty set and d:X×X→[0,∞)d : X \times X \to[0,\infty) satisfies

d(x,y)=0⟺x=y(x,y∈X).(1)d(x,y) = 0 \Longleftrightarrow x = y \qquad(x,y \in X). \tag*{(1)}

Following [12] we do not assume that dd is symmetric, nor that it satisfies a triangle inequality; instead we impose the following two conditions.

Assumption 2.1 (A1). For each ε>0\varepsilon> 0 there exists δ>0\delta> 0 such that d(x,y)≤δd(x,y) \le\delta implies d(y,x)≤εd(y,x) \le\varepsilon.

Assumption 2.2 (A2). For each ε>0\varepsilon> 0 there exists δ>0\delta> 0 such that d(x,y)≤δd(x,y) \le\delta and d(y,z)≤δd(y,z) \le\delta imply d(x,z)≤εd(x,z) \le\varepsilon.

For ε>0\varepsilon> 0 we fix once and for all a choice of δ1(ε)\delta_1(\varepsilon) for (A1) and δ2(ε)\delta_2(\varepsilon) for (A2). Without loss of generality, we may assume that

δi is non-decreasing and δi(ε)≤ε(i=1,2, ε>0).(2)\delta_i \text{ is non-decreasing and } \delta_i(\varepsilon) \le\varepsilon\qquad(i = 1,2,\ \varepsilon> 0). \tag*{(2)}

We refer to δ1\delta_1 and δ2\delta_2 as the symmetry modulus and the triangle modulus of (X,d)(X,d).

Setting

U(ε):={(x,y)∈X×X:d(x,y)≤ε, d(y,x)≤ε},ε>0,(3)U(\varepsilon) := \{(x,y) \in X \times X : d(x,y) \le\varepsilon,\ d(y,x) \le\varepsilon\}, \qquad\varepsilon> 0, \tag*{(3)}

one checks as in [12] that {U(ε)}ε>0\{U(\varepsilon)\}_{\varepsilon> 0} is a base of a uniformity on XX, metrizable by a metric d1d_1. We assume throughout that the metric space (X,d1)(X,d_1) is complete. By construction, for every ρ>0\rho> 0 there is ε>0\varepsilon> 0 with U(ε)⊆{(x,y):d1(x,y)≤ρ}U(\varepsilon) \subseteq\{(x,y) : d_1(x,y) \le\rho\}, and conversely for every ε>0\varepsilon> 0 there is ρ>0\rho> 0 with {(x,y):d1(x,y)≤ρ}⊆U(ε)\{(x,y) : d_1(x,y) \le\rho\} \subseteq U(\varepsilon); in particular

d1(xn,x)→0⟹d(xn,x)→0 and d(x,xn)→0.(4)d_1(x_n,x) \to0 \mathrel{\Longrightarrow} d(x_n,x) \to0 \text{ and } d(x,x_n) \to0. \tag*{(4)}

A set E⊆XE \subseteq X is bounded if sup⁡{d(x,y):x,y∈E}<∞\sup\{d(x,y) : x,y \in E\} < \infty.

Remark 2.3. In several places below we shall strengthen (A2) to the quantitative condition

d(x,z)≤M(d(x,y)+d(y,z))(x,y,z∈X),(5)d(x,z) \le M\bigl(d(x,y) + d(y,z)\bigr) \qquad(x,y,z \in X), \tag*{(5)}

which is the notion of a generalized metric space of [11]; when dd is symmetric this is exactly a bb-metric space with constant MM in the sense of [1, 6]. Taking y=xy=x in (5) forces M≥1M \ge1. Condition (5) implies (A2) with δ2(ε)=ε/(2M)\delta_2(\varepsilon) = \varepsilon/(2M). We refer to the setting of (A1)–(A2) as the qualitative regime and to the setting of (5) as the quantitative regime. When M=1M = 1 and dd is symmetric, (X,d)(X,d) is an ordinary metric space.

Comparison functions

Let Φ\Phi denote the set of all decreasing functions φ:[0,∞)→[0,1]\varphi: [0,\infty) \to[0,1] such that φ(t)<1\varphi(t) < 1 for every t>0t > 0.

Remark 2.4. The requirement φ(t)<1\varphi(t) < 1 is imposed only for t>0t > 0, so that φ(0)=1\varphi(0) = 1 is permitted. This is essential: a decreasing φ:[0,∞)→[0,1)\varphi: [0,\infty) \to[0,1) would satisfy φ(t)≤φ(0)<1\varphi(t) \le\varphi(0) < 1 for every tt, so that the Rakotch condition would collapse to the Banach condition with constant φ(0)\varphi(0) and no generality would be gained. The definition in [12 §1] has codomain [0,1][0,1], as here; the one in [12 §2] has codomain [0,1)[0,1), which we take to be a slip of the pen.

Graded graphs

Let GG be a directed graph with vertex set V(G)=XV(G) = X and edge set E(G)⊆X×XE(G) \subseteq X \times X containing all loops. We write G‾\overline{G} for the symmetrization of GG, that is, the undirected graph in which xx and yy are adjacent whenever (x,y)∈E(G)(x,y) \in E(G) or (y,x)∈E(G)(y,x) \in E(G).

Definition 2.5. A grade on GG is a map w:E(G)→(0,1]w:E(G)\to(0,1]. For α∈(0,1]\alpha\in(0,1] the level cut of GG at α\alpha is the directed graph GαG_{\alpha} with V(Gα)=XV(G_{\alpha})=X and

Eα:={e∈E(G):w(e)≥α}.E_{\alpha}:=\{e\in E(G):w(e)\ge\alpha\}.

The pair (G,w)(G,w) is called a graded graph on XX.

Clearly E1⊆Eα⊆EβE_1\subseteq E_{\alpha}\subseteq E_{\beta} whenever β≤α\beta\le\alpha, so the level cuts form a decreasing family of graphs.

Given a nonempty K⊆XK\subseteq X, a G~α\widetilde{G}_{\alpha}-chain in KK from xx to yy of length qq is a finite sequence ξ0,…,ξq∈K\xi_0,\ldots,\xi_q\in K with ξ0=x\xi_0=x, ξq=y\xi_q=y and, for each i∈{0,…,q−1}i\in\{0,\ldots,q-1\},

(ξi,ξi+1)∈Eαor(ξi+1,ξi)∈Eα.(\xi_i,\xi_{i+1})\in E_{\alpha}\quad\text{or}\quad(\xi_{i+1},\xi_i)\in E_{\alpha}.

We denote by ρG~α(x,y)\rho_{\widetilde{G}_{\alpha}}(x,y) the least length of such a chain (with ρG~α(x,y)=∞\rho_{\widetilde{G}_{\alpha}}(x,y)=\infty if none exists) and we set

N(α):=sup⁡x,y∈KρG~α(x,y)∈N∪{∞},(6)N(\alpha):=\sup_{x,y\in K}\rho_{\widetilde{G}_{\alpha}}(x,y)\in\mathbb{N}\cup\{\infty\}, \tag*{(6)}

the α\alpha-chain diameter of KK. The function α↦N(α)\alpha\mapsto N(\alpha) is non-decreasing, and

A:={α∈(0,1]:N(α)<∞}A:=\{\alpha\in(0,1]:N(\alpha)<\infty\}

is a sub-interval of (0,1](0,1] containing 00 in its closure whenever it is nonempty. The connectivity hypothesis (P3) of [12 page 13] is precisely the statement N(α)<∞N(\alpha)<\infty for the ungraded graph, with n0=N(α)n_0=N(\alpha).

Graded-edge Rakotch contractions

Throughout this section, (G,w)(G,w) is a graded graph on XX, K⊆XK\subseteq X is nonempty and closed in (X,d1)(X,d_1), and T:K→KT:K\to K.

Definition 3.1 (Grade-monotone edge preservation, (C1)). The mapping TT is said to be grade-monotone edge preserving if for every (x,y)∈E(G)(x,y)\in E(G) with x,y∈Kx,y\in K,

(T(x),T(y))∈E(G)andw(T(x),T(y))≥w(x,y).(T(x),T(y))\in E(G)\quad\text{and}\quad w(T(x),T(y))\ge w(x,y).

Condition (C1) strengthens the edge-preservation requirement of [12 (5)] by demanding that TT never weakens a connection. It is what guarantees that an orbit which starts inside a level cut remains there.

Definition 3.2 (Graded Rakotch condition, (C2)). Let {φα}α∈(0,1]⊆Φ\{\varphi_{\alpha}\}_{\alpha\in(0,1]}\subseteq\Phi be a family such that

α≤β⇒φβ(t)≤φα(t)(t≥0),(7)\alpha\le\beta\Rightarrow\varphi_{\beta}(t)\le\varphi_{\alpha}(t)\quad(t\ge0), \tag*{(7)}

that is, α↦φα\alpha\mapsto\varphi_{\alpha} is pointwise non-increasing. The mapping TT is a graded-edge Rakotch contraction with respect to (G,w)(G,w) and {φα}\{\varphi_{\alpha}\} if it satisfies (C1) and

d(T(x),T(y))≤φw(x,y)(d(x,y))d(x,y)for every (x,y)∈E(G) with x,y∈K.(8)d(T(x),T(y))\le\varphi_{w(x,y)}(d(x,y))d(x,y)\quad\text{for every }(x,y)\in E(G)\text{ with }x,y\in K. \tag*{(8)}

We set T0(x)=xT^0(x)=x for $x\in K.

Remark 3.3. If w≡1w\equiv1 and φ1=φ\varphi_1=\varphi, then (C1) reduces to [12 (5)] and (8) reduces to [12 (6)]. If moreover E(G)=K×KE(G)=K\times K, one recovers the hypotheses of [12 Theorem 1]. Finally, if each φα\varphi_{\alpha} is constant, one recovers the graph-theoretic Banach contractions of [7].

The next result shows that Definition 3.2 does not in fact impose any new hypothesis on TT beyond edge preservation and a mild uniformity: the grading may always be manufactured from the mapping itself, and when it is, the comparison family is normalized.

Proposition 3.4 (Canonical grading). Let TT satisfy (x,y)∈E(G)⇒(T(x),T(y))∈E(G)(x,y) \in E(G) \Rightarrow(T(x),T(y)) \in E(G) for x,y∈Kx,y \in K. For (x,y)∈E(G)(x,y) \in E(G) with x,y∈Kx,y \in K put

c(x,y):=sup⁡{d(Tn+1(x),Tn+1(y))d(Tn(x),Tn(y)):n≥0, d(Tn(x),Tn(y))>0},(9)c(x,y) := \sup\left\{ \frac{d(T^{n+1}(x),T^{n+1}(y))}{d(T^n(x),T^n(y))} : n \ge0,\ d(T^n(x),T^n(y)) > 0 \right\}, \tag*{(9)}

with the convention sup⁡∅:=0\sup\varnothing:= 0, and assume c(x,y)<1c(x,y) < 1 for every such pair. Then w:=1−cw := 1-c is a grade on E(G)E(G), and TT is a graded-edge Rakotch contraction with respect to (G,w)(G,w) and the family

φα≡1−α(α∈(0,1]).\varphi_\alpha\equiv1-\alpha\qquad(\alpha\in(0,1]).

Moreover 1−α1-\alpha is optimal, in the sense that no constant c′<1−αc' < 1-\alpha satisfies d(T(x),T(y))≤c′d(x,y)d(T(x),T(y)) \le c'd(x,y) for every (x,y)∈Eα(x,y) \in E_\alpha, whenever the value α\alpha is attained by ww and the supremum in (9) is attained at n=0n=0 for some such edge.

Proof. By hypothesis c(x,y)∈[0,1)c(x,y) \in[0,1), so w(x,y)=1−c(x,y)∈(0,1]w(x,y)=1-c(x,y) \in(0,1] and ww is a grade.

(C1). Edge preservation holds by assumption. Since the mapping TT preserves edges, the pair (T(x),T(y))(T(x),T(y)) lies in E(G)E(G) and, directly from (9),

c(T(x),T(y))=sup⁡{d(Tn+1(x),Tn+1(y))d(Tn(x),Tn(y)):n≥1, d(Tn(x),Tn(y))>0}≤c(x,y),c(T(x),T(y)) = \sup\left\{ \frac{d(T^{n+1}(x),T^{n+1}(y))}{d(T^n(x),T^n(y))} : n \ge1,\ d(T^n(x),T^n(y)) > 0 \right\} \le c(x,y),

the supremum on the right being taken over a subset of the index set defining c(x,y)c(x,y). Hence w(T(x),T(y))≥w(x,y)w(T(x),T(y)) \ge w(x,y).

(C2). Each φα≡1−α\varphi_\alpha\equiv1-\alpha is a constant function with value in [0,1)[0,1), hence lies in Φ\Phi, and α↦1−α\alpha\mapsto1-\alpha is decreasing, so (7) holds. Let (x,y)∈E(G)(x,y) \in E(G) with x,y∈Kx,y \in K. If d(x,y)=0d(x,y)=0 then x=yx=y and (8) is trivial. Otherwise the case n=0n=0 of (9) gives

d(T(x),T(y))≤c(x,y)d(x,y)=(1−w(x,y))d(x,y)=φw(x,y)(d(x,y))d(x,y).d(T(x),T(y)) \le c(x,y)d(x,y)=(1-w(x,y))d(x,y)=\varphi_{w(x,y)}(d(x,y))d(x,y).

Optimality. Suppose (x,y)∈Eα(x,y) \in E_\alpha with w(x,y)=αw(x,y)=\alpha and that the supremum in (9) is attained at n=0n=0. Then d(T(x),T(y))=c(x,y)d(x,y)=(1−α)d(x,y)d(T(x),T(y))=c(x,y)d(x,y)=(1-\alpha)d(x,y), so no smaller constant is admissible.

Remark 3.5. It is tempting to dismiss Definition 3.2 on the ground that φ:=φα0\varphi:= \varphi_{\alpha_0} with α0:=inf⁡{w(e):e∈E(G)}\alpha_0 := \inf\{w(e):e \in E(G)\} satisfies (8) on all of E(G)E(G), so that every graded-edge Rakotch contraction is an ordinary one. This is correct, and it is exactly why the qualitative statements of Section 5 are not new in substance. The content of the grading lies in Section 6: the quantitative estimates involve φα\varphi_\alpha and N(α)N(\alpha) simultaneously, and passing to α0\alpha_0 minimizes the first factor while maximizing the second. Example 6.11 exhibits data for which the choice α0\alpha_0 is strictly worse than the optimal graded choice.

Auxiliary results

We first record the effect of (C1) along an orbit.

Lemma 4.1 (Invariance and monotonicity). Let TT be a graded-edge Rakotch contraction, let α∈(0,1]\alpha\in(0,1] and let x,y∈Kx,y \in K satisfy (x,y)∈Eα(x,y) \in E_\alpha. Then

(Tn(x),Tn(y))∈Eα(n≥0),(T^n(x),T^n(y)) \in E_\alpha\qquad(n \ge0),

and the sequence n↦d(Tn(x),Tn(y))n \mapsto d(T^n(x),T^n(y)) is non-increasing. If moreover φα≡cα\varphi_\alpha\equiv c_\alpha is constant, then

d(Tn(x),Tn(y))≤cαnd(x,y)(n≥0).(10)d(T^n(x),T^n(y)) \le c_\alpha^n d(x,y) \qquad(n \ge0). \tag*{(10)}

Proof. The first assertion holds for n=0n=0 by hypothesis. If (Tn(x),Tn(y))∈Eα(T^n(x),T^n(y)) \in E_\alpha, then (C1) gives (Tn+1(x),Tn+1(y))∈E(G)(T^{n+1}(x),T^{n+1}(y)) \in E(G) and

w(Tn+1(x),Tn+1(y))≥w(Tn(x),Tn(y))≥α,w(T^{n+1}(x),T^{n+1}(y)) \ge w(T^n(x),T^n(y)) \ge\alpha,

so that (Tn+1(x),Tn+1(y))∈Eα(T^{n+1}(x),T^{n+1}(y)) \in E_\alpha; the claim follows by induction. For the second assertion, put an:=d(Tn(x),Tn(y))a_n := d(T^n(x),T^n(y)). Applying (8) to the edge (Tn(x),Tn(y))∈E(G)(T^n(x),T^n(y)) \in E(G) and using φw≤1\varphi_w \le1 we obtain

an+1≤φw(Tn(x),Tn(y))(an)an≤an.a_{n+1} \le\varphi_{w(T^n(x),T^n(y))}(a_n)a_n \le a_n.

If φα≡cα\varphi_\alpha\equiv c_\alpha, then w(Tn(x),Tn(y))≥αw(T^n(x),T^n(y)) \ge\alpha and (7) give an+1≤cαana_{n+1} \le c_\alpha a_n, whence (10) by induction. □

The next lemma is the graded form of [12 Lemma 1]. It converts the multiplicative contraction (8) into an additive decrease that is uniform over all edges of a given level cut.

Lemma 4.2 (Graded uniform decrease). Let TT be a graded-edge Rakotch contraction, let α∈(0,1]\alpha\in(0,1], let ε>0\varepsilon> 0, and let x,y∈Kx,y \in K satisfy

(x,y)∈Eαandd(x,y)>ε.(x,y) \in E_\alpha\qquad\text{and} \qquad d(x,y) > \varepsilon.

Then

d(T(x),T(y))≤d(x,y)−ε(1−φα(ε)).d(T(x),T(y)) \le d(x,y)-\varepsilon(1-\varphi_\alpha(\varepsilon)).

Proof. Write w:=w(x,y)w := w(x,y) and t:=d(x,y)t := d(x,y). Since (x,y)∈Eα(x,y) \in E_\alpha we have w≥αw \ge\alpha, so that φw(t)≤φα(t)\varphi_w(t) \le\varphi_\alpha(t) by (7). Since φα\varphi_\alpha is decreasing and t>εt > \varepsilon, we also have φα(t)≤φα(ε)\varphi_\alpha(t) \le\varphi_\alpha(\varepsilon). Hence, by (8),

t−d(T(x),T(y))≥t(1−φw(t))≥t(1−φα(t))≥t(1−φα(ε))≥ε(1−φα(ε)),t-d(T(x),T(y)) \ge t(1-\varphi_w(t)) \ge t(1-\varphi_\alpha(t)) \ge t(1-\varphi_\alpha(\varepsilon)) \ge\varepsilon(1-\varphi_\alpha(\varepsilon)),

where the last inequality uses t>εt > \varepsilon together with 1−φα(ε)≥01-\varphi_\alpha(\varepsilon) \ge0. Rearranging gives the assertion. □

In [12] the existence of a threshold ε0\varepsilon_0 with the property that short steps along a bounded chain produce a short displacement between its endpoints is deduced from (A2) but is not exhibited. The following lemma supplies it explicitly. Recall the moduli δ1,δ2\delta_1,\delta_2 fixed in (2) and let δ2k\delta_2^{k} denote the kk-fold composition of δ2\delta_2 with itself, with δ20:=id⁡\delta_2^0 := \operatorname{id}.

Lemma 4.3 (Chaining modulus). Define

η1(ε):=min⁡{ε,δ1(ε)},ηm(ε):=η1(δ2m−1(ε))(m≥2, ε>0).(11)\eta_1(\varepsilon) := \min\{\varepsilon,\delta_1(\varepsilon)\}, \qquad\eta_m(\varepsilon) := \eta_1\bigl(\delta_2^{m-1}(\varepsilon)\bigr) \qquad(m \ge2,\ \varepsilon> 0). \tag*{(11)}

Let m≥1m \ge1, let ε>0\varepsilon> 0 and let ξ0,…,ξm∈X\xi_0,\ldots,\xi_m \in X be such that for each i∈{0,…,m−1}i \in\{0,\ldots,m-1\} at least one of the inequalities

d(ξi,ξi+1)≤ηm(ε),d(ξi+1,ξi)≤ηm(ε)d(\xi_i,\xi_{i+1}) \le\eta_m(\varepsilon), \qquad d(\xi_{i+1},\xi_i) \le\eta_m(\varepsilon)

holds. Then d(ξ0,ξm)≤εd(\xi_0,\xi_m) \le\varepsilon.

Proof. We argue by induction on mm. Observe first that, by (2), each ηm\eta_m is non-decreasing and ηm+1≤ηm≤η1≤id⁡\eta_{m+1} \le\eta_m \le\eta_1 \le\operatorname{id}.

Case m=1m=1. If d(ξ0,ξ1)≤η1(ε)≤εd(\xi_0,\xi_1) \le\eta_1(\varepsilon) \le\varepsilon there is nothing to prove. If instead d(ξ1,ξ0)≤η1(ε)≤δ1(ε)d(\xi_1,\xi_0) \le\eta_1(\varepsilon) \le\delta_1(\varepsilon), then Assumption 2.1 yields d(ξ0,ξ1)≤εd(\xi_0,\xi_1) \le\varepsilon.

Inductive step. Let m≥1m \ge1 and assume the assertion holds for chains of length mm. Let ξ0,…,ξm+1\xi_0,\ldots,\xi_{m+1} be a chain all of whose steps are bounded by ηm+1(ε)\eta_{m+1}(\varepsilon), and put ε′:=δ2(ε)\varepsilon' := \delta_2(\varepsilon). By (11),

ηm+1(ε)=η1(δ2m(ε))=η1(δ2m−1(ε′))=ηm(ε′).\eta_{m+1}(\varepsilon)=\eta_1\left(\delta_2^m(\varepsilon)\right)=\eta_1\left(\delta_2^{m-1}(\varepsilon')\right)=\eta_m(\varepsilon').

Hence the first mm steps of the chain are bounded by ηm(ε′)\eta_m(\varepsilon'), and the induction hypothesis, applied with ε′\varepsilon' in place of ε\varepsilon, gives

d(ξ0,ξm)≤ε′=δ2(ε).d(\xi_0,\xi_m) \le\varepsilon'=\delta_2(\varepsilon).

The last step is bounded by ηm+1(ε)=ηm(ε′)≤η1(ε′)\eta_{m+1}(\varepsilon)=\eta_m(\varepsilon') \le\eta_1(\varepsilon'), so the case m=1m=1 applied to the pair (ξm,ξm+1)(\xi_m,\xi_{m+1}) with ε′\varepsilon' in place of ε\varepsilon gives

d(ξm,ξm+1)≤ε′=δ2(ε).d(\xi_m,\xi_{m+1}) \le\varepsilon'=\delta_2(\varepsilon).

Assumption 2.2 now yields d(ξ0,ξm+1)≤εd(\xi_0,\xi_{m+1}) \le\varepsilon, which completes the induction.

Remark 4.4. In the quantitative regime (5) with dd symmetric one may take δ1(ε)=ε\delta_1(\varepsilon)=\varepsilon and δ2(ε)=ε/(2M)\delta_2(\varepsilon)=\varepsilon/(2M), whence

ηm(ε)=ε(2M)m−1(m≥1).\eta_m(\varepsilon)=\frac{\varepsilon}{(2M)^{m-1}}\qquad(m\ge1).

Thus the chaining modulus degrades geometrically in the chain length, at a rate governed by the constant MM. This is the precise mechanism by which the graph invariant N(α)N(\alpha) enters the estimates of § 7, and the reason why no analogue of those estimates is available in the purely qualitative regime.

Fixed point

Let K⊆XK \subseteq X be a nonempty and closed in (X,d1)(X,d_1),

D0:=sup⁡{d(x,y):x,y∈K}<∞,(12)D_0 := \sup\{d(x,y):x,y\in K\}<\infty, \tag*{(12)}

T:K→KT:K\to K is a graded-edge Rakotch contraction with respect to a graded graph (G,w)(G,w) and a family {φα}\{\varphi_\alpha\} as in Definition 3.2, and A≠∅A\ne\varnothing, that is, N(α)<∞N(\alpha)<\infty for at least one α∈(0,1]\alpha\in(0,1].

For ε>0\varepsilon>0 and α∈A\alpha\in A we introduce the two quantities

ε0(ε,α):=ηN(α)(ε),k0(ε,α):=⌈D0ε0(ε,α)(1−φα(ε0(ε,α)))⌉.(13)\varepsilon_0(\varepsilon,\alpha):=\eta_{N(\alpha)}(\varepsilon),\qquad k_0(\varepsilon,\alpha):=\left\lceil\frac{D_0}{\varepsilon_0(\varepsilon,\alpha)\left(1-\varphi_\alpha\left(\varepsilon_0(\varepsilon,\alpha)\right)\right)}\right\rceil. \tag*{(13)}

Assumption 5.1 (A3). ε0(ε,α)\varepsilon_0(\varepsilon,\alpha) and k0(ε,α)k_0(\varepsilon,\alpha) are finite and positive.

Theorem 5.2 (Global uniform convergence). Let Assumption 5.1 hold and let α∈A\alpha\in A. Then:

  1. for every ε>0\varepsilon>0 and every integer n≥k0(ε,α)n\ge k_0(\varepsilon,\alpha),

sup⁡x,y∈Kd(Tn(x),Tn(y))≤ε;(14)\sup_{x,y\in K}d\left(T^n(x),T^n(y)\right)\le\varepsilon; \tag*{(14)}
  1. there exists a point x∗∈Kx^*\in K such that Tn(x)→x∗T^n(x)\to x^* in (X,d1)(X,d_1) as n→∞n\to\infty, for every x∈Kx\in K, and the convergence is uniform on KK.

Proof. Write ε0:=ε0(ε,α)\varepsilon_0 := \varepsilon_0(\varepsilon,\alpha) and k0:=k0(ε,α)k_0 := k_0(\varepsilon,\alpha).

Step 1 (a single edge enters the ε0\varepsilon_0-regime in at most k0k_0 steps). Let (ξ,η)∈Eα(\xi,\eta) \in E_\alpha with ξ,η∈K\xi,\eta\in K. We claim that there is an integer n∈{0,…,k0}n \in\{0,\ldots,k_0\} with d(Tn(ξ),Tn(η))≤ε0d(T^n(\xi),T^n(\eta)) \le\varepsilon_0. Suppose not. Then d(Tn(ξ),Tn(η))>ε0d(T^n(\xi),T^n(\eta)) > \varepsilon_0 for every n∈{0,…,k0}n \in\{0,\ldots,k_0\}, and since (Tn(ξ),Tn(η))∈Eα(T^n(\xi),T^n(\eta)) \in E_\alpha by Lemma 4.1, Lemma 4.2 yields

d(Tn+1(ξ),Tn+1(η))≤d(Tn(ξ),Tn(η))−ε0(1−φα(ε0)),n∈{0,…,k0−1}.d(T^{n+1}(\xi),T^{n+1}(\eta)) \le d(T^n(\xi),T^n(\eta))-\varepsilon_0(1-\varphi_\alpha(\varepsilon_0)), \qquad n \in\{0,\ldots,k_0-1\}.

Summing this telescoping estimate and using (12) we obtain

D0≥d(ξ,η)−d(Tk0(ξ),Tk0(η))=∑i=0k0−1[d(Ti(ξ),Ti(η))−d(Ti+1(ξ),Ti+1(η))]≥k0ε0(1−φα(ε0)),\begin{aligned} D_0 &\ge d(\xi,\eta)-d(T^{k_0}(\xi),T^{k_0}(\eta)) \\ &= \sum_{i=0}^{k_0-1}\left[d(T^i(\xi),T^i(\eta))-d(T^{i+1}(\xi),T^{i+1}(\eta))\right] \\ &\ge k_0\varepsilon_0(1-\varphi_\alpha(\varepsilon_0)), \end{aligned}

that is, k0≤D0ε0−1(1−φα(ε0))−1k_0 \le D_0\varepsilon_0^{-1}(1-\varphi_\alpha(\varepsilon_0))^{-1}. This contradicts (13) and proves the claim.

Step 2 (the regime is absorbing). By Lemma 4.1 the sequence n↦d(Tn(ξ),Tn(η))n \mapsto d(T^n(\xi),T^n(\eta)) is non-increasing. Combined with Step 1 this shows that

d(Tn(ξ),Tn(η))≤ε0for every n≥k0 and every (ξ,η)∈Eα with ξ,η∈K.(15)d(T^n(\xi),T^n(\eta)) \le\varepsilon_0 \qquad\text{for every } n \ge k_0 \text{ and every } (\xi,\eta) \in E_\alpha\text{ with } \xi,\eta\in K. \tag*{(15)}

Step 3 (chaining). Let x,y∈Kx,y \in K. Since N(α)<∞N(\alpha) < \infty there are an integer q≤N(α)q \le N(\alpha) and points ξ0,…,ξq∈K\xi_0,\ldots,\xi_q \in K forming a Gˉα\bar{G}_\alpha-chain from xx to yy. Fix n≥k0n \ge k_0. By (C1) the points Tn(ξ0),…,Tn(ξq)T^n(\xi_0),\ldots,T^n(\xi_q) again form a Gˉα\bar{G}_\alpha-chain, and by (15) each of its steps satisfies

d(Tn(ξi),Tn(ξi+1))≤ε0ord(Tn(ξi+1),Tn(ξi))≤ε0,i∈{0,…,q−1}.d(T^n(\xi_i),T^n(\xi_{i+1})) \le\varepsilon_0 \quad\text{or} \quad d(T^n(\xi_{i+1}),T^n(\xi_i)) \le\varepsilon_0,\qquad i \in\{0,\ldots,q-1\}.

Since ε0=ηN(α)(ε)≤ηq(ε)\varepsilon_0=\eta_{N(\alpha)}(\varepsilon)\le\eta_q(\varepsilon), Lemma 4.3 applies and gives d(Tn(x),Tn(y))≤εd(T^n(x),T^n(y))\le\varepsilon. As x,y∈Kx,y\in K were arbitrary, this proves (14) and hence (i).

Step 4 (the orbits are Cauchy). Let ρ>0\rho>0 and choose ε>0\varepsilon>0 so small that U(ε)⊆{(u,v):d1(u,v)≤ρ}U(\varepsilon)\subseteq\{(u,v):d_1(u,v)\le\rho\}; replacing ε\varepsilon by min⁡{ε,δ1(ε)}\min\{\varepsilon,\delta_1(\varepsilon)\} we may assume in addition that d(u,v)≤εd(u,v)\le\varepsilon implies d(v,u)≤εd(v,u)\le\varepsilon, so that (14) yields

(Tn(x),Tn(y))∈U(ε)(n≥k0(ε,α), x,y∈K).(16)(T^n(x),T^n(y)) \in U(\varepsilon) \qquad(n\ge k_0(\varepsilon,\alpha),\ x,y\in K). \tag*{(16)}

Given x∈Kx\in K and m≥0m\ge0, apply (16) with y:=Tm(x)∈Ky:=T^m(x)\in K to get d1(Tn(x),Tn+m(x))≤ρd_1(T^n(x),T^{n+m}(x))\le\rho for all n≥k0(ε,α)n\ge k_0(\varepsilon,\alpha). Hence {Tn(x)}n≥1\{T^n(x)\}_{n\ge1} is a Cauchy sequence in (X,d1)(X,d_1). Since (X,d1)(X,d_1) is complete and KK is closed, the limit xx∗:=lim⁡n→∞Tn(x)x_x^*:=\lim_{n\to\infty}T^n(x) exists and belongs to KK.

Step 5 (the limit does not depend on the starting point). Let x,y∈Kx,y\in K and ρ>0\rho>0. By (16), d1(Tn(x),Tn(y))≤ρd_1(T^n(x),T^n(y))\le\rho for all sufficiently large nn. Letting n→∞n\to\infty and using the continuity of d1d_1 we obtain d1(xx∗,xy∗)≤ρd_1(x_x^*,x_y^*)\le\rho, and since ρ>0\rho>0 was arbitrary, xx∗=xy∗=:x∗x_x^*=x_y^*=:x^*. Finally, the integer k0(ε,α)k_0(\varepsilon,\alpha) of (13) does not depend on xx, so the convergence is uniform on KK. This proves (ii).

Corollary 5.3. Taking w≡1w\equiv1, φ1=φ\varphi_1=\varphi and α=1\alpha=1 in Theorem 5.2 recovers [12 Theorem 2], with n0=N(1)n_0=N(1).

Theorem 5.2 asserts that all Picard orbits converge to a common limit, but it does not by itself identify that limit as a fixed point of TT; the same is true of [12 Theorem 2]. The obstruction is that TT is assumed to be contractive only along edges, so that no continuity of TT at x∗x^* is available a priori. We record two hypotheses, either of which removes it. The second is the graph-theoretic one and is modelled on property (A) of [7].

Definition 5.4. The graded graph (G,w)(G,w) has property (Aα)(A_{\alpha}) on KK if, whenever {xn}n≥1⊆K\{x_n\}_{n\ge1}\subseteq K satisfies (xn,xn+1)∈Eα(x_n,x_{n+1})\in E_{\alpha} for all nn and xn→xx_n\to x in (X,d1)(X,d_1) with x∈Kx\in K, there exists a subsequence {xnk}\{x_{n_k}\} with (xnk,x)∈Eα(x_{n_k},x)\in E_{\alpha} for all kk.

Theorem 5.5 (Fixed point and uniqueness). Let Assumption 5.1 hold, let α∈A\alpha\in A, and let x∗x^* be as in Theorem 5.2. Assume that at least one of the following conditions holds:

(a) TT is continuous at x∗x^* as a mapping of (K,d1)(K,d_1) into itself;

(b) (G,w)(G,w) has property (Aα)(A_{\alpha}) on KK and there exists x0∈Kx_0\in K with (x0,T(x0))∈Eα(x_0,T(x_0))\in E_{\alpha}.

Then T(x∗)=x∗T(x^*)=x^*, and x∗x^* is the unique fixed point of TT in KK.

Proof. Throughout, x∗x^* denotes the point produced by Theorem 5.2(ii); we recall from that theorem that x∗∈Kx^*\in K and that Tn(x)→x∗T^n(x)\to x^* in (X,d1)(X,d_1) for every x∈Kx\in K. The proof falls into three parts: the fixed point property under (a), the fixed point property under (b), and uniqueness, the last of which uses neither (a) nor (b).

Part I: T(x∗)=x∗T(x^*)=x^* under hypothesis (a).

Step 1. Since x∗∈Kx^*\in K, Theorem 5.2(ii) may be applied with the starting point x:=x∗x:=x^*, and gives

Tn(x∗)⟶x∗ in (X,d1).(17)T^n(x^*)\longrightarrow x^* \text{ in } (X,d_1). \tag*{(17)}

Step 2. The points Tn(x∗)T^n(x^*) all lie in KK, because TT maps KK into itself. Hypothesis (a) states that TT is continuous at x∗x^* as a mapping of (K,d1)(K,d_1) into itself; applying this to the convergent sequence (17) gives

T(Tn(x∗))⟶T(x∗) in (X,d1).(18)T(T^n(x^*))\longrightarrow T(x^*) \text{ in } (X,d_1). \tag*{(18)}

Step 3. On the other hand T(Tn(x∗))=Tn+1(x∗)T(T^n(x^*))=T^{n+1}(x^*), and the sequence {Tn+1(x∗)}n≥0\{T^{n+1}(x^*)\}_{n\ge0} is a shift of the sequence in (17); a shift of a convergent sequence converges to the same limit, so

T(Tn(x∗))⟶x∗ in (X,d1).(19)T(T^n(x^*))\longrightarrow x^* \text{ in } (X,d_1). \tag*{(19)}

Step 4. (X,d1)(X,d_1) is a metric space, so a sequence has at most one limit. Comparing (18) and (19) gives T(x∗)=x∗T(x^*)=x^*.

Part II: T(x∗)=x∗T(x^*)=x^* under hypothesis (b).

Let x0∈Kx_0\in K be the point supplied by (b), so that (x0,T(x0))∈Eα(x_0,T(x_0))\in E_{\alpha}, and put xn:=Tn(x0)x_n:=T^n(x_0) for n≥0n\ge0.

Step 1 (the orbit is a path in EαE_{\alpha}). Apply Lemma 4.1 to the pair (x,y):=(x0,T(x0))∈Eα(x,y):=(x_0,T(x_0))\in E_{\alpha}. Its first assertion gives (Tn(x0),Tn(T(x0)))∈Eα(T^n(x_0),T^n(T(x_0)))\in E_{\alpha} for every n≥0n\ge0, that is,

(xn,xn+1)∈Eα(n≥0).(20)(x_n,x_{n+1})\in E_{\alpha}\qquad(n\ge0). \tag*{(20)}

(Equivalently one may argue directly by induction: if w(xn,xn+1)≥αw(x_n,x_{n+1})\ge\alpha then (C1) gives (xn+1,xn+2)∈E(G)(x_{n+1},x_{n+2})\in E(G) together with $w(x_{n+1},x_{n+2})\ge w(x_n,x_{n+1})\ge\alpha.)

Step 2 (the orbit converges to x∗x^*). By Theorem 5.2(ii),

xn⟶x∗ in (X,d1),x∗∈K.(21)x_n\longrightarrow x^* \text{ in } (X,d_1),\qquad x^*\in K. \tag*{(21)}

Step 3 (edges to the limit). Relations (20) and (21) are precisely the hypotheses of property (Aα)(A_{\alpha}) of Definition 5.4. That property therefore furnishes indices n1<n2<⋯n_1<n_2<\cdots with

(xnk,x∗)∈Eα⊆E(G)(k≥1).(22)(x_{n_k},x^*)\in E_{\alpha}\subseteq E(G)\qquad(k\ge1). \tag*{(22)}

This is the only place where hypothesis (b) is used, and it is what replaces the continuity assumed in Part I: without (22) the contractive estimate (8) could not be applied to any pair involving x∗x^*.

Step 4 (from d1d_1 to dd). By (4), the d1d_1-convergence (21) implies d(xn,x∗)→0d(x_n,x^*)\to0. In particular, writing

ak:=d(xnk,x∗),bk:=d(xnk+1,x∗),a_k:=d(x_{n_k},x^*),\qquad b_k:=d(x_{n_k+1},x^*),

we have ak→0a_k\to0 and bk→0b_k\to0 as k→∞k\to\infty.

Step 5 (the images converge to T(x∗)T(x^*)). Fix k≥1k\ge1. Both xnkx_{n_k} and x∗x^* belong to KK, and (xnk,x∗)∈E(G)(x_{n_k},x^*)\in E(G) by (22), so (8) applies to this pair and gives, using φ≤1\varphi\le1 for every φ∈Φ\varphi\in\Phi,

d(T(xnk),T(x∗))≤φw(xnk,x∗)(ak)ak≤ak.d(T(x_{n_k}),T(x^*))\le\varphi_{w(x_{n_k},x^*)}(a_k)a_k\le a_k.

Since T(xnk)=xnk+1T(x_{n_k})=x_{n_k+1}, this reads

ck:=d(xnk+1,T(x∗))≤ak⟶0.(23)c_k:=d(x_{n_k+1},T(x^*))\le a_k\longrightarrow0. \tag*{(23)}

Step 6 (reversing the arguments). The distance dd is not assumed symmetric, and (23) controls d(xnk+1,T(x∗))d(x_{n_k+1},T(x^*)), whereas the triangle condition (A2) will be applied below to a chain whose first point is T(x∗)T(x^*). Let ε>0\varepsilon>0 and set

ε′:=δ2(ε)>0,ε′′:=δ1(ε′)>0.\varepsilon':=\delta_2(\varepsilon)>0,\qquad\varepsilon'':=\delta_1(\varepsilon')>0.

By (23) there is k1k_1 with ck≤ε′′c_k\le\varepsilon'' for all k≥k1k\ge k_1. Assumption 2.1, applied with the target ε′\varepsilon' and the witness ε′′=δ1(ε′)\varepsilon''=\delta_1(\varepsilon'), then yields

d(T(x∗),xnk+1)≤ε′(k≥k1).(24)d(T(x^*),x_{n_k+1})\le\varepsilon'\qquad(k\ge k_1). \tag*{(24)}

Step 7 (applying the triangle condition). By Step 4 there is k2k_2 with bk≤ε′b_k\le\varepsilon' for all k≥k2k\ge k_2. Fix any k≥max⁡{k1,k2}k\ge\max\{k_1,k_2\}. Then, by (24) and the definition of bkb_k,

d(T(x∗),xnk+1)≤ε′=δ2(ε),d(xnk+1,x∗)≤ε′=δ2(ε).d(T(x^*),x_{n_k+1})\le\varepsilon'=\delta_2(\varepsilon),\qquad d(x_{n_k+1},x^*)\le\varepsilon'=\delta_2(\varepsilon).

Assumption 2.2, applied to the triple (T(x∗),xnk+1,x∗)(T(x^*),x_{n_k+1},x^*), gives

d(T(x∗),x∗)≤ε.d(T(x^*),x^*)\le\varepsilon.

Step 8. The number ε>0\varepsilon>0 in Steps 6 and 7 was arbitrary, so d(T(x∗),x∗)=0d(T(x^*),x^*)=0, and (1) gives T(x∗)=x∗T(x^*)=x^*.

Part III: uniqueness

Step 1. Let y∗∈Ky^*\in K satisfy T(y∗)=y∗T(y^*)=y^*. An immediate induction gives Tn(y∗)=y∗T^n(y^*)=y^* for every n≥0n\ge0, so the sequence {Tn(y∗)}n≥0\{T^n(y^*)\}_{n\ge0} is constant and converges in (X,d1)(X,d_1) to y∗y^*.

Step 2. Since y∗∈Ky^*\in K, Theorem 5.2(ii) applied with the starting point y∗y^* gives Tn(y∗)→x∗T^n(y^*)\to x^* in (X,d1)(X,d_1).

Step 3. Limits in the metric space (X,d1)(X,d_1) are unique, so y∗=x∗y^*=x^*. Combined with Parts I and II, this shows that x∗x^* is the unique fixed point of TT in KK. □

Remark 5.6. Part III of the preceding proof uses neither (a) nor (b), only Assumption 5.1 and Theorem 5.2. Thus a graded-edge Rakotch contraction satisfying Assumption 5.1 has at most one fixed point in KK unconditionally; hypotheses (a) and (b) are needed only for existence. This is in contrast with [12 Theorem 1], where uniqueness requires the additional restriction that dd be finite on K×KK\times K, a restriction subsumed here by (12).

Optimal threshold

The proof of Theorem 5.2 yields an explicit bound on the number of iterations needed to reach a prescribed accuracy. Since α\alpha ranges over AA, the bound may be optimized over the threshold.

Theorem 6.1 (Iteration complexity). Let Assumption 5.1 hold and let ε>0\varepsilon> 0. Then

sup⁡x,y∈Kd(Tn(x),Tn(y))≤εfor every integer n≥K(ε),\sup_{x,y\in K} d\left(T^n(x),T^n(y)\right) \leq\varepsilon\qquad\text{for every integer } n \geq\mathcal{K}(\varepsilon),

where

K(ε):=inf⁡α∈Ak0(ε,α)=inf⁡α∈A⌈D0ηN(α)(ε)(1−φα(ηN(α)(ε)))⌉.\mathcal{K}(\varepsilon) := \inf_{\alpha\in A} k_0(\varepsilon,\alpha) = \inf_{\alpha\in A} \left\lceil\frac{D_0}{\eta_{N(\alpha)}(\varepsilon)\left(1-\varphi_\alpha\left(\eta_{N(\alpha)}(\varepsilon)\right)\right)} \right\rceil.

Proof. Step 1 (each k0(ε,α)k_0(\varepsilon,\alpha) is a well-defined non-negative integer). Fix α∈A\alpha\in A and abbreviate m:=N(α)m:=N(\alpha), which is finite by the definition of AA. We check the three ingredients of (13) in turn.

(i) ηm(ε)>0\eta_m(\varepsilon)>0. By (11), ηm(ε)=η1(δ2∘(m−1)(ε))\eta_m(\varepsilon)=\eta_1\left(\delta_2^{\circ(m-1)}(\varepsilon)\right). The moduli δ1,δ2\delta_1,\delta_2 are witnesses supplied by Assumptions 2.1 and 2.2, hence take strictly positive values at strictly positive arguments. A finite induction of length m−1m-1 therefore gives δ2∘(m−1)(ε)>0\delta_2^{\circ(m-1)}(\varepsilon)>0, and η1(t)=min⁡{t,δ1(t)}>0\eta_1(t)=\min\{t,\delta_1(t)\}>0 for t>0t>0. It is here, and only here, that the finiteness of N(α)N(\alpha) is used: for m=∞m=\infty the composition is an infinite one and the induction is unavailable.

(ii) 1−φα(ηm(ε))>01-\varphi_\alpha(\eta_m(\varepsilon))>0. Indeed ηm(ε)>0\eta_m(\varepsilon)>0 by (i), and every member of Φ\Phi satisfies φ(t)<1\varphi(t)<1 for t>0t>0.

(iii) D0<∞D_0<\infty by Assumption 5.1.

Hence the quotient in (13) is a well-defined element of [0,∞)[0,\infty), and k0(ε,α)k_0(\varepsilon,\alpha), being its ceiling, is a non-negative integer. (It equals 0 only in the degenerate case D0=0D_0=0, in which KK is a singleton.)

Step 2 (the infimum is attained). By Assumption 5.1 the set AA is nonempty, so by Step 1

S:={k0(ε,α):α∈A}S:=\{k_0(\varepsilon,\alpha):\alpha\in A\}

is a nonempty subset of N∪{0}\mathbb{N}\cup\{0\}. By the well-ordering principle SS has a least element, whence

K(ε)=inf⁡α∈Ak0(ε,α)=min⁡S\mathcal{K}(\varepsilon)=\inf_{\alpha\in A} k_0(\varepsilon,\alpha)=\min S

is a non-negative integer and there exists α∗∈A\alpha^*\in A with

k0(ε,α∗)=K(ε).(25)k_0(\varepsilon,\alpha^*)=\mathcal{K}(\varepsilon). \tag*{(25)}

No monotonicity or continuity of α↦k0(ε,α)\alpha\mapsto k_0(\varepsilon,\alpha) is claimed, and α∗\alpha^* need not be unique; only the attainment of the least value is asserted, and that follows from the integrality of the k0k_0 alone.

Step 3 (the conclusion of Theorem 5.2(i) does not involve α\alpha). This is the step that legitimises the optimization, so we isolate it. Write

Σn:=sup⁡x,y∈Kd(Tn(x),Tn(y)).\Sigma_n:=\sup_{x,y\in K}d\left(T^n(x),T^n(y)\right).

Theorem 5.2(i) asserts: for every α∈A\alpha\in A and every integer n≥k0(ε,α)n\geq k_0(\varepsilon,\alpha) one has Σn≤ε\Sigma_n\leq\varepsilon. The quantity Σn\Sigma_n depends only on nn, TT and KK; the threshold α\alpha enters the statement solely through the integer k0(ε,α)k_0(\varepsilon,\alpha) at which the conclusion switches on. Consequently the family of implications indexed by α∈A\alpha\in A may be combined, and Σn≤ε\Sigma_n \le\varepsilon holds as soon as nn exceeds the smallest of these thresholds. Were the conclusion itself α\alpha-dependent, no such combination would be permitted and K(ε)K(\varepsilon) would have to be replaced by a supremum.

Step 4 (conclusion). Let n≥K(ε)n \ge K(\varepsilon) be an integer. By (25) we have n≥k0(ε,α∗)n \ge k_0(\varepsilon,\alpha^*), so Theorem 5.2(i), applied with the single threshold α:=α∗\alpha:= \alpha^*, gives Σn≤ε\Sigma_n \le\varepsilon, which is the assertion. Finally, substituting ε0(ε,α)=ηN(α)(ε)\varepsilon_0(\varepsilon,\alpha) = \eta_{N(\alpha)}(\varepsilon) from (13) into the definition of k0k_0 yields the displayed formula for K(ε)K(\varepsilon). □

We stress that Theorem 6.1 is not merely a restatement of Theorem 5.2(i) with a change of notation. The passage from a fixed α\alpha to the infimum over AA is a genuine strengthening precisely because α↦k0(ε,α)\alpha\mapsto k_0(\varepsilon,\alpha) is not monotone: by (13) its numerator is constant while its denominator involves ηN(α)(ε)\eta_{N(\alpha)}(\varepsilon), which decreases as α\alpha grows, and 1−φα(⋅)1-\varphi_\alpha(\cdot), which increases. Example 6.11 exhibits data for which the minimizing α∗\alpha^* of (25) depends on ε\varepsilon, so that no single threshold is optimal for all tolerances.

For the remainder of this section we place ourselves in the quantitative regime of Remark 2.3 and we assume in addition that dd is symmetric.

Remark 6.2. Symmetry is used only to ensure that the estimate (8), which is stated for a directed edge, may be applied to the reversed steps of a G~α\widetilde{G}_\alpha-chain. Without it one obtains the same conclusion with an extra factor governed by a quantitative form of (A1); we do not pursue this here.

Lemma 6.3 (Polygonal inequality). Assume (5) and let a0,…,aq∈Xa_0,\ldots,a_q \in X with q≥1q \ge1. Then

d(a0,aq)≤Mq−1∑i=0q−1d(ai,ai+1).d(a_0,a_q) \le M^{q-1}\sum_{i=0}^{q-1}d(a_i,a_{i+1}).

Proof. Induction on qq. The case q=1q=1 is trivial. If the assertion holds for qq, then by (5) and M≥1M \ge1,

d(a0,aq+1)≤Md(a0,a1)+Md(a1,aq+1)d(a_0,a_{q+1}) \le M d(a_0,a_1) + M d(a_1,a_{q+1})
≤Md(a0,a1)+M⋅Mq−1∑i=1qd(ai,ai+1)≤Mq∑i=0qd(ai,ai+1).\le M d(a_0,a_1) + M \cdot M^{q-1}\sum_{i=1}^{q}d(a_i,a_{i+1}) \le M^q\sum_{i=0}^{q}d(a_i,a_{i+1}).
□\square

Theorem 6.4 (Geometric rate with a graph constant). Let Assumption 5.1 hold, assume (5) and that dd is symmetric, and suppose that for some α∈A\alpha\in A the comparison function is constant, say φα≡cα∈[0,1)\varphi_\alpha\equiv c_\alpha\in[0,1). Then, for every integer n≥0n \ge0,

sup⁡x,y∈Kd(Tn(x),Tn(y))≤N(α)MN(α)−1D0cαn.\sup_{x,y\in K}d\left(T^n(x),T^n(y)\right) \le N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n.

Proof. Let x,y∈Kx,y \in K and let ξ0,…,ξq\xi_0,\ldots,\xi_q be a G~α\widetilde{G}_\alpha-chain in KK from xx to yy with q≤N(α)q \le N(\alpha). Fix i∈{0,…,q−1}i \in\{0,\ldots,q-1\}. By (10) of Lemma 4.1,

d(Tn(ξi),Tn(ξi+1))≤cαnd(ξi,ξi+1)≤cαnD0,d\left(T^n(\xi_i),T^n(\xi_{i+1})\right) \le c_\alpha^n d(\xi_i,\xi_{i+1}) \le c_\alpha^nD_0,

where symmetry of dd has been used to cover reversed steps. Applying Lemma 6.3 to the points Tn(ξ0),…,Tn(ξq)T^n(\xi_0),\ldots,T^n(\xi_q) we obtain

d(Tn(x),Tn(y))≤Mq−1∑i=0q−1d(Tn(ξi),Tn(ξi+1))≤Mq−1qcαnD0≤N(α)MN(α)−1D0cαn,d\left(T^n(x),T^n(y)\right) \le M^{q-1}\sum_{i=0}^{q-1}d\left(T^n(\xi_i),T^n(\xi_{i+1})\right) \le M^{q-1}q c_\alpha^nD_0 \le N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n,

the last step because M≥1M \ge1 and q≤N(α)q \le N(\alpha). □

Now we exhibit three graded graphs on which every quantity occurring in § 5 and § 7, the grade of each edge, the level cuts EαE_\alpha, the chain diameter N(α)N(\alpha), the admissible set AA, the Picard iterates, and the estimates of Theorems 6.1 and 6.4, is computed explicitly. Everything is phrased in the language of the weighted graph: vertices, edges carrying a grade w(e)∈(0,1]w(e) \in(0,1], level cuts, chains, and the graded Rakotch condition (8).

Throughout, X=RX = \mathbb{R} and

d(x,y)=∣x−y∣p(p≥1),(26)d(x,y) = \lvert x-y\rvert^p \qquad(p \ge1), \tag*{(26)}

so that, by the convexity of t↦tpt \mapsto t^p, condition (5) holds with M=2p−1M = 2^{p-1}; the induced uniformity is the Euclidean one, d1d_1 may be taken to be the Euclidean metric, and (X,d1)(X,d_1) is complete. In each example K⊂RK \subset\mathbb{R} is closed and bounded, so Assumption 5.1 is met once A≠∅A \ne\varnothing is verified. All gradings are the canonical ones of Proposition 3.4, so that

w(x,y)=1−c(x,y),φα≡cα=1−α,(27)w(x,y) = 1-c(x,y), \qquad\varphi_\alpha\equiv c_\alpha= 1-\alpha, \tag*{(27)}

with c(x,y)c(x,y) the supremum of the orbital ratios (9).

We first record an elementary structural fact which explains the shape of the tables below: on a finite graded graph the Picard iteration does not merely converge, it terminates.

Proposition 6.5 (Finite graded graphs collapse). Let Assumption 5.1 hold and suppose KK is finite with at least two points. Then there is an integer n†≥1n^\dagger\ge1 such that TnT^n is constant on KK for every n≥n†n \ge n^\dagger; that is, Tn(x)=x∗T^n(x) = x^* for all x∈Kx \in K and all n≥n†n \ge n^\dagger.

Proof. Put δ:=min⁡{d(x,y):x,y∈K, x≠y}\delta:= \min\{d(x,y):x,y \in K,\ x \ne y\}, which is positive because KK is finite and dd satisfies (1). Choose ε∈(0,δ)\varepsilon\in(0,\delta) and let n†:=k0(ε,α)n^\dagger:= k_0(\varepsilon,\alpha) for some α∈A\alpha\in A, as in (13). By Theorem 5.2(i), d(Tn(x),Tn(y))≤ε<δd(T^n(x),T^n(y)) \le\varepsilon< \delta for all x,y∈Kx,y \in K and all n≥n†n \ge n^\dagger. By the definition of δ\delta this forces Tn(x)=Tn(y)T^n(x) = T^n(y), so TnT^n is constant; its value is the common limit x∗x^* of Theorem 5.2(ii).

Consequently, on a finite graded graph the geometric estimate of Theorem 6.4 is an envelope which is eventually strictly larger than the (vanishing) true quantity. What one should compare is therefore not the two sequences but the two iteration counts: the number of steps predicted by Theorem 6.1 against the number actually required. Example 6.6 shows that the graded prediction can be exact.

Example 6.6. Let p=2p=2, so that M=2M=2, and let

K={v0,v1,v2,v3,v4},v0=0,vi=3i−4 (1≤i≤4),K = \{v_0,v_1,v_2,v_3,v_4\}, \qquad v_0=0,\qquad v_i=3^{i-4}\ (1 \le i \le4),

that is K={0,127,19,13,1}K = \{0,\frac{1}{27},\frac{1}{9},\frac{1}{3},1\}, with

T(v0)=v0,T(vi)=vi−1(1≤i≤4).T(v_0)=v_0,\qquad T(v_i)=v_{i-1}\quad(1 \le i \le4).

Let GG be the complete graph on KK (all 10 unordered pairs, together with all loops), so that the edge-preservation half of (C1) is automatic.

Since {vi}\{v_i\} is decreasing and TT shifts indices downwards, the orbital ratios are computed at once; writing Δ=j−i\Delta=j-i, one finds for 1≤i<j≤41 \le i<j \le4

c(vi,vj)=(1/31−3−Δ)2,c(v0,vj)=(13)2=19(j≥2),c(v0,v1)=0.c(v_i,v_j)=\left(\frac{1/3}{1-3^{-\Delta}}\right)^2,\qquad c(v_0,v_j)=\left(\frac{1}{3}\right)^2=\frac{1}{9}\quad(j\ge2),\qquad c(v_0,v_1)=0.

The resulting canonical grades (27) are collected in Table 1 for Example 6.6; they take five distinct values. Grade monotonicity (C1) holds on every edge, as guaranteed by Proposition 3.4.

edge classpairsc(⋅,⋅)c(\cdot,\cdot)grade ww
{v0,v1}\{v_0,v_1\}v0v1v_0v_10011
spokes at v0v_0v0v2,v0v3,v0v4v_0v_2,v_0v_3,v_0v_41/91/98/9≈0.88898/9\approx0.8889
Δ=3\Delta=3v1v4v_1v_481/67681/676595/676≈0.8802595/676\approx0.8802
Δ=2\Delta=2v1v3,v2v4v_1v_3,v_2v_49/649/6455/64≈0.859455/64\approx0.8594
Δ=1\Delta=1v1v2,v2v3,v3v4v_1v_2,v_2v_3,v_3v_41/41/43/4=0.75003/4=0.7500

Table 1. Canonical Grades

Graded graph of Example 6.6

Figure 1. Figure 1, shows the graded graph of Example 6.6. Thick edges carry grade ≥8/9\ge8/9, dashed edges grades 55/6455/64 and 595/676595/676, dotted edges grade 3/43/4. The mapping TT slides each vertex one step towards v0v_0.

Level cuts and the admissible set. Ordering the grades as in Table 1 gives

N(α)={1,0<α≤34,2,34<α≤89,∞,α>89,soA=(0,89].N(\alpha)= \begin{cases} 1, & 0<\alpha\le\frac{3}{4},\\ 2, & \frac{3}{4}<\alpha\le\frac{8}{9},\\ \infty, & \alpha>\frac{8}{9}, \end{cases} \qquad\text{so}\qquad A=\left(0,\frac{8}{9}\right].

Indeed, for α≤34\alpha\le\frac{3}{4} every pair is an edge of GαG_\alpha, so N(α)=1N(\alpha)=1; for 34<α≤89\frac{3}{4}<\alpha\le\frac{8}{9} the three Δ=1\Delta=1 edges are deleted, but v0v_0 remains adjacent to every vertex, so any two vertices are joined by a G~α\widetilde{G}_\alpha-chain of two hops through v0v_0 and N(α)=2N(\alpha)=2; for α>89\alpha>\frac{8}{9} only {v0,v1}\{v_0,v_1\} survives and G~α\widetilde{G}_\alpha is disconnected. Figure 2 displays the two admissible cuts of Example 6.6. Raising the threshold from 34\frac{3}{4} to 89\frac{8}{9} improves the contraction factor from cα=14c_\alpha=\frac{1}{4} to cα=19c_\alpha=\frac{1}{9} but doubles the chain diameter.

$G_\alpha$ for $\alpha=\frac{3}{4}$ $G_\alpha$ for $\alpha=\frac{8}{9}$

Figure 2. GαG_\alpha for α=34\alpha=\frac{3}{4}: N(α)=1N(\alpha)=1; GαG_\alpha for α=89\alpha=\frac{8}{9}: N(α)=2N(\alpha)=2.

Iterates. The orbit of the vertex set is

n=0: {0,127,19,13,1},n=1: {0,0,127,19,1},n=0:\ \{0,\frac{1}{27},\frac{1}{9},\frac{1}{3},1\},\qquad n=1:\ \{0,0,\frac{1}{27},\frac{1}{9},1\},

n=2: {0,0,0,127,19},n=3: {0,0,0,0,127},n=2:\ \{0,0,0,\frac{1}{27},\frac{1}{9}\},\qquad n=3:\ \{0,0,0,0,\frac{1}{27}\},

n=4: {0},n=4:\ \{0\}, so T4T^4 is constant, in accordance with Proposition 6.5, and the unique fixed point is x∗=v0=0x^*=v_0=0 (Theorem 5.5(a), TT being continuous). With D0=sup⁡x,y∈Kd(x,y)=1D_0=\sup_{x,y\in K}d(x,y)=1 one obtains

sup⁡x,y∈Kd(Tn(x),Tn(y))={9−n(0≤n≤3),0(n≥4).\sup_{x,y\in K}d(T^n(x),T^n(y))= \begin{cases} 9^{-n} & (0\le n\le3),\\ 0 & (n\ge4). \end{cases}

Rates and the optimal threshold. Theorem 6.4 gives, at the two admissible thresholds,

α1=34:N(α)MN(α)−1D0cαn=4−n,α2=89:N(α)MN(α)−1D0cαn=4⋅9−n,\alpha_1=\frac{3}{4}: \quad N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n=4^{-n},\qquad \alpha_2=\frac{8}{9}: \quad N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n=4\cdot9^{-n},

both valid for every n≥0n\ge0. Corollary 6.10 compares

Λ(α1,ε)=log⁡(1/ε)log⁡4,Λ(α2,ε)=2log⁡2+log⁡(1/ε)log⁡9,\Lambda(\alpha_1,\varepsilon)=\frac{\log(1/\varepsilon)}{\log4},\qquad \Lambda(\alpha_2,\varepsilon)=\frac{2\log2+\log(1/\varepsilon)}{\log9},

and Λ(α2,ε)<Λ(α1,ε)\Lambda(\alpha_2,\varepsilon)<\Lambda(\alpha_1,\varepsilon) precisely when log⁡(1/ε)>2(log⁡2)2/log⁡(3/2)\log(1/\varepsilon)>2(\log2)^2/\log(3/2), that is, when ε<ε∗\varepsilon<\varepsilon^* with

ε∗=exp⁡(−2(log⁡2)2log⁡(3/2))≈0.0935.\varepsilon^*=\exp\left(-\frac{2(\log2)^2}{\log(3/2)}\right)\approx0.0935.

Thus the optimal threshold is α1=34\alpha_1=\frac{3}{4} for coarse tolerances and α2=89\alpha_2=\frac{8}{9} for fine ones; since α1\alpha_1 is exactly the ungraded threshold α0=inf⁡{w(e)}\alpha_0=\inf\{w(e)\} of Remark 3.5, the graded theory is strictly better than the ungraded one for every ε<ε∗\varepsilon<\varepsilon^*. Table 2 makes this concrete. The least nn for which the bound of Theorem 6.4 certifies sup⁡x,yd(Tnx,Tny)≤ε\sup_{x,y}d(T^n x,T^n y)\le\varepsilon, against the least nn for which this actually holds, in Example 6.6. At the graded threshold α2\alpha_2 the prediction is exact; the ungraded threshold α1\alpha_1 overestimates by one step.

ε\varepsilonsteps predicted at α1=34\alpha_1=\frac{3}{4}steps predicted at α2=89\alpha_2=\frac{8}{9}steps actually needed
10−110^{-1}222
10−210^{-2}433
10−310^{-3}544

Table 2. Predicted vs Actual Steps

Remark 6.7. The agreement in the last two columns of Table 2 is not an accident of rounding: at α2\alpha_2 one has 4⋅9−3=0.005487≤10−24\cdot9^{-3}=0.005487\le10^{-2} while 4⋅9−2=0.04938>10−24\cdot9^{-2}=0.04938>10^{-2}, and the true values are 9−3=0.0013729^{-3}=0.001372 and 9−2=0.012359^{-2}=0.01235. The graded estimate therefore locates the exact stopping time, whereas the ungraded estimate 4−n4^{-n} requires n=4n=4.

The previous example has N(α)≤2N(\alpha)\le2, so the factor MN(α)−1M^{N(\alpha)-1} of Theorem 6.4 never exceeds MM. We now exhibit a graded graph which is not complete and whose admissible cuts have N(α)=3N(\alpha)=3, so that the graph constant N(α)MN(α)−1N(\alpha)M^{N(\alpha)-1} genuinely reflects the length of the chains used in Step 3 of the proof of Theorem 5.2.

Example 6.8. Let p=2p=2, so M=2M=2, and let

K={x0,x1,x2,x3}={0,1,3,9},K=\{x_0,x_1,x_2,x_3\}=\{0,1,3,9\},
T(x0)=x0,T(xi)=xi−1(1≤i≤3),T(x_0)=x_0,\qquad T(x_i)=x_{i-1}\quad(1\le i\le3),

with E(G)E(G) consisting of the loops together with the three consecutive pairs {x0,x1}\{x_0,x_1\}, {x1,x2}\{x_1,x_2\}, {x2,x3}\{x_2,x_3\} and their reversals. The edge set is TT-invariant, since {xi,xi+1}↦{xi−1,xi}\{x_i,x_{i+1}\}\mapsto\{x_{i-1},x_i\} for i≥1i\ge1 and {x0,x1}\{x_0,x_1\} maps to a loop. The orbital ratios are

c(x0,x1)=0,c(x1,x2)=c(x2,x3)=14,c(x_0,x_1)=0,\qquad c(x_1,x_2)=c(x_2,x_3)=\frac{1}{4},

whence the grades w(x0,x1)=1w(x_0,x_1)=1 and w(x1,x2)=w(x2,x3)=34w(x_1,x_2)=w(x_2,x_3)=\frac{3}{4}. Therefore

N(α)=3for 0<α≤34,N(α)=∞for α>34,A=(0,34],N(\alpha)=3\quad\text{for }0<\alpha\le\frac{3}{4},\qquad N(\alpha)=\infty\quad\text{for }\alpha>\frac{3}{4},\qquad A=\left(0,\frac{3}{4}\right],

the cut at α=34\alpha=\frac{3}{4} being the whole path x0−x1−x2−x3x_0-x_1-x_2-x_3, of graph diameter 3, and the cut above 34\frac{3}{4} retaining only {x0,x1}\{x_0,x_1\}, which leaves x2,x3x_2,x_3 isolated. Figure 3 presents the graded path of Example 6.8; the grey arrows indicate the action of TT. The admissible cut has chain diameter N(α)=3N(\alpha)=3.

Graded path of Example 6.8

Figure 3.

Here D0=∣9−0∣2=81D_0=|9-0|^2=81 and, at the optimal threshold α=34\alpha=\frac{3}{4} with cα=14c_\alpha=\frac{1}{4}, Theorem 6.4 yields

sup⁡x,y∈Kd(Tn(x),Tn(y))≤N(α)MN(α)−1D0cαn=3⋅22⋅81⋅4−n=972⋅4−n,\sup_{x,y\in K}d(T^n(x),T^n(y))\le N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n=3\cdot2^2\cdot81\cdot4^{-n}=972\cdot4^{-n},

against the true values 81,9,1,0,0,…81,9,1,0,0,\ldots for n=0,1,2,3,…n=0,1,2,3,\ldots. The estimate is valid at every step but is conservative, by a factor N(α)MN(α)−1=12N(\alpha)M^{N(\alpha)-1}=12 coming from the three-hop chains and the constant M=2M=2 of the relaxed triangle inequality. This is the price, quantified by Lemma 6.3, of comparing dd with the sum of the dd-lengths of the hops of a chain; Example 6.9 shows that when N(α)=1N(\alpha)=1 no such price is paid and the estimate becomes an identity.

Example 6.9. Let p=1p=1, so that d(x,y)=∣x−y∣d(x,y)=|x-y| and M=1M=1, and let

K={0}∪{2−n:n≥0},T(x)=x2,K=\{0\}\cup\{2^{-n}:n\ge0\},\qquad T(x)=\frac{x}{2},

with GG the complete graph on KK.

The set KK is closed and bounded in R\mathbb{R}, with D0=1D_0=1, and T(K)⊆KT(K)\subseteq K. Because TT is linear, every orbital ratio equals 12\frac{1}{2}: for all x,y∈Kx,y\in K,

d(T(x),T(y))d(x,y)=∣x/2−y/2∣∣x−y∣=12,\frac{d(T(x),T(y))}{d(x,y)}=\frac{|x/2-y/2|}{|x-y|}=\frac{1}{2},

so the canonical grading is constant, w=12w=\frac{1}{2}, and cα=12c_\alpha=\frac{1}{2} for every α∈A=(0,12]\alpha\in A=\left(0,\frac{1}{2}\right]. Since GG is complete, N(α)=1N(\alpha)=1 throughout AA. Figure 4 exhibits the infinite graded ray of Example 6.9 (complete graph; only some edges drawn). Every edge carries grade w=12w=\frac{1}{2}, and N(α)=1N(\alpha)=1.

Theorem 6.4 therefore predicts

sup⁡x,y∈Kd(Tn(x),Tn(y))≤N(α)MN(α)−1D0cαn=2−n,\sup_{x,y\in K}d(T^n(x),T^n(y))\le N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n=2^{-n},

while directly sup⁡x,y∈K∣Tn(x)−Tn(y)∣=2−nsup⁡x,y∈K∣x−y∣=2−n\sup_{x,y\in K}|T^n(x)-T^n(y)|=2^{-n}\sup_{x,y\in K}|x-y|=2^{-n}. Hence

sup⁡x,y∈Kd(Tn(x),Tn(y))=N(α)MN(α)−1D0cαn(n≥0):\sup_{x,y\in K}d(T^n(x),T^n(y))=N(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n\qquad(n\ge0):

the estimate of Theorem 6.4 is attained with equality for every nn. In particular the constant N(α)MN(α)−1D0N(\alpha)M^{N(\alpha)-1}D_0 cannot be improved in general. Note also that KK is infinite, so Proposition 6.5 does not apply and no orbit terminates: the geometric decay persists for all nn, and Tn(x)→0=x∗T^n(x)\to0=x^* without ever reaching it for $x\ne0.

Diagram showing the map $T:x\mapsto x/2$

Figure 4.

Corollary 6.10 (Optimal threshold). Under the hypotheses of Theorem 6.4, suppose that φα≡cα∈[0,1)\varphi_\alpha\equiv c_\alpha\in[0,1) for every α∈A\alpha\in A. Then, for every ε∈(0,D0)\varepsilon\in(0,D_0),

K(ε)≤inf⁡α∈AΛ(α,ε),Λ(α,ε):=(N(α)−1)log⁡M+log⁡N(α)+log⁡(D0/ε)log⁡(1/cα).(28)\mathcal{K}(\varepsilon) \le\inf_{\alpha\in A}\Lambda(\alpha,\varepsilon),\qquad\Lambda(\alpha,\varepsilon):=\frac{(N(\alpha)-1)\log M+\log N(\alpha)+\log(D_0/\varepsilon)}{\log(1/c_\alpha)}. \tag*{(28)}

Proof. Solve N(α)MN(α)−1D0cαn≤εN(\alpha)M^{N(\alpha)-1}D_0c_\alpha^n\le\varepsilon for nn and use Theorem 6.4.

The numerator of Λ(⋅,ε)\Lambda(\cdot,\varepsilon) is non-decreasing in α\alpha, because N(α)N(\alpha) is; the denominator is likewise non-decreasing, because cαc_\alpha is non-increasing. The infimum is therefore attained, in general, at neither endpoint of AA. The following example makes this precise, and shows in addition that the ungraded choice α0\alpha_0 of Remark 3.5 is strictly suboptimal.

Example 6.11 (An interior optimum). Fix p>1p>1 and b∈(0,1)b\in(0,1). Let X=RX=\mathbb{R} with

d(x,y):=∣x−y∣p,d(x,y):=|x-y|^p,

let K:=[0,b]K:=[0,b] and let

T(x):=12x2(x∈K).T(x):=\frac{1}{2}x^2\qquad(x\in K).

Let GG be the complete graph on XX, so that E(G)=X×XE(G)=X\times X.

We verify the hypotheses and compute all the quantities involved.

(1) The space. By the convexity of t↦tpt\mapsto t^p on [0,∞)[0,\infty),

∣x−z∣p≤(∣x−y∣+∣y−z∣)p≤2p−1(∣x−y∣p+∣y−z∣p),|x-z|^p\le(|x-y|+|y-z|)^p\le2^{p-1}(|x-y|^p+|y-z|^p),

so (5) holds with M=2p−1>1M=2^{p-1}>1, and dd is symmetric and satisfies (1). Since U(ε)={(x,y):∣x−y∣≤ε1/p}U(\varepsilon)=\{(x,y): |x-y|\le\varepsilon^{1/p}\}, the uniformity (3) is the usual one on R\mathbb{R}, so d1d_1 may be taken to be the Euclidean metric and (X,d1)(X,d_1) is complete. The set KK is closed and D0=bpD_0=b^p.

(2) The mapping. If 0≤x≤b<10\le x\le b<1 then 0≤x2/2≤b/2≤b0\le x^2/2\le b/2\le b, so T(K)⊆KT(K)\subseteq K. For x,y∈Kx,y\in K,

d(T(x),T(y))=∣x2−y22∣p=(x+y2)p∣x−y∣p=(x+y2)pd(x,y).(29)d(T(x),T(y))=\left|\frac{x^2-y^2}{2}\right|^p=\left(\frac{x+y}{2}\right)^p|x-y|^p=\left(\frac{x+y}{2}\right)^pd(x,y). \tag*{(29)}

(3) The canonical grading. Since x2/2≤xx^2/2\le x on [0,b][0,b], the sequence n↦Tn(x)n\mapsto T^n(x) is non-increasing, so by (29) the supremum in (9) is attained at n=0n=0 and

c(x,y)=(x+y2)p≤bp<1.c(x,y)=\left(\frac{x+y}{2}\right)^p\le b^p<1.

Proposition 3.4 therefore applies: TT is a graded-edge Rakotch contraction for the grade

w(x,y)=1−(x+y2)pw(x,y)=1-\left(\frac{x+y}{2}\right)^p

and the family φα≡cα=1−α\varphi_\alpha\equiv c_\alpha=1-\alpha. (Condition (C1) may also be checked directly: T(x)+T(y)=12(x2+y2)≤x+yT(x)+T(y)=\frac{1}{2}(x^2+y^2)\le x+y on [0,1]2[0,1]^2.)

(4) The level cuts. Put θ:=θ(α):=(1−α)1/p\theta:=\theta(\alpha):=(1-\alpha)^{1/p}, so that θ\theta decreases from 1 to 0 as α\alpha increases from 0 to 1. For x≠yx\ne y,

(x,y)∈Eα⟺(x+y2)p≤1−α⟺x+y≤2θ,(x,y)\in E_\alpha\Longleftrightarrow\left(\frac{x+y}{2}\right)^p\le1-\alpha\Longleftrightarrow x+y\le2\theta,

while every loop has grade 1 and lies in every EαE_\alpha. Consequently:

  • if θ≥b\theta\ge b, every pair of points of KK satisfies x+y≤2b≤2θx+y \le2b \le2\theta, so GαG_\alpha is complete on KK and N(α)=1N(\alpha)=1;

  • if b/2≤θ<bb/2 \le\theta< b, there exist x≠yx \ne y in KK with x+y>2θx+y > 2\theta, so N(α)≥2N(\alpha) \ge2; on the other hand x+0=x≤b≤2θx+0=x \le b \le2\theta for every x∈Kx \in K, so x,0,yx,0,y is a G~α\widetilde{G}_\alpha-chain and N(α)=2N(\alpha)=2;

  • if θ<b/2\theta< b/2, any x∈(2θ,b]x \in(2\theta,b] satisfies x+y>2θx+y > 2\theta for every y∈Ky \in K, so xx is isolated in G~α\widetilde{G}_\alpha and N(α)=∞N(\alpha)=\infty.

Hence

A=(0,1−(b/2)p],N(α)={1,0<α≤α1:=1−bp,2,α1<α≤α2:=1−(b/2)p.A=(0,1-(b/2)^p], \qquad N(\alpha)= \begin{cases} 1, & 0<\alpha\le\alpha_1:=1-b^p,\\ 2, & \alpha_1<\alpha\le\alpha_2:=1-(b/2)^p. \end{cases}

Note that α1=inf⁡{w(e):e∈E(G), e not a loop}\alpha_1=\inf\{w(e):e\in E(G),\ e\text{ not a loop}\} is exactly the ungraded threshold α0\alpha_0 of Remark 3.5, and that 0<α1<α2<10<\alpha_1<\alpha_2<1.

(5) The optimization. Since Λ(⋅,ε)\Lambda(\cdot,\varepsilon) of (28) is minimized, on each of the two branches, at the largest admissible α\alpha, it suffices to compare α1\alpha_1 and α2\alpha_2. Write B:=log⁡(D0/ε)=log⁡(bp/ε)>0B:=\log(D_0/\varepsilon)=\log(b^p/\varepsilon)>0. Using M=2p−1M=2^{p-1} and log⁡M+log⁡2=plog⁡2\log M+\log2=p\log2,

Λ(α1,ε)=Bplog⁡(1/b),Λ(α2,ε)=B+plog⁡2plog⁡(2/b).\Lambda(\alpha_1,\varepsilon)=\frac{B}{p\log(1/b)}, \qquad\Lambda(\alpha_2,\varepsilon)=\frac{B+p\log2}{p\log(2/b)}.

Setting β:=log⁡(1/b)>0\beta:=\log(1/b)>0, the inequality Λ(α2,ε)<Λ(α1,ε)\Lambda(\alpha_2,\varepsilon)<\Lambda(\alpha_1,\varepsilon) is equivalent to B(log⁡2+β)>β(B+plog⁡2)B(\log2+\beta)>\beta(B+p\log2), that is, to B>pβB>p\beta. Hence

arg min⁡α∈A Λ(α,ε)={α1,ε>b2p,α2,ε<b2p,\underset{\alpha\in A}{\operatorname{arg\,min}}\ \Lambda(\alpha,\varepsilon)= \begin{cases} \alpha_1, & \varepsilon>b^{2p},\\ \alpha_2, & \varepsilon<b^{2p}, \end{cases}

with equality of the two values at ε=b2p\varepsilon=b^{2p}.

Remark 6.12. Example 6.11 settles the objection of Remark 3.5 in both of its aspects.

(i) The optimum is interior. For ε∈(b2p,D0)\varepsilon\in(b^{2p},D_0) the minimizer is α1\alpha_1, which lies strictly inside A=(0,α2]A=(0,\alpha_2]. The extreme choices are both bad: as α↓0\alpha\downarrow0 one has cα↑1c_\alpha\uparrow1 and Λ(α,ε)→∞\Lambda(\alpha,\varepsilon)\to\infty, so the weakest threshold is useless, while for ε>b2p\varepsilon>b^{2p} the strongest admissible threshold α2\alpha_2 is strictly worse than α1\alpha_1.

(ii) The grading is not cosmetic. For ε<b2p\varepsilon<b^{2p} the graded optimum α2\alpha_2 is strictly better than the ungraded choice α0=α1\alpha_0=\alpha_1, and

lim⁡ε↓0Λ(α2,ε)Λ(α1,ε)=log⁡(1/b)log⁡(2/b)<1.\lim_{\varepsilon\downarrow0}\frac{\Lambda(\alpha_2,\varepsilon)}{\Lambda(\alpha_1,\varepsilon)} =\frac{\log(1/b)}{\log(2/b)}<1.

For b=12b=\frac{1}{2} this ratio equals 12\frac{1}{2}: the graded bound is asymptotically half the ungraded one. Since the two bounds are derived from the same theorem applied at two thresholds, the improvement is a strict gain of the graded formulation over the formulation of [12], not an artefact of a different proof.

The example is a snowflake bb-metric space: with p>1p>1 it carries the genuine constant M=2p−1>1M=2^{p-1}>1, so the factor MN(α)−1M^{N(\alpha)-1} of Theorem 6.4 is active. The interior optimum is nevertheless not an artefact of this structure. Repeating the computation in the underlying metric D(x,y)=∣x−y∣D(x,y)=|x-y|, that is with p=1p=1 and M=1M=1, leaves the combinatorics of the level cuts unchanged, replaces the crossover value b2pb^{2p} by b2b^2, and leaves the asymptotic ratio log⁡(1/b)/log⁡(2/b)\log(1/b)/\log(2/b) unchanged; the trade-off is therefore driven by the chain-length factor N(α)N(\alpha) alone and survives in an ordinary metric space. Only two values of N(α)N(\alpha) occur here, so the trade-off is resolved by comparing two branches rather than by differentiating a smooth function. Constructions with N(α)N(\alpha) taking any prescribed finite set of values may be obtained by replacing KK with a finite union of suitably scaled copies of [0,b][0,b] and deleting the edges between distinct copies; whether N(α)N(\alpha) can be made to grow along a continuum, so that the optimum is characterized by a first-order condition.

Applications

A quadratic integral equation

Let k ⁣:[0,1]2→[0,∞)k\colon[0,1]^2 \to[0,\infty) be continuous with ∫01k(t,s) ds≤1\int_0^1 k(t,s)\,\mathrm{d}s \le1 for every tt, let b∈(0,1)b \in(0,1) and let p>1p > 1. Consider the equation

x(t)=12∫01k(t,s)x(s)2 ds,t∈[0,1].(30)x(t) = \frac{1}{2}\int_0^1 k(t,s)x(s)^2\,\mathrm{d}s,\qquad t \in[0,1]. \tag*{(30)}

Proposition 7.1. Equation (30) has a unique solution x∗x^* in K:={x∈C[0,1]:0≤x≤b}K := \{x \in C[0,1] : 0 \le x \le b\}, namely x∗≡0x^* \equiv0, and for every x∈Kx \in K the Picard iterates of the right-hand side converge to x∗x^* uniformly on [0,1][0,1], with

∥Fnx−x∗∥∞p≤2(2p−1)bp(b2)pn(n≥0).\lVert\mathcal{F}^n x - x^* \rVert_\infty^p \le2(2^{p-1})b^p\left(\frac{b}{2}\right)^{pn}\qquad(n \ge0).

where F\mathcal{F} denotes the right-hand side of (30).

Proof. Let X=C[0,1]X = C[0,1] with d(x,y)=∥x−y∥∞pd(x,y) = \lVert x-y\rVert_\infty^p; as in Example 6.11, (5) holds with M=2p−1M = 2^{p-1}, the induced uniformity is that of uniform convergence, (X,d1)(X,d_1) is complete and KK is closed with D0=bpD_0 = b^p. If x∈Kx \in K then 0≤(Fx)(t)≤12∥x∥∞2≤b/2≤b0 \le(\mathcal{F}x)(t) \le\frac{1}{2}\lVert x\rVert_\infty^2 \le b/2 \le b, so F(K)⊆K\mathcal{F}(K) \subseteq K. For x,y∈Kx,y \in K and t∈[0,1]t \in[0,1],

∣(Fx)(t)−(Fy)(t)∣≤12∫01k(t,s)∣x(s)2−y(s)2∣ ds≤∥x+y∥∞2∥x−y∥∞,|(\mathcal{F}x)(t)-(\mathcal{F}y)(t)| \le\frac{1}{2}\int_0^1 k(t,s)|x(s)^2-y(s)^2|\,\mathrm{d}s \le\frac{\lVert x+y\rVert_\infty}{2}\lVert x-y\rVert_\infty,

whence d(Fx,Fy)≤(∥x+y∥∞/2)pd(x,y)d(\mathcal{F}x,\mathcal{F}y) \le(\lVert x+y\rVert_\infty/2)^p d(x,y). Take GG complete and w(x,y):=1−(∥x+y∥∞/2)pw(x,y) := 1-(\lVert x+y\rVert_\infty/2)^p. Condition (C1) holds because, using ∫01k(t,s) ds≤1\int_0^1 k(t,s)\,\mathrm{d}s \le1 and x2+y2≤b(x+y)x^2+y^2 \le b(x+y) pointwise on [0,b][0,b],

(Fx)(t)+(Fy)(t)=12∫01k(t,s)(x(s)2+y(s)2) ds≤b2∥x+y∥∞≤∥x+y∥∞,(\mathcal{F}x)(t)+(\mathcal{F}y)(t)=\frac{1}{2}\int_0^1 k(t,s)(x(s)^2+y(s)^2)\,\mathrm{d}s \le\frac{b}{2}\lVert x+y\rVert_\infty\le\lVert x+y\rVert_\infty,

so that ∥Fx+Fy∥∞≤∥x+y∥∞\lVert\mathcal{F}x+\mathcal{F}y\rVert_\infty\le\lVert x+y\rVert_\infty and hence w(Fx,Fy)≥w(x,y)w(\mathcal{F}x,\mathcal{F}y) \ge w(x,y). Thus F\mathcal{F} is a graded-edge Rakotch contraction with φα≡1−α\varphi_\alpha\equiv1-\alpha. Choosing α=α2=1−(b/2)p\alpha= \alpha_2 = 1-(b/2)^p, so that N(α)=2N(\alpha)=2 and cα=(b/2)pc_\alpha=(b/2)^p, Theorem 6.4 gives sup⁡x,y∈Kd(Fnx,Fny)≤2⋅2p−1⋅bp⋅(b/2)pn\sup_{x,y\in K}d(\mathcal{F}^n x,\mathcal{F}^n y)\le2\cdot2^{p-1}\cdot b^p\cdot(b/2)^{pn}, and Theorem 5.5(a) applies since F\mathcal{F} is continuous. The constant function 00 is a fixed point, hence is the unique one. □

Remark 7.2. The solution of (30) in KK being trivial, the interest of Proposition 7.1 lies in the rate rather than in the existence, and in fact that the rate is obtained from a graded threshold which is not the ungraded one. A non-trivial variant is obtained by adding an inhomogeneous term g∈C[0,1]g \in C[0,1] with 0≤g≤b/20 \le g \le b/2 to the right-hand side of (30); the same computation applies verbatim provided 12b2+∥g∥∞≤b\frac{1}{2}b^2+\lVert g\rVert_\infty\le b, and the fixed point is then a non-trivial solution.

A finite weighted digraph

For a finite KK the invariant N(α)N(\alpha) is computable directly: it is the diameter of the level-cut graph G~α\widetilde{G}_{\alpha}, obtainable by breadth-first search in O(∣K∣ ∣Eα∣)O(|K|\,|E_{\alpha}|) time, and the admissible set AA is determined by the ∣E(G)∣|E(G)| distinct values taken by ww. The optimization in Corollary 6.10 is then a finite comparison over at most ∣E(G)∣|E(G)| candidate thresholds, and α∗\alpha^* may be tabulated exactly. We omit the numerical illustration.

Conclusion

The framework of this paper separates two functions that the graph performs in [12]: connecting the space, and carrying the contraction data. Once separated, they are seen to be in competition, and the resulting optimization is what the grading buys. In future we plan to construct a generalized metric space, a graded graph and a mapping satisfying Assumption 5.1 for which α↦N(α)\alpha\mapsto N(\alpha) is unbounded on AA and takes infinitely many values, so that the minimization in Corollary 6.10 is governed by a first-order condition rather than by a comparison of finitely many branches. Example 6.11 realizes two branches; the difficulty in realizing a continuum is that the contraction ratio c(x,y)c(x,y) of Proposition 3.4 depends on the position of the pair in the space, whereas N(α)N(\alpha) depends on the combinatorial length of chains, and coupling the two requires a graph whose edge lengths and edge grades are simultaneously prescribed.

Author Contributions All authors contributed equally and significantly in writing this paper. All authors read and approved the final manuscript.

Funding Not applicable.

Data Availability Not applicable.

Declarations

Competing interests The authors declare that they have no competing interests.

References

  1. [1]I. A. Bakhtin, The contraction mapping principle in quasimetric spaces, Funct. Anal., UI’yanovsk. Gos. Ped. Inst. 30 (1989), 26–37.
  2. [2]S. Banach, Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales, Fund. Math. 3 (1922), 133–181.DOI
  3. [3]I. Beg, A.R. Butt and S. Radojevic, Contraction principle for set valued mappings on a metric space with a graph, Computers and Math. with Applications, 60(2010), 1214-1219DOI
  4. [4]I. Beg and A.R. Butt: Fixed points of set valued graph contractions, J. Inequalities and Appl., 2013(2013):252, 7 pages
  5. [5]F. Bojor, Fixed point theorems for Reich type contractions on metric spaces with a graph, Nonlinear Anal. 75 (2012), 3895–3901.DOI
  6. [6]S. Czerwik, Contraction mappings in b-metric spaces, Acta Math. Inform. Univ. Ostraviensis 1 (1993), 5–11.
  7. [7]J. Jachymski, The contraction principle for mappings on a metric space with a graph, Proc. Amer. Math. Soc. 136 (2008), 1359–1373.DOI
  8. [8]J. J. Nieto and R. Rodríguez-López, Contractive mapping theorems in partially ordered sets and applications to ordinary differential equations, Order 22 (2005), 223–239.DOI
  9. [9]E. Rakotch, A note on contractive mappings, Proc. Amer. Math. Soc. 13 (1962), 459–465.DOI
  10. [10]A. C. M. Ran and M. C. B. Reurings, A fixed point theorem in partially ordered sets and some applications to matrix equations, Proc. Amer. Math. Soc. 132 (2004), 1435–1443.DOI
  11. [11]S. Reich and A. J. Zaslavski, A fixed point result in generalized metric spaces, J. Anal. 30 (2022), 1467–1473.DOI
  12. [12]S. Reich and A. J. Zaslavski, A fixed point result in generalized metric spaces with graphs, Ann. Acad. Rom. Sci. Ser. Math. Appl. 18 (2026), no. 1, 9–18.DOI

Paper details

vlnc:W_saw68kfb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents