Problem A. 898. (January 2025)

A. 898. Let \(\displaystyle n\) be a given positive integer. Ana and Bob play the following game: Ana chooses a polynomial \(\displaystyle p\) of degree \(\displaystyle n\) with integer coefficients. In each round, Bob can choose a finite set \(\displaystyle S\) of positive integers, and Ana responds with a list containing the values of the polynomial \(\displaystyle p\) evaluated at the elements of \(\displaystyle S\) with multiplicity (sorted in increasing order). Determine, in terms of \(\displaystyle n\), the smallest positive integer \(\displaystyle k\) such that Bob can always determine the polynomial \(\displaystyle p\) in at most \(\displaystyle k\) rounds.

Proposed by: Andrei Chirita, Cambridge

(7 pont)

Deadline expired on February 10, 2025.

We will prove that there is a finite set \(\displaystyle S\) of integers such that \(\displaystyle P(S)=Q(S)\) implies \(\displaystyle P=Q\) for any two polynomials \(\displaystyle P,Q\in\mathbb{Z}[X]\) with degree \(\displaystyle n\).

Using this statement Bob can solve the problem with a single question using Ana's answer \(\displaystyle P(S)\): first, he considers all possible values for \(\displaystyle (x_1,P(x_1))\), \(\displaystyle (x_2,P(x_2))\),..., \(\displaystyle (x_{n+1},P(x_{n+1}))\) (clearly there are finitely many options) and for each of these he applies the Lagrange Interpolation Formula to construct a candidate polynomial \(\displaystyle Q\). Next, for each such \(\displaystyle Q\), he checks whether \(\displaystyle Q(S)=P(S)\) or not. Using the statement above this equality implies \(\displaystyle P=Q\), thus after finitely many tries he will find the polynomial chosen by Ana.

To prove our initial statement, let \(\displaystyle x_1,x_2,\dots,x_{m}\) be distinct integers, where \(\displaystyle m=7n+1\). Suppose that \(\displaystyle y_1,y_2,\dots,y_{m}\) is a permutation of \(\displaystyle x_1,\dots,x_m\) and \(\displaystyle P\) and \(\displaystyle Q\) are integer polynomials of degree \(\displaystyle n\) such that \(\displaystyle P(x_i)=Q(y_i)\) for all \(\displaystyle 1\le i\le m\).

If there are at least \(\displaystyle n+1\) integers \(\displaystyle 1\le i\le m\) such that \(\displaystyle x_i=y_i\), then \(\displaystyle P-Q\) has at least \(\displaystyle n+1\) roots. Hence \(\displaystyle P-Q\) is the zero polynomial, so \(\displaystyle P=Q\). Assume otherwise.

Consider all pairs \(\displaystyle \{x_i,y_i\}\) where \(\displaystyle x_i\ne y_i\). We know that there are at least \(\displaystyle 6n+1\) pairs. Each such pair has a common element with at most two other pairs. Thus, if \(\displaystyle l\) is the largest number of pairs such that any two of them are disjoint, it follows that \(\displaystyle 3l\ge 6n+1\), so \(\displaystyle l\ge 2n+1\). This means that we can pick \(\displaystyle 2n+1\) disjoint pairs \(\displaystyle \{a_1,b_1\},\{a_2,b_2\},\dots,\{a_{2n+1},b_{2n+1}\}\).

Let \(\displaystyle P(X)=c_nX^n+c_{n-1}X^{n-1}+\dots+c_0\) and \(\displaystyle Q(X)=d_nX^n+d_{n-1}X^{n-1}+\dots+d_0\). Note that shifting \(\displaystyle P\) and \(\displaystyle Q\) by \(\displaystyle -d_0\) does not affect anything, so assume without loss of generality that \(\displaystyle d_0=0\).

If we fix \(\displaystyle a_1,\dots,a_{2n+1},b_1,\dots,b_{2n+1}\), the relations \(\displaystyle P(a_i)=Q(b_i)\) for \(\displaystyle 1\le i\le 2n+1\) translate into the following system of linear equations:

\(\displaystyle c_n a_1^n + c_{n-1} a_1^{n-1} + \dots + c_0 = d_n b_1^n + d_{n-1} b_1^{n-1} + \dots + d_1 b_1 + d_0,\\ c_n a_2^n + c_{n-1} a_2^{n-1} + \dots + c_0 = d_n b_2^n + d_{n-1} b_2^{n-1} + \dots + d_1 b_2 + d_0, \\ \phantom{c_n a_2^n + c_{n-1} a_2^{n-1} + \dots + c_0 =} \vdots \phantom{= d_n b_2^n + d_{n-1} b_2^{n-1} + \dots + d_1 b_2 + d_0} \\ c_n a_{2n+1}^n + c_{n-1} a_{2n+1}^{n-1} + \dots + c_0 = d_n b_{2n+1}^n + d_{n-1} b_{2n+1}^{n-1} + \dots + d_1 b_{2n+1} + d_0. \)

