# Caltech–UCLA Logic Seminar

## (Aka Cabal Seminar)

The Logic seminar generally meets on Fridays, 2–3:30p.m., at Caltech or UCLA. Contact Alexander Kechris or Itay Neeman if you wish to give a talk.

Schedule of talks, going back to Fall 2016, in reverse chronological order:

# Logic Seminar: 12/15/2017 - 12/15/2018

 Friday Jan 12 2018 14:00-15:30 (MS 6221) Matthew Foreman (UCI) Classifying diffeomorphisms of the torus (part 2) Abstract. In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of compact manifolds. Notable progress was made by Halmos and von Neumann using spectral invariants. Later, Bernoulli shifts were classified by Ornstein using Kolmogorov's notion of entropy. In these talks we show that the general von Neumann problem is intractable in a rigorous sense: the collection of pairs of diffeomorphisms of the torus that are isomorphic is complete analytic — in particular not Borel. It follows that there is no inherently countable procedure for determining whether a given pair (S,T) is isomorphic. A problem closely related to the isomorphism problem is the Realization Problem: which abstract measure preserving transformations can be realized as diffeomorphisms of a compact manifold. The only known restriction is that the transformations must have finite entropy. As a byproduct of the anti-classification result stated above, we show that a large class of previously unknown examples can be realized smoothly. For example there are measure distal diffeomorphisms of the 2-torus of arbitrary countable ordinal height, and diffeomorphisms of the torus whose simplex of invariant measures is affinely homeomorphic to an arbitrary compact Choquet simplex. This latter results are proved by establishing a Global Structure Theorem that says that there is a categorical isomorphism between the collection of ergodic transformations with odometer factors and diffeomorphisms realized by the Anosov-Katok method off conjugacy.Hide

