Zizhu Wang and Miguel Navascués

# Two Dimensional Translation-Invariant Probability Distributions:
Approximations, Characterizations and No-Go Theorems

Zizhu Wang2,1 Miguel Navascués1 1 Institute for Quantum Optics and Quantum
Information (IQOQI) Vienna,
Austrian Academy of Sciences,
Boltzmanngasse 3, 1090 Vienna, Austria
2 Institute of Fundamental and Frontier Sciences,
University of Electronic Science and Technology of China,
Chengdu 610054, China<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction

The distribution of stars at large scales, the vacuum state of a quantum field
theory, the thermal state of any solvable spin model: these are examples of
systems with infinitely many sites where the description of a bounded
environment does not depend on its location within the lattice. We call this
property translation invariance (TI).

An agent exploring an infinite translation-invariant world would find that the
statistics of the local random variables which he can access are constrained
by the requirement of infinite TI. However, and despite a long history of
research on TI systems, driven by the needs of statistical physics (see, e.g.
[1]), it is far from clear what those constraints exactly are.

This conundrum is at the essence of the _TI MARGINAL problem_, where a number
of probability distributions of finitely-many variables are provided and the
task is to certify if they correspond to the marginals of a TI system.
MARGINAL arises naturally at the intersection of quantum information science
and condensed matter physics, when we try to determine whether the dynamical
structure factors of a large spin system are compatible with an underlying
Bell local quantum state [2].

ENERGY, the dual problem of computing the minimum energy per site of a
translation-invariant Hamiltonian, is also of special concern for the
mathematical physics community. While ENERGY is efficiently solvable in one
dimensional ($1D$) systems [3, 4, 5], in $2D$ very few solvable instances are
documented.

What do we know about MARGINAL or ENERGY in $2D$? Not much. We know that the
set of TI marginals is closed and convex [6, 5]. We also know that that the
problem of determining the existence of near-neighbor marginals of a TI
distribution with a given (finite) support is undecidable [7, 8, 4]. In [9]
the case where the random variables are dichotomic is studied and necessary
and sufficient conditions are provided for the existence of a TI extension,
given the _infinitely many_ marginal distributions of any $n$ lattice sites.
In [5] explicit examples of probability distributions for lattice sites within
a $2\times 2$ square are given which, despite satisfying all local symmetries
associated to TI, do not admit $2D$ TI extensions. Similar instances of $2D$
non-extendible distributions constructed from $3\times 3$ squares satisfying
additional rotation and reflection symmetries are also provided. In [6] the
approximability of the MARGINAL problem via convex polytopes is considered.

It is still open under which scenarios one can solve MARGINAL and ENERGY
exactly, or how to attack these problems numerically 111Brute-force
computational methods to decide Bell nonlocality in the simplest $2D$ TI
scenarios or to compute lower bounds on ground state energy densities soon
become intractable due to lack of computer memory.. Even the geometry of the
set of all marginal distributions of $2D$ TI systems remains a mystery: in
$1D$, the marginal distributions of the variables of finitely many sites of TI
systems form a convex polytope in the space of probabilities 222A convex
polytope is a convex set defined by a finite number of linear inequalities
[10, 11].. Should we expect this to hold in $2D$ systems as well?

Motivated by the desire of understanding the nature of quantum nonlocality in
$2D$ materials [2], in this paper we will considerably advance the above
fundamental questions. We will show that, in scenarios where the random
variables take a small number $d$ of possible values, the MARGINAL problem for
nearest-neighbor (for $d=2,3$) and next-to-nearest neighbor distributions (for
$d=2$) is exactly solvable. We also prove solvable a natural variant of
MARGINAL where the TI extension is also required to satisfy invariance under
reflection of the horizontal and vertical axes. An immediate consequence of
these results is that, in any of the above cases, it is possible to solve
ENERGY exactly. For the scenarios not covered above, we provide an algorithm
to approximate the set of TI marginals or solve the ENERGY problem up to
arbitrary precision.

On the negative side, we show that, for arbitrary TI Hamiltonians, ENERGY is
undecidable. We also prove that, contrary to the solvable cases, for local
random variables of high cardinality, the set of nearest-neighbor
distributions admitting a TI extension is no longer a convex polytope in the
space of probabilities or even a semi-algebraic set333A semi-algebraic set is
the union of finitely many regions of ${\mathbb{R}}^{n}$ defined by a finite
number of polynomial inequalities [12].. This implies, in particular, that
standard tools from convex optimization, such as linear programming [13] or
semidefinite programming [14] cannot be used to fully characterize Bell
nonlocality in large $2D$ condensed matter systems.

The structure of this paper is as follows: in Section 2 we will define and
list known properties of the set of marginal 2D TI distributions. We will
introduce the problems MARGINAL and ENERGY, and show how to solve their 1D
versions. We will also describe a simple symmetrization process that will play
an important role in the mathematical proofs to come. The remaining sections
present our original contributions. In Section 3 we will present a practical
algorithm to characterize the set of 2D marginals up to arbitrary accuracy.
Later, in Section 4, we will provide a few instances of the marginal problem
which are exactly solvable. In Section 5 we will prove two no-go theorems
about the set of 2D TI marginals, namely: (a) the problem of computing ENERGY
exactly is undecidable; (b) for random variables with support $d$ greater than
or equal to $2947$, the set of nearest-neighbor distributions is not a semi-
algebraic set.

##  2 The set of marginal 2D TI distributions: definition and known properties

Consider an infinite two-dimensional square lattice, and suppose that each
site $(x,y)\in{\mathbb{Z}}^{2}$ has access to a local random variable
$a_{x,y}$ that can take $d<\infty$ possible values. We will call $d$ the
_local dimension_ of the lattice. For any finite subset $K$ of
${\mathbb{Z}}^{2}$, we will assume that the variables
$a_{K}\equiv\\{a_{z}:z\in K\\}$ follow a probability distribution
$P_{K}(a_{K})$. We say that the system is translation-invariant (TI) if, for
any finite set $K$ and any vector $c\in{\mathbb{Z}}^{2}$,

$P_{K}=P_{K+c},$ (1)

where $K+c=\\{z:z-c\in K\\}$.

TI is a very common property in nature. It is satisfied approximately in large
crystal structures, and exactly by any stationary state in quantum field
theory. In addition, most exactly solvable models in statistical physics
comply with this symmetry in the thermodynamic limit of infinitely many sites.

In this paper we will consider a scenario where an agent conducts local
observations within an infinite 2D TI system. Intuitively, the condition of TI
means that the statistics of the variables within the immediate vicinity of
the agent do not give any clue about his position in the lattice. Our goal is
to determine how the statistics of such a sample are constrained by the
requirement that these variables arise from a 2D TI system.

Figure 1: An agent exploring his surroundings in an infinite TI lattice. In
the picture, the agent only has access to the random variables corresponding
to four nearby sites. How are the statistics of the corresponding four random
variables restricted by the TI condition?

With a slight abuse of notation, any function $P$ assigning probability
distributions $P_{K}(a_{K})$ to any finite set $K\subset{\mathbb{Z}}^{2}$
satisfying eq. (1) and the consistency conditions $\sum_{a_{L}}P_{K\cup
L}(a_{K},a_{L})=P_{K}(a_{K})$ for $K\cap L=\emptyset$ will be called a _2D TI
probability distribution_. Each of the distributions $P_{K}(a_{K})$ will be
denoted the _marginal_ of a 2D TI distribution, or simply a TI marginal. A few
special finite subsets of ${\mathbb{Z}}^{2}$ will appear frequently throughout
this article, so we will need special names for them. $v,h,+,-$, will denote,
respectively, the sets $\\{(0,0),(0,-1)\\}$, $\\{(0,0),(1,0)\\}$,
$\\{(0,0),(1,1)\\}$, $\\{(0,0),(1,-1)\\}$. The bi-variate distributions
$P_{h}(a,b)$, $P_{v}(a,b)$ ($P_{+}(a,b)$, $P_{-}(a,b)$) hence describe the
statistics between nearest neighbors (next-to-nearest neighbors). We will also
use $m\times n$ to describe the rectangle $\\{(x,y):0\leq x<m,0\leq y<n\\}$;
and $|m\times n|$, for $\\{(x,y):|x|<m,|y|<n\\}$. Finally, $1,...,n$ will
denote the set $\cup_{k=1}^{n}\\{(k,0)\\}$.

We will now introduce the two problems which will concern us through the rest
of the article.

######  Definition 1 (The TI MARGINAL problem).

Given a finite number of finite subsets of ${\mathbb{Z}}^{2}$, i.e.,
$\\{K_{i}\\}_{i=1}^{n}$, $|\cup_{i}K_{i}|<\infty$, and the probability
distributions $\\{Q_{i}(a_{K_{i}})\\}_{i}$, determine if there exists a 2D TI
distribution $P$ such that $P_{K_{i}}(a_{K_{i}})=Q(a_{K_{i}})$ for
$i=1,...,n$. In the affirmative case, the distribution $P$ will be called a
_TI extension_ of $\\{Q_{i}(a_{K_{i}})\\}_{i}$.

Figure 2: The 2D TI marginal problem. In the example, there is only one
region, $K=3\times 3$. A probability distribution $Q_{3\times 3}$ for the $9$
variables $\\{a_{i,j}:i,j=0,1,2\\}$ is given (the green square), and the
question is whether there exists a 2D TI system with a marginal probability
distribution $P_{3\times 3}$ (the yellow squares) equal to $Q_{3\times 3}$.

In the following, each configuration of cardinality $d<\infty$ and finite
subsets of ${\mathbb{Z}}^{2}$ $\\{K_{i}\\}_{i=1}^{n}$ will be called _a
scenario_. In any scenario, the set of TI marginals is convex and closed [5].

Sometimes, e.g., in statistical physics, we are not interested in solving the
marginal problem as much as in optimizing linear functionals over the set of
marginals of 2D TI distributions. This motivates the following problem:

######  Definition 2 (The ENERGY problem).

Given $\\{K_{i}\\}_{i=1}^{n}$, with $K_{i}\subset{\mathbb{Z}}^{2}$,
$|\cup_{i}K_{i}|<\infty$, and functions
$F_{i}:\\{0,\ldots,d-1\\}^{|K_{i}|}\to{\mathbb{R}}$, $i=1,...,n$, solve the
optimization problem

$\min_{P}\sum_{i=1}^{n}\sum_{a_{K_{i}}}F_{i}(a_{K_{i}})P_{K_{i}}(a_{K_{i}}),$
(2)

where the minimization is carried out over all TI distributions $P$.

The ENERGY problem is the dual of the MARGINAL problem: given an oracle to
solve one of them approximately, one can devise an algorithm that invokes the
oracle a polynomial number of times in order to solve the other problem with a
similar accuracy [15]. Given $\\{K_{i}\\}_{i=1}^{n}$ and the interactions
$\\{F_{i}\\}_{i=1}^{n}$, consider the family of (classical) 2D Hamiltonians of
the form

