improves upon the communication rates achieved by [@maddah-ali12a] (and its relaxed version in [@maddah-ali13]), which was relied on by all the above works (i.e., [@niesen13; @ghasemi15; @lim2016information; @sengupta15; @DBLP:journals/corr/WangLG16]). It also achieves the exact optimum communication rates among all caching schemes with uncoded prefetching, for all possible values of $N$, $K$, and $M$. As a shorthand notation, we denote the peak and average rates achieved in [@yu2016exact] by $R_{\textup{u}}(N,K,r)$ and $R_{\textup{u,ave}}(N,K,r)$, respectively.[^8] More precisely, we define these functions as follows.

\[def\] Given problem parameters $N$, $K$, $M$, and $r=\frac{KM}{N}$, we define $$\begin{aligned}
                    R_{\textup{u}}(N,K,r)&=
                \frac{\binom{K}{r+1}-\binom{K-\min\{K,N\}}{r+1}}{\binom{K}{r}},\label{eq:rudef}\\
                    R_{\textup{u,ave}}(N,K,r)&=\mathbb{E}_{\boldsymbol{d}}\left[
        \frac{\binom{K}{r+1}-\binom{K-N_{\textup{e}}(\boldsymbol{d})}{r+1}}{\binom{K}{r}}\right]\label{eq:arudef}
            \end{aligned}$$ for $r\in \{0,...,K\}$, where $\boldsymbol{d}$ is uniformly random in $\mathcal{D}=\{1,...,N\}^K$, and $N_{\textup{e}}(\boldsymbol{d})$ denotes the number of distinct requests in $\boldsymbol{d}$.[^9] Furthermore, for general (non-integer) $r\in[0,K]$, $R_{\textup{u}}(N,K,r)$ and $R_{\textup{u,ave}}(N,K,r)$ are defined as the lower convex envelope of their values at $ r\in\{0,1,...,K\}$, respectively. Specifically, for any non-integer $r\in[0,K]$, we have[^10] $$\begin{aligned}
                R_{\textup{u}}(N,K,r)&=\nonumber\\
                (r-\lfloor r\rfloor)& R_{\textup{u}}(N,K,\lceil r\rceil)+(\lceil r\rceil-r)  R_{\textup{u}}(N,K,\lfloor r\rfloor),\label{eq:genrudef}\\
                    R_{\textup{u,ave}}(N,K,r)&=\nonumber\\(r-\lfloor r\rfloor)& R_{\textup{u,ave}}(N,K,\lceil r\rceil)+(\lceil r\rceil-r)  R_{\textup{u,ave}}(N,K,\lfloor r\rfloor).\label{eq:genarudef}
            \end{aligned}$$

Given the above upper bounds, we develop improved converse bounds in this paper, which provides better characterizations for both the peak rate and the average rate.

Main Results {#sec:main}
============

We summarize our main results in the 