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

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

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

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

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

can be rewritten as

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)

and another sequence of Laurent polynomials

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:

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$$$:

and notice that

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

then on one hand

on the other hand

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

Hence, if we define

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

meaning that the desired transition could be expressed as