Skip to Main Content

Definability and Arithmetic

Hector Pasten

Communicated by Notices Associate Editor Antonio Montalbán

Article cover

The purpose of this article is to give an overview of some very active interactions between first order definability and arithmetic. However, even to get started we need to clarify what we mean by “first order definability”. The reader who is already familiar with these notions can safely skip directly to the second section.

For the experts, we would like to clarify that this introductory note is not intended to be a comprehensive survey, and many interesting topics are left out by space limitations: uniformity and effectivity in unlikely intersections, arithmetic of complex function fields, Diophantine sets of infinite extensions of , etc. Furthermore, at several points we prefer to discuss less-general theorems for the sake of clarity of the exposition. Nevertheless, further reading will be indicated at the relevant points.

Languages and structures

For us, a language will be a set consisting of symbols for constants, for relations, and for functions. An -structure is a set endowed with some distinguished constants, relations, and functions that give meaning to the symbols in . For instance, the language of arithmetic is and any (semi-)ring is an -structure in the obvious way.

Given a language , a (first order) -formula is a finite string of symbols that only uses the quantifiers and , the conjunction , the disjunction , implications and , the negation symbol , parentheses, and symbols from (we may use commas to improve readability). One requires that such a formula is well-written: it can be read. For instance, the string of symbols is not an -formula, while is an -formula.

An -formula may or may not have free variables (variables not under a quantifier) and both cases are of interest to us.

Formulas without free variables are called sentences, and given an -structure they can be true or false in the given structure. For instance, recall our -formula ; this is true over but it is false over . If is an -sentence and is an -structure, we write to express that is true on .

Let be an -structure. Formulas with free variables can be used to define subsets of . Indeed, we say that is defined by an -formula with free variables if for every tuple , we have that if and only if .

Let us clarify this important idea with an example. Consider the -structure and the inequality relation

This is -defined by the formula

because the pairs such that holds are precisely the elements of .

A final disclaimer: for the sake of exposition we will often identify the symbols in a language with their interpretation in a structure.

Equipped with these notions, let us discuss a first example of how definability interacts with arithmetic.

What can be expressed using addition?

As a warm-up, let us discuss a classical problem: to understand the sets over the integers that can be defined using addition.

For instance, one can ask whether we can define multiplication in using addition. To have a more precise question we need to be clear about what we mean by “define”. For our purposes, we will restrict our attention to first order formulas over a language. In our case the language will be which is interpreted in in the usual way. Then the question can be formulated as: Is multiplication in definable by a first order formula over the language ?

The key to answer this question is the following classical result of Presburger, which follows from a general result on elimination of quantifiers 16:

Theorem 1 (Presburger).

A subset is first order definable over the language if and only if is eventually periodic: there is such that is periodic in the set .

As a consequence we finally get

Corollary 2.

Multiplication in is not first order definable over the language .

Proof.

Suppose it is. Then so is the set of squares , but this set is not eventually periodic.

The connection between definability and arithmetic in Presburger’s theorem is rather direct. Let us discuss another kind of definable sets that enjoy a less obvious connection with arithmetic.

O-minimal structures

Consider as a structure over the language of real-closed fields expanded by allowing constants from in our formulas.

It is a classical theorem of Tarski that over the language admits elimination of quantifiers: every -formula is equivalent over to an -formula without quantifiers. For instance, consider the formula

(where ). Over this formula defines the interval and, in fact, the same set is defined by the quantifier-free formula

The -definable sets in are called semi-algebraic and, due to elimination of quantifiers, they are exactly the sets defined by finitely many equations and inequalities between polynomials. In particular we get the following consequence of Tarski’s theorem:

Corollary 3.

All the -definable subsets of are finite unions of points and (possibly unbounded) intervals.

The concept of o-minimality —introduced by van den Dries 2— comes as a generalization of this structural result for definable subsets of . This was further developed by Steinhorn, Marker, and many others.

Consider as a structure over a language expanding . We say that this -structure is o-minimal if all -definable subsets of are finite unions of points and intervals.

As an example of a structure which is not o-minimal, consider with the language consisting of and the sine function. Then the (quantifier-free) formula defines a discrete infinite set in .

