Ponder This Challenge - October 2004 - GCD of values of primitive polynomial

Ponder This Challenge:

Puzzle for October 2004.

This month's puzzle is from IQSTAR.
Solutions to one or several parts are okay, but should be accompanied by a proof that your list contains all the possible values and only those, and should be original.

Part 1:
A polynomial is called "primitive" if all the coefficients are integers with their greatest common divisor (GCD) equal to 1. Let P(x) be a primitive polynomial of degree m in x. V(P) is the set of all P(n) where n takes all the integral values. G(P) is the GCD of the elements of V(P). For fixed m, what values can G(P) have?

Part 2:
Let P(x,y,z) be a primitive polynomial of total degree m in (x,y,z). (It involves monomials (x^i*y^j*z^k) where i,j,k are nonnegative integers with i+j+k bounded by m.) V(P) is the set of all P(n1,n2,n3) where n1,n2,n3 take on all the integral values. G(P) is the GCD of the elements of V(P). For fixed m, what values can G(P) have?

Part 3:

What if P(x,y,z) is of degree m separately in each variable? (For each nonzero coefficient, i,j,k are each bounded by m.)

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  ANSWER:

  For both parts 1 and 2, G(P) can be any positive integer which is a divisor of m!.

  We will give the proof for part 2; for part 1 it is similar. Let I=(i,j,k) denote a multi-index. We define I!=i!*j!*k!, and notice that I! is a divisor of m! if |I|=i+j+k is bounded by m, since the multinomial coefficient m!/(i!*j!*k!*(m-|I|)!) is an integer. Let X=(x,y,z) be a setting of the variables. Denote X^I = (x^i*y^j*z^k). P(X) = \sum_I p_I X^I, where p_I are the coefficients.

  V(P), the set of values P(X) where X ranges over integer triples, generates an ideal K, namely all multiples of some integer g. We want to show that g is a divisor of m!.

  For each r=1,2,3, define the operator D_r on polynomials, where D_r(P) gives a new integer polynomial of total degree one less than that of P (or smaller), namely (D_1(P)) (x,y,z) = P(x+1,y,z)-P(x,y,z); (D_2(P)) (x,y,z) = P(x,y+1,z)-P(x,y,z); and (D_3(P)) (x,y,z) = P(x,y,z+1)-P(x,y,z). Clearly (D_r (P))(X) is a linear combination of values of P(*). Pick a maximal index I=(i,j,k) corresponding to a nonzero coefficient p_I. Start with P(X) and apply the operator D_1 i times, then D_2 j times, and D_3 k times. The resulting polynomial is the constant (p_I)(I!), so that this integer is achievable as a sum of values of P(*).

  Now: the polynomial

  B(X) = p_I * [x*(x-1)*...*(x-i+1)] * [y*(y-1)*...*(y-j+1)] * * [z*(z-1)*...*(z-k+1)]

  always takes on values which are multiples of (p_I)(I!), when evaluated at integer triples (n1,n2,n3). So if we subtract B(X) from P(X), we will not increase the range of achievable values.

  So here's the procedure.
  Start with Q(x)=P(x), and a set S of integers initially empty.
  We will maintain three criteria:
  (1) gcd( S union { coefficients of Q } ) = 1.
  (2) For each s in S, the integer s*m! is in K.
  (3) For each integer triple (n1,n2,n3), Q(n1,n2,n3) is in K.
  At the end of the procedure, Q will be 0, so that from (1) and (2) we will have the desired outcome.

  Let I be the maximal index of a nonzero coefficient q_I in Q. Append q_I to S, and replace the polynomial Q(X) by Q(X)-B(X) where B(X) is as defined above.
  Condition (1) is maintained because we kept q_I in S and subtracted multiples of q_I from coefficients of Q.
  Condition (2) is maintained by comments above (I! is a divisor of m!).
  Condition (3) is maintained because the old Q(n1,n2,n3) was in K and

  B(n1,n2,n3)= q_I * [n1*(n1-1)*...*(n1-i+1)] * [n2*(n2-1)*...*(n2-j+1)] * * [n3*(n3-1)*...*(n3-k+1)]

  is also in K, so the new Q(n1,n2,n3) is in K. We have eliminated from Q the term (q_I*X^I), and replaced it with terms of smaller degree, so that eventually Q will go to 0.

  When we reach Q=0, since our three criteria have been maintained, we see that:
  (1') gcd (s in S) = 1;
  (2) For each s in S, s*m! is in K.
  So 1*m! is in K, and g is a divisor of m!.

  The proof generalizes to any number of variables instead of 3.

  Now we show that every divisor of m! is achievable, even in the single variable case (and therefore in the multi-variable case as well). Suppose g is a divisor of m!. Set P(x)=x*(x-1)*(x-2)*...*(x-m+1)+g. For any integer n, P(n) is g plus a multiple of m!. Further, P(0)=g and P(m)=m!+g. So G(P) is a divisor of gcd(g,m!+g)=g (since g is a divisor of m!), and clearly g divides each value of P(n), so g is a divisor of G(P), whence G(P)=g.

  Part 3: Very similar reasoning shows that the allowable values of g are just the divisors of (m!)^3.

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Dan Dima (10.01.2004 @11:29:07 AM EDT)
• Mark J. Tilford (10.02.2004 @12:17:01 PM EDT)
• Luke Pebody (10.02.2004 @02:12:42 PM EDT)
• Jose H. Nieto (10.02.2004 @09:28:22 PM EDT)
• Patrick J. LoPresti (10.02.2004 @08:46:41 AM EDT)
• Daniel Bitin (10.04.2004 @06:16:06 PM EDT)
• Dharmadeep Muppalla (10.06.2004 @08:07:43 AM EDT)
• Libin Shen (10.06.2004 @02:54:46 PM EDT)
• Michael Brand (10.06.2004 @10:08:27 PM EDT)
• Vincent Vermaut (10.07.2004 @02:35:54 AM EDT)
• Raicho Tchalkov (10.07.2004 @05:17:21 PM EDT)
• Amit Sinha (10.08.2004 @10:40:41 AM EDT)
• Wolfgang Kais (10.11.2004 @10:07:45 AM EDT)
• Hagen von Eitzen (10.12.2004 @12:30:21 PM EDT)
• Stephen Lesko (10.25.2004 @03:14:01 PM EDT)
• Vineet Kumar D (10.26.2004 @05:09:22 AM EDT)
• Satish Vedantam (10.29.2004 @09:44:10 PM EDT)
• Divyesh Dixit (10.30.2004 @04:29:16 PM EDT)