9

Given a polynomial with integer roots, is it possible to add an integer to the polynomial so the roots of the new polynomial are also integers.

Apparently it is possible for some polynomials.

For example $$ x^2-6x+5$$ and $$x^2-6x+8$$ satisfy our conditions.

Third order polynomials such as $$x^3-12x^2+41x-30$$ and $$x^3-12x^2+41x-42$$ satisfy the conditions as well.

My question is what is the highest possible degree of polynomials satisfying the said conditions.

YiFan Tey
  • 17,431
  • 4
  • 28
  • 66
Mohammad Riazi-Kermani
  • 68,728
  • Let $\prod_{j=1}^n (x-a_j) = \sum_{l=0}^n \sigma_l(a) x^l$ then you want the rational points on the dimension $n+1$ affine variety $V_n = { (a,b,c) \in \Bbb{C}^n\times \Bbb{C}^n\times \Bbb{C},(\sigma_0(a)-\sigma_0(b))c=1,\forall l \ge 1,\sigma_l(a) = \sigma_l(b)}$ $= { (a,b,c),c\sum_{j=1}^n (a_j^n-b_j^n)=1,\forall 1 \le l \le n-1, \sum_{j=1}^n (a_j^l-b_j^l)=0}$ – reuns Aug 25 '19 at 00:35

3 Answers3

6

The roots of such polynomial pairs are essentially the ideal solutions of the Prouhet–Tarry–Escott problem .

According to above wiki entry, ideals solutions are known for $3 \le n \le 10$ and for $n = 12$. No ideal solution is known for $n = 11$ or for $n \ge 13$.

Following solution for $n = 12$ is extracted from Chen Shuwen's Equal sums of like powers page. Let $$\begin{align} (a)_{i=1}^{12} &= (1,12,25,66,91,130,174,213,238,279,292,303)\\ (b)_{i=1}^{12} &= (4,6,31,58,105,117,187,199,246,273,298,300) \end{align} $$ and consider following two polynomials of degree $12$, $$A(x) = \prod_{i=1}^{12} (x - a_i)\quad\text{ and }\quad B(x) = \prod_{i=1}^{12} (x - b_i)$$ We have $$B(x) - A(x) = 67440294559676054016000$$

achille hui
  • 122,701
  • Can you explain why the Prouhet–Tarry–Escott problem is equivalent to the problem posed in the question? – Vincent Aug 30 '19 at 11:34
  • @Vincent - By Newton's identities, the coefficient of $x^1, \ldots, x^{n-1}$ in $\prod_{k=1}^n(x-c_k)$ is uniquely determined by the power sums $p_m = \sum_{k=1}^n c_k^m$ for $m = 1,\ldots,n-1$. – achille hui Aug 30 '19 at 17:32
2

I don't expect there will be an upper bound.

In the C++ program at the end, note how s4 and t4 are ignored with 4 integers.

The first bit is gp-Pari

parisize = 4000000, primelimit = 500000
? (x-1)*(x-5)*(x-8)*(x-12)
%1 = x^4 - 26*x^3 + 221*x^2 - 676*x + 480
? (x-2)*(x-3)*(x-10)*(x-11)
%2 = x^4 - 26*x^3 + 221*x^2 - 676*x + 660
?

====================================================

jagy@phobeusjunior:~$ ./mse
   1   5   8  12      2   3  10  11
   2   6   9  13      3   4  11  12
   1   7   8  14      2   4  11  13
   3   7  10  14      4   5  12  13
   2   8   9  15      3   5  12  14
   4   8  11  15      5   6  13  14
   3   9  10  16      4   6  13  15
   1   6  11  16      2   4  13  15
   5   9  12  16      6   7  14  15
   1   8  10  17      2   5  13  16
   4  10  11  17      5   7  14  16
   2   7  12  17      3   5  14  16
   6  10  13  17      7   8  15  16
   1   9  10  18      3   4  15  16
   2   9  11  18      3   6  14  17
   5  11  12  18      6   8  15  17
   3   8  13  18      4   6  15  17
   7  11  14  18      8   9  16  17
   2  10  11  19      4   5  16  17
   1   8  12  19      3   4  16  17
   3  10  12  19      4   7  15  18

====================================================

