# nth-order generalizations of the arithmetic-geometric mean

The arithmetic-geometric mean,

$a_{k+1}=\frac{a_k+b_k}{2} \quad b_{k+1}=\sqrt{a_k b_k}$

is one of the celebrated discoveries of Gauss, who found out that it is equivalent to computing a (complete) elliptic integral (which is a special case of the Gauss hypergeometric function ${}_2 F_1$).

I have been wondering if nth-order generalizations of the iteration,

$a_{k+1}=\frac{a_k+b_k}{n} \quad b_{k+1}=\sqrt[n]{a_k b_k}$

have ever been systematically studied. I've seen this paper by Borwein, but have had trouble searching for other papers. In particular, I'm interested if the coupled sequences also have a common limit, and if so, whether the limit is expressible as a hypergeometric function (or generalizations like those of Appell or Lauricella).

Another possible generalization I thought involves $n$ variables and makes use of the elementary symmetric polynomials. To use $n=4$ as an example:

$a_{k+1}=\frac{a_k+b_k+c_k+d_k}{4}$

$b_{k+1}=\sqrt{\frac{a_k b_k+a_k c_k+a_k d_k+b_k c_k+b_k d_k+c_k d_k}{3}}$

$c_{k+1}=\sqrt[3]{\frac{{a_k b_k c_k}+{a_k b_k d_k}+{a_k c_k d_k}+{b_k c_k d_k}}{2}}$

$d_{k+1}=\sqrt[4]{a_k b_k c_k d_k}$

Would these four sequences (and in general the $n$ sequences) tend to a common limit $F(a_0,b_0,c_0,d_0,\dots)$ like in the $n=2$ case, and if so, are they expressible in terms of known functions?

EDIT

Taking into account Darsh Ranjan's comments, I realized that what I should be looking at instead is the generalization whose denominators are binomial coefficients (thus, the general form $\sqrt[j]{\frac{e_j}{\binom{n}{j}}}$, for $j=1\dots n$ where $e_j$ is the jth elementary symmetric polynomial). The case $n=4$ now looks like

$a_{k+1}=\frac{a_k+b_k+c_k+d_k}{4}$

$b_{k+1}=\sqrt{\frac{a_k b_k+a_k c_k+a_k d_k+b_k c_k+b_k d_k+c_k d_k}{6}}$

$c_{k+1}=\sqrt[3]{\frac{{a_k b_k c_k}+{a_k b_k d_k}+{a_k c_k d_k}+{b_k c_k d_k}}{4}}$

$d_{k+1}=\sqrt[4]{a_k b_k c_k d_k}$

So, still the same question: is there a common limit, and if so, is the limit expressible in terms of known functions?

-
Have you worked through any examples? If you get a numerical limit, there are places where you can look it up to see whether it's a "recognizable" number. –  Gerry Myerson Sep 3 '10 at 5:45
It's easy to see that your first example can have no common limit but zero when n isn't 2: (a, b) = ((a+b)/n, (ab)^(1/n)) immediately implies a = (n-1)a, so a is 0 unless n-1 = 1 (i. e., n = 2). Then of course b = 0 from the second component. –  Darsh Ranjan Sep 3 '10 at 6:18
J. M. - not at all. I'm guessing there are lots of interesting generalizations of the AGM (not that I know anything about them). My point was just that the particular "generalizations" you chose don't seem very relevant. Actually, I think your second set of sequences becomes more interesting if you just change the denominators from (4,3,2) to (4,6,4). (Note that if the sequences have a common limit x, then the next iterate of (x,x,x,x) had better be (x,x,x,x).) –  Darsh Ranjan Sep 3 '10 at 7:49
Does anyone have a reference for Gauss's proof (or a modern version) of the statement about elliptic integrals? –  Will Sawin Nov 14 '11 at 21:39
Or I could just find it myself. Since people upvoted this comment, presumably they care: en.wikipedia.org/wiki/Landen%27s_transformation. One just repeatedly applies this and then uses the formula for the circumference of a circle. If there is some integral representation for this mean, it would presumably come from a similar type of transformation. Has anyone checked that it's not the surface area of an ellipsoid in $n$ dimensions? –  Will Sawin Nov 15 '11 at 4:28