# Logic Seminar: 09/1/2016 - 12/14/2017

 Friday Dec 08 2017 14:00-15:30 (MS 6221) Henry Towsner (U Penn) Relatively Random First-Order Structures Abstract. The Aldous-Hoover Theorem gives a characterization of those random processes which generate "exchangeable" first-order structures. Exchangeable structures are precisely those where the "labels" of the points do not matter — they are random structures whose distribution remains the same when we permute the points. They therefore correspond to the structures we get when we sample countable substructures randomly from an ultraproduct; indeed, the original proof of the full Aldous-Hoover Theorem used ultraproducts, and the topic remains intimately tied to the way probability measures behave in ultraproducts. For some purposes, full exchangeability is too strong: we should consider only those permutations respecting some existing structures. A full Aldous-Hoover theorem is not always possible in this setting, and how much we recover turns out to depend on the amalgamation properties of M. Our goal in this talk is to explain the connection between exchangeability and model theoretic notions, without assuming much prior expertise in either.Hide Friday Dec 01 2017 14:00-15:30 (MS 6221) Omer Ben-Neria (UCLA) Singular stationarity Abstract. I will talk about Mutually Stationary sequences of sets. The notion of Mutual Stationarity was introduced by Foreman and Magidor in the 90s, and has been developed as a notion of stationarity for subsets of singular cardinals and as means to address some classical problems in set theory. We will discuss the basic concepts and describe several known and recent results.Hide Friday Nov 03 2017 14:00-15:30 (MS 6221) Matthew Foreman (UCI) Classifying diffeomorphisms of the torus (part 1) Abstract. In 1932 von Neumann proposed classifying the statistical behavior of diffeomorphisms of compact manifolds. Notable progress was made by Halmos and von Neumann using spectral invariants. Later, Bernoulli shifts were classified by Ornstein using Kolmogorov's notion of entropy. In these talks we show that the general von Neumann problem is intractable in a rigorous sense: the collection of pairs of diffeomorphisms of the torus that are isomorphic is complete analytic — in particular not Borel. It follows that there is no inherently countable procedure for determining whether a given pair (S,T) is isomorphic. A problem closely related to the isomorphism problem is the Realization Problem: which abstract measure preserving transformations can be realized as diffeomorphisms of a compact manifold. The only known restriction is that the transformations must have finite entropy. As a byproduct of the anti-classification result stated above, we show that a large class of previously unknown examples can be realized smoothly. For example there are measure distal diffeomorphisms of the 2-torus of arbitrary countable ordinal height, and diffeomorphisms of the torus whose simplex of invariant measures is affinely homeomorphic to an arbitrary compact Choquet simplex. This latter results are proved by establishing a Global Structure Theorem that says that there is a categorical isomorphism between the collection of ergodic transformations with odometer factors and diffeomorphisms realized by the Anosov-Katok method off conjugacy.Hide Friday Oct 20 2017 14:00-15:30 (MS 6221) Jeffrey Bergfalk (Cornell U.) The first omega alephs Abstract. In the early seventies, several decisive relations were noticed between the homological dimension and the cardinality of a small category - particularly for the cardinalities $\aleph_n$ $(n\in\mathbb{N})$. Those relations, in the case of $n=1$, are best understood in terms of Todorcevic's method of minimal walks on the countable ordinals; the higher-$n$-cases point, similarly, to generalizations of that method, and to $n$-dimensional incompactness principles correlated, for each $n$, to $\aleph_n$. All these are ZFC phenomena. How these principles behave on other cardinals is a largely open question. We discuss these matters, and some of their implications both in set theory and in algebraic topology.Hide Friday Oct 13 2017 14:00-15:30 (MS 6221) Kota Takeuchi (University of Tsukuba) Ramsey property and 2-Order Property Abstract. The notion of n-dependence was introduced by Shelah motivated to treat vector spaces with a bilinear form along NIP theories. One of the important tools analyzing the property is the Ramsey property of the class of ordered finite hyper graphs. Actually many of known results, preservation theorem under boolean combinations, finding a witness in a single variable and characterizing the property by generalized indiscernible can be implied from the Ramsey property. In this point of view we introduce the notion of 2-Order Property, which lies between Independent Property and 2-Independent Property, related a Ramsey class consisting of ladder-like graphs, and demonstrate that how the Ramsey property works well to prove similar results. The typical examples of 2-dependence are not 2-OP. So far, It is open if 2-OP is strictly weaker than 2-IP.Hide Wednesday Oct 04 2017 16:00-17:30 (MS 6221) Tobias Kaiser (Universitaet Passau) Asymptotics of parameterized exponential integrals given by Brownian motion on globally subanalytic sets Abstract. (Joint work with Julia Ruppert) Understanding integration in the o-minimal setting is an important and difficult task. By the work of Comte, Lion and Rolin, succeeded by the work of Cluckers and Miller, parameterized integrals of globally subanalytic functions are very well analyzed. But very little is known when the exponential function comes into the game. We consider certain parameterized exponential integrals which come from considering the Brownian motion on globally subanalytic sets. We are able to show nice asymptotic expansions of these integrals. (Note unusual day and time: Wednesday, 4pm.)Hide Friday Sep 29 2017 14:00-15:30 (MS 6221) Dana Bartosova (University of Sao Paulo) Free actions via graphs Abstract. A topological group admits a free action if there is a compact space on which it acts without fixed points. We translate this property into colorability of graphs, which leads us to questions of combinatorial nature. This is a joint work in progress with Vladimir Pestov.Hide Friday Jun 09 2017 14:00-15:30 (MS 6221) Danny Nguyen (UCLA) Complexity of short Presburger arithmetic Abstract. We study complexity of short sentences in Presburger arithmetic. Here by "short" we mean sentences with a bounded number of variables, quantifiers, inequalities and Boolean operations; the input consists only of the integers involved in the inequalities. The problem is motivated by the earlier work on counting integer points in polytopes and their projections in spaces of bounded dimension. We completely resolve the problem. There were some surprises along the way which we also explain. Joint work with Igor Pak.Hide Friday Jun 02 2017 14:00-15:30 (MS 6221) Anush Tserunyan (UIUC) Ergodic hyperfinite decomposition of countable Borel equivalence relations Abstract. A countable Borel equivalence relation $E$ on a probability space can always be generated in two ways: as the orbit equivalence relation of a Borel action of a countable group and as the connectedness relation of a locally countable Borel graph, called a graphing of $E$. When $E$ is measure-preserving, graphings provide a numerical invariant called cost, whose theory has been largely developed and used by Gaboriau and others in establishing rigidity results. A well-known theorem of Hjorth states that when $E$ is ergodic, treeable (admits an acyclic graphing), and has integer or infinite cost $n \le \infty$, then it is generated by an a.e. free measure-preserving action of the free group $\mathbf{F}_n$ on $n$ generators. We give a simpler proof of this theorem and a further development of our technique yields a strengthening of Hjorth's theorem: the action of $\mathbf{F}_n$ can be arranged so that each of the $n$ generators alone acts ergodically. This is joint work with Benjamin Miller.Hide Friday May 26 2017 14:00-15:30 (MS 6221) Igor Pak (UCLA) Complexity of short generating functions Abstract. Short generating functions (GF) are power series defined as sums of terms $ct^k/(1-t^a)(1-t^b)\dots$. One can think of each term as a GF of a generalized arithmetic progression. The size of a short GF $A(t)$ is defined as the total bit length of the parameters $a,b,c,k,\dots$. We study the problem whether a given GF has a short GF presentation of polynomial size. This turn out to be a hard problem both mathematically and computationally. We resolve it modulo some complexity assumptions. Notably, we show that the truncated theta function \$\sum_{k