The question
============


Let $L$ be a [lattice (in the sense of combinatorics, not number theory)](https://en.wikipedia.org/wiki/Lattice_(order)).


An *$L$-bag* will mean a finite multiset of elements of $L$.


Given an $L$-bag $A$, we consider three possible operations that can be performed on $A$:


* *Raising* $A$ means picking some element of $A$ and replacing it by a larger element.
* *Synthesizing* $A$ means picking two elements $a$ and $b$ of $A$ and replacing them by $a \vee b$ and $a \wedge b$.
* *Extending* $A$ means adding a new element to $A$.


If $A$ is an $L$-bag, and if $q \in L$, then $w\_q\left(A\right)$ shall mean the number of elements $a$ of $A$ satisfying $q \leq a$. (Of course, they are counted with multiplicities.) Note that if $0$ is the global minimum of $L$, then $w\_0 \left(A\right) = \left|A\right|$.


If $A$ and $B$ are two $L$-bags, then we say that $A \leq B$ if and only if each $q \in L$ satisfies $w\_q\left(A\right) \leq w\_q\left(B\right)$. (Thus, in particular, we must have $\left|A\right| \leq \left|B\right|$ if $A \leq B$, because we can take $q=0$.)



> 
> **Question.** Is it true that two $L$-bags $A$ and $B$ satisfy $A \leq B$ if and only if $B$ can be obtained from $A$ by a (finite) sequence of raising operations, synthesizing operations and extending operations? If this isn't generally true, is it true for geometric lattices? modular lattices? distributive lattices?
> 
> 
> 


It is easy to see that the "if" part of the question is always true.


Context
=======


One of the most famous lattices is the set of positive integers, with the divisibility relation serving as the $\leq$ order of the lattice. I shall call this lattice $D$. The synthesizing operation on $D$ has been studied, e.g., in [Putnam 2008 problem A3](https://kskedlaya.org/putnam-archive/2008.pdf) ([solution](https://kskedlaya.org/putnam-archive/2008s.pdf)) (to be more precise: that problem studies this operation on tuples, which differ from $L$-bags in that they are ordered). One observation made in the solutions is that if the lattice $L$ is distributive, then for each $j$, any synthesizing operation preserves the meet of all joins of $j$-element sub-multisets of the $L$-bag. The same holds if the words "meet" and "join" are interchanged.


Note that if $a$ and $b$ are two elements of a principal ideal domain $R$, then $\left(R / aR\right) \oplus \left(R / bR\right) \cong \left(R / \gcd\left(a,b\right)R\right) \oplus \left(R / \operatorname{lcm}\left(a,b\right)R\right)$ as $R$-modules. Thus, the synthesizing operation naturally comes up when "streamlining" finitely generated $R$-modules.


My own motivation for the question is that if the answer is positive (at least for the distributive lattice $D$), then ZetaX's claim in [MathLinks post #2284393](http://artofproblemsolving.com/community/c7h408607p2284393) can be proven using Theorem 2 in [math.stackexchange post #2917929](https://math.stackexchange.com/q/2917929/).


When the lattice $L$ is a chain, the answer to the question is definitely positive. In this case, the synthesizing operations do nothing, whereas the relation $\leq$ on $L$-bags is what I believe is called the "Gale order". It can be alternatively defined by "$A \leq B$ if and only if $\left|A\right| \leq \left|B\right|$ and the $k$-th largest element of $A$ is $\leq$ to the $k$-th largest element of $B$ for each $k \leq \left|A\right|$". I don't have good references on this case, but all the proofs are simple. There are connections to coplactic operations (i.e., combinatorial crystals) and Kohnert diagrams, but I think these aren't very topical to the question above.



Gale order on multisets of elements of a lattice
The answer is "no" for the "only if" part of the question, even when the lattice is a Boolean lattice.


For a counterexample, let $L$ be the Boolean lattice of all subsets of $\left\{1,2,3\right\}$. Let $A$ be the $L$-bag whose elements are $\varnothing, \left\{2,3\right\}, \left\{3,1\right\}, \left\{1,2\right\}$. Let $B$ be the $L$-bag whose elements are $\left\{1\right\}, \left\{2\right\}, \left\{3\right\}, \left\{1,2,3\right\}$. Then, $A \leq B$, but $B$ cannot be obtained from $A$ by a (finite) sequence of raising operations, synthesizing operations and extending operations. (Indeed, applying any such operation to $A$ would yield either $A$ again, or an $L$-bag $C$ that no longer satisfies $C \leq B$.)


Sad.