int main()
{
  for(mpz_class d = 4; d <= 25; ++d){
  for(mpz_class c = 3; c < d; ++c){
  for(mpz_class b = 2; b < c; ++b){
  for(mpz_class a = 1; a < b; ++a){

   mpz_class s1,s2,s3,s4;
   s1 = a + b + c + d ;
   s2 = a*a + b*b + c*c + d*d;
   s3 = a*a*a + b*b*b + c*c*c + d*d*d;
   s4 = a*a*a*a + b*b*b*b + c*c*c*c + d*d*d*d;

   for(mpz_class h = 4; h < d; ++h){
   for(mpz_class g = 3; g < h; ++g){
   for(mpz_class f = 2; f < g; ++f){
   for(mpz_class e = 1; e < f; ++e){

      mpz_class t1,t2,t3,t4;
   t1 = e + f + g + h ;
   t2 = e*e + f*f + g*g + h*h;
   t3 = e*e*e + f*f*f + g*g*g + h*h*h;
   t4 = e*e*e*e + f*f*f*f + g*g*g*g + h*h*h*h;


   if( s1 == t1 && s2 == t2 && s3 == t3 )
  {

    cout << setw(4) << a << setw(4) << b << setw(4) << c << setw(4) << d;
    cout << "   ";
    cout << setw(4) << e << setw(4) << f << setw(4) << g << setw(4) << h;
    cout << endl;

  }

  }}}}  //  efgh

  }}}} // abcd

  return 0;
}

=================================================

Will Jagy
  • 139,541
  • The question was about upper bound on degree of the polynomial not the roots. – Mohammad Riazi-Kermani Aug 25 '19 at 00:54
  • @MohammadRiazi-Kermani yes. And, knowing nothing but your quadratic and cubic examples, I decided to find quartic and quintic. The program is so slow that the maximal element is, well, important for practical reasons. – Will Jagy Aug 25 '19 at 00:57
2

here is quintic, all positive integer roots (distinct) with the smallest maximal element, which turns out to be 19.

   2   3  11  15  19      1   5   9  17  18

===========================================================

? ( x-2)*(x-3)*(x-11)*(x-15)*(x-19) 
%3 = x^5 - 50*x^4 + 890*x^3 - 6700*x^2 + 19629*x - 18810
? ( x-1)*(x-5)*(x-9)*(x-17)*(x-18) 
%4 = x^5 - 50*x^4 + 890*x^3 - 6700*x^2 + 19629*x - 13770
?

==========================================================

quintic program slowed way, way, down, I had it print the time at each success 

jagy@phobeusjunior:~$ ./mse
Sat Aug 24 16:46:03 PDT 2019
progress  10
   2   3  11  15  19      1   5   9  17  18
Sat Aug 24 16:50:39 PDT 2019

progress  20
   3   4  12  16  20      2   6  10  18  19
Sat Aug 24 16:54:37 PDT 2019

   2   4  13  15  21      1   7   9  18  20
Sat Aug 24 16:59:55 PDT 2019

   4   5  13  17  21      3   7  11  19  20
Sat Aug 24 17:01:26 PDT 2019

   3   5  14  16  22      2   8  10  19  21
Sat Aug 24 17:10:22 PDT 2019

   5   6  14  18  22      4   8  12  20  21
Sat Aug 24 17:12:45 PDT 2019

   4   6  15  17  23      3   9  11  20  22
Sat Aug 24 17:27:05 PDT 2019

   6   7  15  19  23      5   9  13  21  22
Sat Aug 24 17:30:53 PDT 2019
Will Jagy
  • 139,541
  • 1
    By minimizing the largest absolute value of the roots (just as well shifting these polynomials $10$ to the left), we obtain a pair of polynomials for which the roots of one are precisely the negatives of the roots of the other: $$(y \pm 8)(y \pm 7)(y \mp 1)(y \mp 5)(y \mp 9) .$$ The standard forms of the polynomials are relatively simple and nicely related, too: They are $$y^5 - 110 y^3 + 2629 y \pm 2520 .$$ – Travis Willse Aug 25 '19 at 00:01
  • Mohammad's cubic example has the analogous property, too. – Travis Willse Aug 25 '19 at 00:06
  • @Travis very good. If you find a way to predict, say, a degree six, I'm sure Mohammad would be pleased to know. The quintic program, running now, takes about five minutes between successes. – Will Jagy Aug 25 '19 at 00:08
  • The quadratic examples Mohammad gave, as well as your quartic examples, both enjoyed a different property: After recentering they both have the form $\prod_i (x^2 - a_i^2)$. I don't know whether this property is necessary in the even case, but it's certainly a much smaller search space to consider. – Travis Willse Aug 25 '19 at 00:15
  • @Travis I finally realized that the only "real" examples I'm getting have a minimum element $1.$ Otherwise, given minimum $m,$ we can subtract $(m-1)$ from every element – Will Jagy Aug 25 '19 at 00:20