From Helena.Verrill@home.ivm.de Mon Sep 7 08:18:04 1998 Return-Path: Received: from aw.ivm.net (root@mail.ivm.net [195.78.161.2]) by bmw.autobahn.org (8.8.7/8.8.7) with ESMTP id IAA30557 for ; Mon, 7 Sep 1998 08:18:03 -0700 Received: from default (port51.bn.ivm.de [195.247.226.51]) by aw.ivm.net (8.8.8/8.8.8) with SMTP id RAA29154 for ; Mon, 7 Sep 1998 17:17:08 +0200 X-To: Message-ID: <35F3F90B.736F@home.ivm.de> Date: Mon, 07 Sep 1998 16:17:31 +0100 From: Helena Verrill Reply-To: Helena.Verrill@home.ivm.de X-Mailer: Mozilla 3.01 (Win95; I) MIME-Version: 1.0 To: was@bmw.autobahn.org Subject: Re: permutation result References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Status: RO X-Status: sorry if you got this before -I was trying to work out how to cut down the size of the image file I wanted to attach, so I stoped the send whehjile it was senidng, but I don;t know if that workds or not. Anyway, I'll send the image I mention below separately. H Hi William! Thanks for the email. I was thinking along similar lines after we spoke - about your PP(n) thing anyway, though I hand't really thought about ZZ(n), anyway, I'd thought more or less about thwtayuo said, but only kind of playing with it, not writing down proper rpoofs, since I went to bed quite soon afer we spoke anyway. Anyway, good stuff. Anyway, how about this for an argument - since we can do PP(d), use induction to do do PP(d+1). I'm going to assume n is odd. Suppose we want to make c_1,c_2,c_3,...c_d,c_{d+1} By induction, we can make a sum: a_1,a_2,....a_d + b_1,b_2,....b_d --------------- c_1,c_2,....c_d We need to find a way to make a c_{d+1} appear on the end What are the ways we can make c_{d+1}? I'm going to use notation c_{d+1} = x for short we might have in the last column any of 0, 1 , 2, 3,..... n-1 x, x-1, x-2, x-3, x-n+1 But then, one of the elements of each pair may ave already been used up in the thing that makes the sum of the previous d things. Your argument that we can do up to (n-1)/2 is a kind of pigeon hole principle kind of thing. But anyway, we can't do that if d>(n-1)/2 - we may have used up one of each pair. OK, so, take two numbers from the bottom row, such that - they've not been used, even though the corresponding numbers above them have. You can find a pair like this, since we'll assume that d < n-1 (which is all that's necessary, since you said if we can do d=n-1, then we're done. Anyway, say you've got u,v in the bottom row, (of possible values for the lower part of the sum which adds to x) so u and v are not used amongst the c_i. Now, we can assume that u + v = x, since if not, just add (x-u-v)/2 to everything in the bottom row (ie, to the c_i s and to all the possible values for stuff adding to x) and then subtract the same amount from the b_i. (since n is odd, even if x-u-v is odd, we can just add n and then division by 2 is OK) OK, so now we have u+v=x, and u and v are both in the b_i, and neither in the c_i. Suppose b_1=u, then lets swap c_1 and b_1; so now b_1=c_1 and c_1=u; since u was not in the c_i, this still leaves (c_i) a subset of a permutation; and now we can let b_{d+1}=u and c{d+1}=v. This would be OK, unless c_1 is already in the b_i; but then you can look where it occurred, and make another swap. This process of swapping can be repeated, until top and bottom are both all OK. I claim this process terminates, and so we're done. End of proof. I guess I need to prove this process terminates - it's kind of obvious, another pigeon hole principle type thing. I'm going to draw a picture of it, since it's too difficult to describe quickly... actuall, it's even more diffiuclt to work out how to use paintbrish to draw somethjing - something that takes a few sevonds to scribble on a bit of paper and conveys an idea better than a page of words, seems to take several hours even to begin to get onto a computer picture - very frustrating, so I thin k I'm going to give up with that, and just try and describe in in words. Maybe I should get a scanner, then I could just scan in diagram to send you. OK, here is the argument. You have a chain of things, like you want to swap b_1 with c_1, but c_1=b_3, so then you have to swap b_3 with c_3, but c_3 is the same as b_10, so you have to swap b_10 with c_10, and so on, It's like there is your number line, 0,1,2,....12 (say n=13) and above each number, if it's a b_i for some i, put a circle, if it's a c_i for some i, put a cross. Then join with lines pairs c_i b_i, so this will a graph on the numbers 1 to 1, every vertex having degree at most 2. Now, we have v and u somewhere, and these are only in the b_i, so there is a dot over each, but no cross. We want to replace the dot over u with a cross; then we can pair up u and v in the last column to get x. OK I tried drawing a icture again, attatched. In the picture, I've swapped dots and crosses by mistake. There is a x over 3 (suppose u=3); we want to swap 3 and 8, so we can swap the x and o they have - but that means swapping the x under the 8 for a 0, which means swapping the o under the 9 for an x, which means swapping the x over the 9, ad the swapping something for whatever the 9 joins to. Anyway, you follow a path. this parh must terminate, and then we'll be at a place where there are no contradcitions, and we're done. This is because there are only finitely many placce, so it can't be infinite; and the end can not come back to be beloe 3, since we chose 3 so that there was no 3 in the o vector; and we can't end up back somewere else on the path, since the vertices have only degree 2. So, by induction we have done d+1. Is this really a proof of the whole thing? It feels rather too simple and unenlightening to me, but I can't see any holes in this argument yet. What do you think? Lots of love, Helena