$H_{N}(a_{N\times N})=\sum_{\\{z:K_{i}+z\subset N\times N,\forall
i\\}}\sum_{i=1}^{n}\sum_{b=1}^{d^{|K_{i}|}}F_{i}(b)\delta(a_{K_{i}+z},b),$ (3)

where each Hamiltonian $H_{N}$ describes the finite lattice $N\times N$. The
_minimum energy per site_ of the infinite lattice is defined as
$\lim_{N\to\infty}\frac{1}{N^{2}}\min_{a_{N\times N}}H_{N}(a_{N\times N})$.
ENERGY takes its name from the observation that the minimum energy per site of
the infinite 2D TI Hamiltonian defined by the terms $\\{F_{i}\\}_{i=1}^{n}$
equals $\mbox{{ENERGY}}(\\{F_{i}\\})$. The reader can find a proof at the end
of this section.

As we will see, the TI marginal problem is very hard. However, there exists an
interesting variant whose solution turns out to be trivial.

######  Definition 3 (The MARGINAL problem in 1D).

Let $Q_{1,...,s}(a_{1},...,a_{s})$ be a probability distribution. Determine if
there exists a TI distribution $P$ such that
$P_{1,...,s}(a_{1},...,a_{s})=Q_{1,...,s}(a_{1},...,a_{s})$.

The solution of this problem is folklore among the community of condensed
matter physicists: a distribution $Q_{1,...,s}(a_{1},...,a_{s})$ admits a TI
extension iff $Q_{1,...,s-1}=Q_{2,...,s}$ [3, 4, 5].

Given an arbitrary distribution $Q_{K}$ (not necessarily a TI marginal) of
local variables over a large rectangle $K=m\times n$, one can derive a 2D TI
distribution $P$ such that $P_{s\times t}$ equals a spatial average of all the
$s\times t$ possible rectangles inside $K$ with a correction of the order
$O\left(\frac{\max(s,t)}{\min(m,n)}\right)$.

######  Definition 4 (The symmetrization procedure).

Given $Q_{K}$, define a distribution $\hat{P}$ over the whole plane by tiling
it with copies of the distribution $Q_{K}$. That is, for $K(i,j)\equiv
K+(mi,n,j)$,
$\hat{P}_{\cup_{ij}K(i,j)}(a_{\cup_{ij}K(i,j)})\equiv\prod_{i,j}Q_{K}(a_{K(i,j)})$.
Then, the TI distribution $P$ given by

$P_{K^{\prime}}\equiv\frac{1}{mn}\sum_{x=1}^{n}\sum_{y=1}^{m}\hat{P}_{K^{\prime}+(x,y)}$
(4)

will be called the _symmetrization_ of $Q$.

That $P$ is TI invariant can be seen by noting that $\hat{P}$ is invariant
under translations of $m$ ($n$) sites in the horizontal (vertical) axis.
Random translations of $\\{1,...,m\\}$ and $\\{1,...,n\\}$ sites in those axes
thus turn $\hat{P}$ into a 2D TI distribution.

It can be easily checked that

$\displaystyle
P_{h}=\frac{1}{(m-1)n}\sum_{x=0}^{m-2}\sum_{y=0}^{n-1}Q_{h+(x,y)}+O\left(\frac{1}{m}\right),$
$\displaystyle
P_{v}=\frac{1}{m(n-1)}\sum_{x=0}^{m-1}\sum_{y=0}^{n-2}Q_{v+(x,y)}+O\left(\frac{1}{n}\right).$
(5)

In general,

$\displaystyle P_{s\times t}=$
$\displaystyle\frac{1}{(m-s)(n-t)}\sum_{x=0}^{m-s-1}\sum_{y=0}^{n-t-1}Q_{s\times
t+(x,y)}+$
$\displaystyle+O\left(\frac{s}{m}\right)+O\left(\frac{t}{n}\right).$ (6)

Now we are ready to establish the equivalence between ENERGY and the
computation of the minimum energy per site of a local Hamiltonian. Suppose
that there exists a configuration $a_{{\mathbb{Z}}^{2}}$ of the square lattice
such that $\lim_{N\to\infty}H_{N}(a_{N\times N})/N^{2}=E$. Applying
symmetrization over the distribution $Q_{N\times N}(b)=\delta_{b,a_{N\times
N}}$, with energy-per-site $E_{N}$, one derives a 2D TI distribution $P$ with
$\sum_{i=1}^{n}\sum_{a_{K_{i}}}F_{i}(a_{K_{i}})P_{K_{i}}(a_{K_{i}})=E_{N}+O(1/N)$.
Taking the limit $N\to\infty$, we conclude that the energy value of any
configuration can be matched by a TI marginal. Conversely, given any 2D TI
distribution $P$ with
$\sum_{i=1}^{n}\sum_{a_{K_{i}}}F_{i}(a_{K_{i}})P_{K_{i}}(a_{K_{i}})=E$, for
any $N$ there exists, by convexity, an $N\times N$ square configuration
$a_{N\times N}$ with $P_{N\times N}(a_{N\times N})\not=0$ such that
$H_{N}(a_{N\times N})/N^{2}\leq E+O(1/N)$. It follows that the solutions of
both problems are equal.

##  3 Approximations of the set of TI marginals

In this section we will prove that, for any given scenario, the set of TI
marginals admits an approximate characterization up to arbitrary accuracy.

The symmetrization protocol suggests a simple (but expensive) converging
sequence of relaxations. Given $Q_{K}(a_{K})$, with $K=s\times t$, a necessary
condition for $Q_{K}(a_{K})$ to be a TI marginal is that $Q_{K}(a_{K})$ is the
marginal of a distribution $P^{(n)}$ over the square $n\times n$, subject to
the rules:

$\displaystyle P^{(n)}_{(n-1)\times n+(x,0)}=P^{(n)}_{(n-1)\times n},\mbox{
for }x=0,1,$ $\displaystyle
P^{(n)}_{n\times(n-1)+(0,y)}=P^{(n)}_{n\times(n-1)},\mbox{ for }y=0,1.$ (7)

Intuitively, $P^{(n)}$ is modeling the marginal for the region $n\times n$ of
an overall 2D TI distribution containing $Q_{K}$.

The verification can be carried out via linear programming [13]. Linear
programming is a branch of convex optimization concerned with the resolution
of problems of the form

$\displaystyle\max\bar{c}\cdot\bar{x},$ $\displaystyle\mbox{s.t.
}A\bar{x}\geq\bar{b},\bar{x}\geq 0.$ (8)

where $\bar{c}\in{\mathbb{R}}^{p}$, the $q\times p$ matrix $A$ and
$\bar{b}\in{\mathbb{R}}^{q}$ are the inputs of the problem;
$\bar{x}\in{\mathbb{R}}^{p}$ are the problem variables; and $\bar{s}\geq 0$ is
used to denote that all the components of the vector $\bar{s}$ are non-
negative.

For each (primal) linear program there exists a dual problem

$\displaystyle\min\bar{b}\cdot\bar{x},$ $\displaystyle\mbox{s.t.
}A^{T}\bar{y}\geq\bar{c},\bar{y}\geq 0.$ (9)

Remarkably, the solutions of both primal and dual problems coincide. Numerical
algorithms aimed at solving one problem hence run optimizations over the
primal and dual problems. This allows the solver to give rigorous upper and
lower bounds on the optimal solution. At present, there exist numerous free
software implementations of interior-point methods for linear programs [13,
16]. In addition, all linear programs can be solved exactly via the costly
Fourier-Motzkin elimination method [17].

In our case, we need the solver to verify that there exists a probability
distribution $P^{(n)}_{n\times n}$ for $n^{2}$ variables satisfying the linear
conditions (7), together with $P^{(n)}_{K}=Q_{K}$. This can be formulated as a
linear program by regarding each probability $P^{(n)}_{n\times n}(a_{K})$ as a
free variable, and choosing $A,b$ so that $P^{(n)}_{n\times n}(a_{K})$
satisfies the corresponding linear constraints. As for the objective function
to optimize, we can take $\bar{c}=0$, i.e., the solution of the primal linear
program will be zero provided that there exists a feasible point. If there
exists a distribution $P^{(n)}_{n\times n}(a_{K})$ compatible with $Q_{K}$,
the solver will find it. Conversely, if there is no such distribution, then
the solver will return a solution for the dual problem with an objective value
smaller than $0$. Such a solution is, in effect, a _certificate of
infeasibility_ , that is, a computer-generated proof that $Q_{K}$ is not a TI
marginal.

The method described above is a relaxation of the property of being a TI
marginal: if $Q_{K}$ does not pass the $n^{th}$ test, then it clearly is not a
TI marginal. If, on the other hand, $Q_{K}$ passes the $n^{th}$ test, then we
can apply the symmetrization protocol over the distribution $P_{n\times n}$
and obtain a 2D TI distribution $\hat{P}$ that, due to eq. (6) and the
condition $P_{K}=Q_{K}$, satisfies
$\hat{P}_{K}=Q_{K}+O\left(\frac{\max(s,t)}{n}\right)$.

This algorithm is highly inefficient, though, since the time and space
complexity of the computations scales as $O(e^{\alpha n^{2}})$. Actually,
there is a much more practical relaxation of the set of TI marginals achieving
the same accuracy that just involves $O(e^{\beta n})$ operations.

######  Definition 5 (Approximate solution to the marginal problem).

Given $Q_{K}$, with $K=s\times t$, $t\leq s$, verify that $Q_{K}$ is the
marginal of $P^{(n)}_{n\times t}$, with

$\displaystyle P^{(n)}_{(n-1)\times t+(1,0)}=P^{(n)}_{(n-1)\times t},$
$\displaystyle P^{(n)}_{n\times(t-1)+(0,1)}=P^{(n)}_{n\times(t-1)}.$ (10)

This can again be formulated as a linear program, and is obviously a
relaxation of the property of being a TI marginal. The condition (10) will
appear often in the rest of the article, so we will give it a name. Any
distribution $P_{n\times t}$ in the rectangle $n\times t$ satisfying the above
conditions will be called _locally translation invariant_ (LTI).

To see that the relaxation above is $O(s/n)$-close to the actual set of TI
marginals, suppose that $Q_{K}$ is the marginal of $P^{(n)}_{n\times t}$. We
will next extend $P^{(n)}_{n\times t}$ to a distribution $P^{\prime}_{n\times
n}$ with the property that the marginal of any $s\times t$ rectangle equals
$Q_{K}$.

In order to derive $P^{\prime}_{n\times n}$, we regard $P^{(n)}_{n\times t}$
as the $t$-site marginal of a TI 1D system with local variables of dimension
$d^{n}$. We can do so because $P^{(n)}_{n\times t}$ satisfies the second line
of (10). From the triviality of the marginal problem for TI 1D systems, we
know that there must exist a distribution $P^{\prime}_{n\times n}$ satisfying
the afore-mentioned properties. Finally, it is easy to see, from eq. (5), that
the symmetrization of $P^{\prime}_{n\times n}$ will be a 2D TI distribution
$\hat{P}$ with marginal $\hat{P}_{K}=Q_{K}+O(s/n)$.

