This is one of those things that convinced me that commutative algebra was cool and actually useful for solving combinatorial problems. The Frobenius problem (commonly known as the coin problem, of which a special case is the McNugget problem) asks: given positive integers with , what is the largest integer that cannot be written in the form for nonnegative integers ? For demonstrative purposes, I’ll show you how you can use commutative algebra to solve the case , but the principle generalizes to larger . At the end, I’ll speculate on how one might use this to solve higher-dimensional versions of the Frobenius problem, whatever that might mean.
Let . The problem statement implicitly assumes is finite, but this is not difficult to show, especially when you’re wielding the rocket launcher that is commutative algebra. Notice that is a affine semigroup, which just means that it’s isomorphic to a finitely generated subsemigroup of for some . The saturation of an affine semigroup is what you get when you take the group generated by intersected with the nonnegative cone generates. In symbols, . The difference between an affine semigroup and its saturation is that the saturation “fills in the gaps” of the original affine semigroup so that it looks like it came from an actual group. In our case, . A basic result (Exercise 7.15 from Combinatorial Commutative Algebra by Miller-Sturmfels) says that any affine semigroup contains a translate of its saturation. Well, that means contains a translate of , so there’s some number after which every number is in .
The generating function for is a polynomial, and furthermore it is minus the Hilbert series for , since the monomials in are precisely the ones whose exponents are in . So now if we could find a nice form for , then we’d be done.
We can view as a module over where and . Then we have an exact sequence
where the second map from the left is inclusion and the third map is , which is a surjection, so it suffices to show that we have exactness in the middle. Let and let . Now, it is straightforward to see that . On the other hand, since which is not a field, we know that is not a maximal ideal, hence , where here is the Krull dimension. We know that and the ideal is prime and , so . But the containment implies that , so we have , hence . To show that , we just need to show that is prime, but this follows from the fact that .
Now, note that the Hilbert series for is just since , so by rank-nullity,
where is a polynomial since is. Now, the final answer to our problem is . But
Since the degrees of both sides must be equal, we have , whence . So our answer is . Yay! And we solved it using purely algebra!
One can ask a similar question for higher dimensions. For example, the answer to the Frobenius problem also answers the question “Where does the translate of the saturation of start?” (after adding 1). There’s probably some similar question you can ask about higher dimensions, although now it’s not as clear what the “minimal” place where the saturation starts should be. I think it would make the most sense if an answer to such a question would take the form of a set of “generators”, where everything in the ideal generated by the “generators” is in the saturation. Anyway, if anyone knows the answer already, please let me know! I think the answer might lie in a paper of Maclagan and Smith titled Multigraded Castelnuovo-Mumford Regularity, but since I don’t even understand Castelnuovo-Mumford regularity in one variable, I have little hope of comprehending that paper.
Like always, if you catch any mistakes or have questions, leave a comment!