Is there a standard term for this notion of "quotient of compositions"? ("Quotient of contiguous set partitions"?)

Question

Fix a finite base set $\Omega$, and let $P_1$ and $P_2$ denote two contiguous partitions of $\Omega$ such that the contiguous partition $P_1$ is finer than the contiguous partition $P_2$.

Consider the number of blocks in the finer contiguous partition $P_1$, say the number is $N$. Then the coarsening of the finer contiguous partition $P_1$ leading to the coarser contiguous partition $P_2$ defines a contiguous partition, call it $Q$, of the set $\{1, \dots, N\}$, corresponding to those blocks of $P_1$ which are merged to achieve the coarsened contiguous partition $P_2$.

Then I define $Q$ to be (for lack of a better term) the "quotient contiguous partition" of $P_1$ via $P_2$, $Q:= \frac{P_1}{P_2}$.

Question: Is there a standard term (and ideally also standard notation) for this concept?

Bonus question: Also, given an arbitrary contiguous partition $P_1$ of the set $\Omega$ into $N$ blocks, as well as a contiguous partition $Q$ of the set $\{1, \dots, N\}$, is there a name for the "opposite" operation which returns a coarser contiguous partition $P_2:= P_1 \blacktriangleright Q$ of $\Omega$ by merging the blocks of $P_1$ according to the contiguous partition $Q$?

Examples: Consider $\Omega = \{1,2,3,4,5\}$, and let $P_1 = \{\{1,2\},\{3\},\{4\},\{5\}\}$ (so $N = 4$), and $P_2 = \{ \{1,2,3\}, \{4,5\}\}$. Then in this case $Q = \frac{P_1}{P_2} = \{\{1,2\}, \{3,4\}\}$.

Consider $\Omega = \{1,2,3,4\}$, $P_1 = \{\{1,2\}, \{3\},\{4\}\}$, so $N=3$, define $Q = \{\{1,2\}, \{3\}\}$, then $P_2 = P_1 \blacktriangleright Q = \{\{1,2,3\}, \{4\}\}$.

Note: there is a one-to-one correspondence between contiguous set partitions and compositions. In the lattice diagram in the Wikipedia article, the finer contiguous partitions correspond to the lower parts of the lattice, while the coarser contiguous partitions correspond to the higher parts of the lattice.

Answer 1

This is a very interesting question. As far as I can tell, there is no standard terminology for this, although I was able to find places where this observation has been made before.

Regarding the partial order on compositions (i.e. contiguous set partitions) corresponding to finer vs. coarser, one can find that defined in section 2.1 of this preprint on ArXiV. Notions of finer vs. coarser(/fatter) can also be found in the SageMath reference manual for compositions (i.e. contiguous set partitions) as well as for ordered set partitions.

Bonus question: I will start with your "opposite" operation, namely which has

INPUT:

• A composition $P_1$ of $M$ (contiguous set partition of $[M]=\Omega$) with length $N$.
• A composition $Q$ of $N$ (contiguous set partition of $[N]$) with length $\ell$.

OUTPUT:

• A composition $P_2$ of $M$ (contiguous set partition of $[M]=\Omega$) with length $\ell$.

Here length means the number of blocks/number of parts, and I believe is defined the same way in both the preprint section 2.1 and the Sage Manual for Compositions.

The SageMath reference manual defines this operation as "fatten". The first input $P_1$ is self in the manual, and the second input $Q$ is grouping. So $P_2 = P_1 \blacktriangleright Q =$P1.fatten(Q).

Note that a paper also defines a fattening, but this seems to be unrelated, one reason being since the paper is discussing (unordered) integer partitions, not compositions (ordered integer partitions), as evidenced by the numerous Young diagrams. Other papers besides that one also define "quotient" operations for integer partitions, which again seem to be unrelated.

Question: Personally I would call your "forward" quotient operation the "backwards" or "opposite" operation, but really this difference of opinion is immaterial. Anyway to be unambiguous, the operation I am referring to from your question has the signature:

INPUT:

• A composition $P_1$ of $M$ (contiguous partition of $[M]=\Omega$) with length $N$.
• A composition $P_2$ of $M$ (contiguous partition of $[M]=\Omega$) with length $\ell$ such that $\ell \le N$.

OUTPUT:

• A composition $Q$ of $N$ (contiguous partition of $[N]$) with length $\ell$.

This one is fairly hidden/obscured in the SageMath reference manual, but it does seem to be there. Specifically, the operation is referred to as "refinement splitting lengths" in the manual, where self is the second input $P_2$ to the operation above, and J is the first input $P_1$. The operation is defined in terms of another operation, "refinement splitting".

Anyway, what you define as $Q =\frac{P_1}{P_2} =$P2.refinement_splitting_lengths(P1).

Since the SageMath reference manual does not give sources/references for papers or books that use these terms, this would seem to be a dead end. It seems like the developers might have chosen the names themselves, since they had the same problem you did, of not being able to find pre-existing standard terminology for these operations. Perhaps searching the SageMath "trac" (bug reporting/mailing list) could help; for example it seems from here that refinement_splitting_lengths may have originally been called refinement.

---

Aside: Looking at your question I notice that you originally asked about set partitions, but then switched to the special case of contiguous set partitions due to issues of things being well-defined. However, I think that you could have possibly also generalized to ordered set partitions instead to resolve this, which perhaps you might have found more satisfactory.

