# 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

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!

-