ICMS

Number Theory and Computability

Jun 25, 2007 - Jun 29, 2007

ICMS, 14 India Street, Edinburgh

Organisers

Name	Institution
Everest, Graham	University of East Anglia

Short Report

Many people are fascinated to observe when a polynomial equation has a solution in integers or rational numbers (fractions), especially if the solution is not obvious. Witness the global interest in Simon Singh's book [4] about Fermat's Last Theorem. In 1900, David Hilbert, one of the giants of Mathematics, asked if it is possible to construct a general method which will determine if such an equation has an integral solution.

After several decades of hard thought, a surprising answer emerged from a surprising quarter. In 1970, logicians proved, using ideas that led directly to the invention of the modern computer, that no such general method can exist. This interplay between Logic and Number Theory led to a fantastic rapport developing between workers in these fields, one that has continued up to the present. The aim of the meeting was to build upon earlier workshops in bringing established as well as new workers into this fascinating dialogue.

Hilbert's question having been resolved for the integers, mathematicians naturally ask the same question about other arithmetic structures, such as polynomials or the rational numbers. Some new results have been obtained and the meeting provided a shop window for these.

However the central problem about solvability in rational numbers remains. In 2003, Poonen took a giant leap in that direction by giving a negative answer to Hilbert's question, now in the context of some large subrings of the rational numbers, whose denominators are constrained in some natural way. What is more, he used methods from the arithmetic theory of elliptic curves, itself an extremely exotic and powerful subject. The workshop also gave time over to studying Poonen's methods with the hope of eventually resolving this most difficult problem.

A large number of photographs were taken at this meeting. To view them please follow these links:

Participants list and links to available presentations are further down this page.

Download the pdf file of the full report

Original Details

Hilbert's Tenth Problem concerns the solution of Diophantine Equations; asking whether an algorithm exists which will determine if a system of polynomial equations in a finite number of variables, has an integral solution. This decision problem was eventually settled by Matijasevic who showed that no such algorithm exists. Much of the foundations for the proof were laid by J. Robinson, Davis and Putnam, using tools from Logic. Matijasevic, in the course of his proof brought about an interesting collision between Number Theory and Logic. Specifically, he reduced the problem to one in the arithmetic of integer linear recurrence sequences.

The rational version of Hilbert's Tenth Problem asks the same question as above except that one now seeks a rational solution. This is an unsolved problem.

Within the last six years, several workers have begun to ask whether the rational version of Hilbert's Tenth Problem might be resolved using the arithmetic of higher genus integer recurrence sequences. Similar questions have been formulated for rings of algebraic integers, rings of polynomials, fields of rational functions, rings of analytic and meromorphic functions. Many of these questions remain open.

Despite its apparent theoretical nature, the study of the subject has produced constructions of mathematical objects such as a polynomial whose set of positive values coincides with the set of prime numbers as well as examples of exotic varieties (over various domains of common interest). It has also produced very deep new questions such as Mazur's Question (which relates to the topology of rational points on a variety). Relations have been established with the Theory of Elliptic Curves and Abelian Varieties, Diophantine Geometry, Divisibility Sequences, Hyperbolic Varieties and much besides.

The field has brought together researchers from Number Theory, Logic, Algebraic Geometry and Theory of Computation and a substantial number of young researchers have chosen to work on the mentioned and related problems.

It is hoped that the workshop will contribute substantially to the cross-fertilization of all the mentioned areas and will benefit especially workers in Number Theory and Logic in the U.K. The Workshop will be a sequel to the meetings held at Ghent in 1999, Oberwolfach in 2003 Palo Alto and (American Institute of Mathematics) in 2005.

The expected outcomes, and the techniques developed to approach them, would be of interest to researchers in Mathematics, in particular in the areas of Number Theory and Logic and their interactions. Number Theory of this kind has links with Cryptography and the results may well be of interest to workers in that field and applicable in the short term.

An archive of background reading is available from http://www.mth.uea.ac.uk/~h090/icms.html

Clay Mathematics Institute is holding a meeting on Hilbert's Tenth Problem in March this year. You may also wish to look at some of the resources on their site at http://www.claymath.org/events/h10/ .

Arrangements

Participation
Participation is by invitation only. The workshop will begin on the morning of Monday 25 June and finish on the afternoon of Friday 29 June 2007. In preparation for the workshop you may wish to visit the archive of background reading mentioned above.

