# Calculation on Sparsification and critical clauses in SAT

I followed from this question.

I need to prove, the final result $$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}.$$

But before prove the final result first I need to prove the $$s_k \leq (1 − d/k))s_{\infty}$$. This prove existed in the paper, On the Complexity of k-SAT by Russell Impagliazzo and Ramamohan Paturi, 374 page, Theorem 3.

In that paper, one calculation I am not able to understand, which is,

$$2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$$

,where $$h(\delta) \leq s_\infty/2$$ , $$d \approx s_{\infty}/(2e\log(2/s_{\infty}))$$ and, $$\epsilon$$ is arbitrarily small.

My question is how to get $$s_k \leq (1 − d/k))s_{\infty}$$ from the above inequality? If I plug the value of $$h(\delta)$$ and ignore the $$\epsilon$$ related terms, also unable to deduce $$s_k \leq (1 − d/k))s_{\infty}$$.

And my second question is that how to get final result $$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}$$ from $$s_k \leq (1 − d/k))s_{\infty}$$?

• Simultaneously cross-posted at mathoverflow.net/questions/463578/… . You were told many times before this is against the site rules. Feb 6 at 10:08
• @EmilJeřábek deleted in mathoverflow. Feb 6 at 10:25
• @EmilJeřábek please check my first part answer correct or not. If not please suggest me how to approach. And also please give me some suggestions for second part also. Feb 9 at 22:35
• I'm sorry, but I'm not your personal tutor, and these basic calculations are not appropriate for this site, which is for research-level questions. You should post such questions at math.stackexchange.com or cs.stackexchange.com . Feb 10 at 8:57

First part:

$$2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$$

$$\implies2^{(s_\infty/2)n} + 2^{(s_k+ \epsilon)(1-(\delta/ek))n +\epsilon n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$$

$$\implies 2^{(s_k+ \epsilon)(1-(\delta/ek))n +\epsilon n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}-2^{(s_\infty/2)n}\approx 2^{(s_\infty(1-d/k)+2\epsilon)n}$$

$$\implies 2^{(s_k+ \epsilon)}\leq 2^{(s_\infty(1-d/k)} (\because (1-(\delta/ek)) \approx 1 \space \text {and} \space \epsilon \space \text {is arbitrarily small})$$

$$\implies s_k \leq s_\infty(1-d/k)$$

Second part:

Since in that paper mentioned, $$d \approx s_{\infty}/(2e\log(2/s_{\infty}))$$ and we are given from first part $$s_k \leq s_\infty(1-d/k)$$, how to get $$s_k \leq (1 − \Omega(k^{−1}))s_{\infty}$$? Need anybody's help.

• I really have no idea what goes in your mind wrt the second part. Since $d$ is a constant, $s_k\le s_\infty(1-d/k)$ means $s_k\le s_\infty(1-\Omega(k^{-1}))$ directly from the definition of $\Omega$, there is nothing to prove here. Feb 10 at 9:01