# On the existential theory of the completions of a global field

Philip Dittmann and Arno Fehm  Institut für Algebra, Technische Universität
Dresden, 01062 Dresden, Germany<EMAIL_ADDRESS>Institut für
Algebra, Technische Universität Dresden, 01062 Dresden, Germany  arno.fehm@tu-
dresden.de

###### Abstract.

We discuss the common existential theory of all or almost all completions of a
global function field.

##  1\. Introduction

The celebrated Hasse–Minkowski local-global principle states that a quadratic
form over a global field $K$ has a nontrivial zero in $K$ if and only if it
has a nontrivial zero in each completion of $K$. Given a concrete quadratic
form $f\in K[x_{1},\dots,x_{n}]$ one can effectively decide whether $f$ has a
nontrivial zero in all completions, eventually leading to an algorithm to
decide whether $f$ has a nontrivial zero in $K$.

For polynomials of higher degree the local-global principle fails, and it is
conjectured (for $K$ a number field, see e.g. [Koe14, Poo03]) respectively
known (for $K$ a global function field [Phe91, Vid94, Shl92, Eis03]) that the
problem of whether polynomials over $K$ have a zero in $K$ is undecidable. In
this short note we want to study the local problem, i.e. deciding whether a
polynomial over $K$ has a zero in each completion of $K$.

For number fields $K$, even much more is known by the seminal work of Ax:

######  Theorem 1.1 ([Ax68]).

The (common) $\mathfrak{L}_{\rm val}$-theory of all $\mathbb{Q}_{p}$ and the
$\mathfrak{L}_{\rm val}$-theory of almost all $\mathbb{Q}_{p}$ is decidable.

Here, $\mathfrak{L}_{\rm val}$ is the language of valued fields, and by the
theory of almost all $\mathbb{Q}_{p}$ we mean the set of sentences true in all
but finitely many $\mathbb{Q}_{p}$. Since also the $\mathfrak{L}_{\rm
ring}$-theories of $\mathbb{R}$ and $\mathbb{C}$ are decidable by the work of
Tarski [Tar48], and every number field can be interpreted in $\mathbb{Q}$,
this leads to:

######  Corollary 1.2.

Let $K$ be a number field. The $\mathfrak{L}_{\rm ring}$-theory of all
completions of $K$ and the $\mathfrak{L}_{\rm ring}$-theory of almost all
completions of $K$ is decidable. In particular, it is decidable whether a
given polynomial over $K$ has a zero in all respectively almost all
completions of $K$.111For a sketch see Remark 6.8.

See also [Kar23] for a recent negative result in this direction.

For completions of global function fields, there is at this point little hope
to decide the common theory of all completions, since even the theory of a
single completion $\mathbb{F}_{q}(\\!(t)\\!)$ seems out of reach. For the
existential theory (that is, essentially, deciding which polynomials have
zeros), the following result of Anscombe and the second author is somewhat
orthogonal:

######  Theorem 1.3 ([AF23]).

The existential $\mathfrak{L}_{\rm val}$-theory of all respectively almost all
$\mathbb{F}_{p}(\\!(t)\\!)$, where $p$ runs over the prime numbers, is
decidable.

This builds crucially on our understanding of the existential theory of each
individual $\mathbb{F}_{q}(\\!(t)\\!)$, where we have two kinds of results: By
[AF16], the existential theory of any $\mathbb{F}_{q}(\\!(t)\\!)$ in the
language of valued fields $\mathfrak{L}_{\rm val}$ is decidable. The
existential theory of $\mathbb{F}_{q}(\\!(t)\\!)$ in the language
$\mathfrak{L}_{\rm val}(t)$ of valued fields with a constant symbol for $t$
was shown to be decidable in [DS03] assuming resolution of singularities in
positive characteristic, and in [ADF23] assuming a consequence of local
uniformisation (which in turn follows from resolution of singularities) called
(R4) (see Section 6). Building on and extending these results, we will show:

######  Theorem 1.4.

For a global function field $K$, the following theories are decidable:

  1. $(a)$

the existential $\mathfrak{L}_{\rm val}$-theory of all completions of $K$,

  2. $(b)$

the existential $\mathfrak{L}_{\rm val}$-theory of almost all completions of
$K$,

  3. $(c)$

the existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all completions
of the perfect hull of $K$,

  4. $(d)$

the existential $\mathfrak{L}_{\rm ring}(K)$-theory of almost all completions
of $K$.

Moreover, assuming (R4) holds, also the following theories are decidable:

  1. $(e)$

the existential $\mathfrak{L}_{\rm val}(K)$-theory of all completions of $K$,

  2. $(f)$

the existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all completions
of $K$.

Here, $\mathfrak{L}_{\rm val}(K)$ and $\mathfrak{L}_{\rm ring}(K)$ are the
expansions of $\mathfrak{L}_{\rm val}$ and $\mathfrak{L}_{\rm ring}$ by
constant symbols for the elements of $K$.

######  Corollary 1.5.

For a global function field $K$, it is decidable whether a polynomial over $K$
has a zero in all respectively almost all completions of $K$, where in the
case of "all completions" we need to either restrict to polynomials over the
prime field of $K$, or assume that (R4) holds.

In fact, we will not only prove decidability but also axiomatise these
theories, where possible for general function fields of one variable. Moreover
we will prove the results not just for existential sentences but for
universal/existential sentences, i.e. finite boolean combinations of
existential sentences (so that in particular we can decide not only whether a
given polynomial has a zero in all respectively all but finitely many
completions, but also whether it has a zero in at most finitely many
respectively no completions).

The six parts of Theorem 1.3 are proven in four sections (Section 3-6), where
each section opens with a general result in the model theory of valued fields.
While in the first of these sections (in which parts (a) and (b) are proven)
this result is readily available in the literature, they get more and more
novel as the paper progresses. In Section 2 we fix notation and summarise the
common arguments used in these four settings.

##  2\. Notation and preliminaries

A valued field is a pair $(F,v)$ consisting of a field $F$ and a (Krull)
valuation $v$ on $F$ (with value group written additively). For basics on
valued fields see [EP05]. By a function field (of one variable) we mean a
finitely generated field extension $K/k$ of transcendence degree $1$ such that
$k$ is algebraically closed in $K$. We denote by $\mathbb{P}_{K}$ the set of
places of $K/k$, which we view as (normalised) discrete valuations on $K$,
trivial on $k$. Recall that for each $v\in\mathbb{P}_{K}$, the residue field
$Kv$ is a finite extension of $k$. A global function field is a function field
$K/k$ with $k$ finite. For basics on function fields see [Sti09]. A field is
pseudofinite if it is an infinite model of the theory of finite fields. A
$K$-variety is a separated scheme of finite type over $K$.

We work in the language $\mathfrak{L}_{\rm ring}=\\{+,\cdot,0,1\\}$ of rings,
and the one-sorted language $\mathfrak{L}_{\rm val}=\mathfrak{L}_{\rm
ring}\cup\\{\mathcal{O}\\}$ of valued fields. For a valuation $v$ on a field
$F$ we denote by $F$ the $\mathfrak{L}_{\rm ring}$-structure $F$, and by
$(F,v)$ the corresponding $\mathfrak{L}_{\rm val}$-structure, where we
interpret $\mathcal{O}$ as the valuation ring $\mathcal{O}_{v}$ of $v$. We
will always fix a field $C$ and view extensions $F$ of $C$ as structures in
the language $\mathfrak{L}_{\rm ring}(C)$, which is $\mathfrak{L}_{\rm ring}$
expanded by constant symbols for the elements of $C$, similarly for
$\mathfrak{L}_{\rm val}(C)$. In particular, ${\rm Th}(F)$ is then the
$\mathfrak{L}_{\rm ring}(C)$-theory of the field $F$ and ${\rm Th}(F,v)$
denotes the $\mathfrak{L}_{\rm val}(C)$-theory of the valued field $(F,v)$. We
view the residue field $Fv$ as an $\mathfrak{L}_{\rm ring}(C)$-structure via
the residue map, which for definiteness we define to be constant 0 outside the
valuation ring of $v$. If $v$ is trivial on $C$, then we view $Fv$ again as an
extension of $C$. When we speak of decidability we always assume that $C$ is
countable and comes with a fixed injection $C\rightarrow\mathbb{N}$ such that,
with a standard Gödel coding, the atomic diagram of $C$ is computable. Such an
injection can always be found when $C$ is a global function field (cf. [FJ08,
§19.2]).

An existential respectively universal formula is a formula of the form
$\exists x_{1},\dots,x_{n}\psi$ respectively $\forall x_{1},\dots,x_{n}\psi$
with $\psi$ quantifier-free. A universal/existential formula is a formula
obtained from finitely many existential or universal sentences by conjunctions
and disjunctions. For a theory $T$ we write $T_{\forall/\exists}$ for the set
of universal/existential consequences of $T$ (in the language of $T$), and we
call ${\rm Th}_{\forall/\exists}(M):={\rm Th}(M)_{\forall/\exists}$ the
universal/existential theory of the structure $M$.

