On quantitative versions of theorems due to F. E. Browder and R. Wittmann (Q624339)

The paper under review is another case study in the general program of `proof mining', that is, of logically analyzing proofs with the aim of extracting new (typically effective) information hidden in the proofs. A comprehensive reference for proof mining is the author's book [Applied proof theory. Proof interpretations and their use in mathematics. Berlin: Springer (2008; Zbl 1158.03002)]. The main results of the paper are uniform quantitative versions of two important theorems in metric fixed-point theory of nonexpansive mappings in Hilbert spaces, due to \textit{F. E. Browder} [Arch. Ration. Mech. Anal. 24, 82--90 (1967; Zbl 0148.13601)] and \textit{R. Wittmann} [Arch. Math. 58, No.~5, 486--491 (1992; Zbl 0797.47036)]. Let \(X\) be a Hilbert space, \(C\subseteq X\) a bounded convex closed subset, \(U:C\to C\) a nonexpansive mapping and \(u_0\in C\). For any \(t\in (0, 1)\), the mapping \(U_t(x) := tU(x) + (1-t)u_0\) is a strict contraction, hence it has a unique fixed point \(u_t\). Browder's theorem states that \((u_t)\) converges strongly, as \(t\to 1\), to \(P_{\text{Fix}(T)}u_0\), the fixed point of \(U\) that is closest to \(u_0\). In particular, if we define \(x_n := u_{1-\frac1{n+1}}\), then \(\displaystyle \lim_{n\to\infty}x_n=P_{\text{Fix}(T)}u_0\). Wittmann's theorem says that, under suitable conditions on a sequence of scalars \((\lambda_n)\) in \([0,1]\), including the case \(\lambda_n:= \frac{1}{n+1}\), the so-called Halpern iteration \(x_{n+1}:= \lambda_{n+1}u_0+(1-\lambda_{n+1})U(x_n)\) converges strongly to \(P_{\text{Fix}(T)}u_0\). While one cannot expect to get effective rates of convergence for the sequences \((x_n)\) in the above theorems, logical metatheorems developed by the author [Trans. Am. Math. Soc. 357, No.~1, 89--128 (2005; Zbl 1079.03046)] guarantee the extractability of effective bounds on the no-counterexample interpretation due to \textit{G. Kreisel} [J. Symb. Log. 16, 241--267 (1951; Zbl 0044.00302); J. Symb. Log. 17, 43--58 (1952; Zbl 0046.00701)] of the Cauchy property. This was popularized recently under the name of rate of `metastability' by \textit{T. Tao} [Ergodic Theory Dyn. Syst. 28, No.~2, 657--688 (2008; Zbl 1181.37004)]. Thus, a rate of metastability of a Cauchy sequence \((x_n)\) is a computable functional \(\Phi:{\mathbb N}\times{\mathbb N}^{\mathbb N}\to{\mathbb N}\) satisfying \[ \forall k\in{\mathbb N}\,\forall g : {\mathbb N}\to{\mathbb N}\, \exists N\leq \Phi(k,g)\,\forall i,j\in[N, N + g(N)] \,\,\left(\|x_i-x_j\|< 2^{-k} \right). \] The author extracts explicit and highly uniform rates of metastability from two proofs of Browder's theorem, the original one, using weak sequential compactness and projection arguments, and a second, elementary, one due to \textit{B. Halpern} [Bull. Am. Math. Soc. 73, 957--961 (1967; Zbl 0177.19101)]. Logical analysis of Browder's proof is adapted to get a rate of metastability for Wittmann's theorem. In the final section of the paper the author discusses the situation that results in the elimination of weak compactness in the case of Browder's proof and outlines the procedure to be applied in the general case where such an elimination might no longer be possible.