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!