Pi and the AGM: Exercises 1.1

Exercise 1. By definition, we have

$$\begin{align}a_{n+1} &= \frac{a_{n}+b_{n}}{2} \\ b_{n+1} &= \sqrt{a_n b_n} \\ c_{n+1} &= \frac{a_n-b_n}{2}\end{align}$$

Hence $$a_n = \frac{a_n+b_n}{2} + \frac{a_n-b_n}{2} = a_{n+1} + c_{n+1}$$ and $$b_n = \frac{a_n+b_n}{2} + \frac{a_n-b_n}{2} = a_{n+1} - c_{n+1}$$ and finally $$c_n^2 = \frac{a_{n-1}^2 -2a_{n-1}b_{n-1} + b_{n-1}^2}{4} = \frac{a_{n-1}^2 + 2a_{n-1}b_{n-1} + b_{n-1}^2}{4} - a_{n-1}b_{n-1} = a_n^2 - b_n^2$$ which establishes the desired "backward recurrence": $$\begin{align}a_{n} &= a_{n+1}+c_{n+1} \\ b_{n} &= a_{n+1}-c_{n+1} \\ c_n^2& = a_n^2 - b_n^2\end{align}$$

We may prove the given formula for the negative values of $a_n,b_n,c_n$ by induction. The given formula clearly holds for $n=0$. Furthermore, if we assume that it holds up to some $n\in\mathbb N$, then we have that $$a_{-(n+1)} = a_{-n} + c_{-n} = 2^n (a_n^\ast + b_n^\ast) = 2^{n+1} a_{n+1}^\ast$$ and $$b_{-(n+1)} = a_{-n} - c_{-n} = 2^n (a_n^\ast - b_n^\ast) = 2^{n+1} c_{n+1}^\ast$$ and finally $$c_{-(n+1)} = \sqrt{a_{-(n+1)}^2 - b_{-(n+1)}^2} = 2^n (a_n^\ast + b_n^\ast) = 2^{n+1} a_{n+1}^\ast$$ which establishes the truth of the formula for $(n+1)$, and hence for all $n\in\mathbb N$ by induction.

We also have $$c_n = \frac{a_{n-1}-b_{n-1}}{2} = \frac{a_{n-1}^2-b_{n-1}^2}{2(a_{n-1} + b_{n-1})} = \frac{c_{n-1}^2}{4a_n}$$ Rewriting the quotient $c_{n-1}/2a_n$ as $c_{n-1}/(c_{n-1}+2b_{n-1})$, we can see that $c_{n-1}/2a_n < 1$, and hence $$c_n = \frac{c_{n-1}^2}{4a_n} \leq \frac{c_{n-1}}{2}$$

Finally, we need to establish the given recurrence for $a_n$ in terms of its previous two terms. Since $a_n$ is the average of $a_{n-1}$ and $b_{n-1}$, it follows that $b_{n-1}=2a_n - a_{n-1}$. Thus, we have: $$a_{n+1} = \frac{a_n+b_n}{2} = \frac{a_n+\sqrt{a_{n-1}b_{n-1}}}{2} = \frac{a_n+\sqrt{a_{n-1}(2a_n - a_{n-1})}}{2}$$ which is the desired formula.

Exercise 2. To establish that the harmonic-geometric mean of $\alpha$ and $\beta$ converges to $M(\alpha^{-1},\beta^{-1})^{-1}$, it is sufficient to observe that the sequences $(\alpha_n^{-1})$ and $(\beta_n^{-1})$ satisfy the original AGM recurrence, since this would imply that they converge quadratically to $M(\alpha_0^{-1},\beta_0^{-1})$. Sure enough, we have that $$\frac{1}{\alpha_{n+1}} = \frac{\alpha_n + \beta_n}{2\alpha_n\beta_n} = \frac{\tfrac{1}{\alpha_n}+\tfrac{1}{\beta_n}}{2}$$ and $$\frac{1}{\beta_{n+1}} = \frac{1}{\sqrt{\alpha_n\beta_n}} = \sqrt{\frac{1}{\alpha_n}\cdot \frac{1}{\beta_n}}$$ Implying that the sequences $(\alpha_n^{-1})$ and $(\beta_n^{-1})$ satisfy the AGM recurrence. Since they have initial values $\alpha_0$ and $\beta_0$, we have that they converge quadratically to $M(\alpha_0^{-1},\beta_0^{-1})$, and hence the HGM converges quadratically to $M(\alpha_0^{-1},\beta_0^{-1})^{-1}$.

