MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Say that $m$ is the additive dimension of $n\in\Bbb N$, and write $m=\operatorname{ad}n$, if $m$ is the greatest integer for which there is an irredundant $m$-element set $M\subset\Bbb N$ that provides a partition of $n$ uniquely: namely $$n=k_1+\cdots+k_r\quad\text{with}\quad\{k_i:i=1,...,r\}=M,$$ for some $r\in\Bbb N$, where no other partition of $n$ involves only elements of $M$.

As an illustration, take $n=34$. We can choose $M=\{7,8,12\}$ (for example) in this case, with $34=7+7+8+12$, and so $\operatorname{ad}34=3$, since no other partition of $34$ can be formed from the elements of $M$, while any $4$-element set providing a partition of $34$ has a proper subset that does so too. (The last claim entails some checking.)

Note that $\operatorname{ad}0=0$; $\operatorname{ad}n=1$ for $n=1,2,3,4,6$; $\operatorname{ad}n=2$ for $n=5$ and $n=7,...,16$; and $\operatorname{ad}17=3$ (take $M=\{4,6,7\}$). Thus $17$ is the least integer of additive dimension $3$.

What is the least integer of additive dimension $4$? Further, what is the asymptotic behaviour of $\operatorname{ad}n$ as $n$ becomes large?

(This question was earlier posted on MathStackExchange but was not answered.)

share|cite|improve this question
Earlier post was… – Gerry Myerson Apr 8 '14 at 12:38

I wrote a quick and probably impressively sub-optimal computer program to investigate this. It takes two seconds to ascertain that the least integer of additive dimension at least 4 is 49. The relevant partition is $15+14+12+8$.

(I say "at least 4" because I haven't checked that it doesn't in fact have additive dimension 5.)

share|cite|improve this answer
More a bet than a guess: the next one is $129=16+24+28+30+31$, and the numbers are $(n-1)2^n+1$ :) – მამუკა ჯიბლაძე Apr 8 '14 at 12:18

Let me prove that $A_n=(n-1)2^n+1$ has additive dimension $n$, with corresponding set $M=\{2^n-2^i\colon 0\leq i\leq n-1\}$ and representation $A_n=\sum M$.

Assume that $A_n=k_1+\dots+k_r$ is some representation with $k_i\in M$. Since $k_i< 2^n$ we have $r\geq n$. Let $k_i=2^n-2^{d_i}$; then $\sum_i 2^{d_i}=(2^n-1)+(r-n)2^n$.

Lemma. If $\sum_i 2^{d_i}\equiv -1\pmod{2^k}$, then $|\{i\colon d_i<k\}|\geq k$.

Proof. If we have some equal $d_i$'s, replace them by one number $d_i+1$ with no effect to the mentioned sum. When this process stops, we have exactly one $d_i$ equal to each of $0,1,\dots,k-1$. It remains to notice that $|\{i\colon d_i<n\}|$ does not increase during the process. The lemma is proved.

Finally, the lemma inductively yields that the sum of $k\leq n$ least elements in the list $2^{d_1},\dots,2^{d_r}$ does not exceed $2^k-1$. Thus $\sum_i2^{d_i}\leq 2^n-1+(r-n)2^{n-1}$. Comparing this bound with the value found above we conclude that $n=r$, and the $d_i$ form a permutation of $\{0,1,\dots,n-1\}$, as required.

ADDENDUM. On the other hand, the least number in uniquely representing set $M$ of cardinality $n$ is at least $2^{n-1}$, so the least number of aditive dimension $n$ should be greater than $n2^{n-1}$.

To prove this, set $a=\min M$, $M'=M\setminus\{a\}$, and let $S$ be the set of subset sums of $M'$. Clearly, all such sums are distinct (otherwise we would obtain a different representation by replacing one subsum by another). Moreover, all the sets $S+ka$, $k=0,1,\dots$, are disjoint; otherwise we would have $s'=s+ka$ for some $s,s'\in S$, and we would be able to replace $s'$ by $s+ka$. Since $|S|=2^{n-1}$, the density argument shows that $a\geq 2^{n-1}$.

Perhaps, this argument can be extended to other elements of $M$?

share|cite|improve this answer

Possible OEIS candidate, whose description sounds promising: A115981

share|cite|improve this answer

Theorem: For n, $M_n:=(n-1)2^n+1$ is an upper bound.

As an example take $n=4$. now let $$ \begin{aligned} k_1 & := 8 & = 1000 b \\ k_2 & := 12 & = 1100 b \\ k_3 & := 14 & = 1110 b \\ k_4 & := 15 & = 1111 b \\ \end{aligned} $$

The numbers on the right side are the binary representations of $k_i$

${k_1,k_2,k_3,k_4}$ is a unique partition for $M_4 = k_1+k_2+k_3+k_4 = 49$.

The cases 0 to 3 are already settled in the question. Proof for $n>3$ by induction:

Suppose there would be two different partitions

$$ (*) a_1k1+...+a_nk_n = b_1k1+...+b_nk_n = M_n $$

All factors $a_i$ and $b_i$ are lower than $k_1=2^{n-1}$, since otherwise $a_i*k_i\ge2^{2(n-1)}$, which exceeds $M_n=(n-1)2^n+1$ for all $n>3$. Equation $(*)$ also hold modulo $k_1=2^{n-1}$. This yields the same equation in the induction hypothesis (just drop the first binary digit!). As all coefficient are lower than the modulus, we have $a_i=b_i$ for $i>=2$. Then equation $(*)$ yields $a_1=b_1$ qed.

Conjecture: $M_n$ is already optimal for all $n$.


This proof is flawed! The induction hypothesis doesn't provide uniqueness mod $2^{n-1}$. Sorry!

share|cite|improve this answer

Your Answer


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.