Are these polynomials the same? [closed]

Question

Let $p=2^{127}-1,P,Q\in \mathbb F_p[x]$ with $P(x)=x^2+1$ and $Q(x)=x^2+2$.

Are there some polynomial $H \in \mathbb F_p[x]$ bijectif on $\mathbb F_p$ with $\forall x \in \mathbb F_p, H(P(x))=Q(H(x))$ ?

I have asked here (*) this question but, no answers.

(*) : https://artofproblemsolving.com/community/c6h3323185

Answer 1

No, they aren't.

Each of these self-maps $f\in\{P,Q\}$ has a unique point with a unique preimage $\{0\}$. So any such conjugation $u$ has to fix $0$. For both $f$, we have $f^{\circ 2}(0)\neq 0$, so $f^{\circ 3}(0)$ has exactly two preimages: $f^{\circ 2}(0)$ and its negative. So $u$ has to map $-P^{\circ 2}(0)$ to $-Q^{\circ 2}(0)$. But then one sees that $-P^{\circ 2}(0)$ has two preimages by $P$ while $-Q^{\circ 2}(0)$ has no preimage by $Q$. So there exists no such conjugation.

Precisely: $-P^{\circ 2}(0)=-2$, so $P^{-1}(\{-P^{\circ 2}(0)\})$ is the set of square roots of $-3$, while $-Q^{\circ 2}(0)=-6$, so $Q^{-1}(\{-Q^{\circ 2}(0)\})$ is the set of square roots of $-8$.

Now it's a game using quadratic reciprocity:

• $p$ is 3 mod 4, so $-1$ is not a square mod $p$
• $p$ is $\pm 1$ mod 8, so $2$ is a square mod $p$.
• given this, we see that $-8$ is not a square mod $p$
• since both $3$ and $p$ are $-1$ mod 4, $3$ is a square mod $p$ iff $p$ is not a square mod $3$, i.e., if $p$ is $-1$ mod $3$, which is not the case. So $3$ is not a square mod $p$
• hence $-3$ is a square mod $p$.

Note that we reach the same conclusion for every $p$ which is $7$ mod $24$.

Answer 2

A variant solution: Suppose there is such an $H$. As $H$ is bijective on $\mathbb F_p$, we get that $P^{\circ m}(x)-x$ and $Q^{\circ m}(x)-x$ have the same number of roots for all $m$ (counted without multiplicities). In particular \begin{equation} x^2+x+2 = \frac{P^{\circ 2}(x)-x}{P(x)-x} \end{equation} and \begin{equation} x^2+x+3 = \frac{Q^{\circ 2}(x)-x}{Q(x)-x} \end{equation} have the same number of roots. (Note that $P(x)-x$ and $Q(x)-x$ are separable.) The discriminant of these polynomials is $-7$ and $-11$, respectively. But quadratic reciprocity yields the contradiction \begin{equation} \left(\frac{-7}{p}\right)=1\ne-1=\left(\frac{-11}{p}\right). \end{equation}