section_11.tex

%%%%%%%%%%%%%%%%%%%%% chapter.tex %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% sample chapter
%
% Use this file as a template for your own input.
%
%%%%%%%%%%%%%%%%%%%%%%%% Springer-Verlag %%%%%%%%%%%%%%%%%%%%%%%%%%
%\motto{Use the template \emph{chapter.tex} to style the various elements of your chapter content.}
\subsection{Mapping the Landscape and Telegraphing our Journey}
\sectionmark{Let's Orient Ourselves}
\label{orientation} % Always give a unique label
% use \sectionmark{}
% to alter or adjust the chapter heading in the running head
%\sectionmark{Some Introductions}

How one starts with the Tarskian ideas introduced in their first course in mathematical logic and ends up studying \omy to the end of proving the \pwt is perhaps and unsurprisingly eminently unclear to any who do not already know the methodology. So we don't become too disenfranchised and uninspired as we work our way through the logical results to the end of a number-theoretic result. We lay out a brief map of what is to come and how each part logically follows from its antecedent. This is not perhaps the most interesting course for one interested solely in number theory or simply mathematical logic, but where these two unlikely friends collide creates something wondrous and beautiful. We then go on with just a few words in preparation for what is to come; some definitions, expectations of the experience (or lack thereof) on the reader's part, and a general outline are given. The overly excited reader may feel free to skip right onto Section \ref{setting}, but this section serves as just a bit of an \textit{amuse-bouche} for those not so ready to jump right in.

\bigskip
\footnote{This will come to make sense later and will seem apropos of nothing right now, but please, take no comfort in these short, horizontal lines other than the joy one may find in delineating the would-be abstract from the content proper.}
\centerline{\rule{0.3333\linewidth}{.2pt}}
\smallskip

\subsubsection{And \pw is?}
\noindent Perhaps the best and most prudent question to be asking one's self currently, if for no other reason than determining the worth of their time in reading this whole affair, is what the statement of the \pwt \emph{actually} is? And what, supposing the reader knows the context in which we define \omy, could that have to do with a \ntc result like the \pwt? Well, dear reader, we hope in this brief first section to enlighten you to the big ideas upon which we will ruminate for the remainder of this course and provide a coarse outline of how these come to build on one another in order to start from the relatively basic, to the phenomenal. To live up to this section's name, however, we now state the \pwt -- first informally and then as we will come to prove it. In all cases, however, note that we are speaking to \om expansions of the \emph{real} field, and we will not be covering the theorem and all that leads up to it in full generality.

\begin{theorem}[\pwt (Informal)]
  \label{thm:pwt_informal}
  Let $\tilde{\R}$ an \om expansion of $(\R, <)$. Then \textbf{transcendental} \defnb sets have very \textbf{few} rational points.
\end{theorem}

It is easily understandable, seems reasonable, and (maybe?) doable without too much fuss, doesn't it seem? Here now is the formal statement, which requires the following crash course in notation; we denote by $H$ the usual rational multiplicative height function -- but it also doubles, when not used as a function, as an upper-bound on rational numbers we are interested in (I didn't decide the notation). When taking vectorial input, the height is given by the element-wise maximum. Suppose $X \subseteq \R^n$. Denote $X(\Q) \coloneqq X \cap \Q$ and further $\XQH \subseteq X(\Q)$ with element height as given by the function, $H$, and bounded by the constant, $H$. Finally, the superscripts $\emph{tr}$ and $\emph{alg}$ refer to the transcendental and algebraic parts of the set they sit atop (note, of course, that necessarily we have $X \setminus \Xtr = \Xalg$). What we then want, and what \pw gives us, are good bounds on $\card{\XtrQH}$.

\begin{theorem}[\pwt (Formal)]
  \label{thm:pwt_formal}
  Let $X \subseteq \R^n$ \defnb in $\tilde{\R}$ an \om expansion of $(\R, <)$. Then for any $\epsilon$ there exists some $c$ such that for all $H$,
  \begin{align*}
    \card{\XtrQH} \leq c \cdot H^{\epsilon},
  \end{align*}
  which is a very fine thing indeed -- that last bit being an editorial note, and not (necessarily) part of the honest theorem.
