PDFLINK |

# Definability and Arithmetic

Communicated by *Notices* Associate Editor Antonio Montalbán

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 in the obvious way. -structure

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 while -formula, is an -formula.

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

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

Let be an Formulas with -structure. 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 by the formula -defined

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:

As a consequence we finally get

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 without quantifiers. For instance, consider the formula -formula

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

The sets in -definable 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:

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 . is -structure*o-minimal* if all subsets of -definable 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 ) .

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

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.

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

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.

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:

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.

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 ), of elliptic curves with complex multiplication. -invariants

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 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 -adic (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 ) methods. -adic

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.

### 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 : theorem we have that -squares 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 A set -structure. 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:

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!

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:

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:

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:

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. ?

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:

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:

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

(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: .

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:

The connection with is given by the following folklore result:

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:

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 given by groups in the obvious way. Then the trivial group, up to isomorphism, can be defined by the -structures -sentence:

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

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

While it is obvious that isomorphic are elementarily equivalent, the converse is false in general. For instance, over the language -structures the fields and

The natural fields that one considers when doing arithmetic geometry are *finitely generated fields*. For instance, global fields such as

There has been considerable progress on this problem and one can refer to the work of Duret, Pierce, Poonen, Pop, Rumely, Sabbagh, Scanlon, and Vidaux, among others.

A recent preprint by Dittmann and Pop finally proves Conjecture 24, provided that one excludes the fields of characteristic