Extending AGM to three variables

The AGM (arithmetic-geometric mean) is the limiting value you get when you take the arithmetic and geometric means of two numbers, then take the arithmetic and geometric means of the results, over and over.

    am = lambda x, y: (x + y)*0.5
    gm = lambda x, y: (x * y)**0.5

    def agm(x, y): 
        while x != y:
            x, y = am(x, y), gm(x, y)
        return x

I wrote a three posts about the AGM last week: here, here, and here.

Yesterday I ran across a paper [1] that uses a three-variable form of the AGM. It iteratively takes the arithmetic mean of all pairs and then the geometric mean of all pairs.

    x, y, z = am(x, y), am(y, z), am(x, z)
    x, y, z = gm(x, y), gm(y, z), gm(x, z)

This process also converges, though it converges at a much slower rate than the (two-variable) AGM. Every iteration of the two-variable AGM doubles the number of correct bits in the final result. Every iteration of the three-variable AGM adds two bits to the final answer. So instead of growing exponentially, the number of correct bits grows linearly.

Could we extend this to lists of numbers of any size? Suppose we take the arithmetic mean of all pairs from the list, then the geometric mean of all pairs of arithmetic means. The problem is that the length of our lists is changing. The reason we can extend the AGM to 3 variables is that binom(3, 2) = 3. We start with a list of three numbers and we keep getting back lists of three numbers. But for n > 3, binom(n, 2) ≠ n.

Suppose we start with a list of 4 numbers. There are 6 pairs of numbers to take the arithmetic mean of. Then out of this list of 6 arithmetic means, there are 15 pairs to take the geometric mean of. We’re not in a situation directly analogous to the original AGM since our list of numbers is not of fixed size. But could we keep going anyway?

Well, sorta. Here’s Python code to implement what we described above.

    from itertools import combinations    
    def agmn(xs):
        while max(xs) > min(xs):
            ys = [am(*p) for p in combinations(xs, 2)]
            xs = [gm(*p) for p in combinations(ys, 2)]
        return xs[0]

The code works fine for lists of length 3, but it will never return if you give it longer lists.

The length of our lists is growing doubly exponentially:

    6                                                         
    15                                                        
    105                                                       
    5460                                                      
    14903070                                                  
    111050740260915                                           
    6166133456248548335768188155                              
    19010600900133834176644234577571914951562754277857057935  
    ...

(Incidentally, the numbers of above are a cataloged sequence in OEIS.)

Here’s another approach to defining an extended AGM.

We have a way to define a 3-variable AGM. If we have a list of four numbers, we could apply one step of the 3-variable AGM to every subset with three elements.

In general, we could define an n-variable AGM recursively by repeatedly taking a step of the (n-1)-variable AGM for all n subsets of size n-1.

[1] B. C. Carlson. Hidden Symmetries of Special Functions. SIAM Review , Jul., 1970, Vol. 12, No. 3 (Jul., 1970), pp. 332-345