  The second layer of $^4$He films adsorbed on a graphite substrate is an
excellent experimental platform to study the interplay between superfluid and
structural orders. Here, we report a rigid two-frequency torsional oscillator
study on the second layer as a function of temperature and $^4$He atomic
density. We find that the superfluid density is independent of frequency, which
can be interpreted as unequivocal evidence of genuine superfluidity. The phase
diagram established in this work reveals that a superfluid phase coexists with
hexatic density-wave correlation and a registered solid phase. This suggests
the second layer as a candidate for hosting two exotic quantum ground states:
the spatially modulated superfluid and supersolid phases, resulting from the
interplay between superfluid and structural orders.
