Partitioned Permutations

Partitioned Permutations are used in the context of Free Probability Theory to model higher order freeness and higher order free cumulants, see e.g. [CMS07].

We provide basic functions for working with partitioned permutations. The focus is on factorizing partitioned permutations.

Basics

Formally, a partitioned permutation $(V, \pi)$ consists of a permutation $\pi$ and a partition $V$ of the set $\{1, ..., n\}$ such that the partition dominates the permutation in the sense that every cycle of $\pi$ is contained in one block of $V$. We call $n$ the length of $(V, \pi)$. Mathematically, another length function is more important. It is given by $|(V, \pi)| := n - ( 2 \cdot \text{number of blocks of } V - \text{number of cycles of } \pi),$ and we call this the adjusted length of $(V, \pi)$. Note that this terminology is not used in the literature.

PartitionedPermutation — Type

PartitionedPermutation

The type of partitioned permutations. Fieldnames are

p::PermGroupElem - a permutation
V::SetPartition - a partition

If the permutation has length n, then the partition must have n upper points and 0 lower points. Further, if W is the partition given by the cycles of p, then W must be dominated by V in the sense that every block of W is contained in one block of V. There is one inner constructer of PartitionedPermutation:

PartitionedPermutation(p::PermGroupElem, V::Vector{Int}) constructs the partitioned permutation where the partition is given by the vector V.

If the optional flag check is set to false, then the constructor skips the validation of the requirements mentioned above.

Examples

julia> PartitionedPermutation(perm(symmetric_group(3), [2, 1, 3]), [1, 1, 2])
PartitionedPermutation((1,2), SetPartition([1, 1, 2], Int64[]))

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source

length — Method

length(pp::PartitionedPermutation)

Return the length of a partitioned permutation, i.e. the size of the underlying set.

Examples

julia> length(partitioned_permutation(perm(symmetric_group(2), [2, 1]), [1, 1]))
2

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source

adjusted_length — Method

adjusted_length(pp::PartitionedPermutation)

Return the adjusted length of a partitioned permutation as described in [CMS07] as |(V, pi)| for a partition V and a permutation pi.

Examples

julia> adjusted_length(partitioned_permutation(perm(symmetric_group(2), [2, 1]), [1, 1]))
1

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source

Products of Partitioned Permutations

For two partitioned permutations $(V, \pi)$ and $(W, \sigma)$ one defines their product as $(V, \pi) \cdot (W, \sigma) = (V \vee W, \pi \sigma)$ if $|(V, \pi)| + |(W, \sigma)| = |(V \vee W, \pi \sigma)|$. Otherwise, one sets $(V, \pi) \cdot (W, \sigma) = (O, \mathrm{id})$. Here, $O$ is the partition where every block consists of exactly one element, and $V \vee W$ denotes the join of the partitions $V$ and $W$.

A major problem is the factorization of a partitioned permutation $(V, \pi)$. This involves finding all pairs $(W_1, \sigma_1), (W_2, \sigma_2)$ of partitioned permutations with $(V, \pi) = (W_1, \sigma_1) \cdot (W_2, \sigma_2)$.

* — Method

*(pp_1::PartitionedPermutation, pp_2::PartitionedPermutation)

Return the product of two partitioned permutations as described in [CMS07].

Examples

julia> x = partitioned_permutation(perm(symmetric_group(3), [1, 2, 3]), [1, 2, 3])
PartitionedPermutation((), SetPartition([1, 2, 3], Int64[]))

julia> y = partitioned_permutation(perm(symmetric_group(3), [2, 1, 3]), [1, 1, 3])
PartitionedPermutation((1,2), SetPartition([1, 1, 2], Int64[]))

julia> x*y
PartitionedPermutation((1,2), SetPartition([1, 1, 2], Int64[]))

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source

enumerate_partitioned_permutations — Method

enumerate_partitioned_permutations(n::Int)

Return and calculate all PartitionedPermutation objects of length n

Examples

julia> length(enumerate_partitioned_permutations(6))
4051

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source

factor — Method

factor(pp::PartitionedPermutation)

Return the factorization of pp in form of a set of 2-tuples.

Examples

julia> length(factor(partitioned_permutation(perm(symmetric_group(3), [2, 1, 3]), [1, 1, 2])))
2

Experimental

This function is part of the experimental code in Oscar. Please read here for more details.

source