Exercise 3. Let's start by showing that the quantity $\sqrt{\alpha_n\beta_n}$ is invariant. It sufficed to show that for each $n\in\mathbb N$, we have $\sqrt{\alpha_n\beta_n} = \sqrt{\alpha_{n+1}\beta_{n+1}}$. Sure enough, we can compute: $$\sqrt{\alpha_{n+1}\beta_{n+1}} = \sqrt{\frac{\alpha_n+\beta_n}{2}\cdot \frac{2\alpha_n\beta_n}{\alpha_n+\beta_n}} = \sqrt{\alpha_n\beta_n}$$ which shows that the value of $\sqrt{\alpha_{n}\beta_{n}}$ remains constant throughout the sequence.

To establish quadratic convergence, let us define a sequence $(q_n)$ by letting $q_n = \alpha_n/\beta_n$. We can easily calculate a recurrence for $q_n$ as follows: $$q_{n+1} = \frac{\alpha_{n+1}}{\beta_{n+1}} = \frac{(\alpha_n+\beta_n)(\tfrac{1}{\alpha_n} + \tfrac{1}{\beta_n})}{4} = \frac{2 + \tfrac{\alpha_n}{\beta_n} + \tfrac{\beta_n}{\alpha_n}}{4} = \frac{2 + q_n + q_n^{-1}}{4}$$ As a matter of fact, the sequence $(q_n)$ is simply the fixed-point iteration sequence for the following function: $$f(x) = \frac{2 + x + x^{-1}}{4}$$ This function has a single fixed-point at $x=1$ and we can observe that it is a quadratically attracting fixed point by noticing that $f'(1) = 0$. Furthermore, the range of $f$ for $x\in (0,\infty)$ lies within $[1,\infty)$, and for all $x\in [1,\infty)$, we have that $f(x) \leq \tfrac{1}{4}(x-1)+1$, entailing that all of $(0,\infty)$ lies within the basin of attraction of this fixed point. Hence, we have that $q_n\to 1$ quadratically.

We have already commented that $\sqrt{\alpha_n\beta_n}=c$ is constant, implying that $q_n = \alpha_n^2/c^2 \to 1$, and therefore $\alpha_n\to c$ as $n\to\infty$. By similar reasoning we can also conclude that $\beta_n\to c$ as $n\to\infty$. We have thus established that $(\alpha_n)$ and $(\beta_n)$ both converge, and that they converge to the same value. We may finally establish quadratic convergence by definition through the following manipulation: $$\lim_{n\to\infty}\frac{\alpha_{n+1}-c}{(\alpha_n - c)^2} =\lim_{n\to\infty} \frac{1}{2}\frac{(\sqrt{\alpha_n}-\sqrt{\beta_n})^2}{(\alpha_n-\sqrt{\alpha_n\beta_n})^2} = \lim_{n\to\infty} \frac{1}{2\alpha_n} = \frac{1}{2c}$$ showing by definition that $\alpha_n\to c$ quadratically. A similar manipulation also shows that $\beta_n\to c$ quadratically by definition, completing the proof.

Exercise 4. We are tasked with proving the following facts, where $R$ is the right half-plane, i.e. the region with $\Re > 0$:

1. The AGM is well-defined and quadratically convergent on $R$
2. $g(z)$ is well-defined and its product is quadratically convergent on $R$
3. The convergence is uniformly quadratic on compact sets, in both cases
4. We have $g(z) = M(1,z)$ on $R$

