Topic Seminars

 Topic seminars/Learning groups

Russell Miller (CUNY): Computability for algebraic fields

Abstract: 

The broad theme of this three-week seminar will be computability for algebraic fields, i.e., fields that are algebraic extensions of their prime subfield -- mostly in characteristic 0, so that the prime subfield is the rational numbers.  The second week may seem to go beyond this question, but it will do so in a way that sets us up to return to algebraic fields in the third week.

My intention for this seminar is for no more background to be required than the basic mathematical knowledge that everyone at this workshop will already have.  We will be rigorous about the aspects of the theme about which we all care, without going into formal definitions of Turing machines and the like.  I will lead the seminar, but the meetings should be discussions, not lectures.  Anyone who becomes interested in one of the topics here is welcome to delve into it and present it him/herself the following week.

Tuesday 11/4:  we will introduce computable fields.  These include essentially all countable fields that anybody cares about.  The two most basic questions about a computable field $F$ are:  which polynomials in $F[X]$ factor there; and which polynomials in $F[X]$ have a root in $F$.  When extended to several variables, these questions separate from each other, but in a single variable they are very closely connected:  we will examine how closely, and will prove a theorem quantifying which of the two is the harder question.

Thursday 11/6:  Building isomorphisms between two isomorphic computable fields is a good way to say that we can recognize and identify the individual elements of that field (i.e., of its isomorphism type).  But how hard is this?  We will discuss how to present the set of all isomorphisms between two algebraic fields, as effectively as possible, and how this relates to the standard notion of computable categoricity for these fields.

Tuesday 11/11:  We shift gears and discuss the field of real numbers.  How can one do computability theory on an uncountable structure?  How should one best present a real number?  Starting with a proof of Turing's theorem that decimals are the wrong way to do so, we will discuss why one particular method is the "right" way, how this builds unexpected connections between computability and continuity of functions on $\mathbb R$, and what questions one then naturally asks and answers about computation on $\mathbb R$.  (The complex numbers can be studied in very much the same way:  they appear to be an area ripe for investigation in this way.  We will not go in that direction much in the seminar, but this could get an ambitious researcher started on the topic.)

It is harder to predict the exact topics for the second half of this seminar before we get there, but here is a guess....

Thursday 11/13:  There will likely be questions about the real numbers left over from Tuesday, to be addressed today.  The new concept of a "tree-decidable" structure should appear now:  both $\mathbb R$ and $\mathbb C$ are such structures, meaning that one can come as close as possible to computing their first-order (or "elementary") diagrams.  Additionally, on either 11/11 or 11/13 we will consider the subfield containing only the computable real numbers, which turns out to be a very nice simulation of $\mathbb R$ itself for the purposes of first-order mathematics.

Tuesday-Thursday 11/18 & 11/20:  With the mechanics developed in the study of computability on $\mathbb R$, we can now begin to present Galois groups of infinite algebraic field extensions effectively.  The elements here are much the same as the isomorphisms that will have been discussed on 11/6, except that now they are isomorphisms from a given field $F$ onto itself, i.e., automorphisms.  Among these, the computable automorphisms form a subgroup, just as the computable real numbers formed a subfield of $\mathbb R$, and we wish to ask in what cases that subgroup is as nice as the subfield of $\mathbb R$ was.

Announcements:

The next meeting will be Wednesday, November 12 at 11am, followed by the usual TTh schedule (November 13, 18, 20 at 11am) in the lecture hall.

Paula de Lima Sousa, Henry Klatt, Jacob Rhody, Jose Jeremias Valenzuela Morales (GWU): Computable Structure Theory

Abstract: 

We will be following the books of Antonio Montalban, available for free at his website.  The pace of the course will be adjusted based on the participants, and people are welcome to come and go as they please. As of October 30th, we are begining the second book, which coveres scott analysis.

Announcements: 

The meetings will be on Tuesdays and Thursdays at 2-3pm in the discussion room (Poppelsdorfer Allee 45), starting on September 30. 

Whatsapp group: https://chat.whatsapp.com/KvDtzv8efIsEm4h6ynLCKW

Sebastian Eterovic (University of Vienna): o-minimality and point counting

Abstract: 

1) What is o-minimality, what are some important examples of o-minimal structures, and does it mean that something is definable.

2) The Pila-Wilkie point counting theorem. Since this is intended as a user friendly seminar, we would focus mostly on the statement of the theorem, and skip the (very long and very technical) proof.

3) Two detailed examples of o-minimality and point-counting in action: a proof of Ax's theorem for exponentiation, and a proof of the multiplicative version of the Manin-Mumford conjecture.

Announcements: 

The first talk will be on Thursday, September 25 at 2pm (Poppelsdorfer Allee 45) in the seminar room. 

The next series of talks are Monday September 29, Tuesday September 30, and Thursday October 2, all at 11am in the seminar room.

Toghrul Karimov (MPI SWS): Some applications of o-minimality to computational problems in dynamical systems theory

Talk: Thursday Oct 9th 11am

Abstract: 

The famously open Skolem Problem is to decide, given a linear recurrence sequence (u_n)_n, whether u_n = 0 for some n. The formulation in terms of linear dynamical systems is: given a matrix M, an initial point s, and a hyperplane H, decide whether the orbit <s, Ms, M^2s, ...> reaches (equivalently, avoids) H. I will discuss, among other results, the following: given M, s as above, and a semi-algebraic set T, we can decide whether there exists epsilon > 0 such that all orbits <s', Ms', M^2s', ...> with |s'-s| < epsilon avoid T. The talk is based on the recent paper "Verification of linear dynamical systems via o-minimality of the real numbers".

Bjorn Poonen (MIT): Matiyasevich's diophantine definition of exponentiation

Abstract: 

We will go through the proof in Matiyasevich's book to try to see if it can be simplified or made more conceptual.

Announcements: 

The first meeting took place at 10am on Friday, October 31. The next meeting will be Tuesday, November 4 at 10am in the lecture hall.