Student seminar Hilbert's Tenth Problem

Teacher, Time and Venue, Participants

Teacher is Jaap van Oosten. He can be found at room 5.07, tel. 3305. Email: j.vanoosten AT uu.nl

Participants: Simon Docherty, Nils Donselaar, Eric Faber, Eduardo Gomezcana, Saskia van den Hoeven, Joep Horbach, Merlijn Koek, Fabio Pasquali, Niels Voorneveld, Jetze Zoethout

The meetings are on Mondays, 13:15-15:00, in room 610. First meeting: Week 39 (Monday September 23) 2013.

Requirements, Learning Goals and Grading

Every student presents material, in a blackboard talk. It is permitted to distribute handouts to the audience. The talk lasts 2x45 minutes, but leave 10 minutes free for discussion.

Additionally, every speaker formulates a homework exercise, which the other participants do, and hand in to the speaker a week later. De speaker then grades this work and hands everything (including a model solution) to the teacher. The teacher, after examination, hands the grades to the participants.

Attendance is compulsory.

Learning goals are:
1. Student is able to rework a given text into a coherent and understandable presentation
2. Student has good understanding of the mathematics in the field of the seminar
3. Student can formulate relevant and challenging exercises

Your final grade is composed of your grade for the presentation (40%, of which 20% for understanding the mathematics and 20% for communicating it), the formulation and grading of the homework exercise (10%) and your solutions to the other speakers' exercises (50%).

Subject Matter of the Seminar

In 1900, David Hilbert proposed 23 problems to the mathematical community as being the important ones to solve in the 20th century. His 10th problem reads (in contemporary language):

Find an algorithm for determining whether a polynomial equation with integer coefficients in several unknowns, has a solution in the integers

In 1970, the young Russian mathematician Yuri Matiyasevich proved that it is impossible to find such an algorithm. Matiyasevich built on work by Davis, Putnam and (Julia) Robinson, but his proof also spawned further research on "definability" and "decidability" questions in the theory of number fields, disclosing interesting connections between logic and number theory.

Reading Material

On Hilbert's Tenth Problem, also by Matiyasevich (lectures, University of Calgary 2000). We shall work through these notes in the first five sessions of the seminar.

After this, we shall treat a selection of research papers from the list below:

• Julia Robinson, Definability and Decision Problems in Arithmetic, Journal of Symbolic Logic 14, 2(1949),98--114
  Shows that various arithmetical functions are definable in others (for example, addition is definable in multiplication and the successor function); and the celebrated fact that the integers are definable in the language of rings, in the rational numbers. Uses a bit of number theory (Hasse theorem, Legendre symbol)
• Julia Robinson, Existential Definability in Arithmetic, Transactions of the AMS 72,3(1952),437--449
  Shows that the exponential function is existentially definable in any relation of roughly exponential growth
• Jan Denef, Hilbert's Tenth Problem for Quadratic Rings, Proc. AMS 48 (1975), 1, 214-220
  Proves the unsolvability of Hilbert 10 for such rings. Here is a page with a comment on Denef's paper.
• Jan Denef, The Diophantine Problem for Polynomial Rings and Fields of rational Functions, Transactions AMS 242 (1978),391-399
  Proves the unsolvability of Hilbert 10 for such rings; uses some theory of elliptic curves
• Jan Denef, Diophantine sets over Z[T], Proc. AMS 69 (1978), 148-150
• J. Denef and L. Lipshitz, Diophantine sets over some rings of algebraic integers, Journal of the London Math. Soc. (2),18 (1978), 385-391
• J. Denef, Diophantine sets over algebraic integer rings II, Trans. AMS 257 (1980),1,227-236
• Thanases Pheidas, An undecidability result for power series rings of positive characteristic, Proc. AMS 99 (1987), 2, 364-366
• Thanases Pheidas, An undecidability result for power series rings of positive characteristic II, Proc. AMS 100 (1987), 3, 526-530
• Thanases Pheidas, Hilbert's Tenth Problem for Fields of rational functions over finite fields, Inventiones Math. 103 (1991),1--8
  These Pheidas papers look accessible
• Yuri V. Matiyasevich, My Collaboration with Julia Robinson, Math Intelligencer 14(4): 38--45 (1992)
  A nice piece of history
• Bjorn Poonen, Hilbert's Tenth Problem over Rings of Number-theoretic Interest, lecture notes, Tucson 2003
• Jeroen Demeyer, Recursively Enumerable Sets of Polynomials over a finite Field, Journal of Algebra 310 (2007),2,801--828
• Jeroen Demeyer, Recursively Enumerable Sets of Polynomials over a finite Field are Diophantine, Inventiones Math. 170, 3 (2007), 655-670
  These Demeyer papers look accessible; uses some recursion theory
• Notes on Hilbert's Tenth Problem over Q, by Marco Streng (June 2007)
• Bjorn Poonen, Undecidability in Number Theory, Notices of the AMS 55,3(2008), 344-350
  A very recommended overview of recent trends
• Jochen Koenigsmann, Defining Z in Q, preprint on ArXiv, 2010
  Probably too hard, but has amusing facts. Exhibits a definition of Z in Q by a universal formula, and argues that such a definition by an existential formula is probably impossible.
• For those of you who read Dutch: the Leuven master thesis Hilberts Tiende Probleem en aanverwante kwesties by Frank Feys, treats a lot if material in great detail and could be of help when you prepare your talk.

Schedule

Week 39

Saskia van den Hoeven: Chapter 1 of Matiyasevich's notes Homework Model Solution

Week 40

Nils Donselaar: Chapter 2 of Matiyasevich's notes Homework Model Solution

Week 41

Jetze Zoethout: Chapter 3 of Matiyasevich's notes Homework Model Solution

Week 42

Merlijn Koek: Chapter 4 of Matiyasevich's notes Homework Model Solution

Week 43

Eric Faber: Chapter 5 of Matiyasevich's notes Homework Model Solution

Week 44

Niels Voorneveld: the first Robinson paper Homework Model Solution

Week 45

Simon Docherty: the second Robinson paper Homework

Week 46

Eduardo Gomezcana: the first Denef paper Homework Model Solution

Week 47

Joep Horbach: the first Pheidas paper Homework Model Solution

Week 48

Saskia van den Hoeven: the second Pheidas paper Homework Model Solution

Week 49

Nils Donselaar: the third Pheidas paper Homework Model Solution

Week 50

Jetze Zoethout: the first Demeyer paper, first part Homework Model Solution

Week 51

Eric Faber: the first Demeyer paper, second part Homework Model Solution

Week 2

Monday, January 6 Niels Voorneveld: the second Demeyer paper Homework Model Solution

Week 3

Tuesday, January 14 Simon Docherty: the second Denef paper Homework Model Solution

Week 4

Tuesday, January 21 Eduardo Gomezcana: the Denef-Lpshitz paper Homework Model Solution

Week 5

Tuesday, January 28 Joep Horbach: the fourth Denef paper Homework
The last set of homework is due Thursday February 6, either in my mailbox or as an email to me.

Week 8

Wednesday February 19, 13:30, room 610 Evaluation and grading.

Terug naar de basis.