disconnected scramblable siteswaps From: valeosote@xxxxxxxxxxxxxxxxxx (Miika) Date: 15 Aug 2005 09:26:34 GMT Hi, everyone. I was looking for transitions between 8440, 8404 and 8044 and found that they all needed transition throws between them. This remined me of 714 and 741, which also are permutations of each other and need transition throws. So I wondered if this was always the case. I soon found a counterexample: 5124 and 5241 are are permutations of each other and yet they share two states. Then I remembered that there even are siteswaps that are permutations of each other and go through the all same states, but in different order. An example of these is 5271420 and 4712520. Well then, under what conditions would the permutations of a siteswap not be connected? We call a siteswap scramblable if all of its permutations are also siteswaps. This implies that the difference of any two throws is a multiple of the length of the siteswap. In particular, if the lowest throw is a 0, then all the throws are multiples of the length. Some examples are 630, 714, 825, 9915 and 88080080. What follows is a proof that for scramblable siteswaps, any permutations (which result in essentially different siteswaps) are not connected. Let's assume we are given a juggling state and told that it is part of a scramblable siteswap of length l and the lowest throw is a 0. Can we figure out what the next throw would have to be? Let's call the height of this first throw t. First we number the positions in the state (starting from zero) and then we find the first position without an "x" and whose number is a multiple of l. Let's call this number u. This u is of course one possible value for t (and certainly the only valid value if u=0). If u > 0, according to the way we chose u, the position u-l contains an "x". This means that after l throws, when the siteswap returns to this state, one of the balls have necessarily been thrown so that the (u-l)'th position is again occupied by an "x". Let's call this throw n and its value h, meaning that h is the n'th number in the siteswap. In order for throw n to land in the right place, we must have h = (u-l)+(l-n)+1 = u-n+1. Since the siteswap is scramblable with a lowest throw of 0, h must also be a multiple of l. Since 0 < n < l+1, the only way this can happen is when n=1. Remembering how we called the first throw t, we can now see that t = h = u-n+1 = u. So u is in fact the only possible value for t! In this way we have determined the first throw in the siteswap and this also determines the next state that the siteswap visits. By repeating this process, we can eventually figure out the whole siteswap. Also, it means that a state can only be part of one scramblable siteswap of a given length and lowest throw of 0. Let's look at an example before moving on. We are given the state xxx-xxx--x-x----x and told that it is visited by a scramblable siteswap of length 5 and the lowest throw is a 0. We must determine the siteswap. To determine the first throw, we number the characters starting from zero and find the first multiple of 5 which is a "-". This is found in position 10, so u=10 and therefore position u-l = 10-5 = 5 should contain an "x" (which we can see to be true from looking at the state). After five throws the siteswap returns to state xxx-xxx--x-x----x, and before that, one of the throws has to land so that position u-l again contains an "x". If this was the fifth (and last) throw, then its height would be ( u-l+1 )= 6. If it was the fourth, then it would be ( u-l+2 ) = 7, and so on until the first throw, when its height would be ( u-l+5 ) = u = 10. From these five choices, the only one that is a multiple of 5 is the first throw. Therefore, the first throw must be a 10 (which we write as an "a") and the next state is xx-xxx--xxx----x. We repeat the process to determine the next throw. This time positions 0, 5, 10 and 15 contain an "x", so we are forced to throw a 20 and thus we have quickly figured out the second throw. Eventually we end up with ak50a. a xxx-xxx--x-x----x k xx-xxx--xxx----x 5 x-xxx--xxx----x----x 0 -xxxx-xxx----x----x a xxxx-xxx----x----x Now let's assume that there are two permutations of a scramblable siteswap (where the lowest throw need not be 0) that share a state (but not all). By subtracting the lowest throw from each of the throws, we find two new scramblable siteswaps and this time their lowest throw is a 0. By doing this, each of the states the siteswaps visit also are changed into some other state. Now, for any state that the two original siteswaps shared, there is some state that the new siteswaps also share. This contradicts what was proven earlier, and therefore our assumption was impossible. (Actually, this could have been shown earlier if we hadn't assumed that the lowest throw was a 0, but the calculations would have been slightly more complex. As it already is, there already are quite a few variables in the proof and I thought that this way just made things clearer.) The above examination means, that a state can only be part of one scramblable siteswap of a given length and lowest throw. This means that the circuits in a state graph of two permutations of a scramblable siteswap are either the same or not connected at all. That is, two(non-cyclic) permutations of a scrablable siteswap can't share a state. It also means that the states of a scramblable siteswap are always of a certain form. That is, given a state, it is not very hard to check if it belongs to any scrablable siteswap, and conversly, given a scramblable siteswap, it's relatively easy to find which state its in. It also implies that any scramblable siteswap is prime or multiple copies of the same prime. What I find remarkable, is finding this sort of a relationship between two properties of siteswaps that at first don't seem connected. Two siteswaps being scramblable and permutations of each other seem to be a property of the throw heights, and yet it implies not sharing any states, which is a property of the circuits of the siteswaps in a state graph. A few ending questions: Has someone thought of this before? If so, how'd you prove it? What portion of jugglers are interested in things like this? There. That's all I had on my mind for now. Thanks for listening. -Miika -- (btw, tämä oli kahdeksas viestini) ----== posted via www.jugglingdb.com ==----