Date: Wed, 12 Aug 1998 12:00:45 -0400 (EDT) From: Evan Jones To: rusin@math.niu.edu Subject: [none] Hello. I'm a cellist and music theorist pursuing doctoral degrees in both areas at Eastman. I've enjoyed perusing some of your web pages, and I wanted to ask you something that's been on my mind. Given a set of integers, one can imagine tallying up all the differences contained within the set of integers. For example, for the set {2,3,5,8}, the tally of differences is: one difference of 1 (between 2 and 3), one difference of 2 (between 3 and 5), two differences of 3 (between 2 and 5 and between 5 and 8), one difference of 5 (between 3 and 8), and one difference of 6 (between 2 and 8). I have a hunch that no set of positive non-zero integers will have both the same difference-tally and the same product. Is this true, and, if so, can you convince me of its provability? Thanks for any insight you can provide. Sincerely, Evan Jones evanj@theory.esm.rochester.edu ============================================================================== From: Dave Rusin Date: Thu, 3 Sep 1998 00:49:32 -0500 (CDT) To: evanj@theory.esm.rochester.edu Subject: arithmetic conjecture (for music?) >Given a set of integers, one can imagine tallying up all the differences >contained within the set of integers. For example, for the set {2,3,5,8}, >the tally of differences is: > one difference of 1 (between 2 and 3), > one difference of 2 (between 3 and 5), > two differences of 3 (between 2 and 5 and between 5 and 8), > one difference of 5 (between 3 and 8), > and one difference of 6 (between 2 and 8). > >I have a hunch that no set of positive non-zero integers will have both >the same difference-tally and the same product. Is this true, and, if so, >can you convince me of its provability? {1, 324, 361, 510} and {4, 153, 190, 513} have tallies {37, 149, 186, 323, 360, 509} and product 59,651,640. Regards, ============================================================================== Date: Thu, 3 Sep 1998 18:43:38 -0400 (EDT) From: Evan Jones To: Dave Rusin Subject: Re: arithmetic conjecture (for music?) On Thu, 3 Sep 1998, Dave Rusin wrote: > {1, 324, 361, 510} and {4, 153, 190, 513} have tallies > {37, 149, 186, 323, 360, 509} and product 59,651,640. Thanks so much for figuring this out! Can you tell me: is this the smallest product of integer-sets with the same difference tallies? Maybe that's something you already know, due to the nature of the algorithm you used to find this solution. I'm amazed and pleased that you went to the trouble to help me out with my little issue. Evan Jones ============================================================================== From: Dave Rusin Date: Thu, 3 Sep 1998 20:28:56 -0500 (CDT) To: evanj@theory.esm.rochester.edu Subject: Re: arithmetic conjecture (for music?) >> {1, 324, 361, 510} and {4, 153, 190, 513} have tallies >> {37, 149, 186, 323, 360, 509} and product 59,651,640. > >Thanks so much for figuring this out! Can you tell me: is this the >smallest product of integer-sets with the same difference tallies? >Maybe that's something you already know, due to the nature of the >algorithm you used to find this solution. I'm amazed and pleased that you >went to the trouble to help me out with my little issue. I don't know -- I thought about checking, since the final answers weren't _too_ large, but it looked like a couple orders of magnitudes too much CPU time to do a brute-force search, and I didn't feel like pursuing the algebra. The number of difference tallies determines the number of integers involved. We try for simple combinations: {a,b} vs {c,d}: such a pair would have to be of the form {a, a+x}, {c, c+x} for some x>0; but if say a > c > 0 then clearly a(a+x) > c(c+x). No good. {a,b,c} vs {d,e,f}: in this case if the smaller two difference tallies were x and y, the largest would be x+y. If a and d are the minimal numbers in their sets, we then have sets {a, a+x, a+x+y} and either {d, d+x, d+x+y} or {d, d+y, d+x+y}. The only remaining constraint is the one with products. If for concreteness a > d > 0 then clearly a(a+x)(a+x+y) > d(d+x)(d+x+y), ruling out that combination. Thus it must be the second configuration, with a(a+x)(a+x+y) = d(d+y)(d+x+y). This I can do: take [a,d,x,y]=[6655, 7986, 5075, 854]. I didn't keep my notes on the 4-tuples, but here's how I arrived at the 3-tuples tonight; the reasoning with two 4-tuples was similar. The equation above is quadratic in x. If the coefficients are rational, then the equation has a rational root iff the discriminant ("B^2-4AC") is square. That discriminant is 2 2 2 2 2 2 2 -d (-4 a d - d + 4 a ) - 2 d (-3 a d + 2 a - d ) y + (a + d) y You'll notice this may be written as [(a+d)y]^2 + ..., so if you want this to be a square, say u^2, you get an equation like u^2 - [(a+d)y]^2 = ... Well, that's a difference of two squares there on the left, so it factors, making it easy to read off solutions: the solutions to X^2-Y^2 = C are parameterized by a number k: we must have X+Y=k, X-Y=C/k. Add and subtract these equations to get formulas for X adn Y in terms of k. Well, I'm glossing over a few details (e.g. you have to complete the square in y first) but this is pretty straightforward stuff for quadratic equations. I'll just give you the punchline: parameterizations for x and y in terms of a,d, and this parameter k are 5 5 2 4 4 3 2 3 2 2 3 2 (-k a + 2 a d - 4 d k a - 2 a d - d k a - k a d + 2 d k a 2 2 3 2 / 3 - 2 k a d - d k ) / (a (a + d) k) and / 4 2 3 3 2 2 2 2 2 2 2 3 - (2 a d - 2 a d + k a + 2 k a d + d k + d k a + 4 d k a 3 4 / 3 - 2 d k a + d k) / ((a + d) k) / respectively. Now you can plug in any a,d,k you want. Don't worry about making them integral: since the original equation in {a,d,x,y} is homogeneous (of degree 3), we can just multiply through by a common denominator tomake everything integral. In fact, with this idea in mind, you can just set a=1, say -- you can always scale back at the end. There remains the issue of positivity. Your request is that we take d>0, and we want d and k to make these two things positive. (We also must avoid d=1, since a=d will force x=y and we get the trivial solution of setting up the say triple {a, a+x, a+x+y} twice!). With a and d positive, you either need k>0 and both numerators >0, or all three things negative. It's a little tricky to make the numerators positive: as polynomials in k, they're quadratic and have negative lead coefficients; so we need to choose k between the two roots. That in turn assumes they _have_ two roots, which means their discriminants are positive. Well, those discriminants are (d^2+4d-4)*square and (-4d^2+4d+1)*square respectively, so positivity happens for positive d only if d lies between 0.8284... and 1.2071... What's a nice rational number in there, other than the forbidden d=1? I choose d=6/5, which has the smallest denominator. So now those quadratics both have two roots. We wither select k>0 between the roots of each, or k<0 outisde the roots of each. The first turns out to be impossible, but the second happens if k < -1.727... I choose k=-2. Substitute a=1, d=6/5, k=-2 into the formulas for x, y and get 854/6655, 1015/1331 respectively. Scale everything by 6655 and you get positive integers for a,d,x,y as I presented above. Is this a minimal solution among triples? I doubt it. As you can see, there's plenty of latitude in finding solutions. For 4-tuples I seem to recall I just looked for solutions among positive rationals to a(a+x)(a+x+y)(a+x+y+z)=d(d+z)(d+z+y)(d+z+y+x) which is about the only way to get solutions to the problem you pose for sets of 4 numbers. That's now one equation among 5 unknowns, and (so) we end up expressing a=1 and the other four as rational functions of 3 rational parameters. All you have to do is stay within an open set to keep the four positive. That makes it easy to find solutions, but doesn't really help you find _smallest_ ones. dave