Notice that compositions (contiguous set partitions) and ordered set partitions are related. As the SageMath reference for ordered set partitions notes, every ordered set partition has an associated composition. In fact, as explained in section 2.2. of the preprint, there is a bijection between ordered set partitions and pairs of (i) compositions and (ii) permutations of the ground set such that the descent set of the permutation is a subset of the descent set of the composition. (Descent sets of compositions and of permutations are defined in the preprint.) Note that pairs of compositions and arbitrary permutations are in bijective correspondence with all "ordered ordered set partitions", i.e. set partitions where not only the order of the blocks matters, but also the order of the elements within each block matters.

The SageMath reference manual defines a "fatten" operation for ordered partitions of sets also, where the grouping is assumed to be a composition. However, the grouping could also be an ordered partition of sets. Consider the example they start with, where the finer ordered partition is: $$ \{2,5\}, \{1\}, \{3, 4\} \,.$$ The fattening according to the ordered set partition (grouping) $\{1,3\}, \{2\}$ would be: $$ \{2,3,4,5\}, \{1\} \,, $$ the fattening according to the ordered set partition (grouping) $\{2\}, \{1,3\}$ would be: $$ \{1\}, \{2,3,4,5\} \,,$$ the fattening according to the ordered set partition (grouping) $\{1,2\}, \{3\}$ is: $$ \{1,2,5\}, \{3,4\} \,,$$ the fattening according to the ordered set partition (grouping) $\{3\}, \{1,2\}$ is: $$ \{3,4\}, \{1,2,5\} \,,$$ etc. All of this can be generalized.

Specifically, there is a bijection between ordered partitions of the set $[M]$ with length $N$ ($N$ blocks) and surjective functions $[M] \to [N]$. The equivalence classes/pre-images $f^{-1}(n)$ for every $n \in [N]$ are the blocks of the partition, and the natural order on $[N]$ serves as the order for the blocks. (The requirement that the function is surjective ensures that the number of blocks is exactly $N$ and that there is no double-counting of ordered partitions. Notice also that a surjective function $[M] \to [N]$ exists if and only if $M \ge N$, which is the same condition for an ordered partition of $[M]$ into $N$ blocks to exist. My claim is that this is not a coincidence.)

The grouping is always an ordered partition of $[N]$ into $\ell$ blocks, which according to the above corresponds to a unique surjective function $[N] \to [\ell]$. Then the fattening of the ordered set partition $[M] \xrightarrow{P_1} [N]$ by the grouping (also an ordered set partition) $[N] \xrightarrow{Q} [\ell]$ corresponds to the function $[M] \xrightarrow{Q \circ P_1} [\ell]$. This works because the composition of surjective functions is again a surjective function.

Defining this only for contiguous set partitions corresponds to the restriction that the functions not only be surjective, but also monotone. Specifically, I claim that there is a bijection between contiguous set partitions of $[M]$ into $[N]$ blocks and surjective and monotone functions $[M] \to [N]$ (monotone with respect to the natural orders on $[M]$ and $[N]$). The monotone condition essentially forces the blocks to always have a certain order (for instance, $1$ always goes into the first block), and since the order is always fixed to be the "same" the order of the blocks in some sense no longer matters, i.e. this is why the bijection of surjective monotone functions is with (unordered) contiguous set partitions, not ordered contiguous set partitions.

Anyway, in this case the fattening operation also corresponds to function composition -- this works out since the composition of two monotone functions is again monotone, so the composition of two functions, both of which are surjective and monotone, is again surjective and monotone.

Therefore, your question about "quotient partitions" actually corresponds neatly to a question about "quotients of functions". Specifically, the question of, given two compositions $P_1, P_2$ of $M$ into $N, \ell$ blocks respectively, finding a composition $Q$ of $N$ into $\ell$ blocks such that $P_1 \blacktriangleright Q = P_2$ corresponds to the question of, given surjective and monotone functions $[M] \xrightarrow{P_1} [N]$ and $[M] \xrightarrow{P_2} [\ell]$, finding a unique function $[N] \xrightarrow{Q} [\ell]$ such that $Q \circ P_1 = P_2$. (This is why I would write $Q = \frac{P_2}{P_1}$ instead of $Q = \frac{P_1}{P_2}$, note also that the former also arguably corresponds to the signature of refinement_splitting_lengths in the SageMath.)

Anyway, the fact that $P_1$ is by assumption surjective means that a solution $Q$ is unique (surjective functions are epimorphisms), and a solution always exists I believe by the "finite axiom of choice" (which technically isn't an axiom, but whatever). There is also a simple argument by contradiction, based on the fact that both $P_1$ and $P_2$ are monotone, that the unique solution $Q$ must also be monotone, thus itself correspond to a unique contiguous set partition. (Also a simple argument by contradiction, based on the fact that both $P_1$ and $P_2$ are surjective, that $Q$ must also be surjective.)

Anyway the point being that when $P_1$ and $P_2$ are just surjective, but not necessarily monotone (i.e. they correspond to ordered set partitions), we are still guaranteed a unique solution $Q$ to the equation $Q \circ P_1 = P_2$ which is still guaranteed to be surjective, i.e. to correspond to a unique ordered set partition itself.

This sort of function division problem is called finding an "extension" in some contexts, at least if $P_1$ were injective instead of surjective. It is also called the "determination problem", at least according to section 2 of Article II of Lawvere, Schanuel, Conceptual Mathematics.

What I am trying to say is that to the extent that this quotient partition operation is a special case of determination problem, there is in some sense standard terminology for it (both in the special case of compositions you discuss, and the general case of ordered set partitions you alluded to). Admittedly this doesn't address the specific case you're interested in, so is perhaps a somewhat unsatisfactory answer.