Posts Tagged ‘Dynamics’

Renaud Leplaideur a exposé au groupe de travail de théorie ergodique ses tout derniers travaux avec H. Bruin, A.T. Baraviera et A.O. Lopes. Ils ont en particulier construit, pour tout 0<a<1, une application f_a:S^1\to S^1 de classe C^1 présentant une transition de phase et un compact K, invariant, uniquement ergodique et indifférent: (i) f_a'\geq 1; (ii) (f_a')^{-1}(1)=K; (iii) le potentiel - \log f_a' possède plusieurs mesures d’équilibre.

Ceci généralise l’exemple bien connu de Manneville-Pomeau. Plusieurs autres résultats suggèrent des liens entre cette non-unicité et une certaine invariance par renormalisation du potentiel, sans qu’il soit clair qu’il s’agisse là d’un phénomène général ou encore d’un analogue mathématique du lien entre phénomène critique et invariance par renormalisation établi et exploité par les physiciens théoriciens depuis Wilson et les années 1970.

Read Full Post »

Real-world computers make mistakes, in the sense that once in a while an instruction is executed incorrectly, perhaps because of a corrupted disk. One could naively think that, given, a maximum acceptable probability of an incorrect final result, this would impose a bound on the complexity of possible computation or require an exponential number of repetitions. However (and similarly to the central result of Shannon’s information theory), one can do much better as was explained by Péter Gàcs in his mini-course in Marseilles. P. Gàcs slides can be found here.

Computers are modelized as probabilistic cellular automata: the new states (indexed by \mathbb Z^d are independent conditioned on the old states and each follows a law which is a fixed function of the old states in a neighborhood.  These local transitions are assumed to be “noisy”, i.e., all states have positive probability.

Remark. This “noisiness” does not imply ergodicity (in the sense of Markov chains, i.e., there is a unique stationary probability measure), which is fortunate since ergodicity implies that the initial data is eventually forgotten!

Question. When d=2, the voting model is expected to be non-ergodic but there is a proof only for a continuous time version with specific parameters that can be related to the Ising model.

It is observed that one-dimensional cellular automata cannot compute reliably in the presence of noise. In a way, there is not enough long range communication for cells on the boundary of an erroneous island to tell on which side is the island… The main result of the first lecture was the following:

Theorem (3D-simulation with infinite redundancy). Let U be some one-dimensional cellular automaton. Then there is a 3-dimensional cellular automaton V and z constant C such that, if the local transitions are noisy but with sufficiently small error probability \epsilon, the probability that a given V-state at site (i,j,k) at time n is different from the U-state at site i at the same time is bounded by C\epsilon.

There is a version of this result with finite redundancy. Specifically, for a computation which requires a space S and a time T and a maximal error probability at a given site of $\delta>0$, one can replace the infinite extension \mathbb Z\times\mathbb Z^2 by a finite one \{0,\dots,S\}\times \times\{0,\dots,N\}^2 where N=\mathcal O(\log(ST)/\delta).

The proof relies on a decomposition of the occurence of the “faults” in a hierarchical structures (at level 0, one has only distant single faults, at level 1, one also allows more distant small balls containing faults, etc.).

The second lecture, dealing with reliable computations in 2D, will be reviewed in the following post.

Read Full Post »

Frédéric Le Roux has written a very lucid exposition of the Alpern genericity theorem. This theorem states that the same ergodic properties are generic in the set Auto(T^d) of volume-preserving measurable transformations and in the set Homeo(T^d) of volume-preserving  homeomorphisms.

More precisely,  endow Auto(T^d)   with the weak topology, i.e., the coarsest generated by \mu\mapsto\mu(A), for all measurable subsets A and equip Homeo(T^d)  with the uniform distance.

The theorem considers any P\subset Auto(T^d)  invariant under volume-preserving measurable isomorphisms. It states that P  is a dense G_\delta subset of Auto(T^d) if and only if P\cap Homeo(T^d) is itself a dense G_\delta subset of Homeo(T^d).

Read Full Post »

Kevin McGoff gave a talk at Orsay on his work on the theory of entropy srtuctures and symbolic extensions. This theory was founded by Mike Boyle and Tomasz Downarowicz, among others.

This theory relates the continuity properties of the measure-theoretic entropy function with the existence of symbolic topological extensions with measure-theoretic entropies as close as possible to those of the initial system. This theory ascribes to any topological dynamical system an order of accumulation. M. Boyle and T. Downarowicz have shown that this is a countable ordinal.

David Burguet and K. McGoff have shown that any countable ordinal can be achieved by some topological dynamics. The proof relies on a realization theorem of T. Downarowicz and S. Serafin.

K. McGoff explained how he was able, by a more precise and direct construction to achieve the same on any prescribed compact manifold. The transformation can be chosen to be homeomorphic if the dimension is 2 or more.

Read Full Post »

Erwan Lanneau gave a talk in Orsay about his work on surfaces of translation. Pseudo-Anosov homeomorphisms are homeomorphisms of such surfaces which are affine away from the singular set of the surface and whose differential is hyperbolic. The dilation factor is the dominant eigenvalue of that differential. It is a Perron number.

The minimum of the dilation factor for given genus is known for geni 1 and 2 only (the techniques behind could be extended to genus 3 but not farther). One also knows that c_1/g\leq \log \delta(g)\leq c_2/g.

The main result of the talk is that the above does not hold when restricted to a given type of translation surfaces. More precisely, the moduli space of translation surfaces of given genus splits into connected components (at most three), one of them corresponding to hyperellipticity and the following holds:

Theorem (Boissy-Lanneau) Let \Phi be a pseudo-Anosov on a hyperelliptic translation surface of genus g admitting an involution with 2g+2 fixed points). Assume that \Phi has a unique singularity. Then its dilation is strictly greater than \sqrt{2} (but approach this value as g\to\infty).

