### A combinatorial intermediate value lemma

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

Ndenotes any integer divisible by all integers up tom, then for any collectionof

Nintegers up tom, there is a subsetIof the integers up toNsuch 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.