# What is the least integer of additive dimension 4?

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.)

-
Earlier post was math.stackexchange.com/questions/661256/… – 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.)

-
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$?

-

Possible OEIS candidate, whose description sounds promising: A115981

-

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$.

Edit

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

-