Problem A. 703. (September 2017)

A. 703. Let \(\displaystyle n\ge 2\) be an integer. We call an ordered \(\displaystyle n\)-tuple of integers primitive if the greatest common divisor of its components is \(\displaystyle 1\). Prove that for every finite set \(\displaystyle H\) of primitive \(\displaystyle n\)-tuples, there exists a non-constant homogenous polynomial \(\displaystyle f(x_1,x_2,\dots,x_n)\) with integer coefficients whose value is \(\displaystyle 1\) at every \(\displaystyle n\)-tuple in \(\displaystyle H\).

(Based on the sixth problem of the 58th IMO, Brazil)

(5 pont)

Deadline expired on October 10, 2017.

Solution. Fix a large degree \(\displaystyle d\). Let \(\displaystyle f\) be some homogenous polynomial with integer coefficients with degree \(\displaystyle d\). To each such \(\displaystyle f\), we can assign an \(\displaystyle |H|\)-tuple containing the values of \(\displaystyle f\) at the elements of \(\displaystyle H\). We wish to construct an \(\displaystyle f\) where this \(\displaystyle |H|\)-tuple is precisely \(\displaystyle (1,1,\dots,1)\). To this end, we will create two auxiliary polynomials (of degree \(\displaystyle d\)). First, for each \(\displaystyle v\in H\), we build \(\displaystyle Q_v(x_1,\dots,x_n)\), which attains some integer \(\displaystyle M_v>0\) at \(\displaystyle v\), but vanishes over \(\displaystyle H\setminus\{v\}\). Second, we create \(\displaystyle T(x_1,\dots,x_n)\) with value \(\displaystyle 1\) modulo each \(\displaystyle M_v\) at each element of \(\displaystyle H\). Then an integer combination of \(\displaystyle T\) and the \(\displaystyle Q_v\) will create a polynomial which attains exactly \(\displaystyle 1\) over all elements of \(\displaystyle H\).

Construction of \(\displaystyle Q_v\).

Let \(\displaystyle v\in H\) be arbitrary. First consider

\(\displaystyle P_v(x_1,\dots,x_n):=\prod_{(a_1,a_2,\dots,a_n)\in H\setminus \{v\}} \left( \sum_{i=1}^n (x_i-a_i)^2 \right). \)

Since \(\displaystyle \sum_{i=1}^n (x_i-a_i)^2=0\) iff \(\displaystyle (x_1,\dots,x_n)=(a_1,\dots,a_n)\), we have \(\displaystyle P_v(v)=M_v>0\), but that \(\displaystyle P_v\) vanishes over \(\displaystyle H\setminus\{v\}\).

Moreover, since the coordinates of \(\displaystyle v=(v_1,v_2,\dots,v_n)\) have greatest common divisor \(\displaystyle 1\), Bézout's identity implies that \(\displaystyle \alpha_1v_1+\dots+\alpha_nx_n=1\) for some \(\displaystyle \alpha_i\in\mathbb{Z}\). Now let

\(\displaystyle L_v(x_1,\dots,x_n)=\alpha_1x_1+\dots+\alpha_n x_n.\)

Then for any degree \(\displaystyle d\) larger than \(\displaystyle \deg P_v\), we can take

\(\displaystyle Q_v=P_v\cdot L_v^{d-\deg P_v}\)

to be homogenous, have integer coefficients, and take on value \(\displaystyle M_v\) at \(\displaystyle v\) and \(\displaystyle 0\) over \(\displaystyle H\setminus\{v\}\).

Construction of \(\displaystyle T(x_1,\dots,x_n)\).

Set \(\displaystyle M=2\prod_{v\in H}M_v\). Let the prime factorization of \(\displaystyle M\) be \(\displaystyle M=p_1^{k_1}p_2^{k_2}\dots p_s^{k_s}\). Suppose further that \(\displaystyle d\) is a multiple of \(\displaystyle d_0=n!\cdot \prod_{i=1}^s k_i\varphi\left(p_i^{k_i}\right)\) (we will soon understand the use of this).