This system has a nontrivial solution \(\displaystyle c_n,c_{n-1},\dots,c_0,d_n,\dots,d_1\) if and only if

\(\displaystyle \begin{vmatrix} a_1^n & a_1^{n-1} & \dots & a_1 & 1 & -b_1^n & -b_1^{n-1} & \dots & -b_1 \\ a_2^n & a_2^{n-1} & \dots & a_2 & 1 & -b_2^n & -b_2^{n-1} & \dots & -b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{2n+1}^n & a_{2n+1}^{n-1} & \dots & a_{2n+1} & 1 & -b_{2n+1}^n & -b_{2n+1}^{n-1} & \dots & -b_{2n+1} \end{vmatrix} =0. \)

Hence, if the above determinant is nonzero, it follows that

\(\displaystyle c_n=c_{n-1}=\dots=c_0=d_n=\dots=d_1=0.\)

We thus obtain \(\displaystyle P=Q=0\), which is a contradiction since \(\displaystyle P\) and \(\displaystyle Q\) have degree \(\displaystyle n\).

This gives us the following idea: we construct \(\displaystyle S\) of size \(\displaystyle 7n+1\) such that, for any distinct \(\displaystyle z_1,z_2,\dots,z_{4n+2}\in S\), the determinant

\(\displaystyle f(z_1,z_2,\dots,z_{4n+2})=\begin{vmatrix} z_1^n & z_1^{n-1} & \dots & z_1 & 1 & -z_2^n & -z_2^{n-1} & \dots & -z_2 \\ z_3^n & z_3^{n-1} & \dots & z_3 & 1 & -z_4^n & -z_4^{n-1} & \dots & -z_4 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ z_{4n+1}^n & z_{4n+1}^{n-1} & \dots & z_{4n+1} & 1 & -z_{4n+2}^n & -z_{4n+2}^{n-1} & \dots & -z_{4n+2} \end{vmatrix}\)

is nonzero. Of course, \(\displaystyle f(X_1,\dots,X_{4n+2})\) is a nonzero polynomial.

Define the polynomial

\(\displaystyle R(X_1,\dots,X_{m})=\prod_{1\le i_1,i_2,\dots,i_{4n+2}\le m}f(X_{i_1},X_{i_2},\dots,X_{i_{4n+2}}).\)

All we need is to find distinct integers \(\displaystyle x_1,x_2,\dots,x_{m}\) such that \(\displaystyle R(x_1,\dots,x_{m})\ne 0\).

Lemma. For any positive integer \(\displaystyle n\) and any nonzero \(\displaystyle n\)-variable polynomial \(\displaystyle T(X_1,X_2,\dots,X_{n})\), there are distinct integers \(\displaystyle a_1,a_2,\dots,a_n\) such that

\(\displaystyle T(a_1,a_2,\dots,a_n)\ne 0.\)

Proof. This is an immediate consequence of the Combinatorial Nullstellensatz, however, we give here a proof for the sake of completeness.

We induct on \(\displaystyle n\).

The base case \(\displaystyle n=1\) is trivial, since \(\displaystyle T(X)\) has finitely many roots.

For the induction step, assume that the statement is true for \(\displaystyle n\). We will prove it for \(\displaystyle n+1\).

Write

\(\displaystyle T(X_1,X_2,\dots,X_{n+1})=X_{n+1}^dA_d(X_1,\dots,X_n)+X_{n+1}^{d-1}A_{d-1}(X_1,\dots,X_n)+\dots+A_0(X_1,\dots,X_n)\)

where \(\displaystyle A_d,A_{d-1},\dots,A_0\) are \(\displaystyle n-\)variable polynomials.

Since \(\displaystyle T\) is nonzero, there is an index \(\displaystyle 0\le i\le d\) such that \(\displaystyle A_i\) is nonzero. From the inductive hypothesis, there are distinct integers \(\displaystyle a_1,\dots,a_n\) such that \(\displaystyle A_i(a_1,\dots,a_n)\ne 0\). It follows that the polynomial \(\displaystyle T(a_1,a_2,\dots,a_n,X)\) is nonzero. Hence it has finitely many roots, and this proves that there is an integer \(\displaystyle a_{n+1}\ne a_1,a_2,\dots,a_n\) such that \(\displaystyle T(a_1,a_2,\dots,a_{n+1})\ne 0\), as desired.   \(\displaystyle \square\)

From the Lemma it follows that there are distinct integers \(\displaystyle x_1,x_2,\dots,x_m\) such that \(\displaystyle R(x_1,x_2,\dots,x_m)\) is nonzero, and we can let \(\displaystyle S=\{x_1,x_2,\dots,x_m\}\). Hence, if \(\displaystyle P\) and \(\displaystyle Q\) are integer polynomials of degree \(\displaystyle n\), \(\displaystyle P(S)=Q(S)\) implies \(\displaystyle P=Q\).

Statistics:

8 students sent a solution.
7 points:	Bodor Mátyás, Forrai Boldizsár.
6 points:	Varga Boldizsár.
3 points:	1 student.
1 point:	2 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, January 2025