Repeated substitution and Chebyshev polynomials

2020-01-31 (2020-01-26)

Recently, I was experimenting with a process in which we start with the polynomial $f_0(x) = x$ and obtain $f_n(x) = f_{n-1} \left(\frac{1}{s-x}\right)$ by substituting $x \mapsto \frac{1}{s-x}$, for some number $s \in \mathbb C$. By accident, I saw that both for $s=1$ and $s=-1$, $f_3 = f_0$. Of course, for $s=0$, $f_2 = f_0$ as well. This made me wonder: for which values of $s$ do we have $f_n = f_0$ for some $n>0$?

The first few polynomials

We have

\begin{aligned} f_0 &= \frac{x}{1};\\ f_1 &= \frac{1}{s-x};\\ f_2 &= \frac{s-x}{s^2 - 1 - sx};\\ f_3 &= \frac{s^2 - 1 - sx}{s^3 - 2s - (s^2 - 1)x};\\ f_4 &= \frac{s^3 - 2s - (s^2 - 1) x}{s^4 - 3 s^2 + 1 - (s^3 - 2s) x}. \end{aligned}

Now we can calculate that $f_4 = x$ means that

$s^3 - 2s - (s^2 - 1) x = (s^4 - 3 s^2 + 1) x - (s^3 - 2s) x^2$

so the terms with $x^2$ on the left hand side (these terms amount to $0$) must match the terms with $x^2$ on the right hand side (they amount to $-(s^3 - 2s)$), the terms with $x$ on the left must match the ones on the right and the same for the constant terms. This gives the following equations:

$0 = s^3 - 2s \land -(s^2 - 1) = s^4 - 3 s^2 + 1 \land s^3 - 2 s = 0,$

$s^3 - 2 s = 0 \land s(s^3 - 2s) - (s^2 - 1) = -(s^2 - 1),$

$s^3 - 2 s = 0,$

$s = 0 \lor s = \sqrt{2} \lor s = -\sqrt{2}.$

We could have expected the $s = 0$, since $f_4 = f_2(f_2)$ and if $s = 0$, $f_2 = f_0$, so $f_4(x) = f_2(f_2) = f_2(f_0) = f_0$.

More generally, if a number $d$ divides $n$, and $f_d = f_0$ for some value $s=s_0$, then $f_n = f_0$ for $s=s_0$ as well.

An easier description

Notice that in the equations above, the denominator of $f_n$ matches the numerator of $f_{n+1}$ and the term with $x$ of the denominator matches the constant term of the numerator. This provides us with an easier way to describe the polynomials $f_n$.

More formally, we can define a sequence of polynomials $g_n$ by $g_{-2} = -1$, $g_{-1} = 0$ and $g_n = s g_{n-1} - g_{n-2}$, so

\begin{aligned} g_{-2} &= -1;\\ g_{-1} &= 0;\\ g_0 &= 1;\\ g_1 &= s;\\ g_2 &= s^2-1;\\ g_3 &= s^3 - 2 s;\\ g_4 &= s^4 - 3 s^2 + 1;\\ g_5 &= s^5 - 4 s^3 + 3 s;\\ g_6 &= s^6 - 5 s^4 + 6 s^2 - 1; \end{aligned}

We will now claim that

$f_n = \frac{g_{n-1} - g_{n-2} x}{g_n - g_{n-1} x}.$

Indeed,

$f_0 = \frac{x}{1} = \frac{0 - (-1) x}{1 - 0 x} = \frac{g_{-1} - g_{-2} x}{g_0 - g_{-1} x}.$

Also, if the claim holds for $f_n$, then

$f_{n+1} = \frac{g_{n-1} - g_{n-2} \cdot \frac{1}{s-x}}{g_n - g_{n-1} \cdot \frac{1}{s-x}} =\frac{(s-x) g_{n-1} - g_{n-2}}{(s-x) g_n - g_{n-1}} =\frac{s g_{n-1} - g_{n-2} - g_{n-1} x}{s g_n - g_{n-1} - g_n x} = \frac{g_n - g_{n-1} x}{g_{n+1} - g_n x}.$

The second equality is obtained by multiplying numerator and denominator by $s - x$. This shows that the claim holds for $f_{n+1}$ as well and we conclude by induction that the claim holds for all $f_n$.

Finding a couple more values of $s$

If we want $f_n = f_0 = x$, we must have

$\frac{g_{n-1} - g_{n-2} x}{g_n - g_{n-1} x} = x,$

$g_{n-1} - g_{n-2} x = g_n x - g_{n-1} x^2,$

$g_{n-1} = 0 \land - g_{n-2} = g_n = s g_{n-1} - g_{n-2},$

$g_{n-1} = 0 \land s g_{n-1} = 0,$

$g_{n-1} = 0.$

For example, $f_5 = f_0$ iff

