%%% %===================================================================================================
%%% % $Id: exdivlemma.tex,v 1.44 2004/06/02 09:31:05 jdemeyer Exp $
%%% %===================================================================================================
%%% 
%%% %include(latex.m4)
\documentclass[12pt,english]{article}
\newcommand{\Author}{Jeroen Demeyer\thanks{The first author is a Research 
Assistant of the Fund for Scientific Research - Flanders (Belgium) (F.W.O.-Vlaanderen).}
\and Jan Van Geel\thanks{Work partially supported by the European Community's 
Human Potential Programme under contract HPRN-CT-2002-00287.}}
\newcommand{\Title}{An Existential Divisibility Lemma for Global Fields}
%\input{header.tex}
%===================================================================================================
% $Id: header.tex,v 1.9 2004/05/12 14:03:40 jdemeyer Exp $
%===================================================================================================

\usepackage[margin=25mm]{geometry}
\usepackage{babel,ifthen}
\usepackage{enumerate}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{color}
\ifx\pdfoutput\undefined
	\newcommand{\ifpdf}[2]{#2}
\else
	\newcommand{\ifpdf}[2]{#1}
\fi
\ifpdf
{
	% pdflatex
	\usepackage[pdftex]{graphics}
	\usepackage[pdftex,pdfstartview={FitH},bookmarks]{hyperref}
	\pdfcompresslevel=0
}
{
	% latex
	\usepackage{graphics}
}
%---------------------------------------------------------------------------------------------------

\newcommand{\twodigit}[1]{\ifthenelse{#1 < 10}{0#1}{#1}}
\newcommand{\Date}{\number\year--\twodigit{\number\month}--\twodigit{\number\day}}
\author{\Author}
\title{\Title}
\date{\Date}
%---------------------------------------------------------------------------------------------------

%% \iflanguage{dutch}{
%% 	\newcommand{\theoremname}{Stelling}
%% 	\newcommand{\propname}{Propositie}
%% 	\newcommand{\lemmaname}{Lemma}
%% 	\newcommand{\corname}{Gevolg}
%% 	\newcommand{\claimname}{Bewering}
%% 	\newcommand{\definename}{Definitie}
%% 	\newcommand{\examplename}{Voorbeeld}
%% 	\newcommand{\exercisename}{Oefening}
%% 	\newcommand{\factname}{Feit}
%% 	\newcommand{\factsname}{Feiten}
%% 	\newcommand{\remarkname}{Opmerking}
%% 	\newcommand{\solutionname}{Oplossing}
%% 	\newcommand{\stepname}{Stap}
%% 	\newcommand{\casename}{Geval}
%% }{}

\providecommand{\theoremname}{Theorem}
\providecommand{\propname}{Proposition}
\providecommand{\lemmaname}{Lemma}
\providecommand{\corname}{Corollary}
\providecommand{\claimname}{Claim}
\providecommand{\definename}{Definition}
\providecommand{\examplename}{Example}
\providecommand{\exercisename}{Exercise}
\providecommand{\factname}{Fact}
\providecommand{\factsname}{Facts}
\providecommand{\remarkname}{Remark}
\providecommand{\solutionname}{Solution}
\providecommand{\stepname}{Step}
\providecommand{\casename}{Case}
%---------------------------------------------------------------------------------------------------

\theoremstyle{plain}
\ifx\chaptername\undefined
	\newtheorem{theorem}{\theoremname}
\else
	\newtheorem{theorem}{\theoremname}[chapter]
\fi
\newtheorem{prop}[theorem]{\propname}
\newtheorem{lemma}[theorem]{\lemmaname}
\newtheorem{cor}[theorem]{\corname}
\newtheorem*{claim}{\claimname}

\theoremstyle{definition}
\newtheorem{define}[theorem]{\definename}
\newtheorem*{define*}{\definename}
\newtheorem{example}[theorem]{\examplename}
\newtheorem*{example*}{\examplename}
\newtheorem{exercise}[theorem]{\exercisename}
\newtheorem*{exercise*}{\exercisename}
\newtheorem{fact}[theorem]{\factname}
\newtheorem*{fact*}{\factname}
\newtheorem{facts}[theorem]{\factsname}
\newtheorem*{facts*}{\factsname}

\theoremstyle{remark}
\newtheorem*{remark}{\remarkname}
\newtheorem*{solution}{\solutionname}

\newenvironment{steplist}
	{\begin{list}{\textbf{{\stepname} \arabic{step}:}}
		{
			\usecounter{step}
			\setlength{\labelwidth}{0ex}
			\setlength{\itemindent}{\labelsep}
			\setlength{\leftmargin}{0ex}
		}}
	{\end{list}}
\newcounter{step}

\newenvironment{caselist}
	{\begin{list}{}
		{
			\setlength{\labelwidth}{\textwidth}
			\setlength{\itemindent}{\textwidth}
			\setlength{\labelsep}{0ex}
			\setlength{\leftmargin}{0ex}
			\renewcommand{\makelabel}[1]{\stepcounter{case}\textbf{{\casename} \arabic{case}:} ##1\hfill\rule[-0.8em]{0ex}{0ex}}
		}}
	{\end{list}}
\newcounter{case}
%---------------------------------------------------------------------------------------------------

\newcommand{\inv}{^{-1}}
\newcommand{\iinv}{^{-2}}
\newcommand{\dif}{\mathrm{d}}
\newcommand{\mi}{\mathrm{i}}
\newcommand{\G}{\Gamma}
\newcommand{\Gb}{\Gamma\!}
\newcommand{\eps}{\varepsilon}
\newcommand{\fraka}{\mathfrak{a}}
\newcommand{\frakA}{\mathfrak{A}}
\newcommand{\frakc}{\mathfrak{c}}
\newcommand{\frakC}{\mathfrak{C}}
\newcommand{\frakd}{\mathfrak{d}}
\newcommand{\frakD}{\mathfrak{D}}
\newcommand{\frakm}{\mathfrak{m}}
\newcommand{\frakp}{\mathfrak{p}}
\newcommand{\frakP}{\mathfrak{P}}
\newcommand{\frakq}{\mathfrak{q}}
\newcommand{\frakQ}{\mathfrak{Q}}
\newcommand{\frakr}{\mathfrak{r}}
\newcommand{\frakR}{\mathfrak{R}}
\newcommand{\fraks}{\mathfrak{s}}
\newcommand{\frakS}{\mathfrak{S}}
\newcommand{\frakt}{\mathfrak{t}}
\newcommand{\frakT}{\mathfrak{T}}
\newcommand{\valp}{{v_\frakp}}
\newcommand{\valP}{{v_\frakP}}
\newcommand{\valq}{{v_\frakq}}
\newcommand{\valQ}{{v_\frakQ}}
\newcommand{\valr}{{v_\frakr}}
\newcommand{\valR}{{v_\frakR}}
\newcommand{\vals}{{v_\fraks}}
\newcommand{\valS}{{v_\frakS}}
\newcommand{\valt}{{v_\frakt}}
\newcommand{\valT}{{v_\frakT}}
\newcommand{\maxp}{{\frakm_\frakp}}
\newcommand{\maxq}{{\frakm_\frakq}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\calO}{\mathcal{O}}

\renewcommand{\div}{\,/\,}
\newcommand{\sqq}{\sqrt{q}{\hspace{0.1em}}}

\newcommand{\AS}[2][void]{\ifthenelse{\equal{#1}{void}}{\mathbb{A}\!^{#2}}{\mathbb{A}\!^{#2}(#1)}}
\newcommand{\PS}[2][void]{\ifthenelse{\equal{#1}{void}}{\mathbb{P}^{#2}}{\mathbb{P}^{#2}(#1)}}
\newcommand{\zeros}[1]{\mathrm{Z}(#1)}
\newcommand{\ideal}[1]{\mathrm{I}(#1)}
\newcommand{\FF}[1]{\mathbb{F}_{#1}}
\newcommand{\T}[1]{\mathrm{T}\!_{#1}}
\newcommand{\GF}{\mathrm{GF}}
\newcommand{\AG}{\mathrm{AG}}
\newcommand{\PG}{\mathrm{PG}}

\renewcommand{\vec}{\overrightarrow}
\DeclareMathOperator{\newker}{Ker}
\renewcommand{\ker}{\newker}
\DeclareMathOperator{\im}{Im}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\spn}{span}
\DeclareMathOperator{\rng}{rang}
\DeclareMathOperator{\kar}{kar}
\DeclareMathOperator{\fchar}{char}
\DeclareMathOperator{\sgn}{sign}
\DeclareMathOperator{\aut}{Aut}
\DeclareMathOperator{\gal}{Gal}
\DeclareMathOperator{\ggd}{ggd}
\DeclareMathOperator{\prob}{Prob}
\DeclareMathOperator{\norm}{N}
\DeclareMathOperator{\tr}{Tr}
\DeclareMathOperator{\Br}{Br}
\DeclareMathOperator{\invar}{inv}

\newcommand{\smth}{_\text{glad}}
\newcommand{\sing}{_\text{sing}}
\newcommand{\oneone}{\mbox{$1\!\leftrightarrow\!1$}}
\newcommand{\UFD}{unieke-factorisatiedomein}
\newcommand{\HID}{hoofdideaaldomein}

\newcommand{\set}[2]{\{{#1}\mid{#2}\}}
\newcommand{\quotient}[2]{\raisebox{-1ex}{\raisebox{1ex}{$#1$}\hspace{-0.6ex}\Big/\hspace{-0.6ex}\raisebox{-1ex}{$#2$}}}
\newcommand{\quotientZ}[1]{\quotient{\mathbb{Z}}{#1 \mathbb{Z}}}
\newcommand{\floor}[1]{\left\lfloor\!{#1}\!\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil\!{#1}\!\right\rceil}
\newcommand{\form}[1]{\langle{#1}\rangle}
\newcommand{\absvoid}{|\hspace{1ex}|}
%---------------------------------------------------------------------------------------------------

\setlength{\parindent}{0em}
\setlength{\parskip}{1.0em plus 0.4em minus 0.2em}
%===================================================================================================

\newcommand{\ED}{existential divisibility lemma}
\newcommand{\twoc}{\sideset{_2}{}}
\newcommand{\As}{A_\mathrm{s}}
\newcommand{\An}{A_\mathrm{ns}}
%===================================================================================================

\begin{document}
%###################################################################################################

\maketitle
%===================================================================================================

\section{Introduction}
%===================================================================================================

In \cite{pheidas12} Thanases Pheidas proves, what he calls, existential divisibility lemmas
for $K = \FF{q}(z)$ where $q$ is a prime congruent to $3\bmod 4$ and for $K=\Q$.
Let $R$ be the set of primes $p$ in $\Z$, respectively in $\FF{q}[t]$,
such that $-1$ is not a square in the residue field of $p$.
The existential divisibility lemmas state the existence of an existential formula $\phi(x,y)$
such that:
\emph{if $\phi(x,y)$ holds for $x,y\in K\setminus\{0\}$
then for all primes $p\in R$ for which $v_p(x)$ is odd it follows that $v_p(xy^{-2})>0$.}

Actually putting extra local conditions on the elements $x$
(conditions in the point at infinity in the function field case
and in the real prime and the prime 2 in case $K=\Q$)
the truth of $\phi(x,y)$ for $x,y\in K^*$ is equivalent to the statement:
\emph{for all primes $p\in R$ for which $v_p(x)$ is odd it follows that $v_p(xy^{-2})>0$}.

The formula $\phi(x,y)$ expresses ``almost'' that
\emph{all poles of $x$ in $R$, with odd multiplicity, are poles of $y$}.

These {\ED}s play a role in strategies to obtain
undecidability results for the existential theory of the field $K$.
In \cite{pheidas5} Pheidas proved that the existential theory of $\FF{p^{n}}(t)$ is undecidable.
His proof worked for all odd primes $p$.
Videla (\cite{videla-ff2}) extended this result to rational global function fields of characteristic 2.
Shlapentokh (\cite{shlapentokh-ffff}) showed that the existential theory
of global function fields of characteristic not 2 is undecidable
and finally in her thesis (\cite{eisentraeger-thesis}) Kirsten Eisentr\"ager completed the results
by proving the same result for global function fields in characteristic 2.
This is essentially the (negative) solution of Hilbert's 10th problem for global function fields.

One of the main open questions directly related to Hilbert's 10th problem
is whether or not the existential theory of $\Q$ (or more general of any number field)
is decidable or undecidable.
In \cite{pheidas12} a program to come to a uniform way to attack Hilbert's 10th problem
for global fields is described.
This program generates a series of ``possible facts'' (cf.\ \cite[sections 3 and 4]{pheidas12}),
two of which are related to the {\ED}
and one of them is forced into the strategy
by the fact that the existential divisibility lemma as proved by Pheidas
uses the set of primes $p$ for which $-1$ is not a square in the residue field of $p$.

In view of this Thanases Pheidas and Gunther Cornelissen
raised the question to what extent the existential divisibility lemma holds.
\emph{For which sets of primes does it hold}?
\emph{Why does the condition in the prime 2 occur}?
\emph{Can the lemma be generalized to all global fields}?

Together with Karim Zahidi the second author
worked out a more general version of the existential divisibility lemma.
Namely for $K=\Q$ and for a set of primes that are inert in a quadratic extension of $\Q$.
This result was presented
at the Oberwolfach meeting on Hilbert's 10th problem in January 2003 (cf.\ \cite{oberw-vgeel-zahidi}).

In this paper we generalize the {\ED}
to all global fields $K$ (of characteristic not 2),
and for all sets of primes that are inert in a quadratic extension $L$ of $K$.
We first prove the direct generalisation of Pheidas' existential divisibility lemma,
with conditions in the real primes and in the primes ramifying in $L$.
In the last section we remove all these conditions and prove:

\emph{Let $K$ be a global field
and $R(L/K)$ be the set of primes which are inert in a quadratic extension $L$ of $K$.
Then there is an existential formula $\Omega(x,y)$ which is equivalent with the formula
$$
	\forall \frakr \in R(L/K):
		\left(\valr(x) \text{ odd } \rightarrow \valr(xy\iinv) > 0\right)
$$}
%---------------------------------------------------------------------------------------------------

\section{Preliminaries}
%===================================================================================================

Our discussion of the {\ED} relies on facts about norms and norm groups
of quadratic extensions of local and global fields.
We use the Hasse--Minkowski local--global principle and Hilbert's reciprocity law.
In this section we give a survey of these facts,
for more details and proofs we refer to the literature (e.g.\ \cite{omeara-introqf}).

We start fixing terminology and notation.
Throughout the paper $K$ will be a global field of characteristic not 2,
so it is either a number field
or the function field of a curve over a finite field $\FF{q}$ with $q$ odd.
$L$ will be a quadratic extension of $K$.

With $M_K$ we denote the set of all ``primes'' $\frakp$ of $K$.
In the number field case the \emph{finite} or \emph{non-archimedean} primes
correspond (one to one) to (equivalence classes of) discrete valuations of $K$
and the \emph{infinite} or \emph{archimedean} primes
correspond (one to one) to the different embeddings of $K$ in the complex numbers.
In the function field case all the elements of $M_K$
correspond (one to one) to (equivalence classes of) discrete valuations on $K$.
With every element of $M_K$ there corresponds a normalized absolute value $\absvoid_\frakp$ on $K$,
we let $K_\frakp$ denote the completion of $K$ with respect to this absolute value.

If $\frakp$ is a non-archimedean prime, then $K_{\frakp}$
is the fraction field of a complete discrete valuation ring $\calO_{\frakp}$
and its maximal ideal is a principal ideal.
A generator for this ideal is called a uniformizing element.
We can choose such a uniformizing element in the base field $K$ and denote it with $\pi_\frakp$.
The quotient ring $\calO_\frakp/(\pi_\frakp)$ is a finite field $\FF{\frakp}$,
the residue field of the prime $\frakp$.
The discrete valuation associated with a non-archimedean prime $\frakp$
will be denoted with $\valp$
and we normalize it by $v_\frakp(\pi_{\frakp})=1$.
We use the analogous terminology and notation for primes $\frakP\in M_L$.

All absolute values $\absvoid_\frakp$ extend to the quadratic extension $L/K$
in different ways, depending on the prime $\frakp$.
The possible extensions correspond
to what is called the \emph{splitting behavior} of the prime $\frakp$ in $L$.
For a quadratic extension we have the following possibilities
(in the number field case we distinguish between non-archimedean and archimedean primes,
in the function field case points \ref{split:As} and \ref{split:An} are empty):

\begin{enumerate}
\item\label{split:P} $\frakp$ is a non-archimedean prime and
$L\otimes_{K} K_{\frakp} \cong K_{\frakp}\times K_{\frakp}$.
In this case there are two primes $\frakP_{1}, \frakP_{2}$ in $M_{L}$ lying over $\frakp$,
$L_{\frakP_{1}} \cong L_{\frakP_{2}} \cong K_{\frakp}$ and
$\FF{\frakP_{1}} \cong \FF{\frakP_{2}}\cong \FF{\frakp}$.
We say that the prime $\frakp$ is \emph{completely split} in $L$.

\item\label{split:R} $\frakr$ is a non-archimedean prime and $L\otimes_{K}K_{\frakr}$
is a quadratic field extension $L_{\frakR}$ over $K_{\frakr}$ and
$[\FF{\frakR}:\FF{\frakr}]=2$.
In this case there is only one prime $\frakR$ in $L$ lying over $\frakr$,
the uniformizing element $\pi_{\frakr}$ of $\calO_{\frakr}$
is also a uniformizing element of $\calO_{\frakR}$.
The prime $\frakr$ is said to be \emph{inert} in $L$.

\item\label{split:S} $\fraks$ is a non-archimedean prime and $L\otimes_{K} K_{\fraks}$
is a quadratic field extension $L_{\frakS}$ over $K_{\fraks}$ and $[\FF{\frakS}:\FF{\fraks}]=1$.
Here we also have a unique prime $\frakS$ in $L$ lying over $\fraks$,
but the uniformizing element $\pi_{\fraks}$ of $\calO_{\fraks}$
is not a uniformizing element of $\calO_{\frakS}$.
We have $\pi_{\frakS}^{2} = w\pi_{\fraks}$ with $w$ a unit in $\calO_{\frakS}$.
The prime $\fraks$ is said to \emph{ramify} in $L$.

\item\label{split:As} $\fraka$ is an archimedean prime and
$L\otimes K_{\fraka} \cong K_{\fraka}\times K_{\fraka}$,
the archimedean prime $\fraka$ is said to \emph{split} in $L$.

\item\label{split:An} $\frakc$ is an archimedean prime and $L\otimes_K K_{\frakc}$
is quadratic extension $L_{\frakC}$ of $K_{\frakc}$.
Note that this case can only occur if $K_{\frakc} \cong \R$
and we have $L_{\frakC}\cong \C$, the archimedean prime $\frakc$ \emph{does not split} in $L$.
\end{enumerate}
%---------------------------------------------------------------------------------------------------

We can now partition the set of primes $M_K$
according to the splitting behavior in the quadratic extension $L$:
\begin{align*}
	P(L/K) &= \set{\frakp\in M_K}{\frakp \text{ is a non-archimedean prime, completely split in } L} \\
	R(L/K) &= \set{\frakr \in M_K}{\frakr \text{ is a non-archimedean prime, inert in } L} \\
	S(L/K) &= \set{\fraks \in M_K}{\fraks \text{ is a non-archimedean prime, ramified in } L} \\
	\As(L/K) &= \set{\fraka\in M_K}{\fraka \text{ is an archimedean prime, split in } L} \\
	\An(L/K) &= \set{\frakc\in M_K}{\frakc \text{ is an archimedean prime, not split in } L} \\
\end{align*}

In the number field case we sometimes need to refer
to all archimedean primes therefore we define $A(L/K) = \As(L/K) \cup \An(L/K)$.
In the function field case the sets $A(L/K)$, $\As(L/K)$ and $\An(L/K)$ are empty.

The sets $S(L/K)$, $\As(L/K)$ and $\An(L/K)$ are finite.
The sets $P(L/K)$ and $R(L/K)$ are not empty,
Chebotarev's density theorem yields that these sets
are infinite and both have density $\frac{1}{2}$.
(An other consequence of Chebotarev's theorem states that the set of primes $P(L/K)$
that split completely determine uniquely the (Galois) extension $L/K$.)


The strong approximation theorem~\cite[page 204]{neukirch-az} implies

\begin{prop}\label{app1}
Let $T$ be a finite set of primes in $K$ such that $A(L/K) \subset T$.
Let $a_\frakt \in K$ for $\frakt\in T$.
Choose a prime $\frakp_{0}$ not in $T$.
Then for all $\eps > 0$ there exists an element $x\in K$ such that 
$$ |x - a_\frakt|_{\frakt} < \eps \text{ for all } \frakt\in T \text{ and }
	|x|_\frakq \leq 1 \text{ for all } \frakq \in M_{K}\setminus (T\cup\{\frakp_{0}\}) $$
\end{prop}

As an immediate consequence of this one has

\begin{cor}\label{app2}
Let $T$, $\frakp_{0} \not\in T$ and  $a_\frakt\in K$ be as in the preceding proposition.
Then there exists an element $a\in K$ such that
\begin{align*}
	\valt(a) &= \valt(a_{\frakt}) \text{ for all } \frakt \in T \setminus A(L/K) \\
	\sgn(a) &= \sgn(a_{\frakt}) \text{ for all } 
		\frakt \text{ with } K_{\frakt} \cong \R \\
	\intertext{and}
	\valq(a) &\geq 0 \text{ for all } \frakq \in M_K \setminus(T \cup \{\frakp_{0}\})
\end{align*}
\end{cor}  

Let $\sigma \in \gal(L/K)$ be the non-trivial automorphism of $L$ fixing $K$.
The norm map $\norm_{L/K}:L^{*}\to K^{*}; z\mapsto z\sigma(z)$
defines a quadratic form on the two dimensional vector space $L$ over $K$.
If $L = K(\alpha)$ then we can write this form as
$x^2 + \tr_{L/K}(\alpha)xy + \norm_{L/K}(\alpha)y^2$
with respect to the basis $\{1,\alpha\}$ for $L$ over $K$.
Here $\tr_{L/K}(z) = z + \sigma(z)$ stands for the trace map.

\begin{facts*}
We will denote this quadratic form with $N$
and we have the following facts (cf.\ \cite{omeara-introqf} and \cite{scharlau-qhf}):

\begin{enumerate}
\item For all $\frakp \in P(L/K)$ the quadratic form $N$
has a non-trivial zero over $K_{\frakp}$,
it follows from this that every element of $K_{\frakp}$ is represented by $N$.

\item For all $\frakr \in R(L/K)$ the norm form $N$
has no non-trivial zero over $K_{\frakr}$.
The elements of $K_\frakr$ represented by $N$
are exactly the norms of the extension $L_{\frakR}/K_{\frakr}$,
where $\frakR$ is the unique prime in $L$ lying over $\frakr$.
The norm map $\norm_{L_{\frakR}/K_{\frakr}}$
is surjective on units $\mathcal{U}_\frakr$ in $\calO_\frakr$
and the uniformizing element $\pi_{\frakr}$ is not a norm.
It follows that an element $x\in K_{\frakr}$ is a norm
if and only if its valuation $v_{\frakr}(x)$ is even
(we recall that $v_{\frakr}$ is the discrete valuation associated to $\frakr$
and normalized by $v_{\frakr}(\pi_{\frakr})=1$).

\item For all $\fraks \in S(L/K)$ the norm form $N$
has no non-trivial zero over $K_{\fraks}$.
Again the elements represented by $N$
are the norms of the extension $L_{\frakS}/K_{\fraks}$,
where $\frakS$ is the unique prime in $L$ lying over $\fraks$.
The image $\norm_{L_{\frakS}/K_{\fraks}}(\mathcal{U}_{\frakS})$
of the group of units in $\calO_{\frakS}$ is a subgroup of index 2
in the group $\mathcal{U}_{\fraks}$ of units in $\calO_{\fraks}$.
It follows that $\norm_{L_{\frakS}/K_{\fraks}}(L_{\frakS})$
is a subgroup of index 2 in $K_{\fraks}$,
since $\norm_{L_{\frakS}/K_{\fraks}}(\pi_{\frakS})=u\pi_{\fraks}$
for some unit $u$ in $\calO_{\fraks}$.

\item For primes $\fraka \in \As(L/K)$
we have the same as completely split primes,
namely that every element of $K_\fraka$ is represented by $N$.

\item If $\frakc\in \An(L/K)$, the norm form $N$
has no non-trivial zero over $K_{\frakc}$.
The elements represented by $N$
are the norms of the extension $L_{\frakC}=\C$ over $K_{\frakp}=\R$.
So these are the elements represented as sums of 2 squares in $\R$,
which are exactly the positive elements in $\R$.
\end{enumerate}
\end{facts*}
%---------------------------------------------------------------------------------------------------

For inert primes $\frakr\in R(L/K)$ we need slightly more
than the fact that the norms in $K_{\frakr}$ are the elements of even valuation.

\begin{lemma}\label{normval}
Let $\frakr \in R(L/K)$ be an inert prime and $\frakR$
the unique prime in $L$ lying over $\frakr$.
Let $\alpha \in \calO_{\frakR}$ be such that
$\calO_{\frakR}/(\pi_\frakR) = \FF{\frakR}
	= \FF{\frakr}[\overline{\alpha}] = \big(\calO_{\frakr}/(\pi_\frakr)\big)[\overline{\alpha}]$,
with $\overline{\alpha}$ the reduction of $\alpha \bmod \frakR$.
Then
$$ \valr(\norm_{L_{\frakR}/K_{\frakr}}\big(x + y\alpha)\big)
	= \min(v_\frakr(x^2), v_\frakr(y^2)) $$
for $x,y \in K_{\frakr}$.
\end{lemma}

\begin{proof}
Because $\frakr$ is inert, we may replace $\valr$ with $\valR$ in the statement.

Note that $\sigma \in \gal(L/K)$ extends to a 
generator of  $\gal(L_{\frakR}/K_{\frakr})$, so 
$$ \valR\big(\norm_{L_\frakR/K_\frakr}(x + y\alpha)\big)
	= \valR\big((x + y\alpha)(x + y\sigma(\alpha))\big) = 2 \valR(x + y\alpha) $$
It remains to prove that $\valR(x + y\alpha) = \min(\valR(x), \valR(y))$.

The hypotheses imply that $v_{\frakr}(\alpha)=0$,
since $\overline{\alpha}$ is non-zero in $\FF{\frakR}$.
If $v_{\frakr}(x) \neq v_{\frakr}(y)$,
the properties of discrete valuations immediatly give us
$\valR(x + y\alpha) = \min(\valR(x), \valR(y))$.

Now suppose $\valR(x) = \valR(y) = m$ for a certain integer $m$.
Then we have $x = \pi_\frakr^m x_0$ and $y = \pi_\frakr^m y_0$,
with $x_0$ and $y_0$ elements of $\calO_{\frakr}$ having valuation $0$.

Since $\{1, \overline{\alpha}\}$ is a basis for $\FF{\frakR}$ over $\FF{\frakr}$,
we have that $\overline{x_0 + y_0\alpha} = \overline{x_0} + \overline{y_0}\,\overline{\alpha}$
is a non-zero element of $\FF{\frakR}$, so $\valR(x_0 + y_0\alpha) = 0$.
Hence
$\valR(x + y\alpha) = \valR\big(\pi_{\frakr}^{m}(x_0 + y_0\alpha)\big)
	= m = \min(\valR(x), \valR(y))$.
\end{proof}
%---------------------------------------------------------------------------------------------------

Information on the global norm group $\norm_{L/K}(L^*)\subset K^*$
can be obtained from Hilbert's reciprocity law
as expressed by the exact sequence (cf.\ \cite{reiner-maxord} and \cite{omeara-introqf})
\begin{equation}\label{recip}
	0 \to \twoc\Br(K) \to \bigoplus_{\frakp\in M_{K}} \twoc\Br(K_{\frakp})
	\overset{\sum \invar_{\frakp}}{\to} \mathbb{Z}/2\mathbb{Z} \to 0
\end{equation}
Here $\twoc\Br(F)$ denotes the two component (the elements of exponent two)
of the Brauer group of the field $F$.
The elements of the Brauer group of $F$ are classes of central simple algebras over $F$,
the group law is induced by the tensor product of algebras.
In the case of local and global fields (of characteristic not 2)
the (non-trivial) elements of the two component
of the Brauer group are given by quaternion division algebras,
which in turn can be represented by symbols $(a,b)$ with $a,b$ non-zero elements of the field.
The symbol $(a,b)$ corresponds to the quaternion algebra with basis $\{1,i,j,k\}$ satisfying
$i^2=a, j^2=b, ij=-ji=k=ab$.
If one is not familiar with the theory of Brauer groups,
it is enough to know that the subgroups of elements of exponent 2
are generated multiplicatively by these symbols
modulo the following relations (cf.\ \cite{scharlau-qhf})

\begin{itemize}
\item $(ab,c) = (a,c)(b,c)$ and $(a,bc)=(a,b)(a,c)$
\item for all $a \not= 0,1$; $(a,1-a) = 1$.
\end{itemize}

\begin{remark}
This is true for the two component
of the Brauer group of any field (of characteristic not equal to 2) 
by a theorem of Merkuriev.
For local and global fields one has moreover that the product of symbols 
is equal to a symbol,
this fact does not hold in general.
\end{remark}

The following facts are important for us:
\begin{prop}[{\cite[section 31]{reiner-maxord}}] \label{localbrauer}
Over a local field $K_{\frakp}$
there exists a unique quaternion division algebra $\mathbb{H}_{\frakp}$,
so $\twoc\Br(K_{\frakp})\cong \Z/2\Z$.

This element $\mathbb{H}_{\frakp}$
is split over any quadratic extension $E$ of $K_{\frakp}$,
i.e., $\mathbb{H}_{\frakp}\otimes_{K_{\frakp}} E$ is a full matrix algebra over $K_{\frakp}$
and is therefore trivial in $\Br(K_{\frakp})$.
\end{prop}

In the exact sequence \eqref{recip} presenting Hilbert's reciprocity law
the maps $\invar_{\frakp}: \twoc\Br(K_{\frakp})\to \Z/2\Z$ are defined by
$\invar_{\frakp}(\mathbb{H}_{\frakp})=1\in \Z/2\Z$, proposition~\ref{localbrauer}
says that $\invar_{\frakp}$ is an isomorphism.

\begin{prop}[{\cite[Theorem 30.4]{reiner-maxord}}] \label{brauernorm}
Let $F$ be a field, $\fchar(F) \not= 2$.
A quaternion division algebra $\mathbb{H}$ over $F$
is represented by a symbol of the form $(a,b)$ with $a\in F^{*}\setminus F^{*2}$
if and only if $\mathbb{H} \otimes F(\sqrt{a})$ is trivial in $\twoc\Br(F)$.
If $a\in F^{*}\setminus F^{*2}$ then a symbol $(a,b)$ is trivial in $\twoc\Br(F)$
if and only if $b \in \norm_{F(\sqrt{a})/F}(F(\sqrt{a})^{*})$.
\end{prop}

The second part of this proposition together with Hilbert's reciprocity law
yield the Hasse norm theorem for quadratic extensions $L/K$.
This theorem states that an element in $K$ is a norm of an element in $L$
if and only if it is a norm locally everywhere.
More generally the following holds for quadratic forms over global fields:

\begin{theorem}[Hasse--Minkowski, \cite{scharlau-qhf}] \label{hassemink}
A quadratic form $Q$ over a global field $K$ has a non-trivial zero in $K$
if and only if it has a non-trivial zero in $K_{\frakp}$ for all $\frakp\in M_{K}$.

An element $x$ in a global field $K$
is represented by a quadratic form $Q$ over $K$
if and only if $x$ is represented by $Q$ over $K_{\frakp}$ for all $\frakp\in M_{K}$.
\end{theorem}
%---------------------------------------------------------------------------------------------------

Let $\twoc\Br(L/K)$ be the kernel of the natural group morphism $\twoc\Br(K)\to \twoc\Br(L)$.
Clearly for any element $\omega$ in this kernel we have
$\invar_{\mathfrak{p}}(\omega)\equiv 0\bmod 2$ for $\mathfrak{p}\in P(L/K)\cup A_{s}(L/K)$.
Hilbert's reciprocity law together with the approximation theorem
allows us to give different parameterizations of the finite subgroups of $\twoc\Br(L/K)$.
We will use this in section~\ref{remcond}.

Let $Q$ be a finite set of primes satisfying 
$$ S(L/K) \cup \An(L/K) \subseteq Q \subseteq R(L/K) \cup S(L/K) \cup \An(L/K) $$
Denote with ${\twoc\Br}^{Q}(L/K)$ the subgroup of $\twoc\Br(L/K)$ defined by
$$ {\twoc\Br}^{Q}(L/K) = \set{\omega\in \twoc\Br(L/K)}
	{\invar_{\mathfrak{l}}(\omega) \equiv 0 \bmod 2
		\text{ for all } \mathfrak{l} \in M_K \setminus Q} $$
Hilbert's reciprocity law gives a one-to-one correspondence
between $\twoc\Br^{Q}(L/K)$ and the set $\{Q_0 \subseteq Q|\#Q_0 \text{ even}\}$.
This correspondence is given by 
$$ \omega \mapsto Q_\omega =
	\set{\frakq \in M_K}{\invar_\frakq \omega \equiv 1 \bmod 2} $$
The latter is a subset of $Q$ by the definition of $\twoc\Br^{Q}(L/K)$.

Let $T$ be a finite subset of primes in $R(L/K)\setminus Q$,
and fix a $\Delta \in K^*$ for which $L = K(\sqrt\Delta)$.
Take an $\omega \in \twoc\Br^{Q}(L/K)$,
then $\omega$ is of the form $(\Delta, \lambda)$ with $\lambda \in K^*$.
We claim that we may choose $\lambda$
such that $\valr(\lambda) \geq 0$ for all $\frakr \in R(L/K)$
and $\valt(\lambda) = 0$ for all $\frakt \in T$.
To see this, we note that for  $\mathfrak{t}\in T$ we have 
$\invar_{\mathfrak{t}}(\omega)\equiv 0\bmod 2$,
so $\lambda$ is a norm of $L_\frakT/K_\frakt$
and $\valt(\lambda)$ is even.
Now we apply the approximation theorem (corollary~\ref{app2})
with $\mathfrak{p}_{0}\in P(L/K)$ to find an element $c\in K^{*}$ such that
\begin{align*}
	\valr(c) &\geq -\frac{\valr(\lambda)}{2} \qquad \text{ for all } \frakr \in R(L/K) \\
	\valt(c) &= -\frac{\valt(\lambda)}{2} \qquad \text{ for all } \frakt \in T
\end{align*}
Since $\omega = (\Delta, \lambda) = (\Delta, c^2\lambda)$,
we may replace $\lambda$ by $c^2\lambda$ to obtain the desired conditions.

By choosing one such $\lambda$ for every $\omega\in \twoc\Br^{Q}(L/K)$,
we obtain a set $\Lambda_{Q,T}(L/K)$ parametrizing the elements of $\twoc\Br^{Q}(L/K)$, we have:
\begin{lemma}\label{parset}
Let $Q,T$ and $\Lambda_{Q,T} = \Lambda_{Q,T}(L/K)$ be as above.

There is a one-to-one correspondence between $\Lambda_{Q,T}$
and the subsets of $Q$ with an even number of elements, given by
$$ \lambda \mapsto Q_\lambda =
	\set{\frakq \in Q}{\invar_\frakq(\Delta, \lambda) \equiv 1 \bmod 2} $$
Conversely for every subset $Q_{0}$ of $Q$ with $\#Q_{0}\in 2\mathbb{Z}$ there is a unique
$\lambda\in \Lambda_{Q,T}$ determined by the fact that
$\lambda$ is a norm of $L_{\mathfrak{Q}}/K_{\mathfrak{q}}$,
where $\mathfrak{Q}\in M_{L}$ and $\mathfrak{q}$ is the prime in $K$ lying under $\mathfrak{Q}$,
if and only if $\mathfrak{q}\not\in Q_{0}$.
\end{lemma}

\begin{proof}
Except for the last statement this follows from the contruction of the set $\Lambda_{Q,T}$.
The last statement follows from the fact that
$\invar_{\mathfrak{l}}(\Delta, \lambda) \equiv 0\bmod 2$ for all $\mathfrak{l}\not\in Q$
and that $\invar_{\mathfrak{q}}(\Delta,\lambda)\equiv 1 \bmod 2$
if and only if $\lambda$ is not a norm from $L_{\mathfrak{Q}}/K_{\mathfrak{q}}$.  
\end{proof}  
%---------------------------------------------------------------------------------------------------

\section{Existential Divisibility Lemma}
%===================================================================================================

As before $K$ is a global field (of characteristic not 2) and $L$ is a quadratic extension of $K$.
We fix an element $\Delta \in K^*$ such that $L = K(\sqrt\Delta)$.

\begin{prop}\label{ed1}
There exists an existential formula $\phi(x,y)$ such that:
\begin{enumerate}
\item\label{ed1:a}
Let $x$ and $y$ be  elements of $K^*$ for which $\phi(x,y)$ is true.
If $\frakr$ is any prime in $R(L/K)$ such that $v_{\frakr}(x)$ is odd,
then $v_{\frakr}(xy^{-2}) > 0$.

\item\label{ed1:b}
$\phi(x,y)$ is true for all elements $x$ and $y$ of $K^*$ satisfying the following conditions:
\begin{enumerate}
	\item\label{ed1:exist} There exists at least one $\frakr \in R(L/K)$
		for which $\valr(x)$ is odd.
	\item\label{ed1:RLK} For every $\frakr \in R(L/K)$ with $v_{\frakr}(x)$ odd,
		we have $v_{\frakr}(xy^{-2}) \geq 0$.
	\item\label{ed1:real} For every $\frakc\in \An$
		the element $x$ is positive in $K_{\frakc}\cong \mathbb{R}$.
	\item\label{ed1:SLK} For every $\fraks \in S(L/K)$,
		the element $x$ is a norm from $L_\frakS$,
		where $\frakS$ is the unique prime lying above $\fraks$.
\end{enumerate}
\end{enumerate}
\end{prop}

To prove the proposition we need to use lemma~\ref{normval} for all inert primes $\frakr\in R(L/K)$.
However in general it is not possible to find a primitive element $\alpha \in L$ such that
$\FF{\frakR}=\FF{\frakr}[\overline{\alpha}]$ for all $\frakr\in R(L/K)$.
The following lemma will solve this difficulty:

\begin{lemma}\label{residuegen}
Let $K$ and $L$ be as above.
There exist elements $\alpha_0, \alpha_1 \in L^*$ such that for all
$\frakr\in R(L/K)$ either
$\FF{\frakR} = \FF{\frakr}[\overline{\alpha_0}]$ or
$\FF{\frakR} = \FF{\frakr}[\overline{\alpha_1}]$.
\end{lemma}

\begin{proof}
We start by setting $\alpha_0 = \sqrt\Delta$.
Consider a $\frakr\in R(L/K)$ such that $v_{\frakr}(\Delta)=0$
and (in the number field case) $\frakr$ is not a $2$-adic prime
(i.e., it is not lying above the prime $2$ in $\Q$).
Since $L_\frakR=K_{\frakr}(\sqrt{\Delta})$ is a quadratic extension of $K_{\frakr}$,
it follows from the assumptions on $\frakr$ that $\overline{\Delta}$
is not a square in $\FF{\frakr}$.
This is a consequence of Hensel's lemma since for non-2-adic primes
a square in the residue field lifts to a square in the completion.
So for these primes $\frakr$ we have
$\FF{\frakR}=\FF{\frakr}(\overline{\sqrt{\Delta}})$.

The remaining primes are exactly the inert $2$-adic primes
or the inert primes $\frakr$ for which $v_{\frakr}(\Delta) \neq 0$.
This set $T$ of inert primes is finite, say $T=\{\frakr_{1}, \dots, \frakr_{n}\}$.
For all $i=1, \dots, n$, we let $\frakR_i$ be the unique prime in $L$ lying over $\frakr_i$.

Consider the semi-local ring $\calO_{T}=\cap_{i=1}^{n}(\calO_{\frakr_{i}}\cap K)$
and its integral closure $\widetilde{\calO_{T}}=\cap_{i=1}^{n} (\calO_{\frakR_{i}}\cap L)$.
The canonical morphisms
$$\calO_{T}\hookrightarrow \calO_{\frakr_{i}} \text{ and }
\widetilde{\calO_{T}}\hookrightarrow \calO_{\frakR_{i}}$$
induce isomorphisms
$\calO_{T}/(\pi_{\frakr_{i}})\cong \calO_{\frakr_{i}}/(\pi_{\frakr_{i}})=\FF{\frakr_{i}}$
and $\widetilde{\calO_{T}}/(\pi_{\frakR_{i}})
	\cong \calO_{\frakR_{i}}/(\pi_{\frakR_{i}}) = \FF{\frakR_{i}}$.
For all $i=1, \dots, n$ the residue fields $\FF{\frakR_i}$
are degree 2 extensions of $\FF{\frakr_i}$,
so $\FF{\frakR_i}=\FF{\frakr_i}[\overline{\beta_i}]$.
By the Chinese remainder theorem there exists an element
$\alpha_1\in \widetilde{\calO_{T}}$ such that
$\alpha_1\equiv \overline{\beta_i} \bmod (\pi_{\frakR_i})$.
This implies
$\FF{\frakR_{i}} = \FF{\frakr_{i}}[\overline{\alpha_1}]$ for all $i=1, \dots, n$.
\end{proof}
%---------------------------------------------------------------------------------------------------

We can now prove the proposition.

\begin{proof}
Take $\alpha_0,\alpha_1$ as in lemma~\ref{residuegen}.
We define $\phi(x,y)$ as
$$ \phi(x,y) \leftrightarrow \phi_0(x,y) \wedge \phi_1(x,y) $$
where $\phi_i(x,y)$ is the formula
$$ \phi_i(x,y) \leftrightarrow \exists a,b,c \in K:
	1 + x\norm(y\inv + \alpha_i c) = a^2 - \Delta b^2 $$
or, written in an other way
$$ \phi_i(x,y) \leftrightarrow \exists a,b,c \in K:
	(1 + xy\iinv) + xy\inv\tr(\alpha_i)c + x\norm(\alpha_i)c^2 - a^2 + \Delta b^2 = 0 $$

We will prove part~\ref{ed1:a} of the theorem.
For the sake of contradiction, assume that $\phi(x,y)$ holds,
but $\valr(xy^{-2}) \leq 0$ for some prime $\frakr \in R(L/K)$
for which $v_{\frakr}(x)$ is odd.
Since $\valr(xy^{-2})$ is odd, necessarily $\valr(xy^{-2})<0$.

We have $\FF{\frakR}=\FF{\frakr}[\alpha_{i}]$, with $i$ either equal to $0$ or $1$.
Lemma~\ref{normval} implies
$\valr\big(\norm(y\inv + \alpha_i c)\big) = \min(\valr(y\iinv), \valr(c^2)) \leq \valr(y\iinv)$.
It follows that
$$ \valr\big(x\norm(y\inv + \alpha_i c)\big) \leq \valr(xy\iinv) < 0 $$
Thus $\valr\big(1 + x\norm(y\inv + \alpha_i c)\big) =
	\valr\big(x\norm(y\inv + \alpha_i c)\big)$, which is odd.
But $\phi_i(x,y)$ states that
$1 + x\norm(y\inv + \alpha_i c)$ is equal to $a^2 - \Delta b^2$.
The latter however has even valuation in $\frakr$ since it is a norm, so we found our contradiction.

\vspace{3mm}
To prove part~\ref{ed1:b} of the theorem,
we assume $x$ and $y$ satisfy all the given conditions.

We claim that $\phi_i(x,y)$ ($i=0,1$)
will be true if the following quadratic form is isotropic:
\begin{equation}\label{ed1:form}
	Q_i(a,b,c,d) =
		(1 + xy\iinv)d^2 + xy\inv\tr(\alpha_i)cd + x\norm(\alpha_i)c^2 - a^2 + \Delta b^2
\end{equation}
Indeed, if $Q_i$ is isotropic but $\phi_i(x,y)$ does not hold,
then $Q_i$ must have a solution with $d$ equal to zero:
$$ x\norm(\alpha_i) c^2 - a^2 + \Delta b^2 = 0 $$
Now choose a prime $\frakr \in R(L/K)$ for which $\valr(x)$ is odd.
Then $\valr(x\norm(\alpha_i) c^2)$ will be odd, but $\valr(a^2 - \Delta b^2)$ is even,
which gives a contradiction.

It remains to prove that $Q_i$ ($i = 0,1$) is isotropic in $K$,
or by applying the theorem of Hasse--Minkowski (cf.\ theorem~\ref{hassemink})
that $Q_i$ is isotropic over every completion of $K$.
We check this by considering all possible primes in $M_{K}$.

\begin{caselist}
\item[$\fraka\in A(L/K)$]
$K_{\fraka}\cong \R$ or $\C$.
Set $d = 0$, $c = \frac{1}{\sqrt{x}}$ and $a$ and $b$ such that $\alpha_i = a + b\sqrt\Delta$.
It follows that $Q_i(a,b,c,d)=0$.

\item[$\frakp \in P(L/K)$]
Take $\frakP$ as one of the two primes in $M_{L}$ lying over $\frakp$.
Since $L = K(\sqrt\Delta)$ and $L_{\frakP}=K_{\frakp}$ it follows that
$\Delta$ is a square in $K_\frakp$.
This means that the form $\form{-1, \Delta}$,
which is a subform of $Q_i$, is isotropic in $K_\frakp$.
So also $Q_i$ is isotropic in $K_\frakp$.

\item[$\frakr \in R(L/K)$]
Suppose $\valr(x)$ is even.
We know that $\valr\big(\norm(\alpha_i)\big)$ will also be even,
so we can write $x\norm(\alpha_i) = \pi_{\frakr}^{2m} u$ with $\valr(u) = 0$.
If we set $d = 0$ and $c = \pi_{\frakr}^{-m}$, then the first three terms of
\eqref{ed1:form} will be equal to the unit $u$.
Since every unit in $K_{\frakr}$ is a norm of the extension $L_{\frakR}$,
there exist elements $a$ and $b$ in $L_{\frakR}$ such that $u = \norm(a + b\sqrt\Delta)$.
This proves that $Q_i$ is isotropic.

If $\valr(x)$ is odd, it is given that $\valr(xy\iinv) > 0$.
This implies that $\valr(1 + xy\iinv) = 0$,
so $1 + xy\iinv$ is a unit.
If we set $c = 0$,
we can conclude as above that $Q_i$ is isotropic.

\item[$\fraks \in S(L/K)$]
Setting $d = 0$ and $c = 1$ in $Q_i$ yields
the equation $x\norm_{L_\frakS/K_\fraks}(\alpha_i)
	= \norm_{L_{\frakS}/K_{\fraks}}(a + b\sqrt\Delta)$.
If we write this as
$$ x = \norm_{L_{\frakS}/K_{\fraks}}\left(\frac{a + b\sqrt\Delta}{\alpha_i}\right) $$
we see that this will always have a solution,
because by assumption $x$ is a norm from $L_{\frakS}$ over $K_{\fraks}$,
and $a + b\sqrt\Delta$ represents all elements of $L_\frakS = K_\fraks(\sqrt\Delta)$.
\end{caselist}
\end{proof}
%---------------------------------------------------------------------------------------------------

\begin{remark}
Proposition~\ref{ed1} applied to $K=\Q$ and $L=\Q(i)$ is a direct generalistation
of the existenial divisibility lemma proven by Pheidas in \cite{pheidas12}.
In the ramified primes, only the prime $2$ in that case, Pheidas formulates
alternatives for condition~\ref{ed1:SLK} ($x$ being a local norm).
It would be possible to formulate such alternatives in the general case.
We did not work this out explicitly since in theorem~\ref{exdiv} all
conditions in the ramified primes will be removed.

We also like to point out that condition~\ref{ed1:exist},
the existence of an inert prime where $x$ has an odd value, is not necessary.
Even without this condition one can show that if the quadratic form~\eqref{ed1:form} is isotropic
there also is a zero $(a,b,c,d)$ with $d=1$.
Since removing this condition would not substantially simplify the following section,
we preferred to keep the formulation of the lemma analogous to that of Pheidas.
\end{remark} 
%---------------------------------------------------------------------------------------------------

\section{Removing all extra conditions}\label{remcond}
%===================================================================================================

In this section we will prove a version of the {\ED}
without the local conditions \eqref{ed1:exist}, \eqref{ed1:real} and \eqref{ed1:SLK}.
from proposition~\ref{ed1}.
This way we will find a formula which is equivalent with
\emph{For all primes $\frakr$ in $R(L/K)$ for which $\valr(x)$ is odd,
it holds that $\valr(xy^{-2}) > 0$.}

As an application of this, we give an existential definition
of the set of elements of $K$ having non-negative valuation in a prime.

\begin{lemma}\label{sumsquares}
There exists a number $k$ and elements $u_1, \dots, u_k \in K$
with $\valr(u_i) \geq 0$ for all $\frakr \in R(L/K)$,
such that the following holds:

Take any finite set $T \subset R(L/K)$ and consider the semi-local ring
$\calO_T = \cap_{\frakt \in T}(\calO_{\frakt}\cap K)$.
Every $x \in \calO_T$ can be written as
$$ x = u_1 x_1^2 + u_2 x_2^2 + \dots + u_k x_k^2 $$
with $x_i \in \calO_T \setminus \{0\}$.
\end{lemma}

\begin{proof}
Here we need to give a different arguments 
for $K$ a global function field and for $K$ a number field.

Let $K$ be a global function field of characteristic not 2.
Let $L$ and $T$ be as in the statement of the theorem and let $x\in \calO_T$.
Choose $y \in \calO_T$ such that $y \not= \pm 1$ and $x+y \not= \pm 1$
(this is possible since $\calO_T$ is infinite).
Then
$$ x = \left(\frac{x+y+1}{2}\right)^2 - \left(\frac{x+y-1}{2}\right)^2
	+ \left(\frac{y-1}{2}\right)^2 - \left(\frac{y+1}{2}\right)^2 $$
Since $\frac{1}{2} \in \calO_{T}$ we see that every $x \in \calO_T$
is equal to an alternating sum of four non-zero squares in $\calO_T$.
It follows that the lemma holds in this case with $k = 4$ and $u_1 = u_3 = 1$, $u_2 = u_4 = -1$.

To prove the lemma in the number field case we first note that every integer $x\in \Z$
is represented over $\Z$ by the quadratic form $x_1^2 - x_2^2 + x_3^2 - x_4^2$.
Namely if $x$ is odd choose $y \in \Z$ such that  $x + 4y \not= \pm 1$ and $y\not=\pm 1$,
then
$$ x = \left(\frac{x+4y+1}{2}\right)^2 - \left(\frac{x+4y-1}{2}\right)^2
	+ \left(y-1\right)^2 - \left(y+1\right)^2. $$
If $x$ is even choose $y \in \Z$ such that $y$ is odd, $x+y \not= \pm 1$ and $y \not= \pm 1$,
then
$$ x = \left(\frac{x+y+1}{2}\right)^2 - \left(\frac{x+y-1}{2}\right)^2
	+ \left(\frac{y-1}{2}\right)^2 - \left(\frac{y+1}{2}\right)^2. $$
Note that in these representations of $x \in \Z$ all the coordinates are non-zero.
  
We know that the ring of integers $\calO_K$ of $K$ is a finitely generated $\Z$-module, say 
$$ \calO_K = a_1\Z + a_2\Z + \dots + a_n\Z. $$
Set $k = 4n$ and for the $u_i$'s we take
$a_1, -a_1, a_1, -a_1, a_2, -a_2, a_2, -a_2 \dots, a_n, -a_n, a_n, -a_n$.
Since any integer is represented with non-zero coordinates by the form
$x_1^2 - x_2^2 + x_3^2 - x_4^2$ it follows
that every element of $\calO_K$ is represented with non-zero coordinates by the form
$u_1 x_1^2 + u_2 x_2^2 + \dots + u_{4n} x_{4n}^2$.

Now consider $\calO_T$ with $T$ a finite subset of $R(L/K)$.
Every $x$ in $\calO_T$ can be written as $y/z$ with $y$ and $z$ in $\calO_K$.
And since $\calO_T$ is a principal ideal domain
we may assume that $\valt(z) = 0$ for all $\frakt \in T$.
It follows from the above that
$yz = u_1 x_1^2 + \dots + u_k x_k^2$, with $x_1, \ldots , x_k$ non-zero elements of $\calO_K$.
Then
$$ x = \frac{yz}{z^2} = u_1\left(\frac{x_1}{z}\right)^2 + \dots + u_k\left(\frac{x_k}{z}\right)^2 $$
For all $i=1, \ldots, k$ and $\frakt \in T$ we have $x_i/z \not= 0$
and $\valt(x_i/z) = \valt(x_i) \geq 0$,
which means that $x_i/z \in \calO_T$. 
\end{proof}
%---------------------------------------------------------------------------------------------------

\begin{define}
Given any subset $\Lambda \subseteq K^*$, we define the \emph{support} of $\Lambda$ to be
$$ \supp(\Lambda) = \set{\frakp \in M_K}
	{\exists \lambda \in \Lambda: |\lambda|_\frakp \neq 1} $$
If $\Lambda$ is finite, then $\supp(\Lambda)$ will also be finite.
\end{define}
%---------------------------------------------------------------------------------------------------

Choose four primes $\frakr_1, \frakr_2, \frakr_3, \frakr_4$ in $R(L/K)$
and define the following finite set of primes:
$$ Q = \{\frakr_1, \frakr_2, \frakr_3, \frakr_4\} \cup S(L/K) \cup \An(L/K) $$
Let $T$ be any finite subset of $R(L/K)\setminus Q$ and $\Lambda_{Q,T}$ the subset of $K^*$
parameterizing $\twoc\Br^{Q}(L/K)$ as given in lemma~\ref{parset}.
By construction of $\Lambda_{Q,T}$ it holds that $\supp(\Lambda_{Q,T}) \cap T = \emptyset$.
%---------------------------------------------------------------------------------------------------

\begin{lemma}\label{ed2}
Let $\Lambda=\Lambda_{Q,T}$ be the set as defined above.
There exists an existential formula $\psi_\Lambda(x,y)$ such that:
\begin{enumerate}
\item\label{ed2:a}
Let $x$ and $y$ be elements of $K^*$ for which $\psi_\Lambda(x,y)$ is true.
If $\frakr$ is any prime in $R(L/K) \setminus \supp(\Lambda)$
such that $\valr(x)$ is odd, then $\valr(xy\iinv) > 0$.
\item\label{ed2:b}
Suppose $x$ and $y$ are elements of $K^*$
such that for every $\frakr \in R(L/K)$ with $\valr(x)$ odd,
it holds that $\valr(xy\iinv) > 0$.
Then $\psi_\Lambda(x,y)$ is true.
\end{enumerate}
\end{lemma}

\begin{proof}
To construct the formula $\psi_\Lambda(x,y)$,
we use the $\phi(x,y)$ obtained in lemma~\ref{ed1},
and the $u_i$ from lemma~\ref{sumsquares}.
We also set $u_0 = 1$.
We define $\psi_\Lambda(x,y)$ as
\begin{multline*}
	\exists y_0, y_1, \dots, y_k, z_0, z_1, \dots, z_k \in K: \\
	(y_0 z_0 = 1) \wedge \dots \wedge (y_k z_k = 1)
	\wedge \left((u_0 z_0^2 + \dots + u_k z_k^2)y^2 = 1\right) \\
		\wedge \left(\bigvee_{\lambda \in \Lambda} \phi(\lambda x, y_0)\right)
		\wedge \dots
		\wedge \left(\bigvee_{\lambda \in \Lambda} \phi(\lambda x, y_k)\right)
\end{multline*}

Note that the first two lines are equivalent with
$$ \exists y_0, y_1, \dots y_k \in K^*: \left(u_0 y_0\iinv + \dots + u_k y_k\iinv = y\iinv\right) $$

To prove part \ref{ed2:a}, assume that $\psi_\Lambda(x,y)$ holds.
Take any prime $\frakr \in R(L/K) \setminus \supp(\Lambda)$
for which $\valr(x)$ is odd.
$\psi_\Lambda(x,y)$ implies that for all $i=1, \ldots, k$, $\phi(\lambda_i x,y_i)$ is true
for a certain $\lambda_i \in \Lambda$.
Because $\frakr$ is outside of the support of $\Lambda$,
we know that $\valr(\lambda_i x) = \valr(x)$ is odd.
But now $\phi(\lambda_i x,y_i)$ implies that $\valr(\lambda_i xy_i\iinv) > 0$,
and this valuation is equal to $\valr(xy_i\iinv)$.
Lemma~\ref{sumsquares} gave us $\valr(u_i) \geq 0$,
so we also have $\valr(xu_iy_i\iinv) > 0$.
We conclude the proof of part \ref{ed2:a} by observing that
$$ \valr(xy\iinv) = \valr\left(x(u_0 y_0\iinv + \dots + u_k y_k\iinv)\right) \geq
	\min_{i=0}^k \valr(xu_iy_i\iinv) > 0 $$

For the proof of part~\ref{ed2:b}, suppose we have $x,y \in K^*$ such that
for every $\frakr \in R(L/K)$ with $\valr(x)$ odd,
the inequality $\valr(xy\iinv) > 0$ holds. 

We can use approximation
to get a $y_0\inv$ for which the following finitely many conditions are satisfied:
\begin{enumerate}[(I)]
\item\label{y0:other}
$\valr(y_0\inv) > \valr(y\inv)$ for all
$\frakr \in R(L/K) \setminus \{\frakr_1, \frakr_2, \frakr_3, \frakr_4\}$
for which $\valr(x)$ is odd.
\item\label{y0:r1r3}
$v_{\frakr_j}(y_0\inv) > -v_{\frakr_j}(x)/2$
for $j = 1,3$.
\item\label{y0:r2r4}
$v_{\frakr_j}(y_0\inv - y\inv) = -v_{\frakr_j}(2y\inv) +
	\text{an even number greater than }
 	\max\left(-v_{\frakr_j}(x), 2v_{\frakr_j}(2y\inv)\right)$,
	for $j = 2,4$.
\end{enumerate}

We define these sets of primes:
\begin{align*}
	T_0 &= \{\frakr_1, \frakr_3\} \cup
		\set{\frakr \in R(L/K) \setminus \{\frakr_1, \frakr_2, \frakr_3, \frakr_4\}}
			{\valr(x) \text{ is odd}} \\
	T_1 = T_2 = \dots = T_k &= \{\frakr_2, \frakr_4\} \cup
		\set{\frakr \in R(L/K) \setminus \{\frakr_1, \frakr_2, \frakr_3, \frakr_4\}}
			{\valr(x) \text{ is odd}}
\end{align*}

\begin{claim}
There exist $y_0, y_1, \dots, y_k \in K^*$ such that
$u_0 y_0\iinv + \dots + u_k y_k\iinv = y\iinv$ and
for all $0 \leq i \leq k$ we have $\valr(xy_i\iinv) > 0$ for all $\frakr \in T_i$.
\end{claim}

\textit{Proof of claim.}
We have already constructed $y_0$.
The case $i = 0$ follows easily from \eqref{y0:other} and \eqref{y0:r1r3} above,
together with the hypotheses of part~\ref{ed2:b}.

For every $\frakr \in T_1$ we will prove that $\valr(y\iinv - y_0\iinv)$ is even,
and $\valr(y\iinv - y_0\iinv) \geq -\valr(x)$.
Set
$$ a = y\iinv - y_0\iinv = -(y_0\inv - y\inv)((y_0\inv - y\inv) + 2y\inv) $$
If $\frakr$ is either $\frakr_2$ or $\frakr_4$,then
from \eqref{y0:r2r4} it follows that $\valr(y_0\inv - y\inv) > \valr(2y\inv)$, so
$$ \valr(a) = \valr(y_0\inv - y\inv) + \valr(2y\inv)
	= \text{an even number greater than } -v_{\frakr}(x) $$
If $\frakr$ is not $\frakr_2$ nor $\frakr_4$,
we know that $\valr(x)$ is odd and the hypotheses
say that $\valr(y\iinv) > -\valr(x)$.
Then \eqref{y0:other} implies that
$\valr(a) = \valr(y\iinv - y_0\iinv) = \valr(y\iinv)$ is even and $\valr(a) > -\valr(x)$.

Now we use approximation to find a $\mu \in K$ for which
$$ \valr(\mu) = -\valr(a)/2 \qquad \text{for all } \frakr \in T_1. $$

This way $\mu^2a$ is in the ring $\calO_{T_1}$,
and by applying lemma~\ref{sumsquares} for this ring,
we write $\mu^2a$ as
$$ \mu^2a = u_1 w_1^2 + \dots + u_k w_k^2. $$
If we set $y_i\inv = w_i/\mu$,
then $\valr(y_i\iinv) = 2\valr(w_i) - 2\valr(\mu) \geq 0 + \valr(a) > -\valr(x)$
for $\frakr \in T_1 = T_i$.

This concludes the proof of the claim.

Using this,
we will show that $\bigvee_{\lambda \in \Lambda} \phi(\lambda x, y_0)$ is true.
The argument proving that
$\bigvee_{\lambda \in \Lambda} \phi(\lambda x, y_i)$ is true for $i=1, \ldots k$
is completely analogous but with the role of the pairs
$\{\frakr_1, \frakr_3\}$ and $\{\frakr_2, \frakr_4\}$ exchanged.

We make a subset $Q_0$ of $Q$ of even cardinality.
We start by taking the primes in $\{\frakr_2, \frakr_4\} \cup S(L/K) \cup \An(L/K)$
for which $x$ is not a local norm.
We add $\frakr_1$ to $Q_0$ if $x$ is a norm from $L_{\frakR_1}$.
If necessary, we add $\frakr_3$ to make sure $Q_0$ has an even number of elements.
If we take the $\lambda \in \Lambda$ such that $\lambda$ is a local norm everywhere,
except for the primes in $Q_0$, then $\lambda x$ will have the following properties:
\begin{itemize}
\item
$\lambda x$ is a local norm for all primes in $S(L/K) \cup \An(L/K)$.
\item
$v_{\frakr_1}(\lambda x)$ is odd.
\item
$v_{\frakr_2}(\lambda x)$ is even and $v_{\frakr_4}(\lambda x)$ is even.
\item
$\valr(\lambda x) \equiv \valr(x) \mod{2}$ for all
$\frakr \in R(L/K) \setminus \{\frakr_1, \frakr_2, \frakr_3, \frakr_4\}$.
\end{itemize}

We will now prove that $\phi(\lambda x,y_0)$ is true for this $\lambda \in \Lambda$.
The choice of $\lambda$ already implies
conditions~\ref{ed1:exist}, \ref{ed1:real} and \ref{ed1:SLK}
for part~\ref{ed1:b} of lemma~\ref{ed1}.

In order to prove condition~\ref{ed1:RLK},
take any prime $\frakr \in R(L/K)$ for which $\valr(\lambda x)$ is odd.
We see that $\frakr$ cannot be $\frakr_2$ or $\frakr_4$.
If $\frakr$ is not $\frakr_1$ nor $\frakr_3$,
the fact that $\valr(\lambda x)$ is odd
implies that $\valr(x)$ is odd.
In any case we have $\frakr \in T_0$.
Hence $\valr(\lambda xy_0\iinv) \geq \valr(xy_0\iinv) > 0$
by the preceding claim.
\end{proof}
%---------------------------------------------------------------------------------------------------

The previous lemma is a form of the {\ED}
without conditions in the real primes and ramifying primes.
However, in one direction, it does not work for primes in $\supp(\Lambda_{Q,T})$.
By applying the lemma two times
for well chosen sets $\Lambda_{Q,T}$ and $\Lambda_{Q',T'}$,
we can solve this problem and obtain the main theorem.

\begin{theorem}\label{exdiv}
There is an existential formula $\Omega(x,y)$ which is equivalent with the formula
\begin{equation}\label{ed:expr}
	\forall \frakr \in R(L/K):
		\left(\valr(x) \text{ odd } \rightarrow \valr(xy\iinv) > 0\right)
\end{equation}
\end{theorem}

\begin{proof}
Take eight different primes
$\{\frakr_1, \frakr_2, \frakr_3, \frakr_4, \frakr_1', \frakr_2', \frakr_3', \frakr_4'\}$ in $R(L/K)$,
and define $Q$ as $\{\frakr_1, \frakr_2, \frakr_3, \frakr_4\} \cup S(L/K) \cup \An(L/K)$.
Take $T = \{\frakr_1', \frakr_2', \frakr_3', \frakr_4'\}$ and let $\Lambda = \Lambda_{Q,T}$
be the corresponding set parameterizing $\twoc\Br^{Q}(L/K)$.

Let $Q' = \{\frakr_1', \frakr_2', \frakr_3', \frakr_4'\} \cap S(L/K)\cap \An(L/K)$
and take $T' = \{\frakr_1, \frakr_2, \frakr_3, \frakr_4\} \cup(\supp(\Lambda_{Q,T})\cap R(L/K))$.
Since $T' \cap Q' = \emptyset$ by the choice of $T$, the parameterizing set 
$\Lambda' = \Lambda_{Q',T'}$ is defined.
Note that the choice of $T'$ now implies 
$R(L/K) \cap \supp(\Lambda_{Q,T}) \cap \supp(\Lambda_{Q',T'}) = \emptyset$.

Now we define
$$ \Omega(x,y) \leftrightarrow \psi_\Lambda(x,y) \wedge \psi_{\Lambda'}(x,y) $$

Suppose $\Omega(x,y)$ is true.
$\psi_\Lambda(x,y)$ says that $\valr(x)$ odd implies $\valr(xy\iinv) > 0$
for $\frakr \in R(L/K) \setminus \supp(\Lambda)$.
$\psi_{\Lambda'}(x,y)$ says the same thing for $\frakr \in R(L/K) \setminus \supp(\Lambda')$.
Because $R(L/K) \cap \supp(\Lambda) \cap \supp(\Lambda') = \emptyset$,
we have it for all $\frakr$ in $R(L/K)$.

If \eqref{ed:expr} is satisfied, then we know by lemma~\ref{ed2}
that $\psi_\Lambda(x,y)$ and $\psi_{\Lambda'}(x,y)$ are both true.
\end{proof}
%---------------------------------------------------------------------------------------------------

As mentioned in the introduction our motivation for theorem~\ref{exdiv}
finds its origin in Pheidas' paper~\cite{pheidas12}.
The next corrolary shows that the theorem also generalises the fact that in a global field
the elements integral in a prime $\frakp$ form a diophantine set.
This result in different cases is due to different authors as indicated in the introduction
of chapter~5 in \cite{eisentraeger-thesis}, there one also finds a uniform proof for this fact
based on Hilbert's reciprocity law for the Brauer group of a global field.     
\begin{cor}
For every non-archimedean prime $\frakp \in M_K$,
the set $\set{z \in K}{\valp(z) \geq 0}$ is diophantine.
\end{cor}

\begin{proof}
Let $\mathfrak{p}\in M_{K}$ be a non-archimedean prime.
Choose an other non-archimedean prime $\frakq \not= \frakp$.
Choose $L/K$ a quadratic extension such that
$\frakp \in R(L/K)$ and $\frakq \in S(L/K)$.
To see that such an extension exists, let $K_\frakp(\alpha_\frakp)$
be the unique quadratic unramified extension of $K_\frakp$ and $K_\frakq(\beta_\frakq)$
a totally ramified extension of degree two of $K_\frakq$.
Let $X^2 + a_{\frakp,1}X + a_{\frakp,2}$ be the minimal polynomial of
$\alpha_{\frakp}$ over $K_{\frakp}$ and $X^2 + b_{\frakq,1}X + b_{\frakq,2}$
be the minimal polynomial of $\beta_\frakq$ over $K_\frakq$.
Then lemma (33.8) in \cite{reiner-maxord} states that if $c_1$ and $c_2$
are taken sufficiently close to $a_{\frakp,1}$ and  $b_{\frakq,1}$,
respectively $a_{\frakp,2}$ and $b_{\frakq,2}$,
the polynomial $f(X) = X^2 + c_1X + c_2$ is separable and irreducible over $K$
having a root in $K_\frakp$ and in $K_\frakq$.
It follows that $K(\gamma)$, with $f(\gamma) = 0$,
is a quadratic extension of $K$ with the desired properties.

Let $\omega \in \twoc\Br(K)$ such that $\invar_\frakp \omega \equiv 1 \bmod 2$,
$\invar_\frakq \omega\equiv 1\bmod 2$ and
$\invar_\frakr \omega\equiv 0\bmod2 $ for all primes $\frakr \not= \frakp,\frakq$.
(Such an element $\omega$ exists by Hilbert's reciprocity law).
By construction $L$ is a splitting field of $\omega$.
So $\omega=(\gamma, x)$ with $L = K(\gamma)$.
It follows from the choice of $L$ and $\omega$ that $\valp(x)$ is odd
and $\valr(x)$ is even for all $\frakr \in R(L/K) \setminus \{\frakp\}$.
After multiplying $x$ with a suitable square, we may assume that $\valp(x) = 1$.
Now apply theorem~\ref{exdiv} with this fixed $x$.
Then $\Omega(x,y)$ is equivalent with ``$\valp(xy\iinv) > 0$'',
or ``$\valp(y\inv) > -\valp(x)/2$''.
If we set $y = z\inv$ and use the fact that $\valp(x) = 1$,
we find that $\Omega(x,z\inv)$ is equivalent with ``$\valp(z) \geq 0$''.
\end{proof}
%---------------------------------------------------------------------------------------------------

\bibliographystyle{amsalpha}
%\bibliography{all}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{O'M63}

\bibitem[Eis03]{eisentraeger-thesis}
Kirsten Eisentr\"ager, \emph{Hilbert's tenth problem and arithmetic geometry},
  Ph.D. thesis, University of California at Berkeley, 2003.

\bibitem[Neu92]{neukirch-az}
J\"urgen Neukirch, \emph{Algebraische zahlentheorie}, Springer, 1992.

\bibitem[O'M63]{omeara-introqf}
Timothy O'Meara, \emph{Introduction to quadratic forms}, Springer, 1963.

\bibitem[Phe91]{pheidas5}
Thanases Pheidas, \emph{Hilbert's tenth problem for rational function fields
  over finite fields}, Invent. Math. \textbf{103} (1991), 1--8.

\bibitem[Phe00]{pheidas12}
\bysame, \emph{An effort to prove that the existential theory of $\mathbb{Q}$
  is undecidable}, Contemporary Mathematics \textbf{270} (2000), 237--252.

\bibitem[Rei75]{reiner-maxord}
Irving Reiner, \emph{Maximal orders}, London Academic Press, 1975.

\bibitem[Sch85]{scharlau-qhf}
Winfried Scharlau, \emph{Quadratic and hermitian forms}, Grundlehren Math.
  Wiss., no. 270, Springer Berlin, 1985.

\bibitem[Shl96]{shlapentokh-ffff}
Alexandra Shlapentokh, \emph{Diophantine undecidability over algebraic function
  fields over finite fields of constants}, J. Number Theory \textbf{58} (1996),
  317--342.

\bibitem[Vid94]{videla-ff2}
Carlos Videla, \emph{Hilbert's tenth problem for rational function fields in
  characteristic 2}, Proc. Amer. Math. Soc. \textbf{120} (1994), 249--253.

\bibitem[VZ03]{oberw-vgeel-zahidi}
Jan {Van Geel} and Karim Zahidi, \emph{Quadratic forms and divisibility},
  Mini-Workshop: Hilbert's 10th problem, Mazur's conjecture and divisibility
  sequences, Oberwolfach January 19--25, 2003.

\end{thebibliography}

%---------------------------------------------------------------------------------------------------

\end{document}
%###################################################################################################
