Kvant Math Problem 1564
Let
Verified: yes
Verdicts: PASS + PASS
Solve time: 15m45s
Source on kvant.digital
Problem
Does there exist a finite set $M$ of nonzero real numbers such that for every natural number $n$ there is a polynomial of degree at least $n$ with coefficients from the set $M$, all of whose roots are real and also belong to $M$?
E. Malinnikova
All-Russian School Mathematics Olympiad (1996)
Exploration
Let
$$M={m_1,\dots,m_s}\subset \mathbb R\setminus{0}$$
be finite. Suppose that for every natural number $n$ there exists a polynomial of degree at least $n$, all of whose coefficients belong to $M$ and all of whose roots belong to $M$.
For a polynomial
$$P(x)=a_d\prod_{i=1}^{d}(x-r_i),$$
with $a_d\in M$ and $r_i\in M$, Vieta's formulas express the coefficients through the elementary symmetric functions of the roots. Since the coefficients are restricted to the finite set $M$, the corresponding symmetric functions can take only finitely many values. The first two Vieta relations already impose enough restrictions to force the degree to be bounded.
Problem Understanding
The question asks whether a finite nonzero set $M$ can simultaneously contain every coefficient and every root of polynomials of arbitrarily large degree.
The degree is allowed to grow without bound, while the available coefficient values remain fixed and finite. The first coefficient below the leading term controls the sum of the roots, and the next coefficient controls the second elementary symmetric function. Combining these two quantities yields the sum of the squares of the roots, which turns out to be uniformly bounded. Since every root belongs to a fixed finite nonzero set, that boundedness forces the degree itself to be bounded.
Proof Architecture
Assume that such a finite set $M$ exists.
For an admissible polynomial, Vieta's formulas show that the sum of the roots and the second elementary symmetric sum belong to finite sets depending only on $M$.
Using the identity
$$e_2=\frac{(\sum r_i)^2-\sum r_i^2}{2},$$
it follows that the quantity $\sum r_i^2$ also belongs to a finite set.
Since every root is an element of the fixed finite set $M$, each root square is at least a positive constant. Hence
$$\sum r_i^2$$
grows at least linearly with the degree. A uniform bound for this sum therefore gives a uniform bound for the degree, contradicting the existence of arbitrarily large degrees.
Solution
Assume that a finite set
$$M\subset\mathbb R\setminus{0}$$
satisfies the condition of the problem.
Consider any admissible polynomial of degree $d$:
$$P(x)=a_d\prod_{i=1}^{d}(x-r_i),$$
where
$$a_d\in M,\qquad r_i\in M.$$
Let
$$S_1=\sum_{i=1}^{d} r_i, \qquad e_2=\sum_{1\le i<j\le d} r_i r_j .$$
By Vieta's formulas,
$$a_{d-1}=-a_dS_1, \qquad a_{d-2}=a_d e_2 .$$
Since both $a_d$ and $a_{d-1}$ belong to the finite set $M$, the quotient
$$S_1=-\frac{a_{d-1}}{a_d}$$
belongs to the finite set
$$A=\left{-\frac{u}{v}:u,v\in M\right}.$$
Likewise,
$$e_2=\frac{a_{d-2}}{a_d}$$
belongs to the finite set
$$B=\left{\frac{u}{v}:u,v\in M\right}.$$
Hence both $S_1$ and $e_2$ can take only finitely many values.
Now use the identity
$$S_1^2 = \left(\sum_{i=1}^{d} r_i\right)^2 = \sum_{i=1}^{d} r_i^2 + 2e_2.$$
Therefore
$$\sum_{i=1}^{d} r_i^2 = S_1^2-2e_2.$$
The right-hand side belongs to the finite set
$${a^2-2b:a\in A,\ b\in B}.$$
Consequently there exists a constant $C$ such that every admissible polynomial satisfies
$$\sum_{i=1}^{d} r_i^2\le C.$$
Since $M$ is finite and contains no zero,
$$m:=\min_{x\in M} x^2$$
is a positive number. Every root $r_i$ belongs to $M$, so
$$r_i^2\ge m.$$
Hence
$$\sum_{i=1}^{d} r_i^2\ge dm.$$
Combining this with the previous bound gives
$$dm\le C,$$
so
$$d\le \frac{C}{m}.$$
Thus the degree of every admissible polynomial is bounded by the same constant.
This contradicts the hypothesis that for every natural number $n$ there exists an admissible polynomial of degree at least $n$.
Therefore no finite set $M$ with the required property exists.
Verification of Key Steps
The crucial observation is that Vieta's formulas express
$$S_1=\sum r_i \quad\text{and}\quad e_2=\sum_{i<j} r_i r_j$$
as ratios of coefficients. Since all coefficients belong to the fixed finite set $M$, both quantities range over finite sets.
The identity
$$\sum r_i^2=S_1^2-2e_2$$
then shows that the sum of the squares of the roots is uniformly bounded.
Because every root lies in the finite nonzero set $M$, each root square is bounded below by the positive constant
$$m=\min_{x\in M}x^2.$$
A bounded value of $\sum r_i^2$ therefore yields a uniform bound on the number of roots, hence on the degree.
Alternative Approaches
One may also work with multiplicities of the elements of $M$. Writing the roots as
$$m_1,\dots,m_s$$
with multiplicities $\mu_1,\dots,\mu_s$, the quantities
$$\sum \mu_i m_i \quad\text{and}\quad \sum \mu_i m_i^2$$
are determined by the first two Vieta coefficients and therefore range over finite sets. Since each $m_i^2$ is positive, the second expression immediately bounds
$$\sum \mu_i,$$
which is the degree. This again contradicts the existence of arbitrarily large degrees.