To conclude, we would like to remark that the above sequence of relaxations of
the set of marginals also allows the user to approximately solve ENERGY.
Indeed, given $\\{(F_{i},K_{i})\\}_{i}$, one can carry out, via linear
programming, the optimization:

$\displaystyle E^{n}\equiv$
$\displaystyle\min\sum_{i}\sum_{a_{K_{i}}}F_{i}(a_{K_{i}})P^{(n)}_{K_{i}}(a_{K_{i}}),$
s.t. $\displaystyle P^{(n)}_{(n-1)\times t+(x,0)}=P^{(n)}_{(n-1)\times
t},\mbox{ for }x=0,1,$ $\displaystyle
P^{(n)}_{n\times(t-1)+(0,y)}=P^{(n)}_{n\times(t-1)},\mbox{ for }y=0,1.$ (11)

From what we reasoned above, it follows that
$E^{n}\leq\mbox{{ENERGY}}(\\{(F_{i},K_{i})\\}_{i})\leq E^{n}+O(1/n)$.

##  4 The exact marginal problem in 2D: characterizations

In this section we will identify certain variants or scenarios where the TI
marginal problem is exactly solvable. That is, where there exists an algorithm
that will determine with certainty if the given distributions are TI marginals
or not.

###  4.1 The exact marginal problem with reflection symmetry

Let us start with a relevant variant of the marginal problem: the 2D TI
marginal problem with reflection symmetry. This is the case where, in addition
to demanding the existence of a TI extension, we require this to be invariant
under reflections on both axes. Since Nature is approximately invariant under
parity reflection, this condition holds for the thermal states of many
physically relevant Hamiltonians, such as the isotropic Ising model and the
Potts model [18, 19].

######  Definition 6 (The $s\times 2$ TI marginal problem with reflection
symmetry).

Let $K=s\times 2$. Given $Q_{K}(a_{K})$, determine if there exists a 2D TI
distribution $P$ such that $P_{K}(a_{K})=Q(a_{K})$ and $P_{n\times
n}(a_{n\times n})=P_{n\times n}(a^{H}_{n\times n})=P_{n\times
n}(a^{V}_{n\times n})$, for all $n$. Here, $a^{H}_{n\times n}$,
$a^{V}_{n\times n}$ denote, respectively, the permutation of the variables
$(a_{\\{(x,y)\\}})|_{0\leq x\leq s-1,0\leq y\leq 1}$ associated to a
reflection over the horizontal and vertical axis, respectively.

Interestingly, the $s\times 2$ TI marginal problem with reflection symmetry
can be solved exactly.

######  Proposition 1.

The existence of a 2D TI distribution with reflection symmetry is equivalent
to the conditions:

$\displaystyle Q_{K}(a_{K})=Q_{K}(a^{H}_{K})=Q_{K}(a^{V}_{K}),$ $\displaystyle
Q_{(s-1)\times 2}=Q_{(s-1)\times 2+(1,0)}.$ (12)

###### Proof.

The second condition implies that, viewed as a 1D system of $s$ sites with
local variables of dimension $d^{2}$, $Q_{s\times 2}$ is the marginal of a TI
system. In particular, for any $n$ one can find $P^{1}_{n\times 2}$ with the
property that $P^{1}_{K+(x,0)}=Q_{K}$ for $0\leq x\leq n-s$. This property is
kept if we make the distribution invariant under reflection on both axes.

$\displaystyle P^{2}_{2\times n}(a_{2\times n})=$
$\displaystyle\frac{1}{4}(\hat{P}_{n\times 2}(a_{n\times 2})+\hat{P}_{n\times
2}(a^{H}_{n\times 2})+$ $\displaystyle\hat{P}_{v}(a^{V}_{n\times
2})+\hat{P}_{n\times 2}(a^{HV}_{n\times 2})).$ (13)

Reflection under the horizontal axis implies, in particular, that
$P^{2}_{n\times 1}=P^{2}_{n\times 1+(0,1)}$. Therefore, we can view $P^{2}$ as
the $2$-site marginal of a 1D TI system with variables of local dimension
$d^{n}$ and extend it to an $n\times n$ square. From that point on, we can
consider the symmetrization of this distribution $P^{3}_{n\times n}$, which
will return a 2D TI reflection-symmetric distribution with $Q_{K}+O(1/n)$ as a
marginal. Invoking the closure of the set of marginals of 2D TI distributions
[5], we conclude that $Q_{K}$ admits a 2D TI extension $P$. Finally, since
$Q_{K}$ satisfies reflection symmetry, one can choose $P$ to be symmetric as
well.

∎

The characterization (12) of the set of $s\times 2$ TI marginals with
reflection symmetry implies that, for $F_{K}$ satisfying
$F_{K}(a_{K})=F_{K}(a^{H}_{K})=F_{K}(a^{V}_{K})$, $\mbox{{ENERGY}}(F_{K})$ is
exactly solvable. Indeed, let $\hat{P}_{K}$ be any TI marginal and call $E$
the value of the functional in eq. (2) evaluated in $\hat{P}_{K}$. Then it is
easy to see that $P^{2}_{s\times 2}$, as defined by eq. (13) (replacing $n$ by
$s$), admits a TI, reflection-symmetric extension. Moreover, the value of the
functional is also $E$. It follows that, for
$F_{K}(a_{K})=F_{K}(a^{H}_{K})=F_{K}(a^{V}_{K})$, one can assume that the
minimizer of $\mbox{{ENERGY}}(F_{K})$ is a TI, reflection-symmetric marginal.
Hence one can use linear programming to solve the problem.

###  4.2 Binary local random variables

Take the local dimension of the random variable at each site to be $d=2$
(bits), and suppose that we just want to characterize the bivariate
distributions $P_{h}(a,b),P_{v}(a,b)$ between nearest-neighbors. The next
proposition states that the problem is solvable even for lattices of spatial
dimensions higher than $2$.

######  Proposition 2.

Let $C=\\{(1,0,0,...),(0,1,0,...),...\\}$ be the set of all $k$-dimensional
vectors with null components except one entry with value $1$, and let
$\\{P_{\\{\bar{0},\bar{c}\\}}(a,b):\bar{c}\in C\\}$ be all nearest-neighbor
marginals of a hypercubic lattice of spatial dimension $k$, with
$a,b\in\\{0,1\\}$. Then MARGINAL$(\\{P_{\\{\bar{0},\bar{c}\\}}(a,b):\bar{c}\in
C\\})$ can be formulated as a linear program. Moreover, for spatial dimensions
$k=2,3$, the existence of a TI extension for
$\\{P_{\\{\bar{0},\bar{c}\\}}(a,b):\bar{c}\in C\\}$ is equivalent to LTI,
i.e., the condition that

$\sum_{b}P_{\\{\bar{0},\bar{c}\\}}(x,b)=\sum_{a}P_{\\{\bar{0},\bar{c}^{\prime}\\}}(a,x),$
(14)

for all $\bar{c},\bar{c}^{\prime}\in C$.

For $d=2$ and $k=2,3$ the nearest-neighbor marginal problems are thus trivial.
This perhaps explains why the only known solvable classical models in 2D are
bit models.

###### Proof.

For simplicity, consider the $2D$ case $k=2$. Then, for $d=2$, LTI on either
$P_{h}$ or $P_{v}$ (i.e., $\sum_{a}P_{h}(a,x)=\sum_{a}P_{h}(x,a)$,
$\sum_{a}P_{v}(a,x)=\sum_{a}P_{v}(x,a)$) implies that both distributions
$P_{h}$ and $P_{v}$ are symmetric. Now, suppose that the pair $(P_{h},P_{v})$
admits a 2D TI extension. If we make this extension reflection-invariant -via
eq. (13)-, the distributions $P_{h},P_{v}$ will not change. In other words,
$(P_{h},P_{v})$ is a TI marginal iff it is a TI reflection-symmetric marginal.
From Proposition 1, we know that the marginals of 2D TI reflection-symmetric
distributions correspond to the marginals of symmetric, LTI squares. This
allows us to completely characterize the set of TI marginals $(P_{h},P_{v})$
via linear programming. The above symmetrization argument holds not only in
2D, but in any spatial dimension, and so does the proof of Proposition 1.

It follows that the set of nearest-neighbor marginals in any dimension is
described by a convex polytope, i.e., a set defined by a finite number of
linear inequalities or _facets_ $\\{F^{i}_{h}(P_{h})+F^{i}_{v}(P_{v})+...\leq
0\\}_{i=1}^{n}$, where $F^{i}_{h},F^{i}_{v},...,$ are linear functionals on
the probabilities $P_{h}(a,b)$, $P_{v}(a,b)$, etc. Using standard
combinatorial software [21], we managed to derive the facets
$\\{F^{i}_{h}(P_{h})+F^{i}_{v}(P_{v})\leq 0\\}_{i=1}^{n}$ which define the 2D
set. We verified, using linear programming, that the set all distributions
$(P_{h},P_{v})$ with

$\displaystyle\sum_{a}P_{h}(a,x)=\sum_{a}P_{h}(x,a)=$
$\displaystyle\sum_{a}P_{v}(a,x)=\sum_{a}P_{v}(x,a)$ (15)

cannot violate any of them. This implies that the above conditions, namely,
LTI, characterize completely the set of nearest-neighbor TI marginals.
Similarly, we verified that the analog 3D problem, with input
$\\{P_{\\{\vec{0},\hat{c}\\}}(a,b):\hat{c}=(1,0,0),(0,1,0),(0,0,1)\\}$,
reduces to verifying that conditions (14) hold. ∎

We now move to the problem of characterizing the distributions
$(P_{h},P_{v},P_{+},P_{-})$ corresponding to horizontal and vertical nearest-
neighbors and north-east $(+)$ and south-east $(-)$ next-to-nearest neighbor
distributions in $2D$. This problem is not trivial (i.e., it does not reduce
to verifying LTI), since the distribution
$P_{h}(a,b)=P_{v}(a,b)=P_{+}(a,b)=P_{-}(a,b)=\frac{1}{2}\delta_{a\oplus b,1}$
satisfies $\sum_{a}P_{s}(a,x)=\sum_{a}P_{t}(x,a)$ for $s,t=h,v,+,-$ and yet it
does not admit a TI extension 444Consider the random variables
$a_{0,0},a_{1,0},a_{0,-1}$ and imagine that there exists a probability
distribution $P$ for the three of them, with $P_{h},P_{v},P_{+}$ as marginals.
Then,
$\frac{1}{2}=P_{v}(a_{0,0}=0,a_{0,-1}=1)=P(a_{0,0}=0,a_{1,0}=0,a_{0,-1}=1)+P(a_{0,0}=0,a_{1,0}=1,a_{0,-1}=1)$.
However, by $P_{v}(0,0)=0$ ($P_{+}(1,1)=0$), the first (second) term of the
right hand side must equal zero. We thus reach a contradiction.. And yet, as
the next result shows, the set of nearest and next-to-nearest neighbor
marginals can also be characterized via linear programming.

