Some Questions of Interest
Here are some (of many) math problems/topics I am currently interested in.
Some of these, I think about more actively, while others only from time to time.
I try to gradually elaborate on each of these problems.
If you have any answer, idea or comment, I would be very glad to hear.
Metastability in the hardcore models
[ +/]
Phase transitions and stability against noise in cellular automata and tilings
[ +/]
 The density classification problem
 Stability of cellular automata against noise
 Toom's cellular automata
 Gacs's construction
 ...
The “central limit theorem” of finite (or compact) groups
[ +/]
Do deterministic cellular automata obey the 2nd law of thermodynamics?
[ +/]
 An example of a nonadditive cellular automaton with randomization property
 Q2R cellular automata
 Different proofs of the randomization property of the XOR cellular automaton
 Techniques for proving ergodicity of probabilistic cellular automata
 Randomization in other dynamical systems
(e.g., the $(2 \times, 3 \times)$ model, normal numbers, ...)
 ...
Invariant measures of cellular automata with sufficiently chaotic behavior
[ +/]

Do “typical” configurations exist?
[ +/]
Firstorder transitions and breaking of translation symmetry in lattice models
[ +/]
(December 29, 2013)
The melting of ice into water is an example of a firstorder phase transition.
A phase transition refers to a drastic change in the macroscopic
state of a system when a parameter of the system (temperature in case of melting) is varied.
A firstorder transition occurs when the transformation is discontinuous in the varying parameter.
The melting process is discontinuous because during the transition, the system absorbs
a certain amount of heat (the latent heat) without changing its temperature,
hence a jump in the internal energy from a temperature slightly below the transition point
to a temperature slightly above the transition point.
In statistical mechanics, a macroscopic state of a lattice model
that respects the translational symmetry and has
a given energy density $e$ is described by a probability measure
on the set of microscopic configurations that is invariant and ergodic
under the group of translations, has expected energy density $e$,
and has maximum entropy among all the other candidates.
The ergodicity requirement is to ensure that the density of
local observables (the “macroscopic” observables) are almost surely constant (i.e., deterministic).
Such measures are characterized,
by the theorem of DobrushinLanfordRuelle, as ergodic translationinvariant Gibbs measures,
although the energy density $e$ appears in this characterization only implicitly.
The explicit parameter corresponds to the thermodynamic temperature, which controls
the energy density: for each energy density $e$, there is a unique temperature $T$
such that any translationinvariant Gibbs measure with expected energy density $e$ has temperature $T$.
The Gibbs measures that are not translationinvariant presumably describe
the macroscopic states in which the translational symmetry is broken.
This is justified by extrapolation, or by the local version of the above variational approach.
Here again we should consider only Gibbs measures under which a suitable class of
“macroscopic” observables (the tailmeasurable observables)
are deterministic.
A Gibbs measure at a given temperature that is not “macroscopically deterministic”
can be identified with a probability distribution on the set of
those that are “macroscopically deterministic”,
hence describing a partial knowledge of the macroscopic state.
Here is the problem:
Suppose the system that is being modeled is at the (firstorder) transition temperature (melting point)
but is not given enough heat to pass the transition completely.
How should such an intermediate state be understood in the above setting?
More specifically, assume that during the transition, the internal energy density
jumps from a value $e_1$ to a value $e_2$ (so the latent heat is $e_2e_1$), and consider a value $e$
such that $e_1 < e < e_2$.
Does there exist an ergodic translationinvariant Gibbs measure
with energy density $e$?
How does a typical configuration of an intermediate state look like?
Does the occurrence of a firstorder transition necessarily imply
the breaking of translational symmetry at the transition point?
Statistical mechanics description of quasicrystals
[ +/]
 Is there a latticegas model with a quasicrystaline phase?
 Stability of aperiodic Wang tiles at positive temperature
 The construction of DurandRomashchenkoShen
 Lowtemperature stability of nonperiodic ground configurations
 Is the presence of phase transitions in a lattice gas model algorithmically decidable?
 Is it decidable whether a $d$dimensional strongly irreducible
subshift of finite type is intrinsically ergodic
(i.e., has a unique measure of maximal entropy)?
 ...
Coupling method for random fields and Markov processes on them
[ +/]
 Coupling method of Dobrushin, Wasserstein, Holley, ... and its variants
 Disagreement percolation method of van den Berg and Maes
 Loss network representation and coupling from the past
 Renewal representation of Gibbs measures
 Coupling arguments for the uniqueness problem, ergodicity, and mixing time
 Coupling arguments for proving phase transitions
 ...
Matching, couplings, transportation, joinings, ...
[ +/]
Do the conservation laws of reversible cellular automata have a decidable theory?
[ +/]
Whether a cellular automaton satisfies a given conservation law
can be verified algorithmically. On the other hand, the question
whether a given cellular automaton has any nontrivial conservation law
is undecidable, even among onedimensional cellular automata.
Does this question remain undecidable on the subclass of
reversible (or surjective) cellular automata?
What are some examples of reversible/surjective cellular automata
with finitedimensional (but nontrivial) space of conservation laws?
Does every particleconserving cellular automaton have a particle flow?
[ +/]
Suppose we have a deterministic cellular automaton with a notion of particles
(say, each site is assumed to a have a certain number of particles
depending on its state)
such that the (relative) number of particles is preserved by the dynamics.
Is it always possible to devise a universal local and translationinvariant
recipe that describes the movement of particles on any starting configuration?
For onedimensional cellular automata, the answer is yes,
and there is a partial positive answer in two dimensions.
The general case is however open.
BanachTarski paradox for coin tosses
[ +/]
Description to come ... (but you may guess!)
...
