From: Mok-Kong Shen on
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
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
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
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
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