We fix a field $C$ and denote by $T_{0}$ the $\mathfrak{L}_{\rm
val}(C)$-theory of valued fields extending the trivially valued field $C$. For
an $\mathfrak{L}_{\rm val}(C)$-theory $T\supseteq T_{0}$ and an
$\mathfrak{L}_{\rm ring}(C)$-theory $R$ we denote by $T(R)$ the theory of
$(F,v)\models T$ with $Fv\models R$. Here we view $C$ as embedded into $Fv$
via the residue map.

######  Lemma 2.1.

Let $T\supseteq T_{0}$ be an $\mathfrak{L}_{\rm val}(C)$-theory. Suppose that

($\ast$) ${\rm Th}_{\forall/\exists}(F,v)={\rm
Th}_{\forall/\exists}(F^{\prime},v^{\prime})\mbox{ whenever
}(F,v),(F^{\prime},v^{\prime})\models T\mbox{ with }{\rm
Th}_{\forall/\exists}(Fv)={\rm Th}_{\forall/\exists}(F^{\prime}v^{\prime}).$

Then, with $R_{0}={\rm Th}(\\{Fv:(F,v)\models T\\})$, the following holds:

  1. $(a)$

${\rm Th}_{\forall/\exists}(F,v)=T({\rm
Th}_{\forall/\exists}(Fv))_{\forall/\exists}$ for every $(F,v)\models T$.

  2. $(b)$

If $T$ is computably enumerable and $R\supseteq R_{0}$ is a decidable
$\mathfrak{L}_{\rm ring}(C)$-theory, then $T(R)_{\forall/\exists}$ is
decidable222Recall the assumptions we have made on $C$ above when we speak
about decidability..

  3. $(c)$

If $(R_{i})_{i\in I}$ is a family of deductively closed $\mathfrak{L}_{\rm
ring}(C)$-theories containing $R_{0}$, then $\bigcap_{i\in
I}T(R_{i})_{\forall/\exists}=T(\bigcap_{i\in I}R_{i})_{\forall/\exists}$.

Moreover, if we weaken the conclusion of $(*)$ to ${\rm
Th}_{\forall/\exists}(F)={\rm Th}_{\forall/\exists}(F^{\prime})$, then (a),
(b) and (c) hold if we interpret each "$\forall/\exists$" to refer only to
universal/existential $\mathfrak{L}_{\rm ring}(C)$-sentences.

###### Proof.

This can be seen directly, or deduced from Corollary 2.23 of [AF23]: The
universal/existential sentences of $\mathfrak{L}_{1}=\mathfrak{L}_{\rm
ring}(C)$ and $\mathfrak{L}_{2}=\mathfrak{L}_{\rm val}(C)$ form fragments in
the terminology of that paper, and together with the theories $R_{0}$
respectively $T$ and the map $\sigma\colon(F,v)\mapsto Fv$, they form a bridge
$B$. With $\hat{B}$ the same bridge but now all $\mathfrak{L}_{\rm ring}(C)$\-
respectively $\mathfrak{L}_{\rm val}(C)$-sentences, and $\iota$ the map on
sentences obtained from interpreting the residue field in the valued field, we
obtain an arch $A=(B,\hat{B},\iota)$. Assumption (i) of that corollary is
satisfied by our hypotheses on $C$ and $T$, assumption (ii) is satisfied by
the definition of $R_{0}$, and assumption (iii) is satisfied by ($\ast$ ‣
2.1). Part (a) of our lemma follows from (III) of the corollary, part (b)
follows from (II), and part (c) follows from (I) together with [ADF23, Lemma
2.24]. The "moreover" part follows just the same, after changing
$\mathfrak{L}_{2}$ to $\mathfrak{L}_{\rm ring}(C)$. ∎

##  3\. Existential $\mathfrak{L}_{\rm val}$-theory without parameters

We start by studying the universal/existential $\mathfrak{L}_{\rm val}$-theory
of all and almost all completions of a function field without any parameters.
Here our background theory is the $\mathfrak{L}_{\rm val}$-theory $T_{1}$ of
equicharacteristic henselian nontrivially valued fields of fixed
characteristic $p\geq 0$, which for technical reasons we view as an
$\mathfrak{L}_{\rm val}(C)$-theory for $C=\mathbb{F}_{p}$ respectively
$C=\mathbb{Q}$.

######  Proposition 3.1.

If $(F,v)$ and $(F^{\prime},v^{\prime})$ are equicharacteristic henselian
nontrivially valued fields whose residue fields $Fv$ and
$F^{\prime}v^{\prime}$ have the same universal/existential $\mathfrak{L}_{\rm
ring}$-theory, then $(F,v)$ and $(F^{\prime},v^{\prime})$ have the same
universal/existential $\mathfrak{L}_{\rm val}$-theory. In particular, ($\ast$
‣ 2.1) holds for $T=T_{1}$ with $C$ a prime field.

###### Proof.

By [AF16, Thm. 1.1], $(F,v)$ and $(F^{\prime},v^{\prime})$ have the same
existential $\mathfrak{L}_{\rm val}$-theory, and therefore also the same
universal/existential $\mathfrak{L}_{\rm val}$-theory. ∎

If $K/k$ is a function field and $v\in\mathbb{P}_{K}$, we denote by
$(\hat{K}_{v},\hat{v})$ the completion of $(K,v)$, which is an
equicharacteristic henselian nontrivially valued field with residue field
$\hat{K}_{v}\hat{v}=Kv$.

######  Proposition 3.2.

Let $K/k$ be a function field of one variable. The universal/existential
$\mathfrak{L}_{\rm val}$-theory of all respectively almost all completions
$\hat{K}_{v}$, $v\in\mathbb{P}_{K}$, is the universal/existential theory of
equicharacteristic henselian nontrivially valued fields with residue field a
model of the theory of all respectively almost all $Kv$.

###### Proof.

As ($\ast$ ‣ 2.1) holds for $T=T_{1}$ by Proposition 3.1, and
$(\hat{K}_{v},\hat{v})$ is a model of $T_{1}$, Lemma 2.1(a) gives that ${\rm
Th}_{\forall/\exists}(\hat{K}_{v},\hat{v})=T_{1}({\rm
Th}(Kv))_{\forall/\exists}$ for every $v\in\mathbb{P}_{K}$. Lemma 2.1(c) shows
that for each $P\subseteq\mathbb{P}_{K}$,

(3.1) $\bigcap_{v\in P}T_{1}({\rm
Th}(Kv))_{\forall/\exists}\;=\;T_{1}(\bigcap_{v\in P}{\rm
Th}(Kv))_{\forall/\exists}.$

This immediately implies the claim for all completions by taking
$P=\mathbb{P}_{K}$ in (3.1), and for almost all completions one gets that

$\bigcup_{P_{0}\subseteq\mathbb{P}_{K}\atop\mbox{\tiny
finite}}\bigcap_{v\in\mathbb{P}_{K}\setminus P_{0}}T_{1}({\rm
Th}(Kv))_{\forall/\exists}\;=\;\bigcup_{P_{0}\subseteq\mathbb{P}_{K}\atop\mbox{\tiny
finite}}T_{1}\big{(}\bigcap_{v\in\mathbb{P}_{K}\setminus P_{0}}{\rm
Th}(Kv)\big{)}_{\forall/\exists}\;=\;T_{1}\big{(}\bigcup_{P_{0}\subseteq\mathbb{P}_{K}\atop\mbox{\tiny
finite}}\bigcap_{v\in\mathbb{P}_{K}\setminus P_{0}}{\rm
Th}(Kv)\big{)}_{\forall/\exists},$

where the first equality holds by (3.1) and the second equality holds
trivially. ∎

We now turn to the case where $k=\mathbb{F}_{q}$ is finite. Then $Kv$ is a
finite field for each $v\in\mathbb{P}_{K}$, and the completion
$(\hat{K}_{v},\hat{v})$ of $(K,v)$ is isomorphic to the Laurent series field
$(Kv(\\!(t)\\!),v_{t})$ with the $t$-adic valuation $v_{t}$ [Ser79, Thm.
II.2]. For $f\in k[t,x]$ irreducible we denote by $K_{f}$ the global function
field ${\rm Quot}(k[t,x]/(f))$.

######  Lemma 3.3.

If $k=\mathbb{F}_{q}$, the map $v\mapsto|Kv|$ has finite fibres and

$R(K):=\\{|Kv|:v\in\mathbb{P}_{K}\\}$

is a cofinite subset of $\\{q^{n}:n\in\mathbb{N}\\}$. More precisely, if
$K=K_{f}$ with $f\in\mathbb{F}_{q}[t,x]$ absolutely irreducible of total
degree $\deg(f)$, then

$E(K):=\\{q^{n}:n\in\mathbb{N},q^{n}\notin
R(K)\\}\subseteq\\{q,q^{2},\dots,q^{2{\rm deg}(f)^{2}}\\}.$

###### Proof.

Every $Kv$ is a finite extension of the field of constants $k$, and so
$|Kv|=q^{[Kv:k]}$. Without loss of generality, $d:={\rm deg}(f)>1$. The genus
$g$ of $K$ is at most $(d-1)^{2}/2$ [Sti09, Cor. 3.11.4], and the Hasse–Weil
bound implies that $K$ has a place of degree $n$ whenever $n\geq 4g+3$ [Sti09,
Cor. 5.2.10(c)]. This holds in case $n>2d^{2}$. ∎