$0 = s^4 - 3 s^2 + s = (s^2 + s - 1)(s^2 - s - 1)$

which has solutions $s = \pm \frac{1}{2} \pm \frac{1}{2} \sqrt{5}$. It struck me that $\frac{1}{2} + \frac{1}{2} \sqrt{5}$ is exactly the diagonal length of a pentagon, whilst $\sqrt{2}$, a root of $g_{3}$, is the diagonal length of a square and $1$, a root of $g_{2}$, is the side length of a triangle, so again the distance between vertices that are two edges apart. It seems that $\cos{\frac{\pi}{n}}$ is always a root of $g_{n-1}$. We will prove this and more in the next two sections.

Chebyshev polynomials

In this section, we will show that our polynomials $g_n$ are almost equal to the so-called "Chebyshev polynomials of the second kind". Knowing this, and the way that these polynomials are defined, will provide us with a neat description of the $s$ for which of the $g_n(s) = 0$.

Firstly, recall two trigonometric identities. The angle sum identity gives

$\sin((n + 1)\theta) = \sin(\theta + n \theta) = \sin(\theta) \cos(n \theta) + \cos(\theta) \sin(n \theta),$

which we will call (1), and the product-to-sum identity gives

$2 \cos(n \theta) \sin(\theta) = \sin(n \theta + \theta) - \sin(n \theta - \theta) = \sin((n + 1) \theta) - \sin((n - 1) \theta),$

which we will call (2). Combining these, we obtain

\begin{aligned} 2 \sin((n + 1)\theta) &= 2 \sin(\theta) \cos(n \theta) + 2 \cos(\theta) \sin(n \theta)\\ &= \sin((n + 1) \theta) - \sin((n - 1) \theta) + 2 \cos(\theta) \sin(n \theta) \end{aligned}

or

$\sin((n+1) \theta) = 2 \cos(\theta) \sin(n \theta) - \sin((n - 1) \theta),$

which we will call (3).

We will now define polynomials $U_n$ by

$U_n(\cos(\theta)) = \frac{\sin((n+1) \theta)}{\sin \theta}.$

These are the so-called "Chebyshev polynomials of the second kind". It is not at all obvious that these are actually polynomials, but we will show that now. We have

$U_0(\cos(\theta)) = \frac{\sin(\theta)}{\sin(\theta)} = 1$

and, by (1),

$U_1(\cos(\theta)) = \frac{\sin(2 \theta)}{\sin(\theta)} = \frac{\sin(\theta)\cos(\theta) + \cos(\theta) \sin(\theta)}{\sin(\theta)} = 2 \cos(\theta).$

so $U_0(x) = 1$ en $U_1(x) = 2x$. Now we can use (3) to find a recurrence relation for $U_n$:

$U_n(\cos(\theta)) = \frac{\sin((n+1)\theta)}{\sin(\theta)} = \frac{2\cos(\theta) \sin(n \theta) - \sin((n - 1)\theta)}{\sin(\theta)} = 2 \cos(\theta) U_{n-1}(\theta) - U_{n-2}(\theta),$

or

$U_n(s) = 2 x U_{n-1}(s) - U_{n-2}(s).$

We can now claim that for all n,

$g_n(s) = U_n\left(\frac{s}{2}\right).$

Indeed, $g_0(s) = 1 = U_0(s)$ and $g_1(s) = s = 2 \cdot \frac{s}{2} = U_1(\frac{s}{2})$. Now, suppose the claim holds for all $g_m$ with $0 \leq m \leq n$. Then

$g_n(s) = s g_{n-1}(s) - g_{n-2}(s) = 2 \cdot \frac{s}{2} U_{n-1}\left(\frac{s}{2}\right) - U_{n-2}\left(\frac{s}{2}\right) = U_n\left(\frac{s}{2}\right).$

The zeroes of the Chebyshev polynomials

By definition, $U_{n-1}(\cos(\theta)) = \frac{\sin(n \theta)}{\sin \theta}$, so if we want $U_{n-1}(\frac{1}{2}s) = 0$ and $\frac{1}{2} s = \cos(\theta)$, we must have that $\sin(n \theta) = 0$, so $n \theta = m \pi$ for some integer $0 \leq m \leq n$. We must also have that $\sin(\theta)$ is not zero, so $0 < m < n$.

$s = 2 \cos\left(\frac{m \pi}{n}\right).$

Conclusion

To recap: we have shown that $f_0 = f_n$ if some polynomial that we defined, $g_{n-1}$, is zero in $s$. Since $g_{n-1}(s) = U_{n-1}\left(\frac{1}{2} s\right)$, this happens if $U_{n-1}\left(\frac{s}{2}\right) = 0$, which happens exactly when

$s = 2 \cos\left(\frac{m \pi}{n}\right).$