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,

.

We have

hence

where is a polynomial since is. Now, the final answer to our problem is . But

so

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!

-Alan

A good source for learning the basic properties of C-M regularity is Chapter 4 of Eisenbud’s Geometry of Syzygies. It’s an invariant of a graded module which can be defined using its minimal free resolution, and it tells you when the Hilbert function and Hilbert polynomial start to agree (Theorem 4.2), and is tight in the case the module is Cohen-Macaulay (which is true for all semigroup algebras).

But that book is dealing with standardly graded algebras (i.e., each variable has degree 1). In your case, you have deg(t) = 1, so in order for C[x,y] -> C[t^a,t^b] to be homogeneous, you need deg(x) = a and deg(y) = b. Things can be adjusted if you look at the proof of Theorem 4.2 (it’s nothing high tech).

But all of this assumes that things are still Z-graded. I imagine that the Maclagan-Smith paper says something about Z^n-gradings. It’s not obvious to me what these definitions should mean because all of the definitions in the Z-grading case use that Z is totally ordered.

However, if you’re interested, and around MIT, we should talk (send me an email and we can meet). I like combinatorial commutative algebra.

By:

Steven Samon July 13, 2011at 11:55 PM

Thanks for the reference! I will check that out ASAP. And I’m up for meeting to talk about combinatorial commutative algebra when I’m at MIT. Although I don’t know that much about CCA, it’s one of those things that I want to know a lot about, since it’s relevant to one of my research projects.

By:

aguo777on July 14, 2011at 12:59 AM

I’m pretty sure that there’s no known formula for the Frobenius number with $n \geq 3$. It’s a long-standing open problem.

By:

Graham Leuschkeon July 14, 2011at 2:12 AM

It’s not like killing flies with sledgehammers is a *bad* thing. Speaking as somebody who is very far from an expert on commutative algebra, articles like this are exactly what inspires me to go learn more of it: unexpected applications outside.

By:

Sam Alexanderon July 14, 2011at 8:42 PM

[…] Alan Guo: Cantor’s diagonal argument and undecidability, Commutative algebra and the Frobenius problem […]

By:

Tenth Linkfeston July 30, 2011at 7:07 PM