have $$\begin{aligned}
            A+BM &=\frac{A(N-M)+(A+BN)M}{N} \leq 0. 
        \end{aligned}$$ Obviously $R^*\geq 0$, hence we have $A+BM\leq R^*$.

Combining the above two cases, we have proved that the memory-rate pair $(M,R^*)$ is lower bounded by the lower convex envelope of $\mathcal{S}_{\textup{Lower}}\cup \{({0,J})\}$. This completes the proof of Step $1$.

For Step $2$, we only need to prove that the ratio of $R_{\textup{u}}(N,K,r)$ to the lower convex envelope of $\mathcal{S}_{\textup{Lower}}\cup \{({0,J})\}$ is at most $2.00884$. As mentioned at the beginning of this proof, given that the upper bound $R_{\textup{u}}(N,K,r)$ is convex,[^14] this ratio can only be maximized at the corner points of the envelope, which is a subset of $\mathcal{S}_{\textup{Lower}}\cup \{({0,J})\}$. Hence, we only need to check that $R_{\textup{u}}(N,K,r)\leq 2.00884 R$ holds for any $(M,R)\in \mathcal{S}_{\textup{Lower}}\cup \{({0,J})\}$.

To further simplify the problem, we upper bound $R_{\textup{u}}(N,K,r)$ using the following inequality, which can be easily proved using the results of [@yu2016exact]:[^15] $$\label{eq:decdef}
            R_\textup{u} (N,K,r)\leq R_{\textup{dec}}(M)\triangleq\frac{N-M}{M} (1-(1-\frac{M}{N})^J).$$ Consequently, to prove inequality (\[eq:ru\]), it suffices to prove the following lemma.

\[lemma:decconst\] For any $(M,R)\in \mathcal{S}_{\textup{Lower}}\cup \{({0,J})\}$, we have ${R_{\textup{dec}}(M)} \leq  {2.00884}R$.

The proof of Lemma \[lemma:decconst\] can be found in Appendix \[app:proofdeclemma\]. Assuming its correctness, we have $R_{\textup{u}}(N,K,r)\leq 2.00884 R^*$ for all possible parameter values of $N$, 