One can ask about o-minimal structures beyond over . A first example, due to Denef and van den Dries after work of Gabrielov, is the following: let be the structure over the language consisting of augmented by all functions (for all ) that are real analytic on some open neighborhood of .

Theorem 4.

The structure is o-minimal.

On the other hand, let be the exponential function and let be the structure over the language . Then we have the following celebrated theorem of Wilkie:

Theorem 5.

The structure is o-minimal.

Van den Dries and Miller generalized the previous two results by showing o-minimality over . In fact, o-minimality has been proved over several other languages, but we do not intend to present a survey here.

Definable sets over o-minimal structures are very well-behaved, which allows for a rich theory that generalizes real algebraic geometry (which is the case of over ). Some of the results that can be proved in this generality are existence of cell-decompositions, a good theory of dimension, finiteness of connected components, and parametrization results.

We refer the reader to 3 for an exposition of the theory of o-minimal structures.

Counting rational points

Having discussed the notion of o-minimal structures, let us now turn into connections with arithmetic.

For a rational number with coprime integers, the height of is . The height of a tuple is defined as . For a subset and we define

The story begins with the following counting result of Pila which builds on an earlier result by Bombieri and Pila.

Theorem 6.

Let be a transcendental real analytic function on an open set containing and let be its graph. Let . There is a number such that for all we have

The hypothesis that is transcendental cannot be dropped, as can be easily seen by considering, for instance, .

Naturally, counting rational points is a topic of great arithmetic interest and the previous result provides a very general tool valid for rational points in curves. Pila and Wilkie 12 managed to prove a far-reaching generalization. For this we need to define the transcendental part of a set.

Given a set , we denote by the union of all connected positive dimensional semi-algebraic subsets of (i.e., those definable over or, equivalently, those definable by finitely many equations and inequalities between polynomials). The transcendental part of is . We remark that, in general, is not semialgebraic.

With this notation, the Pila–Wilkie theorem is

Theorem 7.

Let over be an o-minimal structure and let be -definable. Let . There is such that for all we have

Observe that Theorem 6 is a special case when we consider the o-minimal structure .

We remark that in order to get the bound it is unavoidable to discard as this subset can accumulate too many rational points.

While all of this is of course very interesting in its own right, it turns out that since the late 2000s, the point-counting theorems in o-minimal structures have found remarkable and unexpected applications in Diophantine Geometry, in the context of unlikely intersections.

Unlikely intersections

Let be an algebraic variety over endowed with a countable set of “special” points and let be a properly contained subvariety of . Counting dimensions, the intersection is unlikely to happen even if is Zariski dense in . Thus, one might expect to be small, even finite, unless there is a good reason for this to be otherwise.

Here is a concrete instance of this phenomenon. Consider the two-dimensional multiplicative group and its set of torsion points, namely, pairs where are roots of unity. Then is countable and Zariski dense in . Now consider an irreducible curve. Is infinite? A good reason for this to happen would be that is a multiplicative subgroup of , or even a multiplicative translate by a point in . For example, the hyperbola is a multiplicative subgroup and it contains all the points for a root of unity. Lang conjectured that, in fact, this is the only way that can be infinite. The result was later proved, independently, by Ihara, Serre, and Tate.

Theorem 8.

Let be an irreducible curve containing infinitely many torsion points (i.e., points of the form with roots of unity.) Then is the translate by a torsion point of a multiplicative subgroup of .

The previous result has been generalized in a number of ways and there are several other important problems in the subject of unlikely intersections, but here we will restrict our attention only to two of them: the Manin–Mumford conjecture and the André–Oort conjecture.

In its simplest form, the Manin–Mumford conjecture asked the following:

Conjecture 9.

Let be a smooth projective curve of genus defined over a number field , contained in its Jacobian . Then contains at most finitely many torsion points of .

This is a remarkable statement; note that the torsion points of are dense in even in the complex topology, but somehow the curve manages to avoid almost all of them!

The Manin–Mumford conjecture was proved by Raynaud in 1983. Several other proofs came afterward. In 2008 Pila and Zannier gave a new proof via point counting in o-minimal structures. Let us briefly outline the argument.

