Kvant Math Problem 912
For a polynomial to be monotonically increasing on the whole real line, it is enough that its derivative be nonnegative everywhere.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m29s
Source on kvant.digital
Problem
Prove that
- the polynomial $x^2$,
- any polynomial
can be represented as the difference of two polynomials, each of which is a monotonically increasing function.
V. P. Pikulin
Exploration
For a polynomial to be monotonically increasing on the whole real line, it is enough that its derivative be nonnegative everywhere. Thus the problem becomes a question about derivatives.
For the polynomial $x^2$, one may try to write
$$x^2=A(x)-B(x)$$
with both $A'$ and $B'$ nonnegative. Taking
$$A(x)=\frac{x^3}{3}+x^2+x,\qquad B(x)=\frac{x^3}{3}+x$$
gives
$$A'(x)=(x+1)^2,\qquad B'(x)=x^2+1,$$
which are nonnegative for all $x$.
For a general polynomial $P(x)$, it is natural to search for a polynomial $Q(x)$ whose derivative is everywhere large and positive. Then
$$P=Q-(Q-P),$$
and both summands will be increasing provided
$$Q'(x)\ge 0,\qquad Q'(x)-P'(x)\ge 0$$
for all $x$.
The difficulty is to find a single polynomial derivative that dominates $P'$. Since every polynomial grows more slowly than a sufficiently high power of $1+x^2$, the polynomial
$$(1+x^2)^m$$
with $2m>\deg P'$ should eventually dominate $|P'|$. The crucial point is to prove that a suitable constant multiple of this polynomial dominates $P'$ on the entire real line, not merely for large $|x|$.
Problem Understanding
We must prove that $x^2$ can be represented as the difference of two monotonically increasing polynomials and that the same is true for every polynomial.
This is a Type B problem. The statement is already given, so the task is to prove it.
The core difficulty is to show that for an arbitrary polynomial $P$, one can construct an increasing polynomial $Q$ whose derivative is everywhere at least as large as $P'$. Then both $Q$ and $Q-P$ will be increasing.
Proof Architecture
First, exhibit an explicit decomposition of $x^2$ into the difference of two increasing polynomials.
Second, prove that if a polynomial $R$ satisfies $R'(x)\ge0$ for all $x$, then $R$ is monotonically increasing.
Third, for a given polynomial $P$, choose an integer $m$ with $2m>\deg P'$ and show that the function
$$\frac{P'(x)}{(1+x^2)^m}$$
is bounded on $\mathbb R$.
Fourth, choose a constant $M$ exceeding that bound and define $Q$ by
$$Q'(x)=M(1+x^2)^m.$$
Fifth, prove that $Q'(x)\ge0$ and $Q'(x)-P'(x)\ge0$ everywhere, hence both $Q$ and $Q-P$ are increasing.
The most delicate step is the boundedness of
$$\frac{P'(x)}{(1+x^2)^m},$$
because it is this fact that permits a single constant $M$ to dominate $P'$ on the whole real line.
Solution
For the first statement, define
$$A(x)=\frac{x^3}{3}+x^2+x,\qquad B(x)=\frac{x^3}{3}+x.$$
Then
$$A(x)-B(x)=x^2.$$
Furthermore,
$$A'(x)=x^2+2x+1=(x+1)^2\ge0,$$
and
$$B'(x)=x^2+1>0$$
for every real $x$. Hence both $A$ and $B$ are monotonically increasing, and $x^2$ is their difference.
Now let $P(x)$ be an arbitrary polynomial.
Choose an integer $m$ such that
$$2m>\deg P'.$$
Consider the function
$$f(x)=\frac{P'(x)}{(1+x^2)^m}.$$
Since the denominator is never zero, $f$ is continuous on $\mathbb R$.
Because $\deg P'<2m$,
$$\lim_{|x|\to\infty}\frac{P'(x)}{(1+x^2)^m}=0.$$
Hence there exists $R>0$ such that
$$|f(x)|\le1$$
whenever $|x|\ge R$.
On the compact interval $[-R,R]$, the continuous function $f$ attains a maximum and a minimum. Therefore $f$ is bounded on $[-R,R]$. Combining this with the estimate outside $[-R,R]$, we conclude that there exists a constant $C$ such that
$$f(x)\le C$$
for all real $x$.
Choose a constant $M>C$ and let $Q$ be any polynomial satisfying
$$Q'(x)=M(1+x^2)^m.$$
Such a polynomial exists because the right-hand side is a polynomial.
For every real $x$,
$$Q'(x)=M(1+x^2)^m>0.$$
Also,
$$Q'(x)-P'(x) =(1+x^2)^m!\left(M-\frac{P'(x)}{(1+x^2)^m}\right).$$
Since
$$\frac{P'(x)}{(1+x^2)^m}\le C<M,$$
the second factor is positive, and therefore
$$Q'(x)-P'(x)\ge0$$
for all $x$.
Thus both polynomials
$$Q$$
and
$$Q-P$$
have nonnegative derivatives everywhere, so both are monotonically increasing.
Finally,
$$P=Q-(Q-P),$$
which expresses the arbitrary polynomial $P$ as the difference of two monotonically increasing polynomials.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the claim that boundedness of
$$\frac{P'(x)}{(1+x^2)^m}$$
follows from $2m>\deg P'$. Write
$$P'(x)=a_d x^d+\cdots ,$$
where $d<2m$. Then
$$\frac{P'(x)}{(1+x^2)^m} \sim a_d x^{d-2m}$$
as $|x|\to\infty$. Since $d-2m<0$, the ratio tends to $0$. Without the strict inequality $d<2m$, the ratio would not necessarily vanish at infinity.
The second delicate step is proving that $Q'(x)-P'(x)\ge0$. Substituting the definition of $Q'$ gives
$$Q'(x)-P'(x) =(1+x^2)^m!\left(M-\frac{P'(x)}{(1+x^2)^m}\right).$$
The factor $(1+x^2)^m$ is strictly positive. The other factor is positive because $M$ was chosen larger than a global upper bound for the ratio. A careless choice of $M$ larger only than the leading coefficient would not suffice.
The third delicate step is the passage from nonnegative derivative to monotonicity. For any $a<b$,
$$R(b)-R(a)=\int_a^b R'(t),dt.$$
If $R'(t)\ge0$ everywhere, the integral is nonnegative, hence $R(b)\ge R(a)$. This establishes that $R$ is increasing.
Alternative Approaches
Instead of taking
$$Q'(x)=M(1+x^2)^m,$$
one may choose an even integer $2m$ larger than $\deg P'$ and set
$$Q'(x)=M(x^{2m}+1).$$
The same argument works because
$$\frac{P'(x)}{x^{2m}+1}$$
is continuous and tends to $0$ at infinity.
The chosen proof is preferable because $(1+x^2)^m$ is strictly positive for every real $x$. This avoids any discussion of zeros of the dominating polynomial and makes the verification of
$$Q'(x)-P'(x)\ge0$$
completely straightforward.