The semester, we are following a paper of Peterzil and Starchenko in the model theory seminar. Dave Marker gave the first lecture, which was a general interest to the topics the paper will consider. This post is going to give rough notes of Dave’s talk. We begin with a result of Ax:

Theorem: Let f_1, \ldots , f_n \in \mathbb C [[t_1, \ldots , t_m]] \text{ be } \mathbb Q-linearly independent over C. Then  td(f_1, \ldots , f_n , e^{f_1} , \ldots , e^ {f_n } / \mathbb C) \geq n + \text{ rank}\left(\left( \frac{\delta f_i }{\delta t_j } \right) \right).

Geometric version: Let D_n \subseteq \mathbb C^n \times \mathbb (C^*)^n be the group of (x_1, \ldots, x_n ) \mapsto (e^{x_1}, \ldots , e^{x_n} ) . Let f_1, \ldots , f_ n be convergent power series on B. Let U = \Gamma ( exp|_{f(B)}) (note: I will use \Gamma ( - ) to denote the graph of a function). Then the rank of the matrix \left( \frac{\delta f_i }{\delta t_j} \right) is equal to dim (U). The dimension of the Zariski closure of U, denoted U^{zar} is at least n+dim(U) unless the projection of $U$ to its first $n$ coordinates is contained in a linear subspace: \pi_1 (U) \subseteq Z( \sum m_i x_i = c), in which case, \pi_2 (U) \subseteq \prod y_i ^ {m_i} = e^c .

The statement which is usually called the Ax-Lindemann-Weierstrass Theorem (hence ALW) is a more detailed statement of the algebraic content of the geometric version of Ax’s result:

ALW If V_1 \subset \mathbb C^m , \, V_2 \subseteq \mathbb (C^* )^n are irreducible algebraic varieties, with exp(V_1) \subseteq V_2, then there is a coset of an algebraic subgroup of (\mathbb C^* ) ^m so that exp(V_1 ) \subseteq S \subseteq V_2.

Now, we will consider statements of a similar nature in a more general setting. Let A be an abelian variety of dimension d (again we are working over the complex numbers throughout). Then there are \lambda_1 , \ldots , \lambda _2d so that we can realize A as the quotient of \mathbb C^d by \Lambda = \sum \mathbb Z \lambda _i in an analytic manner: that is, there is a surjective analytic map \pi: \mathbb C^d \rightarrow A, with ker(\pi) = \Lambda. We will be considering this map \pi. Much like the complex exponential function, this global map is poorly behaved when we consider it in any expansion of the real field (because it is periodic on \Lambda, with this map and the field structure, it is easy to see that you can interpret the integers).

But, we are still going to use tame model theory (o-minimality) to prove things about this map (eventually) – we are just going to have to be careful about restricting to bounded subsets of the domain. In this setting, we have another ALW-type result (this one was proved by Pila and some cases by others, I think  – if you can give a definitive account of this, please comment below and I will modify the post).

ALW: Let \pi: \mathbb C^d \rightarrow A be as above. Suppose that V \subseteq \mathbb C^d is an irreducible algebraic variety, then \pi (V) ^ {zar} is a coset of a subabelian variety.

Of course, to many of us, these statements about transcendence and restrictions on the algebraic closures of very transcendental maps are interesting in their own right, but there are other reasons that these results have proven useful. We will spend the rest of the time describing the Pila-Zannier approach to diophantine problems in one specific interesting case.

Manin-Mumford (special case): If A is a simple abelian variety over a number field and C \subseteq A is a curve, then C \cap Tor(A) is finite.

We will describe the Pila-Zannier proof. First, we will think about the following maps: \mathbb R^ {2d} \rightarrow ^ \theta \mathbb C ^ d  \rightarrow ^ \pi A, where \theta (\bar x ) = \sum x_ i \lambda _i . Then \pi^{-1} ( Tor A) \in \sum \mathbb Q \lambda _i, and (\pi \circ \theta ) ^{-1} ( Tor A ) = \mathbb Q ^ {2d}. But, we only need to understand the map on F = [0,1]^{2d}, by periodicity.

