betaFeedback

WorksMathematics

Diophantine definability from addition and divisibility over rings of SS-integers

Abstract

Let KK be a number field, let SS be a finite set of places of KK containing the archimedean places, and let OK,S\mathcal{O}_{K,S} denote the ring of SS-integers of KK. We prove that multiplication is positive-existentially definable in (OK,S,0,1,+,∣)(\mathcal{O}_{K,S},0,1,+,\mid) if and only if the unit group OK,S×\mathcal{O}_{K,S}^\times is infinite. This extends a 1977 theorem of Lipshitz for rings of integers to rings of SS-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 Z\mathbb{Z}. More precisely, there is an algorithm which decides, given a system

f1(x)=0, …, fa(x)=0,g1(x)∣h1(x), …, gb(x)∣hb(x)(1)f_1(\mathbf{x}) = 0,\ \ldots,\ f_a(\mathbf{x}) = 0,\qquad g_1(\mathbf{x}) \mid h_1(\mathbf{x}),\ \ldots,\ g_b(\mathbf{x}) \mid h_b(\mathbf{x}) \tag*{(1)}

in the unknowns x=(x1,…,xn)\mathbf{x} = (x_1,\ldots,x_n), where the fif_i, gjg_j and hjh_j are linear polynomials with integer coefficients, whether it has a solution in Z\mathbb{Z}. 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 (Z,0,1,+,∣)(\mathbb{Z},0,1,+,\mid) is decidable. In a series of papers, Lipshitz also studied the problem over the ring of integers OK\mathcal{O}_K of a number field KK. He showed that it is decidable when KK is an imaginary quadratic field [11] and undecidable when KK is real quadratic [Lip78b], and that for every number field KK other than Q\mathbb{Q} or an imaginary quadratic field, multiplication is positive-existentially definable in (OK,0,1,+,∣)(\mathcal{O}_K,0,1,+,\mid) [10]. The latter result shows that the problem over OK\mathcal{O}_K is as hard as Hilbert’s tenth problem over OK\mathcal{O}_K, 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 OK×\mathcal{O}_K^\times is finite, and it is natural to ask what happens for rings of SS-integers.

So far, this question has been answered for Q\mathbb{Q} and imaginary quadratic fields: Cerda-Romero and the author [3] showed that the problem is undecidable for Z[1/m]\mathbb{Z}[1/m] for every integer m≥2m \ge2, and Hormazábal and the author [8] extended this to rings of SS-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 SS-integers of number fields. Let KK be a number field, and let SS be a finite set of places of KK containing the set MK∞M_K^\infty of archimedean places. The ring of SS-integers of KK is

OK,S:={x∈K:∣x∣v≤1 for all v∉S}.\mathcal{O}_{K,S}:=\{x\in K: |x|_v\le1\text{ for all }v\notin S\}.

Our main result is the following.

Theorem 1.1. Multiplication is positive-existentially definable in the structure (OK,S,0,1,+,∣)(\mathcal{O}_{K,S},0,1,+,\mid) if and only if the unit group OK,S×\mathcal{O}_{K,S}^\times is infinite.

By the SS-unit theorem, OK,S×\mathcal{O}_{K,S}^\times is infinite unless S=MK∞S=M_K^\infty and KK is Q\mathbb{Q} or imaginary quadratic. Thus multiplication is positive-existentially definable whenever S≠MK∞S\ne M_K^\infty, and when S=MK∞S=M_K^\infty Theorem 1.1 recovers the theorem of Lipshitz [10] by a different method. The converse direction is immediate: if OK,S×\mathcal{O}_{K,S}^\times is finite, then the positive-existential theory of (OK,S,0,1,+,∣)(\mathcal{O}_{K,S},0,1,+,\mid) is decidable [11, 2], whereas Hilbert’s tenth problem over OK,S=OK\mathcal{O}_{K,S}=\mathcal{O}_K 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 OK,S\mathcal{O}_{K,S} 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 OK,S×\mathcal{O}_{K,S}^\times is infinite. Then there is no algorithm which decides, given a system of the form (1), whether or not it has a solution in OK,S\mathcal{O}_{K,S}. That is, the positive-existential theory of (OK,S,0,1,+,∣)(\mathcal{O}_{K,S},0,1,+,\mid) is undecidable.

We now describe the proof of the nontrivial direction of Theorem 1.1, namely that multiplication is positive-existentially definable when OK,S×\mathcal{O}_{K,S}^{\times} is infinite. It follows the strategy of Lipshitz [10]: one first shows that the relation x≠0x \ne0 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 a∈OKa \in\mathcal{O}_K by its house, that is, the largest absolute value of its conjugates, max⁡v∣σv(a)∣\max_v \lvert\sigma_v(a)\rvert, 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 SS-integers. The previous extensions to rings of SS-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 OK×\mathcal{O}_K^\times to be finite, and this is why they are restricted to Q\mathbb{Q} 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 SS, 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 x≠0x \ne0 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 (x+y)2=x2+2xy+y2(x+y)^2=x^2+2xy+y^2. Finally, in § 6 we complete the proof of Theorem 1.1 and deduce Corollary 1.2.

Notation. Throughout the paper, KK is a number field of degree dd with r1r_1 real embeddings and r2r_2 pairs of complex embeddings, and SS is a finite set of places of KK containing MK∞M_K^\infty. We write MK0M_K^0 for the set of non-archimedean places of KK. Each v∈MK0v \in M_K^0 corresponds to a nonzero prime ideal pv\mathfrak{p}_v of OK\mathcal{O}_K, and every nonzero prime ideal arises in this way; when p=pv\mathfrak{p}=\mathfrak{p}_v we also write ∣⋅∣p\lvert\cdot\rvert_{\mathfrak{p}} for ∣⋅∣v\lvert\cdot\rvert_v. We write vpv_{\mathfrak{p}} for the normalized discrete valuation attached to a nonzero prime ideal p\mathfrak{p}, and

PS:={pv:v∈S∩MK0}\mathcal{P}_S := \{\mathfrak{p}_v : v \in S \cap M_K^0\}

for the set of prime ideals corresponding to the non-archimedean places in SS. By the SS-unit theorem, OK,S×\mathcal{O}_{K,S}^{\times} is finitely generated of rank r:=#S−1r := \#S-1; thus OK,S×\mathcal{O}_{K,S}^{\times} is infinite if and only if r≥1r \ge1. We write Ldiv={=,0,1,+,∣}\mathcal{L}_{\mathrm{div}}=\{=,0,1,+,\mid\} for the language of the structure in Theorem 1.1.

All formulas are interpreted in OK,S\mathcal{O}_{K,S}. In particular, a∣ba\mid b means that b=acb=ac for some c∈OK,Sc\in\mathcal{O}_{K,S}, and aa and bb are associated if a∣ba\mid b and b∣ab\mid a. A formula is positive-existential if it is built from atomic formulas using only ∨\lor, ∧\land and ∃\exists. Subtraction and multiplication by fixed rational integers will be used freely in Ldiv\mathcal{L}_{\mathrm{div}}-formulas, since they can be eliminated by means of auxiliary variables and additive equations. A subset of OK,S\mathcal{O}_{K,S} is positive-existentially definable if it is defined in OK,S\mathcal{O}_{K,S} by a positive-existential Ldiv\mathcal{L}_{\mathrm{div}}-formula without parameters, and, as usual, a function OK,Sn→OK,S\mathcal{O}_{K,S}^n \to\mathcal{O}_{K,S} is called positive-existentially definable if its graph is; thus multiplication is positive-existentially definable if the relation z=xyz = xy is. Further notation will be introduced as it is needed.

Positive-existential definability of OK,S∖{0}\mathcal{O}_{K,S} \setminus\{0\}