######  Theorem 3.4.

Let $K/k$ be a global function field.

  1. (a)

The universal/existential theory of almost all completions $\hat{K}_{v}$ is
the universal/existential theory of equicharacteristic henselian nontrivially
valued fields with residue field a pseudofinite field extending $k$.

  2. (b)

The universal/existential theory of all completions $\hat{K}_{v}$ is the
universal/existential theory of equicharacteristic henselian nontrivially
valued fields whose residue fields are finite or pseudofinite, extend $k$, and
satisfy the additional sentence $\eta_{K}:=\bigwedge_{q^{\prime}\in
E(K)}\neg\chi_{q^{\prime}}$, where $\chi_{q^{\prime}}$ is such that
$M\models\chi_{q^{\prime}}\Leftrightarrow M\cong\mathbb{F}_{q^{\prime}}$.

###### Proof.

(a) follows immediately from Proposition 3.2, since the theory of almost all
$Kv$ is by Lemma 3.3 the theory of almost all finite extensions of
$k\cong\mathbb{F}_{q}$. So if $\psi_{q}$ is a sentence expressing that the
field contains a subfield isomorphic to $\mathbb{F}_{q}$, then a sentence
$\varphi$ holds in almost all $Kv$ if and only if $\psi_{q}\rightarrow\varphi$
holds in almost all finite fields. By [Ax68, Thm. 9] this is the case if and
only if it holds in all pseudofinite fields, i.e. $\varphi$ holds in all
pseudofinite fields extending $\mathbb{F}_{q}$.

For (b), similarly a sentence $\varphi$ holds in all $Kv$ if and only if
$(\psi_{q}\wedge\eta_{K})\rightarrow\varphi$ holds in all finite fields. By
[Ax68, Thm. 9] this is the case if and only if it holds in all finite or
pseudofinite fields, i.e. $\varphi$ holds in all finite or pseudofinite fields
extending $\mathbb{F}_{q}$ that in addition satisfy $\eta_{K}$. ∎

######  Corollary 3.5.

There is an algorithm which, given a prime power $q$, an absolutely
irreducible polynomial $f\in\mathbb{F}_{q}[t,x]$ and a universal/existential
$\mathfrak{L}_{\rm val}$-sentence $\varphi$ decides whether $\varphi$ holds in
all completions of $K_{f}$, and whether $\varphi$ holds in almost all
completions of $K_{f}$.

###### Proof.

By Proposition 3.1 and Lemma 2.1(b), $T_{1}(R)_{\forall/\exists}$ is decidable
for any decidable $\mathfrak{L}_{\rm ring}$-theory $R$. So by Theorem 3.4 it
suffices to show that the theory of pseudofinite fields extending
$\mathbb{F}_{q}$, and the theory of fields that are finite or pseudofinite
extending $\mathbb{F}_{q}$ and satisfying $\eta_{K}$ are decidable. They
indeed are, since the theory of finite fields and the theory of pseudofinite
fields are decidable by Ax [Ax68, Thm. 13, 13’], the map $q\mapsto\psi_{q}$
(defined as in the proof of Theorem 3.4) is obviously computable, and also the
map $(q,f)\mapsto\eta_{K_{f}}$ is computable: By enumerating varieties over
$\mathbb{F}_{q}$ and rational maps we can effectively find a smooth projective
curve $X$ over $\mathbb{F}_{q}$ birationally equivalent to the affine curve
$f=0$, and then $q^{n}\in E(K)$ if and only if every
$\mathbb{F}_{q^{n}}$-rational point of $X$ is $\mathbb{F}_{q^{m}}$-rational
for some $m|n$, $m\neq n$, which we can check for the finitely many $n\leq
2{\rm deg}(f)^{2}$. ∎

Theorem 1.4(a) and (b) are an immediate consequence of Corollary 3.5 in which
we fix $q$ and $f$ with $K\cong K_{f}$.

######  Remark 3.6.

The algorithm described in Corollary 3.5 can be extended to output, whenever
$\varphi$ holds in almost all completions of $K=K_{f}$, a list of precisely
those finitely many $v\in\mathbb{P}_{K}$ such that
$(\hat{K}_{v},\hat{v})\not\models\varphi$. Since making this precise would
first require a choice of presentation of the places of $K$, we omit the
details.

######  Remark 3.7.

If (like in Theorem 1.4) one is interested only in the existential theory
(rather than the universal/existential theory), the description in Theorem
3.4(b) and its proof can be simplified further: For example, if
$K=\mathbb{F}_{q}(t)$, or more generally if $K$ has a place of degree one,
then the existential theory of all $Kv$ is just the existential theory of
$\mathbb{F}_{q}$. In this case, the existential theory of all $\hat{K}_{v}$ is
the existential theory of $\mathbb{F}_{q}(\\!(t)\\!)$. Similarly, the
universal theory of all (or equivalently almost all) $Kv$ equals the universal
theory of the algebraic closure $\overline{\mathbb{F}}_{q}$, and one can show
that the universal theory of all (or almost all) $\hat{K}_{v}$ is the
universal theory of $\overline{\mathbb{F}}_{q}(\\!(t)\\!)$.

######  Remark 3.8.

One could deduce Theorem 1.4(a,b) from the (a priori weaker) corresponding
statement for $\mathfrak{L}_{\rm ring}$ instead of $\mathfrak{L}_{\rm val}$ if
there were an existential $\mathfrak{L}_{\rm ring}$-formula $\varphi(x)$ and a
universal $\mathfrak{L}_{\rm ring}$-formula $\psi(x)$ (all formulas here
without parameters) such that both $\varphi$ and $\psi$ would define the
valuation ring in all (respectively almost all) completions of $K$. However,
since by Lemma 3.3 the smallest elementary class
$\mathcal{F}\supseteq\\{Kv:v\in\mathbb{P}_{K}\\}$ contains pseudofinite fields
extending $\overline{\mathbb{F}}_{q}$, [AF17, Thm. 5.1, Prop. 6.5(a), 6.20(a)]
(with $C=\mathbb{Z}$,
$\mathcal{K}=\\{(\hat{K}_{v},\hat{v}):v\in\mathbb{P}_{K}\\})$ proves that
neither $\varphi$ nor $\psi$ can exist. We point out that although it is known
that there exist $\exists\forall$-formulas and $\forall\exists$-formulas that
define the valuation ring in all completions of $K$ (see [FP15, Thm. 1.4,
1.6], and [FJ17] for more on definable valuations), no universal/existential
formula $\eta$ defines the valuation ring in almost all completions of $K$:
Fix $v_{0}\in\mathbb{P}_{K}$ such that $q^{d}\in R(K)$ for every
$q^{d}\geq|Kv_{0}|$ and such that $\eta$ defines the valuation ring in
$\hat{K}_{v}$ for every $v$ with $|Kv|\geq|Kv_{0}|$. Then $\eta$ defines the
valuation ring of the unique extension of $v_{0}$ in every finite extension of
$\hat{K}_{v_{0}}$. Since both $\eta$ and $\neg\eta$ are logically equivalent
to $\forall\exists$-formulas, and therefore go up chains [CK90, Exercise
3.1.8], this implies that also in the algebraic closure of $\hat{K}_{v_{0}}$,
$\eta$ defines the valuation ring of the unique extension of $v_{0}$,
contradicting quantifier elimination for algebraically closed fields.

##  4\. Existential $\mathfrak{L}_{\rm val}$-theory with constant parameters,
and the perfect hull

Next we consider two cases where adding constants from a subfield $C$ of $K$
does not do much harm: This essentially happens when the fields involved are
perfect. Our background theory now is the $\mathfrak{L}_{\rm val}(C)$-theory
$T_{2}\supseteq T_{1}$ of henselian nontrivially valued fields $(F,v)$
extending the trivially valued field $C$ with $Fv$ perfect and $Fv/C$
separable (which implies $C$ perfect).

######  Proposition 4.1.

Let $C$ be perfect. If $(F,v)$ and $(F^{\prime},v^{\prime})$ are henselian
nontrivially valued fields extending the trivially valued field $C$ whose
residue fields $Fv$ and $F^{\prime}v^{\prime}$ are perfect and have the same
universal/existential $\mathfrak{L}_{\rm ring}(C)$-theory, then $(F,v)$ and
$(F^{\prime},v^{\prime})$ have the same universal/existential
$\mathfrak{L}_{\rm val}(C)$-theory, i.e. ($\ast$ ‣ 2.1) holds for $T=T_{2}$.

###### Proof.

