## Number Theory and Computability

### 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:

### 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
Demeyer, Jeroen
Diophantine sets of polynomials over a finite field
View Abstract
Eisentraeger, Kirsten
First-order undecidability and Hilbert's Tenth Problem for function fields of positive characteristic
View Abstract
Everest, Graham
The arithmetic of elliptic divisibility sequences
View Abstract
Jarden, Moshe
Undecidability of families of rings of totally real integers
View Abstract
Koenigsmann, Jochen
A Galois theoretic approach to decidability of fields
View Abstract
Matiyasevich, Yuri
Computation paradigms in the light of Hilbert's tenth problem
View Abstract
Moret-Bailly, Laurent
Positive-existential definability in Noetherian rings
View Abstract
Pheidas, Thanases C
Meromorphic maps of the punctured torus to the torus and undecidability
View Abstract
Pillay, Anand
A Lindemann-Weierstrass theorem for semi-abelian varieties over function fields
View Abstract
Point, Françoise
Witt modules
View Abstract
Poonen, Bjorn
Characterizing Z in Q with a universal-existential formula
View Abstract
Razon, Aharon
On Rumely's local-global principle
View Abstract
Scanlon, Thomas
Defining valuations on curves
View Abstract
Shlapentokh, Alexandra
HTP over algebraic extensions of rational numbers: normforms vs. elliptic curves. Part 1: normforms, Part 2: elliptic curves
View Abstract
Silverman, Joseph H
P-adic properties of elliptic divisibility sequences
View Abstract
Stange, Katherine
From elliptic divisibility sequences to elliptic nets
View Abstract
Streng, Marco
Divisibility sequences for elliptic curves with complex multiplication
View Abstract
Vsemirnov, Maxim
Diophantine encoding and generalized Cantor's polynomials
View Abstract

### 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 University of Oxford
Macintyre, Angus Queen Mary 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 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