HMMT February

We claim the answer is every complex number $a+b i$ where $a$ and $b$ are rationals whose simplified denominators are not multiples of any prime congruent to 1 modulo 4 . The proof consists of two main steps: proving that powers of $p \equiv 1 \bmod 4$ can't appear in the denominator, and showing all possible values are attainable. We show three different methods of the former part. $\text{* Impossibility}$ via elementary number theory} We first show that no other values are possible. Indeed, it is well known that any polynomial that maps $\mathbb{Z}$ into itself must be of the form $P(n)=\sum_{k=0}^{m} a_{k}\binom{n}{k}$ for integers $a_{k}$ and where we treat the binomials as formal polynomials. This may be proved via finite differences. It is therefore sufficient to show that for any $k,\binom{i}{k}$ can be simplified to a fraction of the form $\frac{a+b i}{c}$, where $a, b, c$ are integers and $c$ is not divisible by any prime that is 1 modulo 4 . We have that $$\binom{i}{k}=\frac{i \cdot(i-1) \cdot \ldots \cdot(i-(k-1))}{k \cdot(k-1) \cdot \ldots \cdot 1}$$ Pick any prime $p$ that is 1 modulo 4 . Since $p$ is 1 modulo 4 , there exist distinct residue classes $x$, $y$ modulo $p$ so that $x^{2} \equiv y^{2} \equiv-1 \bmod p$. We will show that for every integer, $r \leq k$ divisible by $p$ in the denominator, we can pair it with a disjoint set, $\left\{r_{x}, r_{y}\right\}$, of two positive integers less than $k$ in these two residue classes so that $\left(i-r_{x}\right)\left(i-r_{y}\right)$ has real and complex parts divisible by the highest power of $p$ dividing $r$. Thus any factor of $p$ that is 1 modulo 4 in the denominator, exists in the numerator as well, which suffices. Start with $u=1$ and repeat the following process for increasing $u$ until there is nothing left to do. For every positive integer $j \leq k$ such that $p^{u} \mid j$, there exist unique $j_{x}^{\prime}, j_{y}^{\prime} \in\left[j-p^{u}, j\right)$ satisfying $j_{x}^{\prime} \equiv x \bmod p, j_{y}^{\prime} \equiv y \bmod p$ and $p^{u} \mid j_{x}^{\prime}{ }^{2}+1, j_{y}^{\prime}{ }^{2}+1$. So pair $j$ with the set $\left\{j_{x}^{\prime}, j_{y}^{\prime}\right\}$, and pair its old partners if any to the old partners of $j_{x}^{\prime}$ and $j_{y}^{\prime}$. The important feature of this assignment process is that we always have at step $u, p^{\min \left(u, v_{p}(r)\right)} \mid r_{x}+$ $r_{y}, r_{x}^{2}+1, r_{y}^{2}+1$. Thus at the end of the process, $\left(i-r_{x}\right)\left(i-r_{y}\right)=\frac{1}{2}\left(\left(r_{x}+r_{y}\right)^{2}-\left(r_{x}^{2}+1\right)-\left(r_{y}^{2}+1\right)\right)-$ $\left(r_{x}+r_{y}\right) i$ has real and complex parts divisible by $p^{v_{p}(r)}$ as claimed. $\text{* Impossibility}$ via Gaussian Integers} We work in the ring of Gaussian Integers $\mathbb{Z}*=\{a+b i: a, b \in \mathbb{Z}\}$, which is sitting inside number field $\mathbb{Q}*=\{a+b i: a, b \in \mathbb{Q}\}$. It's well-known that $\mathbb{Z}*$ is a unique factorization domain. For any Gaussian prime $\pi$, let $\nu_{p i}(z)$ denote the exponent of $\pi$ in the factorization of $z$. Let $p \equiv 1(\bmod 4)$ be a prime. It's well known that $p$ splits into two Gaussian primes, $p=\pi \bar{\pi}$. Note that it suffices to show $$\begin{equation*} \nu_{\pi}(i(i-1)(i-2) \ldots(i-k+1)) \geq \nu_{\pi}(k!)=\left\lfloor\frac{k}{p}\right\rfloor+\left\lfloor\frac{k}{p^{2}}\right\rfloor+\ldots \tag{*} \end{equation*}$$ because the similar statement for $\bar{\pi}$ will follow. The key claim is the following: Claim. For any integer $t \geq 1$ and $n$, at least one of numbers $i-n-1, i-n-2, \ldots, i-n-p^{t}$ is divisible by $\pi^{t}$. Proof. First, we show that there exists integer $r$ such that $\pi^{t} \mid i-r$. To that end, by Hensel's lemma, there exists an integer $s$ for which $p^{t} \mid s^{2}+1$. Thus, $$\pi^{t} \bar{\pi}^{t} \mid(s-i)(s+i)$$ However, $\operatorname{gcd}(s-i, s+i) \mid 2$, so $\pi^{t}$ must divide either $s-i$ or $s+i$. In particular, $r=s$ or $r=-s$ work. To complete the problem, pick the unique $x \in\left\{1,2, \ldots, p^{t}\right\}$ such that $n+x \equiv r(\bmod p)^{t}$, so $i-(n+x) \equiv$ $i-r\left(\bmod p^{t}\right)$ and hence divisible by $\pi^{t}$. Using the claim repeatedly, we find that among numbers $i, i-1, i-2, \ldots, i-k+1$, - at least $\left\lfloor\frac{k}{p}\right\rfloor$ are divisible by $\pi$ (this is by selecting $\left\lfloor\frac{k}{p}\right\rfloor$ disjoint contiguous block of size $p$ ), - at least $\left\lfloor\frac{k}{p^{2}}\right\rfloor$ are divisible by $\pi^{2}$, - at least $\left\lfloor\frac{k}{p^{3}}\right\rfloor$ are divisible by $\pi^{3}$, ・ $\quad \vdots$ Using these altogether suffices to prove $(*)$. $\text{* Impossibility}$ via $\boldsymbol{p}$-adics} Let $P(i)=a+b i$, and note that $P(-i)=a-b i$. Fix some $p \equiv 1 \bmod 4$, and consider the $p$-adic integers $\mathbb{Z}_{p}$ lying in $\mathbb{Q}_{p}$. Note that $x^{2}+1=0$ has a solution in $\mathbb{Z}_{p}$, and hence $\pm i \in \mathbb{Z}_{p}$. Now take a sequence of integers $m_{k}$ converging to $i$ in $\mathbb{Z}_{p}$, so $-m_{k}$ converges to $-i$. Then since polynomials are continuous, $P\left(m_{k}\right)$ converges to $P(i)$ and $P\left(-m_{k}\right)$ converges to $P(-i)$, so $P\left(m_{k}\right)+P\left(-m_{k}\right)$ and $P\left(m_{k}\right)-P\left(-m_{k}\right)$ converge to $2 x$ and $2 y i$ respectively. Finally, since $P\left(m_{k}\right)$ and $P\left(-m_{k}\right)$ are integers, they have nonnegative $p$-adic valuation, and so by continuity, $2 x$ and $2 y$ have nonegative $p$-adic valuation. Thus, when written as simplified fractions, $a$ and $b$ cannot have any powers of $p$ in their denominator, as desired. $\text{* Construction}$ We now show that all of the claimed values are possible. The set of polynomials, $P$, taking $\mathbb{Z}$ to itself is closed under addition and multiplication, and therefore so is the set of possible values of $P(i)$. It clearly contains $\mathbb{Z}*$ by taking linear polynomials. Thus it suffices to show that $p^{-1}$ is attainable for every prime $p$ that is not 1 modulo 4. $2^{-1}$ is achieved by taking $P(x)=\frac{1}{4} x(x-1)(x-2)(x-3)+3$, so we may focus our attention only on the case where $p$ is 3 modulo 4 . It is then further sufficient to show that some $(a+b i) p^{-1}$ is attainable for $a, b \in \mathbb{Z}$ not both divisible by $p$ because then $(a-b i) \cdot(a+b i) p^{-1}=\left(a^{2}+b^{2}\right) p^{-1}$ is also obtainable and cannot be an integer since -1 is not a quadratic residue modulo $p$, so Bézout's Theorem shows that $p^{-1}$ is attainable. Now with this goal in mind, observe that $$\left|\binom{i}{p}\right|=\frac{1^{2} \cdot\left(1^{2}+1^{2}\right) \cdot \ldots \cdot\left(1^{2}+(p-1)^{2}\right)}{p \cdot(2 p-1) \cdot \ldots \cdot 1}$$ has denominator divisible by $p$, but numerator not divisible by $p$ since again, -1 is not a quadratic residue modulo $p$. Hence we can find some integer $m$ so that $m\binom{i}{p}=(a+b i) p^{-1}$ where $a$ and $b$ that aren't both divisible by $p$ as desired.