Corollary 5.7 of [AF16] implies that ${\rm
Th}_{\forall/\exists}(L,w)=T_{2}({\rm Th}(Lw))_{\forall/\exists}$ for every
$(L,w)\models T_{2}$. We assume ${\rm Th}_{\forall/\exists}(Fv)={\rm
Th}_{\forall/\exists}(F^{\prime}v^{\prime})$ and have to show that ${\rm
Th}_{\forall/\exists}(F,v)={\rm Th}_{\forall/\exists}(F^{\prime},v^{\prime})$,
and so we can replace $(F^{\prime},v^{\prime})$ by an elementary extension to
assume without loss of generality that $F^{\prime}v^{\prime}$ is
$|Fv|^{+}$-saturated. As in particular ${\rm Th}_{\exists}(Fv)\subseteq{\rm
Th}_{\exists}(F^{\prime}v^{\prime})$ we obtain an embedding $Fv\rightarrow
F^{\prime}v^{\prime}$ over $C$ [CK90, Lemma 5.2.1], which extends to an
embedding
$(Fv(\\!(t)\\!),v_{t})\rightarrow(F^{\prime}v^{\prime}(\\!(t)\\!),v_{t})$,
proving

${\rm Th}_{\exists}(F,v)={\rm Th}_{\exists}(Fv(\\!(t)\\!),v_{t})\subseteq{\rm
Th}_{\exists}(F^{\prime}v^{\prime}(\\!(t)\\!),v_{t})={\rm
Th}_{\exists}(F^{\prime},v^{\prime}),$

where the two equalities follow from the result mentioned above, as
$(Fv(\\!(t)\\!),v_{t})$ and $(F^{\prime}v^{\prime}(\\!(t)\\!),v_{t})$ are
models of $T_{2}$. The symmetric argument shows that ${\rm
Th}_{\exists}(F^{\prime},v^{\prime})\subseteq{\rm Th}_{\exists}(F,v)$, hence
${\rm Th}_{\forall/\exists}(F,v)={\rm
Th}_{\forall/\exists}(F^{\prime},v^{\prime})$. ∎

######  Proposition 4.2.

Let $K/k$ be a function field of one variable with $k$ perfect. The
universal/existential $\mathfrak{L}_{\rm val}(k)$-theory of all respectively
almost all completions $\hat{K}_{v}$, $v\in\mathbb{P}_{K}$, is the
universal/existential $\mathfrak{L}_{\rm val}(k)$-theory of henselian
nontrivially valued fields extending the trivially valued field $k$ with
residue field a model of the $\mathfrak{L}_{\rm ring}(k)$-theory of all
respectively almost all $Kv$.

###### Proof.

Let $C=k$ and note that $k$ perfect implies that every $Kv$ is perfect, so
$(\hat{K}_{v},\hat{v})\models T_{2}$ for every $v\in\mathbb{P}_{K}$.
Therefore, this works completely analogous to the proof of Proposition 3.2,
replacing $T_{1}$ by $T_{2}$ and Proposition 3.1 by Proposition 4.1. ∎

For a field $K$ we denote by $K^{\rm perf}$ its maximal purely inseparable
extension within $\overline{K}$. For a valuation $v$ on a field $F$ we denote
the unique extension of $v$ to $F^{\rm perf}$ again by $v$.

######  Proposition 4.3.

Let $K/k$ be a function field of one variable. The following theories
coincide:

  1. (1)

The universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all
$(\hat{K}_{v})^{\rm perf}$, $v\in\mathbb{P}_{K}$.

  2. (2)

The universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all
$\hat{L}_{v}$, $v\in\mathbb{P}_{L}$, where $L=K^{\rm perf}$.

  3. (3)

The universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of henselian
nontrivially valued fields extending the trivially valued field $K^{\rm perf}$
with residue field a model of the $\mathfrak{L}_{\rm ring}(K)$-theory of
almost all $(Kv)^{\rm perf}$.333Recall that we view $Kv$ as an
$\mathfrak{L}_{\rm ring}(C)$-structure via the residue map $C\hookrightarrow
K\rightarrow K_{v}$, where here $C=K$.

###### Proof.

Let $C=K^{\rm perf}$. By Łoś’s theorem [CK90, Thm. 4.1.9], the
$\mathfrak{L}_{\rm val}(C)$-theory of almost all $(\hat{K}_{v})^{\rm perf}$ is
the $\mathfrak{L}_{\rm val}(C)$-theory of the ultraproducts
$(K_{\mathcal{U}},v_{\mathcal{U}})=\prod_{v\in\mathbb{P}_{K}}((\hat{K}_{v})^{\rm
perf},\hat{v})/\mathcal{U}$, where $\mathcal{U}$ runs over the nonprincipal
ultrafilters on $\mathbb{P}_{K}$. As every $((\hat{K}_{v})^{\rm
perf},\hat{v})$ is a perfect henselian nontrivially valued field, so is
$(K_{\mathcal{U}},v_{\mathcal{U}})$. In particular,
$K_{\mathcal{U}}v_{\mathcal{U}}$ is perfect. Since every $c\in C^{\times}$ has
nonzero value for at most finitely many $v\in\mathbb{P}_{K}$,
$v_{\mathcal{U}}$ is trivial on $C$. Thus
$(K_{\mathcal{U}},v_{\mathcal{U}})\models T_{2}$. Similarly, the
$\mathfrak{L}_{\rm val}(C)$-theory of almost all $\hat{L}_{v}$ is the
$\mathfrak{L}_{\rm val}(C)$-theory of the ultraproducts
$(L_{\mathcal{U}},w_{\mathcal{U}})=\prod_{v\in\mathbb{P}_{K}}(\hat{L}_{v},\hat{v})/\mathcal{U}$,
and also $(L_{\mathcal{U}},w_{\mathcal{U}})\models T_{2}$. Moreover, as
$(\hat{K}_{v})^{\rm perf}\hat{v}=(Kv)^{\rm perf}=Lv$, we have that
$K_{\mathcal{U}}v_{\mathcal{U}}=\prod_{v\in\mathbb{P}_{K}}(Kv)^{\rm
perf}/\mathcal{U}=L_{\mathcal{U}}w_{\mathcal{U}}$. Proposition 4.1 and Lemma
2.1(a,c) therefore give that

${\rm Th}_{\forall/\exists}(K_{\mathcal{U}},v_{\mathcal{U}})=T_{2}({\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}}))_{\forall/\exists}=T_{2}({\rm
Th}(L_{\mathcal{U}}w_{\mathcal{U}}))_{\forall/\exists}={\rm
Th}_{\forall/\exists}(L_{\mathcal{U}},w_{\mathcal{U}})$

and

$\bigcap_{\mathcal{U}}{\rm
Th}_{\forall/\exists}(K_{\mathcal{U}},v_{\mathcal{U}})=\bigcap_{\mathcal{U}}T_{2}({\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}}))_{\forall/\exists}=T_{2}(\bigcap_{\mathcal{U}}{\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}}))_{\forall/\exists}.$

As $\bigcap_{\mathcal{U}}{\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}})=\bigcap_{\mathcal{U}}{\rm
Th}(\prod_{v\in\mathbb{P}_{K}}(Kv)^{\rm perf}/\mathcal{U})$ is the
$\mathfrak{L}_{\rm ring}(C)$-theory of almost all $(Kv)^{\rm perf}$,
restricting the languages from $\mathfrak{L}_{\rm val}(C)$ and
$\mathfrak{L}_{\rm ring}(C)$ to $\mathfrak{L}_{\rm val}(K)$ and
$\mathfrak{L}_{\rm ring}(K)$ gives the claim. ∎

######  Lemma 4.4.

For a global function field $K$, the $\mathfrak{L}_{\rm ring}(K)$-theory of
almost all $Kv$, $v\in\mathbb{P}_{K}$, is the $\mathfrak{L}_{\rm
ring}(K)$-theory of pseudofinite fields extending $K$, and it is decidable.

###### Proof.

Let $k$ be the constant field of $K$, fix a separating element $t\in K$, let
$\mathcal{O}_{K}$ be the integral closure of $k[t]$ in $K$, and let
$P\subseteq\mathbb{P}_{K}$ be the set of places $v$ of $K$ with
$\mathcal{O}_{K}\subseteq\mathcal{O}_{v}$. As $\mathbb{P}_{K}\setminus P$ is
the set of poles of $t$, and hence finite, the $\mathfrak{L}_{\rm
ring}(K)$-theory of almost all $Kv$, $v\in\mathbb{P}_{K}$, equals the
$\mathfrak{L}_{\rm ring}(K)$-theory of almost all $Kv$, $v\in P$. By [FJ08,
Theorem 20.9.4], this is the set of all $\mathfrak{L}_{\rm ring}(K)$-sentences
for which $\\{v\in P:Kv\models\varphi\\}$ has Dirichlet density $1$, and it is
decidable444Note that the theorem referenced uses $\mathfrak{L}_{\rm
ring}(\mathcal{O}_{K})$ instead of $\mathfrak{L}_{\rm ring}(K)$, but these
languages are equally expressive.. Moreover, by [FJ08, Theorems 20.9.3] the
latter theory is the set of $\mathfrak{L}_{\rm ring}(K)$-sentences $\varphi$
for which the set of $\sigma$ in ${\rm Aut}(\overline{K}/K)$ (which is a
profinite group canonically isomorphic to the absolute Galois group $G_{K}$)
such that $\varphi$ holds in the fixed field of $\sigma$ has Haar measure $1$.
By [FJ08, Theorem 20.5.4] (with $e=1$), this is precisely the theory of
perfect PAC fields $F$ extending $K$ with $G_{F}\cong\hat{\mathbb{Z}}$, the
free profinite group on $e=1$ generators. As a field $F$ is pseudofinite if
and only if it is perfect and PAC with $G_{F}\cong\hat{\mathbb{Z}}$ (see
[FJ08, Corollary 20.10.5]), this proves the claim. ∎

