  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$). Remarkably, 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 above. For variables of a higher (but finite)
dimensionality, we prove two no-go results. To begin, the exact computation of
the energy per site of arbitrary TI Hamiltonians with only nearest-neighbor
interactions is an undecidable problem. In addition, in scenarios with $d\geq
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.
