Fifty-year-old maths problem finally solved at St Hilda’s

31st August 2023
Portrait of Dr Jamshid Derakhshan

A theoretical problem first posed half a century ago has finally been solved when two mathematicians shared a Eureka moment followed by coffee and biscuits in the common room at St Hilda’s College, Oxford University.

Dr Jamshid Derakhshan (pictured), who lectures in pure mathematics at St Hilda’s, and Professor Angus Macintyre FRS from the University of Edinburgh, have been working together at the interface of logic, number theory and algebra for more than 15 years to develop a model theory for adeles.

Their breakthrough published in July 2023 in the Forum of Mathematics Sigma, a leading open source journal, came when they suddenly realised they could apply this work to a problem first posed in 1968 by James Ax.

Such problems date back to a question posed by Hilbert in 1900 on the existence of an algorithm to “decide” if a polynomial with integer coefficients has an integer root, and Godel’s incompleteness theorem proving that it is impossible to verify whether some statements about natural numbers are true or false.

Having proved such a decidability was true for the entire family of finite fields in a pioneering and very influential work in 1968, Ax posed his problem: Was there an algorithm that could decide for any given mathematical statement if it would hold true for all congruence number systems Z/mZ for all m greater than 1?

As Dr Derakhshan describes it, what they were looking for was a Turing machine that could decide the truth or falsehood of each statement.

The breakthrough came when the two mathematicians realised they could build a bridge between adeles and the congruence number systems.

“The methods of the model theory on adeles we had developed enabled us to get a very short solution to the problem very quickly,” says Dr Derakhshan.

The pair had not thought of the problem when they first developed their theory and had published several papers on the theory before their revelation.

“One day, after thinking a lot on several related issues, we realised we could establish a suitable bridge between our theory and the problem of Ax,” says Dr Derakhshan. “We could see the connection quite clearly immediately. Once we had this connection, the solution was just there. This bridge is what in logic is called an interpretation of one structure in another one.”

Dr Derakhshan believes solving Ax’s problem must be useful in advancing important subjects as it is addressing a very basic question about basic structures.

The sets Z/mZ are much used in pure mathematics especially algebra and number theory, but also in discrete mathematics, combinatorics, theoretical computer science and cryptography.

The bridge connecting these structures to adeles could help understand many deeper areas. Part of this connection and analysis goes via meta-mathematics (using logic to analyse mathematical structures in a different way). Dr Derakhshan believes these connections and interactions should have many applications.

Unusually, the solution to Ax’s problem is only four pages long, which as Dr Derakhshan explains, indicates “the unity and vitality of mathematics and the deep connections that lie within between different subjects and areas such as logic, algebra, analysis and number theory.”

In his opinion, these kinds of solutions springing from new connections are often the most beautiful and elegant.

“Often, they don’t involve tedious or long proofs or calculations,” he says. “You can just see them as a mathematical reality when someone finds them.”

What’s next? He is aiming to relate model theory of adeles with Diophantine geometry (which studies curves defined by polynomials with integer or rational coefficients) and connect integration on adeles with L-functions of curves (which are analytic functions constructed from the number of points on the curve modulo primes). Such connections would be relevant for important problems such as the Birch and Swinnerton Dyer conjecture on elliptic curves (a Millennium Problem) and the Langlands Functoriality Conjecture on adelic groups which unifies representation theory and number theory.

For mathematicians

James Ax posed his problem in a celebrated and revolutionary paper published in 1968 in Annals of Mathematics. In that paper Ax proves that given a statement (a sentence involving addition and multiplication as well as quantifiers) that is first-order in the sense that quantifiers range over objects, there is an algorithm to decide whether that statement is true in all finite fields, and his paper was the start of a whole subject in model-theoretic algebra.

Such decidability questions in mathematics go back to a famous problem of Hilbert asked in the 1900 International Congress of Mathematicians (Hilbert’s 10th problem from his list of 21 problems) asking if there is an algorithm to decide whether a given polynomial with integer coefficients has an integer root.

In 1931, Godel’s famous incompleteness theorem proved that there are statements about natural numbers that cannot be decided to be true or false, and in the 1970’s Hilbert’s 10th problem turned out to have a negative answer following work by several mathematicians.

Ax’s problem asked in that paper was whether there is an algorithm to decide if a given first-order mathematical statement is true in all the congruence number systems Z/mZ for all m greater than 1. We recall the definition of these number systems. Consider the set Z of all integers …,-1,-2,-1,0 1,2,....

For any integer m we can “reduce” the integers modulo m and get the set {0,1,…,m-1} where m is put to be 0, m+1 is put to be equal to 1, and m+2 is put to be equal to 2 etc. More precisely, we identify integers a and b if their difference a-b is divisible by the number m (one says a and b are congruent modulo m).

The resulting set is denoted by Z/mZ={0,1,…,m-1}. For example the clock is a number system modulo 12. There is an addition and multiplication defined on Z/mZ coming from the addition and multiplication on Z.

The problem remained open since 1968 since it was beyond the tools available in the subject of model theory of fields at that time.

An example of a first-order mathematical statement is sentence “A polynomial with integer coefficients has a root”, or the sentence “-1 has a square root”.

The sets Z/mZ were studied systematically for the first time by Carl Friedrich Gauss in his famous opus magnum Disquisitiones Arithmaticae written in 1798 when he was 21 years old and published three years later. This remarkable book pioneers many areas of modern number theory and algebra.

The family of Z/mZ is of fundamental importance in many areas. From Z we get infinitely many finite sets Z/mZ which are much easier to study than Z, and from all these Z/mZ mathematicians hope to be able to go back to Z or the rational numbers and solve various number-theoretic problems.

That explains why these sets Z/mZ are of great importance in number theory and pure maths. They are also fundamental in theoretical computer science and cryptography.

The adeles of number theory are constructed from infinitely many number systems including the real numbers and all p-adic numbers for all prime numbers p and were introduced by Emil Artin in 1945. The p-adic numbers were discovered by Hensel in 1930 and are “non-archimedean” analogs of the real numbers. There are also “geometric adeles” which were introduced by Andre Weil in 1937 and related concepts were defined by Claude Chevalley in the 1930’s.

Both arithmetic and geometric adeles became important parts of modern number theory and geometry and have played a crucial role in many developments. The connections established by Dr Derakhshan and Professor Macintyre between adeles and all Z/mZ give new insights into solutions of other problems. The use of adeles to solve Ax’s problem has been powerful and unexpected.