Firstly, we may take the square-root function $\sqrt{-}$ on $R$ to be a branch that sends $R\to R$ by defining $\sqrt{re^{i\vartheta}} = \sqrt{r} e^{i\vartheta/2}$ for $\vartheta\in (-\pi/2, \pi/2)$. Furthermore, by this definition, we also have that $\sqrt{zw}\in R$ for all $z,w\in R$, making $R$ closed under geometric means. Of course, $R$ is a convex region, so it is also closed under arithmetic means. This makes the AGM a well-defined (though not necessarily convergent) iteration with values in $R$.

Next we will observe that each iteration of the AGM can only increase the minimum real part between the two simultaneous terms of the sequence. That is, if we define $$(z', w') = f(z,w) = (\tfrac{z+w}{2}, \sqrt{zw})$$ then we have $$\min(\Re(z'),\Re(w')) \geq \min(\Re(z),\Re(w))$$ It is clear why $\Re(z') \geq \min(\Re(z),\Re(w))$, since its real part is the average of $\Re(z)$ and $\Re(w)$. To see why this is also true of $\Re(w')$, it helps to express $z,w$ in polar coordinates. If $z=r_1e^{i\vartheta_1}$ and $w=r_2e^{i\vartheta_2}$, then we have that $$\Re(w') = \sqrt{r_1 r_2}\cos\tfrac{\vartheta_1+\vartheta_2}{2}$$ Note that the cosine function is concave on $(-\pi/2,\pi/2)$, and hence also log-concave. This implies that $$\Re(w') = \sqrt{r_1 r_2}\cos\tfrac{\vartheta_1+\vartheta_2}{2}\geq \sqrt{r_1r_2\cos\vartheta_1\cos\vartheta_1}$$ The RHS here is just $\sqrt{\Re(z)\Re(w)}$ and hence $\geq \min(\Re(z),\Re(w))$. Thus, we have established the desired property: $$\min(\Re(z'),\Re(w')) \geq \min(\Re(z),\Re(w))$$ Notice as well that $\max(|z'|,|w'|) \leq \max(|z|, |w|)$ due to the triangle inequality and the fact that $|\sqrt{zw}| = \sqrt{|z|\cdot |w|}$. So we have that with each iteration of the AGM on $R$, the minimum real part of the terms cannot get any smaller, and the maximum norm of the terms cannot get any bigger. That is, if we define $m_n = \min(\Re(a_n),\Re(b_n))$ and $M_n = \max(|a_n|,|b_n|)$, then we have that $(m_n)$ is monotone increasing and $(M_n)$ is monotone decreasing.

Let's make an elementary geometrical observation. If $z,w$ are two numbers in $\mathbb C$ with argument in the interval $(-\pi/4,\pi/4)$, it follows that $|z-w| < |z+w|$. (To see why, treat $z$ and $w$ as vectors and note that their dot product must be positive, because the angle between them is less than $\pi/2$.) Consequently, for any two $z,w\in R$, we have that $|\sqrt{z}-\sqrt{w}| < |\sqrt{z} + \sqrt{w}|$. Therefore: $$|z'-w'| = \tfrac{1}{2}|\sqrt{z}-\sqrt{w}|^2 \leq \tfrac{1}{2}|\sqrt{z}-\sqrt{w}|\cdot|\sqrt{z}+\sqrt{w}| = \tfrac{1}{2}|z-w|$$ This implies that the difference between the simultaneous terms of the AGM recurrence converges to zero at least geometrically, since it is at least halved with each iteration, as evidenced by this bound. We can use this, in conjunction with our previous observation about the minimum real part and maximum norm over the course of the AGM sequence, to prove convergence. Using the reverse triangle inequality, one can establish the bound $|M_n-m_n|\leq |a_n - b_n|$. Consequently, if we define a sequence of rectangular regions $K_n$ as follows: $$K_n = [m_n, M_n]\times \Big[-\sqrt{M_n^2-m_n^2}, ~ \sqrt{M_n^2-m_n^2}\Big] \subset\mathbb R^2$$ then we have that $a_n,b_n\in K_n$ for all $n\in\mathbb N$, the sequence of regions $(K_n)$ is nested, and the lengths and widths of these rectangular regions tends to zero as $n\to\infty$, as a result of $|M_n-m_n| \leq |a_n - b_n| \to 0$. This implies that $(a_n)$ and $(b_n)$ both converge, and that they converge to the same limit. Hence, we have established convergence of the AGM.