\end{theorem}

\subsubsection{There but Not Back Again}

How we shall prove this is not direct by most meanings or usages of the term and is not going to follow the proof originally given by the eponyms for the theorem. Rather, we will more so be following a later, arguably nicer proof given just this year (if you are reading this in 2022) by Bhardwaj and van den Dries \cite{bhardwaj_pilawilkie_2022}, that makes clever use of semialgebraic cell decomposition for a large part of the original proof, and elsewhere use a proof of the Yomdin-Gromov theorem given by Binyamini and Novikov \cite{binyamini_yomdingromov_2021} also very recently.

The broad strokes are as follows, with some bits left out in the majority, just definitional. This encompasses most of Part I of these notes -- as this is, after all, a graduate course on this topic. We start from the very basics with \defnbly, \omy, the Finiteness Theorem in 2 variables (which goes on to be used more broadly), and then \cds. With basics in place, we define definable choice and curve selection and then go on to show that \defnb and algebraic dimension are in agreement. Closer to the majority of the matter, we go on to prove the theorems mentioned above that, when all put together, allow us to produce a proof of \pw. Some parts are taken for granted (for example, assuming uniform finiteness without proof), and in general, we treat only expansions of the real field rather than a more generic structure -- and this allows us to use a few tricks such as the Baire Category theorem at one point. On the whole, however, this set of notes constitutes almost all but some of the trickier details in a fully self-contained proof of the \pw theorem, and the reader is directed to where any gaps may be addressed when present.


\sectionmark{A Small Bit Before we Begin}
\subsubsection{Before the Lectures Proper}

We feel somewhat compelled to address an aspect of this topic that we felt was slightly neglected in the curriculum. Had one seen the list of attendees to these lectures, the reason for skipping over such `trivialities' as we are about to point out briefly is clear — with several attendees being former students of Pila or Wilkie themselves. Still, for the \emph{not-even-amateur} logician, the following certainly bears some explicit mention.

In the absence of the results we come to find, \omy may appear a relatively unmotivated idea to study. Of course, as the pure mathematicians we are (or hope one day to be), why \emph{shouldn't} the mere concept of further understanding be enough to compel our interest? Still, the progression from introductory mathematical logic and the importance and usefulness of quantifier elimination (QE) to \omy is one that was unapparent to this author until being noted elsewhere. We don't claim this to be a failure of the course so much as a failure in personal preparation, but should the reader find themselves similarly underprepared, then they will find themselves thankful for this little pretext.

To keep things brief, we will say just this: in a predicate logical system, we are interested in quantifier elimination. The result of the elimination of quantifiers is essentially the answer to the question a quantified statement asks. Perhaps the most famous example of this is the existence of real roots of quadratic equations. We ask the quantified `question':
\begin{align}
  \exists x \in \R . (a \cdot x^2 + b \cdot x + c = 0 \wedge a \neq 0)
\end{align}
— that is, does there exist such an $x$? The quantifier eliminated equivalent form is
\begin{align}
  b^2 - 4 \cdot a \cdot c \geq 0 \wedge a \neq 0,
\end{align}
the first half of which should be recognized as the quadratic discriminant (and the second just to ensure non-degeneracy). Here, quantifier elimination gives the exact and deterministic characterization of the answer to the quantified statement -- and it is this property that motivates its study. We trust at this point that the motivation has been sufficiently belaboured.

It is known that first-order theories with QE (that is, decidability for the theory can be reduced to the question of satisfaction of quantifier-free sentence in the theory) are model complete. In the interest of not straying too far, we leave it to the reader to believe or convince themselves that this is a desirable property. While this is not the focus of how we define \omy in this course, a structure is indeed \om exactly if every formula given by no more than one free variable and some subset of $M$-parameters is equivalent to a quantifier-free formula defined only by these parameters, and the ordering on the structure \cite{marker_model_2002}. Thus, for anyone finding themselves perhaps unconvinced upfront of the merit of some of the ideas explored here (outside the Pila-Wilkie Theorem), we hope this motivates the sequence we are about to take on. And for everyone else, we hope that this section did not bore you too thoroughly.


