Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Note: The problem is solved! See EDIT below.


The following question about integer partitions arose from a purely "practical" question: Does there exist better dynamic programming algorithms for the Knapsack problem?

Let $n,k$ be natural numbers, $n\gg k$. By a partition (of $n$ into $k$ parts) I mean a vector $x=(x_1,\ldots,x_k)$ of non-negative integers such that $x_1+\cdots+x_k=n$. Since order here matters, we have $\tbinom{n+k-1}{k-1}=\tbinom{n+k-1}{n}$ partitions. By an $r$-test I mean a pair $(S,b)$ where $S\subseteq \{1,\ldots,k\}$, $|S|=r$ and $0\leq b\leq n$ is an integer. Say that a partition $x$ passes such a test if $\sum_{i\in S}x_i=b$. Let us call $S$ the support, and $b$ the threshold of the test $(S,b)$. Finally, let $T(r)=T_{n,k}(r)$ denote the smallest number of $r$-tests such that every partition passes at least one of these tests. It is easy to see that:

  1. $T(k)=1$: every partition passes the test $(\{1,\ldots,k\},n)$.
  2. $T(k-r)=T(r)$ for all $r=1,\ldots,k-1$: a partition passes a test $(S,b)$ if and only if it passes the test $(\overline{S},n-b)$.
  3. $T(r)\leq n+1$: just take all tests $(S,b)$ with $S=\{1,\ldots,r\}$ and $b=0,1,\ldots,n$.

Form (3) we have that $T(1)+T(2)+\cdots+T(k)\leq O(kn)$.

Does $T(1)+T(2)+\cdots+T(k)\geq \Omega(kn)$?

