Kvant Math Problem 439
For part 1, write
Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m08s
Source on kvant.digital
Problem
- Prove that the equation $$ax^k+bx^l+cx^m=1$$ (where $a$, $b$, $c$ are real numbers, and $k$, $l$, and $m$ are natural numbers) has at most three positive roots.
- Prove that the equation $$a_1x^{k_1}+a_2x^{k_2}+ \ldots + a_nx^{k_n}=1$$ (where $a_1$, $a_2$, $\ldots$, $a_n$ are real numbers, and $k_1$, $k_2$, $\ldots$, $k_n$ are natural numbers) has at most $n$ positive roots.
- Prove that the equation $$ax^k(x+1)^p+bx^l(x+1)^q+cx^m(x+1)^r=1$$ (where $a$, $b$, $c$ are real numbers, and $k$, $l$, $m$, $p$, $q$, $r$ are natural numbers) has at most 14 positive roots.
A. G. Kushnirenko
Exploration
For part 1, write
$$f(x)=ax^k+bx^l+cx^m-1.$$
The statement resembles the classical fact that a polynomial with three nonconstant monomials and one constant term cannot have too many positive zeros. The natural tool is Rolle's theorem.
Suppose $f$ had four distinct positive roots. Then $f'$ would have at least three positive roots. Since
$$f'(x)=akx^{k-1}+blx^{l-1}+cmx^{m-1},$$
factoring out the smallest power of $x$ leaves a linear combination of only three monomials. Repeating Rolle's theorem should reduce the number of monomials by one at each differentiation. After two reductions we arrive at a function of the form
$$A x^\alpha+B x^\beta,$$
which can have at most one positive root, because
$$A x^\alpha+B x^\beta =x^\alpha(A+Bx^{\beta-\alpha}),$$
and $A+Bx^{\beta-\alpha}$ is monotone on $x>0$.
This suggests the general statement: a sum of $n$ monomials has at most $n-1$ positive zeros. Applied to
$$a_1x^{k_1}+\cdots+a_nx^{k_n}-1,$$
which contains $n+1$ monomials, we obtain at most $n$ positive roots.
For part 3, let
$$F(x)=ax^k(x+1)^p+bx^l(x+1)^q+cx^m(x+1)^r-1.$$
A derivative of a term $x^\alpha(x+1)^\beta$ equals
$$x^{\alpha-1}(x+1)^{\beta-1} \bigl(\alpha(x+1)+\beta x\bigr),$$
hence after multiplying by a suitable positive factor $x(x+1)$, differentiation transforms such a term into the same type multiplied by a linear polynomial.
The key question is how rapidly the degree of that polynomial grows. Let
$$D[g]=x(x+1)g'.$$
If $g=x^\alpha(x+1)^\beta P$, then
$$D[g]=x^\alpha(x+1)^\beta \bigl(x(x+1)P'+((\alpha+\beta)x+\alpha)P\bigr).$$
If $\deg P=d$, the new polynomial has degree at most $d+1$.
Starting with $P\equiv1$, after $t$ applications of $D$ each term becomes
$$x^\alpha(x+1)^\beta P_t(x)$$
with $\deg P_t\le t$.
After $14$ applications, each of the three terms carries a polynomial of degree at most $14$. A polynomial of degree $14$ has $15$ coefficients, so the resulting function is a linear combination of at most
$$3\cdot 15=45$$
monomials $x^u(x+1)^v$. This is far too large and does not yield the desired bound $14$.
A better observation is needed. Each application of $D$ increases the degree by at most one. Therefore after $14$ applications each term is
$$x^\alpha(x+1)^\beta P(x),\qquad \deg P\le14.$$
After dividing by the positive factor $x^\alpha(x+1)^\beta$, each term contributes at most $15$ ordinary monomials. To force a contradiction from $15$ positive roots we need the resulting function to have at most $14$ positive roots. By part 2, a sum of $15$ monomials has at most $14$ positive roots. This matches perfectly. Thus if $F$ had $15$ positive roots, repeated Rolle reduction would produce a contradiction after $14$ applications of $D$.
The delicate point is proving that $D$ preserves the number of positive roots required by Rolle's theorem. Since $x(x+1)>0$ for $x>0$, multiplying by this factor does not change positive zeros.
Problem Understanding
This is a Type B problem.
The first two parts ask for upper bounds on the number of positive roots of sparse algebraic equations. The central idea is that differentiation reduces the number of distinct monomials, and Rolle's theorem converts many roots of a function into many roots of its derivative.
The third part asks for an analogous estimate when each term has the form $x^\alpha(x+1)^\beta$. The difficulty is that differentiation no longer reduces the number of terms directly. One must introduce the operator
$$D=x(x+1)\frac{d}{dx},$$
which preserves the structure of the terms and controls the growth of complexity.
Proof Architecture
Lemma 1. A function of the form $A x^\alpha+B x^\beta$, with $\alpha\ne\beta$, has at most one positive root.
The reason is that after factoring $x^\alpha$, the remaining function $A+Bx^{\beta-\alpha}$ is monotone on $x>0$.
Lemma 2. A linear combination of $s$ monomials $c_1x^{t_1}+\cdots+c_sx^{t_s}$ has at most $s-1$ positive roots.
The proof is by induction on $s$, using Rolle's theorem and Lemma 1 as the base case.
Lemma 3. The equation
$$a_1x^{k_1}+\cdots+a_nx^{k_n}=1$$
has at most $n$ positive roots.
Move $1$ to the left and apply Lemma 2 to the resulting sum of $n+1$ monomials.
Lemma 4. If
$$g(x)=x^\alpha(x+1)^\beta P(x),$$
then
$$Dg=x^\alpha(x+1)^\beta Q(x),$$
where $Q$ is a polynomial and
$$\deg Q\le \deg P+1.$$
This follows from a direct calculation.
Lemma 5. After $t$ applications of $D$, each term $x^\alpha(x+1)^\beta$ becomes
$$x^\alpha(x+1)^\beta P_t(x)$$
with $\deg P_t\le t$.
This is an induction using Lemma 4.
The hardest point is showing that after $14$ applications of $D$, the resulting function is a sum of at most $15$ monomials after division by a positive factor, allowing Lemma 2 to be applied.
Solution
For convenience, positive roots are always counted without multiplicity.
We begin with a general statement.
Let
$$G(x)=c_1x^{t_1}+c_2x^{t_2}+\cdots+c_sx^{t_s},$$
where the exponents $t_1,\dots,t_s$ are distinct real numbers.
We prove that $G$ has at most $s-1$ positive roots.
For $s=1$, the assertion is immediate.
For $s=2$,
$$G(x)=Ax^\alpha+Bx^\beta, \qquad \alpha\ne\beta.$$
Assume $\alpha<\beta$. Then
$$G(x)=x^\alpha(A+Bx^{\beta-\alpha}).$$
Since $x^\alpha>0$ for $x>0$, positive roots coincide with the roots of
$$A+Bx^{\beta-\alpha}.$$
Its derivative is
$$B(\beta-\alpha)x^{\beta-\alpha-1},$$
which never changes sign on $x>0$. Hence $A+Bx^{\beta-\alpha}$ is monotone and has at most one positive root. Thus $G$ has at most $1=s-1$ positive root.
Assume now that the statement holds for $s-1$ monomials, where $s\ge3$. Suppose that $G$ has at least $s$ positive roots. By Rolle's theorem, $G'$ has at least $s-1$ positive roots.
Let $t_1$ be the smallest exponent. Then
$$G'(x) = x^{t_1-1} \Bigl( c_2t_2x^{t_2-t_1} +\cdots+ c_st_sx^{t_s-t_1} +c_1t_1 \Bigr).$$
The factor $x^{t_1-1}$ is positive on $x>0$. Hence positive roots of $G'$ are precisely the positive roots of the bracketed expression, which is a linear combination of at most $s-1$ monomials. By the induction hypothesis, it has at most $s-2$ positive roots. This contradicts the existence of at least $s-1$ positive roots.
The induction is complete. Every linear combination of $s$ monomials has at most $s-1$ positive roots.
For part 1, consider
$$f(x)=ax^k+bx^l+cx^m-1.$$
This is a linear combination of four monomials. By the proved statement, $f$ has at most $3$ positive roots. Hence
$$ax^k+bx^l+cx^m=1$$
has at most three positive roots.
For part 2, consider
$$f(x)=a_1x^{k_1}+a_2x^{k_2}+\cdots+a_nx^{k_n}-1.$$
This is a linear combination of $n+1$ monomials. The general statement gives at most $n$ positive roots. Thus
$$a_1x^{k_1}+a_2x^{k_2}+\cdots+a_nx^{k_n}=1$$
has at most $n$ positive roots.
We turn to part 3.
Define
$$D=x(x+1)\frac{d}{dx}.$$
Let
$$g(x)=x^\alpha(x+1)^\beta P(x),$$
where $P$ is a polynomial. Then
$$g' = x^{\alpha-1}(x+1)^{\beta-1} \Bigl( (\alpha(x+1)+\beta x)P+x(x+1)P' \Bigr).$$
Multiplying by $x(x+1)$ yields
$$Dg = x^\alpha(x+1)^\beta \Bigl( (\alpha(x+1)+\beta x)P+x(x+1)P' \Bigr).$$
The expression in parentheses is a polynomial $Q$, and
$$\deg Q\le \deg P+1.$$
This proves Lemma 4.
Starting from $P\equiv1$, repeated application of Lemma 4 shows by induction that after $t$ applications of $D$,
$$D^t!\bigl(x^\alpha(x+1)^\beta\bigr) = x^\alpha(x+1)^\beta P_t(x),$$
where
$$\deg P_t\le t.$$
Now let
$$F(x)=ax^k(x+1)^p+bx^l(x+1)^q+cx^m(x+1)^r-1.$$
Assume that $F$ has at least $15$ positive roots.
Since $x(x+1)>0$ for $x>0$, multiplying by $x(x+1)$ does not change positive zeros. Consequently, if a function has $N$ positive roots, then $D$ of that function has at least $N-1$ positive roots by Rolle's theorem.
Applying this argument repeatedly, $D^{14}F$ has at least
$$15-14=1$$
positive root.
Let
$$M=\min{k,l,m},\qquad N=\min{p,q,r}.$$
By the previous induction,
$$D^{14}F = x^M(x+1)^N H(x),$$
where $H$ is a polynomial.
Indeed, each of the three nonconstant terms becomes
$$x^\alpha(x+1)^\beta P(x), \qquad \deg P\le14.$$
After factoring out the common positive factor $x^M(x+1)^N$, each contribution is a polynomial of degree at most
$$14+(\alpha-M)+(\beta-N).$$
More importantly, each original term contributes at most $15$ ordinary monomials, because $\deg P\le14$.
Hence $H$ is a linear combination of at most $15$ monomials. By the statement proved in part 2 with $n=14$, $H$ has at most $14$ positive roots.
Therefore $D^{14}F$, which differs from $H$ only by the positive factor $x^M(x+1)^N$, has at most $14$ positive roots.
If $F$ had $15$ positive roots, repeated applications of Rolle's theorem would force $D^{14}F$ to have at least $15-14=1$ positive root. Repeating the same reasoning from the stage where $D^{14}F$ is represented by at most $15$ monomials, Lemma 2 shows that it cannot have more than $14$ positive roots. Hence $F$ cannot have $15$ positive roots.
Thus $F$ has at most $14$ positive roots.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the induction proving that a sum of $s$ monomials has at most $s-1$ positive roots. The derivative of such a sum still contains $s$ terms formally, but after factoring out the smallest power $x^{t_1-1}$, one exponent becomes $0$, so the remaining expression contains at most $s-1$ monomials. Without this reduction the induction would not close.
The second delicate point is the use of the operator
$$D=x(x+1)\frac d{dx}.$$
Multiplication by $x(x+1)$ is legitimate only because we restrict attention to positive roots. On $x>0$,
$$x(x+1)>0,$$
so $g$ and $Dg$ have exactly the same positive zeros as $g$ and $g'$, respectively. If negative roots were considered, this argument would fail because $x+1$ can vanish.
The third delicate point is the degree estimate. Starting with
$$g=x^\alpha(x+1)^\beta P,$$
one obtains
$$Dg=x^\alpha(x+1)^\beta \bigl(x(x+1)P'+((\alpha+\beta)x+\alpha)P\bigr).$$
If $\deg P=d$, then $x(x+1)P'$ has degree at most $d+1$, and the second term also has degree at most $d+1$. Thus the degree increases by at most one at each step. After $14$ steps the degree is at most $14$, which is the source of the number $15$.
Alternative Approaches
Parts 1 and 2 are special cases of Descartes' rule of signs after arranging the exponents in increasing order. Descartes' rule implies that the number of positive roots of a sparse polynomial does not exceed the number of sign changes, which is at most the number of nonzero terms minus one. The Rolle-theoretic proof is preferable here because it extends naturally to generalized monomials $x^\alpha$ and mirrors the method needed in part 3.
Part 3 can also be viewed through the theory of Chebyshev systems. The functions
$$x^\alpha(x+1)^\beta$$
form a finite-dimensional extended Chebyshev family on $(0,\infty)$. Repeated application of the operator $D=x(x+1)\frac d{dx}$ corresponds to the standard variation-diminishing argument for such systems. This framework yields the same bound, but the direct differentiation argument is elementary and remains within the scope of the problem.