Let $f(x) = 1/(1-x)$. We can interpret this as the generating function of an infinite list of $1$s: $(1, 1, 1, \cdots)$.

Now, let's consider $(f \circ f \circ f)(x)$. We first compute $(f \circ f)(x)$, and use this to compute $f \circ f \circ f$.

\begin{align*} &(f \circ f)(x) = \frac{1}{1 - \frac{1}{1-x}} \\ &= \frac{1}{\frac{(1 - x) - 1}{1-x}} = \frac{1-x}{-x} = \frac{x-1}{x} = 1 - \frac{1}{x} \\ \end{align*}

\begin{align*} &(f \circ f \circ f)(x) = (f \circ f)(f(x)) = 1 - \frac{1}{f(x)} = 1 - (1 - x) = x \end{align*}

What is going on? It's cool that $f^{\circ 3} = id$, but I don't have an explanation for this. I lose the ability to interpret this as a generating function at step $(2)$: When we compute $f \circ f= 1 - 1/x$, it's unclear to me what this represents.

I have an explanation, but it's not very enlightening. We can consider $f$ as a mobius transform: $f(z) = (0\cdot z + 1)/(-z+1)$. This gives the matrix $F$ such that $F^3 = I$. So there should be some complex analytic explanation that I am unable to divine.

$$ F = \begin{bmatrix} 0 & 1 \\ -1 &1 \end{bmatrix}; \quad F^3 = -I \underset{\small{\text{(projectively)}}}{\simeq} I $$

I was hoping to view either some Riemann sphere-based explanation (I don't know this very well) or a combinatorial explanation of the above phenomenon.

  • 3
    $\begingroup$ $f(f(x)) = 1-1/x$ is not analytic near $x=0$, how would you interpret that as a generating function? $\endgroup$ – Martin R Jun 10 at 13:12
  • 2
    $\begingroup$ Composition of generating functions does not deal well with constant term. For example, the representation by substitution that Combinatorial species offers for composition requires a zero constant term(Probably to avoid trying to put structure of what is not there). Check Bergeron's Combinatorial Species book. $\endgroup$ – Phicar Jun 10 at 15:07
  • 1
    $\begingroup$ There might be something here if we categorify - something in the vein of seven trees in one (see Baez week 202 for a blog post about it). $\endgroup$ – runway44 Jul 18 at 3:43

Here are some interpretations in the context of Möbius transformations, i.e. of the holomorphic automorphism of the extended complex plane (or Riemann sphere). I'll use the notation $f^{[n]}$ for the $n$-th iteration of $f$.

A quick way to see that $f^{[3]} = id$ is the following: The Möbius transformation $f(z) = 1/(1-z)$ maps the points $0, 1, \infty$ to $1, \infty, 0$, respectively, i.e. those three points are permuted cyclically. It follows that $f^{[3]}$ fixes these points. Since a Möbius transformation is uniquely determined by the image of three distinct points, $f^{[3]} = id$.

Another way is to use the classification of Möbius transformations. (See also John Olsen: The Geometry of Möbius Transformations for a nice overview). $$ f(z) = \frac{0z + 1}{-1z + 1} $$ has $\operatorname{tr}^2(f) = (0+1)^2 = 1$, so that it is an elliptic transform. Elliptic transformations are conjugate to a rotation $z \mapsto \lambda z$ with the same (squared) trace: $$ \lambda + \frac 1 \lambda + 2 = \operatorname{tr}^2(f) = 1 \\ \implies \lambda^2 + \lambda + 1 = 0 \\ \implies \lambda^3 = 1 \, , \, \lambda \ne 1 \, . $$ So $f$ is conjugate to a rotation by a third root of unity, and that implies $f^{[3]} = id$.

That conjugation can also be computed explicitly. The fixed points of $f$ are roots of $z^2-z+1=0$ which are $$ z_{1, 2} = \frac 12 (1 \pm i \sqrt 3) \, . $$ It follows that with $$ T(z) = \frac{z-z_1}{z-z_2} $$ the “conjugate” Möbius transformation $g = T \circ f \circ T^{-1}$ has the fixed points $0$ and $\infty$ and therefore is a rotation: $$ T(f(z)) = \lambda T(z) $$ for some constant $\lambda \in \Bbb C$. For $z = \infty$ we get $$ -\frac{z_1}{z_2} = T(f(\infty)) = \lambda T(\infty) = \lambda \, , $$ i.e. $\lambda = \frac 12 (-1 + i\sqrt 3)$. $\lambda$ is a third root of unity, so that $$ T(f(f(f(z)))) = T(z) \implies f^{[3]}= id \, . $$

| cite | improve this answer | |
  • $\begingroup$ Thank you for pointing me to the reference related to the mobius transform! This is a good explanation from the complex analysis perspective :D. I am still holding out hope for a purely combinatorial explanation, however. $\endgroup$ – Siddharth Bhat Jun 10 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.