Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
    
Earlier post was math.stackexchange.com/questions/661256/… –  Gerry Myerson Apr 8 at 12:38
add comment

3 Answers 3

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|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 at 12:18
add comment

Possible OEIS candidate, whose description sounds promising: A115981

share|improve this answer
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

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.