The goal of this section is to show that the set of nonzero elements of OK,S\mathcal{O}_{K,S} is positive-existentially definable (see Proposition 2.1). The idea, going back to Lipshitz [Lip78b, Lip77], is to consider a formula of the form

ψ≠(x):=∃λ,μ,t  (λx+μ(pt+b)=1),\psi_{\neq}(x) := \exists\lambda,\mu,t\;(\lambda x + \mu(pt+b) = 1),

where pp is an odd prime and bb an integer, both to be chosen below. For this formula to define x≠0x \ne0, the arithmetic progression pt+bpt+b must satisfy two requirements. On the one hand, it should contain no units, so that ψ≠(0)\psi_{\neq}(0) fails; on the other hand, for every x≠0x \ne0 there should exist a term pt+bpt+b of the progression such that xx and pt+bpt+b 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 bb is not divisible by pp (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 ±1\pm1, while every element of the progression has norm congruent to bdb^d modulo pp, so it suffices to choose bb with bd≢±1b^d \not\equiv\pm1 (mod pp) (cf. [10]). In OK,S\mathcal{O}_{K,S} this argument breaks down, since units need not have norm ±1\pm1. We use instead the Chebotarev density theorem to find a prime pp such that every unit of OK,S\mathcal{O}_{K,S} is a square modulo some prime of KK above pp; choosing bb to be a quadratic nonresidue modulo pp then ensures that the progression contains no units.

We fix some notation for the proof. For a nonzero prime ideal p\mathfrak{p} of OK\mathcal{O}_K, let Ovp\mathcal{O}_{v_{\mathfrak{p}}} denote the valuation ring of vpv_{\mathfrak{p}}, Fp\mathbb{F}_{\mathfrak{p}} its residue field, and red⁡p:Ovp→Fp\operatorname{red}_{\mathfrak{p}}:\mathcal{O}_{v_{\mathfrak{p}}}\to\mathbb{F}_{\mathfrak{p}} the reduction map. If p∉PS\mathfrak{p}\notin\mathcal{P}_S, then OK,S⊆Ovp\mathcal{O}_{K,S}\subseteq\mathcal{O}_{v_{\mathfrak{p}}}, so red⁡p\operatorname{red}_{\mathfrak{p}} is defined on OK,S\mathcal{O}_{K,S}.

Proposition 2.1. The set OK,S∖{0}\mathcal{O}_{K,S}\setminus\{0\} is positive-existentially Ldiv\mathcal{L}_{\mathrm{div}}-definable in the structure OK,S\mathcal{O}_{K,S}.

Proof. We first choose pp and bb so that the first of the two requirements above is satisfied.

Claim. There exist an odd rational prime pp, not below any prime in PS\mathcal{P}_S, and an integer 0<b<p0<b<p such that pt+b∉OK,S×pt+b\notin\mathcal{O}_{K,S}^{\times} for every t∈OK,St\in\mathcal{O}_{K,S}.

Proof of the claim. Let ε1,…,εg\varepsilon_1,\ldots,\varepsilon_g generate the finitely generated group OK,S×\mathcal{O}_{K,S}^{\times} (see [Neu99, Ch. I, Corollary 11.7]), and let LL be a finite Galois extension of Q\mathbb{Q} containing KK and ε1,…,εg\sqrt{\varepsilon_1},\ldots,\sqrt{\varepsilon_g}. Applying the Chebotarev density theorem [Neu99, Ch. VII, Theorem 13.4] to the trivial conjugacy class, we find an odd rational prime pp that splits completely in LL and is not below any prime in PS\mathcal{P}_S. Fix a prime p\mathfrak{p} of KK above pp and a prime P\mathfrak{P} of LL above p\mathfrak{p}. Since pp splits completely in LL, we have Fp=Fp=Fp\mathbb{F}_{\mathfrak{p}}=\mathbb{F}_p=\mathbb{F}_p. Moreover, since p∉PSp\notin\mathcal{P}_S, each εi\varepsilon_i is a unit in Ovp\mathcal{O}_{v_{\mathfrak{p}}}. Since

vp(εi)=12vp(εi)=0,v_{\mathfrak{p}}\left(\sqrt{\varepsilon_i}\right)=\frac{1}{2}v_{\mathfrak{p}}(\varepsilon_i)=0,

each εi\sqrt{\varepsilon_i} is a unit in Ovp\mathcal{O}_{v_{\mathfrak{p}}}. Hence red⁡p(εi)=red⁡p(εi)2\operatorname{red}_{p}(\varepsilon_i)=\operatorname{red}_{\mathfrak{p}}\left(\sqrt{\varepsilon_i}\right)^2 is a nonzero square in Fp\mathbb{F}_p for every ii, and therefore red⁡p(ε)\operatorname{red}_{p}(\varepsilon) is a nonzero square for every ε∈OK,S×\varepsilon\in\mathcal{O}_{K,S}^{\times}.

Now choose 0<b<p0<b<p which is not a square modulo pp. Since p∈Ppp\in\mathcal{P}_p, for every t∈OK,St\in\mathcal{O}_{K,S} we have red⁡p(pt+b)=b\operatorname{red}_{p}(pt+b)=b, which is not a square in Fp\mathbb{F}_p. Hence pt+b∉OK,S×pt+b\notin\mathcal{O}_{K,S}^{\times}, proving the claim. □

Fix pp and bb as in the claim; it remains to check the second requirement. In Ldiv\mathcal{L}_{\mathrm{div}}, the formula ψ≠(x)\psi_{\ne}(x) is expressed by

∃A,B,t(x∣A∧pt+b∣B∧A+B=1),\exists A,B,t\left(x\mid A\land pt+b\mid B\land A+B=1\right),

which translates to: there exist λ,μ,t∈OK,S\lambda,\mu,t\in\mathcal{O}_{K,S} such that

λx+μ(pt+b)=1.\lambda x+\mu(pt+b)=1.

We show that it defines OK,S∖{0}\mathcal{O}_{K,S}\setminus\{0\}.

If x=0x=0, then ψ≠(x)\psi_{\ne}(x) fails: otherwise μ(pt+b)=1\mu(pt+b)=1 for some μ,t∈OK,S\mu,t\in\mathcal{O}_{K,S}, so pt+bpt+b would be a unit, contradicting the claim.

Suppose now that x≠0x\ne0. Then only finitely many maximal ideals q1,…,qn\mathfrak{q}_1,\ldots,\mathfrak{q}_n of OK,S\mathcal{O}_{K,S} contain xx (if xx is a unit, n=0n=0 and any tt works). For each ii, choose a residue class tit_i modulo qi\mathfrak{q}_i such that pti+b∉qipt_i+b\notin\mathfrak{q}_i. This is possible: if p∈qip\in\mathfrak{q}_i, then qi∩Z=pZ\mathfrak{q}_i\cap\mathbb{Z}=p\mathbb{Z} and 0<b<p0<b<p, so every residue class works; otherwise, pp is invertible modulo qi\mathfrak{q}_i, and only one residue class must be avoided. Using the Chinese remainder theorem we can find t∈OK,St\in\mathcal{O}_{K,S} such that

t≡ti(modqi)t\equiv t_i\pmod{\mathfrak{q}_i}

for every ii. Then pt+bpt+b lies in no maximal ideal containing xx, so

xOK,S+(pt+b)OK,S=OK,S.x\mathcal{O}_{K,S}+(pt+b)\mathcal{O}_{K,S}=\mathcal{O}_{K,S}.

Hence there exist λ,μ∈OK,S\lambda,\mu\in\mathcal{O}_{K,S} such that

λx+μ(pt+b)=1.\lambda x+\mu(pt+b)=1.

Thus ψ≠(x)\psi_{\ne}(x) 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 x,y,zx,y,z are units and z=xyz=xy, then, for every tt,

z+ty=y(x+t),z+ty=y(x+t),

so x+tx+t and z+tyz+ty are associated.

The difficulty lies in the converse: we need to know that if x+tx+t and z+tyz+ty are associated for sufficiently many values of tt, then z=xyz=xy. Lipshitz [10] establishes a statement of this kind over OKO_K for units which are sufficiently large, using properties of the norm which fail in OK,SO_{K,S}, 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 z=xyz=xy, 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 xx, yy, zz, that forces z=xyz=xy.

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 FF be a field of characteristic 00, let n≥1n \ge1, let a1,…,an∈F×a_1,\ldots,a_n \in F^\times and let Γ\Gamma be a subgroup of (F×)n(F^\times)^n of finite rank ρ\rho. Then the number of solutions (u1,…,un)∈Γ(u_1,\ldots,u_n) \in\Gamma of the equation

a1u1+⋯+anun=1a_1u_1+\cdots+a_nu_n=1

such that ∑i∈Iaiui≠0\sum_{i\in I}a_i u_i \ne0 for every nonempty subset I⊆{1,…,n}I \subseteq\{1,\ldots,n\} is at most exp⁡((6n)3n(ρ+1))\exp((6n)^{3n}(\rho+1)).

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 NN of associations in the formula below can be chosen independently of xx, yy and zz.

Proposition 3.2. There is a positive-existential LdivL_{\mathrm{div}}-formula Prod⁡u(x,y,z)\operatorname{Prod}_u(x,y,z) such that, for all x,y,z∈OK,Sx,y,z \in O_{K,S}, the formula Prod⁡u(x,y,z)\operatorname{Prod}_u(x,y,z) holds in OK,SO_{K,S} if and only if x,y,zx,y,z are units and z=xyz=xy.

Proof. Fix a rational prime ℓ\ell not below any prime in PS\mathcal{P}_S. Then ℓi\ell^i is not a unit of OK,SO_{K,S} for any i≥1i \ge1. Recall that rr is the rank of OK,S×O_{K,S}^{\times}. Let

N:=3189(r+2),N := 3^{18^9(r+2)},

and let assoc⁡(a,b)\operatorname{assoc}(a,b) denote the formula

a∣b∧b∣a.a \mid b \land b \mid a.

Define

Prod⁡u(x,y,z):x∣1∧y∣1∧z∣1∧⋀i=1Nassoc⁡(x+ℓi,z+ℓiy).\operatorname{Prod}_u(x,y,z):\quad x \mid1 \land y \mid1 \land z \mid1 \land\bigwedge_{i=1}^{N}\operatorname{assoc}(x+\ell^i,z+\ell^i y).

We show that Prod⁡u(x,y,z)\operatorname{Prod}_u(x,y,z) holds if and only if x,y,zx,y,z are units and z=xyz=xy. Suppose first that x,y,zx,y,z are units and z=xyz=xy. Then, for every 1≤i≤N1 \le i \le N,

z+ℓiy=y(x+ℓi),(2)z+\ell^i y=y(x+\ell^i), \tag*{(2)}

and yy is a unit, so x+ℓix+\ell^i and z+ℓiyz+\ell^iy are associated. Hence Prod⁡u(x,y,z)\operatorname{Prod}_{\mathrm{u}}(x,y,z) holds. Conversely, suppose that Prod⁡u(x,y,z)\operatorname{Prod}_{\mathrm{u}}(x,y,z) holds. Then x,y,zx,y,z are units. Fix 1≤i≤N1\le i\le N. Since x+ℓix+\ell^i and z+ℓiyz+\ell^iy are associated, there is a unit εi\varepsilon_i such that

x+ℓi−εiz−εiℓiy=0.x+\ell^i-\varepsilon_i z-\varepsilon_i\ell^iy=0.

Dividing by xx gives

zxεi−1xℓi+yxεiℓi=1.(3)\frac{z}{x}\varepsilon_i-\frac{1}{x}\ell^i+\frac{y}{x}\varepsilon_i\ell^i=1. \tag*{(3)}

Let

Γ={(ε,t,εt):ε∈OK,S×, t∈⟨ℓ⟩}⊆(K×)3.\Gamma=\{(\varepsilon,t,\varepsilon t):\varepsilon\in\mathcal{O}_{K,S}^{\times},\ t\in\langle\ell\rangle\}\subseteq(K^\times)^3.

Notice that Γ\Gamma has rank r+1r+1, since the projection onto the first two coordinates gives an isomorphism onto OK,S××⟨ℓ⟩\mathcal{O}_{K,S}^{\times}\times\langle\ell\rangle.

By (3), for each 1≤i≤N1\le i\le N the triple

(εi,ℓi,εiℓi)∈Γ(\varepsilon_i,\ell^i,\varepsilon_i\ell^i)\in\Gamma

is a solution of the equation

a1u1+a2u2+a3u3=1,wherea1=zx,a2=−1x,a3=yx.a_1u_1+a_2u_2+a_3u_3=1,\qquad\text{where}\quad a_1=\frac{z}{x},\quad a_2=-\frac{1}{x},\quad a_3=\frac{y}{x}.

Applying Theorem 3.1 with n=3n=3 and ρ=r+1\rho=r+1, we see that this equation has at most

exp⁡(189(r+2))<N\exp(18^9(r+2))<N

nondegenerate solutions in Γ\Gamma.

The NN solutions

(εi,ℓi,εiℓi),1≤i≤N,(\varepsilon_i,\ell^i,\varepsilon_i\ell^i),\qquad1\le i\le N,

are pairwise distinct, since their second coordinates are distinct. Hence at least one of them is degenerate. Fix such an ii. Since all three terms in (3) are nonzero and their sum is 11, any vanishing proper subsum consists of exactly two terms. There are three possibilities:

  1. If

zxεi−1xℓi=0,\frac{z}{x}\varepsilon_i-\frac{1}{x}\ell^i=0,

then ℓi=εiz\ell^i=\varepsilon_i z, which is impossible since εiz\varepsilon_i z is a unit whereas ℓi\ell^i is not.

  1. If

zxεi+yxεiℓi=0,\frac{z}{x}\varepsilon_i+\frac{y}{x}\varepsilon_i\ell^i=0,

then ℓi=−z/y\ell^i=-z/y, which is again impossible since −z/y-z/y is a unit.

  1. If

−1xℓi+yxεiℓi=0,-\frac{1}{x}\ell^i+\frac{y}{x}\varepsilon_i\ell^i=0,

then εi=y−1\varepsilon_i=y^{-1}. Thus case (iii) must occur. Substituting εi=y−1\varepsilon_i=y^{-1} into (3) gives

zxy=1,\frac{z}{xy}=1,

and hence z=xyz=xy. This concludes the proof of the proposition.

In particular, for every fixed integer n≥1n \ge1, iterating Prod⁡u\operatorname{Prod}_u shows that the relation “ε\varepsilon is a unit and η=εn\eta=\varepsilon^n” 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 Z\mathbb{Z}, size is measured by the absolute value, and divisibility controls it: if a∣ba \mid b and b≠0b \ne0, then ∣a∣≤∣b∣|a| \le|b|. 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 OK,S\mathcal{O}_{K,S} we first need a global measure of size, which takes all places of KK into account: Lipshitz [10] uses the house over OK\mathcal{O}_K, and we use the Weil height HKH_K.

The difficulty is to control HKH_K by means of divisibility. Over OK\mathcal{O}_K, Lipshitz does so through the norm, which is monotone with respect to divisibility; in OK,S\mathcal{O}_{K,S} the norm no longer has this property. We use instead the norm NSN_S away from SS, 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 KK, and then define HKH_K and NSN_S precisely. Let MKM_K denote the set of places of KK, so that MK=MK∞∪MK0M_K=M_K^\infty\cup M_K^0. For a nonzero prime ideal p\mathfrak{p} of OK\mathcal{O}_K we write Np:=#(OK/p)N\mathfrak{p}:=\#(\mathcal{O}_K/\mathfrak{p}) for its absolute norm. For each v∈MK∞v\in M_K^\infty we fix an embedding σv:K→C\sigma_v:K\to\mathbb{C} inducing vv, and we set dv=1d_v=1 or 22 according to whether vv is real or complex; thus #MK∞=r1+r2\#M_K^\infty=r_1+r_2 and ∑v∈MK∞dv=d\sum_{v\in M_K^\infty}d_v=d. We normalize the absolute values by

∣a∣p=Np−vp(a)(p≠0 prime),∣a∣v=∣σv(a)∣dv(v∈MK∞),|a|_{\mathfrak{p}}=N\mathfrak{p}^{-v_{\mathfrak{p}}(a)} \quad(\mathfrak{p}\ne0\text{ prime}),\qquad |a|_v=|\sigma_v(a)|^{d_v} \quad(v\in M_K^\infty),

so that the product formula ∏v∈MK∣a∣v=1\prod_{v\in M_K}|a|_v=1 holds for every a∈K×a\in K^\times. Note that if vv is complex then ∣⋅∣v|\cdot|_v does not satisfy the triangle inequality; in all cases, however, we have

∣a+b∣v≤2dvmax⁡{∣a∣v,∣b∣v}(v∈MK∞),(4)|a+b|_v\le2^{d_v}\max\{|a|_v,|b|_v\} \qquad(v\in M_K^\infty), \tag*{(4)}

while ∣a+b∣p≤max⁡{∣a∣p,∣b∣p}|a+b|_{\mathfrak{p}}\le\max\{|a|_{\mathfrak{p}},|b|_{\mathfrak{p}}\}, with equality if ∣a∣p≠∣b∣p|a|_{\mathfrak{p}}\ne|b|_{\mathfrak{p}}. Finally, we write p1,…,pkp_1,\ldots,p_k for the distinct rational primes lying below the primes in PSP_S, and set P:=p1⋯pkP:=p_1\cdots p_k (so that k=0k=0 and P=1P=1 if S=MK∞S=M_K^\infty). If a rational integer nn is coprime to PP, then vp(n)=0v_{\mathfrak{p}}(n)=0 for every p∈PS\mathfrak{p}\in P_S.

Definition 4.1. For a∈Ka \in K, the height of aa is

HK(a):=∏v∈MKmax⁡{1,∣a∣v}.H_K(a) := \prod_{v \in M_K} \max\{1, |a|_v\}.

For a∈OK,S∖{0}a \in\mathcal{O}_{K,S} \setminus\{0\}, the norm of aa away from SS is

NS(a):=∏p∉PSN(p)vp(a).N_S(a) := \prod_{\mathfrak{p} \notin P_S} \mathop{\mathrm{N}}(\mathfrak{p})^{v_{\mathfrak{p}}(a)}.

Thus HKH_K is the (relative, multiplicative) Weil height on KK; see [7 Part B]. If a∈OK,Sa \in\mathcal{O}_{K,S}, then ∣a∣v≤1|a|_v \leq1 for v∉Sv \notin S, so only the places of SS contribute to HK(a)H_K(a):

HK(a)=∏v∈Smax⁡{1,∣a∣v}(a∈OK,S).(5)H_K(a) = \prod_{v \in S} \max\{1, |a|_v\} \qquad(a \in\mathcal{O}_{K,S}). \tag*{(5)}

The quantity NS(a)N_S(a) is the index of the ideal aOK,Sa\mathcal{O}_{K,S} in OK,S\mathcal{O}_{K,S}, although we shall not need this interpretation. Here are the basic properties of HKH_K and NSN_S which we shall use.

Lemma 4.2. Let a,b∈OK,S∖{0}a,b \in\mathcal{O}_{K,S} \setminus\{0\}.

(i) We have NS(a)=∏v∈S∣a∣vN_S(a) = \prod_{v \in S} |a|_v. In particular, 1≤NS(a)≤HK(a)1 \leq N_S(a) \leq H_K(a).

(ii) If a∣ba \mid b, then NS(a)≤NS(b)N_S(a) \leq N_S(b).

(iii) HK(a+b)≤2dHK(a)HK(b)H_K(a+b) \leq2^d H_K(a)H_K(b), HK(ab)≤HK(a)HK(b)H_K(ab) \leq H_K(a)H_K(b), HK(−a)=HK(a)H_K(-a) = H_K(a), and HK(an)=HK(a)nH_K(a^n) = H_K(a)^n for n≥1n \geq1.

(iv) If nn is a nonzero rational integer coprime to PP, then NS(n)=∣n∣dN_S(n) = |n|^d.

Proof. (i) By the product formula,

∏v∈S∣a∣v=∏p∉PS∣a∣p−1=∏p∉PSN(p)vp(a)=NS(a).\prod_{v \in S} |a|_v = \prod_{\mathfrak{p} \notin P_S} |a|_{\mathfrak{p}}^{-1} = \prod_{\mathfrak{p} \notin P_S} \mathop{\mathrm{N}}(\mathfrak{p})^{v_{\mathfrak{p}}(a)} = N_S(a).

Since vp(a)≥0v_{\mathfrak{p}}(a) \geq0 for p∉PS\mathfrak{p} \notin P_S, we have NS(a)≥1N_S(a) \geq1, and NS(a)≤HK(a)N_S(a) \leq H_K(a) follows by comparing with (5) term by term.

(ii) If b=acb = ac, then c∈OK,S∖{0}c \in\mathcal{O}_{K,S} \setminus\{0\}, so NS(b)=NS(a)NS(c)≥NS(a)N_S(b) = N_S(a)N_S(c) \geq N_S(a) by (i).

(iii) By (3) and the ultrametric inequality,

max⁡{1,∣a+b∣v}≤2dvmax⁡{1,∣a∣v}max⁡{1,∣b∣v}\max\{1, |a+b|_v\} \leq2^{d_v}\max\{1, |a|_v\}\max\{1, |b|_v\}

for every v∈MKv \in M_K, where, in this proof only, we put dv=0d_v = 0 for vv non-archimedean. Taking the product over all places gives the first inequality. The remaining statements follow from max⁡{1,st}≤max⁡{1,s}max⁡{1,t}\max\{1,st\} \leq\max\{1,s\}\max\{1,t\} and max⁡{1,sn}=max⁡{1,s}n\max\{1,s^n\} = \max\{1,s\}^n for real s,t≥0s,t \geq0.

(iv) Since nn is coprime to PP, we have ∣n∣p=1|n|_{\mathfrak{p}} = 1 for p∈PS\mathfrak{p} \in P_S, while ∣n∣v=∣n∣dv|n|_v = |n|^{d_v} for v∈MK∞v \in M_K^\infty. The claim now follows from (i).

Remark 4.3. Writing ∣a∣v=max⁡{1,∣a∣v}min⁡{1,∣a∣v}|a|_v=\max\{1,|a|_v\}\min\{1,|a|_v\} in (5) and using (5), we obtain

NS(a)=HK(a)∏v∈Smin⁡{1,∣a∣v}(a∈OK,S∖{0}).(6)N_S(a)=H_K(a)\prod_{v\in S}\min\{1,|a|_v\}\qquad(a\in\mathcal{O}_{K,S}\setminus\{0\}). \tag*{(6)}

Thus NS(a)N_S(a) is comparable to HK(a)H_K(a) precisely when ∣a∣v|a|_v is not small for any v∈Sv\in S.

The first consequence of Lemma 4.2 is a lower bound for units satisfying a congruence. In § 5 this is what forces ε\varepsilon to be large.

Corollary 4.4. Let nn be a nonzero rational integer coprime to PP, and let ε∈OK,S×\varepsilon\in\mathcal{O}_{K,S}^{\times} with ε≠1\varepsilon\ne1 and n∣ε−1n\mid\varepsilon-1. Then HK(ε)≥(∣n∣/2)dH_K(\varepsilon)\geq(|n|/2)^d.

Proof. By Lemma 4.2, ∣n∣d=NS(n)≤NS(ε−1)≤HK(ε−1)≤2dHK(ε)|n|^d=N_S(n)\leq N_S(\varepsilon-1)\leq H_K(\varepsilon-1)\leq2^dH_K(\varepsilon). □\square

We now prepare the proof of Proposition 4.7. By (6), the task is to find a translate a+ja+j, or a+jηa+j\eta with η\eta a unit, which is not small at any place of SS. At a prime p∈PS\mathfrak{p}\in P_S this is controlled by valuations: if vp(a)≠vp(b)v_{\mathfrak{p}}(a)\ne v_{\mathfrak{p}}(b), then ∣a+b∣p=max⁡{∣a∣p,∣b∣p}|a+b|_{\mathfrak{p}}=\max\{|a|_{\mathfrak{p}},|b|_{\mathfrak{p}}\}. At an archimedean place vv, the number σv(a)+j\sigma_v(a)+j may be very small for a particular integer jj, but this can happen for at most one jj; hence among any r1+r2+1r_1+r_2+1 integers there is one for which σv(a)+j\sigma_v(a)+j is not small at any archimedean place. This motivates the following definition.

Definition 4.5. A set JJ of positive integers is admissible if #J=r1+r2+1\#J=r_1+r_2+1 and every j∈Jj\in J is coprime to PP. For such JJ we set

cJ:=(2max⁡J+1)−1.c_J:=(2\max J+1)^{-1}.

Lemma 4.6. Let JJ be admissible, and for each v∈MK∞v\in M_K^\infty let zvz_v be a complex number. Then there exists j∈Jj\in J such that

∣zv+j∣≥cJmax⁡{1,∣zv∣}for every v∈MK∞.|z_v+j|\geq c_J\max\{1,|z_v|\}\qquad\text{for every }v\in M_K^\infty.

Proof. For each v∈MK∞v\in M_K^\infty, there is at most one integer ii such that ∣zv+i∣<12|z_v+i|<\frac{1}{2}. Since JJ contains more elements than there are archimedean places, we may choose j∈Jj\in J such that ∣zv+j∣≥12|z_v+j|\geq\frac{1}{2} for every v∈MK∞v\in M_K^\infty.

Fix such a jj, and write j∗:=max⁡Jj^*:=\max J. For every v∈MK∞v\in M_K^\infty we have, on the one hand,

1≤2∣zv+j∣≤(2j∗+1)∣zv+j∣,1\leq2|z_v+j|\leq(2j^*+1)|z_v+j|,

and on the other hand the triangle inequality gives

∣zv∣≤∣zv+j∣+j≤∣zv+j∣+2j∗∣zv+j∣=(2j∗+1)∣zv+j∣.|z_v|\leq|z_v+j|+j\leq|z_v+j|+2j^*|z_v+j|=(2j^*+1)|z_v+j|.

Combining these inequalities yields the desired conclusion. □\square

Here is the main result of the section.

Proposition 4.7. Let JJ be admissible, and let a∈OK,S∖{0}a\in\mathcal{O}_{K,S}\setminus\{0\}.

(i) Suppose that vp(a)≠0v_{\mathfrak p}(a) \ne0 for every p∈PS\mathfrak p \in\mathcal{P}_S. If b∈OK,S∖{0}b \in\mathcal{O}_{K,S} \setminus\{0\} and a+j∣ba+j \mid b for every j∈Jj \in J, then

HK(a)≤cJ−dNS(b).H_K(a) \le c_J^{-d}N_S(b).

(ii) Let η∈OK,S×\eta\in\mathcal{O}_{K,S}^{\times}, and suppose that vp(a)≠vp(η)v_{\mathfrak p}(a) \ne v_{\mathfrak p}(\eta) for every p∈PS\mathfrak p \in\mathcal{P}_S. Then there exists j∈Jj \in J such that a+jη≠0a+j\eta\ne0 and

NS(a+jη)≥cJdHK(η)HK(a).N_S(a+j\eta) \ge c_J^d\frac{H_K(\eta)}{H_K(a)}.

Proof. (i) Applying Lemma 4.6 with zv=σv(a)z_v=\sigma_v(a), we obtain j∈Jj \in J such that ∣σv(a)+j∣≥cJmax⁡{1,∣σv(a)∣}|\sigma_v(a)+j| \ge c_J\max\{1,|\sigma_v(a)|\} for every v∈MK∞v \in M_K^\infty. Raising this to the power dvd_v gives

∣a+j∣v≥cJdvmax⁡{1,∣a∣v}(v∈MK∞);|a+j|_v \ge c_J^{d_v}\max\{1,|a|_v\}\qquad(v \in M_K^\infty);

in particular, a+j≠0a+j \ne0. For p∈PS\mathfrak p \in\mathcal{P}_S we have vp(j)=0≠vp(a)v_{\mathfrak p}(j)=0 \ne v_{\mathfrak p}(a), and hence ∣a+j∣p=max⁡{1,∣a∣p}|a+j|_{\mathfrak p}=\max\{1,|a|_{\mathfrak p}\}. Taking the product over v∈Sv \in S and using (5) and Lemma 4.2 (i) and (ii), we obtain

cJdHK(a)≤∏v∈S∣a+j∣v=NS(a+j)≤NS(b).c_J^dH_K(a)\le\prod_{v\in S}|a+j|_v=N_S(a+j)\le N_S(b).

(ii) Since η\eta is a unit, σv(η)≠0\sigma_v(\eta)\ne0 for every v∈MK∞v\in M_K^\infty. Applying Lemma 4.6 with zv=σv(a)/σv(η)z_v=\sigma_v(a)/\sigma_v(\eta) and multiplying the resulting inequalities by ∣σv(η)∣|\sigma_v(\eta)|, we obtain j∈Jj\in J such that

∣a+jη∣v≥cJdvmax⁡{∣a∣v,∣η∣v}(v∈MK∞).|a+j\eta|_v\ge c_J^{d_v}\max\{|a|_v,|\eta|_v\}\qquad(v\in M_K^\infty).

In particular, a+jη≠0a+j\eta\ne0. For p∈PS\mathfrak p\in\mathcal{P}_S we have vp(jη)=vp(η)≠vp(a)v_{\mathfrak p}(j\eta)=v_{\mathfrak p}(\eta)\ne v_{\mathfrak p}(a), and hence ∣a+jη∣p=max⁡{∣a∣p,∣η∣p}|a+j\eta|_{\mathfrak p}=\max\{|a|_{\mathfrak p},|\eta|_{\mathfrak p}\}. Using Lemma 4.2 (i) and the elementary inequality max⁡{s,t}≥max⁡{1,t}min⁡{1,s}\max\{s,t\}\ge\max\{1,t\}\min\{1,s\}, valid for real s,t≥0s,t\ge0, we get

NS(a+jη)≥cJd∏v∈Smax⁡{∣a∣v,∣η∣v}≥cJd∏v∈Smax⁡{1,∣η∣v}∏v∈Smin⁡{1,∣a∣v}.N_S(a+j\eta)\ge c_J^d\prod_{v\in S}\max\{|a|_v,|\eta|_v\}\ge c_J^d\prod_{v\in S}\max\{1,|\eta|_v\}\prod_{v\in S}\min\{1,|a|_v\}.

By (5) and (6), the two products on the right are HK(η)H_K(\eta) and NS(a)/HK(a)N_S(a)/H_K(a), respectively. Since NS(a)≥1N_S(a)\ge1 by Lemma 4.2 (i), we conclude that

NS(a+jη)≥cJdHK(η)HK(a).N_S(a+j\eta)\ge c_J^d\frac{H_K(\eta)}{H_K(a)}.

Remark 4.8. The hypotheses on vp(a)v_{\mathfrak p}(a), p∈PS\mathfrak p\in\mathcal{P}_S, are not automatic, and they are the reason for the rescaling of xx by pαp^\alpha and of yy by p2αp^{2\alpha} in the next section.

We record for future use the following elementary analogue of the Euler–Fermat theorem.

Lemma 4.9. Let ξ∈OK,S×\xi\in\mathcal{O}_{K,S}^{\times} be a unit of infinite order, and let a∈OK,S∖{0}a \in\mathcal{O}_{K,S} \setminus\{0\}. Then there exists an integer n≥1n \ge1 such that ε:=ξn\varepsilon:= \xi^n is a unit of infinite order with a∣ε−1a \mid\varepsilon- 1.

Proof. Since OK,S/aOK,S\mathcal{O}_{K,S}/a\mathcal{O}_{K,S} is finite, the image of ξ\xi in its unit group has finite order, say n≥1n \ge1. Then ε:=ξn\varepsilon:= \xi^n satisfies a∣ε−1a \mid\varepsilon- 1, and it has infinite order since ξ\xi does. □

Definability of the squaring function

We now come to the main step of the proof: we construct a positive-existential formula φsq(x,y)\varphi_{\mathrm{sq}}(x,y) which holds in OK,S\mathcal{O}_{K,S} if and only if y=x2y=x^2, 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 KK and SS, which we now fix (see also Remark 6.1). Recall from § 4 that p1,…,pkp_1,\ldots,p_k are the rational primes below the primes in PS\mathcal{P}_S and that P=p1⋯pkP=p_1\cdots p_k.

  • Set m:=r1+r2+1m:=r_1+r_2+1 and js:=1+Psj_s:=1+P^s for 0≤s<3m0\le s<3m. We split these 3m3m integers into three consecutive sets of mm elements: for i=0,1,2i=0,1,2, let Ji:={jim,jim+1,…,j(i+1)m−1}J_i:=\{j_{im},j_{im+1},\ldots,j_{(i+1)m-1}\}.

  • Set jmax⁡:=1+P(3m−1)j_{\max}:=1+P^{(3m-1)}, the largest of the jsj_s, and set c:=(2jmax⁡+1)−1c:=(2j_{\max}+1)^{-1} and C:=(2/c)dC:=(2/c)^d.

  • For a multi-index α=(α1,…,αk)∈Z≥0k\alpha=(\alpha_1,\ldots,\alpha_k)\in\mathbb{Z}_{\ge0}^k we write pα:=∏i=1kpiαip^\alpha:=\prod_{i=1}^k p_i^{\alpha_i}, and we set A:={0,1,…,3d}k\mathcal{A}:=\{0,1,\ldots,3d\}^k. (If S=MK∞S=M_K^\infty, then A\mathcal{A} consists only of the empty multi-index, and pα=1p^\alpha=1.)

  • Let qq be a rational prime, coprime to PP, with q>64c−5q>64c^{-5}.

Each jsj_s is congruent to 11 modulo every pip_i, and hence is coprime to PP. Thus each JiJ_i is admissible in the sense of Definition 4.5, the sets J0J_0, J1J_1 and J2J_2 are pairwise disjoint, and cJi≥ccJ_i\ge c for i=0,1,2i=0,1,2. They will play the role of the admissible sets of translations in Proposition 4.7.

We can now write down the formula. Let φsq(x,y)\varphi_{\mathrm{sq}}(x,y) be

(x=0∧y=0)∨(ψ≠(x)∧ψ≠(y)∧∃ε,η,δ ψ(x,y,ε,η,δ)),(7)(x=0\wedge y=0)\vee(\psi_{\ne}(x)\wedge\psi_{\ne}(y)\wedge\exists\varepsilon,\eta,\delta\ \psi(x,y,\varepsilon,\eta,\delta)), \tag*{(7)}

where ψ≠\psi_{\ne} is the formula of Proposition 2.1, and ψ(x,y,ε,η,δ)\psi(x,y,\varepsilon,\eta,\delta) is the conjunction of the following four formulas:

ψ1(ε):ε∣1∧ψ≠(ε−1)∧q∣ε−1,(8)\psi_1(\varepsilon):\quad\varepsilon\mid1 \wedge\psi_{\ne}(\varepsilon-1) \wedge q \mid\varepsilon-1, \tag*{(8)}
ψ2(ε,η,δ):η=ε5∧δ=ε10,(9)\psi_2(\varepsilon,\eta,\delta):\quad\eta=\varepsilon^5 \wedge\delta=\varepsilon^{10}, \tag*{(9)}
ψ3(x,y,ε):⋀α∈A⋁i=02⋀j∈Ji(pαx+j∣ε−1∧p2αy+j∣ε−1),(10)\psi_3(x,y,\varepsilon):\quad\bigwedge_{\alpha\in\mathcal{A}}\bigvee_{i=0}^{2}\bigwedge_{j\in J_i}(p^\alpha x+j\mid\varepsilon-1\wedge p^{2\alpha}y+j\mid\varepsilon-1), \tag*{(10)}
ψ4(x,y,η,δ):⋀α∈A⋀j∈J0pαx+jη∣p2αy−j2δ.(11)\psi_4(x,y,\eta,\delta):\quad\bigwedge_{\alpha\in\mathcal{A}}\bigwedge_{j\in J_0}p^\alpha x+j\eta\mid p^{2\alpha}y-j^2\delta. \tag*{(11)}

All the index sets and constants involved are fixed; in particular, pαp^\alpha, p2αp^{2\alpha}, jj and j2j^2 are rational integers, and the conditions η=ε5\eta=\varepsilon^5 and δ=ε10\delta=\varepsilon^{10} can be expressed as explained at the end of § 3. Thus φsq\varphi_{\mathrm{sq}} is a positive-existential Ldiv\mathcal{L}_{\mathrm{div}}-formula.

Let us explain the role of the various parts of φsq\varphi_{\mathrm{sq}}. The idea is that, if y≠x2y\ne x^2, the nonzero element p2α(y−x2)p^{2\alpha}(y-x^2) is forced to have a divisor which is too large. Condition ψ1\psi_1 gives a lower bound for the height of the unit ε\varepsilon: since ε≠1\varepsilon\ne1 and q∣ε−1q\mid\varepsilon-1, Corollary 4.4 shows that ε\varepsilon is large, independently of xx and yy. Condition ψ3\psi_3 gives upper bounds for the heights of pαxp^\alpha x and p2αyp^{2\alpha}y in terms of that of ε\varepsilon, by Proposition 4.7 (i). Condition ψ2\psi_2 provides the powers η=ε5\eta=\varepsilon^5 and δ=η2\delta=\eta^2. Finally, since pαx+jηp^\alpha x+j\eta always divides p2αx2−j2δp^{2\alpha}x^2-j^2\delta, condition ψ4\psi_4 implies that pαx+jηp^\alpha x+j\eta divides p2α(y−x2)p^{2\alpha}(y-x^2), and by Proposition 4.7 (ii) and the previous bounds, this divisor is too large for some jj unless y=x2y=x^2. With these estimates, the exponent 5 is the smallest one for which this comparison works.

Theorem 5.1. Suppose that r≥1r\ge1. Then for all x,y∈OK,Sx,y\in\mathcal{O}_{K,S}, the formula φsq(x,y)\varphi_{\mathrm{sq}}(x,y) holds in OK,S\mathcal{O}_{K,S} if and only if y=x2y=x^2. In particular, the graph of the squaring function is positive-existentially definable in the Ldiv\mathcal{L}_{\mathrm{div}}-structure OK,S\mathcal{O}_{K,S}.

Proof. First suppose that y=x2y=x^2. If x=0x=0, then the first disjunct in (7) holds. We may therefore assume that x≠0x\ne0, and hence y≠0y\ne0; thus ψ≠(x)\psi_{\ne}(x) and ψ≠(y)\psi_{\ne}(y) hold by Proposition 2.1. For each α∈A\alpha\in\mathcal{A} there is at most one jj such that pαx+j=0p^\alpha x+j=0 and at most one jj such that p2αy+j=0p^{2\alpha}y+j=0. Since the sets J0J_0, J1J_1 and J2J_2 are pairwise disjoint, there is i(α)∈{0,1,2}i(\alpha)\in\{0,1,2\} such that none of the elements pαx+jp^\alpha x+j and p2αy+jp^{2\alpha}y+j, with j∈Ji(α)j\in J_{i(\alpha)}, is zero. Since r≥1r\ge1, there is a unit ξ\xi of infinite order; this is the only point in the proof where the hypothesis r≥1r\ge1 is used. Applying Lemma 4.9 to ξ\xi and to the product of qq and all these elements (for all α∈A\alpha\in\mathcal{A}), we obtain a unit ε\varepsilon of infinite order such that q∣ε−1q\mid\varepsilon-1 and (10) holds. Since ε≠1\varepsilon\ne1, (8) holds by Proposition 2.1. Let η=ε5\eta=\varepsilon^5 and δ=ε10\delta=\varepsilon^{10}, so that (9) holds by Proposition 3.2. Finally, (11) holds because

p2αy−j2ε10=(pαx+jε5)(pαx−jε5).p^{2\alpha}y-j^2\varepsilon^{10}=(p^\alpha x+j\varepsilon^5)(p^\alpha x-j\varepsilon^5).

Thus all four conditions in (7) are satisfied, and hence φsq(x,y)\varphi_{\mathrm{sq}}(x,y) 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, x≠0x\ne0 y≠0y \ne0. Fix ε\varepsilon, η\eta and δ\delta such that ψ(x,y,ε,η,δ)\psi(x,y,\varepsilon,\eta,\delta) holds. Then ε\varepsilon is a unit, ε≠1\varepsilon\ne1, q∣ε−1q \mid\varepsilon- 1, η=ε5\eta= \varepsilon^5 and δ=ε10\delta= \varepsilon^{10}. We first choose the rescaling.

Claim A. There exists a multi-index α∈A\alpha\in\mathcal{A} such that vp(pαx)≠0v_{\mathfrak{p}}(p^\alpha x) \ne0, vp(p2αy)≠0v_{\mathfrak{p}}(p^{2\alpha}y) \ne0 and vp(pαx)≠5vp(ε)v_{\mathfrak{p}}(p^\alpha x) \ne5v_{\mathfrak{p}}(\varepsilon) for every p∈PS\mathfrak{p} \in\mathcal{P}_S.

Proof of Claim A. For each 1≤i≤k1 \le i \le k, choose

αi∈{0,…,3d}∖({−vp(x)e(p:pi):p∣pi}∪{−vp(y)2e(p:pi):p∣pi}∪{5vp(ε)−vp(x)e(p:pi):p∣pi})\alpha_i \in\{0,\ldots,3d\} \setminus\left(\left\{\frac{-v_{\mathfrak{p}}(x)}{e(\mathfrak{p}:p_i)}:\mathfrak{p}\mid p_i\right\}\cup\left\{\frac{-v_{\mathfrak{p}}(y)}{2e(\mathfrak{p}:p_i)}:\mathfrak{p}\mid p_i\right\}\cup\left\{\frac{5v_{\mathfrak{p}}(\varepsilon)-v_{\mathfrak{p}}(x)}{e(\mathfrak{p}:p_i)}:\mathfrak{p}\mid p_i\right\}\right)

arbitrarily, where p\mathfrak{p} ranges over the primes in PS\mathcal{P}_S above pip_i and e(p:pi)e(\mathfrak{p}:p_i) denotes the ramification index. This is possible since there are at most dd primes above pip_i, so at most 3d3d values have to be avoided. Since vp(pαx)=αie(p:pi)+vp(x)v_{\mathfrak{p}}(p^\alpha x)=\alpha_i e(\mathfrak{p}:p_i)+v_{\mathfrak{p}}(x) and vp(p2αy)=2αie(p:pi)+vp(y)v_{\mathfrak{p}}(p^{2\alpha}y)=2\alpha_i e(\mathfrak{p}:p_i)+v_{\mathfrak{p}}(y) for p∣pi\mathfrak{p}\mid p_i, the multi-index α=(α1,…,αk)\alpha=(\alpha_1,\ldots,\alpha_k) is as required. □

Fix such an α\alpha, and write

X:=pαx,Y:=p2αy.X := p^\alpha x,\qquad Y := p^{2\alpha}y.

Claim B. We have

HK(X)≤CHK(ε)andHK(Y)≤CHK(ε).(12)H_K(X) \le C H_K(\varepsilon) \quad\text{and}\quad H_K(Y) \le C H_K(\varepsilon). \tag*{(12)}

Proof of Claim B. Since (10) holds, there is i∈{0,1,2}i \in\{0,1,2\} such that X+j∣ε−1X+j\mid\varepsilon-1 and Y+j∣ε−1Y+j\mid\varepsilon-1 for every j∈Jij\in J_i. By Claim A, vp(X)≠0v_{\mathfrak{p}}(X)\ne0 and vp(Y)≠0v_{\mathfrak{p}}(Y)\ne0 for every p∈PS\mathfrak{p}\in\mathcal{P}_S. Applying Proposition 4.7 (i) with J=JiJ=J_i to the nonzero element ε−1\varepsilon-1, and using Lemma 4.2 and cJi≥cc_{J_i}\ge c, we obtain

HK(X)≤c−dNS(ε−1)≤c−dHK(ε−1)≤(2/c)dHK(ε)=CHK(ε),H_K(X)\le c^{-d}N_S(\varepsilon-1)\le c^{-d}H_K(\varepsilon-1)\le(2/c)^dH_K(\varepsilon)=CH_K(\varepsilon),

and similarly for YY. □

Suppose, towards a contradiction, that D:=Y−X2≠0D:=Y-X^2\ne0. For every j∈J0j\in J_0, condition (11) gives

X+jε5∣Y−j2ε10,X+j\varepsilon^5\mid Y-j^2\varepsilon^{10},

while

X+jε5∣X2−j2ε10.X+j\varepsilon^5\mid X^2-j^2\varepsilon^{10}.

Hence X+jε5∣DX+j\varepsilon^5\mid D for every j∈J0j\in J_0. By Claim A, we may apply Proposition 4.7 (ii) with J=J0J=J_0, a=Xa=X and η=ε5\eta=\varepsilon^5, and so, using cJ0≥cc_{J_0}\ge c and HK(ε5)=HK(ε)H_K(\varepsilon^5)=H_K(\varepsilon) (Lemma 4.2 (iii)), there is j∈J0j\in J_0 such that X+jε5≠0X+j\varepsilon^5\ne0 and

NS(X+jε5)≥cdHK(ε)5HK(X)N_S(X+j\varepsilon^5)\ge c^d\frac{H_K(\varepsilon)^5}{H_K(X)}

Combining this with Claim B, Lemma 4.2 and the divisibility X+jε5∣DX+j\varepsilon^5\mid D, we obtain

cdC−1HK(ε)4≤cdHK(ε)5HK(X)≤NS(X+jε5)≤NS(D)≤HK(D)≤2dHK(Y)HK(X)2≤2dC3HK(ε)3.(13)\begin{aligned} c^d C^{-1}H_K(\varepsilon)^4 &\le c^d\frac{H_K(\varepsilon)^5}{H_K(X)} \le N_S(X+j\varepsilon^5) \\ &\le N_S(D) \le H_K(D) \le2^d H_K(Y)H_K(X)^2 \\ &\le2^d C^3H_K(\varepsilon)^3. \tag*{(13)} \end{aligned}

Canceling HK(ε)3H_K(\varepsilon)^3 in (13) gives

HK(ε)≤2dc−dC4=(32c−5)d.(14)H_K(\varepsilon)\le2^d c^{-d}C^4=(32c^{-5})^d. \tag*{(14)}

On the other hand, by ψ1\psi_1, Corollary 4.4 and our choice of qq,

HK(ε)≥(q/2)d>(32c−5)d,(15)H_K(\varepsilon)\ge(q/2)^d>(32c^{-5})^d, \tag*{(15)}

contradicting (14). Therefore Y=X2Y=X^2, that is, p2α(y−x2)=0p^{2\alpha}(y-x^2)=0, and so y=x2y=x^2. This concludes the proof. □\square

Undecidability

We first note that Theorem 1.1 follows from Theorem 5.1. Indeed, suppose that r≥1r\ge1. Since

2xy=(x+y)2−x2−y22xy=(x+y)^2-x^2-y^2

and OK,S\mathcal{O}_{K,S} 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 ψ≠\psi_{\ne}, Prod⁡u\operatorname{Prod}_u and φsq\varphi_{\mathrm{sq}} on which it is built, are rational integers, which can be expressed in Ldiv\mathcal{L}_{\mathrm{div}} by means of 11 and ++. It is, however, not uniform in KK and SS: the integers pp and bb of Proposition 2.1, the prime ℓ\ell and the number NN of Proposition 3.2, and the prime qq, the sets JiJ_i and the multi-indices in AA of § 5 all depend on KK and SS.

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 Ldiv\mathcal{L}_{\mathrm{div}}.

The undecidability results quoted above concern polynomial equations whose coefficients may lie in OK,S\mathcal{O}_{K,S}. These constants cannot simply be named in Ldiv\mathcal{L}_{\mathrm{div}}: in general they are not even definable without parameters, since an automorphism of KK preserving OK,S\mathcal{O}_{K,S} preserves addition and divisibility (for instance, 2\sqrt{2} and −2-\sqrt{2} satisfy the same parameter-free formulas in Z[2]\mathbb{Z}[\sqrt{2}]). The following standard observation allows us to remove them.

Lemma 6.2. Let RR be a subring of KK which is finitely generated as a Z\mathbb{Z}-algebra and has fraction field KK. Then for every system of polynomial equations with coefficients in RR one can effectively construct a system of polynomial equations with coefficients in Z\mathbb{Z} which has a solution over RR if and only if the original system does.

Proof. Fix a finite presentation

R≅Z[X1,…,Xh]/(g1,…,ge),R \cong\mathbb{Z}[X_{1},\ldots,X_{h}]/(g_{1},\ldots,g_{e}),

and let θ1,…,θh\theta_{1},\ldots,\theta_{h} be the images of X1,…,XhX_{1},\ldots,X_{h}. Replace each coefficient of the given system by a polynomial expression in θ1,…,θh\theta_{1},\ldots,\theta_{h} with integer coefficients, replace θ1,…,θh\theta_{1},\ldots,\theta_{h} by new variables t1,…,tht_{1},\ldots,t_{h}, and add the equations gλ(t1,…,th)=0g_{\lambda}(t_{1},\ldots,t_{h})=0 for λ=1,…,e\lambda=1,\ldots,e.

Clearly, if the original system has a solution, then so does the new one (take ti=θit_{i}=\theta_{i}). Conversely, a solution t1,…,th∈Rt_{1},\ldots,t_{h}\in R of the equations gλ=0g_{\lambda}=0 determines a homomorphism of Z\mathbb{Z}-algebras ϕ:R→R\phi:R\to R with ϕ(θi)=ti\phi(\theta_{i})=t_{i}. We claim that ϕ\phi is injective. Indeed, a nonzero element κ\kappa of its kernel is algebraic over Q\mathbb{Q}, so it satisfies an equation with integer coefficients and nonzero constant term n0n_{0}; it follows that n0∈ker⁡ϕn_{0}\in\ker\phi, which is impossible since ϕ(n0)=n0≠0\phi(n_{0})=n_{0}\ne0. Therefore, ϕ\phi extends to a field embedding K→KK\to K, which is an automorphism of finite order, say nn. Since ϕ(R)⊆R\phi(R)\subseteq R, we have R=ϕn(R)⊆ϕ(R)⊆RR=\phi^{n}(R)\subseteq\phi(R)\subseteq R, so ϕ(R)=R\phi(R)=R. Applying ϕ−1\phi^{-1} 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 f∈Z[x1,…,xn]f\in\mathbb{Z}[x_{1},\ldots,x_{n}], whether ff has a zero in OK,Sn\mathcal{O}_{K,S}^{n}.

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 OK\mathcal{O}_{K}, and Eisenträger [5 Theorem 7.9] showed that OK\mathcal{O}_{K} is Diophantine over OK,S\mathcal{O}_{K,S}; hence Hilbert’s tenth problem over OK,S\mathcal{O}_{K,S}, for polynomials with coefficients in OK,S\mathcal{O}_{K,S}, also has a negative answer. To apply Lemma 6.2, we note that OK,S\mathcal{O}_{K,S} is finitely generated as a Z\mathbb{Z}-algebra: if hKh_{K} denotes the class number of KK, ap∈OKa_{\mathfrak{p}}\in\mathcal{O}_{K} is a generator of phK\mathfrak{p}^{h_{K}} for each p∈PS\mathfrak{p}\in P_{S}, and a:=∏p∈PSapa:=\prod_{\mathfrak{p}\in P_{S}}a_{\mathfrak{p}}, then OK,S=OK[a−1]\mathcal{O}_{K,S}=\mathcal{O}_{K}[a^{-1}]. Lemma 6.2 now allows us to replace the coefficients by integers.

Proof of Corollary 1.2. Suppose that r≥1r\geq1. By Theorem 1.1, every polynomial equation with integer coefficients can be effectively translated into a positive-existential LdivL_{\mathrm{div}}-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. [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. [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. [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. [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. [5][Eis03] K. Eisenträger, Hilbert’s tenth problem and arithmetic geometry. PhD thesis, University of California, Berkeley, 2003.
  6. [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. [7][HS00] M. Hindry and J. H. Silverman, Diophantine geometry. An introduction. Graduate Texts in Mathematics, 201, Springer, New York, 2000.DOI
  8. [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. [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. [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. [11][Lip78a] L. Lipshitz, The Diophantine problem for addition and divisibility. Trans. Amer. Math. Soc. 235(1978), 271–283.DOI

Paper details

vlnc:W_f33w5qw7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude

View statement
Looking for related papers…
Contents