######  Proposition 3.

For $d=2$, the nearest and next-to-nearest neighbors marginals
$P_{h},P_{v},P_{+},P_{-}$ admit a TI extension iff they are marginals of a
distribution $P_{2\times 2}$ satisfying LTI.

###### Proof.

If $P_{h},P_{v},P_{+},P_{-}$ are TI marginals, then they must constitute an
approximate solution of the marginal problem, in the sense explained in
Definition 5. In particular, they must belong to the polytope of distributions
$P_{h},P_{v},P_{+},P_{-}$ admitting a $2\times 2$ LTI extension. We find,
using the combinatorial software Panda [21], that this polytope has $13$
extreme points, each of which belongs to $6$ classes modulo rotations,
reflections and relabelings of the variables:

  1. (C1)

The two points in this class are deterministic:
$P_{h}(a,b)=P_{v}(a,b)=P_{+}(a,b)=P_{-}(a,b)=\delta_{a,0}\delta_{b,0}$ and
$P_{h}(a,b)=P_{v}(a,b)=P_{+}(a,b)=P_{-}(a,b)=\delta_{a,1}\delta_{b,1}$. They
obviously admit a deterministic 2D TI extension.

  2. (C2)

This class has two elements of the form

$\displaystyle P_{h}(a,b)=\frac{1}{2}\delta_{a,b\oplus
s},P_{v}(a,b)=\frac{1}{2}\delta_{a\oplus 1,b\oplus s}$ (16) $\displaystyle
P_{+}(a,b)=P_{-}(a,b)=\frac{1}{2}\delta_{a\oplus 1,b},$ (17)

with $s=0,1$.

The two elements are generated by applying the symmetrization process to the
$2\times 2$ deterministic distributions

$\begin{array}[]{|c|c|}\hline\cr 0&0\\\ \hline\cr 1&1\\\
\hline\cr\end{array},\begin{array}[]{|c|c|}\hline\cr 1&0\\\ \hline\cr 1&0\\\
\hline\cr\end{array}.$ (18)

  3. (C3)

This class contains just one element, namely:

$\displaystyle P_{h}(a,b)=P_{v}(a,b)=\frac{1}{2}\delta_{a\oplus 1,b}$ (19)
$\displaystyle P_{+}(a,b)=P_{-}(a,b)=\frac{1}{2}\delta_{a,b}.$ (20)

It is generated by the $2\times 2$ deterministic distribution

$\begin{array}[]{|c|c|}\hline\cr 1&0\\\ \hline\cr 0&1\\\
\hline\cr\end{array}.$ (21)

  4. (C4)

The class has two elements of the form

$\displaystyle
P_{h}(a,b)=P_{v}(a,b)=P_{+}(a,b)=P_{-}(a,b)=\frac{1}{4}(\delta_{a,s}+\delta_{b,s}),$
(22)

with $s=0,1$. They are respectively generated by symmetrizing the $2\times 2$
deterministic distributions:

$\begin{array}[]{|c|c|}\hline\cr 1&0\\\ \hline\cr 0&0\\\
\hline\cr\end{array},\begin{array}[]{|c|c|}\hline\cr 0&1\\\ \hline\cr 1&1\\\
\hline\cr\end{array}.$ (23)

  5. (C5)

This class has four elements, generated via applying reflections to the
generator:

$\displaystyle P_{h}(a,b)=P_{v}(a,b)=P_{+}(a,b)=\frac{1}{3}\delta_{a\cdot
b,0},$ (24) $\displaystyle
P_{-}(a,b)=\frac{2}{3}\delta_{a,0}\delta_{b,0}+\frac{1}{3}\delta_{a,1}\delta_{b,1}.$
(25)

The latter, in turn, can be generated by the $3\times 3$ deterministic
distribution

$\begin{array}[]{|c|c|c|}\hline\cr 0&0&1\\\ \hline\cr 0&1&0\\\ \hline\cr
1&0&0\\\ \hline\cr\end{array}.$ (26)

  6. (C6)

This class has two elements, generated either by applying the identity or a
$\pi/2$ rotation over the generator:

$\displaystyle P_{h}(a,b)=P_{v}(a,b)=\frac{1}{4},$ (27) $\displaystyle
P_{+}(a,b)=\frac{1}{2}\delta_{a\oplus
b,1},P_{-}(a,b)=\frac{1}{2}\delta_{a\oplus b,0}.$ (28)

It can be verified that the generator in turn can be built from the $4\times
4$ distribution:

$\begin{array}[]{|c|c|c|c|}\hline\cr 1&1&0&0\\\ \hline\cr 1&0&0&1\\\ \hline\cr
0&0&1&1\\\ \hline\cr 0&1&1&0\\\ \hline\cr\end{array}.$ (29)

Since all these points are TI marginals, any convex combination thereof will
also be a TI marginal. It follows that, for $d=2$, the first level of the
hierarchy presented in Def. 5 already characterizes all nearest and next-to-
nearest neighbor TI marginals.

∎

From Proposition 3 one can infer the exact solvability of the ENERGY problem
for TI Hamiltonians with nearest and next-to-nearest neighbor interactions.
Indeed, since any TI marginal is a convex combination of the above $13$
points, one just needs to evaluate the energy per site of each of them and
take the smallest result. It is worth noting that, for each extreme point $P$
listed above, there exists a unique (modulo translations) deterministic
distribution $\tilde{P}$ for the whole lattice such that
$\mbox{supp}(\tilde{P}_{g+z})\subset\mbox{supp}P_{g}$, with $g=h,v,+,-$ and
$z\in{\mathbb{Z}}^{2}$. Now, let the value of
$\mbox{{ENERGY}}(F_{h},F_{v},F_{+},F_{-})$ be achieved by just one extreme
point $P$ of the set of TI marginals. If $P$ is generated by tiling the plane
with an irreducible rectangle of size $m\times n$, then the number of lattice
configurations achieving the minimum energy per site of the corresponding
Hamiltonian is $mn$. Assuming that, at zero temperature, the system is in an
equal mixture of all such configurations, its entropy will be $S_{0}=\ln(mn)$.
As we will see in the next section, the uniqueness of the extended
distribution on the whole lattice is lost when each site can take more than
two values. This is in contrast to the situation in one dimension, where
maximal entropy extensions of LTI distributions exist and are unique [5].

###  4.3 Ternary local random variables

The purpose of this section is to characterize the set of TI nearest-neighbor
marginals $P_{h},P_{v}$ for ternary local random variables ($d=3$). For $d=2$,
all such $P_{h}$ and $P_{v}$ can be characterized simply by imposing (14). For
$d=3$, this condition is not sufficient. Take, for example, the distribution
$P_{h}(0,2)=P_{h}(1,0)=P_{h}(2,1)=P_{v}(0,2)=P_{v}(1,2)=P_{v}(2,1)=\frac{1}{3}$.
It can be easily checked that this distribution satisfies eq. (14). However,
one can verify numerically that it does not belong to the first level of the
hierarchy of approximations proposed in Definition 5.

Luckily, this first approximation turns out to be enough to characterize the
nearest-neighbor TI marginals.

######  Proposition 4.

For $d=3$, the nearest-neighbor marginals $P_{h},P_{v}$ admit a TI extension
iff they are compatible with a distribution $P_{2\times 2}$ satisfying LTI.

###### Proof.

The proof follows the same lines as the proof of Proposition 3. To find the
extreme points/facets of the polytope of marginals admitting a $P_{2\times 2}$
LTI extension, we first use a linear program to maximize random objective
functions under such a set. The vectors thus obtained are either vertices of
the polytope or lie on the facets. By computing the dual description of this
set of vectors, we obtain a set of linear inequalities some of which may be
facets of the polytope we seek. To check whether the inequalities are indeed
facets we use linear programming again but this time taking the vectors which
define the inequalities (without the bounds) as objective functions. If an
inequality is indeed a facet then maximizing this objective function using the
same constrains as before will give us the upper bound of the inequality as
the value of the objective function. If it is not a facet then this
maximization will violate the upper bound of the inequality, at which time we
can add the vector achieving this maximization to the list of potential
vertices. By iterating this violation/addition procedure until no inequality
can be violated when performing the second maximization, we obtain all the
facets of the polytope, from which the extreme points can also be computed. In
the $d=3$ case, the polytope is defined by 98 extreme points, which fall into
10 equivalence classes after taking local permutations of outcomes and
reflections into account. A representative from each class is given below,
with $P_{h}(a,b)$ and $P_{v}(a,b)$ written as a vector whose $i$th coordinate
in base $3$ gives the values of $a,b$:
$P_{h,v}(a,b)\equiv(0_{a}0_{b},0_{a}1_{b},0_{a}2_{b},\ldots,2_{a}2_{b})$. It
can be readily checked that each of these class representatives can be
generated by symmetrizing the depicted deterministic distributions
accompanying it.

  1. (C1)

$\begin{array}[]{|c|}\hline\cr 2\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$ $\displaystyle=(0,0,0,0,0,0,0,0,1),$ $\displaystyle
P_{v}$ $\displaystyle=(0,0,0,0,0,0,0,0,1).$

  2. (C2)

$\begin{array}[]{|c|c|}\hline\cr 1&2\\\ \hline\cr 2&1\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$ $\displaystyle=(0,0,0,0,0,\frac{1}{2},0,\frac{1}{2},0),$
$\displaystyle P_{v}$ $\displaystyle=(0,0,0,0,0,\frac{1}{2},0,\frac{1}{2},0).$

  3. (C3)

$\begin{array}[]{|c|c|}\hline\cr 1&2\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$ $\displaystyle=(0,0,0,0,0,\frac{1}{2},0,\frac{1}{2},0),$
$\displaystyle P_{v}$ $\displaystyle=(0,0,0,0,\frac{1}{2},0,0,0,\frac{1}{2}).$

  4. (C4)

$\begin{array}[]{|c|c|}\hline\cr 0&2\\\ \hline\cr 2&2\\\ \hline\cr 1&1\\\
\hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{6},0,\frac{1}{3},0,\frac{1}{6},0,\frac{1}{3}),$
$\displaystyle P_{v}$
$\displaystyle=(0,0,\frac{1}{6},\frac{1}{6},0,\frac{1}{6},0,\frac{1}{3},\frac{1}{6}).$

  5. (C5)

$\begin{array}[]{|c|c|}\hline\cr 0&2\\\ \hline\cr 2&1\\\ \hline\cr 1&1\\\
\hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{6},0,\frac{1}{3},\frac{1}{6},\frac{1}{6},\frac{1}{6},0),$
$\displaystyle P_{v}$
$\displaystyle=(0,0,\frac{1}{6},\frac{1}{6},\frac{1}{6},\frac{1}{6},0,\frac{1}{3},0).$

  6. (C6)