######  Theorem 4.5.

For a global function field $K$, the universal/existential $\mathfrak{L}_{\rm
val}(K)$-theory of almost all $(\hat{K}_{v})^{\rm perf}$,
$v\in\mathbb{P}_{K}$, is the universal/existential $\mathfrak{L}_{\rm
val}(K)$-theory of henselian nontrivially valued fields extending the
trivially valued field $K^{\rm perf}$ with residue field pseudofinite, and it
is decidable.

###### Proof.

As each $Kv$ is finite and therefore $Kv=(Kv)^{\rm perf}$, by Lemma 4.4 the
$\mathfrak{L}_{\rm ring}(K)$-theory of almost all $(Kv)^{\rm perf}$ is the
theory of pseudofinite fields containing $K$. Therefore, the first part
follows from Proposition 4.3. The decidability follows from Proposition 4.1,
Lemma 4.4 and Lemma 2.1(b). ∎

Combining this with the equivalence of (1) and (2) in Proposition 4.3 proves
Theorem 1.4(c).

######  Remark 4.6.

We are not able to prove that the universal/existential $\mathfrak{L}_{\rm
val}(K)$-theory of all $(\hat{K}_{v})^{\rm perf}$ is decidable. This is,
however, not surprising: Such an algorithm would, in particular, be able to
solve the open problem of deciding the existential $\mathfrak{L}_{\rm
val}(K)$-theory of each individual $(\hat{K}_{v_{0}})^{\rm perf}$: If we fix a
$z\in K$ whose only zero is $v_{0}$, then $(\hat{K}_{v_{0}})^{\rm
perf}\models\varphi$ if and only if
$z^{-1}\notin\mathcal{O}\rightarrow\varphi$ holds in all $(\hat{K}_{v})^{\rm
perf}$.

##  5\. Existential $\mathfrak{L}_{\rm ring}$-theory with parameters

We now return to the completions of $K$ and allow arbitrary parameters from
$K$, where we can obtain unconditional results when we restrict the language
to $\mathfrak{L}_{\rm ring}$ (rather than $\mathfrak{L}_{\rm val}$). Here it
will be crucial that a pseudofinite field $L$ is PAC, i.e. every geometrically
integral $L$-variety has $L$-rational points, cf. the proof of Lemma 4.4.

Let $T_{3}\supseteq T_{1}$ be the $\mathfrak{L}_{\rm val}(C)$-theory of
henselian nontrivially valued fields $(F,v)$ extending the trivially valued
field $C$ such that $F/C$ is separable and every geometrically integral smooth
$C$-variety has $Fv$-rational points.

######  Proposition 5.1.

Let $C$ be a field of imperfect exponent at most $1$. If $(F,v)$ and
$(F^{\prime},v^{\prime})$ are henselian nontrivially valued separable
extensions of the trivially valued field $C$ such that $Fv$ and
$F^{\prime}v^{\prime}$ have the same universal/existential $\mathfrak{L}_{\rm
ring}(C)$-theory and every geometrically integral smooth affine $C$-variety
has a rational point over both $Fv$ and $F^{\prime}v^{\prime}$, then $F$ and
$F^{\prime}$ have the same universal/existential $\mathfrak{L}_{\rm
ring}(C)$-theory, i.e. ($\ast$ ‣ 2.1) holds for $T=T_{3}$ with the weaker
conclusion for $\mathfrak{L}_{\rm ring}(C)$ instead of $\mathfrak{L}_{\rm
val}(C)$.

###### Proof.

We claim that by enlarging $C$ we can assume without loss of generality that
$C$ is separably closed in $Fv$ and $F^{\prime}v^{\prime}$. Indeed, if $D$ is
the separable algebraic closure of $C$ in $Fv$, then $C$ and $D$ have the same
imperfect exponent [FJ08, Lemma 2.7.3]. Moreover, since $Fv$ and
$F^{\prime}v^{\prime}$ have the same universal/existential $\mathfrak{L}_{\rm
ring}(K)$-theory, the relative algebraic closure of $C$ in $Fv$ is isomorphic
to the one in $F^{\prime}v^{\prime}$ [FJ08, Lemma 20.6.3(b)], and so we can
choose an isomorphism of $D$ with the separable algebraic closure of $C$ in
$F^{\prime}v^{\prime}$. As $v$ is trivial on $C$, we can identify the
separable algebraic closure of $C$ in $F$ with a subfield of $D$ via the
residue map, and since $v$ is henselian, this subfield is actually all of $D$
(cf. [AF16, Lemma 2.3]). Similarly we identify $D$ with the separable
algebraic closure of $C$ in $F^{\prime}$. Note that $F$ and $F^{\prime}$
remain separable over $D$. Finally, every geometrically integral smooth affine
$D$-variety has a rational point over $Fv$ and $F^{\prime}v^{\prime}$: Such a
$D$-variety is the base change of a geometrically integral smooth affine
$C^{\prime}$-variety $V$ for a finite subextension $C^{\prime}/C$ of $D/C$.
The Weil restriction $W={\rm res}_{C^{\prime}/C}(V)$ is a geometrically
integral smooth affine $C$-variety (see [Sch94, Prop. 4.9] and [Die01, Lemma
1.10]), hence $W(Fv)\neq\emptyset$ by assumption. From the morphism
$W_{C^{\prime}}\rightarrow V$ (see [Sch94, 4.2.5]) we conclude that also
$V(Fv)\neq\emptyset$, and similarly $V(F^{\prime}v^{\prime})\neq\emptyset$.

So from now on assume that $C$ is separably closed in $Fv$ and
$F^{\prime}v^{\prime}$. We already argued that then it is also separably
closed in $F$. Since $F/C$ is separable, $C$ is therefore relatively
algebraically closed in $F$. Together with the assumption of imperfect
exponent at most $1$ this implies that $F/C$ is regular [FJ08, Lemma 2.7.5].
Similarly, $F^{\prime}/C$ is regular. Therefore, by [Dit23, Lemma 4.2], $F$
and $F^{\prime}$ have the same existential $\mathfrak{L}_{\rm
ring}(C)$-theory, and therefore the same universal/existential
$\mathfrak{L}_{\rm ring}(C)$-theory, as soon as every geometrically integral
smooth affine $C$-variety $V$ has an $F$-rational point if and only if it has
an $F^{\prime}$-rational point. But every such $V$ has an $Fv$-rational point
by assumption, and this $Fv$-rational point lifts to an $F$-rational point of
$V$ since $v$ is henselian (see for instance [BLR90, §2.3 Prop. 5]), and
similarly to an $F^{\prime}$-rational point. This concludes the proof. ∎

######  Lemma 5.2.

Let $K$ be a global function field. The $\mathfrak{L}_{\rm val}(K)$-theory of
almost all $\hat{K}_{v}$ contains the $\mathfrak{L}_{\rm val}(K)$-theory of
henselian nontrivially valued fields separable over the trivially valued field
$K$ with residue field pseudofinite.

###### Proof.

Each $(\hat{K}_{v},\hat{v})$ is henselian nontrivially valued. Furthermore,
each $\hat{K}_{v}$ is separable over $K$, since a uniformiser $\pi\in K$ for
$v$ is a $p$-basis for both $K$ and $\hat{K}_{v}$. For each $x\in K^{\times}$,
$v(x)\neq 0$ for only finitely many $v\in\mathbb{P}_{K}$, so models of the
$\mathfrak{L}_{\rm val}(K)$-theory of almost all $\hat{K}_{v}$ have valuation
trivial on $K$. Finally, such a model has pseudofinite residue field by Lemma
4.4. ∎

######  Theorem 5.3.

Let $K$ be a global function field. The universal/existential
$\mathfrak{L}_{\rm ring}(K)$-theory of almost all $\hat{K}_{v}$,
$v\in\mathbb{P}_{K}$, is the universal/existential $\mathfrak{L}_{\rm
ring}(K)$-part of the $\mathfrak{L}_{\rm val}(K)$-theory of henselian
nontrivially valued fields separable over the trivially valued field $K$ with
residue field pseudofinite, and it is decidable.

###### Proof.

Let $C=K$. The $\mathfrak{L}_{\rm val}(K)$-theory of almost all $\hat{K}_{v}$
is the $\mathfrak{L}_{\rm val}(K)$-theory of nonprincipal ultraproducts
$(K_{\mathcal{U}},v_{\mathcal{U}})=\prod_{v\in\mathbb{P}_{K}}(\hat{K}_{v},\hat{v})/\mathcal{U}$.
By Lemma 5.2, every such $(K_{\mathcal{U}},v_{\mathcal{U}})$ is a model of
$T_{3}$: Indeed, pseudofinite fields are PAC, so even every geometrically
integral $K_{\mathcal{U}}v_{\mathcal{U}}$-variety has a
$K_{\mathcal{U}}v_{\mathcal{U}}$-rational point. So by Proposition 5.1 and
Lemma 2.1(a,c),

