# Curious identity between the two kinds of Chebyshev polynomials

I have found, by accident, an identity that relates a sum of Chebyshev polynomials of the first kind to a Chebyshev polynomial of the second kind. It goes as follows:

Given an integer partition of $$n$$, let $$g_a$$ be the number of times $$a$$ appears in said partition.$${}^1$$ Then the following identity holds for all $$n \in\mathbb{N}$$:

$$U_n(x) = \sum_{\substack{n_i>0\\ \sum_i n_i = n}} \frac{1}{\prod_{a\in \{n_i\}} g_a!} \prod_{i=1} \frac{2}{n_i} T_{n_i}(x)\,.$$

The sum is over all integer partitions of $$n$$, the product is on all $$n_i$$'s in the partition, with repetitions.

I have a very roundabout way to prove this identity (I'll skip the details). The left hand side is obtained by contracting two symmetric traceless tensors of $$SO(4)$$. That is, letting $$|x|=|y|=1$$ and $$x,y\in \mathbb{R}^4$$ then $$(x^{i_1}\cdots x^{i_n} - \mathrm{traces}) (y_{i_1}\cdots y_{i_n} - \mathrm{traces}) \propto U_n(x\cdot y)\,.$$ The right hand side instead comes from the same contraction but in spinor notation. Namely we let $$\mathrm{x} = \left(\begin{matrix}x_3-x_4 & x_1 - i x_2 \\ x_1 + i x_2 & -x_3-x_4\end{matrix}\right)\,,\quad \bar{\mathrm{x}} = \epsilon\, \mathrm{x}\, \epsilon^T\,,$$ and $$\mathrm{y}$$ in a similar way ($$\epsilon$$ is the Levi Civita tensor). Then we introduce two dimensional spinors $$\eta,\tilde{\eta}$$ let $$\partial_{\eta^\alpha}\eta^\beta = \delta_\alpha^\beta$$ (similar for $$\tilde{\eta}$$) and finally $$(\partial_\eta \mathrm{x} \partial_{\tilde{\eta}})^n (\eta \mathrm{y}\tilde{\eta})^n \sim \sum_{\substack{n_i>0\\ \sum_i n_i = n}} \# \prod_{i} \mathrm{tr}\,((\mathrm{x}\bar{\mathrm{y}})^{n_i})\,.$$ The sum over partitions comes from a combinatoric argument. Then it's a simple exercise to show that $$\mathrm{tr}\,((\mathrm{x}\bar{\mathrm{y}})^n) \propto T_n(x\cdot y)$$.

My questions are

1. Is this identity known already?
2. If not, could you come up with some more direct argument to prove it?

$$\;{}^1$$ For example, $$(1,1,1,2,2,3)$$ is an integer partition of $$n=10$$ with $$g_1 =3,\, g_2=2,\,g_3=1$$.

Here is how to prove it with more standard methods. First of all, let me restate your identity:

Definition. Let $$\mathbb{N}=\left\{ 0,1,2,\ldots\right\}$$. A partition shall mean an integer partition, i.e., a weakly decreasing finite list of positive integers. If $$\lambda$$ is a partition and $$i$$ is a positive integer, then $$m_{i}\left( \lambda\right)$$ shall mean the number of times that $$i$$ appears as entry of $$\lambda$$. (For example, $$m_{3}\left( \left( 4,3,3,1\right) \right) =2$$ and $$m_{2}\left( \left( 4,3,3,1\right) \right) =0$$.) The size $$\left\vert \lambda\right\vert$$ of a partition is defined to be the sum of all entries of $$\lambda$$. If $$n\in\mathbb{N}$$, then a partition of $$n$$ means a partition of size $$n$$. We write "$$\lambda\vdash n$$" for "$$\lambda$$ is a partition of $$n$$".

Definition. We let $$T_n\left(x\right)$$ denote the Chebyshev polynomials of the first kind, which can be defined (e.g.) by the recurrence $$T_0\left(x\right) = 1$$ and $$T_1\left(x\right) = x$$ and $$T_{n+1}\left(x\right) = 2x T_n\left(x\right) - T_{n-1}\left(x\right)$$. We let $$U_n\left(x\right)$$ denote the Chebyshev polynomials of the second kind, which can be defined (e.g.) by the recurrence $$U_0\left(x\right) = 1$$ and $$U_1\left(x\right) = 2x$$ and $$U_{n+1}\left(x\right) = 2x U_n\left(x\right) - U_{n-1}\left(x\right)$$.

Theorem 1. For any $$n\in\mathbb{N}$$, we have $$$$U_{n}\left( x\right) =\sum_{\lambda=\left( \lambda_{1},\lambda_{2} ,\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \cdot\prod_{j=1}^{k}\left( 2T_{\lambda_{j}}\left( x\right) \right) .$$$$

To prove this, I will use two well-known generating-function identities for Chebyshev polynomials, both of which appear on the Wikipedia: $$$$\sum_{n=0}^{\infty}T_{n}\left( x\right) t^{n}=\dfrac{1-tx}{1-2tx+t^{2}} \label{darij1.eq.T-gen} \tag{1}$$$$ and $$$$\sum_{n=0}^{\infty}U_{n}\left( x\right) t^{n}=\dfrac{1}{1-2tx+t^{2} }. \label{darij1.eq.U-gen} \tag{2}$$$$ These are identities in the ring $$\left( \mathbb{Q}\left[ x\right] \right) \left[ \left[ t\right] \right]$$ of formal power series in the variable $$t$$ over the polynomial ring $$\mathbb{Q}\left[ x\right]$$. Both identities can easily be derived from the above recurrent definitions of $$T_n\left(x\right)$$ and $$U_n\left(x\right)$$.

Now, subtracting the equality $$\underbrace{T_{0}\left( x\right) } _{=1}\underbrace{t^{0}}_{=1}=1$$ from the identity \eqref{darij1.eq.T-gen}, we obtain $$$$\sum_{n=1}^{\infty}T_{n}\left( x\right) t^{n}=\dfrac{1-tx}{1-2tx+t^{2} }-1=t\cdot\dfrac{x-t}{1-2tx+t^{2}}.$$$$ Dividing both sides of this by $$t$$, we obtain $$$$\sum_{n=1}^{\infty}T_{n}\left( x\right) t^{n-1} = \dfrac{x-t}{1-2tx+t^{2}}.$$$$ Integrating both sides of this equality over $$t$$, we find \begin{align} \sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n} & =\int\dfrac {x-t}{1-2tx+t^{2}}dt\nonumber\\ & =\dfrac{1}{2}\log\dfrac{1}{1-2tx+t^{2}} \label{darij1.eq.T-ge2} \tag{3} \end{align} (as you can easily check by differentiation). (Note that this identity also appears on the Wikipedia, under the guise of $$\sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n}=\log\dfrac{1}{\sqrt{1-2tx+t^{2}}}$$, apparently because someone finds square roots simpler than division by $$2$$.)

Multiplying both sides of the equality \eqref{darij1.eq.T-ge2} by $$2$$, we obtain $$$$2\sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n}=\log\dfrac {1}{1-2tx+t^{2}}.$$$$ Hence, $$$$\log\dfrac{1}{1-2tx+t^{2}}=2\sum_{n=1}^{\infty}T_{n}\left( x\right) \dfrac{t^{n}}{n}=\sum_{n=1}^{\infty}2T_{n}\left( x\right) \dfrac{t^{n}}{n},$$$$ so that $$$$\dfrac{1}{1-2tx+t^{2}}=\exp\left( \sum_{n=1}^{\infty}2T_{n}\left( x\right) \dfrac{t^{n}}{n}\right) .$$$$ Hence, \eqref{darij1.eq.U-gen} becomes $$$$\sum_{n=0}^{\infty}U_{n}\left( x\right) t^{n}=\dfrac{1}{1-2tx+t^{2}} =\exp\left( \sum_{n=1}^{\infty}2T_{n}\left( x\right) \dfrac{t^{n}} {n}\right) . \label{darij1.eq.T-ge3} \tag{4}$$$$

