April 24, 2014

November 16-21, 2009
Workshop on Computational Differential Geometry, Topology, and Dynamics

Talk Titles and Abstracts

Zin Arai (Hokkaido)
Dror Bar-Natan (Toronto)
Carlos Beltran (Cantabria)
Martin Berz (Michigan State)
Ilia Binder (Toronto)
Mark Braverman (Microsoft Research)
Nathan Dunfield (Illinois)
Herbert Edelsbrunner (Duke)
Joel Hass (UC, Davis)
Pat Hooper (Northwestern)
Angel Jorba (Barcelona)*
Svetlana Katok (Penn State)
Stefano Luzzatto (ICTP)
Assaf Naor (NYU )*

Igor Pak (UCLA)
Roland Roeder (Stony Brook)
Saul Schleimer (Warwick)
Richard Schwartz (Brown)
Carles Simó (Universidad de Barcelona)
Sergei Tabachnikov (Penn State)
Morwen Thistlethwaite (Tennessee)
Dylan Thurston (Barnard College, Columbia)
Warwick Tucker (Uppsala)
Shmuel Weinberger (Chicago)
Daniel Wilczak (Bergen)
Yosef Yomdin (Weizmann Institute)
Piotr Zgliczynski (Jagiellonian)
* may be confirmed

Zin Arai (Hokkaido University)
Rigorous verification of uniform hyperbolicity, subshifts of finite type and the pruning front

In this talk, we propose a rigorous computational algorithm for proving uniform hyperbolicity of dynamical systems. We avoid the difficulty of constructing hyperbolic splittings by introducing quasi-hyperbolicity, which is computationally much more tractable than uniform hyperbolicity.

We also discuss how to describe the dynamics of hyperbolic invariant sets. That is, we give some algorithms to rigorously construct a conjugacy to subshifts of finite type. Using this algorithm, we compute the exact value of the topological entropy of the real Henon map for many regions of parameter values.

Furthermore, applications of the hyperbolicity algorithm include rigorous computation of the monodromy action of the complex Henon map, which turns out to be closely related to the pruning front theory, a generalization of the kneading theory to higher dimensional systems.

Dror Bar-Natan (Toronto)
Dessert: Hilbert's 13th Problem, in Full Colour

To end a week of deep thinking with a nice colourful light dessert, we will present the Kolmogorov-Arnol'd solution of Hilbert's 13th problem with lots of computer-generated rainbow-painted 3D pictures.

In short, Hilbert asked if a certain specific function of three variables can be written as a multiple (yet finite) composition of continuous functions of just two variables. Kolmogorov and Arnol'd showed him silly (ok, it took about 60 years, so it was a bit tricky) by showing that ANY continuous function f of any finite number of variables is a finite composition of continuous functions of a single variable and several instances of the binary function "+" (addition). For f(x,y)=xy, this may be xy=exp(log x + log y). For f(x,y,z)=x^y/z, this may be exp(exp(log y + log log x) + (-log z)). What might it be for (say) the real part of the Riemann zeta function?

The only original material in this talk will be the pictures; the math was known since around 1957.


Carlos Beltran (Universidad de Cantabria)
A difficult minimization problem: the distribution of points in the sphere

Given N points in the 2-dimensional sphere, the logarithmic potential is the sum of the logs of the inverses of the Euclidean distances between the points. The 7th problem in Smale's list of problems for the XXI Century asks, how to distribute N points in the 2-dimensional sphere in such a way that the logarithmic potential is minimized - or almost minimized? In the talk I will present an overview of the history and progress of this problem, and present some recent results which relate it to the distribution of the condition number for polynomial solving. Home-made experiments with surprising conclussions will also be presented. There may be more questions than answers in this talk.


Ilia Binder (Toronto)
Walk on Sphere algorithm and boundary geometry

Walk on Spheres algorithm is a standard algorithm for solving Dirichlet problem. We discuss the relation of the rate of convergence of this algorithm and certain fine geometric properties of the domain boundary. This is a joint work with Mark Braverman (Microsoft Research/University of Toronto)

Mark Braverman (Microsoft Research)
Computability and Complexity of Julia Sets

In this talk we will present a survey on the computational properties of quadratic Julia sets.

Nathan Dunfield (Illinois)
Practical solutions to hard problems in 3-dimensional topology.

Many fundamental problems in 3-dimensional topology are known to be algorithmically solvable, using tools ranging from normal surface theory to hyperbolic geometry. However, most of these algorithms are too slow to be of use in any interesting example, and in fact some of these problems are known to be NP-hard or worse. I will discuss other methods, based on various heurisitics, randomization, and hyperbolic geometry, which can effectively solve some of these problems in practice. Particular questions of interest will be whether a 3-manifold fibers over the circle, its Heegaard genus, and the rank of its fundamental group. I will conclude with a brief demonstration of SnapPy, a modern Python interface to Jeff Weeks SnapPea.

