  This paper studies the caching system of multiple cache-enabled users with
random demands. Under nonuniform file popularity, we thoroughly characterize
the optimal uncoded cache placement structure for the coded caching scheme
(CCS). Formulating the cache placement as an optimization problem to minimize
the average delivery rate, we identify the file group structure in the optimal
solution. We show that, regardless of the file popularity distribution, there
are \emph{at most three file groups} in the optimal cache placement{, where
files within a group have the same cache placement}. We further characterize
the complete structure of the optimal cache placement and obtain the
closed-form solution in each of the three file group structures. A simple
algorithm is developed to obtain the final optimal cache placement by comparing
a set of candidate closed-form solutions computed in parallel. We provide
insight into the file groups formed by the optimal cache placement. The optimal
placement solution also indicates that coding between file groups may be
explored during delivery, in contrast to the existing suboptimal file grouping
schemes. Using the file group structure in the optimal cache placement for the
CCS, we propose a new information-theoretic converse bound for coded caching
that is tighter than the existing best one. Moreover, we characterize the file
subpacketization in the CCS with the optimal cache placement solution and show
that the maximum subpacketization level in the worst case scales as
$\mathcal{O}(2^K/\sqrt{K})$ for $K$ users.
