I'm having a look at this paper http://arxiv-web3.library.cornell.edu/pdf/0903.3048v1.pdf namely Theorem 5 and why it implies Theorem 2 immediately.
Basically, I'm hoping somebody could explain to me, why, for $k$ large, that if $k \le m^{\frac{1+\log_{2} m}{2}}(1+o(1))$, then this immediately implies that $m \ge 2^{\sqrt{2\log_{2} k}(1+o(1))}$.
I can't seem to rearrange this as it gets far too messy. Any help hugely appreciated!
Without going into too much detail:
Taking logs, $$ \log_2k\le\frac{1+\log_2m}{2}\log_2m+\underbrace{\log_2(1+o(1))}_{o(1)}\le\frac{(\log_2m) ^2}{2}(1+o(1))$$ (the latter estimate is quite rough). From this $$(\log_2m) ^2\ge2\log_2k(1+o(1)).$$ Take the square root and exponentiate, and you're done. (The final $o(1)$ term will be negative, so it could seem more natural to write $(1-o(1))$ on the right.)