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

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!

• I must be misunderstanding something, because the easiest example seems to be a counterexample. Consider $A_1=\{2/W\}$ and $B=\{W\}$. Then $A_1 < B$ with inequality. But the given algorithm would translate $A_1$ to $A_2 = \{1\}\{W\}$, and $B < A_2$, again with inequality. – Peter Taylor Oct 18 '17 at 10:43
• If we allow more general symbols then cancellation might not hold. For example, if $\{3/BB\}$ can either be paid with $\{B\}\{B\}$ or with any three mana, then $\{B/W\}\{B\}\{W\}\{3\} \geq \{B/W\}\{3/BB\}\{3/WW\}$ but $\{B\}\{W\}\{3\} \not\geq\{3/BB\}\{3/WW\}$. – Julian Rosen Oct 19 '17 at 2:28
• Your new question #2 is still negative. Take $\{2/B\}\{W\}\geq \{2/W\}\{W/B\}$. If we replace $\{2/B\}$ with $\{1\}$, then the inequality breaks. – Pace Nielsen Oct 19 '17 at 6:38
• An arguably simpler example than @Julian's, in the sense that it drops out of an attempted proof, is $BW(B+W) \ge (BB+WW)(B+W)$ but $BW \not\ge BB+WW$. Note the advantages of sum-product notation for seeing why. – Peter Taylor Oct 20 '17 at 7:17
• Harry, are you trying to make an argument that they should bring back mana burn? ;-) – Pace Nielsen Oct 20 '17 at 13:33

## 1 Answer

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.

• I suppose this can be adapted to any recession cone...? – Zach Teitler Dec 27 '17 at 1:41
• Oh, that's a good point (and makes some sense of why I failed to find counterexamples...). I have to note that this doesn't satisfy the condition I specified that $A$ and $B$ themselves be contained in the first orthant but that's easily fixed (translate them up until they are and it still works). – Harry Altman Dec 27 '17 at 6:16
• Annoyingly, this answers the revised question but not the original. That is, we know that "cost convexity" implies cancellation, and I asked whether "symbol convexity" (which holds for MTG symbols) implies "cost convexity". The answer is no. Unfortunately that doesn't tell us whether cost convexity does indeed hold! It still might hold even though the implication doesn't work. Still, unless someone posts a solution to that pretty quickly, I think I'm going to call this solved, even though the original question remains unsolved. And then if someone wants to re-ask that or something they can... – Harry Altman Dec 27 '17 at 6:20
• I suppose this is the best we can do for now, though -- your answer shows that to solve this problem, we'd have to solve the problem for polytopes in one dimension less. And even proving sufficient conditions it's not know how to do in dimensions greater than 2. So since there are more than 3 types of mana, this is probably the best answer we'll get for now. I'm going to mark this solved. – Harry Altman Dec 29 '17 at 6:56