$\bigcap_{\mathcal{U}}{\rm
Th}_{\forall/\exists}(K_{\mathcal{U}})=\bigcap_{\mathcal{U}}T_{3}({\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}}))_{\forall/\exists}=T_{3}(\bigcap_{\mathcal{U}}{\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}}))_{\forall/\exists},$

where now $\forall/\exists$ denotes universal/existential $\mathfrak{L}_{\rm
ring}(K)$-consequences. As $\bigcap_{\mathcal{U}}{\rm
Th}(K_{\mathcal{U}}v_{\mathcal{U}})=\bigcap_{\mathcal{U}}{\rm
Th}(\prod_{v\in\mathbb{P}_{K}}Kv/\mathcal{U})$ is the $\mathfrak{L}_{\rm
ring}(K)$-theory of almost all $Kv$, which by Lemma 4.4 is the
$\mathfrak{L}_{\rm ring}(K)$-theory of pseudofinite fields containing $K$, the
first claim follows. The decidability follows from Lemma 2.1(b) and Lemma 4.4.
∎

This in particular proves Theorem 1.4(d).

######  Remark 5.4.

Unlike in the other sections, it is essential here that the theory of almost
all residue fields of a global function field contains the theory of PAC
fields. The assumption on rational points in Proposition 5.1 could be dropped
if we were willing to assume some variant of resolution of singularities, but
under (R4) we obtain stronger results in any case (see Section 6).

######  Remark 5.5.

Similar to Remark 4.6, we are not able to prove the decidability of the
universal/existential $\mathfrak{L}_{\rm ring}(K)$-theory of all $\hat{K}_{v}$
as this would imply the decidability of the existential $\mathfrak{L}_{\rm
ring}(K)$-theory of each individual $\hat{K}_{v_{0}}$ (instead of
$z^{-1}\notin\mathcal{O}$ use a universal/existential $\mathfrak{L}_{\rm
ring}(K)$-sentence that determines the size of the relative algebraic closure
of $k$ in the field, and the intersection of the field with a suitably large
finite extension of $K$), which in turn would solve the open problem of
deciding the existential $\mathfrak{L}_{\rm val}(K)$-theory of
$\hat{K}_{v_{0}}$, as the valuation ring in $\hat{K}_{v_{0}}$ is definable
both by an existential and by a universal $\mathfrak{L}_{\rm
ring}(K)$-formula, cf. [ADF23, Lemma 4.9].

On the other hand it seems unlikely that the decidability of the
universal/existential $\mathfrak{L}_{\rm ring}(K)$-theory of almost all
$\hat{K}_{v}$ directly implies the decidability of the the
universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all
$\hat{K}_{v}$, cf. Remark 3.8. The relevant questions here are:

######  Question 5.6.

For a global function field $K$, are there a universal and an existential
$\mathfrak{L}_{\rm ring}(K)$-formula that define the valuation ring in almost
all $\hat{K}_{v}$? Is there even any universal/existential formula that does
this?

##  6\. Existential $\mathfrak{L}_{\rm val}$-theory with parameters

In this final section we return to $\mathfrak{L}_{\rm val}$ instead of
$\mathfrak{L}_{\rm ring}$. We will obtain results conditional on the following
weak consequence of resolution of singularities from [ADF23, p. 2016],
mentioned already in the introduction:

  1. (R4)

Every field $L$ which is existentially closed in $L(\\!(t)\\!)$ is
existentially closed in every extension $F/L$ for which there exists a
valuation $v$ on $F$ trivial on $L$ with residue field $Fv=L$.

Fix a field $C$ of characteristic $p>0$ and $t\in C$. We consider the
following property of a valued field $(F,v)$ with $C\subseteq F$:

  1. UR($t$)

For every $s\in F$, the element $t-s^{p}\in F$ either has non-positive value
under $v$, or it is a uniformiser.

Here, a uniformiser for $v$ is an element of $F$ of minimal positive value.
Note that property UR($t$) is axiomatised by the universal $\mathfrak{L}_{\rm
val}(C)$-sentence

$\forall
s,r\big{(}r\not\in\mathcal{O}\rightarrow(t-s^{p})r^{2}\not\in\mathcal{O}\big{)}.$

We let $T_{4}\supseteq T_{1}$ be the theory of henselian nontrivially valued
fields $(F,v)$ extending the trivially valued field $C$ satisfying UR($t$).

######  Proposition 6.1.

Assume (R4). Suppose there exists a perfect subfield $C_{0}\subseteq C$ with
$C/C_{0}(t)$ separable algebraic. If $(F,v)$ and $(F^{\prime},v^{\prime})$ are
henselian nontrivially valued fields extending the trivially valued field $C$
satisfying UR($t$) such that $Fv$ and $F^{\prime}v^{\prime}$ have the same
universal/existential $\mathfrak{L}_{\rm ring}(C)$-theory, then $(F,v)$ and
$(F^{\prime},v^{\prime})$ have the same universal/existential
$\mathfrak{L}_{\rm val}(C)$-theory, i.e. ($\ast$ ‣ 2.1) holds for $T=T_{4}$.

###### Proof.

If $t$ does not have a $p$-th root in $Fv$, and hence no $p$-th root in
$F^{\prime}v^{\prime}$, then $Fv/C$ and $F^{\prime}v^{\prime}/C$ are
separable, and in this case the claim follows from [ADF23, Corollary 4.16]
(using (R4)). So let us suppose that $t$ is a $p$-th power in $Fv$ and
therefore also in $F^{\prime}v^{\prime}$. The identity on the perfect field
$C_{0}$ extends to sections $\zeta\colon Fv\to F$ and $\zeta^{\prime}\colon
F^{\prime}v^{\prime}\to F^{\prime}$ of the residue homomorphisms [ADF23,
Proposition 4.5]. Let $s:=\zeta(t^{1/p})$ and
$s^{\prime}:=\zeta^{\prime}(t^{1/p})$, so that $v(t-s^{p})>0$,
$v^{\prime}(t-s^{\prime p})>0$. By UR($t$), $\pi:=t-s^{p}$ and
$\pi^{\prime}:=t-s^{\prime p}$ are uniformisers for $v$ and $v^{\prime}$,
respectively. As $Fv$ and $F^{\prime}v^{\prime}$ have the same
universal/existential $\mathfrak{L}_{\rm ring}(C)$-theory, the relative
algebraic closures $D$ and $D^{\prime}$ of $C$ in $Fv$ respectively
$F^{\prime}v^{\prime}$ are isomorphic (see again [FJ08, Lemma 20.6.3(b)]), and
we fix once and for all an isomorphism and identify them. As $D$ has imperfect
exponent at most $1$ (since it can be no higher than that of $C$) the
extensions $Fv/D$ and $F^{\prime}v^{\prime}/D$ are separable [FJ08, Lemma
2.7.5]. The $C_{0}$-isomorphism
$\zeta^{\prime}\circ\zeta^{-1}|_{\zeta(D)}\colon\zeta(D)\rightarrow\zeta^{\prime}(D)$
extends uniquely to an isomorphism
$g\colon\zeta(D)(\pi)\rightarrow\zeta^{\prime}(D)(\pi^{\prime})$ with
$g(\pi)=\pi^{\prime}$. As $v$ is trivial on $\zeta(D)$ and $v(\pi)>0$,
$v|_{\zeta(D)(\pi)}$ is the $\pi$-adic valuation on the function field
$\zeta(D)(\pi)$, and similarly for
$v^{\prime}|_{\zeta^{\prime}(D)(\pi^{\prime})}$. Therefore, $g$ is in fact an
isomorphism of valued subfields of $(F,v)$ respectively
$(F^{\prime},v^{\prime})$. As $g(s)=s^{\prime}$ and $g(\pi)=\pi^{\prime}$, we
have $g(t)=t$, so $g$ is even a $C_{0}(t)$-isomorphism.

Now [ADF23, Proposition 4.11] implies (using (R4)) that the
universal/existential $\mathfrak{L}_{\rm val}$-theories of $(F,v)$ and
$(F^{\prime},v^{\prime})$ agree, with parameters from $\zeta(D)(\pi)$ and
$\zeta^{\prime}(D)(\pi^{\prime})$ respectively, where the parameter fields are
identified via $g$. Let $c\in C$ be arbitrary, and let $f\in C_{0}(t)[x]$ be
its minimal polynomial over $C_{0}$. Now $c$ is the unique zero of $f$ in $F$
with the same residue as $\zeta(c)\in\zeta(D)$. This identifies $c$ as the
unique witness in $(F,v)$ of the quantifier-free $\mathfrak{L}_{\rm
val}(\zeta(D)(\pi))$-formula

$f(x)=0\wedge(x-\zeta(c))\pi^{-1}\in\mathcal{O}.$

It follows that the universal/existential $\mathfrak{L}_{\rm val}(C)$-theories
of $(F,v)$ and $(F^{\prime},v^{\prime})$ agree, since parameters from $C$ may
be eliminated in favour of parameters from $\zeta(D)(\pi)$ and
$\zeta^{\prime}(D)(\pi^{\prime})$, respectively. ∎

######  Remark 6.2.