$\begin{array}[]{|c|c|}\hline\cr 0&2\\\ \hline\cr 2&1\\\ \hline\cr 2&0\\\
\hline\cr 1&2\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{4},0,0,\frac{1}{4},\frac{1}{4},\frac{1}{4},0),$
$\displaystyle P_{v}$
$\displaystyle=(0,0,\frac{1}{4},\frac{1}{4},0,0,0,\frac{1}{4},\frac{1}{4}).$

  7. (C7)

$\begin{array}[]{|c|c|}\hline\cr 0&2\\\ \hline\cr 1&2\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{4},0,0,\frac{1}{4},\frac{1}{4},\frac{1}{4},0),$
$\displaystyle P_{v}$
$\displaystyle=(0,\frac{1}{4},0,\frac{1}{4},0,0,0,0,\frac{1}{2}).$

  8. (C8)

$\begin{array}[]{|c|c|c|c|}\hline\cr 2&1&0&2\\\ \hline\cr 2&1&1&0\\\
\hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{4},\frac{1}{4},\frac{1}{8},0,0,\frac{1}{4},\frac{1}{8}),$
$\displaystyle P_{v}$
$\displaystyle=(0,\frac{1}{8},\frac{1}{8},\frac{1}{8},\frac{1}{4},0,\frac{1}{8},0,\frac{1}{4}).$

  9. (C9)

$\begin{array}[]{|c|c|c|}\hline\cr 0&2&1\\\ \hline\cr 2&1&0\\\ \hline\cr
1&0&2\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{3},\frac{1}{3},0,0,0,\frac{1}{3},0),$
$\displaystyle P_{v}$
$\displaystyle=(0,0,\frac{1}{3},\frac{1}{3},0,0,0,\frac{1}{3},0).$

  10. (C10)

$\begin{array}[]{|c|c|c|}\hline\cr 0&2&1\\\ \hline\cr\end{array}$

$\displaystyle P_{h}$
$\displaystyle=(0,0,\frac{1}{3},\frac{1}{3},0,0,0,\frac{1}{3},0),$
$\displaystyle P_{v}$
$\displaystyle=(\frac{1}{3},0,0,0,\frac{1}{3},0,0,0,\frac{1}{3}).$

∎

##  5 The exact marginal problem in 2D: no-go theorems

In view of the results of the previous section, one would imagine that the
exact resolution of the marginal problem for scenarios with high local
dimension $d$ is merely a matter of computational power. Note that all the
marginal sets characterized so far satisfy the following properties:

  1. 1.

They allow us to solve ENERGY exactly.

  2. 2.

When we represent them in probability space, they happen to be convex
polytopes, i.e., sets determined by a finite number of linear inequalities.
More broadly, they are _semi-algebraic sets_. A subset ${\mathcal{S}}$ of
${\mathbb{R}}^{s}$ is a _basic closed semi-algebraic set_ if there exist a
finite number of polynomials $\\{F_{i}\\}_{i=1}^{u}$ on
$\bar{x}\in{\mathbb{R}}^{s}$ and the slack vector $\bar{y}\in{\mathbb{R}}^{t}$
such that

$\displaystyle\bar{x}\in{\cal S}\mbox{ iff }$
$\displaystyle\exists\bar{y}\in{\mathbb{R}}^{t},s.t.$ $\displaystyle
F_{i}(\bar{x},\bar{y})\geq 0,i=1,...,u.$ (30)

All subsets of ${\mathbb{R}}^{t}$ which one can characterize via linear
programming [13] or the more general tool of semidefinite programming [14]
fall within this category. A semi-algebraic set would be the union of a finite
number of basic closed semi-algebraic sets. However, it is easy to show that
any closed convex semi-algebraic set is also basic, so in the following we
will use both terms interchangeably.

Extrapolating, one would expect that the marginal sets of 2D TI distributions
with arbitrary $d$ should retain at least one of the above features.

In the following pages we show that this is not the case even when we aim at
solving the simplest non-trivial marginal problem: the characterization of
$(P_{h},P_{v})$.

###  5.1 Undecidability of ENERGY

In this section we will prove the following result:

######  Theorem 5.

There exists no algorithm to solve $\mbox{{ENERGY}}(F_{h},F_{v})$ for
arbitrary local dimension $d$ and
$F_{h},F_{v}:\\{0,...,d-1\\}^{2}\to\\{0,1\\}$.

The proof of this theorem, as well as the proof of the next no-go result, will
rely heavily on certain mathematical results on tilings of the plane, so let
us first introduce a basic vocabulary.

Let $A$ be a finite alphabet. Any function $f:{\mathbb{Z}}^{2}\to A$ defines a
_tiling of the plane_ with the set of tiles $A$. Any pair of subsets ${\cal
T}=({\cal T}_{h},{\cal T}_{v})$ of $A\times A$ defines a _tiling rule_. We say
that a tiling $f$ respects the tiling rule ${\cal T}$ if, for all
$(x,y)\in{\mathbb{Z}}^{2}$,

$(f(x,y),f(x+1,y))\in{\cal T}_{h},(f(x,y),f(x,y+1))\in{\cal T}_{v}.$ (31)

If the rule ${\cal T}$ is implicitly known, we call $f$ a valid tiling.

Certain rules ${\cal T}$ do not admit any valid tiling, e.g.: take
$A=\\{0,1\\}$ and ${\cal T}_{h}=\\{(0,1)\\},{\cal T}_{v}=A\times A$. The
problem of deciding if a given rule ${\cal T}$ admits a valid tiling was first
raised by Wang [22], and proven undecidable by Berger [23], who also showed
the existence of tiling rules ${\cal T}$ admitting just aperiodic tilings. The
construction used by Berger to derive the latter result uses 20426 tiles. This
number has been decreasing over the years as new aperiodic tiling rules
requiring less tiles were found. The current record, held by Jeandel and Rao,
uses only 11 tiles [24].

We will prove that $\mbox{{ENERGY}}(F_{h},F_{v})$ is undecidable by reducing
it to the general tiling problem. Let ${\cal T}$ be a tiling rule, and define
the input of ENERGY as

$\displaystyle F_{h}(a,b)=$ $\displaystyle 1,\mbox{ if }(a,b)\in{\cal T}_{h},$
$\displaystyle 0,\mbox{ otherwise},$ $\displaystyle F_{v}(a,b)=$
$\displaystyle 1,\mbox{ if }(a,b)\in{\cal T}_{v},$ $\displaystyle 0,\mbox{
otherwise}.$ (32)

We claim that $\mbox{{ENERGY}}(F_{h},F_{v})=2$ iff ${\cal T}$ admits a valid
tiling. Consequently, the ENERGY problem is undecidable.

First, suppose that ${\cal T}$ admits a valid tiling. We choose an $n\times n$
square of this tiling, and apply symmetrization to obtain the marginals
$P^{(n)}_{h},P^{(n)}_{v}$ of a 2D TI distribution. Those will satisfy
$F_{h}(P^{(n)}_{h})+F_{v}(P^{(n)}_{v})=2-O(1/n)$. That way, we obtain a
sequence of TI marginals $(P^{(n)}_{h},P^{(n)}_{v})_{n}$ whose energy per site
tends to $2$. The closure of the set of TI marginals implies that there exists
a TI marginal $(P^{\star}_{h},P^{\star}_{v})$ with
$F_{h}(P^{\star}_{h})+F_{v}(P^{\star}_{v})=2$. Since $F_{h}(P),F_{v}(P)\leq 1$
for any distribution, this implies that $\mbox{{ENERGY}}(F_{h},F_{v})=2$.

Conversely, suppose that $\mbox{{ENERGY}}(F_{h},F_{v})=2$. Then, there exists
a 2D TI distribution $P$ saturating the bound. Given $P_{|n\times n|}$, take
any configuration $a_{|n\times n|}$ such that $P_{|n\times n|}\not=0$.
Obviously, $a_{|n\times n|}$ is a valid tiling for $|n\times n|$. Now,
consider $P_{|(n+1)\times(n+1)|}$ and take any configuration
$a_{|(n+1)\times(n+1)|}$ such that $a_{|n\times n|}$ is an inner square of
$a_{|(n+1)\times(n+1)|}$ and
$P_{|(n+1)\times(n+1)|}(a_{|(n+1)\times(n+1)|})\not=0$. That such a
configuration must exist follows from the fact that
$\sum_{a^{\prime}}P_{|(n+1)\times(n+1)|}(a_{|n\times
n|},a^{\prime})=P_{|n\times n|}(a_{|n\times n|})\not=0$, where $a^{\prime}$
denotes the local variables of the inner border of the $|(n+1)\times(n+1)|$
square. Iterating, we obtain a sequence $(a_{|n\times n|})_{n}$ of valid tiles
for ever-growing squares with the particularity that, for all $n$,
$a_{|n\times n|}$ is contained in $a_{|(n+1)\times(n+1)|}$. The desired tiling
of the plane is hence given by the function $f$ assigning to each point
$(x,y)$, with $|x|<n,|y|<n$ the corresponding tile in $a_{|n\times n|}$.

###  5.2 The set of TI nearest-neighbors marginals is not a semi-algebraic set

The goal of this section is to prove the following theorem.

######  Theorem 6.

For $d=2947$, the set of nearest-neighbor TI marginals $P_{h},P_{v}$ is not
semi-algebraic. Moreover, some pieces of its boundary are smoothly curved.

Before proving this theorem, we want to remark that the value of $d=2947$
comes from the number of tiles required by our construction below. It is not
necessarily tight: for all we know, the critical value $d$ which marks the
transition from polytopes to curved sets could be as low as $4$. It is
possible that, similar to the history of the minimum set of Wang tiles
discussed above, our upper bound $d=2947$ be improved in the future. A
consequence of Theorem 6 is that, for $d\geq 2947$, the set of nearest-
neighbor TI marginals cannot be characterized by either linear or semidefinite
programming [14].

###### Proof.

The idea of the proof is as follows: given a finite alphabet $A$, we will
define a tiling rule ${\cal T}$, and we will consider the set ${\cal P}$ of
all TI marginals $(P_{h}(a,b),P_{v}(a,b))$, with $a,b\in A$ such that

$\sum_{(a,b)\in{\cal T}_{h}}P_{h}(a,b)=\sum_{(a,b)\in{\cal
T}_{v}}P_{v}(a,b)=1.$ (33)

That is, we will consider the intersection between the set of TI marginals and
two planes defined by integer coefficients. If the set of all TI marginals
$(P_{h},P_{v})$ were semi-algebraic or a polytope, then so would ${\cal P}$.

We will then define two linear 1-site parameters

$\omega\equiv\sum_{a\in A}\hat{\omega}(a)P_{(0,0)}(a),\eta\equiv\sum_{a\in
A}\hat{\eta}(a)P_{(0,0)}(a),$ (34)

