Unexpected application of cosines

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
4	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
8	Dominater069	154
8	nor	154

Hi everyone!

This blog is inspired by some contestant solutions to 104234F - Palindromic Polynomial. In short, problem asks you to find a polynomial such that $$$A(x_i) = y_i$$$ for several given pairs $$$(x_i, y_i)$$$, and the coefficients of $$$A(x)$$$ read the same left-to-right and right-to-left (i.e., they form a palindrome). The intended solution utilizes the fact that for such polynomial, it always holds that

$$$ A(x) = x^n A(x^{-1}), $$$

as $$$x^n A(x^{-1})$$$ is exactly the polynomial $$$A(x)$$$ with reversed coefficients (assuming the degree is $$$n$$$).

Representing palindromic polynomials with polynomials in $$$x+\frac{1}{x}$$$

Several solutions from contestants, however, relied on a different criterion for $$$A(x)$$$. Rather than using the identity above, participants found out that palindromic polynomials can always be represented as

$$$ A(x) = x^{d} B\left(x+\frac{1}{x}\right), $$$

when its degree $$$2d$$$ is even, or as

$$$ A(x) = x^{d} (1+x) B\left(x+\frac{1}{x}\right), $$$

when its degree $$$2d+1$$$ is odd. In both cases, $$$B(x)$$$ is a polynomial of degree $$$d$$$. This representation allows for much simpler solution, but in this blog we will talk about why it exists in the first place, rather than how to use it to solve the problem.

Thanks to ecnerwala for explaining me this approach in more detail!

Getting rid of odd degrees

First things first, we should notice that a palindromic polynomial $$$A(x)$$$ of odd degree always has a root $$$x=-1$$$, as it is an alternating sum of the polynomial's coefficients, and coefficients from the right half go into this sum with different sign from corresponding coefficients in the left half. Then, dividing $$$A(x)$$$ by $$$1+x$$$ we get a palindromic polynomial of degree $$$2d$$$ instead of $$$2d+1$$$.

This allows us to focus on the polynomials of even degree.

Representing polynomials of even degrees with $$$x^k + \frac{1}{x^k}$$$

First of all we may notice that palindromic polynomials of even degree $$$2d$$$ can always be represented as

$$$ A(x) = \sum\limits_{i=0}^d a_i (x^{d-i} + x^{d+i}) = x^d \sum\limits_{i=0}^d a_i \left(x^i + \frac{1}{x^i}\right) $$$

for some sequence $$$a_0, a_1, \dots, a_d$$$ which is easily derived from the coefficients of $$$A(x)$$$. Now we should show that the sum

$$$ \sum\limits_{i=0}^d a_i \left(x^i + \frac{1}{x^i}\right) $$$

can be rewritten as

$$$ B\left(x+\frac{1}{x}\right) = \sum\limits_{i=0}^d b_i \left(x+\frac{1}{x}\right)^i $$$

with some sequence $$$b_0, b_1, \dots, b_d$$$.

Changing basis from $$$x^k + \frac{1}{x^k}$$$ to $$$\left(x+\frac{1}{x} \right)^k$$$

Consider the sequence of Laurent polynomials (i.e. polynomials, in which negative degrees are allowed)

$$$ A_k = \left(x+\frac{1}{x}\right)^k, $$$

and another sequence of Laurent polynomials

$$$ B_k = x^k + \frac{1}{x^k}. $$$

As it turns out, these two sequences have the same linear span. What it practically means, is that every element of $$$B_k$$$ may be represented as a finite linear combination of the elements of $$$A_k$$$, and vice versa. It is somewhat trivial in one direction:

$$$ A_k = \sum\limits_{i=0}^k \binom{k}{i} x^{k-2i} = \sum\limits_{i=0}^{\lfloor k/2 \rfloor} \binom{k}{i} \left(x^{k-2i}+\frac{1}{x^{k-2i}}\right). $$$

With some special consideration for even $$$k$$$, as the middle coefficient should be additionally divided by $$$2$$$. You can represent it with lower triangular matrix with $$$1$$$ on the diagonal (except for the first row where it's $$$\frac{1}{2}$$$), which would mean that the matrix is invertible and there is, indeed, the representation for $$$B_k$$$ in terms of $$$A_k$$$ as well.

But what about cosines?

We will need a bit of complex numbers magic here. The explanation above, while technically correct, doesn't really shed any light on why it is true at all. To better understand it, consider the substitution $$$x=e^{i \theta}$$$, then one can use the explicit formula for $$$\cos \theta$$$:

$$$ \cos \theta = \frac{e^{i\theta} + e^{-i\theta}}{2}, $$$

and notice that

$$$\begin{gather} A_k = 2^k \cos^k \theta, \\ B_k = 2 \cos k \theta. \end{gather}$$$

Then, it is a well known fact that $$$\cos k \theta$$$ can be represented in terms of $$$1, \cos \theta, \cos^2 \theta, \dots, \cos^k \theta$$$. To prove it, consider the identity

$$$ e^{i\theta} = \cos \theta + i \sin \theta, $$$

then on one hand

$$$ e^{ik \theta} = \cos k \theta + i \sin k \theta, $$$

on the other hand

$$$ e^{i k \theta} = (e^{i \theta})^k = (\cos \theta + i \sin \theta)^k = \sum\limits_{j=0}^k \binom{k}{j} i^j \sin^j \theta \cos^{k-j} \theta. $$$

Now, we're only interested in the real part of the said expression, hence the one with even $$$j$$$. Using $$$\sin^2 \theta = 1 - \cos^2 \theta$$$, we get

$$$ \cos k \theta = \sum\limits_{j=0}^{\lfloor k / 2 \rfloor} \binom{k}{2j} (\cos^2 \theta - 1)^j \cos^{k-2j} \theta. $$$

Hence, if we define

$$$ T_k(x) = \sum\limits_{j=0}^{\lfloor k / 2 \rfloor} \binom{k}{2j} (x^2 - 1)^j x^{k-2j}, $$$

we can see that $$$T_k (\cos x) = \cos kx$$$. The sequence of polynomials $$$T_0, T_1, T_2, \dots$$$ defined in such way is also known as Chebyshev polynomials. In the context of our problem, it would mean that

$$$ T_k\left(\frac{x+x^{-1}}{2}\right) = \frac{x^k + x^{-k}}{2}, $$$

meaning that the desired transition could be expressed as

$$$ \sum\limits_{i=0}^d a_i \left(x^i + \frac{1}{x^i}\right) = 2 \sum\limits_{i=0}^d a_i T_i\left( \frac{x+x^{-1}}{2} \right) = B\left(x+\frac{1}{x}\right). $$$