\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{USEMO 2019/2}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 10}
\maketitle

\section*{Problem}
Let $\ZZ[x]$ denote the set of single-variable
polynomials in $x$ with integer coefficients.
Find all functions $\theta \colon \ZZ[x] \to \ZZ[x]$
(i.e.\ functions taking polynomials to polynomials) such that
\begin{itemize}
  \ii for any polynomials $p,q \in \ZZ[x]$,
  $\theta(p+q) = \theta(p) + \theta(q)$;
  \ii for any polynomial $p \in \ZZ[x]$,
  $p$ has an integer root if and only if $\theta(p)$ does.
\end{itemize}

\section*{Video}
\href{https://www.youtube.com/watch?v=V2TNgUwbs6A&list=PLi6h8GM1FA6yfhMMNqJi1mht4KmZnXpj6}{\texttt{https://youtu.be/V2TNgUwbs6A}}

\section*{External Link}
\url{https://aops.com/community/p15412166}

\newpage

\section*{Solution}
The answer is that
\[ \theta(x) = r(x) \cdot p(\pm x + c) \]
for any choice of $c \in \ZZ$,
$r(x)$ without an integer root,
with the choice of sign fixed.
For the converse direction we present two approaches.

\paragraph{First solution.}
It's clear that this works, so we prove it is the only one.
Let $r(x) = \theta(1)$,
which has no integer root since the constant $1$ has no roots at all.

\bigskip

\textbf{Part 1.}
We fix a positive integer $n$ and start by determining $\theta(x^n)$
which is the bulk of the problem.
Let $f(x) = \theta(x^n)$.
We look at
\[ \theta(ax^n+b) = a \cdot f(x)  + b \cdot r(x). \]
Let $g(x) = f(x) / r(x)$, a quotient of two polynomials
whose denominator never vanishes.
By using the problem condition in both directions,
varying $x \in \ZZ$ and $-b/a \in \QQ$, we find that
\[ \frac{f(x)}{r(x)} \text{ takes on exactly the values }
  \dots, (-2)^n, (-1)^n, 0^n, 1^n, 2^n, 3^n, \dots
  \text { for } x \in \ZZ \]
So let $g(x) = f(x) / r(x)$ now.

\begin{claim*}
  [Rational functions can't be integer-valued forever]
  Since $g$ maps integers to integers,
  it must actually be a polynomial with rational coefficients.
\end{claim*}
\begin{proof}
  We will only need the condition that $g$ maps integers to integers.

  If not, then by the division algorithm,
  we have $g(x) = d(x) + \frac{f_1(x)}{f_2(x)}$
  for some polynomials $d(x), f_1(x), f_2(x)$ in $\QQ[x]$
  with $\deg f_2 > \deg f_1 \ge 0$.
  There exists an integer $D$ such that $D \cdot d(x) \in \ZZ[x]$
  (say the lcm of the denominators of the coefficients of $g$).

  But for large enough integers $x$ the value of $\frac{f_1(x)}{f_2(x)}$
  is a nonzero and has absolute value less than $\frac 1D$.
  This is a contradiction.
\end{proof}

\begin{remark*}
  You can't drop the condition that $g$ has rational
  (rather than integer) coefficients in the proof above;
  consider $g(x) = \half x(x+1)$ for example.

  A common wrong approach is to try to use
  the same logic on $\theta(x^n) / \theta(x^{n-1})$ for $n \ge 2$.
  This doesn't work since $\theta(x^n)$ and $\theta(x^{n-1})$
  could have a common root for $n \ge 2$
  and therefore the problem condition essentially says nothing.
\end{remark*}

Let $C$ be an integer divisible by every denominator in the coefficients of $g$.
Then apparently
\[ h(x) = C^n \cdot g(x) \]
is a polynomial which only takes only $n$th powers as $x \in \ZZ$.

\begin{claim*}
  [\href{https://aops.com/community/q2h1215192p6307719}{Polya and Szego}]
  Since $h$ is a polynomial with integer coefficients
  whose only values are $n$th powers,
  it must itself be the $n$th power of a polynomial.
\end{claim*}
\begin{proof}
  This is a classical folklore problem,
  but we prove it for completeness.

  Decompose $h$ into irreducible factors as
  \[ h(x) = c \cdot f_0(x)^{e_0}
    \cdot f_1(x)^{e_1} \cdot f_2(x)^{e_2} \cdot f_3(x)^{e_3} \cdot
    \dots \cdot f_m(x)^{e_m} \]
  where the $f_i$ are nonconstant and $c$ is an integer,
  and $e_i > 0$ for all $i > 0$.
  We also assume $m > 0$.

  We use the following facts:
  \begin{itemize}
    \ii In general, if $A(x), B(x) \in \ZZ[x]$ are coprime,
    then $\gcd(A,B)$ is bounded by some constant $C_{A,B}$.
    This follows by Bezout lemma.

    \ii If $A(x) \in \ZZ[x]$ is a nonconstant polynomial,
    then there are infinitely many primes dividing
    some element in the range of $A$.
    This is called Schur's theorem.

    \ii Let $A(x) \in \ZZ[x]$ be an irreducible polynomial,
    and let $A'(x)$ be its derivative.
    Then if $p$ is prime and $p > C_{A,A'}$,
    and $p$ has root in $\FF_p$,
    then there exists $x$ with $\nu_p(A(x)) = 1$.
    This follows by Hensel lemma.
  \end{itemize}

  Now for the main proof.
  By the above facts and the Chinese remainder theorem
  (together with Dirichlet theorem),
  we can select enormous primes $p_1 < p_2 < \dots < p_m < q$
  (exceeding $c$, $e$, $\max e_i$, $\max C_{f_i, x}$,
  $\max C_{f_i, f_j}$ for all $i$ and $j$)
  and a single integer $N$ satisfying the following constraints:
  \begin{itemize}
    \ii $\nu_{p_i}(f_i(N)) = 1$ for all $i = 1, \dots, m$,
    by requiring $N \equiv t_i \pmod{p_i^2}$ for suitable
    constant $t_i$ not divisible by $p_i$
    (because of Hensel lemma);

    \ii $p_i \nmid f_j(N)$ whenever $i \neq j$;
    this follows by the fact that $p_i > C_{f_i,f_j}$;
  \end{itemize}
  Now look at the value of $f(N)$.
  It has
  \begin{align*}
    \nu_{p_1}(f(N)) &= e_1 \\
    \nu_{p_2}(f(N)) &= e_2 \\
    &\vdotswithin{=} \\
    \nu_{p_m}(f(N)) &= e_m.
  \end{align*}
  Now $f(N)$ is a $n$th power
  so $n$ divides all of $e_1$, \dots, $e_m$.
  Finally $c$ must be an $n$th power too.
\end{proof}

So $h(x)$ is an $n$th power; thus so is $g(x)$.
Let's write $g(x) = p(x)^n$ then;
so we find that the range of $p(x)$ contains either $k$ or $-k$,
for every integer $k$.
For density reasons, this forces $p$ to be linear,
and actually of the form $p(x) = \pm x + c$ for some constant $c$.

\bigskip

\textbf{Part 2.}
We have now shown $\theta(x^n) = (\pm x + c)^n r(x)$,
for every $n$, for some sign and choice of $c$ depending possibly on $n$.
It remains to show that the choices of signs and constants are compatible
across the different values of $n$.
So let's verify this.

By applying a suitable transformation on $x$
let's assume $\theta(x) = x$ for simplicity.
Then look at $\theta(x^n + a x) = (\pm x + c)^n + a x$
for choices of integers $a$.
This is apparently supposed to have a root for each choice of $a$,
but if $c \neq 0$, this means $\frac 1x(\pm x + c)^n$
can take any integer value, which is obviously not true for density reasons.
This means $c = 0$, so it shows $\theta(x^n) = \pm x^n$ for any integer $n$.

Finally, by considering $\theta(x^n + x - 2) = \pm x^n - x + 2$,
we see the sign must be $+$ for the RHS to have an integer root.
This finishes the proof.

\paragraph{Second solution, outline (by contestants).}
The solution is like the previous one,
but replaces the high-powered Polya and Szego with the following simpler result.
\begin{claim*}
  [Odd-degree polynomials are determined by their range]
  Let $P(x) \in \ZZ[x]$ be an odd-degree polynomial.
  Let $Q(x)$ be another polynomial with the same range as $P$ over $\ZZ$.
  Then $P(x) = Q(\pm x + c)$ for some $\pm$ and $c$.
\end{claim*}
\begin{proof}
  First, $Q$ also has odd degree since it must be unbounded in both directions.
  By negating if needed, assume $Q$ has positive leading coefficient.

  Take a sufficiently large integer $n_0$
  such that $P(x)$ and $Q(x)$ are both
  strictly increasing for $x \ge n_0$,
  and moreover $P(n_0) > \max_{x < n_0} P(x)$,
  $Q(n_0) > \max_{x < n_0} P(x)$.
  Then take an even larger integer $n_1 > n_0$ such that
  $\min(P(n_1), Q(n_1)) > \max(P(n_0), Q(n_0))$.
  Choose $n_2 > n_0$ such that $P(n_1) = Q(n_2)$.
  We find that this implies
  \begin{align*}
    P(n_1) &= Q(n_2) \\
    P(n_1+1) &= Q(n_2+1) \\
    P(n_1+2) &= Q(n_2+2) \\
    P(n_1+3) &= Q(n_2+3)
  \end{align*}
  and so on.
  So $P$ is a shift of $Q$ as needed.
\end{proof}

This is enough to force $\theta(x^n) = (\pm x + c)^n r(x)$
when $n$ is odd.
When $n$ is even, for each integer $k$ one can consider
\[ \theta(kx^{n+3} + x^n) = k\theta(x^{n+3}) + \theta(x^n) \]
and use the claim on $\theta(x^{n+3})$ and $\theta(kx^{n+3}+x^n)$
to pin down $\theta(x^n)$.

\paragraph{Third solution (from author).}
The answers are as before
and we prove only the converse direction.

\begin{lemma*} Given two polynomials $P,Q\in\ZZ[x]$, if $P+nQ$ has an integer root for all $n$, then either $P$ and $Q$ share an integer root or $P(x)=\left(\frac{x+m}k\right)Q(x)$ for some integers $m,k$ with $k\neq 0$.
\end{lemma*}
\begin{proof} Let $d=\gcd(P(0),Q(0))$ so $P(0)=dr$ and $Q(0)=ds$. Now, for an integer root $k_n$ of $P+nQ$,
  \[ k_n|P(0)+nQ(0)=dr+nds=d(r+ns). \]
Let $p$ be a prime $\equiv r\bmod s$, of which there are infinitely many by Dirichlet's theorem. Now, for $n=\frac{p-r}{s}$, we have
\[ k_n|dp. \]
As the divisors of $dp$ are exactly those of $d$ times $1$ or $p$, there exists a (not necessarily positive) divisor $j$ of $d$ and a $t\in\{1,p\}$ so that $k_n=dt$ for infinitely many $n$. In the first case, we have that $P(j)+nQ(j)=0$ for infinitely many $n$ and some fixed $j$, which implies that $j$ is a root of both $P$ and $Q$. In the second case, we have, noting $p=r+ns$, that
\[ P(j(r+ns))+nQ(j(r+ns))=0. \]
As this holds for infinitely many $n$, we may rewrite it as a polynomial equation
\[ P(x)=(ax+b)Q(x) \]
for some rational $a,b$. Now, we know that $(ax+b+n)Q(x)$ has a rational root for all $n\in\ZZ$. If $Q$ has an integer root then $P$ does as well and we are in our first case; otherwise, $\frac{n+b}{a}\in\ZZ$ for all $n\in\ZZ$. This implies that $1/a\in\ZZ$, let it be $k$. Then $b/a\in\ZZ$; let it be $m$.
This finishes the proof.
\end{proof}

Now, let $P_n(x)=f(x^n)$. We claim that $P_1(x)=(\pm x+t)P_0(x)$ for some $t\in\ZZ$. Indeed, $P_1+nP_0$ has an integer root for all $n$, so either $P_1$ and $P_0$ share an integer root or $P_1(x)=\left(\frac{x+m}k\right)P_0(x)$ for some $m,k\in\ZZ$. They clearly cannot share a root, since $P_0(x)$ cannot have any integer roots. Now,
\[ kP_1(x)+P_0(x)=(x+m+k)P_0(x) \]
has an integer root, so $kx+1$ must as well, and thus $k=\pm 1$, as desired. Now, we see that
\[ \theta\left(a(x^n-c^n)+b(x-c)\right)=a\big(P_n(x)-c^nP_0(x)\big)+b\big(P_1(x)-cP_0(x)\big) \]
has an integer root for any $c,a,b$. Let $Q=P_n-c^nP_0$ and $R=P_1-cP_0$. Since $aQ+bR$ has an integer root for all $a,b\in\ZZ$, we can apply our lemma on both the pair $(Q,R)$ and $(R,Q)$; if they do not share an integer root, then $Q$ must be a linear polynomial times $R$ and $R$ must be a linear times $Q$, a contradiction unless they are both $0$ (in which case they share any integer root). So, $Q$ and $R$ share an integer root. We have
\[ R(x)=P_1(x)-cP_0(x)=(\pm x+t-c)P_0(x), \]
and $P_0$ has no integer root as $1$ has no integer root, so we have that $\pm(c-t)$ is the only integer root of $R$ and is thus also a root of $Q$; in particular
\[ P_n(\pm(c-t))=c^nP_0(\pm(c-t)) \]
for all $c\in\ZZ$. This is a polynomial equation that holds for infinitely many $c$ so we must have that
\[ P_n(\pm(x-t))=x^nP_0(\pm(x-t))\implies P_n(x)=(\pm x+t)^nP_0(x). \]
Thus, if $Q(x)=\sum_{i=0}^d a_ix^i$,
\[ \theta(Q(x))=\theta\left(\sum_{i=0}^d a_ix^i\right)=\sum_{i=0}^d a_i(\pm x+t)^i P_0(x)=P_0(x)Q(\pm x+t), \]
finishing the proof.

\end{document}