and characterize the set ${\cal S}$ of feasible values $(\omega,\lambda)$ in
${\cal P}$. We will find that the boundary of ${\cal S}$ contains both flat
and a smoothly curved pieces, so we will conclude that the set of nearest-
neighbor TI marginals with variables of dimension $d=|A|$ does not form a
polytope. Similarly, by proving that ${\cal S}$ is not a basic closed semi-
algebraic set, we will demonstrate that neither is the set of TI marginals.

The proof relies heavily on the connection between aperiodic tilings and
immortal points of dynamical systems first pointed out in [25] and later
extended in [26]. Before giving our implementation which proves the statement
above we will briefly review the general construction given in [25, 26].

Let $M$ be a $2\times 2$ matrix with rational coefficients; and $c$, a
rational vector in ${\mathbb{R}}^{2}$. We will consider a number $u$ of unit
squares $\\{R^{i}\\}_{i=1}^{u}$ in ${\mathbb{R}}^{2}$, each of them defined by
their integer corners
$U^{i}=\\{(m^{i},n^{i}),(m^{i}+1,n^{i}),(m^{i},n^{i}+1),(m^{i}+1,n^{i}+1)\\}$.
Let $R\equiv\cup_{i=1}^{u}R^{i}$. The tiles used in this construction are all
derived from the prototile given in Fig. 3. A tile is labeled by four vectors
in ${\mathbb{R}}^{2}$, called $t,b,l,r$ (_top, bottom, left and right_) and a
_region_ $i\in\\{1,...,u\\}$. The components of $l$ and $r$ are rational,
$t\in U^{i}$ and $b\in U^{j}$ for some $j=1,...,u$. A valid tile also
satisfies the relation $f(t)+l=b+r$, where
$f:{\mathbb{R}}^{2}\to{\mathbb{R}}^{2}$ is the affine function
$f(\bar{z})\equiv M\bar{z}+c$.

Given any set $A$ (finite or infinite) of tiles so labeled and satisfying such
constraints, the tiling rules we will consider are:

  1. 1.

To the right of any tile with region $i$ and right vector $r$, there can only
be a tile with region $i$ and left vector $r$.

  2. 2.

To the bottom of any tile with bottom vector $b$, there can only be a tile
with top vector $b$.

Figure 3: The Kari prototile.

The first rule can be seen to imply that, for any valid row of tiles
$k=1,...,m$ of the form $(i,t_{k},b_{k},l_{k},r_{k})$,

$f(\langle t\rangle)+\frac{l_{1}}{m}=\langle b\rangle+\frac{r_{m}}{m},$ (35)

where $\langle t\rangle,\langle b\rangle$, are, respectively, the arithmetic
means of the top and bottom vectors of the $n$ tiles. Note that, by convexity,
$\langle t\rangle\in R^{i}$, $\langle b\rangle\in\mbox{conv}(R)$.

Figure 4: Law of averages for a segment of Kari tiles. For large $m$,
$f(\langle t\rangle)\approx\langle b\rangle$.

Let $A$ be such that the set $L$ of possible left vectors $l$, viewed as a
subset of ${\mathbb{R}}^{2}$, is bounded and equal to the set of feasible
right vectors. It follows that, for $n$ sufficiently large, we can view each
valid row as a vector $\bar{z}\in R^{i}$ undergoing the transformation
$\bar{z}\to M\bar{z}+c$. Moreover, by the second tiling rule, given the
validly tiled rectangle $|m\times n|$, with $m\gg n\gg 1$, the sequence of top
vector averages on each row $j$ can be interpreted as an orbit inside $R$
given by $(\bar{z}_{j}=f^{-j}(\bar{z}_{0})+O(\frac{n}{m}):j=-n,...,n)$. In
addition, the region of the $j^{th}$ row indicates which square
$R^{1},...,R^{u}$ contains $\bar{z}_{j}$. Taking the limit
$n\to\infty,\frac{n}{m}\to 0$, a valid tiling is only possible if
$f^{j}(\bar{z}_{0})\in R$ for all $j\in{\mathbb{Z}}$. $\bar{z}_{0}$ is then
called an _immortal point_ of the _dynamical system_ given by $M$, $c$ and
$R$.

The breakthrough in [25, 26] was to realize that, conversely, there always
exists a _finite_ alphabet $A$ such that any immortal point of the system
$(M,c,R)$ can be represented with a valid tiling of $A$.

Let $\bar{v}\in{\mathbb{R}}^{2}$, and, for any $k\in{\mathbb{Z}}$, define
$A_{k}(\bar{v})\equiv\lfloor k\bar{v}\rfloor$, where the floor is taken for
each coordinate of $\bar{v}$. Now, denote $B_{k}(\bar{v})\equiv
A_{k}(\bar{v})-A_{k-1}(\bar{v})$. It can be shown that, if $\bar{v}\in R^{j}$,
then $B_{k}(\bar{v})\in U^{j}$. Similarly,
$\frac{1}{N}\sum_{k=1}^{N}B_{k+h}(\bar{v})=\bar{v}\pm O(1/N)$.

Now, suppose that, for any $i=1,...,u$, and any immortal point $\bar{v}\in
R^{i}$, $A$ contains the set $A^{\prime}$ of all tiles $T_{k}(\bar{v})$ with
region $i$ and top, bottom, left and right vectors of the form:

$\displaystyle t_{k}(\bar{v})$ $\displaystyle=B_{k}(\bar{v}),$ $\displaystyle
b_{k}(\bar{v})$ $\displaystyle=B_{k}(f(\bar{v})),$ $\displaystyle
l_{k}(\bar{v})$
$\displaystyle=f(A_{k-1}(\bar{v}))-A_{k-1}(f(\bar{v}))+(k-1)c,$ $\displaystyle
r_{k}(\bar{v})$ $\displaystyle=f(A_{k}(\bar{v}))-A_{k}(f(\bar{v}))+kc,$ (36)

for all $k\in{\mathbb{Z}}$. It can be verified that these tiles satisfy the
conditions $f(t)+l=b+r$, $t\in U^{i}$, $b\in\cup_{j=1}^{u}U^{j}$.

Since $r_{k}(\bar{v})=l_{k+1}(\bar{v})$, the tiles
$T_{k}(\bar{v}),T_{k+1}(\bar{v}),T_{k+2}(\bar{v}),...,T_{k+m}(\bar{v})$ form a
valid row for any $m$. We can extend this row below by placing another row of
the form $T_{k}(f(\bar{v})),T_{k+1}(f(\bar{v})),T_{k+2}(f(\bar{v})),...$, with
$M\bar{v}\in R^{i^{\prime}}$. Iterating, we can tile the whole plane in this
fashion, provided that $\bar{v}$ is an immortal point. From the properties of
$B_{k}(\bar{v})$, the averages of the inputs of each row $j$ tend to
$f^{j}(\bar{v})$ in the limit $n\to\infty$, $\frac{n}{m}\to 0$.

It rests to see that $A^{\prime}$ is a finite set. The top and bottom vectors
of each tile belong to $\cup_{i=1}^{u}U^{i}$, and so they can only take
finitely many values. As for the left or right vectors of the tile, they must
belong to the set
$L^{\prime}=\\{r_{k}(\bar{v}):\bar{v}\in{\mathbb{R}}^{2},k\in{\mathbb{Z}}\\}$.
Let $l\in L^{\prime}$ and denote by $l_{s}$ its $s^{th}$ component. Using the
relations $x-1\leq\lfloor x\rfloor\leq x$ repeatedly, we have that

$\mu^{-}_{s}:=-\sum_{j^{+}}M_{s,j}+c_{s}\leq l_{s}\leq
1-\sum_{j^{-}}M_{s,j}+c_{s}=:\mu^{+}_{s}$ (37)

where $j^{+}$ ($j^{-}$) ranges over all those $j$ such that $M_{s,j}>0$
($M_{s,j}<0$).

Call $m_{s}$ the common denominator $m_{s}$ of the rational numbers
$\\{M_{s,j}\\}_{j},c_{s}$ (remember that $M,c$ are assumed to be rational).
From the definition of $L^{\prime}$, it follows that $l\in L^{\prime}$ must
satisfy $\left(\begin{array}[]{cc}m_{1}&0\\\
0&m_{2}\end{array}\right)l\in{\mathbb{Z}}^{2}$. Define then the set
$L=\\{l:m_{s}l_{s}\in{\mathbb{Z}},\mu^{-}_{s}\leq
l_{s}\leq\mu^{+}_{s},s=1,2\\}$. Clearly $L$ is bounded and contains
$L^{\prime}$.

In order to generate $A$, we go through all regions $i,j=1,...,u$ and all
combinations of top and bottom vectors $t\in U^{i},b\in U^{j}$, and any left
vector $l\in L$ and verify that the right vector $r=f(t)+l-b$ also belongs to
$L$. If it does, then we add the tile $(i,t,l,r)$ to the definition of $A$.
That way, we end up with a finite alphabet that, via the above tiling rules,
can describe all immortal orbits of the dynamical system $(M,c,R)$. This is a
simplification of the construction proposed in [26] to simulate a dynamical
system where the transformation $f$ may depend on the region $i$, i.e., $z\to
M^{i}z+c^{i}$.

To prove our result, we take $M,c$ to be

$M=\left(\begin{array}[]{cc}\frac{4}{5}&-\frac{3}{5}\\\
\frac{3}{5}&\frac{4}{5}\end{array}\right),c=\left(\begin{array}[]{c}\frac{1}{5}\\\
\frac{1}{5}\end{array}\right),$ (38)

and consider the regions $R^{1},R^{2}$ corresponding to the unit squares
$[0,-1]\times[0,1]$, $[0,1]\times[0,1]$, respectively. Using the above
construction, we find that we can simulate the dynamical system defined by
$(M,c,R)$ via an alphabet of $2947$ tiles.

The action of $f$ over a vector $\bar{z}$ can be rewritten
$f(z)=M(z-\hat{c})+\hat{c}$, with $\hat{c}=(-1/5,2/5)$, where $M$ implements a
counter-clockwise rotation by an angle
$\phi_{0}=\arccos\left(\frac{4}{5}\right)$. Sequential applications of $f$
over an initial vector $z_{0}$ have thus the effect of rotating the vector an
angle $\phi_{0}$ with respect to the point $\hat{c}$, see Figure 5.

Figure 5: The action of $f$. The effect of the affine transformation $f$ over
an arbitrary vector $z$ is to rotate it by an angle $\phi_{0}$ with respect to
the point $\hat{c}=(-1/5,2/5)$.

As we will see later, $\phi_{0}$ is an irrational multiple of $2\pi$. Hence,
by applying $M$ sequentially, we can induce a rotation arbitrarily close to
any angle $\theta$. It follows that a point $\bar{z}$ is immortal in the
dynamical system given by $(M,c,R)$ iff
$\|\bar{z}-\hat{c}\|_{2}\leq\frac{2}{5}$.

We are interested in the following extensive quantities:

