WorksMathematics
Diophantine definability from addition and divisibility over rings of -integers
Abstract
Let be a number field, let be a finite set of places of containing the archimedean places, and let denote the ring of -integers of . We prove that multiplication is positive-existentially definable in if and only if the unit group is infinite. This extends a 1977 theorem of Lipshitz for rings of integers to rings of -integers. One of the key ingredients is a uniform bound for unit equations due to Evertse, Schlickewei and Schmidt, which we use to recover multiplication on the unit group.
MSC 2020: Primary 11U05; Secondary 03B25
Introduction
In the 1970s, Lipshitz [11] and, independently, Bel’tyukov [2] proved that one can decide algorithmically whether a system of linear equations and divisibility conditions has a solution in . More precisely, there is an algorithm which decides, given a system
in the unknowns , where the , and are linear polynomials with integer coefficients, whether it has a solution in . This is in sharp contrast with Hilbert’s tenth problem: by the theorem of Matiyasevich [Mat70], building on work of Davis, Putnam and Robinson [4], no such algorithm exists if polynomials of arbitrary degree are allowed. In the language of logic, the result of Lipshitz and Bel’tyukov says that the positive-existential theory of the structure is decidable. In a series of papers, Lipshitz also studied the problem over the ring of integers of a number field . He showed that it is decidable when is an imaginary quadratic field [11] and undecidable when is real quadratic [Lip78b], and that for every number field other than or an imaginary quadratic field, multiplication is positive-existentially definable in [10]. The latter result shows that the problem over is as hard as Hilbert’s tenth problem over , which was only recently shown to have a negative answer, by Koymans and Pagano [9] and, independently, by Alpöge, Bhargava, Ho and Shnidman [1]. Thus, for rings of integers, the problem is decidable precisely when the unit group is finite, and it is natural to ask what happens for rings of -integers.
So far, this question has been answered for and imaginary quadratic fields: Cerda-Romero and the author [3] showed that the problem is undecidable for for every integer , and Hormazábal and the author [8] extended this to rings of -integers of imaginary quadratic fields. The problem has also been studied in other directions; see, for instance, Pheidas [Phe04] for polynomial rings and Martínez-Ranero, Utreras and Vidaux [MUV22] for holomorphy subrings of global fields.
In this paper we treat arbitrary rings of -integers of number fields. Let be a number field, and let be a finite set of places of containing the set of archimedean places. The ring of -integers of is
Our main result is the following.
Theorem 1.1. Multiplication is positive-existentially definable in the structure if and only if the unit group is infinite.
By the -unit theorem, is infinite unless and is or imaginary quadratic. Thus multiplication is positive-existentially definable whenever , and when Theorem 1.1 recovers the theorem of Lipshitz [10] by a different method. The converse direction is immediate: if is finite, then the positive-existential theory of is decidable [11, 2], whereas Hilbert’s tenth problem over has a negative answer [Mat70, KP27, ABHS26], even for equations with integer coefficients (see Theorem 6.3), so multiplication cannot be positive-existentially definable. The results of [9, 1], combined with work of Eisenträger [5 Theorem 7.9], give a negative answer to Hilbert’s tenth problem over as well, even for equations with integer coefficients (see § 6). Together with Theorem 1.1, this gives the following.
Corollary 1.2. Suppose that the unit group is infinite. Then there is no algorithm which decides, given a system of the form (1), whether or not it has a solution in . That is, the positive-existential theory of is undecidable.
We now describe the proof of the nontrivial direction of Theorem 1.1, namely that multiplication is positive-existentially definable when is infinite. It follows the strategy of Lipshitz [10]: one first shows that the relation is positive-existentially definable, then defines multiplication on the unit group, and finally defines squaring by comparing the sizes of elements related by divisibility. However, Lipshitz measures the size of an element by its house, that is, the largest absolute value of its conjugates, , and he controls it using the fact that a nonzero algebraic integer has norm of absolute value at least 1, which is no longer true for -integers. The previous extensions to rings of -integers [3, 8] deal with this failure by explicit estimates, which remain manageable because there is only one archimedean place; moreover, they define multiplication on the unit group by an argument which requires to be finite, and this is why they are restricted to and imaginary quadratic fields. The key new development is that we deal with both difficulties in a way which does not rely on these special features: we measure size by the Weil height together with the norm away from , which turns divisibility into size estimates in a uniform way, and we define multiplication on the unit group using the uniform bound of Evertse, Schlickewei and Schmidt for unit equations. These two ingredients may be of independent interest.
The paper follows the three steps of this strategy. In § 2 we show that the relation is positive-existentially definable, and in § 3 we define multiplication on the unit group. In § 4 we develop the size estimates, and in § 5 we use them to define squaring; multiplication then follows from the identity . Finally, in § 6 we complete the proof of Theorem 1.1 and deduce Corollary 1.2.
Notation. Throughout the paper, is a number field of degree with real embeddings and pairs of complex embeddings, and is a finite set of places of containing . We write for the set of non-archimedean places of . Each corresponds to a nonzero prime ideal of , and every nonzero prime ideal arises in this way; when we also write for . We write for the normalized discrete valuation attached to a nonzero prime ideal , and
for the set of prime ideals corresponding to the non-archimedean places in . By the -unit theorem, is finitely generated of rank ; thus is infinite if and only if . We write for the language of the structure in Theorem 1.1.
All formulas are interpreted in . In particular, means that for some , and and are associated if and . A formula is positive-existential if it is built from atomic formulas using only , and . Subtraction and multiplication by fixed rational integers will be used freely in -formulas, since they can be eliminated by means of auxiliary variables and additive equations. A subset of is positive-existentially definable if it is defined in by a positive-existential -formula without parameters, and, as usual, a function is called positive-existentially definable if its graph is; thus multiplication is positive-existentially definable if the relation is. Further notation will be introduced as it is needed.
Positive-existential definability of
The goal of this section is to show that the set of nonzero elements of is positive-existentially definable (see Proposition 2.1). The idea, going back to Lipshitz [Lip78b, Lip77], is to consider a formula of the form
where is an odd prime and an integer, both to be chosen below. For this formula to define , the arithmetic progression must satisfy two requirements. On the one hand, it should contain no units, so that fails; on the other hand, for every there should exist a term of the progression such that and generate the unit ideal.
Each of these requirements is easily satisfied on its own; the point is to satisfy both at once. By the Chinese remainder theorem, the second requirement holds as soon as is not divisible by (see the proof below), so the problem is to find such a progression which contains no units. For rings of integers this can be done using norms: units have norm , while every element of the progression has norm congruent to modulo , so it suffices to choose with (mod ) (cf. [10]). In this argument breaks down, since units need not have norm . We use instead the Chebotarev density theorem to find a prime such that every unit of is a square modulo some prime of above ; choosing to be a quadratic nonresidue modulo then ensures that the progression contains no units.
We fix some notation for the proof. For a nonzero prime ideal of , let denote the valuation ring of , its residue field, and the reduction map. If , then , so is defined on .
Proposition 2.1. The set is positive-existentially -definable in the structure .
Proof. We first choose and so that the first of the two requirements above is satisfied.
Claim. There exist an odd rational prime , not below any prime in , and an integer such that for every .
Proof of the claim. Let generate the finitely generated group (see [Neu99, Ch. I, Corollary 11.7]), and let be a finite Galois extension of containing and . Applying the Chebotarev density theorem [Neu99, Ch. VII, Theorem 13.4] to the trivial conjugacy class, we find an odd rational prime that splits completely in and is not below any prime in . Fix a prime of above and a prime of above . Since splits completely in , we have . Moreover, since , each is a unit in . Since
each is a unit in . Hence is a nonzero square in for every , and therefore is a nonzero square for every .
Now choose which is not a square modulo . Since , for every we have , which is not a square in . Hence , proving the claim. □
Fix and as in the claim; it remains to check the second requirement. In , the formula is expressed by
which translates to: there exist such that
We show that it defines .
If , then fails: otherwise for some , so would be a unit, contradicting the claim.
Suppose now that . Then only finitely many maximal ideals of contain (if is a unit, and any works). For each , choose a residue class modulo such that . This is possible: if , then and , so every residue class works; otherwise, is invertible modulo , and only one residue class must be avoided. Using the Chinese remainder theorem we can find such that
for every . Then lies in no maximal ideal containing , so
Hence there exist such that
Thus holds. □
Multiplication on the unit group
We next give a positive-existential definition of multiplication on the unit group. The basic idea, which already underlies Lipshitz’s argument [10], is the following algebraic observation. If are units and , then, for every ,
so and are associated.
The difficulty lies in the converse: we need to know that if and are associated for sufficiently many values of , then . Lipshitz [10] establishes a statement of this kind over for units which are sufficiently large, using properties of the norm which fail in , and it seems that his techniques are not easily adapted to our setting. We therefore take a different route: we impose the associations above for sufficiently many translations and show that, unless , each of them gives rise to a nondegenerate solution of a unit equation. A uniform bound on the number of such solutions then gives a fixed number of translations, independent of , , , that forces .
The required uniform bound is provided by a theorem of Evertse, Schlickewei and Schmidt [6 Theorem 1.1], which we recall next.
Theorem 3.1. Let be a field of characteristic , let , let and let be a subgroup of of finite rank . Then the number of solutions of the equation
such that for every nonempty subset is at most .
Solutions as in Theorem 3.1 are called nondegenerate. The crucial feature for our application is that the bound is uniform in the coefficients: it depends only on the rank of the group, so the number of associations in the formula below can be chosen independently of , and .
Proposition 3.2. There is a positive-existential -formula such that, for all , the formula holds in if and only if are units and .
Proof. Fix a rational prime not below any prime in . Then is not a unit of for any . Recall that is the rank of . Let
and let denote the formula
Define
We show that holds if and only if are units and . Suppose first that are units and . Then, for every ,
and is a unit, so and are associated. Hence holds. Conversely, suppose that holds. Then are units. Fix . Since and are associated, there is a unit such that
Dividing by gives
Let
Notice that has rank , since the projection onto the first two coordinates gives an isomorphism onto .
By (3), for each the triple
is a solution of the equation
Applying Theorem 3.1 with and , we see that this equation has at most
nondegenerate solutions in .
The solutions
are pairwise distinct, since their second coordinates are distinct. Hence at least one of them is degenerate. Fix such an . Since all three terms in (3) are nonzero and their sum is , any vanishing proper subsum consists of exactly two terms. There are three possibilities:
If
then , which is impossible since is a unit whereas is not.
If
then , which is again impossible since is a unit.
If
then . Thus case (iii) must occur. Substituting into (3) gives
and hence . This concludes the proof of the proposition.
In particular, for every fixed integer , iterating shows that the relation “ is a unit and ” is positive-existentially definable; we shall use such conditions freely in what follows.
Size estimates from divisibility
In this section we develop the size estimates which are needed to define squaring in § 5. In , size is measured by the absolute value, and divisibility controls it: if and , then . In particular, a nonzero integer cannot be divisible by an integer of larger absolute value, and this is the kind of contradiction on which § 5 rests. Over we first need a global measure of size, which takes all places of into account: Lipshitz [10] uses the house over , and we use the Weil height .
The difficulty is to control by means of divisibility. Over , Lipshitz does so through the norm, which is monotone with respect to divisibility; in the norm no longer has this property. We use instead the norm away from , which is monotone with respect to divisibility but gives only partial information, and we recover the height from it by means of the product formula and suitable translations (see Lemma 4.6). The main result of the section is Proposition 4.7.
We begin by fixing the normalization of the absolute values of , and then define and precisely. Let denote the set of places of , so that . For a nonzero prime ideal of we write for its absolute norm. For each we fix an embedding inducing , and we set or according to whether is real or complex; thus and . We normalize the absolute values by
so that the product formula holds for every . Note that if is complex then does not satisfy the triangle inequality; in all cases, however, we have
while , with equality if . Finally, we write for the distinct rational primes lying below the primes in , and set (so that and if ). If a rational integer is coprime to , then for every .
Definition 4.1. For , the height of is
For , the norm of away from is
Thus is the (relative, multiplicative) Weil height on ; see [7 Part B]. If , then for , so only the places of contribute to :
The quantity is the index of the ideal in , although we shall not need this interpretation. Here are the basic properties of and which we shall use.
Lemma 4.2. Let .
(i) We have . In particular, .
(ii) If , then .
(iii) , , , and for .
(iv) If is a nonzero rational integer coprime to , then .
Proof. (i) By the product formula,
Since for , we have , and follows by comparing with (5) term by term.
(ii) If , then , so by (i).
(iii) By (3) and the ultrametric inequality,
for every , where, in this proof only, we put for non-archimedean. Taking the product over all places gives the first inequality. The remaining statements follow from and for real .
(iv) Since is coprime to , we have for , while for . The claim now follows from (i).
Remark 4.3. Writing in (5) and using (5), we obtain
Thus is comparable to precisely when is not small for any .
The first consequence of Lemma 4.2 is a lower bound for units satisfying a congruence. In § 5 this is what forces to be large.
Corollary 4.4. Let be a nonzero rational integer coprime to , and let with and . Then .
Proof. By Lemma 4.2, .
We now prepare the proof of Proposition 4.7. By (6), the task is to find a translate , or with a unit, which is not small at any place of . At a prime this is controlled by valuations: if , then . At an archimedean place , the number may be very small for a particular integer , but this can happen for at most one ; hence among any integers there is one for which is not small at any archimedean place. This motivates the following definition.
Definition 4.5. A set of positive integers is admissible if and every is coprime to . For such we set
Lemma 4.6. Let be admissible, and for each let be a complex number. Then there exists such that
Proof. For each , there is at most one integer such that . Since contains more elements than there are archimedean places, we may choose such that for every .
Fix such a , and write . For every we have, on the one hand,
and on the other hand the triangle inequality gives
Combining these inequalities yields the desired conclusion.
Here is the main result of the section.
Proposition 4.7. Let be admissible, and let .
(i) Suppose that for every . If and for every , then
(ii) Let , and suppose that for every . Then there exists such that and
Proof. (i) Applying Lemma 4.6 with , we obtain such that for every . Raising this to the power gives
in particular, . For we have , and hence . Taking the product over and using (5) and Lemma 4.2 (i) and (ii), we obtain
(ii) Since is a unit, for every . Applying Lemma 4.6 with and multiplying the resulting inequalities by , we obtain such that
In particular, . For we have , and hence . Using Lemma 4.2 (i) and the elementary inequality , valid for real , we get
By (5) and (6), the two products on the right are and , respectively. Since by Lemma 4.2 (i), we conclude that
Remark 4.8. The hypotheses on , , are not automatic, and they are the reason for the rescaling of by and of by in the next section.
We record for future use the following elementary analogue of the Euler–Fermat theorem.
Lemma 4.9. Let be a unit of infinite order, and let . Then there exists an integer such that is a unit of infinite order with .
Proof. Since is finite, the image of in its unit group has finite order, say . Then satisfies , and it has infinite order since does. □
Definability of the squaring function
We now come to the main step of the proof: we construct a positive-existential formula which holds in if and only if , so that it defines the graph of the squaring function. We first write down the formula, then explain the role of each of its parts, and finally prove that it has this property (Theorem 5.1).
The formula involves some auxiliary integers and constants, depending only on and , which we now fix (see also Remark 6.1). Recall from § 4 that are the rational primes below the primes in and that .
Set and for . We split these integers into three consecutive sets of elements: for , let .
Set , the largest of the , and set and .
For a multi-index we write , and we set . (If , then consists only of the empty multi-index, and .)
Let be a rational prime, coprime to , with .
Each is congruent to modulo every , and hence is coprime to . Thus each is admissible in the sense of Definition 4.5, the sets , and are pairwise disjoint, and for . They will play the role of the admissible sets of translations in Proposition 4.7.
We can now write down the formula. Let be
where is the formula of Proposition 2.1, and is the conjunction of the following four formulas:
All the index sets and constants involved are fixed; in particular, , , and are rational integers, and the conditions and can be expressed as explained at the end of § 3. Thus is a positive-existential -formula.
Let us explain the role of the various parts of . The idea is that, if , the nonzero element is forced to have a divisor which is too large. Condition gives a lower bound for the height of the unit : since and , Corollary 4.4 shows that is large, independently of and . Condition gives upper bounds for the heights of and in terms of that of , by Proposition 4.7 (i). Condition provides the powers and . Finally, since always divides , condition implies that divides , and by Proposition 4.7 (ii) and the previous bounds, this divisor is too large for some unless . With these estimates, the exponent 5 is the smallest one for which this comparison works.
Theorem 5.1. Suppose that . Then for all , the formula holds in if and only if . In particular, the graph of the squaring function is positive-existentially definable in the -structure .
Proof. First suppose that . If , then the first disjunct in (7) holds. We may therefore assume that , and hence ; thus and hold by Proposition 2.1. For each there is at most one such that and at most one such that . Since the sets , and are pairwise disjoint, there is such that none of the elements and , with , is zero. Since , there is a unit of infinite order; this is the only point in the proof where the hypothesis is used. Applying Lemma 4.9 to and to the product of and all these elements (for all ), we obtain a unit of infinite order such that and (10) holds. Since , (8) holds by Proposition 2.1. Let and , so that (9) holds by Proposition 3.2. Finally, (11) holds because
Thus all four conditions in (7) are satisfied, and hence holds.
We now prove the converse. If the first disjunct of (7) holds, there is nothing to prove, so assume that the second disjunct holds. In particular, . Fix , and such that holds. Then is a unit, , , and . We first choose the rescaling.
Claim A. There exists a multi-index such that , and for every .
Proof of Claim A. For each , choose
arbitrarily, where ranges over the primes in above and denotes the ramification index. This is possible since there are at most primes above , so at most values have to be avoided. Since and for , the multi-index is as required. □
Fix such an , and write
Claim B. We have
Proof of Claim B. Since (10) holds, there is such that and for every . By Claim A, and for every . Applying Proposition 4.7 (i) with to the nonzero element , and using Lemma 4.2 and , we obtain
and similarly for . □
Suppose, towards a contradiction, that . For every , condition (11) gives
while
Hence for every . By Claim A, we may apply Proposition 4.7 (ii) with , and , and so, using and (Lemma 4.2 (iii)), there is such that and
Combining this with Claim B, Lemma 4.2 and the divisibility , we obtain
Canceling in (13) gives
On the other hand, by , Corollary 4.4 and our choice of ,
contradicting (14). Therefore , that is, , and so . This concludes the proof.
Undecidability
We first note that Theorem 1.1 follows from Theorem 5.1. Indeed, suppose that . Since
and has characteristic 0, multiplication is positive-existentially definable from squaring. The converse direction was explained after the statement of Theorem 1.1.
Remark 6.1. The resulting formula for multiplication contains no parameters: the only constants occurring in it, and in the formulas , and on which it is built, are rational integers, which can be expressed in by means of and . It is, however, not uniform in and : the integers and of Proposition 2.1, the prime and the number of Proposition 3.2, and the prime , the sets and the multi-indices in of § 5 all depend on and .
The rest of this section is devoted to the proof of Corollary 1.2. The arguments are standard, and probably folklore; we include them for completeness, and in order to make precise that undecidability holds already for equations with integer coefficients, which is what is needed for the language .
The undecidability results quoted above concern polynomial equations whose coefficients may lie in . These constants cannot simply be named in : in general they are not even definable without parameters, since an automorphism of preserving preserves addition and divisibility (for instance, and satisfy the same parameter-free formulas in ). The following standard observation allows us to remove them.
Lemma 6.2. Let be a subring of which is finitely generated as a -algebra and has fraction field . Then for every system of polynomial equations with coefficients in one can effectively construct a system of polynomial equations with coefficients in which has a solution over if and only if the original system does.
Proof. Fix a finite presentation
and let be the images of . Replace each coefficient of the given system by a polynomial expression in with integer coefficients, replace by new variables , and add the equations for .
Clearly, if the original system has a solution, then so does the new one (take ). Conversely, a solution of the equations determines a homomorphism of -algebras with . We claim that is injective. Indeed, a nonzero element of its kernel is algebraic over , so it satisfies an equation with integer coefficients and nonzero constant term ; it follows that , which is impossible since . Therefore, extends to a field embedding , which is an automorphism of finite order, say . Since , we have , so . Applying to a solution of the new system we obtain a solution of the original one.
Theorem 6.3. There is no algorithm which decides, given a polynomial , whether has a zero in .
Proof. Koymans and Pagano [9] and, independently, Alpöge, Bhargava, Ho and Shnidman [1] proved that Hilbert’s tenth problem has a negative answer over , and Eisenträger [5 Theorem 7.9] showed that is Diophantine over ; hence Hilbert’s tenth problem over , for polynomials with coefficients in , also has a negative answer. To apply Lemma 6.2, we note that is finitely generated as a -algebra: if denotes the class number of , is a generator of for each , and , then . Lemma 6.2 now allows us to replace the coefficients by integers.
Proof of Corollary 1.2. Suppose that . By Theorem 1.1, every polynomial equation with integer coefficients can be effectively translated into a positive-existential -sentence, which in turn can be effectively written as a finite disjunction of sentences, each asserting that a system of the form (1) has a solution. An algorithm deciding the solvability of systems of the form (1) would therefore contradict Theorem 6.3.
Statement on the use of AI tools
During the preparation of this manuscript the author used Claude (Anthropic), an AI assistant, for proofreading, including checking the computations of the constants and the hypotheses of the statements, for advice on the structure of the paper, and for grammar and style, including drafting parts of the expository text. The mathematical results and the strategy of proof are due to the author, who reviewed and edited all content produced with the assistance of this tool and takes full responsibility for the content of the paper. This statement was itself drafted with the assistance of the same tool.
Carlos Martínez-Ranero
Email: [email protected]
Homepage: www2.udec.cl/ cmartinezr
Address:
Universidad de Concepción, Concepción, Chile
Facultad de Ciencias Físicas y Matemáticas
Departamento de Matemática
References
- [1][ABHS26] L. Alpöge, M. Bhargava, W. Ho and A. Shnidman, Rank stability in quadratic extensions and Hilbert’s tenth problem for the ring of integers of a number field. Invent. Math. 243(2026), 1129–1139.
- [2][Bel76] A. P. Bel’tuykov, Decidability of the universal theory of natural numbers with addition and divisibility (Russian). Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 60(1976), 15–28, 221.
- [3][CM17] L. Cerda-Romero and C. Martínez-Ranero, The Diophantine problem for addition and divisibility over subrings of the rationals. J. Symb. Log. 82(2017), 1140–1149.
- [4][DPR61] M. Davis, H. Putnam and J. Robinson, The decision problem for exponential Diophantine equations. Ann. of Math. (2) 74(1961), 425–436.DOI
- [5][Eis03] K. Eisenträger, Hilbert’s tenth problem and arithmetic geometry. PhD thesis, University of California, Berkeley, 2003.
- [6][ESS02] J.-H. Evertse, H. P. Schlickewei and W. M. Schmidt, Linear equations in variables which lie in a multiplicative group. Ann. of Math. (2) 155(2002), 807–836.DOI
- [7][HS00] M. Hindry and J. H. Silverman, Diophantine geometry. An introduction. Graduate Texts in Mathematics, 201, Springer, New York, 2000.DOI
- [8][HM25] N. Hormazábal and C. Martínez-Ranero, The Diophantine problem for addition and divisibility for rings of S-integers of quadratic imaginary extensions of Q. Preprint, 2025, arXiv:2510.1758.
- [9][KP27] P. Koymans and C. Pagano, Hilbert’s tenth problem via additive combinatorics. J. Amer. Math. Soc. 40(2027), 195–234.arxiv.org/abs/2412.01768
- [10][Lip77] L. Lipshitz, Undecidable existential problems for addition and divisibility in algebraic number rings. II. Proc. Amer. Math. Soc. 64(1977), 122–128.DOI
- [11][Lip78a] L. Lipshitz, The Diophantine problem for addition and divisibility. Trans. Amer. Math. Soc. 235(1978), 271–283.DOI