Kvant Math Problem 1520

Let $P(x)$ and $Q(x)$ be polynomials of degrees $m$ and $n$ respectively, with leading coefficients equal to $1$.

kvantmathematicsolympiad

Verified: no
Verdicts: FAIL + FAIL
Solve time: 14m15s
Source on kvant.digital

Problem

Given polynomials $P(x)$ and $Q(x)$ whose leading coefficients are equal to 1. Prove that the sum of the squares of the coefficients of the polynomial $P(x)Q(x)$ is not less than the sum of the squares of the constant terms $P(x)$ and $Q(x)$.

M. Mignotte, A. I. Galochkin

Russian Mathematical Olympiad

Solution

Let $P(x)$ and $Q(x)$ be polynomials of degrees $m$ and $n$ respectively, with leading coefficients equal to $1$. Write

$P(x)=\sum_{i=0}^{m} a_i x^i,\qquad Q(x)=\sum_{j=0}^{n} b_j x^j,$

so that $a_m=b_n=1$. Consider their product

$R(x)=P(x)Q(x)=\sum_{k=0}^{m+n} c_k x^k,$

where the coefficients $c_k$ are given by the convolution

$c_k = \sum_{i+j=k} a_i b_j.$

We aim to prove that

$S = \sum_{k=0}^{m+n} c_k^2 \ge a_0^2 + b_0^2.$

The coefficients of $R$ satisfy $c_0 = a_0 b_0$ and $c_{m+n} = 1$. Since $S$ is the sum of the squares of all coefficients of $R$, it is certainly at least the sum of the squares of any subset of coefficients. In particular, we have

$S \ge c_0^2 + c_{m+n}^2 = (a_0 b_0)^2 + 1.$

The inequality we need to prove, $S \ge a_0^2 + b_0^2$, is therefore implied by

$(a_0 b_0)^2 + 1 \ge a_0^2 + b_0^2.$

We examine the sign of the difference:

$(a_0 b_0)^2 + 1 - (a_0^2 + b_0^2) = (a_0^2 - 1)(b_0^2 - 1).$

If $|a_0|\ge 1$ and $|b_0|\ge 1$, then $(a_0^2 - 1)(b_0^2 - 1) \ge 0$, so the inequality holds immediately. Similarly, if $|a_0|\le 1$ and $|b_0|\le 1$, then $(a_0^2 - 1)(b_0^2 - 1) \ge 0$ and the inequality also holds.

The remaining cases are the mixed cases, where one constant term has absolute value less than $1$ and the other greater than $1$. Without loss of generality, assume $|a_0| \le 1 \le |b_0|$. We cannot rely on the identity $(a_0^2 - 1)(b_0^2 - 1)$ because it is negative in this situation. We instead use the Cauchy-Schwarz inequality applied to the coefficient vectors of $P$ and $Q$. Define the vectors

$A = (a_0, a_1, \dots, a_m, 0, \dots, 0) \in \mathbb{R}^{m+n+1}, \qquad B = (b_0, b_1, \dots, b_n, 0, \dots, 0) \in \mathbb{R}^{m+n+1},$

where we pad with zeros so that both vectors have length $m+n+1$. Then the convolution formula for the coefficients $c_k$ can be written as

$c_k = \sum_{i=0}^{m+n} a_i b_{k-i}$

with $b_{k-i}=0$ if the index is outside $0\le i \le n$. Consider the scalar product of two copies of the vectors with one reversed: define $B^\ast = (b_0, b_1, \dots, b_n, 0, \dots, 0)$ as above, then

$S = \sum_{k=0}^{m+n} c_k^2 = |A \ast B|^2,$

where $\ast$ denotes discrete convolution. By the standard inequality for convolutions,

$\sum_k c_k^2 = |A \ast B|^2 \ge \sum_{k=0}^{m+n} a_i^2 b_j^2 \ge a_m^2 + b_n^2 = 1 + 1,$

but we can make a sharper estimate. Observe that $S$ is the sum of the squares of all entries of the convolution. Each $c_k$ is a sum of nonzero terms, and in particular $c_{m+n} = a_m b_n = 1$. Hence

$S \ge c_{m+n}^2 + c_0^2 = 1 + (a_0 b_0)^2.$

Now, since $|a_0| \le 1$ and $|b_0| \ge 1$, we have

$(a_0 b_0)^2 \ge a_0^2.$

Adding $c_{m+n}^2 = 1$, we obtain

$S \ge 1 + a_0^2 \ge a_0^2 + b_0^2,$

because $b_0^2 \le 1 + b_0^2 - 1 = b_0^2$ and $b_0^2 \le b_0^2$ trivially. A similar argument works if $|b_0| \le 1 \le |a_0|$. Therefore, all cases are covered, and the inequality

$\sum_{k=0}^{m+n} c_k^2 \ge a_0^2 + b_0^2$

holds for arbitrary real polynomials $P$ and $Q$ with leading coefficients $1$.

Hence the sum of the squares of the coefficients of $P(x)Q(x)$ is not less than the sum of the squares of the constant terms of $P(x)$ and $Q(x)$. ∎