From: Mok-Kong Shen on 14 Jan 2010 14:26 wizzi fig wrote: > Mok-Kong Shen wrote: >> To generate a permutation that is not decomposable into cycles ... > > If P is a permutation, the sequence P(0), P(1), ... , P(2^w-1) > produces each value 0..2^w-1 exactly once. The function H that maps P > (i) to P(i+1) is thus "a permutation that is not decomposable into > cycles". [snip] A bijective mapping does not necessarily mean a cycle free permutation, example: 1 2 3 4 5 6 2 3 1 5 6 4 M. K. Shen
From: wizzi fig on 14 Jan 2010 15:15 On Jan 14, 2:26 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > wizzi fig wrote: > > Mok-Kong Shen wrote: > >> To generate a permutation that is not decomposable into cycles ... > > > If P is a permutation, the sequence P(0), P(1), ... , P(2^w-1) > > produces each value 0..2^w-1 exactly once. The function H that maps P > > (i) to P(i+1) is thus "a permutation that is not decomposable into > > cycles". [snip] > > A bijective mapping does not necessarily mean a cycle free > permutation, example: > > 1 2 3 4 5 6 > 2 3 1 5 6 4 I think we are on different pages. Given your example, my function H would be i 1 2 3 4 5 6 H(i) 5 3 1 2 6 4 Computing x_(i+1)=H(x_i) recursively (I would say "iteratively") runs through every value before repeating. I *think* that is the trait you are after. Bob H (via a send-only email address)
From: Mok-Kong Shen on 14 Jan 2010 15:36 wizzi fig wrote: > Mok-Kong Shen wrote: >> wizzi fig wrote: >>> Mok-Kong Shen wrote: >>>> To generate a permutation that is not decomposable into cycles ... >> >>> If P is a permutation, the sequence P(0), P(1), ... , P(2^w-1) >>> produces each value 0..2^w-1 exactly once. The function H that maps P >>> (i) to P(i+1) is thus "a permutation that is not decomposable into >>> cycles". [snip] >> >> A bijective mapping does not necessarily mean a cycle free >> permutation, example: >> >> 1 2 3 4 5 6 >> 2 3 1 5 6 4 > > I think we are on different pages. Given your example, my function H > would be > > i 1 2 3 4 5 6 > H(i) 5 3 1 2 6 4 > > Computing x_(i+1)=H(x_i) recursively (I would say "iteratively") runs > through every value before repeating. I *think* that is the trait you > are after. I seems that I indeed have not understood you. What I mean is this: If P(x) is an 'arbitrary' bijective mapping of [0,n-1] to [0,n-1], then computing x_(i+1)=P(x_i) starting from an arbitrary x_0 isn't guaranteed to produce all values of [0,n-1]. In case P(x) is a polynomial (mod 2^w), the criteria I quoted from [4] ensures this for n=2^w. The criteria of [1] only ensures that the mapping is bijective, i.e. P(0), P(1), .... P(n-1) are all distinct and hence constitutes a permutation of [0,n-1]. In fact, the identity mapping P(x)=x trivially satisfies that criteria and the resulting permutation is certainly not cycle free. But what is exactly your point? Sorry that I haven't yet understood you. M. K. Shen
From: wizzi fig on 14 Jan 2010 16:11 On Jan 14, 3:36 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > wizzi fig wrote: > > Mok-Kong Shen wrote: > >> wizzi fig wrote: > >>> Mok-Kong Shen wrote: > >>>> To generate a permutation that is not decomposable into cycles ... > > >>> If P is a permutation, the sequence P(0), P(1), ... , P(2^w-1) > >>> produces each value 0..2^w-1 exactly once. The function H that maps P > >>> (i) to P(i+1) is thus "a permutation that is not decomposable into > >>> cycles". [snip] > > >> A bijective mapping does not necessarily mean a cycle free > >> permutation, example: > > >> 1 2 3 4 5 6 > >> 2 3 1 5 6 4 > > > I think we are on different pages. Given your example, my function H > > would be > > > i 1 2 3 4 5 6 > > H(i) 5 3 1 2 6 4 > > > Computing x_(i+1)=H(x_i) recursively (I would say "iteratively") runs > > through every value before repeating. I *think* that is the trait you > > are after. > > I seems that I indeed have not understood you. What I mean is this: > If P(x) is an 'arbitrary' bijective mapping of [0,n-1] to [0,n-1], > then computing x_(i+1)=P(x_i) starting from an arbitrary x_0 isn't > guaranteed to produce all values of [0,n-1]. In case P(x) is a > polynomial (mod 2^w), the criteria I quoted from [4] ensures this > for n=2^w. The criteria of [1] only ensures that the mapping is > bijective, i.e. P(0), P(1), .... P(n-1) are all distinct and hence > constitutes a permutation of [0,n-1]. In fact, the identity mapping > P(x)=x trivially satisfies that criteria and the resulting permutation > is certainly not cycle free. > > But what is exactly your point? Sorry that I haven't yet understood you. > > M. K. Shen My first point is that if P is any 'arbitrary' permutation, we can use it to create a function H, and that when H is applied repeatedly, as x_ (i+1)=H(x_i), you will find that H has one cycle covering all possible values. My second point is that if P is a polynomial, H is a polynomial. For a concrete example, suppose we are working modulo 8 and P(x) = 2x^3+x+1. P is a permutation but does not have a single cycle. x 0 1 2 3 4 5 6 7 P(x) 1 4 3 2 5 0 7 6 But the function H(x) = P(P'(x)+1) necessarily has a single, full cycle. Why? Because this cycle is the lower row of the table for P (x), read left to right. I.E. H(1) is 4, H(4) is 3, and so on. H is also a polynomial. Why? Because P'(x) = P(P(P(x))) is a polynomial. That we can get the inverse of P by applying P thrice is a result of the fact that the cycles of P are (0,1,4,5), (2,3) and (6,7), the GCD of the periods of those cycles is 4, so applying P four times will be the identity, so applying P three times is the inverse. I'll let you work out what those actual polynomials are (for P' and H). The degrees shouldn't get very large in this case, because exponents can be reduced by the equivalence of x^5 and x^3. > ... the identity mapping > P(x)=x trivially satisfies that criteria and the resulting permutation > is certainly not cycle free. In this case H(x) = x+1, which has a single, full cycle. Bob H
From: Mok-Kong Shen on 14 Jan 2010 16:38
wizzi fig wrote: > My first point is that if P is any 'arbitrary' permutation, we can use > it to create a function H, and that when H is applied repeatedly, as x_ > (i+1)=H(x_i), you will find that H has one cycle covering all possible > values. [snip] I am confused. I have difficulty to understand this. Let P(x) be an arbitrarily given polynomial which happens to not generate cycle free permutation. Are you going to 'examine' all the values P(i), i=0,...n-1 and then apply certain techniques of yours to 'create' a polynomial H(x), or is there a method without having to examine these values? Anyway, if you ever succeed in doing that, then you will find that your H(x) satisfies the criteria I quoted from [4]. So why don't you simply apply that criteria in the first place to choose your polynomials for use in your applications? M. K. Shen |