Re: Challenae question for mathematician


C6L1V@xxxxxxx wrote:
Arturo Magidin wrote:

[.snip.]

If we let S = { (1,2), (2,3), (3,4), ..., (n-1,n) }.

We can express (a)(b)^{-1} = (3,4) as a product of elements of S by

(3,4) = (3,4).

You can express (c)(b)^{-1} = (3,5) as a product of elements of S by

(3,5) = (3,5)(4,5)(3,4) [composing right to left]

For an element x of S_n, define its S-length to be the least number of
factors needed to express x as a product of elements of S.

Just as a matter of interest, how does one determine the S-length,
since there are many distinct product representations of the same S?

I confess that I am not particularly well-versed in algorithmic
problems relating to permutation groups. I know that's a weak point in
my proposal, if no good algorithmic way exists to do so.

Certainly you can do it in exponential time, since there is an easy way
to express any cycle as products of elements of S, which gives you an
easy upper bound for length_S(x) for any x (add the lengths of the
cycles).


Define the
"distance" from x to y, d(x,y) to be the length of xy^{-1}.

Is this the same as the minimum number of factors needed to get from x
to y?

It would be: say you can get from x to y by applying s_1, s_2, s_3,....
s_k. That means that

s_1*s_2*...*s_k x = y

from which you get

xy^{-1} = s_k^{-1} * ... * s_1^{-1} = s_k * ... * s_1

so the number of transpositions needed to convert x into y is greater
than or equal to d(x,y). And if d(x,y) = k, then xy^{-1} = s_1 * ... *
s_k for some s_i in S, from which you get
s_k*...*s_1*x = y, hence you need at most d(x,y) transpositions to get
from x to y.

Arturo Magidin, sans .sig

.