Sketch of proof.

The abelian variety , over , is biholomorphic to for a suitable lattice . Thus, there is a real-analytic uniformization which descends to , hence, having as a fundamental domain.

The points in corresponding to torsion points of are precisely those with rational coordinates, and the height of such rational points in is essentially the same as the order of the corresponding torsion point in .

On the other hand, the complex curve corresponds, via , to a certain -definable set . One wishes to show that has only finitely many rational points. For the moment, let us assume that , so that . By the Pila–Wilkie theorem on the o-minimal structure , for every we have

But if is a torsion point of large order and it belongs to , then its Galois orbit over the base number field has to be considerably large (a precise estimate was proved by Masser; alternatively, one can use results of Serre), giving too many torsion points in : the whole Galois orbit of . A careful analysis of the situation leads to a lower bound of the form

for certain fixed and . This contradicts the upper bound coming from the Pila–Wilkie theorem. Then one has to justify why to conclude the argument.

The approach in the previous sketch of proof is known as the Pila–Zannier strategy.

This leads to the following general question: Given a transcendental analytic uniformization of an algebraic variety , how to characterize those sets such that both and are algebraic? Such sets might be called bi-algebraic for . Of course this is only a vague question, but in many applications of the Pila–Zannier strategy it is a crucial step of the argument in order to compute . Nowadays there is a general approach to computing bi-algebraic sets by means of generalizations of the Ax–Schanuel theorem from functional transcendence.

Another important problem in the setting of unlikely intersections is the André–Oort conjecture. This concerns the special points (in a technical sense) of a Shimura variety; in the simplest case, an example of Shimura variety is the affine line over (seen as the modular curve ), and its set of special points are the -invariants of elliptic curves with complex multiplication.

Conjecture 10.

Let be a Shimura variety and let be an irreducible subvariety of . If the set of special points of contained in is Zariski dense in , then is a special subvariety.

After partial progress by André (unconditional) and Edixhoven (under GRH), a breakthrough occurred in 2011 when Pila unconditionally proved the André–Oort conjecture for products of modular curves using the Pila–Zannier strategy.

These ideas led to a series of advances on the André–Oort conjecture by several authors. It soon became clear that the two main difficulties were: necessary results on bi-algebraic sets for the relevant analytic uniformizations, and lower bounds on the size of Galois orbits of special points. The first difficulty was solved by Klingler, Ullmo, and Yafaev in 2014. The issue on sizes of Galois orbits remained as the final obstruction. Very recently, a preprint by Pila–Shankar–Tsimerman finally proves the André–Oort conjecture in full generality by bringing -adic Hodge theory into the study of heights of special points. This builds on work of Binyamini–Schmidt–Yafaev (based on an idea of Schmidt) and an earlier result by Tsimerman for (which crucially relies on work of Masser–Wüstholz, Andreatta–Goren–Howard–Madapusi Pera, and Yuan–Zhang). But this is not the end of the story; the Zilber–Pink conjecture still awaits on the horizon!

There are several excellent expositions about the connections between o-minimality and Diophantine geometry. See for instance 4 or 20.

Diophantine equations

Let us go back to the basics: Diophantine equations. These are polynomials equations in possibly many variables and having integral coefficients, for which integral or rational solutions are sought.

The topic is very old. It seems that the earliest written record of a (non-linear) Diophantine equation is the Babylonian clay tablet Plimpton 322, written about 1800 BC. This tablet displays several integral solutions of the Diophantine equation .

However, Diophantine equations are named after the greek mathematician Diophantus of Alexandria (3rd century AD), due to his series of books Arithmetica where he presents a systematic study of several of these equations. In Arithmetica, Diophantus provides examples of integral and rational solutions of Diophantine equations along with a detailed explanation of the method by which the solutions were found.

In modern language, here are some remarkable examples from Arithmetica:

Book II, problem 8: Parametrization of the conic by rational functions, using the chord method.

Book IV, problem 24: Duplication of points in the elliptic curve by the tangent method.

Book VI, problem 17: Construction of rational points in the genus curve (birational to ) by specializing an algebraic identity. This equation was fully solved by Wetherell in the nineties using -adic methods.