This is joint work with (separately) Dinakar Ramakrishnan, Helen Wong, and Marc Culler.


Herbert Edelsbrunner (Duke University)
Measuring with algebra

Persistent homology is an algebraic method for measuring the scale of a homology class in a filtration. Taking the sublevel sets of a real-valued function, we get a measure on the features that are born and die as we increase the threshold. This bridge between algebra and measure theory is solidified by results about the stability of the diagram we use to express persistence. Using the bottleneck distance for diagrams, we get stability for general, tame functions. Using the Wasserstein distance, we get stability for Lipschitz functions on a large class of spaces. Generalizing the theory
from filtrations to zigzag modules, we extend the differential notion of transversality to a measure and get stability for intersections. These stability results have plenty of ramifications inside and outside mathematics.


Joel Hass (University of California, Davis)
Unknot diagrams requiring a quadratic number of Reidemeister moves to untangle

It is usually more difficult to obtain lower bounds on the computational complexity of a problem than to obtain upper bounds. Several years ago, in work with
Lagarias, we obtained exponential upper bounds on the number of Reidemeister moves required to pass from an n crossing diagram of the unknot to the trivial diagram.

In recent work with Tahl Nowik, we found a sequence of unknot diagrams for which the minimum number of Reidemeister moves required to pass to the trivial diagram is quadratic with respect to the number of crossings. The result is proved by introducing a new invariant of knot diagrams.


Pat Hooper (Northwestern University)
Billiards in nearly isosceles triangles

It is a wide open question if polygons always have periodic billiard paths. This question is unknown even for triangles. In this talk, I will explain why nearly isosceles triangles have periodic billiard paths.

While not proved using a computer, this result is ``computer inspired.'' I will demonstrate McBilliards, a program used to investigate periodic billiard paths in triangles. I will use this program to illustrate the theorem alluded to above, and to guide the audience through the main ideas in the proof.

Both the program McBilliards and the mathematics mentioned above are joint work with R. Schwartz.


Svetlana Katok (Pennsylvania State University)
Reduction theory and coding of geodesics on the modular surface.

In this talk I will describe two "computer inspired" results related to coding of geodesics on the modular surface. The first result deals with one-dimensional maps related to a family of (a,b)-continued fractions. Numerical experiments led us to formulate and eventually prove sufficient condition for validity of the Reduction theory conjecture, proposed by Don Zagier, that states that the associated natural extension maps have attractors with finite rectangular structure where every point of the plane is mapped after finitely many iterations. I will show that the structure of these attractors can be ``computed" from the data (a,b), and give a dynamical interpretation of the ``reduction theory" that underlines these constructions.

The second result answers a question when arithmetic coding via "minus" continued fractions (a=-1,b=0) coincides with the geometric coding that consists of recording the successive sides of the standard fundamental region cut by the geodesic. This question is related to complexity of the geometric coding and identification of a maximal 1- step topological Markov chain of admissible geometric codes. Some of these results are joint with Ilie Ugarcovici.

Stefano Luzzatto (International Centre for Theoretical Physics (ICTP))
Deciding the undecidable: Probabilistic arguments versus finite resolution dynamics

Many families of dynamical systems exhibit so many bifurcations that it is essentially impossible to determine the precise dynamical properties corresponding to a specific parameter. In this talk we will discuss two possible approaches to this issue. One is to prove that certain dynamical phenomena occur for a positive Lebesgue measure set of parameters, thus giving in some sense a "probability" that the chosen parameter satisfies the required conditions. This approach has been applied since 1981 to some families of one-dimensional and strongly dissipative higher dimensional maps (though explicit quantitative estimates have been obtained only in 2006 - Luzzatto & Takahasi, Nonlinearity), but at the moment we are not even close to obtaining such results for more general systems.

In this talk we will focus on an alternative approach suggested recently by Luzzatto and Pilarczyk which applies to much more general dissipative systems. Rather than obtaining a result about the probability that a certain system satisfies certain conditions we develop some notions which allow us to prove rigorous results about a specific parameter value at the cost of describing the dynamics of the systems only at a finite resolution. As an example of the application of these ideas we prove rigorously by computer-assisted calculations that the Henon map for Henon's classical parameter values is "topologically mixing at all resolutions coarser than 10^-5".



Igor Pak, UCLA
Acute triangulations of polytopes

A simplex in R^d is called acute if all its dihedral angles are < pi/2. An acute triangulation of a polytope is a triangulation (as a CW-complex) into acute simplices. The problem of finding acute triangulations is of interest in discrete geometry, the finite element method, and other applications. In this talk I will survey a number of known and recent results on acute triangulations.  In particular, we describe a complete solution for d-dim cubes, which involve delicate computations (in 3-dim) and a topological (negative) argument in higher dimensions.  We conclude with some open problems. Part of the talk is based on the recent paper joint with Eryk Kopczynski and Piotr Przytycki.