To strengthen this to quadratic convergence, let us use the following algebraic identity about the terms of the AGM, which follows directly from the recurrence and is mentioned in the chapter: $$a_{n+1}-b_{n+1} = \frac{1}{2}\Big(\frac{a_n-b_n}{\sqrt{a_n}+\sqrt{b_n}}\Big)^2$$ which can be rearranged to $$\frac{a_{n+1}-b_{n+1}}{(a_n-b_n)^2} = \frac{1}{2}\frac{1}{(\sqrt{a_n}+\sqrt{b_n})^2}$$ Since $a_n$ and $b_n$ converge to the same value $\in R$ as $n\to\infty$, we have that $\sqrt{a_n}+\sqrt{b_n}$ converges to a nonzero complex number, and so the RHS of this equality converges as $n\to\infty$, implying quadratic convergence by definition. Note that we can also easily deduce uniform quadratic convergence on compact sets from this property. For if $K\subset R$ is compact, we have that $$m = \min_{z\in K}\Re(z) \in (0,\infty)$$ and $$M = \max_{z\in K} |z|\in (0,\infty)$$ both exist. This gives easy positive upper and lower bounds on the magnitude of the limit of the quantity $\sqrt{a_n}+\sqrt{b_n}$, namely an upper bound of $2\sqrt{M}$ and a lower bound of $2\sqrt{m}$. Since these upper and lower bounds yield positive upper and lower bounds on the magnitude of the constant of quadratic convergence that depend only on the compact region $K$, we have uniform quadratic convergence as desired.

Next, let's consider the function $g(z)$ as defined in the chapter. Define $(a_n),(b_n)$ via the usual AGM recurrence with initial values $a_0 = 1$ and $b_0 = k_0 = z$. We then have that $$M(1,k_0) = M(a_0, b_0) = M(1,k_{N+1})\cdot\prod_{n=0}^N \frac{1+k_n}{2}$$ by applying $n$ times the functional equation for $f(z) = M(1,z)$. Applying the homogeneity of $M$ again, we have $$M(1,k_0) = \frac{1}{a_{N+1}}\cdot M(a_{N+1},b_{N+1})\cdot\prod_{n=0}^N \frac{1+k_n}{2}$$ Of course, we also know that $M(a_i,b_i)=M(a_j,b_j)$ for any $i,j\in\mathbb N$, hence we can cancel $M(1,k_0)$ on the LHS with $M(a_{N+1},b_{N+1})$ on the RHS, and hence: $$a_{N+1} = \prod_{n=0}^N \frac{1+k_n}{2}$$ This proves immediately that the infinite product definition for $g$ converges quadratically, since $(a_n)$ converges quadratically, as proven above. The uniform quadratic convergence of $g$ on compact sets also follows directly from the uniform quadratic convergence of the AGM on compact sets, since the partial products agree exactly with the elements of $(a_n)$ for the given initial conditions $(a_0,b_0)=(1,z)$. The analyticity of $g$ follows from an elementary theorem of complex analysis which states that when the sum $|1-f_n(z)|$ converges uniformly on compact subsets of an open set $U$ for some sequence of analytic functions $f_n$, then the infinite product of the $f_n$ converges uniformly to an analytic function on compact subsets of $U$ (and inductively, we know each $k_n$ is an analytic function of $z\in R$). We also have $g(z) = M(1,z)$, completing the exercise (finally!).