# How to find two monic polynomials with the same number of roots mod p for each prime p

Given an arbitrary monic polynomial $f_1$, is there an elegant way of identifying another $f_2$ such that both have the same number of roots (counting repeated roots as distinct) of $f_i \equiv 0 \bmod p$ for each prime $p$, excluding the trivial transformations $f_2(x)=f_1(ax+b)$? A sufficient condition is that their real roots can be related by rationals, but identifying a suitable $f_2$ from a given $f_1$ seems to require trial and error and much messy algebra. For example, $f_1=x^3+756x+1302$ and $f_2=x^3-126x+714$ have discriminants $-193^2 \times 2^2 3^5 7^2$ and $-11^2 \times 2^2 3^5 7^2$ respectively, and their real roots $\alpha,\beta$ are related by $\beta=\dfrac{-5\alpha^2+29\alpha-2520}{193}$, $\alpha=\dfrac{5\beta^2+37\beta-420}{11}$. The polynomial $f_3=x^3+42x-182$ has discriminant $-5^2 \times 2^2 3^5 7^2$ but its real root doesn't appear to have any similar relation to $\alpha$ or $\beta$. As an example of correspondence of number of roots, $f_1 \equiv 0 \bmod 19$ has three roots: 9,14,15, $f_2 \equiv 0 \bmod 19$ also has three roots: 1,5,13, but $f_3 \equiv 0 \bmod 19$ has no solutions.

If $f_1(r) \equiv 0 \bmod p$, then $(-5 \times r^2+29 \times r-2520)193^{-1} \bmod p$ is a root of $f_2 \equiv 0 \bmod p$, so it's clear why $f_1$ and $f_2$ have the same number of roots.

• Take $f(x+1)\;$? – lulu Mar 21 '18 at 15:30
• What do you mean $f_i \equiv 0 \bmod p$? This is never going to be always true, and it's trivially true for roots – vrugtehagel Mar 21 '18 at 15:34
• I have changed the post to clarify your query – af59 Mar 21 '18 at 17:52

Note that the better question here is why $f_1$ and $f_2$ have the same number of roots over $\mathbb{F}_p$ for every prime $p$, although $f_1$ and $f_2$ are not related by a transformation $x\mapsto x+a$. Indeed, $$f_1(x+a)=x^3 + 3x^2a + 3x(a^2 + 252) + a^3 + 756a + 1302,$$ so that $f_2=f_1(x+a)$ would imply $a=0$, a contradiction.
• You only show that $f_1$ and $f_2$ have the same number of roots for $p=19$ in your edit. – Dietrich Burde Mar 21 '18 at 20:50
• I have generalised this for any $p$ – af59 Mar 21 '18 at 21:44
I found a solution in Weiss: Algebraic Number Theory, proposition 3-7-12. Using the given example, find the rational polynomial $1/f_1'(x)$. This can be done by finding by evaluating $(ax^2+bx+c)f_1'(x)$, and requiring that the coefficients of $x^2,x^1,x^0$ are 0,0,1 respectively. This gives $1/f_1'(x)=(12x^2-31x+6048)/4693374=F$ say. Weiss shows that for $f_1=x^3+px^2+qx+r$, a suitable $f_2$ can be constructed from adding arbitrary multiples of $F,F(x+p),F(x^2+px+q)$, calculating the products algebraically. The $f_2$ in the example is $-332F-4xF$.