Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$.
Our question is:
$f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which one exactly holds?
(where $\log(n) = \lceil \log_2(n) \rceil$ is a function from $\mathbb N$ to $\mathbb N$.)
$\ $
This question arose when we intended to encode some sets as strings surjectively
Denote $[n] = \{0, 1, 2,\dotsc n-1\}$ and let $g(n) = \Theta(2^{\log^{k+1} \ (n)})$ be a function from $\mathbb N$ to $\mathbb N$.
We wonder whether there is a surjection from $\{S \mid S\subseteq [n] \text{ and } |S|\leq \log^k(n)\}$ to $\{0,1\}^{\leq g(n)}$, where $\{0,1\}^{\leq g(n)}$ is the set of binary strings of length no larger than $g(n)$
If $f(n) = o(2^{\log^{k+1} \ (n)})$, no such surjection exists.
If $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, we may choose a precise $g(n)$ to make the surjection possible.