I am only interested in a rough bound holding for infinitely many numbers $n$ and $k$. The difficulty here is that the supports $S$ of different tests $(S,b)$ may be different, and may even overlap. If, say, all test must have the same support, say $S=\{1,\ldots,r\}$, then $T(r)\geq n+1$ thresholds $b$ are necessary for every $r=1,\ldots,n-1$: if some threshold $b$ is missing, then the vector $x=(b,0,\ldots,0,n-b)$ is a partition but it passes none of the tests. If, however, we had an additional test $(S',0)$ with $S'=\{2,\ldots,r+1\}$, then $x$ would already pass this test.

In general, even the case $r=1$ is not quite clear (at least to me).

Does $T(1)\geq \Omega(n)$?

Take a minimal set of $1$-tests, and let $B_i$ be the set of thresholds $b$ used by the $i$-th tests $(\{i\},b)$. Hence, we have to lower-bound $T(1)=\sum_{i=1}^k|B_i|$. We only know that $\overline{B}_1\times \overline{B}_2\times \cdots\times \overline{B_k}$ must avoid any partition. Simplest possibilities are to take $B_1=\{0,1,\ldots,n\}$ and $B_2=\ldots=B_k=\emptyset$, or to take all the $B_i$ equal to $\{0,1,\ldots,n/k\}$. Both possibilities use about $n$ tests. But how to argue that there are no better possibilities?

Has anybody seen anything related being considered?

EDIT: When properly used, Gerhard's "missing threshold" hint for the case $r=1$ leads to a tight answer $T(r)=n+1$ for all $1\leq r\leq k-1$.

In fact, we always need $\geq n+1$ tests, as long as supports are strictly smaller than $k$.

Proof: Argue by induction on $n$ and on the number $m$ of supports in the collection. If $m=1$, then we need $n+1$ tests, by the argument above. For general $m$, fix one support $S$ containing no other support (from our collection of tests) as a proper subset. Then take the smallest number $c$ which does not appear as a threshold $b$ in any of our tests of the form $(S,b)$. Thus, we must already have at least $c$ tests with support $S$. The remaining tests $(T,b)$ with $T\not\subseteq S$ can be modified in such a way that they cover all partitions of $n-c$ into $k-|S|$ parts. Namely, fix a string of numbers $(a_i:i\in S)$ summing up to $c$, and concentrate on partitions of $n$ containing this string. If some test $(T,b)$ participates in covering any of such partitions, and if $T\cap S\neq \emptyset$, then replace $(T,b)$ by the test $(T\setminus S,b')$ where $b'=b-\sum_{i\in S\cap T}a_i$. By induction hypothesis, there must be at least $n-c+1$ such tests, giving a lower bound $n+1$ on the total number of tests. $\Box$

Thanks, Gerhard, for a useful hint!

share|improve this question
    
You're welcome. If you want to follow the MathOverflow format, on your next question, anything that is an answer goes in the answer section. Your edit would do nicely in the answer section, although it is ok where it is. Gerhard "Happy To Be Of Service" Paseman, 2011.12.10 –  Gerhard Paseman Dec 10 '11 at 19:55
add comment

2 Answers

up vote 3 down vote accepted

I think your expression for the number of partitions needs a $k-1$ at the bottom instead of a $k$.

Considering $T(1)$, suppose you have a number of tests indexed by $t$ of the form $x_k=b_t$. If you are not covering all of the range, you will have a number of partitions missed out by this set of tests. To cover the remaining partitions with additional tests, if $b_t$ is small the additional tests will look like test for partitions into $k-1$ blocks of $n-c$ for $c$ not equal to any $b_t$.

You will thus either need $o(n)$ tests for $T(1)$ for the given $n$ and $k$, or you will step down to the situation for $n-c$ and $k-1$. I leave it to you to figure out how small $c$ can be to prove what you want and still keep $n- c >> k-1$, iterating all the way down of course. You may be able to get $\Omega(kn^{1- \epsilon})$ at least.

Gerhard "Ask Me About System Design" Paseman, 2011.12.08

share|improve this answer
    
@Gerhard: Thanks for pointing to my stupid a mistake in the number of partitions! (Have now corrected.) Case of $T(1)$: to keep $n-c\gg k-1$ is not a problem because we have a freedom to choose $n$ much larger than $k$. The problem is that we may have so many different numbers $n-c$ to partition into $k-1$ parts. –  Stasys Dec 8 '11 at 18:32
    
For $\Omega$ estimates, that's not a problem: that's an advantage. Good luck in using it. Gerhard "You Can Ignore Some Numbers" Paseman, 2011.12.08 –  Gerhard Paseman Dec 8 '11 at 18:39
    
If I thought it would do any good, I would repeat my previous comment. I can only suggest that if for one number c, you can show \Omega(n^(1-\epsilon)) many cases, then that lower bound should hold for $n$. Gerhard "Hoping More Words Aids Clarity" Paseman, 2011.12.08 –  Gerhard Paseman Dec 8 '11 at 19:11
add comment

Sorry for writing this as an answer. I am new here, all "comment" or "edit" buttons somehow disappeared after a short time. @Gerhard: I am sorry for a duplicated comment (haven't found any possibility to remove it or at least to excuse). Also, I cannot upvote your answer (too few points). Not a lucky start ...


Concerning the simplest case $r=1$, I think that Gerhard's observation even yields $T(1)\geq n+1$ by simple induction. To parametrize the problem, let $t_p(m)$ denote the smallest number of $1$-tests covering all partitions of $m$ into $p$ parts. Hence, in my previous notation, $T(1)=t_k(n)$. We will prove $t_k(n)\geq n+1$ by induction on $n$ and $k$. Basis case $t_1(n)= n+1$ trivially holds. For the induction step, fix a smallest set of tests achieving $t_k(n)$, and let $c$ be the smallest number not used as a threshold in the $k$-th of these tests. Then all partitions of $n-c$ into $k-1$ parts must be covered by the remaining tests. Since the $k$-th block must already have at least $c$ tests, induction hypothesis yields the desired lower bound $t_k(n)\geq c +t_{k-1}(n-c)\geq c + (n-c)+1=n+1$.
Can something similar work for $r\geq 2$, when we have overlapping supports?

share|improve this answer
    
You have two accounts now because of losing a browser cookie or something. For T(2) you should by a similar argument get something like n - 2k as a lower bound, by grouping variables into pairs. You may get something better by making better use of the information, but I think you have your result for n > k^2. You can ask a moderator about merging accounts. Gerhard "Ask Me About System Design" Paseman, 2011.12.09 –  Gerhard Paseman Dec 9 '11 at 10:02
    
Actually, the induction above seems to yield $T(1)\geq n+1$, because the $k$-th block of tests must have at least $c$ (not just $c-1$) thresholds (we have $0$ in our domain; sorry, have overseen this). Since now the bound does not depend on $k$, this also yields $T(r)\geq n+1$ in the case when the supports of $r$-tests form a decomposition of $[n]$ into $p=k/r$ subsets: this corresponds to partitions of $n$ into $p$ blocks, and we can use $T(1)$. The case of overlapping supports may, however, be harder. –  Stasys Dec 9 '11 at 14:32
    
P.S. I edited my "answer-commment" accordingly: replaced $T(1)\geq n-k$ by $T(1)\geq n+1$. I also asked moderators to merge my two accounts (thanks for a hint!). –  Stasys Dec 9 '11 at 16:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.