UK Visas
If you are travelling from overseas you may require an entry visa. A European visa does not guarantee entry to the UK. Please use this link to the UK Visas site to find out if you need a visa and if so how to apply for one. If you do require a visa, ICMS can provide a signed invitation letter.

Venue
The workshop will take place at the head-quarters of ICMS, 14 India Street, Edinburgh. This house is the birthplace of James Clerk Maxwell and is situated in the historic New Town of Edinburgh, near the city centre.

The ICMS travel pages contain advice on how to travel to Edinburgh. For local information the finding ICMS page shows the location of ICMS and contains useful maps of the city centre.

The seminar room at ICMS has whiteboards, 2 overhead projectors, a data projector and laptop.

Wireless access is available throughout the ICMS building. There are also 7 public PCs which may be used at any time for internet access and to check email.

Accommodation
ICMS will arrange single en-suite rooms in local guest houses for those who require it. Accommodation is typically about 15 to 30 minutes walk from ICMS. Participants are also free to make their own arrangements and may claim back the cost, with receipts, up to a maximum of £45.00 per night bed and breakfast. A list of Edinburgh accommodation of various sorts and prices is available here . Sections 1-3 are particularly relevant.

Meals and Refreshments
A sandwich lunch will be provided on the first day of the workshop, Monday 25 June. For the remainder of the days, participants are free to go out for lunch and explore the many cafes, restaurants, sandwich shops and bars in the surrounding area. On arrival we will provide you with a ‘welcome’ pack which will contain information about eating places nearby.

Morning and afternoon refreshments will be provided throughout the workshop.

There will be an informal wine reception after the close of lectures on Monday 25 June.

On Tuesday 26 June you are invited to attend an informal supper at Nargile Turkish Restaurant. The workshop dinner will take place on the evening of Thursday 28 June. The workshop grant will cover the cost of these 2 meals.

Registration
Registration will take place between 09.30 and 10.20 on Monday 25 June. The talks will start at 10.30.

Financial Arrangements
Unless otherwise specified in your invitation letter, the workshop grant will cover the cost of your bed and breakfast accommodation, tea/coffee throughout the workshop, lunch on the first day, the wine reception, the informal supper on Tuesday and the Workshop Dinner on Thursday evening.

If we have agreed to pay some of your travel costs, you will be informed by email. Reimbursement will take place after the workshop. At Registration you will be given an expenses claim form and this should be submitted to ICMS, with receipts. Please note that we cannot reimburse any item without a receipt.

Under the terms of our EPSRC funding we are required to charge a 30.00 GBP registration fee to cover costs not admissible under the grant. The fee will be payable on arrival at the workshop payment may be by cash, sterling cheque or credit/debit card. If you anticipate any difficulty covering the fee, please let me know.

Programme

Monday 25 June

09.30 - 10.20	Registration
10.20 - 10.30	Welcome
10.30 - 11.30	Yuri Matiyasevich (Steklov Institute of Mathematics) Computation paradigms in the light of Hilbert's tenth problem Presentation
11.30 - 12.30	Kirsten Eisentraeger (University of Michigan) First-order undecidability and Hilbert's Tenth Problem for function fields of positive characteristic
12.30 - 14.30	Lunch (sandwich lunch provided)
14.30 - 15.30	Graham Everest (University of East Anglia) The arithmetic of elliptic divisibility sequences
15.30 - 16.00	Coffee/Tea
16.00 - 17.00	Jochen Koenigsmann (Max Planck Institut für Mathematik) A Galois theoretic approach to decidability of fields
17.00 - 18.30	Wine reception at ICMS

Tuesday 26 June

10.00 - 11.00	Bjorn Poonen (University of California, Berkeley) Characterizing Z in Q with a universal-existential formula
11.00 - 11.30	Coffee/Tea
11.30 - 12.30	Jeroen Demeyer (Ghent University) Diophantine sets of polynomials over a finite field
12.30 - 14.30	Lunch
14.30 - 15.30	Alexandra Shlapentokh (East Carolina University) HTP over algebraic extensions of rational numbers: normforms vs. elliptic curves. Part I: normforms Presentation
15.30 - 16.00	Coffee/Tea
16.00 - 17.00	Aharon Razon (Elta Systems) On Rumely's local-global principle
19.00	Informal group supper at Nargile Turkish Restaurant

