1

I am trying to show that $\log_2(2^{k^2-k}-(2^{k-1}-1)^k) = k^2-2k+o(k)$. This question is coming from this paper. On page 5 of the paper, after Conjecture 3.1, the authors discuss an example. I have computed the cardinality of that family $\mathcal A$ and it turns out to be $2^{k^2-k}-(2^{k-1}-1)^k$. But I am having some trouble computing the asymptotic relation claimed by them.

I guess one has to 'take out' $2^{k^2-2k}$ from the expression of $\mathcal A$, take $\log_2$ and show that the remaining function is $o(k)$ but this is not turning out to be an easy limit. Could someone please help me with this?

alephnot
  • 300

1 Answers1

3

Note that $$\begin{align}(2^{k-1}-1)^k&=2^{k(k-1)}-k2^{(k-1)^2}+\sum_{j=0}^{k-2}\binom{k}{j}2^{(k-1)j}(-1)^{k-j}\\ &=2^{k(k-1)}-k2^{(k-1)^2}+o(2^{(k-1)^2})\end{align}$$ because $$\left|\sum_{j=0}^{k-2}\binom{k}{j}2^{(k-1)j}(-1)^{k-j}\right|\leq \binom{k}{2}2^{(k-1)(k-2)}+2^{(k-1)(k-3)}\sum_{j=0}^{k-3}\binom{k}{j}\\<\binom{k}{2}2^{(k-1)(k-2)}+2^{(k-1)(k-3)+k}=o(2^{(k-1)^2}).$$ Hence $$\begin{align}\log_2(2^{k^2-k}-(2^{k-1}-1)^k) &= \log_2(k2^{(k-1)^2}+o(2^{(k-1)^2}))\\ &=\log_2(2^{(k-1)^2}(k+o(1)))\\ &=(k-1)^2+o(k)=k^2-2k+o(k). \end{align}$$

Robert Z
  • 145,942
  • Note that $o(x)=xo(1)$. – Robert Z Aug 01 '21 at 09:55
  • Why are the remaining terms in the binomial expansion of $(2^{k-1}-1)^{k}, o(2^{(k-1)^2})$? I understand that they are polynomial divided by an exponential but there would terms of the type $\binom{k}{k/2}$. How would you deal with them? – alephnot Aug 01 '21 at 10:00
  • Also, why is $\log_2(k+o(1))=o(\log(k))$? – alephnot Aug 01 '21 at 10:13
  • @alephnot I edited my answer. Is it clear now? – Robert Z Aug 01 '21 at 10:16
  • Ah okay it is $o(k)$. Cool! Thank you so much; nice answer. I understood – alephnot Aug 01 '21 at 10:19
  • Since $2^{(k-1)(k-3)+k}=2^{k^2-3k+3+k}=2^{k^2-2k+3}$, I think you have to go one step further to $j=k-4$. – alephnot Aug 01 '21 at 10:59
  • $(k−1)(k−3)=k^2-4k+3$ – Robert Z Aug 01 '21 at 11:00
  • Haha, my bad! :) – alephnot Aug 01 '21 at 11:01
  • @Robert Z. Using your first formula $$\left( 1- \frac{1}{2^{k-1}} \right)^k=\left(2^{k-1}- 1\right)^k \frac{1}{2^{k(k-1)}} =\frac{1}{2^{k(k-1)}}\left[ 2^{k(k-1)}-k2^{(k-1)^2}+o(2^{(k-1)^2}) \right]= \ =1-\frac{k2^{(k-1)^2}}{2^{k(k-1)}}+o\left(\frac{k2^{(k-1)^2}}{2^{k(k-1)}}\right)=1-\frac{2k}{2^{k}}+o\left(\frac{2k}{2^{k}}\right)$$

    but you have $1-\frac{2k}{2^{k^2}}+o(\frac{2k}{2^{k^2}})$

     – zkutch Aug 02 '21 at 00:59
  • @zkutch Thanks for pointing out. You are correct! – Robert Z Aug 02 '21 at 07:11