the peak rate (i.e., inequalities (\[eq:ru\]) and (\[eq:lru\])) within this section. The proof for the average rate (i.e., inequalities (\[eq:ruave\]) and (\[eq:lruave\])) can be found in Appendix \[app:ave1\].

We start by proving the general factor-of-$2.00884$ characterization for inequality (\[eq:ru\]). Then we focus on the special case of $N\geq\frac{K(K+1)}{2}$ and prove inequality (\[eq:lru\]). As mentioned in Remark \[rem:ru\], the upper bounds of $R^*$ stated in Theorem \[th:gconst\] can be proved using the caching scheme provided in [@yu2016exact]. Hence, it suffices to prove the lower bounds of (\[eq:ru\]) and (\[eq:lru\]).

Proof of inequality (\[eq:ru\])
-------------------------------

The proof of inequality (\[eq:ru\]) consists of $2$ steps. In Step $1$, we first prove, assuming the correctness of Theorem \[th:general\], that the memory-rate pair $(M,R^*)$ is lower bounded by the lower convex envelope of a set of points in $\mathcal{S}_{\textup{Lower}}\cup \{({0,J})\}$, where $$\begin{aligned}
\label{def:sl}
        \mathcal{S}_{\textup{Lower}}=&\left\{(M,R)=\left(\frac{N-\ell+1}{s}, \frac{s-1}{2}+\frac{\ell(\ell-1)}{2s}\right)\ \right| \nonumber\\ &s\in\{1,...,J\}, \ell\in\{1,...,s\} \left.\vphantom{(M,R)=\left(\frac{N-\ell+1}{s}, \frac{s-1}{2}+\frac{\ell(\ell-1)}{2s}\right)}\right\}
        \end{aligned}$$ where $J=\min\{N,K\}$, given parameters $N$ and $K$. Then in Step $2$, we exploit the convexity of the upper bound $R_{\textup{u}}(N,K,r)$, and prove that it is within a factor of $2.00884$ from the above converse by checking all the corner points of the envelope.

For Step $1$, we first prove that $R^*$ is lower 