10
$\begingroup$

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

$\endgroup$
1

4 Answers 4

4
$\begingroup$

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

$\endgroup$
1
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

Possible OEIS candidate, whose description sounds promising: A115981

$\endgroup$
2
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.