  We study "random surfaces," which are random real (or integer) valued
functions on Z^d. The laws are determined by convex, nearest neighbor,
difference potentials that are invariant under translation by a full-rank
sublattice L of Z^d; they include many discrete and continuous height models
(e.g., domino tilings, square ice, the harmonic crystal, the Ginzburg-Landau
grad-phi interface model, the linear solid-on-solid model) as special cases.
  A gradient phase is an L-ergodic gradient Gibbs measure with finite specific
free energy. A gradient phase is smooth if it is the gradient of an ordinary
Gibbs measure; otherwise it is rough. We prove a variational
principle--characterizing gradient phases of a given slope as minimizers of the
specific free energy--and an empirical measure large deviations principle (with
a unique rate function minimizer) for random surfaces on mesh approximations of
bounded domains.
  Using a geometric technique called "cluster swapping" (a variant of the
Swendsen-Wang update for Fortuin-Kasteleyn clusters), we also prove that the
surface tension is strictly convex and that if u is in the interior of the
space of finite-surface tension slopes, then there exists a minimal energy
gradient phase mu_u of slope u. This mu_u is always unique for real valued
random surfaces.
  In the discrete models, mu_u is unique if at least one of the following
holds: d is in {1, 2}, there exists a rough gradient phase of slope u, or u is
irrational. When d=2, the slopes of all smooth phases (a.k.a. crystal facets)
lie in the dual lattice of L.
