October 2004
<<September October November>>
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