You want Maclaurin's inequality. Given $n$ positive numbers $a_1, a_2,\dots,a_n$, write $$(x+a_1)(x+a_2)\cdots(x+a_n) = x^n + S_1x^{n-1} + \cdots + S_{n-1}x + S_n,$$ so $S_i$ is the $i$-th elementary symmetric function of $a_1,\dots,a_n$. For $i = 1,\dots,n$, set $A_i = S_i/\binom{n}{i}$. When $n = 2$, $A_1 = (a_1+a_2)/2$ and $A_2 = a_1a_2$. Maclaurin's inequality is that $$A_1 \geq \sqrt{A_2} \geq \sqrt[3]{A_3} \geq \cdots \geq \sqrt[n]{A_n},$$ where the inequality signs are all strict unless $a_1,\dots,a_n$ are all equal. The inequality of the outer terms, $A_1 \geq \sqrt[n]{A_n}$, is the arithmetic-geometric mean inequality for $n$ positive numbers.

From a list of $n$ positive numbers $a_1,\dots,a_n$ we have produced another list of $n$ positive numbers $A_1,\sqrt{A_2},\dots,\sqrt[n]{A_n}$. The construction can be repeated.

Theorem: All the terms in the list tend to the same limit.

Off the top of my head I can't recall a reference where this is proved. It was studied by Meissel in 1875 for $n = 3$.

For example, if we start with the three numbers 1, 2, 3 then after 4 iterations the three numbers we get all look like 1.9099262335 to 10 digits after the decimal point.

