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
We are given the cycles $\{\sigma_1,\dots,\sigma_{2n-1}\}$ in $S_n$, where
- $\sigma_1=(1)$, $\sigma_{2n-1}=(n)$ (the identity element).
- for every $m$, $\sigma_m=(i,i+1,\dots,j)$ such that
- 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$).