For a prime $p$, let $\mathbb{F}_p$ denote the integers modulo $p$, and let $\mathbb{F}_p[x]$ be the set of polynomials with coefficients in $\mathbb{F}_p$. Find all $p$ for which there exists a quartic polynomial $P(x) \in \mathbb{F}_p[x]$ such that for all integers $k$, there exists some integer $\ell$ such that $P(\ell) \equiv k \pmod p$. (Note that there are $p^4(p-1)$ quartic polynomials in $\mathbb{F}_p[x]$ in total.) Aprameya Tripathy
Problem
Source: ELMO 2024/6
Tags: number theory, polynomial, Elmo
21.06.2024 19:15
We claim $\boxed{p=2,3,7}$. Some constructions for $p=2$ and $p=3$ are $x^4$ and $x^4-x^2+x$, respectively. Suppose that a polynomial $P$ works. Then, $P(0)$, $P(1)$, $\ldots$, $P(p-1)$ must be a permutation of $0$, $1$, $\ldots$, $p-1$ modulo $p$. Notice $\sum_{i=0}^{p-1}P(i)^j\equiv0\pmod p$ for all $j\leq p-2$ since $\sum_{i=0}^{p-1}P(i)^j\equiv\sum_{i=0}^{p-1}i^j\equiv0\pmod p$. In particular, this implies that for all $j\leq p-2$, the sum of the $x^{(p-1)k}$ coefficients of $P(x)^j$ for positive integers $k$ must be a multiple of $p$, otherwise the sum would not be a multiple of $p$. If $p\equiv1\pmod4$, $P(x)^{\frac{p-1}4}$ has a $x^{p-1}$ coefficient of $1$, which is a contradiction. If $p\equiv3\pmod4$ and $p>3$, multiplying $P$ by a constant and subtracting $P(0)$ allows us to assume without loss of generality $P$ is monic and $P(0)=0$. Let $P(x)=x^4+ax^3+bx^2+cx$. The polynomial $P\left(x-\frac a4\right)$ modulo $p$ also satisfies the same conditions, so assume without loss of generality $a=0$. Now, $P(x)=x^4+bx^2+cx$. We have $$P(x)^{\frac{p+1}4}=x^{p+1}+b\frac{p+1}4x^{p-1}+\cdots,$$so since $p+1<2(p-1)$, we get $b=0$. Now, $P(x)=x^4+cx$, so $$P(x)^{\frac{p+5}4}=x^{p+5}+c\frac{p+5}4x^{p+2}+c^2\binom{\frac{p+5}4}2x^{p-1}+\cdots.$$If $p>7$, then $p+5<2(p-1)$, so $c^2\binom{\frac{p+5}4}2$ must be a multiple of $p$. This means $0\equiv c^2\frac{(p+5)(p+1)}{32}\equiv\frac5{32}c^2\pmod p$, so $c=0$. However, $P(1)=P(-1)=1$, contradiction. Now, if $p=7$, we get $7\mid1+3c^2$, so $c=\pm3$, and we can verify that the polynomial $P(x)=x^4+3x$ works.
21.06.2024 19:17
pull up to https://en.wikipedia.org/wiki/Permutation_polynomial.
21.06.2024 19:51
Apparently, the original wording was $\mathbb F_p[x]$ be the set of quartic polynomials? I will only show $p\leq 7$. Disproving $p=5$ and constructing $p\in\{2,3,7\}$ is left as an exercise. Assume $p\geq 11$. By translation, we can WLOG that the quartic is $P(x) = x^4+ax^2+bx$. If we can find $(x,y)$ such that $$\frac{P(x)-P(y)}{x-y} = (x+y)(x^2+y^2) + a(x+y) + b \equiv 0\pmod p,$$but $x\not\equiv y\pmod p$, then we are done. If $b=0$, then the curve factors to $(x+y)(x^2+y^2+a)$, so it's easy to find a solution by QR. Henceforth assume $b\neq 0$. Notice that there are at most $3$ solutions when $x\equiv y\pmod p$. Thus, it suffices to show that the cubic curve $(x+y)(x^2+y^2)+a(x+y)+b=0$ has at least $4$ solution modulo $p$. We now make a change of variable. Set $s=x+y$ and $t=x-y$. Thus, we may rewrite this equation to \begin{align*}\frac{s^3+st^2}2 + as + 2b = 0 &\iff -st^2 = s^3+2as+b \\ &\iff -\frac{t^2}{s^4} = 1 + \frac{2a}{s^2} + \frac{b}{s^3}. \end{align*}Notice that $s=0$ is not a solution if $b\neq 0$. Hence, if we let $u=\tfrac 1s$ and $v=\tfrac t{s^2}$, then $v^2 = bu^3+2au+1$. This is an equation of an elliptic curve (up to the quadratic twist of a Weierstrass form). Thus, by Hasse-Weil bound, there are at least $p+1-2\sqrt p \geq (\sqrt{11}-1)^2 > 3$ solutions modulo $p$, done.
21.06.2024 20:03
21.06.2024 20:16
21.06.2024 20:24
So, people were solving ELMO problems some 127 years ago. In fact, they did the same not just for degree $4$, but all $d \le 5$ (and with exactly the same method...). See also here for a very similar problem (with the same solution idea) posted on AoPS some time ago.
21.06.2024 20:29
Tintarn wrote: So, people were solving ELMO problems some 127 years ago. In fact, they did the same not just for degree $4$, but all $d \le 5$ (and with exactly the same method...). See also here for a very similar problem (with the same solution idea) posted on AoPS some time ago. India TST 2024 Day 3 Problem 2 was also based on the same/similar idea.
21.06.2024 20:54
edit: awww mark beat me to it. I'm not super experienced with elliptic curves (LOL), so can someone check this? The answer is $p \in \{2, 3, 7\}$. For $p = 2$, $x^4$ works, for $p = 3$, $x^4 - x(x-2)$ works, for $p = 7$, $x^4 + 3x$ works. We now assume $p \geq 5, p \neq 7$ and prove all such $p$ fail. By a change of variables $x \mapsto x - c$, and noting that shifting the polynomial does not change whether or not it is a bijection, it suffices to check the polynomials of the form \begin{align*} P(x) &= x^4 + ax^2 + bx \end{align*}Now, suppose $P(x) = P(y)$ for some distinct $x, y \in \mathbb{F}_p$. Then we have \begin{align*} \frac{P(x) - P(y)}{x - y} &= 0 \\ (x+y)(x^2 + y^2) + a(x+y) + b &= 0 \end{align*}Substitute $u = x^2 + y^2$, $v = x + y$. Note that there exist distinct $x, y$ corresponding to $u, v$ precisely iff $2u - v^2$ is a nonzero square in $\mathbb{F}_p$. Now the above would imply \begin{align*} uv + av + b &= 0 \\ u + a &= -\frac{b}{v} \end{align*}So it suffices to find $a, b$ such that there exists a $v \in \mathbb{F}_p$ such that \begin{align*} \bigg(\frac{-2b/v-2a-v^2}{p}\bigg) &= 1 \end{align*}By a change of variables (involving $v \mapsto 1/v$), it suffices to find $a', b'$ such that there exists a solution $(x, y)$ where $y \neq 0$ in the equation \begin{align*} Q(x) := x^3 + a'x^2 + b' &= y^2 \end{align*}Manually check the cases $p = 2, 3$. Now in the cases $p \geq 5$, if the discriminant of $Q$ is zero, then $Q$ has multiple roots, and so it can be factored as either $Q(x) = x^3$ or $Q(x) = (x-c)^2(x-d)$. In the former case $(1, 1)$ gives the desired solution; in the latter case either $(d + 1, d+1-c)$ or $(d + 4, d+4-c)$ works. If the discriminant is nonzero, then the given equation defines an elliptic curve over $\mathbb{F}_p$, and therefore by the Hasse bound (lol) the number of solutions $(x, y)$ is at least $p - 2\sqrt{p}$. For $p \geq 11$ this is at least $4$, so since there are at most three solutions where $y = 0$, this gives us a desired solution. We now check the case $p = 5$. In the case $p = 5$, note that since the polynomials of degree $\leq 4$ bijectively correspond with the functions on $\mathbb{F}_p$, each such polynomial is equal to the polynomial \begin{align*} \sum_i -P(i)(x-i+1) \ldots (x-i+p-1). \end{align*}However, if $P$ is bijective, then the $x^4$ term must be $\sum_i -P(i) = 0$, so no quartic works.
21.06.2024 20:57
The answer is only $p=2$ (with $x^4$), $p=3$ (with $x^4-x^2+2x$) and $p=7$ (with $x^4+3x$), all of which can be quickly checked to work. The key idea is the following: Theorem (Hermite): Suppose $f\in \mathbb{F}_p[x]$ is surjective. Then for all $0\le t\le p-2$, we must have that $f(x)^t\pmod{x^p-x}$ has degree at most $p-2$. Proof: This comes from the easy fact that $f\equiv g$ at all points modulo $p$ if and only if $f\equiv g\pmod{x^p-x}$. This follows by the fact that all $a\in \mathbb{F}_p$ are roots of $x^p-x$. Therefore, modulo $x^p-x$, $f$ is equivalent to its Lagrange Interpolating Polynomial. But Lagrange Interpolation is very easy over $\mathbb{F}_p$ because the following function represents $f$ (because of Fermat's Little Theorem): $$g(x)=\sum_{a\in \mathbb{F}_p}f(a)(1-(x-a)^{p-1}).$$But then the Lagrange Interpolating Polynomial for $f^t$ is $$g_t(x)=\sum_{a\in \mathbb{F}_p}f(a)^t(1-(x-a)^{p-1}).$$Therefore $$[x^{p-1}]g_t(x)=-\sum_{a\in \mathbb{F}_p}f(a)^t.$$If $f$ is surjective, this is equivalent to $$-\sum_{a\in \mathbb{F}_p}a^t.$$This is well-known to be equivalent to $0$ for $0\le t\le p-2$, as desired. $\square$ Assume $p>2$. We can quickly get rid of primes that are $1$ modulo $4$ because raising a quartic to the power of $\frac{p-1}{4}$ yields a polynomial of degree $p-1$, even modulo $x^p-x$. Now, suppose $p\equiv 3\pmod{4}$ and $f\in \mathbb{F}_p[x]$ is surjective. Depress $f$ (one can quickly check that this is allowed modulo $p$), shift $f$ so that the constant term is $0$, then scale so that $f$ is monic. It thus suffices to only consider polynomials of the form $x^4+ax^2+bx$. Set $p=4k+3$. Note that $$(x^4+ax^2+bx)^{k+1}=x^{4k+4}+(k+1)ax^{4k+2}+\cdots.$$Reducing modulo $x^p-x$, we see that we need $(k+1)a\equiv 0\pmod{p}$, i.e. $a=0$. Hence we restrict our view to polynomials $x^4+bx$. Now note that $$(x^4+bx)^{k+2}=x^{4k+8}+(k+2)bx^{4k+5}+\binom{k+2}{2}b^2x^{4k+2}+\cdots.$$Reducing modulo $x^p-x$, we hence require that $\binom{k+2}{2}b^2\equiv 0\pmod{p}$ when $k>1$ (because $x^{4k+8}$ and $x^{4k+5}$ reduce to smaller terms). Hence $b=0$, and clearly $x^4$ is not surjective. We're done because the case $k=1$ leads to $p=7$.
22.06.2024 19:15
By the way, the original version of this problem asked to count the number of surjective cubics modulo $p>3$, which uses similar ideas but is somewhat easier.
02.11.2024 19:10
I am so sad I had to use an overcomplicated sledgehammer but alas. This is obvious for $p=2$, hence assume $p \geq 3$ (we are going to explicitly give the polynomial $Q$ later). Because of shifting, scaling and what not, we can safely assume \[Q(x)=x^4+ax^2+bx\]Now we will work in $\mathbb{F}_p$; there exists $a$, $b$ such that there exist no $x \neq y$ such that \begin{align*} &x^4+ax^2+bx=y^4+ay^2+by\\ \iff &(x+y)(x^2+y^2)+a(x+y)+b=0 \end{align*}If $b=0$, then just take $x=-y$. Now let $x=\frac z2+w$ and $y= \frac z2 - w$. Make sure $z \neq 0$. So we get \[w^2=\frac{-az-b-\frac{z^3}2}{2z}\]And so we get that \[\frac{-z^3-cz-d}z\]is a non quadratic residue for all $z \neq 0$ (here $c=2a$ and $d=2b$). Now finally change $z$ to $\frac 1z$ to get that \[\left(\frac{-1-cz^2-dz^3}p \right)=-1\]for all $z \neq 0$. And now sadly (because I have RMO tomorrow), I need to nuke this by using Hasse-Weil bound as $p \geq 11$, means that there are $p+1-2\sqrt{p}>3$ solutions and see that $-1-cz^2-dz^3=0$ has atmost $3$ solutions by Lagrange and hence done. One can easily check $p=5$ does not work and we can take $Q(x)=x^4$, $x^4+2x^2+x$, $x^4+3x$ for $p=2$, $3$, $7$ respectively. Hence only solutions are $\boxed{p=2,3,7}$.