16
$\begingroup$

Let a polynomial with integer coefficients be nice if

  1. this polynomial has distinct integer roots;
  2. its derivative has also integer roots.

For instance $$p(x)=x(x-9)(x-24),\\ p'(x)=3(x-4)(x-18)$$ is the smallest known nice cubic polynomial. Smallest here means a polynomial with the smallest diameter. The diameter of the polynomial $p$ is the diameter of the set of the roots of $p$ in the complex plane. But how to verify with the help of MA that there are no smaller ones?

$\endgroup$
6
  • 2
    $\begingroup$ Did you mean distinct integer roots? Also, nonnegative roots? $\endgroup$
    – Carl Woll
    Sep 3, 2021 at 19:19
  • $\begingroup$ An example with negative roots: (x + 1) (x - 8) (x - 23) that is smaller than 216. $\endgroup$
    – Carl Woll
    Sep 3, 2021 at 19:29
  • $\begingroup$ @CarlWoll Yes, distinct is important, I edited the question. Also the "smallest" needs to be slightly redefined. $\endgroup$
    – yarchik
    Sep 3, 2021 at 19:53
  • $\begingroup$ The redefinition in terms of the diameter of the set of roots makes the question much harder. If the roots are bounded by a certain magnitude away from zero, a brute-force approach could be employed. But I'm not sure how to get Mathematica to rule out the possibility that a polynomial with roots $N + a$, $N + b$, and $N +c$ is "nice" for relatively small $a$, $b$, $c$ and arbitrarily large $N$. $\endgroup$ Sep 3, 2021 at 19:57
  • 1
    $\begingroup$ Wait, no, I withdraw my objection. If the polynomial I mentioned is "nice", then so is a polynomial with roots $a$, $b$, and $c$; just make the substitution $x \to x + N$. $\endgroup$ Sep 3, 2021 at 20:10

2 Answers 2

16
$\begingroup$

We can perform a brute-force search on all such polynomials with roots up to a certain magnitude. First note that if $p(x)$ is a "nice" polynomial with roots $x_1 < x_2 < x_3$, then so is $q(x)$, the polynomial with roots $0$, $x_2 - x_1$, and $x_3-x_1$. This means that we only need to look for polynomials with one root at 0 and the other two roots positive integers. Moreover, we can restrict our case-checking to cases with $x_3 \geq 2 x_2$, since if we have a "nice" polynomial with roots $0, x_2, x_3$, then the polynomial with roots $0, x_3-x_2, x_3$ is also "nice". (Make the substitution $x \to x_3 - x$ to see this.) Finally, we can multiply any "nice" polynomial by an overall factor to get another "nice" polynomial; so we only need to check monic polynomials.

Define a monic polynomial with roots $0, x_2, x_3$, and a function to find the roots of its derivative:

p[x_, x2_, x3_] = x (x - x2) (x - x3)
derroots[x2_, x3_] = x /. Solve[D[p[x, x2, x3], x] == 0, x]

Generate all polynomials with $x_3 \leq x_\text{max}$, and select all of them for which their derivative vanishes at integer points:

xmax = 100;
results = Select[Flatten[
   Table[{{x2, x3}, derroots[x2, x3]}, 
         {x2, 1, xmax}, {x3, 2 x2, xmax}], 1], 
       And @@ Map[IntegerQ, Last[#], {1}] &]

(* {{{9, 24}, {4, 18}}, {{15, 63}, {7, 45}}, {{18, 48}, {8, 36}}, {{21, 45}, {9, 35}}, 
   {{27, 72}, {12, 54}}, {{36, 96}, {16, 72}}, {{42, 90}, {18, 70}}} *)

Interpreting this output, here are all the "nice" cubic polynomials with a root diameter less than or equal to 100, up to translations and inversions: \begin{align*} p(x) &= x(x-9)(x-24) & p'(x) &= 3 (x-4)(x-18) \\ p(x) &= x(x-21)(x-45) & p'(x) &= 3 (x-9)(x-35) \\ p(x) &= x(x-18)(x-48) & p'(x) &= 3 (x-8)(x-36)\\ p(x) &= x(x-15)(x-63) & p'(x) &= 3 (x-7)(x-45) \\ p(x) &= x(x-27)(x-72) & p'(x) &= 3 (x-12)(x-54) \\ p(x) &= x(x-42)(x-90) & p'(x) &= 3 (x-18)(x-70) \\ p(x) &= x(x-36)(x-96) & p'(x) &= 3 (x-16)(x-72) \\ \end{align*}

The case found by the OP is indeed the one with the smallest root diameter.

We can also define "quasi-nice" polynomials as those whose roots are integers and whose extrema are rational numbers. To find these, we replace IntegerQ in the above code by Element[#, Rationals] &; this yields four "quasi-nice" cubic polynomials with a root diameter smaller than 24: \begin{align*} p(x) &= x(x-3)(x-8) & p'(x) &= (3x-4)(x-6) \\ p(x) &= x(x-7)(x-15) & p'(x) &= (x-3)(3x-35) \\ p(x) &= x(x-6)(x-16) & p'(x) &= (3x-8)(x-12) \\ p(x) &= x(x-5)(x-21) & p'(x) &= (3x-7)(x-15) \end{align*} The code also returns an addition 24 "quasi-nice" polynomials with root diameter between 24 and 100.

$\endgroup$
16
$\begingroup$

Using @Michael's formulation of the problem, we can use Reduce to show that the given nice polynomial is smallest. Consider:

p[x_] := x(x-b)(x-c);

We want to find positive integers b and c such that p'[x] = 3(x-d)(x-e) with d and e integers. So:

eqns = Resolve[ForAll[x, p'[x] == 3(x-d)(x-e)]]

2 b + 2 c - 3 d - 3 e == 0 && b c - 3 d e == 0

Now, using this we can check using Reduce:

Reduce[eqns && 0 < b < c < 24, {b, c, d, e}, Integers]

False

So, 24 is indeed the smallest diameter. We can find the OP polynomial with:

Reduce[eqns && 0 < b < c <= 24, {b, c, d, e}, Integers]

(b == 9 && c == 24 && d == 4 && e == 18) || (b == 9 && c == 24 && d == 18 && e == 4) || (b == 15 && c == 24 && d == 6 && e == 20) || (b == 15 && c == 24 && d == 20 && e == 6)

$\endgroup$
1
  • $\begingroup$ Your answer is equally useful. Unfortunately, cannot accept both. $\endgroup$
    – yarchik
    Sep 4, 2021 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.