$\displaystyle\Omega\equiv\frac{1}{(2m+1)(2n+1)}\sum_{x=-m}^{m}\sum_{y=-n}^{n}\left(t_{1}(x,y)+\frac{1}{5}\right)\delta_{i(x,y),2},$
(39) $\displaystyle
H\equiv\frac{1}{(2m+1)(2n+1)}\sum_{x=-m}^{m}\sum_{y=-n}^{n}\delta_{i(x,y),2},$
(40)

where $i(x,y),t(x,y),b(x,y),l(x,y),r(x,y)$ denote the parameters specifying
the tile at position $(x,y)$; $t_{1}$ is the first coordinate of the top
vector $t$; and $\delta$, the Kronecker delta. We will show that, if
$n\to\infty$ and $\frac{n}{m}\to 0$, the set of feasible $(\Omega,H)$ is
parametrized by the curve

$\left\\{\left(\frac{\mu}{\pi}\sqrt{1-\left(\frac{1}{5\mu}\right)^{2}},\frac{1}{\pi}\arccos\left(\frac{1}{5\mu}\right)\right):\frac{1}{5}\leq\mu\leq\frac{2}{5}\right\\}.$
(41)

Intuitively, the vector $z$ defined at the top side of each row of the tiling
is turning by an amount $\phi_{0}$ from row to row. The witness (39)
corresponds to the average of $\bar{z}-\hat{c}$’s first coordinate in the
region $R^{2}$. That is,

$W=\lim_{N\to\infty}\frac{1}{2N+1}\sum_{k=-N}^{N}\mu\cos(\varphi+k\phi_{0})\chi_{[-\arccos\left(\frac{1}{5\mu}\right),\arccos\left(\frac{1}{5\mu}\right)]}(\varphi+k\phi_{0}),$
(42)

where $\varphi$ is the angle of $\bar{z}$ at row $j=0$ with respect to the
$\hat{x}$ axis; $\mu=\|z-\hat{c}\|_{2}$ and $\chi_{O}(p)$ is the
characteristic function that equals $1$ when $p\in O$ and $0$ otherwise. Since
$\phi_{0}$ is not congruent, we expect the above expression to converge to

$\frac{1}{2\pi}\int_{-\arccos\left(\frac{1}{5\mu}\right)}^{\arccos\left(\frac{1}{5\mu}\right)}d\theta\mu\cos(\theta)=\frac{\mu}{\pi}\sqrt{1-\left(\frac{1}{5\mu}\right)^{2}},$
(43)

for $\frac{1}{5}\leq\mu\leq\frac{2}{5}$ and $0$ otherwise. Analogously, the
second witness (40) measures the presence of vector $z$ in $R^{2}$, and so it
should converge to

$\frac{1}{2\pi}\int_{-\arccos\left(\frac{1}{5\mu}\right)}^{\arccos\left(\frac{1}{5\mu}\right)}d\theta=\frac{1}{\pi}\arccos\left(\frac{1}{5\mu}\right),$
(44)

for $\frac{1}{5}\leq\mu\leq\frac{2}{5}$ and $0$ otherwise. The coordinates of
an arbitrary feasible point $(\Omega,H)$ will thus belong to the trajectory
(41).

To justify eqs. (43), (44), though, we need to prove a result that relates the
integration of a function with the sampling over $(\varphi+k\phi_{0})_{k}$.

######  Lemma 1.

Let $\phi_{0}$ be such that $m\phi_{0}\not=0\mbox{ }(\mbox{mod }2\pi)$ for all
$m$, and let $g(\phi)$ be any piecewise continuous bounded function in
$\phi\in[-\pi,\pi]$. Then, for any $\varphi\in[-\pi,\pi]$,

$g^{\star}:=\lim_{N\to\infty}\frac{1}{N}\sum_{k=1}^{N}g(\varphi+k\phi_{0})=\frac{1}{2\pi}\int_{-\pi}^{\pi}d\theta
g(\theta).$ (45)

###### Proof.

Note that, for any $m\in{\mathbb{Z}}$,

$\displaystyle\lim_{N\to\infty}\frac{1}{N}\sum_{k=1}^{N}e^{m(\varphi+k\phi_{0})}=$
$\displaystyle 0,\mbox{ for }m\not=0,$ $\displaystyle 1\mbox{ for }m=0.$ (46)

Let $g(\theta)$ be a periodic, piecewise _differentiable_ bounded function.
Then it converges uniformly under a Fourier expansion, i.e., for any
$\epsilon>0$, there exists $R$ such that $|g(\theta)-g_{R}(\theta)|<\epsilon$
for all $\theta\in[-\pi,\pi]$, where
$g_{R}(\theta)=\sum_{m=-R}^{R}c_{m}e^{m\theta}$ and $\\{c_{m}\\}_{m}$ are the
Fourier coefficients of $g(\theta)$.

Now, from eq. (46), we have that

$g^{\star}_{R}=c_{0}=\frac{1}{2\pi}\int_{-\pi}^{\pi}d\theta g(\theta),\forall
R.$ (47)

Since the $\star$ process is, in fact, an average,
$|g^{\star}_{R}-g^{\star}|<\epsilon$, and we conclude that eq. (45) holds for
all piece-wise derivable bounded functions. The general result can be obtained
by noticing that, for any piece-wise continuous function $g$, there exist two
sequences of piece-wise derivable functions $(g^{u}_{n})_{n}$,
$(g^{d}_{n})_{n}$ such that $g^{d}_{n}(\theta)\leq g(\theta)\leq
g^{u}_{n}(\theta)$ for all $n,\theta$ and
$\lim_{n\to\infty}\int_{-\pi}^{\pi}d\theta
g^{d}_{n}(\theta)=\lim_{n\to\infty}\int_{-\pi}^{\pi}d\theta
g^{u}_{n}(\theta)$. ∎

To apply the above lemma, we still need to show that $\phi_{0}$ is congruent.
This follows from $\sin(\phi_{0})=\frac{3}{5}$ and Niven’s theorem [27,
pp.41], that states that the only angles $0\leq\phi\leq\pi/2$ with
$\phi=\frac{m}{n}\pi$ and rational sine are $0$, $\frac{\pi}{6}$ and
$\frac{\pi}{2}$.

We have just shown that, in the limits $n\to\infty$, $\frac{n}{m}\to 0$, the
vector of feasible values $(\Omega,H)$ in an $n\times m$ valid tiling is
parametrized by eq. (41). What does this have to do with TI marginals?
Consider a random variable taking values in the tile set $A$, and a TI
marginal $(P_{h},P_{v})$ satisfying the constraint:

$\sum_{(a,b)\in{\cal T}_{h}}P_{h}(a,b)=\sum_{(a,b)\in{\cal
T}_{v}}P_{v}(a,b)=1.$ (48)

Consider also the linear functionals given by

$\displaystyle\omega(P_{h},P_{v})\equiv\sum_{a\in
A}P(a)\left(t_{1}(a)+\frac{1}{5}\right)\delta_{i(a),2},$
$\displaystyle\eta(P_{h},P_{v})\equiv\sum_{a\in A}P(a)\delta_{i(a),2},$ (49)

where $t_{1}(a)\in\\{0,\pm 1\\}$ $(i(a)\in\\{1,2\\})$ denotes the 2nd
coordinate of the top side (the region) of tile $a$.

By definition, for any $n,m$ there exists a LTI distribution $P_{n\times m}$
with nearest-neighbor marginals $(P_{h},P_{v})$. $P_{n\times m}$ can be seen
as a convex combination of tilings $a_{n\times m}^{k}$ with weight $p_{k}$ of
the set $n\times m$. Moreover, due to condition (48), all of them must be
valid tilings. Hence,

$\omega(P_{h},P_{v})=\sum_{k}p_{k}\Omega(a_{n\times
m}^{k}),\eta(P_{h},P_{v})=\sum_{k}p_{k}H(a_{n\times m}^{k}).$ (50)

In the limit $n\to\infty$, $\frac{n}{m}\to 0$, the point $(\omega,\eta)$
belongs to the convex hull ${\cal S}$ of the curve (41). It can be verified
that $\frac{d^{2}\eta}{d\omega^{2}}\leq 0$, i.e., the curve is concave. Hence
the boundary of ${\cal S}$ is given by curve (41) and the segment joining its
start and end points, see Figure 6.

Figure 6: Accessible values for the parameters $\omega$ and $\eta$ are given
by the shaded region.

It rests to show that any point of the shaded region in Figure 6 is achievable
by a TI marginal. Since the set of TI marginals is convex, it is enough to see
that one can achieve the extreme points of the set ${\cal S}$. Let
$\frac{1}{5}\leq\mu\leq\frac{2}{5}$ and take any valid tiling $a_{Z^{2}}$ of
the plane describing a vector $z\in{\mathbb{R}}^{2}$ with
$\|z-\hat{c}\|_{2}=\mu$. Further take any increasing sequence of rectangles
$m^{(k)}\times n^{(k)}$, with $\lim_{k\to\infty}n^{(k)}/m^{(k)}=0$.
Symmetrizing the deterministic distribution $a_{m^{(k)}\times n^{(k)}}$, we
obtain a sequence of TI marginals $(P^{(k)}_{h},P^{(k)}_{h})_{k}$ which
violate (48) by an amount $O(1/n^{(k)})$. By Weiestrass’ theorem, there exists
a subsequence of this sequence that converges to a pair of distributions, call
them $(P_{h},P_{v})$. By closure of the set of TI marginals, $(P_{h},P_{v})$
admits a 2D TI extension. Moreover, it satisfies (48) and $\omega,\eta$ are
are given by eq. (41).

As it is clear from Figure 6, the upper piece of ${\cal S}$’s boundary is
smoothly curved. In other words: ${\cal S}$ is not a polytope, and so neither
is the set of nearest-neighbor TI marginals. In order to show that it is also
not a semi-algebraic set, see eq. (30), we will assume that it is and prove
the result by contradiction.

${\cal S}$ is the result of intersecting the set of TI marginals with a number
of planes followed by a projection on the variables $\omega,\eta$: from our
hypothesis, it follows that it is also a basic closed semi-algebraic set.
Adding the variables $\nu,\mu$ and the relations
$\mu^{2}-\frac{1}{25}-\pi^{2}\omega^{2}=0$, $\mu\geq\frac{1}{5}$, $\nu\geq 0$,
$\mu\nu-\frac{1}{5}=0$, we have a new closed semi-algebraic set for the
variables $(\omega,\eta,\mu,\nu)$. Its projection onto $(\nu,\eta)$ gives rise
to a new semi-algebraic set ${\cal S}^{\prime}$, with its boundary containing
the curve $\\{(\nu,\frac{\arccos(\nu)}{\pi}):\nu\in[\frac{1}{2},1]\\}$.

By the Tarski-Seidenberg projection theorem [28, 12], ${\cal S}^{\prime}$ is
determined by a number of polynomials $\\{G_{i}\\}_{i=1}^{u}$, such that

$\displaystyle(\nu,\eta)\in\tilde{{\cal S}^{\prime}}\mbox{ iff }$
$\displaystyle G_{i}(\omega,\eta)\geq 0,i=1,...,u.$ (51)

