Let $d(n)$ be the number of divisors of a nonnegative integer $n$ (we set $d(0)=0$). Find all positive integers $d$ such that there exists a two-variable polynomial $P(x,y)$ of degree $d$ with integer coefficients such that: for any positive integer $y$, there are infinitely many positive integers $x$ such that $\gcd(x,y)=1$ and $d(|P(x,y)|) \mid x$, and for any positive integer $x$, there are infinitely many positive integers $y$ such that $\gcd(x,y)=1$ and $d(|P(x,y)|) \mid y$. Allen Wang
Problem
Source: ELMO Shortlist 2024/N8
Tags: Elmo, number theory
MarkBcc168
22.06.2024 18:56
The answer is that all $d$ works. In the solution below, we show that $P(x,y)=x^ay^b$ works.
Let $a$ and $r$ be positive integers. Then, there are infinitely many positive integers $x$ for which the number of (positive integer) divisors of $ax^r$ divides $x$.
Let $\mathcal P = \{p_1, \ldots, p_n\}$ be a finite set of primes that includes
all prime divisors of $a$;
all primes at most $r$; and
a prime $p_1$ coprime to $r$.
We make $x$ divisible by only primes in $\mathcal P$. The idea is that for each prime $p \in \mathcal P$, we pick an exponent $\nu_p(x)$ so that $\nu_p(ax^r)+1$ is very large and has all prime factors in $P$.
We now make this precise. We commit to selecting $x$ to be of the form \[ x = \prod_{i=1}^n p_i^{e_i} \]for some positive integers $e_i$, in which case we have \[ d(ax^r) = \prod_{i=1}^n \left( re_i + \nu_{p_i}(a) + 1 \right). \]
Let $y = p_1^M$ for some large integer $M$. Since $y$ is coprime to $r$, there exists $z_i \in \{1, \cdots, r\}$ such that $ \nu_{p_i}(a)+1 \equiv z_i y\pmod r$, so we take $e_i$ such that $re_i + \nu_{p_i}(a)+1 = yz_i$. This implies that
$$d(ax^r) = y^n \prod_{i=1}^n z_i,$$which contains only primes in $\mathcal P$ with multiplicity at most $n(M+\log_2 r)$.
Given how the $e_i$ are selected, we also have
$$e_i = \frac{1}{r}(z_i y - O(1)) \ge \frac{y}{r} - O(1) = \frac{p_1^M}{r} - O(1).$$For sufficiently large $M$, $e_i$ exceeds $n(M+\log_2 r)$, which certainly implies $d(ax^r) \mid x$.
IAmTheHazard
22.06.2024 19:02
Here's the author's (i.e. my) original solution, using a different polynomial. The fact that $x^ay^b$ works was first found by Advaith Avadhanam The answer is that all $d$ work. In fact, choosing $P(x,y)=(x+y)^d$ will do the job. By symmetry it suffices to show that for any positive integer $y$, there are infinitely many choices of $x \perp y$ such that $d(|P(x,y)|) \mid x$. We commit to choosing $x$ of the form $p^k-y$, so $d(|P(x,y)|)=kd+1$. Unless $p \mid y$, which happens finitely often, this guarantees that $x \perp y$. Suppose that we can find some prime $q$ dividing $y^d-1$ such that $q \equiv 1 \pmod{d}$, so we can write $q=kd+1$ for some positive integer $k$. Then $y$ is a $k$-th power modulo $q$ for order reasons, and since $q \nmid y$ there exists some nonzero residue $a$ such that $a^k \equiv y \pmod{q}$. By Dirichlet we can then find infinitely many primes $p \equiv a \pmod{q}$, whence $kd+1=q \mid p^k-y$ as desired. In most cases, such a prime $q$ is supplied by Zsigmondy's theorem: any primitive prime divisor $q$ of $y^d-1$ (i.e. prime dividing $y^d-1$ which doesn't divide $y^k-1$ for any $0<k<d$) must have $\mathrm{ord}_q(y)=d$ by definition, hence $d \mid p-1$. We now deal with the following edge cases: If $y=1$, then such a prime $q$ obviously exists by Dirichlet's theorem. If $d=1$ and $y=2$, then such a prime $q$ obviously exists. If $d=2$ and $y+1 \neq 2$ is a power of $2$, then $y-1$ is not a power of $2$ and hence has some odd prime divisor, which then divides $y^2-1=(y-1)(y+1)$. Letting $q$ be this odd prime divisor works. If $d=6$ and $y=2$, then $q=7$ works. This finishes the problem. $\blacksquare$