Past Logic Seminar

Habegger showed that a subvariety of a fibre power of the Legendre family of elliptic curves is special if and only if it contains a Zariski-dense set of special points. I'll discuss joint work with Gal Binyamini, Harry Schmidt, and Margaret Thomas in which we use pfaffian methods to obtain an effective uniform version of Manin-Mumford for products of CM elliptic curves. Using this we then prove an effective version of Habegger's result.

The Zilber-Pink conjecture predicts that if V is a proper subvariety of an arithmetic variety S (e.g. abelian variety, Shimura variety, others) not contained in a proper special subvariety of V, then the “unlikely intersections” of V with the proper special subvarieties of S are not Zariski dense in V. In this talk I will present a strong counterpart to the Zilber-Pink conjecture, namely that under some natural conditions, likely intersections are in fact Euclidean dense in V.  This is joint work with Tom Scanlon.

I shall present a new flexible method showing that every countable model of PA admits a pointwise definable end-extension, one in which every point is definable without parameters. Also, any model of PA of size at most continuum admits an extension that is Leibnizian, meaning that any two distinct points are separated by some expressible property. Similar results hold in set theory, where one can also achieve V=L in the extension, or indeed any suitable theory holding in an inner model of the original model.

A conjecture due to Zilber predicts that the complex exponential field is quasiminimal: that is, that all subsets of the complex numbers that are definable in the language of rings expanded by a symbol for the complex exponential function are countable or cocountable.
Zilber showed that this conjecture would follow from Schanuel's Conjecture and an existential closedness type property asserting that certain systems of exponential-polynomial equations can be solved in the complex numbers; later on, Bays and Kirby were able to remove the dependence on Schanuel's Conjecture, shifting all the focus to the existence of solutions. In this talk, I will discuss recent work about the quasiminimality of a reduct of the complex exponential field, that is, the complex numbers expanded by multivalued power functions. This is joint work with Jonathan Kirby.

The usual language of algebraic geometry is not appropriate for Arithmetical geometry: addition is singular at the real prime. We developed two languages that overcome this problem: one replace rings by the collection of “vectors” or by bi-operads and another based on “matrices” or props. These are the two languages of [Har17], but we omit the involutions which brings considerable simplifications. Once one understands the delicate commutativity condition one can proceed following Grothendieck footsteps exactly. The square matrices, when viewed up to conjugation, give us new commutative rings with Frobenius endomorphisms.

Affine logic is the fragment of continuous logic in which the connectives are limited to affine functions. I will discuss the basics of this logic, first studied by Bagheri, and present the results of a recent joint work with I. Ben Yaacov and T. Tsankov in which we initiate the study of extreme types and extremal models in affine logic.

In particular, I will discuss an extremal decomposition result for models of simplicial affine theories, which generalizes the ergodic decomposition theorem.

In their seminal 2012 paper, Elekes and Szabó found that a certain weak combinatorial non-expansion property of an algebraic relation suffices to trigger the group configuration theorem, showing that only (approximate subgroups of) algebraic groups can be responsible for it. I will discuss some more recent variations and elaborations on this result, focusing on the case of ternary relations on varieties of dimension >1.

Let $k,l>1$ be two multiplicatively independent integers. A subset $X$ of $\mathbb{N}^n$ is $k$-recognizable if the set of $k$-ary representations of $X$ is recognized by some finite automaton. Cobham's famous theorem states that a subset of the natural numbers is both $k$-recognizable and $l$-recognizable if and only if it is Presburger-definable (or equivalently: semilinear). We show the following strengthening. Let $X$ be $k$-recognizable, let $Y$ be $l$-recognizable such that both $X$ and $Y$ are not Presburger-definable. Then the first-order logical theory of $(\mathbb{N},+,X,Y)$ is undecidable. This is in contrast to a well-known theorem of Büchi that the first-order logical theory of $(\mathbb{N},+,X)$ is decidable. Our work strengthens and depends on earlier work of Villemaire and Bès. The essence of Cobham's theorem is that recognizability depends strongly on the choice of the base $k$. Our results strengthens this: two non-Presburger definable sets that are recognizable in multiplicatively independent bases, are not only distinct, but together computationally intractable over Presburger arithmetic. This is joint work with Christian Schulz.

