**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)$.
- $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)$.
- $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!











How local the property of "being a partition" is?
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 