Now, we recall one of the staple formulas of algebraic combinatorics (probably in EC or Wilf or similar sources):

Proposition 2. Let $$R$$ be a commutative $$\mathbb{Q}$$-algebra (for example, $$\mathbb{Q}$$ or $$\mathbb{Q}\left[ x\right]$$). Let $$b_{1},b_{2},b_{3} ,\ldots\in R$$ and $$c_{0},c_{1},c_{2},\ldots\in R$$ be such that $$$$\sum_{n=0}^{\infty}c_{n}t^{n}=\exp\left( \sum_{n=1}^{\infty}b_{n}\dfrac {t^{n}}{n}\right)$$$$ in the ring $$R\left[ \left[ t\right] \right]$$ of formal power series. Then, $$$$c_{n}=\sum_{\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \cdot\prod_{j=1}^{k}b_{\lambda_{j}}$$$$ for each $$n\in\mathbb{N}$$.

Proof of Proposition 2. An infinite sequence $$\left( k_{1},k_{2} ,k_{3},\ldots\right) \in\mathbb{N}^{\infty}$$ of nonnegative integers will be called a weak composition if all but finitely many $$i\geq1$$ satisfy $$k_{i}=0$$. There is a bijection \begin{align} \left\{ \text{partitions}\right\} & \rightarrow\left\{ \text{weak compositions}\right\} ,\nonumber\\ \lambda & \mapsto\left( m_{1}\left( \lambda\right) ,m_{2}\left( \lambda\right) ,m_{3}\left( \lambda\right) ,\ldots\right) \label{darij1.pf.p2.1} \tag{5} \end{align} (since any partition $$\lambda$$ is uniquely determined by the numbers $$m_{1}\left( \lambda\right) ,m_{2}\left( \lambda\right) ,m_{3}\left( \lambda\right) ,\ldots$$ which record how often each positive integer appears in $$\lambda$$). We notice that any partition $$\lambda$$ satisfies $$$$1m_{1}\left( \lambda\right) +2m_{2}\left( \lambda\right) +3m_{3}\left( \lambda\right) +\cdots=\left\vert \lambda\right\vert \label{darij1.pf.p2.2} \tag{6}$$$$ (because $$\left\vert \lambda\right\vert$$ is the sum of all entries of $$\lambda$$, while $$1m_{1}\left( \lambda\right) +2m_{2}\left( \lambda\right) +3m_{3}\left( \lambda\right) +\cdots$$ is what becomes of this sum after equal addends are bunched together). Moreover, any partition $$\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right)$$ satisfies $$$$\prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }=\prod_{j=1} ^{k}b_{\lambda_{j}} \label{darij1.pf.p2.3} \tag{7}$$$$ (for a similar reason: the product $$\prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }$$ is what will become of the product $$\prod_{j=1} ^{k}b_{\lambda_{j}}$$ if you bunch factors corresponding to equal entries of $$\lambda$$ together).