Read Full Post »

Most of topological dynamics studies systems of the form T:X\to X where T is a continuous self-map and X is a compact metric space. One approach is to “reduce” such systems to symbolic dynamical system, i.e., \sigma:S\to X where S is a closed subset of \{1,\dots,d\}^{\mathbb Z} and \sigma((x_n)_{n\in\mathbb Z})=(x_{n+1})_{n\in\mathbb Z} such that \sigma(S)=S.

J. Auslander asked about the obstructions for a topological system T:X\to X to have a symbolic extension, i.e., a symbolic system \sigma:S\to S and a continuous surjection \pi:S\to X commuting with the dynamics: \pi\circ\sigma =T\circ\pi. There is an obvious one: a symbolic system (and therefore its topological factors) has finite topological entropy. Is there any other?

M. Boyle showed that this was indeed the case. With D. Fiebig and U. Fiebig, he showed that asymptotically h-expansive systems (including C^\infty self-maps of compact manifolds by a result of mine based on Yomdin’s theory) always have a “nice” symbolic extension. T. Downarowicz and S. Newhouse showed that generic C^1 map have no symbolic extension whatever, leaving open the question of diffeomorphisms with finite smoothness.

T. Downarowicz and A. Maas showed that C^r interval maps also always have symbolic extensions for 1<r<\infty.

David BURGUET has finally proved the same for arbitrary C^2 surface diffeomorphisms, see his preprint here.

Behind these works there is a rich and beautiful topological/ergodic/functional-analytical theory of entropy (called the entropy structure by T. Downarowicz) which does yet have the audience it deserves, in my opinion.

Read Full Post »

I have shown that, like diffeomorphisms, piecewise affine surface homeomorphisms are approximated in entropy by horseshoes, away from their singularities. It follows in particular that their topological entropy is lower-semicontinuous: a small perturbation cannot cause a macroscopic drop in entropy.

The continuity of the entropy for such maps had been an open problem for some time. Rigorous numerical estimates by Duncan SANDS and Yutaka ISHII seemed to suggest some discontinuous drops, but investigation at a small scale suggested these drops to be steep yet continuous variations.

Izzet B. YILDIZ has solved this question by finding for Lozi maps f_{a,b}(x,y)=(1-a|x|+by,x) on \mathbb R^2, small numbers \epsilon_1,\epsilon_2>0 such that, setting (a,b)=(1.4+\epsilon_1,0.4+\epsilon_1), for all 0<\epsilon<\epsilon_2:

  • h_{top}(f_{a,b})=0;
  • h_{top}(f_{a+\epsilon,b})>\frac14\log\frac12(\sqrt{5}+1).

The verification turns out to be quite simple (once you know where to look!). The non-wandering set of f_{a,b} is shown to be reduced to be reduced to the fixed points of its fourth iterates, yielding the zero entropy immediately. f_{a+\epsilon,b} on the other hand is shown to admit 2 disjoint closed quadrilaterals U,V such that f^4(U) hyperbolically crosses both U and V and f^4(V) hyperbolically crosses U. This means that the sides of U and V can be branded alternatively s and u with the following property. The image of a u side crosses each of U,V it meets, intersecting both their s sides and none of their u sides. This again yields the entropy estimate.

Read Full Post »

Older Posts »