Roland Roeder (SUNY Stony Brook)
Computing arithmetic invariants for hyperbolic reflection groups

I will demonstrate a collection of computer scripts written in PARI/GP to compute the commensurability invariants known as the invariant trace field and invariant quaternion algebra for reflection groups determined by compact polyhedra in H^3. These scripts also allow one to determine arithmeticity of such groups and the isomorphism class of the invariant quaternion algebra by analyzing its ramification. (They are similar to the program SNAP that does the same thing for hyperbolic manifolds of finite volume.)

I present many computed examples of these invariants. This is enough to show that most of the groups that we consider are pairwise incommensurable. For pairs of groups with identical invariants, not all is lost: when both groups are arithmetic, having identical invariants guarantees commensurability. We discover some "unexpected" commensurable pairs this way.

I will conclude by describing a notion of mutation for polyhedra which enables one to construct many (often non-arithmetic) pairs of polyhedra having the same invariant trace field and quaternion algebras. For these mutant pairs of polyhedra it is typically an open question whether the reflection groups are commensurable.

This is joint work with Omar Antolin-Camarena and Gregg Maloney.


Saul Schleimer (University of Warwick)
Twister: building triangulations of surface bundles

I will explain the main ideas behind Twister, a program written by Tracy Hall and myself, that produces triangulations based on Dehn twist data. We have used the program to produce a census of bundles in genus two. Twister is also useful for producing counterexamples. At the end of the talk I will demo the program.


Richard Schwartz (Brown University)
Polygonal Outer Billiards

Outer billiards is a dynamical system consisting of a discrete sequence of moves done on the outside of a convex shape in the plane. I will demonstrate some graphical user interfaces I wrote which help explore the geometry and dymamics of outer billiards when it is defined relative to a polygon. Along the way, I'll sketch my solution of the Moser-Neumann problem, which asks if one can have unbounded orbits in an outer billiards system. The main result is that outer billiards relative to a kite has unbounded orbits if and only if the kite is irrational.

Carles Simó (Universidad de Barcelona)
The role of Dynamical Systems in Celestial Mechanics. Applications to Astronomy and Astrodynamics

Sergei Tabachnikov (Penn State University)
Pentagrama Myrificum, Old wine into new wineskins

The Pentagram map is a projectively natural iteration on plane polygons introduced by R. Schwartz 17 years ago. Computer experiments show that the Pentagram map exhibits quasi-periodic behavior. Based on joint work with R. Schwartz and V. Ovsienko, I shall describe the Pentagram map as a completely integrable system. A by-product of this research is a collections of new configuration theorems of classical projective geometry, discovered in computer experiments. A number of open problems will be formulated.

Morwen Thistlethwaite (Tennessee)
The exact computation of some representation varieties

A method is described for the exact computation of representation varieties of groups having small presentations, for example triangle groups or fundamental groups of hyperbolic 3-manifolds with small volume. We are particularly interested in deforming the canonical SO(n,1)-representation of the group of a hyperbolic n-manifold or orbifold into SL(n+1,R) or into SU(n,1), this last group bringing us to the intriguing world of complex hyperbolic geometry.


Dylan Thurston (Barnard College, Columbia)
Rigidity of Graphs

When do the lengths of the edges of a straight-edge framework determine the positions of the vertices? The problem comes up all the time in applications ranging molecular biology to sensor networks to computer vision. But it also turns out that the problem is NP-hard in general. It becomes easier if you require the initial position to be generic; then there is a polynomial algorithm based on the \emph{stress matrix} of the graph. But even in this case, actually reconstructing the positions from the edge-length is difficult. There is a good algorithm in case the framework is \emph{universally} rigid: the edge lengths determine the framework independently of the embedding dimension. There is again a characterization of such frameworks in terms of the stress matrix.
This is joint work with Steven Gortler and Alex Healy.

Warwick Tucker (Uppsala)
A rigorous lower bound for the stability regions of the quadratic map

We establish a lower bound on the measure of the set of stable parameters a for the quadratic map $Q_a(x) = ax(1?x2)$. For these parameters, we prove that $Q_a$
either has a single stable periodic orbit or a period-doubling bifurcation. From this result, we also obtain a non-trivial upper bound on the set of stochastic parameters for $Q_a$.

This is joint work with Daniel Wilczak.

Shmuel Weinberger (Chicago)
Persistent homology of data, loop spaces, and landscapes.