We have the following product rule (i.e., analogue of the distributivity law) for infinite products of infinite sums: If $$\left( a_{i,k}\right) _{i\geq1\text{ and }k\geq0}$$ is a family of elements of $$R\left[ \left[ t\right] \right]$$ satisfying $$a_{i,0}=1$$ for each $$i\geq1$$, then $$$$\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}a_{i,k}=\sum_{\substack{\left( k_{1},k_{2},k_{3},\ldots\right) \text{ is a}\\\text{weak composition}} }\prod_{i=1}^{\infty}a_{i,k_{i}}, \label{darij1.pf.p2.prodrule} \tag{8}$$$$ provided that everything formally converges (i.e., for each given $$N\in\mathbb{N}$$, all but finitely many pairs $$\left( i,k\right) \in\left\{ 1,2,3,\ldots\right\} ^{2}$$ satisfy $$t^N \mid a_{i,k}$$ in $$R\left[\left[t\right]\right]$$).

We have \begin{align} \sum_{n=0}^{\infty}c_{n}t^{n} & =\exp\left( \sum_{n=1}^{\infty}b_{n} \dfrac{t^{n}}{n}\right) =\prod_{n=1}^{\infty}\underbrace{\exp\left( b_{n}\dfrac{t^{n}}{n}\right) }_{\substack{=\sum_{k=0}^{\infty}\dfrac{1} {k!}\left( b_{n}\dfrac{t^{n}}{n}\right) ^{k}\\\text{(since }\exp z=\sum_{k=0}^{\infty}\dfrac{1}{k!}z^{k}\text{)}}}\nonumber\\ & \qquad \left(\text{since \exp\left(\sum_{i\in I} a_i\right) = \prod_{i\in I} \exp a_i for any family \left(a_i\right)_{i\in I}}\right) \nonumber\\ & =\prod_{n=1}^{\infty}\sum_{k=0}^{\infty}\dfrac{1}{k!}\left( b_{n} \dfrac{t^{n}}{n}\right) ^{k}=\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}\dfrac {1}{k!}\underbrace{\left( b_{i}\dfrac{t^{i}}{i}\right) ^{k}}_{=\dfrac {b_{i}^{k}t^{ik}}{i^{k}}}\nonumber\\ & \qquad\left( \text{here, we have renamed the index }n\text{ as }i\right) \nonumber\\ & =\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}\dfrac{1}{k!}\cdot\dfrac{b_{i} ^{k}t^{ik}}{i^{k}}=\prod_{i=1}^{\infty}\sum_{k=0}^{\infty}\dfrac{b_{i} ^{k}t^{ik}}{i^{k}k!}\nonumber\\ & =\sum_{\substack{\left( k_{1},k_{2},k_{3},\ldots\right) \text{ is a}\\\text{weak composition}}}\prod_{i=1}^{\infty}\dfrac{b_{i}^{k_{i}} t^{ik_{i}}}{i^{k_{i}}k_{i}!}\nonumber\\ & \qquad\left( \text{by the product rule \eqref{darij1.pf.p2.prodrule}, applied to }a_{i,k}=\dfrac{b_{i}^{k}t^{ik}}{i^{k}k!}\right) \nonumber\\ & =\sum_{\lambda\text{ is a partition}}\underbrace{\prod_{i=1}^{\infty} \dfrac{b_{i}^{m_{i}\left( \lambda\right) }t^{im_{i}\left( \lambda\right) }}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}}_{=\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \left( \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) \left( \prod_{i=1}^{\infty}t^{im_{i}\left( \lambda\right) }\right) }\nonumber\\ & \qquad\left( \begin{array} [c]{c} \text{here, we have substituted }\left( m_{1}\left( \lambda\right) ,m_{2}\left( \lambda\right) ,m_{3}\left( \lambda\right) ,\ldots\right) \\ \text{for }\left( k_{1},k_{2},k_{3},\ldots\right) \text{ in the sum, due to the bijection \eqref{darij1.pf.p2.1}} \end{array} \right) \nonumber\\ & =\sum_{\lambda\text{ is a partition}}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \left( \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) \underbrace{\left( \prod_{i=1}^{\infty}t^{im_{i}\left( \lambda\right) }\right) }_{\substack{=t^{1m_{1}\left( \lambda\right) +2m_{2}\left( \lambda\right) +3m_{3}\left( \lambda\right) +\cdots}\\=t^{\left\vert \lambda\right\vert }\\\text{(by \eqref{darij1.pf.p2.2})}}}\nonumber\\ & =\sum_{\lambda\text{ is a partition}}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \left( \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) t^{\left\vert \lambda\right\vert }. \label{darij1.pf.p2.6} \tag{9} \end{align}

