Say that a set $S \subset \mathbb Z^+$ can *express* $n$ if there is some way to add elements of $S$ (possibly more than once) to equal $n$. Call $S$ *critical* if moreover no proper subset of $S$ can express $n$.


For instance, $\{3,4\}$ is critical for $n=11$, because $3+4+4=11$, but $11$ is not a multiple of $3$ or $4$.


Given $n$, what is the maximum size of a critical set? Call this number $u\_n$.


Observe that if $S$ is a critical set for $n$, then $\{2n+1\}\cup\{2k \mid k \in S\}$ is critical for $4n+1$. [1] So the growth rate for $u\_n$ is at least logarithmic.


I hypothesise that $u\_n = \Theta(\log n)$. In fact, it seems to be that $u\_n \sim \ln n$. How does one prove that $u\_n = \Theta(\log n)$ (assuming that it's true)?




---


[1] - Proof: Clearly, $S' = \{2n+1\}\cup\{2k \mid k \in S\}$ can express $4n+1$. We see that we must use $2n+1$ at least once to do this, as the other elements of $S'$ are all even. What's left is to express $2n$. We can't use $2n+1$ to do this as it's greater than $2n$. So we use what's left of $S'$, which is $\{2k \mid k \in S\}$, and we see that it's critical for $2n$. QED


Erratum: The claim in [1] was previously that $S' = \{n+1\}\cup\{2k \mid k \in S\}$ was critical for $3n+1$.



Maximum size of a critical set that sums to $n$
It seems that $u\_n\sim \log\_2 n$.


To show that $2^{u\_n}\leq n+1$, notice that the sums of all subsets of a critical set $S\_n$ are distinct and do not exceed $n$. Indeed, if two subsets have the same sum, we may assume they are disjoint. Then we may use this equality to get rid of one of their elements in a representation of $n$.


The converse estimate is similar to the approach to a question I mentioned in a comment, with some technicalities.


Assume that $n\geq t^32^t$, so that $t\sim \log\_2n$. Choose $k\leq t$ such that $k$ is coprime with $2^k-1$ (we may achieve $k\sim t$ even by choosing a prime $k$). Let $ 1\leq a\leq k$ satisfy $b=(2^k-1)a\equiv n\pmod k$; notice that $b<t2^t$. Finally, set $D=(n-b)/k>(k-1)k2^k$.


We claim that the set 
$$
 S=\{D+a2^i\colon 0\leq i<k\}
$$
fits. The sum of elements in $S$ is $kD+b=n$, and we claim this to be the unique representation of $n$ as a sum of elements from $S$.


Indeed, consider any such sum. If it contains less than $k$ elements, the sum does not exceed $(k-1)(D+a2^k)<kD<n$. Similarly, if the representation contains more than $k$ summands, the sum is greater than $(k+1)D>kD+k2^k>n$. So the sum contains exactly $k$ summands. Subtracting $kD$ and dividing by $a$, we get a representation of $2^k-1$ as a sum of $k$ powers of $2$ which is unique.


