We develop an analytic approach for the study of lattice heteropolymers and apply it to copolymers with correlated Markovian sequences. According to our analysis, heteropolymers present three different dense phases depending upon the temperature, the nature of the monomer interactions, and the sequence correlations: (i) a liquid phase, (ii) a "soft glass" phase, and (iii) a "frozen glass" phase. The presence of the intermediate "soft glass" phase is predicted, for instance, in the case of polyampholytes with sequences that favor the alternation of monomers. Our approach is based on the cavity method, a refined Bethe-Peierls approximation adapted to frustrated systems. It amounts to a mean-field treatment in which the nearest-neighbor correlations, which are crucial in the dense phases of heteropolymers, are handled exactly. This approach is powerful and versatile; it can be improved systematically and generalized to other polymeric systems.(C) 2004 American Institute of Physics.