6
$\begingroup$

Notation notes:

  • The cycle $(i,i+1,\dots,j)\in S_n$ is the permutation $(1)(2)...(i,i+1,\dots,j)\dots(n)$ in cycle notation.

Motivation

Given a factorization of a permutation into certain cycles with non negative exponents, is it possible to find a factorization of the permutation to the same cycle factors (in the same order) but with bounds on the exponents of the factors?

For example (factorizing $(1,2)$):

$(1,2) = (1,2)^1(1,2,3)^0(2,3)^0$

But if the exponent of $(12)$ must be zero we also have

$(1,2) = (1,2)^0(1,2,3)^1(2,3)^1$

The Cycles

Given $\{\sigma_1,\dots,\sigma_{2n-1}\}$ cycles in $S_n$, where $\sigma_1=(1)$, $\sigma_{2n-1}=(n)$ (the identity element) and:

  • $\sigma_m=(i,i+1,\dots,j)$ for every $m$.
  • For every two consecutive cycles $\sigma_m=(i,i+1,\dots,j)$ and $\sigma_{m+1}=(k,k+1,\dots,l)$ either $(k=i$ and $l=j+1)$ or $(k=i+1$ and $l=j)$ allowing a special case $(i,i-1)$ to mean $Id$.

In other words, the cycle brackets keep moving one by one to the right from $(1)$ to $(n)$:
Example in $S_4$:

$\bbox[yellow]{(1)}(2)(3)(4)$ $\quad\sigma_1=(1)$
$\bbox[yellow]{(1)(2)}(3)(4)$ $\quad\sigma_2=(1,2)$
$\bbox[yellow]{(1)(2)(3)}(4)$ $\quad\sigma_3=(1,2,3)$
$(1)\bbox[yellow]{(2)(3)}(4)$ $\quad\sigma_4=(2,3)$
$(1)(2)\bbox[yellow]{(3)}(4)$ $\quad\sigma_5=(3)$
$(1)(2)(3)(4)$ $\quad\sigma_6=()=Id$
$(1)(2)(3)\bbox[yellow]{(4)}$ $\quad\sigma_7=(4)$

Equal Factorizations

Now we are given $\pi\in S_n$ such that $$ \pi = \sigma_1^{\alpha_1}\dots\sigma_{2n-1}^{\alpha_{2n-1}}.$$ where $\{\alpha_1,\dots,\alpha_{2n-1}\}$ are non negative integer exponents.

We are also given $2n-1$ non negative integer bounds on the exponents $\{m_1,\dots,m_{2n-1}\}$. We can assume that each bound $m_i$ is also smaller than the length of the cycle $\sigma_i$.

Are there non negative integer exponents $\{\beta_1,\dots,\beta_{2n-1}\}$ such that $\beta_i\leq m_i$ for every $i$ and $ \pi = \sigma_1^{\beta_1}\dots\sigma_{2n-1}^{\beta_{2n-1}}$?

Comments

It is not important what are the values of $\beta_i$, just whether they exist.

One could go over every possible combination of values of $\beta_i$, which is $\prod m_i$ options, is there a faster way?

Empirical

The following was generated going over all possible exponents:
$\pi=(1,5)(2,4)$ in $S_5$ can be presented as $\pi=(1)^{\alpha_1}(1,2)^{\alpha_2}(1,2,3)^{\alpha_3}(1,2,3,4)^{\alpha_4}(1,2,3,4,5)^{\alpha_5}(2,3,4,5)^{\alpha_6}(3,4,5)^{\alpha_7}(4,5)^{\alpha_8}(5)^{\alpha_9}$ for the following values of $(\alpha_1,\dots,\alpha_9)$:
(0, 0, 0, 0, 4, 3, 2, 1, 0) (0, 0, 0, 1, 4, 2, 2, 1, 0) (0, 0, 0, 2, 4, 1, 2, 1, 0) (0, 0, 0, 3, 4, 0, 2, 1, 0) (0, 0, 1, 0, 4, 3, 1, 1, 0) (0, 0, 1, 1, 4, 2, 1, 1, 0) (0, 0, 1, 2, 4, 1, 1, 1, 0) (0, 0, 1, 3, 4, 0, 1, 1, 0) (0, 0, 2, 0, 4, 3, 0, 1, 0) (0, 0, 2, 1, 4, 2, 0, 1, 0) (0, 0, 2, 2, 4, 1, 0, 1, 0) (0, 0, 2, 3, 4, 0, 0, 1, 0) (0, 1, 0, 0, 4, 3, 2, 0, 0) (0, 1, 0, 1, 4, 2, 2, 0, 0) (0, 1, 0, 2, 4, 1, 2, 0, 0) (0, 1, 0, 3, 4, 0, 2, 0, 0) (0, 1, 1, 0, 4, 3, 1, 0, 0) (0, 1, 1, 1, 4, 2, 1, 0, 0) (0, 1, 1, 2, 4, 1, 1, 0, 0) (0, 1, 1, 3, 4, 0, 1, 0, 0) (0, 1, 2, 0, 4, 3, 0, 0, 0) (0, 1, 2, 1, 4, 2, 0, 0, 0) (0, 1, 2, 2, 4, 1, 0, 0, 0) (0, 1, 2, 3, 4, 0, 0, 0, 0)

In this example it stands out that the largest cycle $(1,2,3,4,5)$ has an exponent $4$ in all solutions and the sum of exponents is a constant $10$ (which happens to be the number of inversions in $\pi$).

$\endgroup$
  • $\begingroup$ In the generality in which you present the problem, I would be surprised if anything can be said. However, the particular example you looked at seems very interesting and could be generalized. I would be curious to know what happens in $S_6$ if you take factorizations of (16)(25)(34) using the analogous sequence of factors (1),(12),..(123456),(23456),...(6). Are there 120 factorizations? Do the other patterns you noticed continue? (I'm assuming you have code so it would be easy to check these things.) $\endgroup$ – Hugh Thomas Dec 16 '14 at 18:58
  • $\begingroup$ Hello @HughThomas, thank you for taking a look. Yes, for this specific example in $S_n$ (up to $n=7$) the number of solutions is $(n-1)!$, the maximal cycle always in maximal exponent (its inverse) and the sum of exponents is the number of inversions in $\pi$. $\endgroup$ – Daugmented Dec 16 '14 at 19:10
  • $\begingroup$ Cool! Would you be satisfied with a solution which focussed on these cases? Or is there a different way you would like to focus it instead? As I said, I think the general problem may be too broad to get good answers. $\endgroup$ – Hugh Thomas Dec 16 '14 at 19:15
  • $\begingroup$ I'd be happy to find the minimal conditions (on the boundaries of the exponents) for the existence of a solution for this case... we can try and generalize as we go (eventually, we need to find out in the general case, given some boundaries on the exponents, if it has a solution in sub exponential time). $\endgroup$ – Daugmented Dec 16 '14 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.