Re: Permutation of maximum cycle


vincent64@xxxxxxxxx schrieb:

A permutation p on (1,2,...,n) has a period (or cycle) k defined as the
minimum integer > 1 such that p^k = p. Given n, what is the largest
potential value for k?

For n<7, k=n is the best one can get, with one exception:
For n=5, you may have k=6: (12)(3 4 5)

For n>6, assume you have a permutation of maximal period k=k(n).
Wlog assume that p was chosen among all permutations of maximal order
to have a maximal numer of fix points.
We have k(n)>n because (1 2)(3 ,,, n) has period 2*(n-2)>n for odd n
and (1 2)(3 ... n-1)(n) has period 2*(n-3)>n for even n.
Hence p has at least 2 cycles of order >1.
Consider any two such distinct cycles of periods k1, k2.
Let d=gcd(k1,k2).
If d>1, we can change the permutation by replacing the first cycle with
its d'th power without changing the order of the complete permutation.
The first cycle splits into d cycles of length k1/d and we can drop d-1
of these cycles (i.e. replace them by fix points) contradicting the
choice of p.
Hence d=1.
Consider one cycle of period k1>1.
If k1 is not a prime power, then k1=a*b with a,b>1 and gcd(a,b)=1.
But then a+b<k1 (because wlog a>b>=2 and a*b >= a*2 = a+a > a+b), hence
the k1-cycle can be replaced by an a-cycle and a b-cycle and at least
one additional fixpoint - contradicting the choice of p.
Hence k1 is a prime power.

the quest for maximal order of a permutation is therefore the quest for
a maximal
value of
2^a * 3^b * 5^c * ...
subject to the restriction that
2^a + 3^b + 5^c * ... <= n

Using this, it is quite simple to determine the maximal period for a
given n with a simple computer program (if n is not too big).

We may also make several inferences from the above:
For example if b>=1 and 3*2^a <= 2*3^(b-1), then we way replace a by
a+2 and b by b-1 to obtain a better value. Therefore

2^a > 2/9 * 3^b (which trivially holds if b=0)

OTOH, if a>=1 and 2*3^b <= 2^(a-1), we may replace a by a-1 and b by
b+1. Thus

2^a < 4 * 3^b (which trivially holds if a=0).

Thus 2^a/3^b is approximately 1.
In a similar fashion, all other factors are approximately equal, with
much more tolerance, though.


Please reply directly to vincentg at
datashaping.com. Thank you.

No, read here.

.

Relevant Pages