Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems

We study the properties of the set of marginal distributions of infinite translation-invariant systems in the 2D square lattice. In cases where the local variables can only take a small number d of possible values, we completely solve the marginal or membership problem for nearest-neighbors distributions (d=2,3) and nearest and next-to-nearest neighbors distributions (d=2). All these sets form convex polytopes in probability space. This allows us to devise an algorithm to compute the minimum energy per site of any TI Hamiltonian in these scenarios exactly. We also devise a simple algorithm to approximate the minimum energy per site up to arbitrary accuracy for the cases not covered. For variables of a higher (but finite) dimensionality, we prove two no-go results. The exact computation of the energy per site of arbitrary TI Hamiltonians with only nearest-neighbor interactions is undecidable. In addition, in scenarios with d≧2947, the boundary of the set of nearest-neighbor marginal distributions contains both flat and smoothly curved surfaces and the set itself is not semi-algebraic. This implies, in particular, that it cannot be characterized via semidefinite programming, even if we allow the input of the program to include polynomials of nearest-neighbor probabilities.