Now, for any point $\hat{s}$ on the boundary of $\tilde{{\cal S}}^{\prime}$ at
least one of these polynomials must be null; otherwise, we could perturb
$\hat{s}$ in any direction and the polynomial inequalities (30) would still
hold. It follows that any point $\hat{s}$ on the boundary of $\tilde{{\cal
S}}^{\prime}$ satisfies $g(\hat{s})=0$, where
$g(\hat{s})\equiv\prod_{i=1}^{u}G_{i}(\hat{s})$. In particular, we have that

$g\left(\nu,\frac{\arccos(\nu)}{\pi}\right)=0,$ (52)

for $\nu\in[1/2,1]$. This contradicts the fact that the inverse of cosine is a
transcendental function. ∎

##  6 Conclusion

In this work, we have studied the problem of deciding whether a number of
distributions correspond to the marginals of a 2D TI system, what we called
the MARGINAL problem. We found that this problem is exactly solvable in
scenarios of low local dimension and nearest or next-to-nearest neighbor
statistics. We also showed that a natural variant of the problem, where we
also demand symmetry under reflection, is solvable for all local dimensions.
For other scenarios, we proposed a general algorithm to approximately solve
the MARGINAL problem, as well as its dual, the ENERGY problem, where the goal
is to minimize a linear functional of TI marginals.

We also proved several no-go theorems concerning these two problems. We showed
that the ENERGY problem is undecidable in general, so we cannot expect to
identify the sets of TI marginals exactly for arbitrary $d$. We find that for
$d$ high enough, those sets are neither real polytopes nor semi-algebraic
sets. Our techniques to prove negative results relied on a correspondence,
proposed by Kari [25, 26], between aperiodic tilings and immortal points of
dynamical systems. Perhaps because of this, our upper bounds on the minimal
dimension over which the set of TI marginals ceases to admit a simple
description seem very poor. It is an open question how to lower those bounds.
Could it be that, already for dimensions of order $10$, we can experience the
transition from a rational polytope to a convex object where parts of the
boundary are smoothly curved? And, could it be that, for dimensions small
enough, the description of the sets ceases to be a polytope but nonetheless
admits a practical description via semidefinite programming?

Finally, we hope our methods and results can be applied to the study of other
thermodynamical quantities or out-of-equilibrium systems. An immediate follow-
up to our work would be to relate TI marginals to the maximum entropy per site
of the whole lattice configuration from which they originate. That way, we
would be able to compute interesting thermodynamical quantities of TI systems,
such as the free energy, at non-zero temperature. Such maximum entropy
extensions of TI marginals have been studied on the 1D Euclidean lattice and
the Bethe lattice [5], but nothing is known when the lattice is 2D Euclidean.
In this regard, our results on the uniqueness of the extendibility of the
extreme points of $d=2$ TI marginals suggest that a full characterization of
the set of achievable TI marginals plus maximum entropy in that scenario is on
the horizon.

M.N. acknowledges interesting and useful discussions with David Pérez-García.
The authors would like to thank Aernout van Enter for pointing out several
related works.

This work does not have any experimental data.

Both authors contributed equally to this work. Both authors gave final
approval for publication.

We have no competing interests.

This work was supported by the FQXi grant “The physics of events”.

## References

  * Baxter [2007] Rodney James Baxter.  _Exactly Solved Models in Statistical Mechanics_.  Dover Publications, 2007.
  * Wang et al. [2017] Zizhu Wang, Sukhwinder Singh, and Miguel Navascués.  Entanglement and Nonlocality in Infinite 1D Systems.  _Phys. Rev. Lett._ , 118:230401, Jun 2017.  10.1103/PhysRevLett.118.230401.  URL https://link.aps.org/doi/10.1103/PhysRevLett.118.230401.
  * Schlijper [1985] Antoine Gerard Schlijper.  On some variational approximations in two-dimensional classical lattice systems.  _Journal of Statistical Physics_ , 40(1):1–27, 1985.  10.1007/BF01010524.  URL http://dx.doi.org/10.1007/BF01010524.
  * Pivato [2001] Marcus Pivato.  Building a stationary stochastic process from a finite-dimensional marginal.  _Canadian Journal of Mathematics_ , 53(2):382–413, 2001.  10.4153/CJM-2001-016-3.  URL http://dx.doi.org/10.4153/CJM-2001-016-3.
  * Goldstein et al. [2017] Sheldon Goldstein, Tobias Kuna, Joel Louis Lebowitz, and Eugene Richard Speer.  Translation Invariant Extensions of Finite Volume Measures.  _Journal of Statistical Physics_ , 166(3):765–782, 2017.  10.1007/s10955-016-1595-8.  URL http://dx.doi.org/10.1007/s10955-016-1595-8.
  * Chazottes et al. [2012] Jean-René Chazottes, Jean-Marc Gambaudo, Michael Hochman, and Edgardo Ugalde.  On the finite-dimensional marginals of shift-invariant measures.  _Ergodic Theory and Dynamical Systems_ , 32(5):1485–1500, 2012.  URL http://dx.doi.org/10.1017/S0143385711000526.
  * Ruelle [1978] David Ruelle.  _Thermodynamic Formalism: The Mathematical Structures of Equilibrium Statistical Mechanics_.  Addison-Wesley, 1st edition, 1978.
  * Schlijper [1988] Antoine Gerard Schlijper.  Tiling problems and undecidability in the cluster variation method.  _Journal of Statistical Physics_ , 50(3):689–714, 1988.  10.1007/BF01026496.  URL http://dx.doi.org/10.1007/BF01026496.
  * Kuna et al. [2011] Tobias Kuna, Joel Louis Lebowitz, and Eugene Richard Speer.  Necessary and sufficient conditions for realizability of point processes.  _The Annals of Applied Probability_ , 21(4):1253–1281, 08 2011.  10.1214/10-AAP703.  URL http://dx.doi.org/10.1214/10-AAP703.
  * Grünbaum [2003] Branko Grünbaum.  _Convex Polytopes_ , volume 221 of _Graduate Texts in Mathematics_.  Springer, New York, 2nd edition, 2003.  URL http://dx.doi.org/10.1007/978-1-4613-0019-9.
  * Ziegler [1995] Günter Matthias Ziegler.  _Lectures on Polytopes_ , volume 152 of _Graduate Texts in Mathematics_.  Springer, New York, 1995.  URL http://dx.doi.org/10.1007/978-1-4613-8431-1.
  * Bochnak et al. [1998] Jacek Bochnak, Michel Coste, and Marie-Françoise Roy.  _Real Algebraic Geometry_ , volume 36 of _Ergebnisse der Mathematik und ihrer Grenzgebiete_.  Springer Berlin Heidelberg, 1998.  10.1007/978-3-662-03718-8.  URL http://dx.doi.org/10.1007/978-3-662-03718-8.
  * Nering and Tucker [1993] Evan D. Nering and Albert W. Tucker.  _Linear Programs and Related Problems_.  Academic Press, 1993.
  * Vandenberghe and Boyd [1996] Lieven Vandenberghe and Stephen Boyd.  Semidefinite programming.  _SIAM Review_ , 38(1):49–95, 1996.  URL http://dx.doi.org/10.1137/1038003.
  * Grötschel et al. [1988] Martin Grötschel, László Lovász, and Alexander Schrijver.  _Geometric Algorithms and Combinatorial Optimization_ , volume 2 of _Algorithms and Combinatorics_.  Springer Berlin Heidelberg, 1988.  10.1007/978-3-642-97881-4.  URL http://dx.doi.org/10.1007/978-3-642-97881-4.
  * Matoušek and Gärtner [2007] Jiří Matoušek and Bernd Gärtner.  _Understanding and Using Linear Programming_.  Universitext. Springer, Berlin, Heidelberg, 2007.  10.1007/978-3-540-30717-4.  URL http://dx.doi.org/10.1007/978-3-540-30717-4.
  * Williams [1986] H. Paul Williams.  Fourier’s Method of Linear Programming and Its Dual.  _The American Mathematical Monthly_ , 93(9):681–695, 1986.  10.2307/2322281.  URL http://www.jstor.org/stable/2322281.
  * McCoy and Wu [2014] Barry M McCoy and Tai Tsun Wu.  _The Two-Dimensional Ising Model_.  Dover Publications, 2nd edition, 2014.
  * Wu [1982] Fa-Yueh Wu.  The Potts model.  _Rev. Mod. Phys._ , 54:235–268, Jan 1982.  10.1103/RevModPhys.54.235.  URL http://link.aps.org/doi/10.1103/RevModPhys.54.235.
  * [20] See Supplemental Material at [URL will be inserted by publisher] for proof.
  * Lörwald and Reinelt [2015] Stefan Lörwald and Gerhard Reinelt.  PANDA: a software for polyhedral transformations.  _EURO Journal on Computational Optimization_ , pages 1–12, 2015.  ISSN 2192-4406.  10.1007/s13675-015-0040-0.  URL http://dx.doi.org/10.1007/s13675-015-0040-0.
  * Wang [1961] Hao Wang.  Proving Theorems by Pattern Recognition — II.  _Bell System Technical Journal_ , 40(1):1–41, 1961.  10.1002/j.1538-7305.1961.tb03975.x.  URL http://dx.doi.org/10.1002/j.1538-7305.1961.tb03975.x.
  * Berger [1966] Robert Berger.  _The Undecidability of the Domino Problem_.  Number 66 in Memoirs of the American Mathematical Society. American Mathematical Society, 1966.
  * Jeandel and Rao [2015] Emmanuel Jeandel and Michael Rao.  An aperiodic set of 11 Wang tiles.  _arXiv:1506.06492_ , 2015.  URL https://arxiv.org/abs/1506.06492.
  * Kari [1996] Jarkko Kari.  A small aperiodic set of Wang tiles.  _Discrete Mathematics_ , 160(1):259 – 264, 1996\.  10.1016/0012-365X(95)00120-L.  URL http://www.sciencedirect.com/science/article/pii/0012365X9500120L.
  * Kari [2008] Jarkko Kari.  On the Undecidability of the Tiling Problem.  In Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors, _SOFSEM 2008: Theory and Practice of Computer Science_ , volume 4910 of _Lecture Notes in Computer Science_ , pages 74–82. Springer Berlin Heidelberg, 2008.  10.1007/978-3-540-77566-9_7.  URL http://dx.doi.org/10.1007/978-3-540-77566-9_7.
  * Niven [1956] Ivan Niven.  _Irrational Numbers_.  Number 11 in Carus Mathematical Monographs. Mathematical Association of America, 1956.
  * Bierstone and Milman [1988] Edward Bierstone and Pierre D. Milman.  Semianalytic and subanalytic sets.  _Publications Mathématiques de l’Institut des Hautes Études Scientifiques_ , 67(1):5–42, 1988.  10.1007/BF02699126.  URL http://dx.doi.org/10.1007/BF02699126.