If $Fv/C$ is separable, axiom UR($t$) is automatically satisfied, since
$v(t-s^{p})\leq 0$ for all $s$. Otherwise, the axiom cannot be dispensed with.
Indeed, let $s\in F$ with $v(t-s^{p})>0$, so $t-s^{p}$ is a uniformiser by
assumption. Then the extension field $F^{\prime}:=F(\sqrt{t-s^{p}})$ with the
unique extension of $v$ is totally ramified and hence also has residue field
$Fv$, but the $\mathfrak{L}_{\rm val}(C)$-theories of $F$ and $F^{\prime}$
differ since the universal statement UR($t$) holds in $F$ but not in
$F^{\prime}$ (take $s$ as above and $r:=\sqrt{t-s^{p}}$).

######  Remark 6.3.

For a valued field $(F,v)$ with $F\supseteq C$ such that
$t\in\mathcal{O}:=\mathcal{O}_{v}$, axiom UR($t$) is equivalent to the
assertion that the element $1\otimes dt\in
Fv\otimes_{\mathcal{O}}\Omega_{\mathcal{O}}$ does not vanish, where
$\Omega_{\mathcal{O}}$ is the $\mathcal{O}$-module of (absolute) Kähler
differentials. Indeed, if UR($t$) fails to hold, there exists $s\in F$ such
that $t-s^{p}$ is in the square of the maximal ideal $\mathfrak{m}$ of
$\mathcal{O}$. It is then easy to show that $1\otimes dt=1\otimes d(t-s^{p})$
vanishes in $Fv\otimes_{\mathcal{O}}\Omega_{\mathcal{O}}$. Assume conversely
that $1\otimes dt\in Fv\otimes_{\mathcal{O}}\Omega_{\mathcal{O}}$ vanishes. We
consider the so-called conormal sequence of $Fv$-modules

$0\to\mathfrak{m}/\mathfrak{m}^{2}\to
Fv\otimes_{\mathcal{O}}\Omega_{\mathcal{O}}\to\Omega_{Fv}\to 0.$

(See [Eis95, Proposition 16.3], and [Eis95, Corollary 16.13] for exactness at
the first place; note that we write $\Omega_{Fv}$ and $\Omega_{\mathcal{O}}$
where Eisenbud would write $\Omega_{Fv/\mathbb{F}_{p}}$ and
$\Omega_{\mathcal{O}/\mathbb{F}_{p}}$.) We see that $dt\in\Omega_{Fv}$ must
vanish, and so $t$ has a $p$-th root in $Fv$. Let $s\in\mathcal{O}$ with
$v(t-s^{p})>0$. We have $dt=d(t-s^{p})$, and so $1\otimes dt$ is the image of
$(t-s^{p})+\mathfrak{m}^{2}$ under the first map in the conormal sequence. By
injectivity, it follows that $t-s^{p}\in\mathfrak{m}^{2}$, so UR($t$) is
violated.

This explains the name $\mathrm{UR}(t)$ (ur for unramified): The assertion is
that there is no ramification witnessed by the differential $dt$. We will need
the following elementary form of this:

######  Lemma 6.4.

Let $K/k$ be a global function field of characteristic $p$, $t\in K$ a
separating element, and $v\in\mathbb{P}_{K}$. Then UR($t$) holds in
$\hat{K}_{v}$ whenever $v$ is not one of the finitely many places ramifying
over the subfield $k(t)$.

###### Proof.

This could be deduced from the characterisation given in Remark 6.3, but we
give a direct argument. Assume that $v$ does not ramify over $k(t)$. If
$v(t)<0$, this implies that $v(t)=-1$, and so for arbitrary $s\in\hat{K}_{v}$
we have $v(t-s^{p})=\min(v(t),v(s^{p}))\leq-1$ since $v(t)\neq v(s^{p})$.
Assume now that $v(t)\geq 0$. The restriction $v|_{k(t)}$ is the place of
$k(t)$ associated to an irreducible polynomial $f\in k[t]$. Since $k[t]/(f)$
is perfect, there exists $g\in k[t]$ such that $f|t-g^{p}$. As the right-hand
side is a separable polynomial, $f^{2}\nmid t-g^{p}$. Since $v$ does not
ramify over $k(t)$, we deduce that $v(t-g^{p})=1$. For arbitrary
$s\in\hat{K}_{v}$, we write $t-s^{p}=(t-g^{p})+(g-s)^{p}$, and observe that
the two summands have different value under $v$, so
$v(t-s^{p})=\min(v(t-g^{p}),v((g-s)^{p}))\leq v(t-g^{p})=1$. This shows that
UR($t$) holds in $\hat{K}_{v}$. ∎

######  Theorem 6.5.

Assume (R4). Let $K/k$ be a global function field of characteristic $p$ and
let $t\in K$ be a separating element.

  1. $(a)$

The universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all
$\hat{K}_{v}$, $v\in\mathbb{P}_{K}$, is the universal/existential theory of
henselian nontrivially valued fields extending the trivially valued field $K$,
satisfying UR($t$), and with residue field pseudofinite.

  2. $(b)$

The universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of all
$\hat{K}_{v}$, $v\in\mathbb{P}_{K}$, is the universal/existential theory of
henselian nontrivially valued fields $(L,w)$ containing $K$ with residue field
finite or pseudofinite such that UR($t$) holds unless $w(z_{u_{i}})>0$ for
some $i=1,\dots,r$, and such that ${\rm Th}_{\forall/\exists}(L,w)={\rm
Th}_{\forall/\exists}(\hat{K}_{v},\hat{v})$ whenever $w(z_{v})>0$ for some
$v\in\mathbb{P}_{K}$, where for each $v\in\mathbb{P}_{K}$, $z_{v}\in K$ is
chosen to have a zero only at $v$, and $u_{1},\dots,u_{r}$ is the list of
places of $K$ which ramify over $k(t)$.

###### Proof.

Let $C=K$. By Lemma 5.2 and Lemma 6.4, any model of the $\mathfrak{L}_{\rm
val}(K)$-theory of almost all $\hat{K}_{v}$ is a model of $T_{4}$. Therefore
the proof of (a) works completely analogous to the proof of Theorem 5.3,
replacing $T_{3}$ by $T_{4}$ and Proposition 5.1 by Proposition 6.1.

Taking (a) into account, part (b) asserts that a field $(L,w)$ satisfies the
universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of all $\hat{K}_{v}$,
$v\in\mathbb{P}_{K}$, if and only if $(L,w)$ either satisfies the
universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of _almost_ all
$\hat{K}_{v}$, or ${\rm Th}_{\forall/\exists}(L,w)={\rm
Th}_{\forall/\exists}(\hat{K}_{v},\hat{v})$ for some $v\in\mathbb{P}_{K}$.
This is true on general grounds. Indeed, suppose that $(L,w)$ does not satisfy
the universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of almost all
$\hat{K}_{v}$, so that $(L,w)\models\neg\varphi$ for some
universal/existential $\mathfrak{L}_{\rm val}(K)$-sentence $\varphi$ which is
true in all $\hat{K}_{v}$ except for finitely many exceptional places
$v_{1},\dotsc,v_{n}$. If $(L,w)$ also does not satisfy the
universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of any individual
$(\hat{K}_{v},\hat{v})$, we in particular have universal/existential
$\mathfrak{L}_{\rm val}(K)$-sentences $\varphi_{1},\dotsc,\varphi_{n}$ such
that $(L,w)\models\neg\varphi_{i}$ but
$(\hat{K}_{v_{i}},\hat{v}_{i})\models\varphi_{i}$ for every $i=1,\dotsc,n$.
Therefore $(L,w)\not\models\varphi\vee\varphi_{1}\vee\dotsb\vee\varphi_{n}$
even though $(\hat{K}_{v},\hat{v})$ satisfies the sentence on the right-hand
side for every $v\in\mathbb{P}_{K}$, and so $(L,w)$ is not a model of the
universal/existential theory of all $(\hat{K}_{v},\hat{v})$. Conversely, if
$(L,w)$ satisfies either the universal/existential $\mathfrak{L}_{\rm
val}(K)$-theory of almost all $\hat{K}_{v}$, or of one individual
$\hat{K}_{v}$, it is clear that $(L,w)$ satisfies the common
universal/existential $\mathfrak{L}_{\rm val}(K)$-theory of all $\hat{K}_{v}$.
∎

######  Corollary 6.6.

Assume (R4). Let $K/k$ be a global function field. The $\mathfrak{L}_{\rm
val}(K)$-theory of almost all $\hat{K}_{v}$ and the $\mathfrak{L}_{\rm
val}(K)$-theory of all $\hat{K}_{v}$ are decidable.

###### Proof.

