Are Minkowski sums of upward closed "convex" sets in $\mathbb{N}^k$ still "convex"? (WAS: Comparing mana costs in Magic: The Gathering)

Question

This was originally a question about comparing mana costs in Magic: The Gathering, but it's turned into a question about Minkowski sums of upward-closed convex sets in $\mathbb{N}^k$. The original question is preserved below, if you want to see the original motivation (or have an answer to the original question that doesn't bear on this new one).

The question is this -- say we have two convex polyhedra $A$ and $B$ in $\mathbb{R}_{\ge0}^k$ whose vertices lie in the lattice $\mathbb{Z}^k$ (they're "lattice polyhedra"); and say moreover that both $A$ and $B$ are upward closed in the obvious partial order (i.e., for each of them, the recession cone is equal to $\mathbb{R}_{\ge0}^k$). Then is $(A+B)\cap \mathbb{Z}^k=(A\cap\mathbb{Z}^k)+(B\cap\mathbb{Z}^k)$?

This question seems to be more commonly asked in the case that $A$ and $B$ are polytopes, that is bounded, that is both have recession cone equal to $\{0\}$ rather than to $\mathbb{R}_{\ge0}^k$. In this case the answer is no, and just proving conditions under which it holds is as best I can tell an open problem in dimensions greater than 2. But I'm wondering if in this alternate context the problem is easier.

That's the question; but if you want to know what this has to do with mana costs in Magic: The Gathering, or whether it might be easier to answer the original question rather than this, read on...

---

Yes, this is a combinatorics question, dealing with something like matchings where sometimes one vertex is allowed to match two other vertices instead of just one like usual! But it arises from Magic and so will need some setup to state. (I would certainly be interested in generalizations, too.)

Background: In Magic: The Gathering, there are 6 types of "mana", denoted {W}, {U}, {B}, {R}, {G} (the 5 colors of mana), and {C} (colorless mana). (We can also imagine a 7th type, {P}, representing 2 life; this is not an actual type of mana.) Mana comes in whole number amounts; by an "amount of mana" I mean a specified whole number amount of each type (and some amount of life, I suppose). A mana cost describes a set of amounts of mana sufficient to pay the cost. A mana cost consists of some number of the following symbols:

• {W}, {U}, {B}, {R}, {G} -- payable only by 1 mana of that color
• {C} -- payable only by 1 colorless mana
• {W/U}, {U/B}, {B/R}, {R/G}, {G/W}, {W/B}, {U/R}, {B/G}, {R/W}, {G/U} -- payable by 1 mana of either appropriate color (all 10 color pairs are listed here)
• {1} -- payable by 1 mana of any type, colored or colorless
• {W/P}, {U/P}, {B/P}, {R/P}, {G/P} -- payable by the appropriate color or by 2 life (which we can think of as a fictitious type of mana, {P})
• {2/W}, {2/U}, {2/B}, {2/R}, {2/G} -- payable by the appropriate color of mana or by any 2 mana (colored or colorless)

(Yes, for those familiar with Magic, I am ignoring {X} and I am ignoring the question of snow, since those don't seriously affect the problem. Indeed we didn't actually need all the above, but I figured I'd be thorough...)

We can put a partial ordering on the set of mana costs as follows: A≤B if any amount of mana sufficient to pay for B is sufficient to pay for A.

Then, the question is, given two mana costs, how can we determine whether one is less than equal to another or not?

If we ignore the existence of the symbols of the form {2/M}, then this problem is not hard; using Hall's marriage theorem, we can see that one just has to check a number of inequalities; specifically, that for each set S of types of mana (including the fictitious {P}), the number of mana symbols in A corresponding to a subset of S must be no more than the number of mana symbols in B corresponding to a subset of S. This gives us at most 2^7 inequalities to check (in fact given the symbols that actually exist one only needs to check 65 of them).

But the {2/M} symbols are more of a problem. Because they can correspond to 1 or 2 mana, the marriage theorem doesn't apply. One way to handle this is disambiguation -- each {2/M} symbol can be disambiguated to either {2} or {M}. Then A≤B iff for every disambiguation B' of B there's some disambiguation A' of A such that A'≤B'.

However, this is slow in the worst case, because it requires checking lots of disambiguations. My question is: Can we do better?

I hypothesize the following two statements that will help reduce the number of disambiguations needed when symbols of the form {2/M} are involved:

1. Cancellation applies. That is: If we define addition of mana costs in the obvious way, it's clear that $a\le b$ implies $a+c\le b+c$. If we don't allow symbols of the form {2/M}, the converse also holds, by the reasoning above. Question: Does it also hold when such symbols are allowed? Edit: It seems a positive answer to #3 implies a positive answer to this (see comments). I'm retitling the question to focus on #3.

2. Suppose we have mana costs A and B and suppose M is a color such that the symbol {2/M} does not occur in A. Is it true then that A≤B if and only if A≤B', where B' consists of B but with all instances of {2/M} replaced by {1}? (EDIT: Disproved in the comments by Pace Nielsen. It does however hold if we require A have no symbols of the form {2/M} for all colors M (again, sketch in the comments), but unfortunately that weaker form doesn't form such a useful part of computing the order relation.)

3. (Added after Will Sawin asked it in the comments) -- is the set of amounts of mana sufficient to pay for a given mana cost (including the fictitious {P}) equal to a convex polyhedron intersected with the integer lattice? (Or integer amounts of mana and even amounts of life, if you prefer to think of it that way.) If so this might give us a faster way to compare than disambiguation, by comparing the convex sets (assuming they can be determined quickly; I'm not sure that they can). (This is definitely true if we ignore symbols of the form {2/M}, by the above reasoning.) Note that it's important here that we allow overpaying; it's not true if we don't (see comments).

(I don't think there's any way to get rid of the necessity of doing at least some disambiguations; if A has more of some {2/M} symbol than B, I think you are just going to have to handle those manually. But both the above statements at least would bring it down to only doing that.)

So far I haven't been able to prove these work, nor find any counterexample. Can anyone prove or disprove these?

In addition like I said I'd be interested to see generalizations. As long as each symbol corresponds to 1 mana the whole thing just comes down to the marriage theorem like I said above. But when symbols can correspond to varying amounts I wouldn't expect it to work so nicely in general. It does seem to still work nicely for the set of symbols that actually exist, as listed above (although I might be wrong!). Is there some abstract property of this set of symbols that causes this, so that we can say when this sort of thing happens? It would be interesting to see.

Thank you all!

Answer 1

It seems to me that all of the standard counter-examples to the polytope question easily adapt to be counter examples to this question: Take any polytopes in $\mathbb{Z}^{k-1}$ with $(A_0+B_0) \cap \mathbb{Z}^{k-1} \neq (A_0 \cap \mathbb{Z}^{k-1}) + (B_0 \cap \mathbb{Z}^{k-1})$. Embed $\mathbb{Z}^{k-1}$ into $\mathbb{Z}^k$ as $\{ (x_1, \ldots, x_k) : \sum x_i=0 \}$. Let $A$ and $B$ be the Minkowski sums $A_0+\mathbb{Z}_{\geq 0}^k$ and $B_0 + \mathbb{Z}_{\geq 0}^k$. Then $(A+B) \cap \mathbb{Z}^{k-1} = (A_0+B_0) \cap \mathbb{Z}^{k-1}$, $A \cap \mathbb{Z}^{k-1}=A_0\cap \mathbb{Z}^{k-1}$ and $B \cap \mathbb{Z}^{k-1}=B_0\cap \mathbb{Z}^{k-1}$, so $A$ and $B$ have the same problem.

As a concrete example, take $A_0 = \mathrm{Hull}( (0,0,0),\ (1,1,-2))$ and $B_0 = \mathrm{Hull}( (1,0,-1),\ (0,1,-1))$. Then $(1,1,-2) \in A_0 + B_0$, but is not in $(A_0 \cap \mathbb{Z}^3) + (B_0 \cap \mathbb{Z}^3)$. Take $A = A_0 + \mathbb{Z}_{\geq 0}^3$ and $B = B_0 + \mathbb{Z}_{\geq 0}^3$ and you see exactly the same problem occurring with the recession cones your requested.