How local the property of "being a partition" is?

Question

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!

Answer 1

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

Answer 2

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?