Diophantus’s Arithmetica deeply influenced several scholars who wrote notes on the margin of their copies of the book. Just to mention two:

Around 1637 Fermat wrote in the margin of Book II, problem 8 (quoted above) the statement of his famous “Last Theorem” (solved in the nineties by Wiles) along with an apology for not having enough space for writing his proof.

On the other hand, two centuries earlier than Fermat, Chortasmenos wrote in the margin of the same problem “May your soul, Diophantus, be with Satan because of the difficulty of your other theorems and, particularly, of this one.” And in fact, Diophantine equations are truly difficult in a technical sense.

In 1900 Hilbert proposed a famous list of 23 problems. The tenth problem in the list was the following:

Hilbert’s Tenth Problem (HTP): Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

The notion of “process” in the statement of HTP was later formalized as Turing machine (or “algorithm” for short). After the work of M. Davis, H. Putnam, and J. Robinson, in 1970 Y. Matiyasevich gave a negative solution to this problem 8.

Theorem 11.

HTP is unsolvable: there is no algorithm to decide solvability in of Diophantine equations.

Diophantine sets of integers

Let us return to the subject of definability. The key to Theorem 11 is the notion of Diophantine set: those subsets of that can be defined using Diophantine equations. The precise definition is the following:

A set is Diophantine if there are polynomials such that for each we have if and only if there is with for all .

(We remark that one can always take by considering .)

As a first example of Diophantine set we have the odd integers: is odd if and only if there is with . Here, and .

A more interesting example is given by the relation : by the -squares theorem we have that if and only if there are with .

Here is an alternative way to think about Diophantine sets. Consider an affine algebraic variety defined by equations over and take its set of integral points . Now, project onto its first coordinates. The set constructed in this way is Diophantine, and every Diophantine set arises from this construction.

For instance, in our example of odd integers we can take as the line defined by , consider all integer solutions , and then project onto the -coordinate.

There is yet a third equivalent way to define Diophantine sets. Recall the language and consider as an -structure. A set is Diophantine if and only if it is defined by a positive existential -formula.

This requires some explanation. A formula is positive existential if the only quantifier in it is , it contains no negations, and the only connectives that it uses are and .

For instance, odd integers are defined by the formula .

One can use Diophantine sets to construct new ones. For instance, we can exhibit the relation as a Diophantine set by the positive existential formula

where each is hiding four existential quantifiers.

At first one might find the fact that the relation can be expressed over without using negations quite impressive. It makes us wonder what else can be presented as a Diophantine set over .

Certainly, not every subset of can be Diophantine: there are only countably many Diophantine sets (count the equations). A more interesting restriction is the following:

Lemma 12.

Every Diophantine set is listable: there is an algorithm that produces all of its elements and nothing else.

Proof.

Consider a Diophantine set defined by the formula

where is a polynomial (by our earlier remarks on multiplication of polynomials and sums of squares of polynomials, this suffices). Then let us algorithmically enumerate the elements and at each step evaluate . If one gets a non-zero value, we ignore this , while if we get we print the first coordinates of . This process algorithmically produces all the elements of and nothing else.

The previous lemma might seem to provide a restriction on Diophantine sets that is too weak. For instance, the set of factorials is certainly listable, while there is no obvious reason for it to be Diophantine. It turns out that, actually, there is no other restriction: Diophantine sets over are the same as listable sets!

Theorem 13 (DPRM).

Over , listable sets are the same as Diophantine sets.

Thus, for instance, the sets of factorials, powers of , primes, etc. are indeed Diophantine!

The DPRM theorem is named after M. Davis, H. Putnam, J. Robinson, and Y. Matiyasevich. The core of the proof is to use Diophantine sets to simulate any Turing machine; Davis, Putnam, and Robinson reduced the problem to showing that the graph of the exponential function () is Diophantine, while Matiyasevich provided the final step by showing that this is indeed the case 8.

While the knowledge of a precise description of all Diophantine sets is a remarkable achievement in its own right, it was obtained as a tool to give a negative solution to HTP. Let us explain this point:

Proof of Theorem 11 using DPRM.

Thanks to a theorem of Turing, the Halting problem from computability theory provides a set which is listable but it is not decidable: there is no algorithm to decide membership to .

Nevertheless, is listable, so it is Diophantine by the DPRM theorem. Let be a polynomial such that is defined by

Now, for each let be the polynomial . For the sake of contradiction suppose that HTP has a positive solution and let be an algorithm that decides solvability of Diophantine equations over .

Given apply to ; if the output is YES then has a solution in integers and , hence, . Otherwise, . This decides membership to ; a contradiction.

The DPRM theorem is not an isolated result and analogues have been obtained in other contexts. For instance we mention the work of Demeyer over .

Extensions of Hilbert’s tenth problem

Let be a (commutative, unitary) ring which is computable. Roughly speaking, this means that and its operations can be encoded in in a computable way, thus, one can use elements from as inputs for an algorithm (Turing machine).

Hilbert’s tenth problem can be seen as a special case of the following more general question:

Problem 14 ().

Is there an algorithm to decide the following? Given a system of polynomial equations over as input, to decide whether the system has solutions over .

In this generality one does not always have a negative solution. However, we are interested in rings with rich arithmetic, so that one can expect a negative solution to .

As we will see, the key to approach the generalized HTP is the notion of a Diophantine set over : the definition is the same as over but now the polynomials have coefficients in . Alternatively (and more convenient in practice) we say that is Diophantine (over ) if there is a positive existential formula over with parameters from (i.e., elements of are allowed in ) such that for each we have

We refer the reader to the excellent surveys 5 and 14 for more information on extensions of HTP, as well as the books 19 and 10. Here we will only focus in the case of rings of integers and global fields.

The case of rings of integers

A natural extension of Hilbert’s tenth problem is to ask the analogous question not only for but also for rings of integers of number fields, such as or the Gaussian integers .

Let be a number field, that is, a finite algebraic extension of . Let be its ring of integers. Denef and Lipshitz 1 proposed the following conjecture in the seventies:

Conjecture 15.

For every number field we have that has a negative solution.

But, how to approach this problem? Should we follow the DPRM strategy by simulating Turing machines over ? It turns out that we don’t have to reinvent the wheel.

Lemma 16.

Let be a number field. If is Diophantine over , then has a negative solution.

Proof.

Assume that is Diophantine in . For the sake of contradiction, suppose that there is an algorithm that decides solvability over of systems of polynomial equations over . Take any Diophantine equation over . Now consider the system over formed by the equation seen over and, for each variable , the requirement that (which by assumption can be done with Diophantine equations over !).

Apply to . If the output is YES then has a solution over with all the in , and if the output is NO then such a solution does not exist. Thus, we have decided solvability of over . We get a contradiction with the negative solution to .

So, the key is to show that is Diophantine in . We remark that, actually, it is a theorem of J. Robinson dating back to the fifties that is first order definable in for every number field ; it is the Diophantine definability what remains open.

In the seventies and eighties, Conjecture 15 was proved in the following cases:

is totally real or quadratic extension of totally real (Denef–Lipshitz)

has exactly one pair of complex conjugate embeddings (Pheidas, Shlapentokh, Videla)

is abelian over (Shapiro–Shlapentokh).

After a long hiatus, some new families of cases were proved by Mazur and Rubin in 2015 and by Garcia-Fritz and Pasten in 2019.

In addition, Conjecture 15 is known to follow from standard conjectures on elliptic curves: Mazur and Rubin proved this under the finiteness conjecture for Shaferevich–Tate groups, Murty and Pasten proved this under the BSD conjecture, and most recently Pasten proved this under certain well-known conjecture on ranks of fibres of elliptic surfaces. See 9 and the references therein for more details.

All the recent progress on Conjecture 15 has followed from an elliptic curve criterion proved independently by Poonen and Shlapentokh 18:

Theorem 17.

Let be an extension of number fields. If there is an elliptic curve over with positive rank over that remains the same over , then is Diophantine in .

This result has some predecessors in the work of Denef, Poonen, and Cornelissen–Pheidas–Zahidi. Currently, it is the most promising approach to showing that is Diophantine in for every number field , which in view of Lemma 16 would prove Conjecture 15.

