  One of the main methods for protecting quantum information against
decoherence is to encode information in the ground subspace (or the low energy
sector) of a Hamiltonian with a large energy gap which penalizes errors from
environment. The protecting Hamiltonian is chosen such that its degenerate
ground subspace is an error detecting code for the errors caused by the
interaction with the environment. We consider environments with arbitrary
number of local sites, e.g. spins, whose interactions among themselves are
local and bounded. Then, assuming the system is interacting with a finite
number of sites in the environment, we prove that, up to second order with
respect to the coupling constant, decoherence and relaxation are suppressed by
a factor which grows exponentially fast with the ratio of energy penalty to the
norm of local interactions in the environment. The state may, however, still
evolve unitarily inside the code subspace due to the Lamb shift effect. In the
context of adiabatic quantum computation, this means that the evolution inside
the code subspace is effectively governed by a renormalized Hamiltonian. The
result is derived from first principles, without use of master equations or
their assumptions, and holds even in the infinite temperature limit. We also
prove that unbounded or non-local interactions in the environment at sites far
from the system do not considerably modify the exponential suppression. Our
main technical tool is a new bound on the decay of power spectral density at
high frequencies for local observables and many-body Hamiltonians with bounded
and local interactions in a neighborhood around the support of the observable.