\subsubsection{Preliminary Definitions}
\label{sec:prelim-defns}
Throughout, we will be working with models $ \M = \Mlt$ of the theory of dense linear orders (DLO) \emph{without endpoints}. For now, $M$ will be fixed, but we will look at some specific instances later on. Perhaps then, one of the most important definitions, to begin with, is that of \emph{definability}.

%\begin{definition}[Definability of sets (without parameters) \cite{marker_basic_2002}]
\begin{definition}[Definability of sets (without parameters)]
For $n \in \N$, we say a set $A \subseteq M^n$ is \emph{definable without parameters} if there exists some formula in our language, $ \phi$, satisfied exactly by the elements of $A$.
\end{definition}

%\begin{definition}[Definability of sets \cite{marker_basic_2002}]
\begin{definition}[Definability of sets]
For $X \subseteq M$ and $n \in \N$, then we say a set $A \subseteq M^n$ is \emph{definable with parameters from $X$} if there exists some formula in our language, $ \phi$, and elements $b_1, \hdots, b_m$, such that $ \phi$ is satisfied exactly by the elements of $A$ along with the parameters in $X$.
\end{definition}

Notice then that definability without a parameter is simply the case of definability with parameters coming from the empty set. These definitions immediately and naturally induce the idea of definable functions and definable points. In particular, a function is definable in parameters if its graph is definable by those same parameters in $\M = \Mlt$. Similarly, an element $a$ is definable in $\M$ (with parameters) if the singleton $\{a\}$ is definable in $ \M$ by those same parameters. This isn't something we will need to consider too extensively.

When introduced to a novel space, we are often interested in what its open intervals look like. We have the following characterization:

\begin{definition}[Open Interval]
  A set, $A \subset M$ is an open interval in $\Mlt$ if $A$ is of one of the following forms:
  \begin{itemize}
    \item $(a, b)$ with $a < b \in M$
    \item $(- \infty, a)$ with $a \in M$
    \item $(a, \infty)$ with $a \in M$
  \end{itemize}
\end{definition}

We say further that intervals of the first type — that is, those having finite bounds — are \emph{bounded}. Easy to miss but important to note is that the endpoints must sit inside our domain. So, for example, in $(\Q, <)$, the set $(-5, \sqrt{7})$ is \emph{not} an open interval.

We imbue $M$ with the order topology and $M^n$ with the product topology. We then define what it means to be an \om expansion.

\begin{definition}[\Om expansion]
  Taking $\mathcal{M} = \Mltp$ an expansion of $\Mlt$, we say $\mathcal{M}$ is \om if every definable (with parameters) subset of $M$ is given by a finite union of open intervals and points.
\end{definition}

\begin{svgraybox}
  If we weaken the above and ask only for \emph{convex} sets (which are a superset of our open intervals) in place of open intervals, then the above would define \emph{weak \omy} — but that won't be a topic of discussion here.
\end{svgraybox}

For the etymologically inclined, it is noted that the `o' in \om comes from the shortening of `order-minimality'. For more information on the history and development of the idea of \omy, one may reference
\textit{Tame Topology \& \Om Structures} \cite{dries_tame_1998} or \textit{Definable Sets in Ordered Structures I} \cite{pillay_definable_1986} and \textit{II} \cite{knight_definable_1986}.


Some (arguably) simple examples of \om structures are given by expansions of the real field. Consider, for example, $\overline{\R} = (\R, <, +, -, \cdot, 0, 1)$ and the further expansion $\R_{\textrm{exp}} = (\overline{\R}, \exp)$, both of which are \om. Mind not to mistake the use of `simplicity' as an indication that these are trivial or did not require particular and considerable consideration — rather, just that they have a relatively simple-seeming form. We fix $\M$ an \om structure and move on to our first theorem for now and in the future.