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 ($d=2,3$) distributions and nearest and next-to-nearest neighbors ($d=2$) distributions. 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 a number of 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≥ 5457$, the set of nearest-neighbor marginal distributions is not described by any linear or semidefinite program with an input of algebraic numbers. For $d\gtrsim 10^{12}$, the boundary of the set contains both flat and smoothly curved surfaces and cannot be characterized with a finite set of polynomial inequalities. ; Comment: 32 pages, 5 figures. This work was not funded by the European Research Council