\documentclass[11pt]{scrartcl}
\usepackage{evan}
\begin{document}
\title{USEMO 2022/5}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 103}
\maketitle
\section*{Problem}
Let $\tau(n)$ denote the number of positive integer divisors
of a positive integer $n$ (for example, $\tau(2022)=8$).
Given a polynomial $P(X)$ with integer coefficients,
we define a sequence $a_1$, $a_2$, \dots\ of nonnegative integers by setting
\[
a_n = \begin{cases}
\gcd\big( P(n), \; \tau(P(n)) \big) & \text{if } P(n) > 0 \\
0 & \text{if } P(n) \le 0
\end{cases}
\]
for each positive integer $n$.
We then say the sequence \emph{has limit infinity}
if every integer occurs in this sequence only finitely many times (possibly not at all).
Does there exist a choice of $P(X)$ for which
the sequence $a_1$, $a_2$, \dots\ has limit infinity?
\section*{Video}
\href{https://www.youtube.com/watch?v=dC9VpiGVRqs}{\texttt{https://youtu.be/dC9VpiGVRqs}}
\section*{External Link}
\url{https://aops.com/community/p26379812}
\newpage
\section*{Solution}
We claim the answer is no, such $P$ does not exist.
Clearly we may assume $P$ is nonconstant with positive leading coefficient.
Fix $P$ and fix constants $n_0, c > 0$ such that $c = P(n_0) > 0$.
We are going to prove that infinitely many terms of the sequence
are at most $c$.
We start with the following lemma.
\begin{claim*}
For each integer $n \ge 2$, there exists an integer $r = r(n)$ such that
\begin{itemize}
\ii For any prime $p$ which is at most $n$,
we have $\nu_p(P(r)) = \nu_p(c)$.
\ii We have \[ c \cdot \prod_{\text{prime }p \le n}
\le r \le 2c \cdot \prod_{\text{prime }p \le n} p. \]
\end{itemize}
\end{claim*}
\begin{proof}
This follows by the Chinese remainder theorem:
for each $p \le n$ we require $r \equiv n_0 \pmod{p^{\nu_p(c)+1}}$,
which guarantees $\nu_p(P(r)) = \nu_p(P(n_0)) = \nu_p(c)$.
Then there exists such an $r$ modulo $\prod_{p \le n} p^{\nu_p(c)+1}$ as needed.
\end{proof}
Assume for contradiction that all $a_i$ are eventually larger than $c$.
Take $n$ large enough that $n > c$ and $r = r(n)$ has $a_r > c$.
Then consider the term $a_r$:
\begin{itemize}
\ii Using the conditions in the lemma
it follows there exists a prime $p_n > n$
which divides $a_r = \gcd(P(r), \tau(P(r)))$
(otherwise $a_r$, which divides $P(r)$, is at most $c$).
\ii As $p_n$ divides $\tau(P(r))$, this forces $P(r)$ to be divisible by
(at least) $q_n^{p_n-1}$ for some prime $q_n$.
\ii For the small primes $p$ at most $n$,
we have $\nu_p(P(r)) = \nu_p(c) < c < n \le p_n - 1$.
It follows that $q_n > n$.
\ii Ergo, \[ P(r) \ge q_r^{p_r-1} > n^n. \]
\end{itemize}
In other words, for large enough $n$, we have the asymptotic estimate
\begin{align*}
n^n &< P(r) = O(1) \cdot r^{\deg P} \\
&= O(1) \cdot c^{\deg P} \cdot \prod_{\text{prime } p \le n} p^{\deg p} \\
&< O(1) \cdot n^{\deg P \cdot \pi(n)}
\end{align*}
where $\pi(n)$ denotes the number of primes less than $n$.
For large enough $n$ this is impossible since the primes have zero density:
\[ \lim_{n \to \infty} \frac{\pi(n)}{n} = 0. \]
\begin{remark*}
For completeness, we outline a short elementary proof that
$\lim_{n \to \infty} \frac{\pi(n)}{n} = 0$.
For integers $M > 0$ define
\[ \delta(M) \coloneqq \prod_{p \le M} \left( 1 - \frac 1p \right). \]
Then $\pi(n) < \delta(M)n + \prod_{p \le M} p$,
so it suffices to check that $\lim_{M \to \infty} \delta(M) = 0$.
But
\[
\frac{1}{\delta(M)}
= \prod_{p \le M} \left( 1 - \frac 1p \right)\inv
= \prod_{p \le M} \left( 1 + \frac1p + \frac{1}{p^2} + \dots \right)
\ge 1 + \frac 12 + \dots + \frac 1M
\]
which diverges for large $M$.
\end{remark*}
\end{document}