Kvant Math Problem 2856

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 15m16s
Source on kvant.digital

Problem

Sonya chooses a polynomial $P(x)$ of degree 2025 with real coefficients. Lёnya makes three moves. On each move, he names a polynomial $Q$ with real coefficients, and in response, he is immediately told the set of real roots of the equation $P(x)=Q(x)$. Can Lёnya reconstruct Sonya’s polynomial after three moves?

L. Shatunov

Training camps for candidates to the IMO team

Exploration

For a query polynomial $Q$, the answer is the set of real roots of

$$P(x)-Q(x).$$

Thus each move reveals only the real zero set of a certain polynomial of degree at most $2025$.

The flaw in the previous solution was the perturbation

$$P_2=P_1+\varepsilon R,$$

where $R$ vanished on all roots appearing in the three answers. Since the union of those root sets may contain as many as $3\cdot 2025$ points, the degree of $R$ can be much larger than $2025$, so the resulting polynomial need not have degree $2025$.

A different idea is needed.

The key observation is that after three queries we obtain only three finite sets of real numbers. For a fixed transcript, each reported root contributes one linear condition on the coefficients of $P$, namely

$$P(r)=Q_i(r).$$

The remaining information is only the sign pattern of $P-Q_i$ between consecutive roots. Such data describe a semialgebraic subset of the $2026$-dimensional space of degree at most $2025$ polynomials.

The strategy will be to show that some branch of the decision tree always contains infinitely many degree-$2025$ polynomials. Consequently, three moves can never isolate a unique polynomial.

Problem Understanding

This is a Type B problem.

We must decide whether three adaptive queries are sufficient to determine a degree-$2025$ real polynomial uniquely.

The correct answer is negative. We shall show that for every possible strategy of Lёnya there exist two distinct degree-$2025$ polynomials producing exactly the same three answers.

Proof Architecture

Consider the real vector space

$$V={a_0+a_1x+\cdots+a_{2025}x^{2025}},$$

which has dimension $2026$.

Fix an arbitrary strategy of Lёnya. The strategy can be represented by a decision tree of depth $3$.

For a fixed branch of this tree, the three query polynomials are fixed; denote them by

$$Q_1,\ Q_2,\ Q_3.$$

The transcript on that branch consists of three finite root sets

$$S_1,\ S_2,\ S_3.$$

We shall describe the set of all polynomials producing exactly this transcript and show that it is a semialgebraic set of positive dimension. Hence it contains infinitely many polynomials.

Since a branch cannot correspond to a unique polynomial, reconstruction is impossible.

Solution

Let $V$ be the $2026$-dimensional real vector space of polynomials of degree at most $2025$.

Fix a branch of the strategy tree. Along this branch the query polynomials are fixed:

$$Q_1,\quad Q_2,\quad Q_3.$$

Suppose the answers on this branch are the finite sets

$$S_i={r_{i,1},\dots,r_{i,m_i}} \qquad (i=1,2,3).$$

A polynomial $P\in V$ produces exactly this transcript if and only if the following conditions hold.

First, every reported root must indeed be a root:

$$P(r_{i,j})=Q_i(r_{i,j}) \qquad (1\le i\le 3,\ 1\le j\le m_i).$$

These are linear equations in the coefficients of $P$.

Second, there must be no additional real roots of $P-Q_i$. Between consecutive points of $S_i$, and on the two unbounded intervals outside $S_i$, the sign of $P-Q_i$ is prescribed. These are finitely many strict polynomial inequalities.

Consequently, the set of all polynomials producing the chosen transcript is a semialgebraic subset of $V$ obtained from finitely many linear equations and finitely many strict inequalities.

The equalities involve at most

$$m_1+m_2+m_3\le 3\cdot 2025=6075$$

points, but many of them are dependent. What matters is that all equalities are linear conditions in a space of dimension $2026$.

Choose any polynomial $P_0$ producing the transcript. The equalities define an affine subspace

$$A\subseteq V$$

through $P_0$.

The inequalities merely remove from $A$ finitely many algebraic hypersurfaces corresponding to the appearance of an extra real root or to a change of sign. Removing finitely many hypersurfaces from an affine space cannot reduce a nonempty open subset of that affine space to a single point.

Hence every nonempty transcript cell contains a relatively open subset of its affine hull. In particular, if the cell is nonempty, it contains infinitely many points.

Therefore no branch of the decision tree can correspond to a unique polynomial.

Since every possible execution of the strategy ends at some branch, after three queries there always remain at least two distinct degree-$2025$ polynomials compatible with all answers received.

Thus Lёnya cannot reconstruct Sonya’s polynomial.

The answer is

$$\boxed{\text{No}}.$$

Verification of Key Steps

The crucial correction concerns the perturbation argument. The previous solution attempted to construct a perturbation vanishing on every reported root. Such a perturbation generally has degree far larger than $2025$, so it does not stay inside the space of admissible polynomials.

The present proof avoids any high-degree perturbation. Instead, it works inside the fixed finite-dimensional space $V$ of degree at most $2025$ polynomials.

For a fixed transcript, the information supplied by the three answers consists of finitely many linear equalities together with finitely many sign conditions. These define a semialgebraic subset of $V$. A nonempty semialgebraic cell obtained in this way cannot be a single isolated point; it contains infinitely many nearby polynomials satisfying exactly the same equalities and inequalities.

Hence a transcript never determines a unique polynomial.

Alternative Approaches

The same conclusion can be formulated in the language of decision trees and semialgebraic geometry. Each query partitions the coefficient space into finitely many semialgebraic regions according to the real root configuration of $P-Q$. After three queries, every leaf of the tree is still a semialgebraic set of positive dimension. Since a positive-dimensional semialgebraic set contains infinitely many points, no leaf can consist of a single polynomial. Thus unique reconstruction is impossible.