Persistent homology is a useful tool for dealing with "errors", whether noise in data, or geometrical perturbations to topological invariants. In this talk, I will explain some formalism and recast some old theorems in these terms, giving a new proof or so, explain the meaning of long and short "persistence intervals" and speculative on some further directions.


Daniel Wilczak (University of Bergen)
Rigorous numerics for homoclinic tangencies

We propose a method for computer-assisted verification of the existence of homoclinic tangencies for maps. The method is geometric in the spirit and assumes that the map is of class C^2 for which we can compute enclosures for values and derivatives up to the second order. Having a rigorous solver for variational equations one can apply the method to Poincare maps.

The method has been successfully applied to the Henon map and the forced-damped pendulum equation.

The main numerical result states that a suitable Poincare map for the
forced-damped pendulum

x'' + bx' + sin(x) = cos(t)

admits a homoclinic tangency unfolding generically for some parameter value beta close to 0.2471.

This is a joint work with Piotr Zgliczynski


Yosef Yomdin (The Weizmann Institute of Science)
I. Center-Focus Problem for Abel equation, Moment vanishing, Compositions, and Mathieu and Zhao conjectures

Center-Focus problem for Abel equation (1) y'=p(x)y^2+q(x)y^3 on [a,b] is to give conditions on p and q for all the solutions of (1) to satisfy y(a)=y(b). This problem turns out to be closely related with the vanishing problem for the moments of the form \int_a^b P^k(x)Q(x) dP(x), with P=\int p, Q=\int q. Recently F. Pakovich and M. Muzychuk completely solved the Moments vanishing problem for p,q - polynomials. The answer is given in terms of certain composition relations between P and Q. For Laurent polynomials situation is more complicated. In a very recent work F. Pakovich has achieved a serious progress in understanding vanishing conditions for rational functions and, in particular, for Laurent polynomials. In particular, new relations with the Mathieu conjecture in representations of compact Lie groups have appeared, and (through the recent work of Wenhua Zhao) to certain questions closely related to the Jacobian conjecture.

Moment vanishing problem is closely related to the "moment inversion problem": reconstruct the functions P and Q from their known moments. The corresponding question for Abel equation (1) provides a generalization of the Center-Focus problem. It also appears naturally in Signal Processing. We plan to present this part in a separate talk at this workshop.

Yosef Yomdin (The Weizmann Institute of Science)
II. "Algebraic" reconstruction of Signals and Images from Fourier Data

We discuss the problem of reconstruction of signals with singularities from integral measurements (like Fourier coefficients or moments). The "Algebraic Reconstruction" assumes rather detailed a priori information on the form of the signals: we need their parametric models. But assuming such models are known, Algebraic Reconstruction promises a very high resolution, significantly better than with the "Compressed Sensing" approach. The mathematics involved strongly resembles "the moment inversion problem" considered in the first talk at this workshop, in connection with the Center-Focus problem for Abel differential equation. We give an overview of some essential mathematical ingredients in Algebraic Reconstruction approach.

However, in order to apply Algebraic Reconstruction method to images, we need their "parametric representation". Is it possible at all? This is a well known and very difficult problem (sometimes called "vectorization of photo-realistic images"): Develop a representation scheme for images, based on "geometric models", and satisfying the following two requirements:

- The representation preserves a full visual quality of high resolution photo-realistic images.
- The total data volume in the representation is significantly lower than in the original pixel image ("compression").

Here "geometric models" are assumed to be analytic parametric expressions, capturing faithfully a local visual content of the image. In order to satisfy the "compression" requirement their scale must be of order at least of a few pixels. This problem is well known to be extremely difficult. On the other hand, even its partial solution could provide strong tools in a wide variety of imaging problems, in particular, in image analysis and processing. We plan to discuss the "state of the art" in the geometric image modelization.
Finally, we plan to shortly present a problem of capturing image objects with high-level models. As an application, we shall discuss a "Photo-Animator" tool allowing one to easily produce complicated video-clips from a single photo.


Piotr Zgliczynski (Jagiellonian University)
Heteroclinic connections between fixed points for Kuramoto-Sivashinki PDE, a computer assisted proof

We will discuss the method of self-consistent bounds for dissipitaive PDEs. This methods allows for a direct application of tools from dynamical system theory (finite dimensional) to dissipative PDE. This includes both: abstract theorems and rigours algorithms for integration of PDEs. As an example we will discuss a computer assisted proof of the existence of some heteroclinic connections between fixed points for Kuramoto-Sivashinski PDE on the line with odd and periodic boundary conditions.

The proof consists of the following stages:
1) the proof of the existence of two fixed points, "the source" and "the target"
2) rigorous estimates for the attracting region around the target point
3) rigorous estimates for one dimensional unstable manifold of the source point
4) rigorous integration of PDE - the propagation of the unstable manifold of the source until it enters the basin of attraction of the target point.



Back to top