Fix some \(\displaystyle i\in\{1,2,\dots,s\}\), and let \(\displaystyle q=p_i^{k_i}=p^k\). We first construct a polynomial which has value \(\displaystyle 1\) mod \(\displaystyle q\) whenever \(\displaystyle x_1,x_2,\dots,x_n\) are integers, not all of them divisible by \(\displaystyle p\). Doing this is essentially an application of PIE. In particular, for each \(\displaystyle j=1,2,\dots,n\), define

\(\displaystyle T_j(x_1,\dots,x_n)=\sum_{1\le i_1< i_2< \dots< i_j\le n} x_{i_1}^{d/j}x_{i_2}^{d/j}\dots x_{i_j}^{d/j}.\)

Then if \(\displaystyle d\) is a multiple of \(\displaystyle n!\cdot k\varphi(q)\), Euler-Fermat implies

\(\displaystyle x^{d/j}\equiv \begin{cases} 1\pmod{q}\quad\text{ha }p\not|x \\ 0\pmod{q}\quad \text{ha }p|x \end{cases},\)

so if exactly \(\displaystyle \nu\) of \(\displaystyle x_1,x_2,\dots,x_n\) are not divisible by \(\displaystyle p\), then

\(\displaystyle T_j(x_1,x_2,\dots,x_n)\equiv \binom{\nu}{j}\pmod{q}.\)

(Here we denote \(\displaystyle \binom\nu j=0\) if \(\displaystyle j>\nu\).) For \(\displaystyle \nu=1,2,\dots,n\), the Binomial Theorem implies

\(\displaystyle (1-1)^\nu=1-\binom \nu1+\binom \nu2\mp\dots\pm \binom \nu n,\)

so all this proves that polynomial

\(\displaystyle T[q]=T_1-T_2\pm\dots\pm T_n\)

has value \(\displaystyle 1\) mod \(\displaystyle q\), whenever at least one of \(\displaystyle x_1,x_2,\dots,x_n\) is not divisible by \(\displaystyle p\).

Having constructed polynomial \(\displaystyle T[q]\) (with degree \(\displaystyle d\)) for each prime power \(\displaystyle q\) in \(\displaystyle M\), we simply choose polynomial \(\displaystyle T\) by making each of its coefficients in its expanded form congruent to the corresponding coefficient of \(\displaystyle T[p_i^{k_i}]\) modulo \(\displaystyle p_i^{k_i}\) for each \(\displaystyle i=1,2,\dots,s\); this amounts to applying the Chinese Remainder Theorem (CRT) \(\displaystyle \binom{d+n-1}{n-1}\) times.

Then another application of CRT shows that \(\displaystyle T(x_1,x_2,\dots,x_n)\equiv 1\pmod{M}\) if \(\displaystyle (x_1,\dots,x_n)\in H\). Indeed, \(\displaystyle T\equiv 1\pmod{p_i^{k_i}}\) for each \(\displaystyle i\), because \(\displaystyle p_i\) cannot divide all of \(\displaystyle x_1,\dots,x_n\).

Finishing up.

Choose \(\displaystyle d\) to be a multiple of \(\displaystyle d_0\) larger than the degree of all the \(\displaystyle P_v\)'s. With this \(\displaystyle d\), we'll have \(\displaystyle T(v)=1+M_v\ell_v\) with some \(\displaystyle \ell_v\in\mathbb{Z}\) for all \(\displaystyle v\in H\). In this case,

\(\displaystyle f(x_1,\dots,x_n)=T(x_1,\dots,x_n)-\sum_{v\in H}\ell_v Q_v(x_1,\dots,x_n)\)

satisfies the required conditions.

Statistics:

9 students sent a solution.
5 points:	Beke Csongor, Bukva Balázs, Gáspár Attila, Imolay András, Janzer Orsolya Lili, Matolcsi Dávid, Schrettner Jakab, Simon Dániel Gábor, Szabó Kristóf.

Problems in Mathematics of KöMaL, September 2017