  The most momentous requirement a quantum theory of gravity must satisfy is
Background Independence, necessitating in particular an ab initio derivation of
the arena all non-gravitational physics takes place in, namely spacetime. Using
the background field technique, this requirement translates into the condition
of an unbroken split-symmetry connecting the (quantized) metric fluctuations to
the (classical) background metric. If the regularization scheme used violates
split-symmetry during the quantization process it is mandatory to restore it in
the end at the level of observable physics. In this paper we present a detailed
investigation of split-symmetry breaking and restoration within the Effective
Average Action (EAA) approach to Quantum Einstein Gravity (QEG) with a special
emphasis on the Asymptotic Safety conjecture. In particular we demonstrate for
the first time in a non-trivial setting that the two key requirements of
Background Independence and Asymptotic Safety can be satisfied simultaneously.
Carefully disentangling fluctuation and background fields, we employ a
`bi-metric' ansatz for the EAA and project the flow generated by its functional
renormalization group equation on a truncated theory space spanned by two
separate Einstein-Hilbert actions for the dynamical and the background metric,
respectively. A new powerful method is used to derive the corresponding
renormalization group (RG) equations for the Newton- and cosmological constant,
both in the dynamical and the background sector. We classify and analyze their
solutions in detail, determine their fixed point structure, and identify an
attractor mechanism which turns out instrumental in the split-symmetry
restoration. We show that there exists a subset of RG trajectories which are
both asymptotically safe and split-symmetry restoring. We conclude that the
next generation of truncations must be bi-metric.
