Nuking mosquitoes: Commutative algebra and the Frobenius problem

Posted by: Alan Guo | July 13, 2011

Nuking mosquitoes: Commutative algebra and the Frobenius problem

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 $a_1, a_2, \ldots, a_n$ with $\gcd(a_1, a_2,\ldots,a_n) = 1$ , what is the largest integer $m$ that cannot be written in the form $m = c_1a_1 + c_2a_2 + \cdots c_na_n$ for nonnegative integers $c_i$ ? For demonstrative purposes, I’ll show you how you can use commutative algebra to solve the case $n = 2$ , but the principle generalizes to larger $n$ . 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 $Q = \{c_1 a + c_2 b : c_1,c_2 \ge 0\}$ . The problem statement implicitly assumes $\mathbb{N} \setminus Q$ is finite, but this is not difficult to show, especially when you’re wielding the rocket launcher that is commutative algebra. Notice that $Q$ is a affine semigroup, which just means that it’s isomorphic to a finitely generated subsemigroup of $\mathbb{Z}^d$ for some $d$ . The saturation $Q_{\text{sat}}$ of an affine semigroup $Q$ is what you get when you take the group generated by $Q$ intersected with the nonnegative cone $Q$ generates. In symbols, $Q_{\text{sat}} = \mathbb{Z} Q \cap \mathbb{R_+} Q$ . 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, $Q_{\text{sat}} = \mathbb{N}$ . 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 $Q$ contains a translate of $\mathbb{N}$ , so there’s some number after which every number is in $Q$ .

The generating function $p(t) = \sum_{i \notin Q} t^i$ for $\mathbb{N} \setminus Q$ is a polynomial, and furthermore it is $\frac{1}{1-t}$ minus the Hilbert series $h_M(t)$ for $M = \mathbb{C}[t^a, t^b]$ , since the monomials in $\mathbb{C}[t^a, t^b]$ are precisely the ones whose exponents are in $Q$ . So now if we could find a nice form for $h_M(t)$ , then we’d be done.

We can view $M$ as a module over $R = \mathbb{C}[x,y]$ where $\deg(x) = a$ and $\deg(y) = b$ . Then we have an exact sequence

$0 \to (x^b - y^a) \to \mathbb{C}[x,y] \to \mathbb{C}[t^a,t^b] \to 0$

where the second map from the left is inclusion and the third map is $x \mapsto t^a, y \mapsto t^b$ , which is a surjection, so it suffices to show that we have exactness in the middle. Let $I = (x^b - y^a)$ and let $K = \ker(R \to M)$ . Now, it is straightforward to see that $I \subseteq K$ . On the other hand, since $\mathbb{C}[x,y] / K \cong \mathbb{C}[t^a,t^b]$ which is not a field, we know that $K$ is not a maximal ideal, hence $\dim K \ge 1$ , where $\dim$ here is the Krull dimension. We know that $\dim \mathbb{C}[x,y] = 2$ and the $0$ ideal is prime and $0 \subsetneq I$ , so $\dim I \le 1$ . But the containment $I \subseteq K$ implies that $\dim I \ge \dim K$ , so we have $1 \ge \dim I \ge \dim K \ge 1$ , hence $\dim I = \dim K$ . To show that $I = K$ , we just need to show that $I$ is prime, but this follows from the fact that $\gcd(a,b) = 1$ .

Now, note that the Hilbert series $h_I(t)$ for $I$ is just $\frac{t^{ab}}{(1-t^a)(1-t^b)}$ since $\deg(x^b - y^a) = ab$ , so by rank-nullity,

$\displaystyle h_M(t) = h_R(t) - h_I(t) = \frac{1 - t^{ab}}{(1-t^a)(1-t^b)}$ .

We have

$\displaystyle h_M(t) + p(t) = \sum_{i \in Q} t^i + \sum_{i \notin Q} = \sum_{i \in \mathbb{N}} t^i = \frac{1}{1-t},$

hence

$\displaystyle h_M(t) = \frac{1}{1-t} - p(t) = \frac{f(t)}{1-t}$

where $f(t) = 1 - p(t) + tp(t)$ is a polynomial since $p(t)$ is. Now, the final answer to our problem is $\deg p = \deg f - 1$ . But

$\displaystyle \frac{1-t^{ab}}{(1-t^a)(1-t^b)} = \frac{f(t)}{1-t}$

$(1-t)(1-t^{ab}) = (1-t^a)(1-t^b)f(t).$

Since the degrees of both sides must be equal, we have $1 + ab = a + b + \deg f$ , whence $\deg f = 1 + ab - a - b$ . So our answer is $\deg p = ab - a - b$ . 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 $Q$ 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

About these ads

Posted in Commutative Algebra | Tags: Commutative Algebra, frobenius problem, hilbert series

Responses

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 Sam on July 13, 2011
at 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: aguo777 on July 14, 2011
at 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 Leuschke on July 14, 2011
at 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 Alexander on July 14, 2011
at 8:42 PM
[...] Alan Guo: Cantor’s diagonal argument and undecidability, Commutative algebra and the Frobenius problem [...]
By: Tenth Linkfest on July 30, 2011
at 7:07 PM

Concrete Nonsense