Toward a characterization of modularity using shatter functions, we show that an o-minimal expansion of the  real ordered additive group $(\mathbb{R}; 0, +,<)$ does not define restricted multiplication if and only if the shatter function of every definable family is asymptotic to a polynomial. Our result implies that vc-density can only take integer values in $(\mathbb{R}; 0, +,<)$ confirming a special case of a conjecture by Chernikov. (Joint with Abdul Basit.)

We will define a notion of a semi-retraction between two first-order structures introduced by Scow. We show how a semi-retraction encodes Ramsey problems of finitely-generated substructes of one structure into the other under the most general conditions. We will compare semi-retractions to a category-theoretic notion of pre-adjunction recently popularized by Masulovic. We will accompany the results with examples and questions. This is a joint work with Lynn Scow.

The equivalence of NSOP${}_1$ and NSOP${}_3$, two model-theoretic complexity properties, remains open, and both the classes NSOP${}_1$ and NSOP${}_3$ are more complex than even the simple unstable theories. And yet, it turns out that classical geometric stability theory, in particular the group configuration theorem of Hrushovski (1992), is capable of controlling classification theory on either side of the NSOP${}_1$-SOP${}_3$ dichotomy, via the expansion of stable theories by generic predicates and equivalence relations. This allows us to construct new examples of strictly NSOP${}_1$ theories. We introduce generic expansions corresponding, though universal axioms, to definable relations in the underlying theory, and discuss the existence of model companions for some of these expansions. In the case where the defining relation in the underlying theory $T$ is a ternary relation $R(x, y, z)$ coming from a surface in 3-space, we give a surprising application of the group configuration theorem to classifying the corresponding generic expansion $T^R$. Namely, when $T$ is weakly minimal and eliminates the quantifier $\exists^{\infty}$, $T^R$ is strictly NSOP${}_4$ and TP${}_2$ exactly when $R$ comes from the graph of a type-definable group operation; otherwise, depending on whether the expansion is by a generic predicate or a generic equivalence relation, it is simple or NSOP${}_1$.

In his pioneering and celebrated 1968 paper on the elementary theory of finite fields Ax asked if the theory of the class of all the finite rings $\mathbb{Z}/m\mathbb{Z}$, for all $m>1$, is decidable. In that paper, Ax proved that the existential theory of this class is decidable via his result that the theory of the class of all the rings $\mathbb{Z}/p^n\mathbb{Z}$ (with $p$ and $n$ varying) is decidable. This used Chebotarev’s Density Theorem and model theory of pseudo-finite fields.

I will talk about a recent solution jointly with Angus Macintyre of Ax’s Problem using model theory of the ring of adeles of the rational numbers.

We will construct several algebras of functions definable in R_{an,\exp} which are stable under parametric integration. 

Given one such algebra A, we will study the parametric Mellin and Fourier transforms of the functions in A. These are complex-valued oscillatory functions, thus we leave the realm of o-minimality. However, we will show that some of the geometric tameness of the functions in A passes on to their integral transforms.

I will explain how the model-theoretic algebraic closure in Zilber’s pseudo-exponential field can be described in terms of the self-sufficient closure. I will sketch a proof and show how the Mordell-Lang conjecture for algebraic tori comes into play. If time permits, I’ll also talk about the characterisation of strongly minimal sets and their geometries. This is joint work (still in progress) with Jonathan Kirby.

Zarankiewicz's problem for hypergraphs asks for upper bounds on the number of edges of a hypergraph that has no complete sub-hypergraphs of a given size. Let M be an o-minimal structure. Basit-Chernikov-Starchenko-Tao-Tran (2021) proved that the following are equivalent:

(1) "linear Zarankiewicz's bounds" hold for hypergraphs whose edge relation is induced by a fixed relation definable in M

(2) M does not define an infinite field.

We prove that the following are equivalent:

(1') linear Zarankiewicz bounds hold for sufficiently "distant" hypergraphs whose edge relation is induced by a fixed relation definable in M

(2') M does not define a full field (that is, one whose domain is the whole universe of M).

This is joint work (in progress) with Aris Papadopoulos.

I will discuss the following statement, a definable version of the (p,q) theorem of Jiří Matoušek from combinatorics, conjectured by Chernikov and Simon:

Suppose that T is NIP and that phi(x,b) does not fork over a model M. Then there is some formula psi(y) in tp(b/M) such that the partial type {phi(x,b’) : psi(b’)} is consistent.

Given a cover U of a family of smooth complex algebraic varieties, we associate with it a class C of structures locally definable in an o-minimal expansion of the reals, containing the cover U.  We prove that the class is ℵ0-homogeneous over submodels and stable. It follows that C is categorical in cardinality ℵ1. In the one-dimensional case we prove that a slight modification of C is an abstract elementary class categorical in all uncountable cardinals.
 

We call affine logic the fragment of continuous logic in which the connectives are limited to linear combinations and the constants (but quantification is allowed, in the usual continuous form). This fragment has been introduced and studied by S.M. Bagheri, the first to observe that this is the appropriate framework to consider convex combinations of metric structures and, more generally, ultrameans, i.e., ultraproducts in which the ultrafilter is replaced by a finitely additive probability measure. Bagheri has shown that many fundamental results of continuous logic hold in affine logic in an appropriate form, including Łoś's theorem, the compactness theorem, and the Keisler--Shelah isomorphism theorem.

In affine logic, type spaces are compact convex sets. In this talk I will report on an ongoing work with I. Ben Yaacov and T. Tsankov, in which we initiate the study of extremal models in affine logic, i.e., those that only realize extreme types.

From a model theoretic point of view, local fields of positive characteristic, i.e. fields of Laurent series over finite fields, are much less well understood than their characteristic zero counterparts - the fields of real, complex and p-adic numbers. I will discuss different approaches to axiomatize and decide at least their existential theory in various languages and under various forms of resolution of singularities. This includes new joint work with Sylvy Anscombe and Philip Dittmann.

A theorem of Chatzidakis, van den Dries and Macintyre, stemming ultimately from the Lang-Weil estimates, asserts, roughly, that if $\phi(x,y)$ is a formula in the language of rings (where $x,y$ are tuples) then the size of the solution set of $\phi(x,a)$ in any finite field $F_q $(where $a$ is a parameter tuple from $F_q$) takes one of finitely many dimension-measure pairs as $F_q$ and $a$ vary: for a finite set $E$ of pairs $(\mu,d)$ ($\mu$ rational, $d$ integer) dependent on $\phi$, any set $\phi(F_q,a)$ has size roughly $\mu q^d$ for some $(\mu,d) \in E$.

This led in work of Elwes, Steinhorn and myself to the notion of 'asymptotic class’ of finite structures (a class satisfying essentially the conclusion of Chatzidakis-van den Dries-Macintyre). As an example, by a theorem of Ryten, any family of finite simple groups of fixed Lie type forms an asymptotic class. There is a corresponding notion for infinite structures of  'measurable structure’ (e.g. a pseudofinite field, by the Chatzidakis-van den Dries-Macintyre theorem, or certain pseudofinite difference fields).

I will discuss a body of work with Sylvy Anscombe, Charles Steinhorn and Daniel Wolf which generalises this, incorporating a richer range of examples with fewer model-theoretic constraints; for example, the corresponding infinite 'generalised measurable’ structures, for which the definable sets are assigned values in some ordered semiring, need no longer have simple theory. I will also discuss a variant in which sizes of definable sets in finite structures are given exactly rather than asymptotically.

The Skolem Problem asks to decide whether a linearly recurrent sequence (LRS) over the rationals has a zero term.  It is sometimes considered as the halting problem for linear loops.   In this talk we will give an overview of two current approaches to establishing decidability of this problem.  First, we observe that the Skolem Problem for LRS with simple characteristic roots is decidable subject to the $p$-adic Schanuel conjecture and the exponential-local-global principle.  Next, we define a set $S$ of positive integers such that (i) $S$ has positive lower density and (ii) The Skolem Problem is decidable relative to $S$, i.e., one can effectively determine the set of all zeros of a given LRS that lie in $S$.

The talk is based on joint work with Y. Bilu, F. Luca, J. Ouaknine, D. Pursar, and J. Nieuwveld.  

We study the definability of valuation rings in ordered fields (in the language of ordered rings). We show that any henselian valuation ring that is definable in the language of ordered rings is already definable in the language of rings. However, this does not hold when we drop the assumption of henselianity.

This is joint work with Philip Dittmann, Sebastian Krapp and Salma Kuhlmann.