Testing polynomial equivalence

Question

Suppose I have two polynomials, P(x) and Q(x), of the same degree and with the same leading coefficient. How can I test if the two are equivalent in the sense that there exists some $k$ with $P(x+k)=Q(x)$? P and Q are in $\mathbb{Z}[x].$

Answer 1

The condition of $\mathbb{Z}[x]$ isn't required.

Suppose we have 2 polynomial $P(x)$ and $Q(x)$, whose coefficients of $x^i$ are $P_i$ and $Q_i$ respectively. If they are equivalent in the sense of $P(x+k) = Q(k)$, then

1. Their degree must be the same, which we denote as $n$.
2. Their leading coefficient must be the same, which we denote as $a_n=P_n=Q_n$
3. $P(x+k) - a_n(x+k)^n = Q(x) - a_n x^n$

By considering the coefficient of $x^{n-1}$ in the last equation, this tells us that $P_{n-1} + nk a_n = Q_{n-1}$.

This allows you to calculate $k$ in terms of the various knowns, in which case you can just substitute in and check if we have equivalence.

We can simply check that $Q(i) = P(i+k)$ for $n+1$ distinct values of $i$, which tell us that they agree as degree $n$ polynomials.