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

Area of Science:

• Statistical Mechanics
• Computational Physics
• Probability Theory

Background:

• Infinite translation-invariant systems are crucial in statistical mechanics.
• Understanding marginal distributions is key to characterizing system properties.
• The computational complexity of these systems is a significant challenge.

Purpose of the Study:

• To characterize the set of marginal distributions for 2D lattice systems.
• To solve the marginal membership problem for specific interaction ranges and variable types.
• To develop algorithms for computing minimum energy per site.

Main Methods:

• Analysis of marginal distributions in probability space.
• Identification of convex polytopes for small variable sets (d=2, 3).
• Development of exact and approximate algorithms for minimum energy calculation.

Main Results:

• Marginal distribution sets for nearest-neighbor (d=2,3) and next-to-nearest-neighbor (d=2) interactions form convex polytopes.
• Exact algorithms for minimum energy per site were devised for these cases.
• Undecidability was proven for exact energy computation in higher dimensions (nearest-neighbor interactions).
• For d>=2947, marginal distribution sets are not semi-algebraic, precluding semidefinite programming characterization.

Conclusions:

• The structure of marginal distributions simplifies significantly for small local variable sets, enabling exact solutions.
• Computational complexity increases dramatically with system size and dimensionality, leading to undecidable problems.
• Advanced mathematical structures (non-semi-algebraic sets) arise in larger systems, posing fundamental limits on analytical and computational approaches.