Cups, Peas, and Grothendieck
A combinatorial problem with connections to a result of Grothendieck
Alexander Grothendieck was one of the great mathematicians of the 
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 
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.
The Problem
Imagine that Alice is given a set of cups, where each one contains between 
Say the cups are in a 
- All cups contain at most
peas.
- The total number of peas in cups with strictly less than
.
Call a cup full if the cup has 
Some Examples
Suppose that Alice starts with cups that contain either 
Here is a more general case: suppose that Alice gets cups with 
- She pours a
- She pours a
When she has done this she will be left with some number of 
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
state by pouring operations.
The proof is simply a generalization of the idea used in the last example. Given cups of size 
Open Problems
Is this a standard problem? In any case, what are the best values for
Finally, I will explain the connection between the cup problem and the Ax-Grothendieck theorem in a future post.
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.
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).
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).
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?
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?
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”
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].
Can you fix it
Dick
This is a copy of the original in French.
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].”
Please excuse all these corrections.
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].
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.
You should consider posting this on Math Overflow.
Grothendieck is as ethic as man with integrity as great in mathematics. Greatings Dick!
Now, his letter poses interesting questions about the intelectual property rights of a mathematician. AFAIK mathematics results can not be copyrighted nor patented (in theory, of course) so making public one´s result seems irreversible. Would he prefer that someone published now the same results changing the words in it not quoting him as author ?
Although i do not agree with this state of affairs (the discovery/invention distinction is phylosophicaly weak and even if it was right and the the rule is to only grant property rights for invented things, who invented the land to which property rights are granted since a while everywhere ?).
For the same subject in another blog, where they publish the handwritten Grothendiecks letter (does Grothendiecks mandate of not publishing include this letter ?) see:
http://sbseminar.wordpress.com/2010/02/09/grothendiecks-letter/