Some of the discussions during the Random Matrix, L-functions and primes conference reminded me of an old combinatorial question I had been struggling with around the time of my PhD thesis, because of some potential (but highly hypothetical) applications to automorphic forms. After moving to Bordeaux, I had the chance of having Laurent Habsieger as a colleague and I told him about the question, which he then solved within a few days, around April 2001. (He is currently Directeur de Recherche for the CNRS in Lyon).
Here’s the problem in question, which involves an arbitrary positive integer m:
Is it true, or not, that if N denotes any integer divisible by all integers up to m, then for any collection
of N integers up to m, there is a subset I of the integers up to N such that
I see this as a kind of “intermediate value” property, since the sum over all integers of f(i) must be at least N. The condition that N be divisible by each integer up to m is necessary (because one can take each integer f(i) to be the same k in that range), and it is also clear that if N has the stated property, then any multiple of it also does (by splitting the range into subsets of size N).
I won’t explain the rather technical application I had in mind (which turned out to be so hypothetical as to vanish away anyway), but rather propose this as a challenge to combinatorialists (it might be already known, of course, though there would be a good chance Habsieger would have recognized it if it was standard). In fact, Habsieger’s proof shows that the answer is “Yes”, except possibly if m=5 or 6 (where the smallest N allowed, which is 60 here, might not work, and must be replaced, e.g., by 120 and 240, and their multiples, respectively). I believe these exceptions are just due to my ignorance in clearing up the corner cases in Habsieger’s argument, but in a sense I would be delighted if it were the case that the exceptions are genuine. (In fact, in my version, his argument works for m at least equal to 7, but the other potential exceptions can easily be treated by hand).
Since this is a challenge, I won’t reproduce the main ideas of the (quite elegant) argument, but the whole solution can be read in this write-up of his solution, which I have just put on the “Notes and unpublished results” section of my home page.