Wednesday 27 June

10.00 - 11.00	Joseph H Silverman (Brown Univeristy) P-adic properties of elliptic divisibility sequences
11.00 - 11.30	Coffee/Tea
11.30 - 12.30	Anand Pillay (University of Leeds) A Lindemann-Weierstrass theorem for semi-abelian varieties over function fields
12.30 - 14.00	Lunch
14.00 - 15.00	Thomas Scanlon (University of California, Berkeley) Defining valuations on curves
15.00 - 15.30	Coffee/Tea
15.30 - 16.30	Alexandra Shlapentokh (East Carolina University) HTP over algebraic extensions of rational numbers: normforms vs. elliptic curves. Part II: elliptic curves Presentation
17.00 - 17.45	Screening of Julia Robinson and Hilbert's Tenth Problem www.zalafilms.com/films/juliarobinson.html

Thursday 28 June

10.00 - 11.00	Laurent Moret-Bailly (IRMAR, Université de Rennes 1) Positive-existential definability in Noetherian rings Presentation
11.00 - 11.30	Coffee/Tea
11.30 - 12.30	Moshe Jarden (Tel Aviv University) Undecidability of families of rings of totally real integers
12.30 - 14.30	Lunch
14.30 - 15.30	Katherine Stange (Brown University) From elliptic divisibility sequences to elliptic nets
15.30 - 16.00	Coffee/Tea
16.00 - 17.00	Maxim Vsemirnov (Steklov Institute of Mathematics) Diophantine encoding and generalized Cantor's polynomials
19.00	Workshop dinner at First Coast Restaurant

Friday 29 June

10.00 - 11.00	Marco Streng (Universiteit Leiden) Divisibility sequences for elliptic curves with complex multiplication
11.00 - 11.30	Coffee/Tea
11.30 - 12.30	*Thanases C Pheidas* (University of Crete) Meromorphic maps of the punctured torus to the torus and undecidability
12.30 - 14.00	Lunch
14.00 - 15.00	Gregory Cherlin (Rutgers University) Permutation groups of finite Morley rank Presentation
15.00 - 15.30	Coffee/Tea
15.30 - 16.30	Françoise Point (Mons-Hainaut University) Witt modules Presentation
16.30	Close of workshop

Presentations:

Presentation Details
Cherlin, Gregory
Permutation groups of finite Morley rank
View Abstract Hide Abstract
Groups of finite Morley rank are abstract groups equipped with a notion of dimension analogous to "dimension of Zariski closure" in the algebraic case. The abelian groups in this category turn out to carry some useful number theoretic information. It has been conjectured that the simple groups in this category are algebraic. Attempts to build a theory similar to the classification of finite simple groups have led to partial results which can be applied to the study of permutation groups of finite Morley rank much as the full classification is applied in the finite case. In particular, with Borovik, we have the following: for a primitive permutation group G of finite Morley rank acting definably on a set X, the rank of G can be bounded in terms of the rank of X. This result appears to be new even in the algebraic case.
Demeyer, Jeroen
Diophantine sets of polynomials over a finite field
View Abstract Hide Abstract
We prove that recursively enumerable subsets of mathbb{F}_q are diophantine over mathbb{F}_q.
Eisentraeger, Kirsten
First-order undecidability and Hilbert's Tenth Problem for function fields of positive characteristic
View Abstract Hide Abstract
We prove that the first-order theory of any function field of odd characteristic is undecidable (joint work with A. Shlapentokh). When K is the function field of a variety of dimension at least 2 over an algebraically closed field of odd characteristic, we can also prove that Hilbert's Tenth Problem for K is undecidable.
Everest, Graham
The arithmetic of elliptic divisibility sequences
View Abstract Hide Abstract
The sequences of the title are higher genus analogues of classical sequences such as Mersenne and Fibonacci. The same questions asked of these can also be asked in higher genus and the results are sometimes similar and sometimes radically different. I will report on results of both kinds. The biggest surprise concerns the question about whether infinitely many terms are prime. The surprise element comes on two fronts - one being that proofs are known in special cases and the other being that only finitely many terms are prime in higher genus.
Jarden, Moshe
Undecidability of families of rings of totally real integers
View Abstract Hide Abstract
Combining methods of Julia Robinson and of Cherlin-Jarden, we prove that for every positive integer e the theory of all sentences that hold in the ring Z_{tr}(sigma_1,ldots,sigma_e) for almost all (sig_1,ldots,sig_e)in Gal(Q)^e is undecidable. (Joint work with Carlos Videla)
Koenigsmann, Jochen
A Galois theoretic approach to decidability of fields
View Abstract Hide Abstract
We will present a translation manual between the first order theory of a field K and the first order theory of the absolute Galois group of the rational function field K(t) over K. This will enable us to attack decidability problems over fields via Galois theory.
Matiyasevich, Yuri
Computation paradigms in the light of Hilbert's tenth problem
View Abstract Hide Abstract
The talk would be a survey of a century long history of interplay between Hilbert's tenth problem (about solvability of Diophantine equations) and different notions and ideas from Computability Theory.
Moret-Bailly, Laurent
Positive-existential definability in Noetherian rings
View Abstract Hide Abstract
We try to characterize (some of) the (commutative) rings R with the property () the set of nonzero elements of R is positive-existentially definable (in other words, positive-existential and existential definability coincide for R). We prove that "most" Noetherian rings satisfy (). More precisely: (1) If R is a Noetherian domain and () does not hold, then R must be local and Henselian (and, of course, not a field). (2) If R is Noetherian, local, excellent, Henselian and positive-dimensional, then () does not hold. We also investigate some non-Noetherian rings, in particular rings of analytic functions.
Pheidas, Thanases C
Meromorphic maps of the punctured torus to the torus and undecidability
View Abstract Hide Abstract
We present a decomposition theorem for meromorphic functions from the punctured torus to the torus and we present a program which might produce a proof of an analogue of Hilbert's tenth problem for fields of meromorphic functions. We discuss some geometric aspects and further questions, in relation to conjectures of Lang and Vojta.
Pillay, Anand
A Lindemann-Weierstrass theorem for semi-abelian varieties over function fields
View Abstract Hide Abstract
The Lindemann-Weierstrass theorem says that if x_{1},..,x_{n} are algebraic numbers which are linearly independent over the field of rationals, then e^{x_{1}},..,e^{x_{n}} are algebraically independent. We will give a differential algebraic analogue for possibly non-isoconstant semiabelian varieties over {bf C}(t). The isoconstant case is included in a theorem of Ax. (Joint work with Daniel Bertrand) rationals, then e^{x_{1}},..,e^{x_{n}} are algebraically independent. We will give a differential algebraic analogue for possibly non-isoconstant semiabelian varieties over {bf C}(t). The isoconstant case is included in a theorem of Ax.
Point, Françoise
Witt modules
View Abstract Hide Abstract
We consider valued difference fields of either mixed or equal characteristic as valued modules over the Ore ring of Frobenius polynomials. Under certain assumptions on the residue field and value group, we prove a quantifier elimination result first in the pure module language, then in the language augmented with a chain aof additive subgroups and finally in a two-sorted structure with a valuation map. We apply it to prove that these structures do not have the independence property.
Poonen, Bjorn
Characterizing Z in Q with a universal-existential formula
View Abstract Hide Abstract
We prove that Z in definable in Q by a formula with 2 universal quantifiers followed by 7 existential quantifiers. It follows that there is no algorithm for deciding, given an algebraic family of Q-morphisms, whether there exists one that is surjective on rational points.
Razon, Aharon
On Rumely's local-global principle
View Abstract Hide Abstract
Rumely's local global principle gives an affirmative solution to Hilbert's Tenth Problem over rings of integers of large algebraic fields. In a joint work with M. Jarden, we generalize our earlier paper on Rumely's local global principle to remove the perfectness assumption on the field and to include archimedean primes.
Scanlon, Thomas
Defining valuations on curves
View Abstract Hide Abstract
We discuss a method for defining the valuations corresponding to closed points on the function fields of curves over f.g. fields based on a local-global principle of Auslander and Brumer.
Shlapentokh, Alexandra
HTP over algebraic extensions of rational numbers: normforms vs. elliptic curves. Part 1: normforms, Part 2: elliptic curves
View Abstract Hide Abstract
We will use some old and new results to discuss how norm forms and elliptic curves have been used to show Diophantine undecidability of rings inside algebraic extensions of rational numbers.
Silverman, Joseph H
P-adic properties of elliptic divisibility sequences
View Abstract Hide Abstract
Elliptic divisibility sequences arise as sequences of denominators of the multiples of points on elliptic curves. I will summarize some of the basic properties of such sequences, including Ward's characterization in terms of the classical Weierstrass sigma function, and then will discuss a p-adic version of Ward's result that can be used to prove that certain subsequences converge p-adically to numbers that are algebraic over Q.
Stange, Katherine
From elliptic divisibility sequences to elliptic nets
View Abstract Hide Abstract
An elliptic net is a map W: mathbb{Z}^n rightarrow mathbb{Z} determined by a choice of elliptic curve E and n rational points P_1, ldots, P_n in E. In a sense to be made precise, W(a_1,ldots,a_n) is associated to the linear combination a_1P_1 + ldots + a_nP_n. The values can be generated from a finite initial set via a recurrence relation. Elliptic divisibility sequences arise as the n=1 case. I will give an introduction to the topic, and show how many of the important properties of elliptic divisibility sequences generalise to elliptic nets. Nets can also be defined more generally for elliptic curves over arbitrary fields.
Streng, Marco
Divisibility sequences for elliptic curves with complex multiplication
View Abstract Hide Abstract
Elliptic divisibility sequences arise as sequences of denominators of the integer multiples of a rational point on an elliptic curve. Such sequences are known to have primitive divisors from some point on. If the elliptic curve has complex multiplication, then we show how the endomorphism ring can be used to index a similar sequence and we prove that this sequence also has primitive divisors. The classical proof fails in this context and will be replaced by an inclusion-exclusion argument and sharper diophantine estimates.
Vsemirnov, Maxim
Diophantine encoding and generalized Cantor's polynomials
View Abstract Hide Abstract
There are two especilally nice functions among all one-to-one mappings from NxN onto N. These functions are very "simple" and natural as they are given by polynomials. They were already known to G.Cantor. The construction can be generalized to higher dimensions in several ways. The problem of classification of bijective polynomial mappings from NxNx...xN onto N was raised by C.Smorynski. It gives us another example of a number-theoretic problem which is easy to state and hard to solve. Even in the simplest case of quadratic polynomials in two variables the first proof required very deep tools. Only recently new and more elementary approaches were found. They can be also extended to cubic polynomials in three variables. In that case some properties of elliptic curves come into play. In my talk I shall give an overview of the problem and concentrate on recent developments.

