From: wodzak@cs.missouri.edu (Michael Wodzak) Newsgroups: sci.math Subject: pascal's triangle Date: 17 Apr 1995 14:15:13 GMT A couple of months ago I posted this problem, which was answered (I am told by colleagues) almost instantly, by someone in Harvard. Unfortunately I was having computer problems, and so never got to see the reply, and none of my colleagues kept it for me! So if you are that lucky, blessed keeper of the truth, could you please e-mail the answer to wodzak@mumathnx5.cs.missouri.edu Here, once again is the problem: Consider the space generated by finite linear combinations of the vectors v1, v2, v3,.... Where v1 is the k_th row of pascal's triangle followed by an infinite tail of zeros, v2 is v1 preceded by a single zero, v3 is v2 preceded by a single zero, etc. For k = 1,2,..,9, the smallest finite linear combination with integer coefficients has l_1 norm (sum of absolute value of coordinates) equal to 2k, and in fact this is a lower bound for each k. My question was and is "Is this lower bound always achieved?" ============================================================================== From: gerry@macadam.mpce.mq.edu.au (Gerry Myerson) Newsgroups: sci.math Subject: Re: pascal's triangle Date: 18 Apr 1995 19:27:38 -0500 I'd like to see this, too, so I hope it will be posted to the group. It sounds to me like another of the many rephrasings of the Tarry- Escott problem ("multigrades"); if so, the question you are asking is the big unsolved problem in the area. Gerry Myerson [Original message was attached -- djr] ============================================================================== From: rusin@washington.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: pascals triangle Date: 18 Apr 1995 21:25:30 GMT In article <3n0n7l$o8n@news.missouri.edu>, Michael Wodzak wrote: >I am still having difficulty with this: Here's a partial answer -- maybe you can finish it faster than I can, since this seems to be so urgent. >v1 is the k_th row of pascal's triangle followed by an infinite tail of zeros. >v2 is v1 preceded by a single zero. >v3 is v2 preceded by a single zero. >v4 is v3 preceded by a single zero. >etc. >Take finite linear integer combinations of v1,v2,v3,v4,... . I assume you mean a _nonzero_ linear combination. >For each k, I know that 2k is a lower bound for the l1 norm of these sums >Is this always achieved? Well, you want to find integers a_i so that Sum( a_i v_i) has L1 norm equal to 2k. Very well, let's view this vector space as the set of polynomials in one variable X ; the string (r0, r1, r2, r3, ...) in the vector space stands for the polynomial Sum ( r_i X^i ). Then your v_i is the polynomial X^(i-1) * (1+X)^k and your linear combination is just a polynomial P(X) * (1+X)^k. You're asking if it's possible to choose an integral P making this product have L1 norm equal to 2k. That means you want the product to be Q= Sum ( X^(m_i) ) - Sum ( X^(n_i) ) where there are 2k summands altogether, possibly with some m_i or n_i repeated. (For example, X^3 + 2X -1 has norm 4, and it's (X^3+X^1+X^1) - (X^0). ). Very well, what does it take for Q to be a multiple of (1+X)^k (in the ring Z[X] ) ? This says nothing more nor less than that (-1) is a root of multiplicity k of Q, that is Q(-1)=Q'(-1)=Q''(-1)=...=0. Now, I think it's a little easier to let R(x) = Q(-x); that way you're looking for a polynomial R which is just a sum of 2k signed monomials for which R(1)=R'(1)=...=R^(k-1)(1) = 0. These are easy conditions to work with. If R = Sum( X^m_i ) - Sum( X^n_i ), then R(1) = 0 means there are just as many m's as n's -- in your case, k of each. Then R'(1)=0 means Sum (m_i) = Sum (n_i). Likewise, R''(1)=0 means Sum ( m_i(m_i-1) ) = Sum( n_i(n_i - 1) ), but in the presence of the previous equation, this is equivalent to Sum( m_i^2 ) = Sum( n_i^2 ). In short, your question may be reduced to the following: show that there exist two sets of k positive integers { m_i } and { n_i } such that Sum( m_i^ j ) = Sum( n_i ^j ) for j = 1, 2, ..., k-1. You can also express this using the elementary symmetric polynomials: the first k-1 of them will be equal for the m's and n's. In particular, this means that the m's and n's are roots of polynomials of degree k all of whose coefficients are equal except the last. This, in turn, may be stated as the condition that the products Prod ( m_i - n_j, i=1...k ) are equal for j = 1,2, ..., k. So you have only to do some experimenting with fatorizations of integers to find a number which can be decomposed into k factors in k rather similar ways. For example, when k=3, we note that 12 = 1.2.6 = (-3).(-2).2 = (-4).(-3).1 so we may use { m_i } = { 1, 2, 6 } and { n_i } = { 0, 4, 5 }. You can check that the sums are equal (to 9) as are the sums of their squares (equal to 41), so that R(X)= (X^1 + X^2 + X^6) - (X^0 + X^4 + X^5) does indeed have a triple root at X=1. Working backwards, we find Q(X) = X^6+X^5-X^4+X^2-X-1, and P(X) = Q(X)/(1+X)^3 = X^3-2X^2+2X-1, so that the coefficients you wanted (the a_i) are 1, -2, 2, and -1. There is probably some simple way to write down a highly-factorable number which permits k related decompositions into k factors; I haven't spotted it yet but perhaps another reader will. dave ============================================================================== [After posting the above, I found the next article in the sci.math.research archives -- djr] ============================================================================== From: elkies@ramanujan.harvard.edu (Noam Elkies) Newsgroups: sci.math.research Subject: Multigrades (Re: pascal's triangle) Date: 11 Dec 1994 00:11:23 GMT In article <3cakvk$pat@golf.ustores.missouri.edu> wodzak@cs.missouri.edu (Michael Wodzak) writes: >Take any row of Pascal's triangle and adjoin any number of zeros to >it and consider the object a vector , eg.v1= >{1,5,10,10,5,1,0,0,0,0}. Get a collection of such vectors by >shifting the nonzeros to the right and filling up the left with >sufficient zeros to maintain the dimension of the vectors, ie, v2= >{0,1,5,10,10,5,1,0,0,0}, v3={0,0,1,5,10,10,5,1,0,0} etc. >Now take integer combinations of the vectors you have constructed >w=n1.v1+ n2.v2 +n3.v3+......where n1,n2,n3 are any integers at least >one of which is nonzero. ... that is, take (the coefficients of) a polynomial divisible by (x+1)^k. >Finally, compute ||w||_1 , the l1 norm of w. >I can show that ,for any integer combination, ||w||>= 2k, where k is >the second element in the chosen row of Pascal's triangle. It's more convenient to see this for the clearly equivalent problem of a polynomial divisible by (x-1)^k. To wit, let ||w||_1 = 2n, and write the polynomial as sum(x^(a_i) - x^(b_i), i=1..n). This is divisible by (x-1)^k iff for each m=k. >Indeed, for the rows{1,1}, {1,2,1}, {1,3,3,1}, {1,4,6,4,1}, the >values||w||=2, ||w||=4,||w||=6,||w||=8, respectively, are readily >obtainable [...] However, the smallest value for ||w|| that >I can achieve for the row {1,5,10,10,5,1} is 12. If n=k the a_i and b_i are said to constitute a "perfect multigrade" of order n. It seems that these were once an object of intense study -- I once saw a book from the 1940's(?) titled "Mehrgraedige Gleichungen" -- but are not very well known today. Last I heard it was known that there are infinitely many perfect multigrades of orders <=6, and at least isolated examples of orders 7,8,9,10. So yes, the least ||w|| for the 5th row is 10. >The empirical evidence seems to suggest that minimal values for ||w|| >are achieved with integer combinations which are in some sense >symmetric. Can you show this to be the case? Most of the examples known are symmetric, but asymmetric ones exist for some small n. >I personally am begining to suspect that ||w|| is not linearly but >exponentially related to k -- is this a reasonable conjecture? A pigeonhole/counting argument shows that the minimal ||w|| grows no faster than a constant multiple of k^2; as far as I know this is the best upper bound known. --Noam D. Elkies (elkies@zariski.harvard.edu) Dept. of Mathematics, Harvard University ============================================================================== [I requested clarification from Myerson about his post -- djr] ============================================================================== Date: Thu, 20 Apr 1995 08:52:01 +1000 To: rusin@math.niu.edu From: Gerry Myerson Subject: Re: pascal's triangle The Tarry-Escott problem: given a positive integer n, find two sets of integers a_1, ..., a_r and b_1, ..., b_r, with r as small as possible, such that sum (a_j)^k = sum (b_j)^k for k = 1, 2, ..., n. E.g., for n = 2, we may take r = 3; 1 + 4 + 4 = 2 + 2 + 5, and 1 + 16 + 16 = 4 + 4 + 25. To avoid trivialities, the b_j may not be taken to be a permutation of the a_j. It is not hard to show that r is at least n + 1; it is known that r = n + 1 for n = 1, 2, ..., 9; it is conjectured that r = n + 1 for all n. A book has been written about the problem; Albert Gloden, Mehrgradige Gleichungen, Noordhoff, Groningen 1944. The first edition (which I have never seen) was in French; Egalit\'es Multigrades. There is a little bit about the problem in Hardy and Wright, also in Albert Beiler, Recreations in the Theory of Numbers, Dover, 1964. There was a paper on the n = 9 case by C. J. Smyth in Math. Comp., maybe 4 years back. Have fun! Gerry Myerson (gerry@mpce.mq.edu.au) Centre for Number Theory Research (E7A) Macquarie University, NSW 2109, Australia