Finally, we mention a surprising result of Shlapentokh 9 that considerably simplifies the problem:

Theorem 18.

Suppose that for every quadratic extension of number fields one has that is Diophantine in . Then for every number field we have that is Diophantine in .

Global fields

A global field is a field which is either a number field (finite extension of ) or the function field of a curve over a finite field. For the sake of exposition, let us restrict our attention to the two most basic cases: and for a prime power ( prime).

First, we have the following celebrated theorem of Pheidas 11:

Theorem 19.

If is odd, then has a negative answer.

(The case of even is due to Videla.) Pheidas proved this result by constructing an interpretation (in a technical sense) of in using positive existential formulas. Then one can transfer the negative answer of to a negative answer for very much as in the proof of Lemma 16. The proof of Theorem 19 requires definability of Frobenius orbits and of valuations. As of today, all the results on Hilbert’s tenth problem for positive characteristic function fields require in some way these two key steps. This technique has been generalized by several authors, and in particular, Eisentraeger and Shlapentokh extended Phedias’s theorem to all global function fields.

As the arithmetic of is believed to be analogous to that of , one expects that also has a negative solution, but this remains as a main open problem in the field. As in Lemma 16 the strategy is to show that is Diophantine in . There are several partial results in the literature, and we can highlight:

(i)

(J. Robinson 17) There is a first order definition of in .

(ii)

(Poonen 13) There is a computable set of primes with density in the primes such that has a negative solution.

(iii)

(Koenigsmann, 6) The set of non-integers is Diophantine in . Furthermore, there are definitions of in with quantifiers of the form and (a Diophantine definition would be of the form .)

On the other hand, it might be the case that is not Diophantine in , which would require an alternative approach to . First, we have the following conjecture of Mazur proposed in 1992:

Conjecture 20.

Let be an algebraic variety over and let be the real closure of its set of rational points in . Then is semi-algebraic; in particular, it has finitely many connected components.

This conjecture implies at once that is not Diophantine in ; otherwise, one would get an affine algebraic variety such that the projection of onto the fist coordinate is , contradicting Mazur’s conjecture.

In another direction, we have the following conjecture of the author:

Conjecture 21.

Let be a Diophantine set. Then the supremum of in , if finite, is algebraic.

The connection with is given by the following folklore result:

Lemma 22.

If is Diophantine in , then listable sets and Diophantine sets of are the same.

Thus, if is Diophantine in then the set of increasing decimal approximations of would be Diophantine, contradicting Conjecture 21.

In addition to the previous conjectures there is the following result of Kollár 7:

Theorem 23.

is not Diophantine in .

Thus, if one believes that the arithmetic of in is analogous to that of in , then this can be considered as evidence toward the non-Diophantineness of in .

Elementary equivalence versus isomorphism

So far we have discussed the connection between arithmetic and definability of sets inside a structure. But first order formulas over a language can also be used to define a structure across a class of -structures.

For instance, let be the language of groups and let us define as the class of -structures given by groups in the obvious way. Then the trivial group, up to isomorphism, can be defined by the -sentence:

That is, a group is isomorphic to the trivial group if and only if .

Two -structures that cannot be distinguished by the truth of first order -sentences are called elementarily equivalent: to so say, they have the same theorems (expressible by first order formulas). In our example, the trivial group seen as an -structure is only elementary equivalent to groups that are isomorphic to itself.

While it is obvious that isomorphic -structures are elementarily equivalent, the converse is false in general. For instance, over the language the fields and are elementarily equivalent (by a result of Tarski) but they are not isomorphic: one is countable and the other is not.

The natural fields that one considers when doing arithmetic geometry are finitely generated fields. For instance, global fields such as and are finitely generated. Let us call this class of fields and consider them as -structures. The following conjecture seems to have appeared in print by the first time in 15, although it was around already in the seventies:

Conjecture 24.

Within the class of -structures, isomorphism is the same as elementary equivalence.

There has been considerable progress on this problem and one can refer to the work of Duret, Pierce, Poonen, Pop, Rumely, Sab