Participants

Name	Institution
Aliev, Iskander	University of Edinburgh
Cherlin, Gregory	Rutgers University
D'Aquino, Paola	Seconda Università di Napoli
Demeyer, Jeroen	Ghent University
Eisentraeger, Kirsten	University of Michigan
Everest, Graham	University of East Anglia
Flenner, Joseph	University of California, Berkeley
Geyer, Wulf-Dieter	University of Erlangen-Nurnberg
Gica, Alexandru	University of Bucharest
Ingram, Patrick	University of Toronto
Jarden, Moshe	Tel Aviv University
Koenigsmann, Jochen	Max Planck Institut für Mathematik
Macintyre, Angus	University of London
Mahe, Valery	University of East Anglia
Matiyasevich, Yuri	Steklov Institute of Mathematics
Michaux, Christian	Université de Mons-Hainaut
Moret-Bailly, Laurent	IRMAR, Université de Rennes 1
Pheidas, Thanases C	University of Crete
Pillay, Anand	University of Leeds
Point, Françoise	Mons-Hainaut University
Poonen, Bjorn	University of California, Berkeley
Razon, Aharon	Elta Systems
Riviere, Cedric	University of Mons-Hainaut
Scanlon, Thomas	University of California, Berkeley
Shlapentokh, Alexandra	East Carolina University
Silverman, Joseph H	Brown University
Stange, Katherine	Brown University
Stephens, Nelson	Bristol University
Streng, Marco	Universiteit Leiden
Swart, Christine	University of Cape Town
Van Geel, Jan	Ghent University
Vidaux, Xavier	Universidad de Concepción
Videla, Carlos	Mount Royal College, Calgary
Vsemirnov, Maxim	Steklov Institute of Mathematics
Zahidi, Karim	University of Ghent