University Seminar- Computability, Complexity, and Algebraic Structure- 10^(65 quadrillion) obstacles to Hilbert’s Tenth Problem

Time: Friday, September 5, 11:00am – 12:00noon

Place: Phillips B152

Speaker:  Keshav Srinivasan, GWU

Title: 10^(65 quadrillion) obstacles to Hilbert’s Tenth Problem

Abstract:  Hilbert's Tenth Problem, part of David Hilbert's famous list of problems proposed in the early 20th century, asks for an algorithm to decide which Diophantine equations have integer solutions and which do not. Davis, Matiyasevich, Putnam, and Robinson showed that there is no such algorithm, by showing that Turing Machines could be encoded into Diophantine sets and thus an algorithm for Hilbert's Tenth Problem would decide the Halting Problem, an impossibility. This has inspired efforts by logicians, number theorists, and algebraic geometers to solve generalizations of Hilbert's Tenth Problem for various algebraic number fields, by finding existential definitions of Z in those fields.  Toward that goal, Daans and Becher found a constructive reduction in the number of existential quantifiers required to define the intersection of Diophantine sets in an algebraic number field. We study numerical upper bounds on the degree of the Diophantine equations required to achieve this quantifier reduction. In many cases they can be 10^(65 quadrillion) or larger, demonstrating a striking tradeoff between number of quantifiers and polynomial degree.