2
$\begingroup$

For integers $n \ge 0$ and $k \ge 2$, define $E^k_n$ as the set of tuples $b \in \{0,\ldots, k\}^{\log n}$, such that $n = \sum_{0 \le i \le \log n} b_i 2 ^i.$

Note that the only element of $E^1_n$ is simply $n$ in base $2$.

Clearly $|E^k_n| \le k^{\log n} = n^{\log k}$, but what is a better, ideally tight, upperbound?

My guess is that $n^{\frac{\log k}{\log \log n} }$ is an upperbound.

$\endgroup$
3
  • 4
    $\begingroup$ $\log n$ is not an integer (for $n\ne1$). So, what does $\{\,0,\dots,k\,\}^{\log n}$ mean? $\endgroup$ Commented Jul 5, 2019 at 23:15
  • $\begingroup$ Well, at least in theoretical computer science, by convention, logarithms are rounded down. $\endgroup$ Commented May 3, 2020 at 8:44
  • $\begingroup$ Any thoughts about the answer that Greg posted last year? $\endgroup$ Commented May 3, 2020 at 9:16

1 Answer 1

2
$\begingroup$

Here is an answer for certain values of $k$, which disproves your guess and suggests an alternate conjecture.

Suppose that $k=2^\ell-1$ for some $\ell\ge2$. Then each digit $b_i$ can be written uniquely in binary: $b_i = \sum_{j=0}^{\ell-1} a_{i,j}2^j$ with each $a_{i,j}\in\{0,1\}$. Thus $$ \sum_{0\le i\le \log n} b_i 2^i = \sum_{0\le i\le \log n} \sum_{j=0}^{\ell-1} a_{i,j}2^j 2^i = \sum_{j=0}^{\ell-1} 2^j \sum_{0\le i\le \log n} a_{i,j} 2^i. $$ But note that for fixed $j$, the inner sum simply equals every integer between $0$ and $2^{\log n+1}-1$ once each. In particular, the number of solutions to $$ n = \sum_{0\le i\le \log n} b_i 2^i $$ is the same as the number of solutions to $$ n = \sum_{j=0}^{\ell-1} 2^j m_j $$ with each $0\le m_j < 2^{\log n+1}$. The number of such solutions is easy to work out asymptotically; if I made no mistakes, the answer is approximately \begin{align*} \frac{n^{\ell-1}}{(\ell-1)!2^{\ell(\ell-1)/2}} &= \frac{n^{\log_2(k+1)-1}}{(\log_2(k+1)-1)!2^{\log_2(k+1)(\log_2(k+1)-1)/2}}. \end{align*} Since the denominator doesn't depend on $n$, this shows that for these values of $k$, the function grows faster than $n^{(\log k)/\log\log n}$.

My suspicion is that the correct rate of growth is something like $n^{\log_2 k - 1}$ for all $k$. (The $n^{-1}$ factor makes sense since there are $kn$ possible values for the sum and we want to single out one of them.)

$\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.