A combinatorial problem with connections to a result of Grothendieck

Alexander Grothendieck was one of the great mathematicians of the ${20^{th}}$ 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 ${57}$, but this is not a prime since ${57= 3 \times 19}$. 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”:

${\dots}$ 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 ${\mathbb{C}^{n} \rightarrow \mathbb{C}^{n}}$ 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.

The Problem

Imagine that Alice is given a set of cups, where each one contains between ${1}$ and ${b}$ 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 ${(k,l)}$ state provided:

1. All cups contain at most ${l}$ peas.
2. The total number of peas in cups with strictly less than ${l}$ peas is ${k}$.

Call a cup full if the cup has ${l}$ peas. Thus, the second condition is the number of peas in non-full cups is at most ${k}$: clearly, most of the peas are in cups that are full. The question is: Given ${b}$, are there ${k,l}$ so that Alice can always reach a ${(k,l)}$ state by only doing pouring operations? Note, for a fixed ${b}$, we need a fixed ${(k,l)}$ so that given any instance of cups with 1 to ${b}$ peas, Alice should be able to reduce it to a ${(k,l)}$ state.

Some Examples

Suppose that Alice starts with cups that contain either ${1}$ or ${2}$ peas. Then, clearly she can achieve a ${(1,2)}$ state. She just pours as many cups with ${1}$ pea into another cup with ${1}$ pea. When she cannot do any more, all the cups have ${2}$ peas—except for at most one cup.

Here is a more general case: suppose that Alice gets cups with ${1}$, ${2}$, or ${3}$ peas. Then, I claim that she can reach a ${(7,6)}$ state. First, we can assume that Alice looks at all the ${1}$ cups and ${2}$ cups and gets them to a ${(1,2)}$ state. When this is done she will have at most one ${1}$ cup, and some number of ${2}$ and ${3}$ cups. Then, she makes ${6}$ cups in two different ways:

• She pours a ${2}$ and another ${2}$ into some ${2}$: this makes one ${6}$.
• She pours a ${3}$ into some other ${3}$: this makes one ${6}$ also.

When she has done this she will be left with some number of ${6}$ cups, and at most one ${1}$ cup, at most two ${2}$ cups, and at most one ${3}$ cup. This adds up to ${8}$. But, she can avoid ${8}$, since if this is the situation she can make one more ${6}$ cup:

$\displaystyle 1 + 2 + 3 = 6.$

Thus, the claim is true.

The General Case

I claim without a detailed proof the following theorem:

Theorem: For any ${b}$ there are ${k,l}$ so given any number of cups of up to ${b}$ peas, Alice can reach a ${(k,l)}$ state by pouring operations.

The proof is simply a generalization of the idea used in the last example. Given cups of size ${r}$ and ${s}$, create cups of size ${rs}$: a repeated use of this idea will eventually stop with all but a “few” peas left over. The bound this yields on ${(k,l)}$ is finite, but it is not very small.

Open Problems

Is this a standard problem? In any case, what are the best values for ${k,l}$ given ${b}$?

Finally, I will explain the connection between the cup problem and the Ax-Grothendieck theorem in a future post.

February 16, 2010 12:09 pm

Unless I’m missing something, minimizing l seems straightforward: it has to be the LCM of 1..b, because you have to handle the situation where every cup you’re given has the same number of peas.

It seems unlikely that choosing larger values of l could reduce k, so then the interesting part of the problem seems to be whether you can systematically apply tricks like your reduction from the k=8 tok=7 for b=3.

My gut feeling is that those tweaks won’t make a significant difference (in some appropriately defined asymptotic sense), and that they’ll be non-systematic. Fortunately gut feelings are often (interestingly) wrong.

February 16, 2010 12:45 pm

If you care only about k, then one can give an exact bound: it is the smallest number that is divisible by 1, 2, …, b. That is, the lcm(1, 2, …, b) which is OEIS A003418.

