Time complexity of PPZ algorithm

I am trying to understand PPZ (Paturi, Pudlák, Zane) derandomization algorithm for k-SAT, it seems to be very difficult for me. The last line in the below of the image, I don't understand the time complexity.

My question is how to get at most $$\widetilde{O}(2^{n(1−c_k)})$$ time for $$c_k = \frac{1}{2k} − o(\frac{1}{2})$$, where the asymptotics in $$o(. . .)$$ is when $$k\to\infty$$?

Details of the note is here. Above image is 1.3 section of this PDF.

$$\let\ep\varepsilon$$Note that the stated estimate $$\tilde O\bigl(2^{H(\ep)n}\bigr)$$ on the volume of the Hamming ball only holds for $$\ep\le1/2$$ (for $$\ep\ge1/2$$, it stays $$\Theta(2^n)$$). As the paper says, in order to optimize the sum, a good choice is $$\ep\le1/2$$ such that $$H(\ep)=1-\ep/k$$.
For $$k$$ large, this is close to $$1$$, and $$H(\ep)$$ is close to $$1$$ for $$\ep$$ close to $$1/2$$. Thus, write $$\ep=\frac12(1-\delta)$$, $$\delta\ge0$$, and compute the asymptotics of $$H(\ep)$$ for small $$\delta$$: \begin{align*} H(\ep)&=\ep\bigl(1-\log(1-\delta)\bigr)+(1-\ep)\bigl(1-\log(1+\delta)\bigr)\\ &=1+\ep\bigl(\delta+\tfrac12\delta^2+O(\delta^3)\bigr)\log e+(1-\ep)\bigl(-\delta+\tfrac12\delta^2+O(\delta^3)\bigr)\log e\\ &=1-(1-2\ep)\delta\log e+\tfrac12\delta^2\log e+O(\delta^3)\\ &=1-\frac{\log e}2\delta^2+O(\delta^3). \end{align*} The equation $$H(\ep)=1-\ep/k$$ becomes $$1-\frac{\log e}2\delta^2(1+O(\delta))=1-\frac1{2k}(1+O(\delta)),$$ thus $$\delta=\frac1{\sqrt{k\log e}}(1+O(\delta))$$, which solves to $$\delta=\frac1{\sqrt{k\log e}}+O(k^{-1}).$$ Plugging this back, $$\ep$$ satisfies $$H(\ep)=1-\frac\ep k=1-\frac1{2k}+\frac1{2k^{3/2}\sqrt{\log e}}+O(k^{-2}).$$ So, we get $$c_k=\frac1{2k}-\frac1{2k^{3/2}\sqrt{\log e}}+O(k^{-2}).$$
• I’m not sure I understand your comment. This is the asymptotic expansion of $\log(1-\delta)$ up to $O(\delta^3)$; I could have used more terms to get a more precise estimate, but this is enough for the basic bound on $c_k$. Jan 26 at 12:56
• You write, $$1-\frac{\log e}2\delta^2(1+O(\delta))=1-\frac1{2k}(1+O(\delta)),$$, it should be $$1-\frac{\log e}2\delta^2(1-O(\delta))=1-\frac1{2k}(1-O(\delta)),$$? Jan 26 at 14:10
• The two $O(\delta)$ functions on each side are different, of course, hence you can't cancel them. E.g., we have $(1+x)(1+O(x))=(1+2x)(1+O(x))$, but not $x=2x$. Jan 26 at 15:57
• I’m sorry, but I don’t have the time to teach you basic algebraic manipulation with O(...). I subtracted $1$ from both sides, multiplied the equation by $-2/\log e$, divided it by the $1+O(1)$ function from the LHS to get $\delta^2=\frac1{k\log e}(1+O(1))$, and took a square root. This all works because $(1+x)^{-1}=1+O(x)$, $(1+x)(1+y)=1+O(|x|+|y|)$, and $\sqrt{1+x}=1+O(x)$. To solve $\delta=\frac1{\sqrt{k\log e}}(1+O(\delta))$, it is perhaps easiest to do it in two steps: first $\delta$ is a priori bounded, hence weakening the RHS, the equation implies $\delta=O(k^{-1/2})$. Then plug ... Jan 30 at 14:21
• ... this bound to the RHS again to get $\delta=\frac1{\sqrt{k\log e}}(1+O(k^{-1/2}))=\frac1{\sqrt{k\log e}}+O(k^{-1})$. Jan 30 at 14:23