[Edit: Here is a proof of the common limit, based on Will Sawin's first comment below to my answer. Order the numbers $a_1,\dots,a_n$ so that $a_1 \geq \cdots \geq a_n > 0$. By Maclaurin's inequality (or really just the arithmetic-geometric mean inequality) $A_1 \geq \sqrt[n]{A_n}$ and we will bound $A_1 - \sqrt[n]{A_n}$ from above in terms of $a_1 - a_n$ by bounding $A_1$ from above and $\sqrt[n]{A_n}$ from below using just $a_1$ and $a_n$. To bound $A_1$ from above,
$$A_1 = \frac{a_1 + \cdots + a_n}{n} \leq \frac{(n-1)a_1 + a_n}{n} = a_1 - \frac{a_1 - a_n}{n}$$ and to bound $A_n$ from below we write $A_n = a_1\cdots a_n \geq a_n^n$, so $$\sqrt[n]{A_n} \geq a_n.$$ Therefore $$0 \leq A_1 - \sqrt[n]{A_n} \leq \left(a_1 - \frac{a_1 - a_n}{n}\right) - a_n = \left(1 - \frac{1}{n}\right)(a_1 - a_n).$$ Start from an $n$-tuple $(a_1,a_2,\dots,a_n)$ which is ordered so that $a_1 \geq \cdots \geq a_n > 0$ and construct the $n$-tuple $(A_1,\sqrt{A_2},\dots,\sqrt[n]{A_n})$ and keep repeating this, which produces a sequence of $n$-tuples $(a_1^{(k)},a_2^{(k)},\dots,a_n^{(k)})$ for $k = 0,1,2,\dots$, where $a_i^{(0)} = a_i$. Let's look at the sequence of first coordinates $a_1^{(k)}$. An arithmetic mean of positive numbers is bounded above by the largest number, so $a_1 = a_1^{(0)} \geq a_1^{(1)} \geq a_1^{(2)} \geq \cdots > 0$. Therefore the sequence $a_1^{(k)}$ converges as $k \rightarrow \infty$. (The limit is positive because the sequence of last coordinates $a_n^{(k)}$ is non-decreasing and $a_1^{(k)} \geq a_n^{(k)} \geq a_n^{(0)} = a_n$ for all $k$.) The above calculation shows $$0 \leq a_1^{(k)} - a_n^{(k)} \leq \left(1 - \frac{1}{n}\right)(a_1^{(k-1)} - a_n^{(k-1)}),$$ so $0 \leq a_1^{(k)} - a_n^{(k)} \leq (1 - 1/n)^k(a_1 - a_n)$. Letting $k \rightarrow \infty$ we see the sequence of last coordinates $a_n^{(0)},a_n^{(1)},a_n^{(2)},\dots$ converges to the limit of the sequence of first coordinates $a_1^{(0)}, a_1^{(1)}, a_1^{(2)},\dots$. Since $a_1^{(k)} \geq a_i^{(k)} \geq a_n^{(k)}$, each intermediate sequence $a_i^{(0)},a_i^{(1)},a_i^{(2)},\dots$ converges to the same limit. ]

-
Nice, this is my first time to hear about this generalization of the AM-GM inequality. Thanks KConrad! You wouldn't happen to know anything about convergence rate now, would you? (Though experimentation shows that it never takes more than six iterations for 20 digit accuracy for positive real inputs; I haven't done tests for complex inputs). –  J. M. Sep 3 '10 at 19:46
Unfortunately, as I wrote in my answer above, I can't remember where I saw the proof that the iteration converges. If you can find such a reference then I am sure the proof will show you why the convergence is fast, e.g., perhaps after some specific number of iterations the difference between the largest and smallest number should be cut down by at least a factor of 2. Consider posting a new question asking for a reference on the convergence. –  KConrad Sep 5 '10 at 2:06
If you don't care about getting a good bound, finding a proof isn't very hard. Suppose $x$ and $y$ are the smallest and largest values of $a_i$, with $d=y−x$. We want to bound $A_1-\sqrt[n]{A_n}$ as a function of $d$, which we can do by just noticing that $A_1\leq y-d/n$ and $A_n\geq x^n$. Therefore, $d$ decreases at least exponentially, and they all have the same limit. –  Will Sawin Nov 14 '11 at 18:04
If you want an estimate of the convergence speed, the following argument can probably be made rigorous: Let $a_i=a+\epsilon\delta_i$ for small $\epsilon$.We can write the arithmetic mean as $a+\epsilon \sum_i \delta_i/n$ and all the other means as $a+\epsilon \sum_i \delta_i/n+O(\epsilon^2)$, using their Taylor series ,so one can write the second iteration in terms of the first with $\epsilon'=O(\epsilon^2)$ –  Will Sawin Nov 14 '11 at 21:07

Gauss's hypergeometric formula for the AGM can also be interpreted in terms of a complete elliptic integral $\int_0^{\pi/2} \phantom. d\theta / \sqrt{a^2 \cos^2 \theta + b^2 \sin^2 \theta}$. There's a remarkable generalization to complete hyperelliptic integrals in genus 2 arising from a four-variable AGM: $$(a,b,c,d) \mapsto \left( \frac14(a+b+c+d), \frac12\bigl(\sqrt{ab}+\sqrt{cd}\phantom.\bigr), \frac12\bigl(\sqrt{ac}+\sqrt{bd}\phantom.\bigr), \frac12\bigl(\sqrt{ad}+\sqrt{bc}\phantom.\bigr) \right)$$ (whose specialization $a=b$, $c=d$ recovers the usual AGM). One source available online is

Jarvis, Frazer: Higher genus arithmetic-geometric means, Ramanujan J. 17 (2008), 1–17.

-
Wow! I haven't looked at this subject in quite a while, but I'll try to grab that paper. Thanks a lot! –  J. M. Nov 15 '11 at 16:25
See also Bost (Jean-Benoît) and Mestre (Jean-François), Moyenne arithmético-géométrique et périodes des courbes de genre 1 et 2, Gaz. Math. 38 (1988), 36–64. –  Chandan Singh Dalawat Nov 27 '11 at 4:46

You may want to check a book by J.M. Borwein and P.B. Borwein titled "Pi and the AGM". The convergence is quadratic in the sense that the number of settled digits doubles in every turn in the long run. AGM of 2 numbers leads to elliptic functions but for three or more numbers the problem seems open.

-