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 hard-core 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 non-additive 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?
First-order transitions and breaking of translation symmetry in lattice models
(December 29, 2013)
The melting of ice into water is an example of a first-order 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 first-order 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 Dobrushin-Lanford-Ruelle, as ergodic translation-invariant 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 translation-invariant Gibbs measure with expected energy density $e$ has temperature $T$.
The Gibbs measures that are not translation-invariant 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 tail-measurable observables)
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 (first-order) 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_2-e_1$), and consider a value $e$
such that $e_1 < e < e_2$.
Does there exist an ergodic translation-invariant Gibbs measure
with energy density $e$?
How does a typical configuration of an intermediate state look like?
Does the occurrence of a first-order transition necessarily imply
the breaking of translational symmetry at the transition point?
Statistical mechanics description of quasicrystals
- Is there a lattice-gas model with a quasicrystaline phase?
- Stability of aperiodic Wang tiles at positive temperature
- The construction of Durand-Romashchenko-Shen
- Low-temperature stability of non-periodic 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 non-trivial conservation law
is undecidable, even among one-dimensional 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 finite-dimensional (but non-trivial) space of conservation laws?
Does every particle-conserving 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 translation-invariant
recipe that describes the movement of particles on any starting configuration?
For one-dimensional cellular automata, the answer is yes,
and there is a partial positive answer in two dimensions.
The general case is however open.
Banach-Tarski paradox for coin tosses
Description to come ... (but you may guess!)