Fix a separating element $t\in K$ and let $P_{0}\subseteq\mathbb{P}_{K}$ be
the finite set of places that ramify over $k(t)$. Similar to before, the
decidability of the universal/existential $\mathfrak{L}_{\rm val}(K)$-theory
of almost all $\hat{K}_{v}$ follows immediately from Proposition 6.1, Lemma
4.4 and Lemma 2.1(b). In order to decide whether a given universal/existential
$\mathfrak{L}_{\rm val}(K)$-sentence $\varphi$, holds in all $\hat{K}_{v}$
first check whether it holds in almost all of them. If yes, then by Theorem
6.5 and the completeness theorem, there is a proof of $\varphi$ from the set
of axioms for henselian nontrivially valued fields extending the trivially
valued field $C=K$ satisfying UR($t$) and with residue field pseudofinite. As
this set of axioms is computable (see in particular Lemma 4.4), the set of
consequences is computably enumerable, and so by enumerating all proofs from
these axioms, we will eventually find a proof of $\varphi$. Apart from
possibly using UR($t$), which holds in $\hat{K}_{v}$ for all $v\notin P_{0}$
(Lemma 6.4), this proof will involve only finitely many constants from $K$ and
only finitely many axioms of pseudofinite fields, and so we can compute a
finite set $P_{1}\subseteq\mathbb{P}_{K}$ such that
$\hat{K}_{v}\models\varphi$ for every $v\notin P_{0}\cup P_{1}$. To determine
whether $\hat{K}_{v}\models\varphi$ for each of the finitely many $v\in
P_{0}\cup P_{1}$, we use [ADF23, Theorem 4.12], which (again assuming (R4))
gives a uniform decidability of each individual ${\rm
Th}_{\forall/\exists}(\hat{K}_{v},\hat{v})$. ∎

This proves the remaining parts $(e)$ and $(f)$ of Theorem 1.4.

######  Remark 6.7.

All algorithms presented in this paper can in fact be made uniform in the
global function field $K$, similar to Corollary 3.5. For Corollary 6.6, this
could take the following form: There exists an algorithm that takes as input a
prime power $q$, an absolutely irreducible $f\in\mathbb{F}_{q}[t,x]$ (say
separable in $x$) and a universal/existential $\mathfrak{L}_{\rm
val}(\mathbb{F}_{q}[t,x])$-sentence $\varphi$, and determines whether
$\varphi$ holds in all respectively almost all completions of the global
function field $K_{f}={\rm Quot}(\mathbb{F}_{q}[t,x]/(f))$, where the
parameters from $\mathbb{F}_{q}[t,x]$ are interpreted as their residues in
$K_{f}$. To formally prove this, we would have to argue that the decidability
in Lemma 2.1(b) is uniform in $R$, and that all parts of our axiomatisations
for a given $K_{f}$ are computable from $f$, like in Corollary 6.6(b) the
finite list of places of $K_{f}$ which ramify over $\mathbb{F}_{q}(t)$.

######  Remark 6.8.

As indicated in the introduction, Corollary 1.2 about completions of number
fields follows from Theorem 1.1 about completions of $\mathbb{Q}$: Indeed, if
$L=\mathbb{Q}[x]/(f)$ is a number field, then
$\mathbb{Q}_{p}[x]/(f)\cong\mathbb{Q}_{p}\otimes_{\mathbb{Q}}L\cong\prod_{w|p}\hat{L}_{w}$,
where $w$ runs over the finitely many places of $L$ over $p$, cf. [Ser79, II
§3 Theorem 1]. So an $\mathfrak{L}_{\rm ring}$-sentence $\varphi$ holds in all
respectively almost all $\hat{L}_{w}$ if and only if $\varphi_{f}$ holds in
all respectively almost all $\mathbb{Q}_{p}$, where $\varphi_{f}$ is a
sentence expressing that, if $f=f_{1}\cdots f_{r}$ is the decomposition into
irreducible factors, $\varphi$ holds in each of the fields generated by a root
of one of the $f_{i}$. Note however that this does not immediately reduce
Theorem 1.4 to the special case of the rational function field
$K=\mathbb{F}_{p}(t)$, as $\varphi_{f}$ introduces new quantifiers on top of
those of $\varphi$. For existential $\mathfrak{L}_{\rm ring}(K)$-sentences,
this problem can be overcome (see [Dit18, Proposition 2.1.2], and also [ADF20,
§6]), so that at least part (d) of Theorem 1.4 could be deduced from the
special case $K=\mathbb{F}_{p}(t)$, but this is much less clear for parts (c),
(e) and (f) of that theorem.

## Acknowledgements

A. F. would like to thank Sylvy Anscombe for helpful discussions at an early
stage of this project. A. F. was funded by the Deutsche Forschungsgemeinschaft
(DFG) - 404427454.

## References

  * [ADF20] S. Anscombe, P. Dittmann and A. Fehm.  A p-adic analogue of Siegel’s theorem on sums of squares.  Math. Nachrichten 293:1434–1451, 2020
  * [ADF23] S. Anscombe, P. Dittmann and A. Fehm.  Axiomatizing the existential theory of $\mathbb{F}_{q}(\\!(t)\\!)$.  Algebra & Number Theory 17(11):2013–2032, 2023.
  * [AF16] S. Anscombe and A. Fehm.  The existential theory of equicharacteristic henselian valued fields.  Algebra & Number Theory 10(3):665–683, 2016.
  * [AF17] S. Anscombe and A. Fehm.  Characterizing diophantine henselian valuations rings and valuation ideals.  Proc. Lond. Math. Soc. 115:293–322, 2017.
  * [AF23] S. Anscombe and A. Fehm.  Interpretations of syntactic fragments of theories of fields.  arXiv:2312.17616 [math.LO], 2023.
  * [Ax68] J. Ax.  The elementary theory of finite fields.  Annals of Math. 88(2):239–271, 1968.
  * [BLR90] S. Bosch, W. Lütkebohmert and M. Raynaud.  Néron models.  Springer, 1990.
  * [CK90] C. C. Chang and H. J. Keisler.  Model Theory. Third edition. Studies in Logic and the Foundations of Mathematics, 73. North-Holland Publishing Co., Amsterdam, 1990.
  * [DS03] J. Denef and H. Schoutens.  On the decidability of the existential theory of $\mathbb{F}_{p}[[t]]$.  In Valuation theory and its applications, (Saskatoon, 1999), vol. II, edited by F.-V. Kuhlmann et al., Fields Inst. Commun. 33, Amer. Math. Soc., Providence, RI, pp. 43–60, 2003.
  * [Die01] C. Diem.  A study on theoretical and practical aspects of Weil-restrictions of varieties.  Doctoral thesis, Essen, 2001.
  * [Dit18] P. Dittmann.  A model-theoretic approach to the arithmetic of global fields.  Doctoral thesis, Oxford, 2018.
  * [Dit23] P. Dittmann.  Two examples concerning existential undecidability in fields.  Journal of Symbolic Logic, in press, 2023.
  * [Eis95] D. Eisenbud.  Commutative algebra. With a view toward algebraic geometry. Graduate Texts in Mathematics, 150.  Springer-Verlag, New York, 1995.
  * [Eis03] K. Eisenträger.  Hilbert’s tenth problem for algebraic function fields of characteristic 2.  Pacific J. Math. 210(2):261–281, 2003.
  * [EP05] A. Engler and A. Prestel.  Valued Fields.  Springer Monographs in Mathematics.  Springer, 2005.
  * [FJ17] A. Fehm and F. Jahnke.  Recent progress on definability of Henselian valuations. In: F. Broglia, F. Delon, M. Dickmann, D. Gondard, and V. Powers (eds.), Proceedings of the Conference on Ordered Algebraic Structures and Related Topics,  Contemporary Mathematics Volume 697, 2017.
  * [FP15] A. Fehm and A. Prestel.  Uniform definability of henselian valuation rings in the Macintyre language.  Bull. London Math. Soc. 47:693–703, 2015.
  * [FJ08] M. D. Fried and M. Jarden.  Field arithmetic.  3rd edition, Springer, 2008.
  * [Kar23] K. Kartas.  An undecidability result for the asymptotic theory of p-adic fields.  Ann. Pure Appl. Logic 174(2), paper no. 103203, 2023.
  * [Koe14] J. Koenigsmann.  Undecidability in Number Theory.  In: L. van den Dries et al. (eds.), Model Theory in Algebra, Analysis and Arithmetic, Springer, 2014.
  * [Phe91] T. Pheidas.  Hilbert’s tenth problem for fields of rational functions over finite fields.  Invent. Math. 103:1–8, 1991.
  * [Poo03] B. Poonen.  Hilbert’s tenth problem over rings of number theoretic interest.  Lecture Notes, available at http://www-math.mit.edu/~poonen/papers/aws2003.pdf, 2003.
  * [Sch94] C. Scheiderer.  Real and Étale Cohomology.  Springer, 1994.
  * [Ser79] J.-P. Serre.  Local Fields.  Springer, 1979.
  * [Shl92] A. Shlapentokh.  Hilbert’s tenth problem for rings of algebraic functions in one variable over fields of constants of positive characteristic.  Trans. Amer. Math. Soc. 333(1):275–298, 1992.
  * [Sti09] H. Stichtenoth.  Algebraic Function Fields and Codes.  Second edition. Springer, 2009.
  * [Tar48] A. Tarski.  A decision method for elementary algebra and geometry (prepared for publication by J. C. C. McKinsey),  U.S. Air Force Project RAND, R-109, the RAND Corporation, Santa Monica, California, 1948.
  * [Vid94] C. R. Videla.  Hilbert’s tenth problem for rational function fields in characteristic 2.  Proc. Amer. Math. Soc. 120(1):249–253, 1994.