So, let C \subseteq A be a curve, and let X  = (\pi \circ \theta ) ^{-1}, and let now we will think about X \cap F, which is definable in the o-minimal structure $\mathbb R_{an}$ (the real field augmented by maps of any analytic function of any number of variables restricted to a compact subset). Now, a powerful theorem will come onto the scene (actually, it already did in Pila’s proof of ALW, but this seminar is about proving ALW in another manner, so lets disregard that…).

Pila-Wilkie: Let X \subseteq \mathbb R ^m be definable in an o-minimal structure and let X ^{alg} be the union of connected semialgebraic curves. Then for any q \in \mathbb Q, let H(q) = max (|a|, |b|) with q = \frac{a}{b} in lowest terms, and for all \epsilon >0|\{ q \in [0,1]^m  \, | \, \bar q \in X \setminus X^{alg} , \, H(q) \leq N \} | << N^\epsilon.

Note that in general X^{alg} can be a countable union of algebraic curves (for instance, think about the graph of$latex x^y=z$ in \mathbb R^3. So, one point of the result is that one can characterize a certain a priori analytic curve as algebraic just by finding a lot of points on the curve. Then if you know a transcendence result (e.g. ALW above), these two points can be played off of each other.

Under the assumptions for our MM-type problem, X^alg is empty, because one can prove that if X contains a semi-algebraic curve, then \pi^{-1} (C) contains an algebraic curve (we won’t prove this). Of course, the only way this happens is for C to be the coset of an abelian subvariety, but there are none, by simplicity.

Now, there is a result of Masser: \exists l \exists N such that if a is a torsion point of order $n \geq N $, then a has at least n^l many conjugates over $k$. Now of course, we have a problem – if we do have infinitely many torsion points on our curve, then add some torsion point of order at least N. One can, bound the height of the preimage of the torsion points in X \cap F as a linear function of their order. But, now we get at least n^l many of these points, which violates Pila-Wilkie. So, we must have had only finitely many torsion points on our curve.

This was the end of Dave’s seminar. Several comments: as mentioned, Pila-Wilkie is used in two places – once to prove the functional transcendence results (this is quite involved) and onces to play off of a result like Masser’s (in other contexts, there are other results of a similar spirit). This seminar is about proving the functional transcendence results in a more straightforward manner without appealing to Pila-Wilkie. Pila-Wilkie is “ineffective” in the sense that we know that the growth rate of the points on the certain definable sets must be small, but we don’t know the constants or at what point the growth rates kick in – so there are fewer than n^\epsilon many points happens eventually, for large enough n,  but we don’t know what large enough means. So, effectivizing these finiteness statements with specific bounds is of quite a bit of interest. It has been done in certain contexts, but that is another story for another time.


Discovering a frequently (at least partially) rediscovered concept

The following post is ultimately going to be used for proving certain finiteness statements in various algebraic settings (we’ll do that in another post). But before we get to the algebra, I am going to describe some infinitary combinatorics which makes proving the algebraic results reasonably painless (some of the results we describe have proofs in the literature, and invariably, these are much more complicated since they are really discovering the same sort of finiteness principles, but in different incarnations.

The title of the post comes from an article of Kruskal explaining the theory of well-quasi-orderings (wqo) and the theory of better-quasi-orderings (bqo). I had heard about these theories a number of years ago, but like many things, only decided to learn things in detail once I had some more visceral motivation.

quasi-ordering (qo) is a reflexive and transitive relation on a set; we use x \leq y for the binary relation holding between x \text{ and }  y. A quasi ordering is a partial ordering (poset), if, additionally,  \leq is antisymmetric: x \leq y \leq x implies x=y. From a quasi-ordered set, one can obtain a partially ordered set via taking the quotient by the equivalence relation x \sim y \text{ if } x \leq y \leq x. For the algebraic applications we have in mind, we only need partial orders, but I want to explain things more generally.

A quasi-ordering is a well-quasi-ordering (wqo) if:

  • every descending set a_1 > a_2 >a_3>\ldots is finite, and
  • any set of pairwise incomparable elements (called an antichain) is finite.

There are alternate equivalent formulations of the concept which are sometimes convenient to use. For instance, a qo is a wqo iff every infinite sequence contains an infinite ascending sequence.

It is easy to see that wqo are closed under many finitary sorts of operations (homomorphic images, finite unions, cartesian products, etc.). Why not just work with partial orders and ignore the possibility of not having antisymmetry? Certain rather natural constructions do not preserve partial orders, but do preserve qo. For instance, take the set of sequences from some po, and set (a_i) \preceq (b_i) if there is a subsequence (b_{n_i}) such that for each i \in \mathbb N, \, a_i \leq b_{n_i}. Then \preceq is not necessarily a po, but it is a qo. You can read about the history of the concept of wqo in the paper of Kruskal linked above. Many people used related concepts going back to at least the 1930s, but the first formal use according to Kruskal is by Higman (1952). But Simpson (in the chapter “BQO Theory and Fraisse’s conjecture” in Recursive aspects of descriptive set theory) writes that the notion appears in Kaplansky’s thesis (1941) – I don’t feel like checking precisely (but comment below if you know). We will concentrate on wqo for the rest of this post, before moving on to bqo and the algebraic applications I have in mind in posts following this one.

Higman proved that the set of finite sequences with entries from a finite set ordered by the subsequence relation is a wqo. Higman’s theorem is a special case of Kruskal’s tree theorem (the set of finite trees with labels from a wqo set is itself a wqo under the homeomorphic embedding relation). Higman studies the objects around this area with a fairly general outlook in the first part of his paper, seeking to develop what he called the “finite basis property” in a more general way than he strictly needed for the results he was pursuing, which we will describe next.

If X, \leq is a qo, and A \subset X, then we denote by cl(A), the closure of A (or maybe we ought to write the upward closure of A), \begin{array}{rcl} cl(A) &=& \{ x \in X \, | \, a \leq x, \text{ for some } a \in A\}. \end{array}

Naturally, we call a set open if it is the complement of a closed set. So, you might call the open sets in X initial, and we will use the abjectives open and initial interchangeably. Higman says a qo has the finite basis property (FBP) if every closed subset of X is the closure of a finite set. Higman notes the following equivalent formulations:

Theorem: The following conditions on X , \leq are equivalent:

  1. Every closed subset of X is the closure of a finite subset.
  2. X, \leq is a wqo.
  3. ACC (ascending chain condition) on closed sets.
  4. Every infinite sequence of elements has an infinite ascending sequence.

In addition, it is easy to see that every open set is the collection of elements below some fixed finite set and DCC on open sets are equivalent to FBP. Dickson’s Lemma is essentially FBP for the partial product order on \mathbb N ^m.

Higman didn’t seem to be interested in wqo, per se; he was trying to solve a problem of Erdos and Rado. To explain the problem, we will need a few definitions.

An abstract algebra (in the sense of Higman) is a set A together with some collection M of functions f: A^{n_f} \rightarrow A where n_f is called the arity of f. This is just a structure (in the sense of model theory) in the language which has function symbols of the correct arity for each element of M. Higman assumes that there is some maximal arity, r \in \mathbb N, and denotes the subset of r-ary functions by M_r.

An M-subalgebra of A is simply a substructure B \leq A. An M-algebra with no subalgebras is called minimal (note that we are allowing 0-ary functions, which prevents the minimal algebras from being empty. A quasi order on A makes A an ordered algebra if for any a \leq b \in A, \, f \in M, \text{ and } x , \, y tuples of elements (possibly empty) from A whose total length is appropriate, we have f (x,a,y) \leq f (x,b,y).

The order is a divisibility order if for any appropriate length tuples and elements as above, a \leq f (x,a,y). Given a quasi order \preceq on M_r, we say that \preceq is compatible with \leq if f \preceq g implies that f(x) \leq g(x) for any appropriate length tuple x \in A. Higman proved:

Theorem Suppose (A, M) is a minimal algebra, and M_r is quasi-ordered with FBP for each r = 0 , \ldots , n and M_r = \emptyset \text{ for } r >n. Then any divisibility order on (A,M) which is compatible with the quasi-orders on M_r has the FBP.

Suppose for a moment that every M_r is finite and that the order on M_r is trivial. Then compatibility means that (A, M \setminus M_0) has a set of generators with FBP. In this case the content of the above theorem is given by:

Theorem An abstract algebra with a finite set of operations has the FBP in a divisibility order if and only if any generating set has the FBP.

Erdos and Rado had previously proved the theorems in special cases.






UCLA model theory seminar and Markoff triples

A few weekends ago there was an AMS sectional meeting in Chicago – I mainly attended the special session on model theory, but I found Peter Sarnak’s AMS Erdős Memorial Lecture extremely interesting. I will describe the results briefly, and also mention some interesting connects below.

Sarnak also made quite a few interesting nontechnical remarks about mathematics in general (or maybe about number theory generally). Let me paraphrase one thing he said. At a certain point he was describing number theory, and explaining the prevalence of various technologies a priori completely unrelated to the integers or rational numbers or anything else in number theory and he said that number theory is about the sort of results being proven and that he didn’t care at all about the method used in the pursuit – that any method was permissible, and that was something which in some way characterized the subject.

I don’t really know if I agree – I think there must be quite a few number theorists who find various theorems or subfield interesting precisely because of the use of certain methods. In fact, earlier in the day, various people I was having lunch with expressed  a viewpoint which seemed in opposition to Sarnak’s (maybe not completely opposed). Their point was that the problems and results that get people excited are more a part of the social activity of mathematics, not necessarily having to do with any sort of reality. This isn’t exactly opposed to Sarnak’s point of view, but still, there is something real about the integers. During lunch, I was arguing Sarnak’s side, but it’s hard for me to tell if I really felt strongly or I was just in the mood for debate.

Continue reading

Vaught’s conjecture conference

Last week in Berkeley, there was a Vaught’s conjecture conference happening.

I don’t have anything particularly clever to say about the conjecture, but here is a list of open problems suggested at the meeting. It is my understanding that more will eventually be available at the conference webpage (there were multiple problem sessions).

Since it is not likely that I will write anything about this anywhere else, I want to talk about Vaught’s conjecture for on special theory: the theory of differentially closed fields of characteristic zero. In the early 80’s Shelah proved Vaught’s conjecture for \omega-stable theories. So, it was easy to see that there were either \aleph _0 or continuum-many countable differentially closed fields; it is very easy to see that there are at least \aleph_0-many, by counting the transcendence degree of the constants, for instance.

It was nearly a decade later before Hrushovski and Sokolovic proved that there were continuum-many countable differentially closed fields. Continue reading

Model Theory seminar: Janak

Janak Ramakrishnan gave today’s model theory seminar, which was about classifying definable linear orders and definable partial orders in an o-minimal structure. His slides are posted below.

Janak actually talked more generally, about structures with the order extension (OE) property (defined in the linked slides), and at one point asked if someone knew an example of a structure without this property, at point several people began thinking about whether the theory of a linear order and a partial order (so two binary symbols, no information about how they play together, one is a linear order and one is a partial order) has a model companion. This theory should not have the order extension property. I don’t know if anyone has written something to this effect down at some point, but it would seem to be a good exercise, unless I am missing something. Of course, there is always the question of whether there is some more natural structure which fails OE. I tried to suggest a sort of example from valuation theory, but seminar was ending.

Differential primitive element theorem, an update

I have posted an update to my earlier post about the differential primitive element theorem. Essentially, I now go through Theorem 1 of Pogudin’s paper.

My impression so far is the same as it was when I wrote the first post. The argument seems to use cleverness and elementary differential algebra, and so far, it is quite clear to read. The crux of the proof at a certain point involves essentially changing the derivation slightly. It seems like some of the lemmas (1-4) along with use of differential Chow forms might give a proof of the theorem, but I have not checked the details yet.

Primitive elements in differential field extensions

In this post, all the fields are characteristic zero – characteristic p differential fields are more complicated.

It is a classical theorem that any field extension F/K such that [F:K] is finite is actually generated by a single element. Kolchin proved an analog of this theorem in the setting of differential fields: finitely generated differential field extensions which are differentially algebraic are generated by a single element, assuming that the derivation is nontrivial on the base field K (that is, K has at least one nonconstant).

Kolchin’s theorem is not true without the assumption that K contains a nonconstant. For the easiest example showing this, take K to be a constant differential field and two transcendental constants c_1, c_2; K (c_1, c_2) = K \langle c_1 , c_2 \rangle is not generated by any single element over K. Continue reading