{"id":143,"date":"2008-11-06T20:01:54","date_gmt":"2008-11-06T19:01:54","guid":{"rendered":"https:\/\/wpethzprd.ethz.ch\/kowalski\/2008\/11\/06\/a-combinatorial-intermediate-value-lemma\/"},"modified":"2024-02-20T13:40:57","modified_gmt":"2024-02-20T11:40:57","slug":"a-combinatorial-intermediate-value-lemma","status":"publish","type":"post","link":"https:\/\/blogs.ethz.ch\/kowalski\/2008\/11\/06\/a-combinatorial-intermediate-value-lemma\/","title":{"rendered":"A combinatorial intermediate value lemma"},"content":{"rendered":"

Some of the discussions during the Random Matrix, L-functions and primes<\/em><\/a> 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<\/em> for the CNRS in Lyon).<\/p>\n

Here’s the problem in question, which involves an arbitrary positive integer m<\/em>:<\/p>\n

Is it true, or not, that if N<\/em> denotes any integer divisible by all integers up to m<\/em>, then for any collection<\/p>\n

$latex f(1),\\ldots, f(N),\\text{ with } 1\\leq f(i)\\leq m,$<\/p>\n

of N<\/em> integers up to m<\/em>, there is a subset I<\/em> of the integers up to N<\/em> such that<\/p>\n

$latex \\sum_{i\\in I}{f(i)}=N$<\/p><\/blockquote>\n

I see this as a kind of “intermediate value” property, since the sum over all integers of f(i)<\/em> must be at least N<\/em>. The condition that N<\/em> be divisible by each integer up to m<\/em> is necessary (because one can take each integer f(i)<\/em> to be the same k<\/em> in that range), and it is also clear that if N<\/em> has the stated property, then any multiple of it also does (by splitting the range into subsets of size N<\/em>).<\/p>\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<\/em> or 6<\/em> (where the smallest N<\/em> allowed, which is 60<\/em> 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<\/em> the case that the exceptions are genuine. (In fact, in my version, his argument works for m<\/em> at least equal to 7<\/em>, but the other potential exceptions can easily be treated by hand).<\/p>\n

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<\/a> of his solution, which I have just put on the “Notes and unpublished results<\/a>” section of my home page.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading A combinatorial intermediate value lemma<\/span><\/a><\/p>\n","protected":false},"author":625,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-143","post","type-post","status-publish","format-standard","hentry","category-blogroll"],"_links":{"self":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/143","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/users\/625"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/comments?post=143"}],"version-history":[{"count":0,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/posts\/143\/revisions"}],"wp:attachment":[{"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/media?parent=143"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/categories?post=143"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ethz.ch\/kowalski\/wp-json\/wp\/v2\/tags?post=143"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}