Pf. Suppose k is not divisible by some d, with 1 <= d <= b. Then an arrangement of a lot of buckets with d peas can never be made into one that has even one bucket with k peas.

Suppose k is divisible by lcm(1, 2, …, b). Then consider d, with 1 <= d <= b. If there are more than k/d buckets with d peas in each, we can combine them to get a bucket with k buckets. After repeating this operation, there will be at most k/d – 1 buckets left with exactly d peas. If you do this for all d, there will be at most sum_d(k/d-1) buckets with less than k peas. □

I think that some number theory says k is e^theta(n). The corresponding l from this proof (which in not optimal) is also something like e^theta(n).

February 16, 2010 1:01 pm

Errata: It appears I have switched the roles of k and l — oops! Also, “are more than” should be “are at least”, and “n” should be “b”. Finally, the relevant sum for (the actual) k is sum_d(k-d), which I believe remains e^theta(b).

February 16, 2010 1:53 pm

Your definition of a (k,l)-state doesn’t seem to match how you actually used it; the 2nd requirement is supposed to be counting cups, not peas, and should just require it to be at most k?

February 16, 2010 2:08 pm

Interesting. I’m a layman but I’d guess that:

1) l is divisible by d!
2) k is larger than l

1) suppose l is not divisible by f ≤ d, then k is not finite since we can always present an instance with more than k/f cups , each one containing f peas.

2) we can always present an instance with (d-1)!-1 cups, each one containing d peas, plus 2 cups, each one containg (d-1) peas.

What’s the most interesting question: assessing whether l strickly equals d! or minimizing k or something else?

February 16, 2010 2:51 pm

mmm… one very simple thing I did not realized before: whatever k is for l=d! then for l=F*d! we have k ≤ k’. So if we want to minimized k we can focus on l=d!

Miscalenious: sorry “d” refers to what rjlipton refers as “b”

5. February 18, 2010 10:50 am

From an article by Laurent Lafforge intitled Alexandre Grothendieck et Robert Langlands (Les Dossiers de La Recherche Nº 20, p. 57, 2005):

Grothendieck est un homme très mystérieux, un véritable extraterrestre dans l’histoire des mathématiques. Il les a pensées de façon extrêmement abstraite et avec une énergie surhumaine. (…) Il s’était donné pour but premier de prouver les quatres “conjectures de Weil”. Il en a démontrée trois et la derniére a été par Pierre Deligne en 1973 [avec des outils développés par Grothendieck].

Or in English (my translation):

Grothendieck was a very mysterious man, a real alien in the history of mathematics. He thought them in a very abstract way and with a superhuman energy. (…) He set as his first aim proving the four “Weil conjectures”. He proved three, and Pierre Deligne the last one in 1973 [with the tools developed by Grothendieck].

February 18, 2010 10:59 am

Can you fix it
Dick

• March 17, 2010 9:25 am

This is a copy of the original in French.

• March 23, 2010 1:18 pm

This is my last attempt to improve the translation.

“Grothendieck is a very mysterious man, a veritable outstanding figure in the history of math. He thought of math in an extremely abstract way and with super-human energy. (…) He had a goal to prove the four conjectures of Weil. He was able to show three of them, and the fourth was shown by Pierre Deligne in 1973 [with the use of tools developed by Grothendieck].”

6. February 18, 2010 6:55 pm

I regret the error ” … was … ” in my translation.
I even don’t know if there is a need of it but here is a revised one:
Grothendieck is a very mysterious man, a real alien in the history of Mathematics. He thought of Mathematics in a very high abstract way, and as he had a superhuman power. (…) He focused his efforts in proving the four Weil Conjectures, three of which were proved by him. Pierre Deligne proved the last one in 1973 [with the tools developed by Grothendieck].

• February 19, 2010 3:10 am

Correction:

He thought of Mathematics in a very high abstract way, with a superhuman power.

Remark: of course, my reply above was meant to Dick.

February 22, 2010 2:39 pm

You should consider posting this on Math Overflow.