Now, let $$n\in\mathbb{N}$$. Comparing coefficients of $$t^{n}$$ on both sides of the equality \eqref{darij1.pf.p2.6}, we obtain \begin{align*} c_{n} & =\underbrace{\sum_{\substack{\lambda\text{ is a partition;} \\\left\vert \lambda\right\vert =n}}}_{\substack{=\sum_{\lambda\vdash n}\\\text{(since the partitions of }n\\\text{are precisely the partitions }\lambda\\\text{with }\left\vert \lambda\right\vert =n\text{)}}}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \prod_{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\\ & =\sum_{\lambda\vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \prod_{i=1}^{\infty }b_{i}^{m_{i}\left( \lambda\right) }\\ & =\sum_{\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \underbrace{\left( \prod _{i=1}^{\infty}b_{i}^{m_{i}\left( \lambda\right) }\right) } _{\substack{=\prod_{j=1}^{k}b_{\lambda_{j}}\\\text{(by \eqref{darij1.pf.p2.3})}}}\\ & =\sum_{\lambda=\left( \lambda_{1},\lambda_{2},\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac{1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \prod_{j=1}^{k}b_{\lambda_{j}}. \end{align*} This proves Proposition 2. $$\blacksquare$$

Proof of Theorem 1. Recall the identity \eqref{darij1.eq.T-ge3}. Thus, Proposition 2 (applied to $$R=\mathbb{Q}\left[ x\right]$$ and $$c_{n} =U_{n}\left( x\right)$$ and $$b_{n}=2T_{n}\left( x\right)$$) yields that $$$$U_{n}\left( x\right) =\sum_{\lambda=\left( \lambda_{1},\lambda_{2} ,\ldots,\lambda_{k}\right) \vdash n}\left( \prod_{i=1}^{\infty}\dfrac {1}{i^{m_{i}\left( \lambda\right) }m_{i}\left( \lambda\right) !}\right) \cdot\prod_{j=1}^{k}\left( 2T_{\lambda_{j}}\left( x\right) \right)$$$$ for each $$n\in\mathbb{N}$$. This proves Theorem 1. $$\blacksquare$$

• After your proof I realized that this could be trivially generalized to general Gegenbauer polynomials by letting $U_n(x)\to G_n^{(\alpha)}(x)$ and $2T_{\lambda_j}(x) \to 2\alpha T_{\lambda_j}(x)$. Furthermore, for $\alpha = (d-2)/2$, $d\in\mathbb{N}$ I can prove it in my way too. – MannyC Feb 15 '20 at 8:23
• Why only for the canonical scaling dimension $\alpha$? There is no reason to be afraid of fractional free fields. – Abdelmalek Abdesselam Feb 15 '20 at 23:38
• I was about to show the details of my proof in a self-answer but I did not have time today. Essentially I want to express the left hand side as a contraction of $d$ dimensional, rank $n$ symmetric traceless tensors and the right hand side as traces of products of matrices belonging to the Clifford algebra in $d$ dimensions. While I believe these concepts can be generalized to any $d$, I have no rigorous way of doing so. – MannyC Feb 16 '20 at 0:12

I think I can sketch a shorter proof.

Let $$z_j = x_j+x_j^{-1}$$, and let $$p_m$$ and $$h_m$$ denote the power-sum and complete homogeneous symmetric polynomial.

Then (see e.g p.3 in this preprint) $$2 T_m(z_j/2) = p_m(x_j,x_j^{-1}) \text{ and } U_m(z_j/2) = h_m(x_j,x_j^{-1})$$

Now, we can use the Newton identities, to express $$h_m$$ in terms of the power-sum symmetric functions. This gives a relation between the $$U_m$$ and the $$T_m$$.

Looking at your formula, it is very similar to the Newton identity.

• +1. I agree this is probably the best way to understand the identity. Another relevant reference is the article "Miraculous cancellations for quantum SL2" by Francis Bonahon, arxiv.org/abs/1708.07617 – Abdelmalek Abdesselam Feb 15 '20 at 23:33
• Ah -- I actually got my proof by reverse engineering a symmetric functions argument, but I wasn't aware of you proving the necessary formulas in your preprint! – darij grinberg Feb 16 '20 at 0:55