Cups, Peas, and Grothendieck
A combinatorial problem with connections to a result of Grothendieck
Alexander Grothendieck was one of the great mathematicians of the century. He has worked on many parts of mathematics, but is perhaps best known for his revolutionary work in algebraic geometry.
Today I want to discuss a combinatorial problem that has come up recently in my research. The problem is new to me, although it could easily be a well known problem—just not one well known to me. In any case, the problem seems interesting, and is connected to one of the famous theorems of Grothendieck.
There are many great stories about him—The Artist and the Mathematician is a good source of information about this unique genius. He has, for example, a “prime” named after him. The legendary story is that Grothendieck was once asked for a particular prime number, and he suggested , but this is not a prime since . Oh well.
Grothendieck is also famous for burning 25,000 pages of his original mathematics, and then disappearing into the Pyrenees. This happened back in the summer of 1991, yet much of his brilliant work was saved and is currently available on the web. He is apparently quite upset about this, and he has written a letter to Luc Illusie just this past January. He states in the letter, called his “Declaration d’intention de non-publication”:
that essentially all materials that have been published in his absence have been done without his permission. He asks that none of his work should be reproduced in whole or in part, and even further that libraries containing such copies of his work remove them.
This is so different from the view most of us take—we are always hoping someone will want to read our work. We want to see our fields advance, and hope that our small contributions may help advance them. But, clearly Grothendieck is special and is quite different from the rest of us.
Let’s turn to the famous theorem of Grothendieck:
Theorem: Any polynomial map from that is injective, is also surjective.
This is usually called the Ax-Grothendieck theorem—after James Ax and Grothendieck. I love this beautiful theorem and am currently trying to extend it. My combinatorial problem is a lemma that I need to prove my extension.
Imagine that Alice is given a set of cups, where each one contains between and small peas. Alice can see how many peas there are in any cup, and her goal is to “even” out the amounts in the cups. The only operation Alice can perform is: pour all of the contents of one cup into another cup—she then must throw out the empty cup. She is not allowed to move peas one by one. It has to be all of the cup or nothing.
Say the cups are in a state provided:
- All cups contain at most peas.
- The total number of peas in cups with strictly less than peas is .
Call a cup full if the cup has peas. Thus, the second condition is the number of peas in non-full cups is at most : clearly, most of the peas are in cups that are full. The question is: Given , are there so that Alice can always reach a state by only doing pouring operations? Note, for a fixed , we need a fixed so that given any instance of cups with 1 to peas, Alice should be able to reduce it to a state.
Suppose that Alice starts with cups that contain either or peas. Then, clearly she can achieve a state. She just pours as many cups with pea into another cup with pea. When she cannot do any more, all the cups have peas—except for at most one cup.
Here is a more general case: suppose that Alice gets cups with , , or peas. Then, I claim that she can reach a state. First, we can assume that Alice looks at all the cups and cups and gets them to a state. When this is done she will have at most one cup, and some number of and cups. Then, she makes cups in two different ways:
- She pours a and another into some : this makes one .
- She pours a into some other : this makes one also.
When she has done this she will be left with some number of cups, and at most one cup, at most two cups, and at most one cup. This adds up to . But, she can avoid , since if this is the situation she can make one more cup:
Thus, the claim is true.
The General Case
I claim without a detailed proof the following theorem:
Theorem: For any there are so given any number of cups of up to peas, Alice can reach a state by pouring operations.
The proof is simply a generalization of the idea used in the last example. Given cups of size and , create cups of size : a repeated use of this idea will eventually stop with all but a “few” peas left over. The bound this yields on is finite, but it is not very small.
Is this a standard problem? In any case, what are the best values for given ?
Finally, I will explain the connection between the cup problem and the Ax-Grothendieck theorem in a future post.