The question

Let $L$ be a lattice (in the sense of combinatorics, not number theory).

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.


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 (solution) (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 can be proven using Theorem 2 in math.stackexchange post #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.

  • $\begingroup$ I don't understand: can't I just add many copies of $0$ to $A$ to get something greater than $A$? But how can I do this via raising or synthesizing? $\endgroup$ – Sam Hopkins Sep 15 '18 at 18:31
  • $\begingroup$ Let’s say I take the graded lattice with 0,1 and three incomparable elements at rank one. Then take A to be set of the incomparable rank one guys, B to be multi set with 0 twice, and 1 once. Then I believe A <= B but I don’t think it can be obtained the way you want. Or maybe I’m missing something. $\endgroup$ – Sam Hopkins Sep 15 '18 at 18:47
  • $\begingroup$ @SamHopkins: Ah, you're right! So we need at least distributivity. $\endgroup$ – darij grinberg Sep 15 '18 at 18:53
  • $\begingroup$ I think you can do the same thing with the Boolean lattice of rank 3: take A = set of three rank one guys, B=0 twice, 1 once $\endgroup$ – Sam Hopkins Sep 15 '18 at 19:04
  • $\begingroup$ @SamHopkins: I don't think so. I think you can get $B$ from $A$ by two synthesizings. $\endgroup$ – darij grinberg Sep 15 '18 at 19:07

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$.)


| cite | improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.