Unexpected application of cosines

Правка en6, от adamant, 2023-03-12 14:01:40

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). $$$
Теги tutorial, cosinus, polynomials, chebyshev

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский adamant 2023-03-12 21:11:47 0 (published)
en7 Английский adamant 2023-03-12 21:11:39 13 (saved to drafts)
en6 Английский adamant 2023-03-12 14:01:40 89
en5 Английский adamant 2023-03-12 13:55:55 6437 (published)
en4 Английский adamant 2023-03-12 05:01:57 1032 Tiny change: 'r even $k$' -> 'r even $k$, as it would be additionally divided by $2$.'
en3 Английский adamant 2023-03-12 04:43:57 84 Tiny change: '.' -> 'Hi everyone!\n\n'
en2 Английский adamant 2023-03-12 04:42:59 45
en1 Английский adamant 2023-03-12 04:42:29 50 Initial revision (saved to drafts)