% AUTOGENERATED FILE; you probably want to edit the .tex.in file, not this.
\documentclass{article}
\usepackage[utf8]{inputenc}
\pagestyle{headings}
\usepackage{amssymb,amsmath,enumerate,amsthm,url}
\usepackage[all,cmtip]{xy}
\usepackage{graphicx}
\usepackage[numbers]{natbib}
\usepackage{bibentry}
\usepackage{hyperref}
\providecommand{\Dashv}{\mathrel{\text{\reflectbox{$\vDash$}}}}
\providecommand{\eqnref}[1]{(\ref{e:#1})}
\providecommand{\secref}[1]{\S\ref{s:#1}}
\providecommand{\mapsfrom}{\mathrel{\reflectbox{\ensuremath{\mapsto}}}}
\bibliographystyle{alpha}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem*}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem*{lemma*}{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\newtheorem*{fact*}{Fact}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem*{corollary*}{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem*{claim*}{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{definition*}{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem*{notation*}{Notation}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem{example}[theorem]{Example}
\newtheorem*{example*}{Example}
\newtheorem{note}[theorem]{Note}
\newtheorem*{note*}{Note}
\newtheorem{question}[theorem]{Question}
\newtheorem*{question*}{Question}
\setlength{\paperheight}{150cm}
\usepackage[left=120px,right=120px,top=10px,bottom=10px]{geometry}
\begin{document}

\title{Pseudofinite dimension and measure in pseudofinite fields}
\author{Martin Bays}
\date{19.05.2021}
\maketitle

\tableofcontents

\newcommand{\fin}{{\operatorname{fin}}}
\newcommand{\tp}{{\operatorname{tp}}}
\newcommand{\alg}{{\operatorname{alg}}}
\newcommand{\Gal}{{\operatorname{Gal}}}
\newcommand{\Zar}{{\operatorname{Zar}}}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\M}{\mathcal{M}}

\let\polL\L
\renewcommand{\L}{\mathcal{L}}

\newcommand{\Los}{\polL{}o\'s}

\newcommand*{\fa}[1]{\forall#1.\;}
\newcommand*{\ex}[1]{\exists#1.\;}
\newcommand*{\fasup}[2]{\forall^{#1}#2.\;}
\newcommand*{\exsup}[2]{\exists^{#1}#2.\;}

\newcommand*{\defn}[1]{\textbf{#1}}

\section{Preliminaries}
\subsection{Notation}
\begin{itemize}\item $\L := \{+,\cdot\}$.
\item $x,y,z,a,b,c,\ldots $ denote tuples.
\item $|x|$ denotes the length of the tuple $x$.
\item $M^x := M^{|x|}$.
\end{itemize}

\subsection{Pseudofinite cardinality}
\begin{definition}
    If $\U$ is an ultrafilter on a set $I$
    and $(X_i)_{i \in I}$ are finite sets,
    we define the \defn{pseudofinite cardinality} of the ultraproduct by
    $$\left|{\prod_{i \rightarrow  \U} X_i}\right| := \lim_{i \rightarrow  \U} |X_i| \in \N^\U. $$

    In particular, if $\M_i$ are finite $\L$-structures and $\phi(x,y)$ is an $\L$-formula,
    and $b_i \in (\M_i)^y$, then
    $$\left|{\phi(\prod_{i \rightarrow  \U} \M_i, \lim_{i \rightarrow  \U} b_i)}\right| =
    \lim_{i\rightarrow \U} |\phi(\M_i,b_i)|.$$
\end{definition}

\section{Chatzidakis - van den Dries - Macintyre}
\subsection{Finitary version}
\begin{theorem}[Chatzidakis - van den Dries - Macintyre] \label{t:cdmfin}
    Let $\phi(x,y)$ be an $\L$-formula.
    Then there are
    \begin{itemize}\item $C \in \R_{>0}$,
    \item $G \subseteq_{\fin}  (\{0,\ldots ,|x|\} \times \Q_{>0}) \cup \{(0,0)\}$, and
    \item $\L$-formulas $(\theta_{\phi,d,m}(y))_{(d,m) \in G}$,
    \end{itemize}
    such that for any finite field $\F_q$,
    \begin{itemize}\item $\F_q \vDash  \fa y \bigvee_{(d,m) \in G} \theta_{\phi,d,m}(y)$
    \item for each $(d,m) \in G$,
    for $b \in (\F_q)^y$,
    $$ \F_q \vDash  \theta_{\phi,d,m}(b) \\\Leftrightarrow  \left|{| \phi(\F_q,b) | - mq^d}\right| \leq  Cq^{d-\frac12} $$
    \end{itemize}
\end{theorem}

\subsection{Asymptotic version}
To prove Theorem~\ref{t:cdmfin},
it suffices to prove it with ``for any finite field'' replaced by ``for all 
sufficiently large finite fields''.
Indeed, we can then increase $C$ and modify the $\theta_{\phi,d,m}$ to 
handle the finitely many remaining finite fields.

\emph{Explicitly: to deal with fields of size $\leq q_0$,
set
\begin{itemize}\item $C' := \max(C, q_0^{|x|+\frac12}+1)$,
so $|\phi(\F_{q_0},b)| \leq  q_0^{|x|} \leq  C'q_0^{-\frac12}$;
\item $\theta'_{\phi,0,0}(y) := \theta_{\phi,0,0}(y) \vee \exsup{\leq q_0}x x=x$;
\item $\theta'_{\phi,d,m}(y) := \exsup{>q_0}x x=x \wedge \theta_{\phi,d,m}(y)$
for $(d,m) \neq  (0,0)$.
\end{itemize}
}

\subsection{Pseudofinite version}

By \Los, this asymptotic statement is equivalent to the following, which 
we will prove using the model theory of pseudofinite fields.

\begin{theorem}[CDM, pseudofinite version] \label{t:cdmpsf}
    Let $\phi(x,y)$ be an $\L$-formula.

    Then there are
    \begin{itemize}\item $C \in \R$,
    \item $G \subseteq_{\fin}  (\{0,\ldots ,|x|\} \times \Q_{>0}) \cup \{(0,0)\}$, and
    \item $\L$-formulas $(\theta_{\phi,d,m}(y))_{(d,m) \in G}$,
    \end{itemize}
    such that for any infinite ultraproduct of finite fields $F$,
    \begin{itemize}\item $F \vDash  \fa y \bigvee_{(d,m) \in G} \theta_{\phi,d,m}(y)$
    \item for each $(d,m) \in G$,
    for $b \in F^y$,
    $$ F \vDash  \theta_{\phi,d,m}(b) \;\Leftrightarrow \; \left|{| \phi(F,b) | - m|F|^d}\right| \leq  C|F|^{d-\frac12} $$
    \end{itemize}
\end{theorem}

\begin{remark*}
    Given $b \in F^y$, we can recover the corresponding $d,m$ from $N := 
    |\phi(F,b)|$ as
    $$ d = \operatorname{st}(\log_{|F|}(N));\; m = \operatorname{st}\left({\frac N{|F|^d}}\right).$$

    Hence the $\theta_{\phi,d,m}(y)$ are pairwise inconsistent, so form a partition.
\end{remark*}
\begin{remark*}
    In fact $d = \dim(\phi(F,b)^\Zar)$. We will see that this falls out of the proof.
\end{remark*}
\begin{remark*}
    $|\phi(F,b)| < (m+1)|F|^d$ since $|F|^{\frac12} > \R \ni C$.
\end{remark*}
\begin{remark*}
    Let $F \vDash  \operatorname{Psf}$ and $b \in F^y$.

    If $F$ is not an ultraproduct of finite fields, then $|F|$ and $|\phi(F,b)|$ are undefined.

    But $F$ is elementarily equivalent to an ultraproduct of finite fields,
    \\so $b \vDash  \theta_{\phi,d,m}(y)$ for some unique $(d,m) \in G$,
    \\so this assigns a well-defined dimension and measure to $\phi(F,b)$.
\end{remark*}

\subsection{``Local'' version}

Since an ultraproduct of ultraproducts of finite fields is an ultraproduct of finite fields,
Theorem~\ref{t:cdmpsf} is in turn equivalent to:

\begin{theorem}[CDM, local version] \label{t:cdmpsfloc}
    Let $\phi(x,y)$ be an $\L$-formula.

    Let $F$ be an infinite ultraproduct of finite fields, and let $b \in F$.
    Then there are
    \begin{itemize}\item $(C,d,m) \in \R \times (\{0,\ldots ,|x|\} \times \Q_{>0} \cup \{(0,0)\})$ 
    and
    \item an $\L$-formula $\theta(y) \ni \tp^F(b)$ such that:
    \end{itemize}
    \begin{align*} \label{a:estimate}
        \tag{*}
        \text{for any }&\text{infinite ultraproduct of finite fields $F'$ and any $b' \in F'$,}
        \\ &F' \vDash  \theta(b') \;\Rightarrow \; \left|{| \phi(F',b') | - m|F'|^d}\right| \leq  C|F'|^{d-\frac12}
    \end{align*}
\end{theorem}

\begin{proof}[Sketch proof of Theorem~\ref{t:cdmpsf} from Theorem~\ref{t:cdmpsfloc}] \mbox{}
    \begin{itemize}\item Let $\Xi \subseteq  \N \times \{0,\ldots ,|x|\} \times \Q_{>0} \cup \{(0,0)\} \times \L$ be the set of 4-tuples $(C,d,m,\theta)$ satisfying (\ref{a:estimate}).
    \item Theorem~\ref{t:cdmpsf} asserts that for some finite subset of $\Xi$,
    the corresponding $\theta$ cover any $F$.
    (We use here the disjointness of the $\theta$ for distinct pairs $(d,m)$.)
    % (Indeed, then take the disjunction of the corresponding theta if there are 
    % repetitions of any $(d,m)$, and take the max of the finitely many $C$. We 
    % get $\Leftrightarrow $ rather than just $\Rightarrow $, because of the remark that distinct 
    % $(d,m)$ must be disjoint.)
    \item If not, taking an ultraproduct over finite subsets of $\Xi$ of 
    counterexamples $b \in F$,
    we obtain $b^* \in F^*$ for which $F^* \vDash  \neg\theta(b^*)$ for any $(C,d,m,\theta) \in \Xi$,
    contradicting Theorem~\ref{t:cdmpsfloc}.
    \end{itemize}
\end{proof}

\section{Proof}
We prove Theorem~\ref{t:cdmpsfloc}.
So let $\phi(x,y)$ be an $\L$-formula.

Let $F$ be an infinite ultraproduct of finite fields,
and let $b \in F^y$.

We consider a series of increasingly complicated cases for the definable set 
$\phi(F,b)$,
and in each case we find $C,d,m,\theta$ as required.

\subsection{Case 1: $\phi(F,b) = V(F)$, $V$ absolutely irreducible.}

\newcommand{\ff}{\overline f}
\newcommand{\calV}{\mathcal V}
\begin{fact}
    Let $\ff(x,y) = (f_i(x,y))_{i<m}$ be polynomials over $\Z$,
    and let $d \in \N$.
    Then there is a quantifier-free ring formula $A_{\ff,d}(y)$
    such that for any field $F$ and $b \in F^y$,
    $$ F \vDash  A_{\ff,d}(b) \;\Leftrightarrow \; \calV(\ff(x,b))) \text{ is absolutely irreducible of dimension $d$.}$$
\end{fact}

\begin{fact}[Lang-Weil]
    There is a function $C_{LW} : \N^2 \rightarrow  \R$ such that
    %Given $n,d \in \N$,
    %there exists $C \in \R$ such that
    if $\F_q$ is a finite field
    and $W$ is an absolutely irreducible variety defined by polynomials in 
    $\F_q[X_1,\ldots ,X_n]_{\leq D}$,
    $$\left|{|W(\F_q)| - q^{\dim(W)}}\right| \leq  C_{LW}(n,D)q^{\dim(W)-\frac12}.$$
\end{fact}

We deduce:
\begin{lemma}
    If $F = \prod_{i\rightarrow \U} \F_{q_i}$ is an infinite ultraproduct of finite fields
    and $W$ is an absolutely irreducible variety defined by polynomials in 
    $F[X_1,\ldots ,X_n]_{\leq D}$,
    $$\left|{|W(F)| - |F|^{\dim(W)}}\right| \leq  C_{LW}(n,D)|F|^{\dim(W)-\frac12}.$$
\end{lemma}
\begin{proof} \mbox{}
    \begin{itemize}\item Say $W = \calV(\ff(x,c))$ where $f_i \in \Z(x,y)$ and $c = \lim_{i\rightarrow \U}c_i \in F^y$.

    \item Let $d := \dim W$.

    \item By \Los, the following holds for $\U$-many $i$:
    \begin{itemize}\item\; $\F_{q_i} \vDash  A_{\ff,d}(c_i)$; hence
    \item\; $W_i := \calV(\ff(x,c_i))$ is absolutely irreducible of dimension $d$; hence
    \item\; $\left|{|W_i(\F_{q_i})| - q_i^{\dim(W)}}\right| \leq  C_{LW}(n,D)q_i^{\dim(W)-\frac12}.$
    \end{itemize}

    \item We conclude since
    $|W(F)| = \lim_{i\rightarrow \U} |W_i(\F_{q_i})|$ and $|F| = \lim_{i\rightarrow \U} q_i$.
    \end{itemize}
\end{proof}

Now suppose $\phi(F,b) = V(F)$ for an absolutely irreducible variety 
$V = \calV(\ff(x,c))$ where $f_i(x,y)$ has degree $\leq D$ in $x$ and $c \in F^y$.

Then we can take:
\begin{itemize}\item $C := C_{LW}(|x|,D)$,
\item $d := \dim(V)$,
\item $m := 1$,
\item $\theta(y) :=
\ex z ( A_{\ff,d}(z) \wedge \fa x (\phi(x,y) \leftrightarrow  x \in \calV(\ff(x,z))) )$.
\end{itemize}

\subsection{Case 2: $\phi(F,b) = V(F)$}

\begin{itemize}\item Suppose $\phi(F,b) = V(F)$ where $V$ is a Zariski-closed set.
\item Replacing $V$ with the Zariski closure of $V(F)$,
we may assume that $V(F)$ is Zariski dense in $V$.
\item $V$ has an irreducible decomposition $V = \bigcup_{i<n} V_i$ where $V_i$ is 
an absolutely irreducible variety, and $V_i \not\subseteq  V_j$ for $i\neq j$.
\item We show that our estimate on $|V(F)|$ holds with
    \begin{align*} d &:= \dim V = \max_i \dim(V_i)
    \\ m &:= | \{ i : \dim(V_i) = d \} |.
    \end{align*}
\item Since $V(F) = \bigcup_i V_i(F)$ is Zariski-dense in $V$,
also $V_i(F)$ is Zariski-dense in $V_i$ for all $i$.
\item So each $V_i$ is $F$-invariant, and $F$ is perfect, so each $V_i$ is defined over $F$.
\item Any intersection of two or more of the $V_i$ has dimension $< d$.
\item By inclusion-exclusion,
    $$ | \phi(F,b) | = \left|{\bigcup_i V_i(F)}\right| = \sum_{ \emptyset  \neq  I \subseteq  n } (-1)^{|I| - 1} \left|{\left({\bigcap_{i \in I} V_i}\right)(F)}\right| = \sum_i |V_i(F)| + \ldots $$
\item Applying Case 1 to the $V_i$, and inductively applying the present case to the lower dimensional intersections, we conclude:
\[ \left|{\phi(F,b) - m|F|^d}\right| \leq 
\sum_{i<m} C_i |F|^{d-\frac12} + C' |F|^{d-1} \leq  C|F|^{d-\frac12},\]
where $C' \in \R$ is large enough to bound the terms in the inclusion-exclusion 
formula arising from the finitely many lower dimensional $V_i$ and the 
intersections of two or more $V_i$,
and setting $C := \sum_{i<m} C_i + 1$ (and using $|F|^{\frac12} > \R \ni C'$).

\item Set
\begin{align*} \theta(y) := \ex{y_0,\ldots ,y_{n-1}} (&(\fa x \phi(x,y) \leftrightarrow  \bigvee_{i<n} \psi_i(x,y_i) )\\
& \wedge \bigwedge_i \theta_i(y_i)\\
& \wedge \bigwedge_{I \subseteq  n, |I| \geq  2} \theta_I((y_i)_{i \in I})) ,\end{align*}
where
    \begin{itemize}\item $V_i(F) = \psi_i(F,b_i)$,
    \item $\theta_i$ are as in Case 1 for $\psi_i$,
    \item $\theta_I$ are obtained by inductive application of the present case to $\bigwedge_{i \in I} \psi_i(x,y_i)$.
    \end{itemize}
\item Note that we do have $d = \dim(\phi(F,b)^\Zar)$ in this case.
\end{itemize}

\subsection{Case 3: $\phi(F,b) = X(F)$, $X$ constructible}
(\emph{Constructible} means: boolean combination of Zariski-closed.)
\begin{itemize}\item
Intersecting with $X(F)^\Zar$, we can assume $X(F)$ is Zariski-dense in $X$.
\item We can write $X$ as a disjoint union $X = \dot\bigcup_i V_i \setminus W_i$ where 
$V_i$ is absolutely irreducible and $W_i \subsetneq  V_i$ is a proper closed subset.
\item Set $d := \max_i \dim(V_i) = \dim(X(F)^\Zar)$ and $m := |\{ i : \dim(V_i) = d \}|$.
\item \[ |X(F)| = \sum_i (|V_i(F)| - |W_i(F)|),\]
so the estimate follows by applying Case 2 to each $V_i$ and $W_i$,
\\using $\dim(W_i) < d$ and the Zariski density of $V_i(F)$ in $V_i$.

\emph{(Note: we could alternatively use the Rabinovich trick here.)}

\emph{(Alternative alternative (thanks to Martin Hils for suggesting this): 
note that $X^{\Zar} \setminus X$ is constructible of lower dimension; use this case 
inductively to handle it, and Case 2 for $X^{\Zar}$ (in which $F$-points are 
Zariski-dense).)}

\item $\theta$ expresses that this decomposition and the estimates for the various terms hold.
\end{itemize}

\subsection{Case 4: $\phi(F,b) = X(F)$ arbitrary}
\begin{itemize}\item Recall: there exists a Zariski-closed set $V$ over $F$ and a co-ordinate 
projection $\pi$ such that $\pi_F := \pi|_{V(F)} : V(F) \twoheadrightarrow  X(F)$ is 
surjective with boundedly finite fibres.

\item So we have a definable partition $X(F) = \dot\bigcup_{1 \leq  n \leq  M} X_n(F)$ 
where
$$X_n(F) := \{ a \in X(F) : |\pi_F^{-1}(a)| = n \}.$$

\item We may assume that $V(F)$ is Zariski-dense in $V$.

\item Consider the constructible sets
$$W_k := \{ (x_1,\ldots ,x_k) : x_i \in V,\; \pi(x_i) = \pi(x_j),\; x_i \neq  x_j\; (\forall i\neq j) \} \subseteq  V^k,$$
and maps $$\pi_{k,F} : W_k(F) \rightarrow  X(F);\; (x_1,\ldots ,x_k) \mapsto  \pi(x_1).$$

\item For $a \in X_n(F)$ and $1 \leq  n,k \leq  M$,
$$ |\pi_{k,F}^{-1}(a)| = P_{kn} =
\begin{cases}
    \frac{n!}{(n-k)!} & (k \leq  n) \\
    0                 & (k > n)
\end{cases}
.$$

\item Now the matrix $P$ is lower triangular, and non-zero on the diagonal,
\\so $P$ has an inverse $P^{-1} \in \operatorname{GL}_M(\Q)$.
$$ |W_k(F)| = \sum_{1\leq n\leq M} P_{kn} |X_n(F)| ,$$
hence
$$ |X_n(F)| = \sum_{1\leq k\leq M} (P^{-1})_{nk} |W_k(F)| .$$

\item Now \[ |X(F)| = \sum_{1\leq n\leq M} |X_n(F)|.\]
By Case 3 we can estimate $|W_k(F)|$ with $(d_k,m_k)$ say,
\\so we obtain our estimate for $|X(F)|$ with
\begin{align*} d &:= \max_i d_i
\\ m &:= \sum_{\{(n,k) \;:\; d_k = d\}} (P^{-1})_{nk} m_k \in \Q .\end{align*}
\item $\theta(y)$ expresses that $\phi(F,y)$ is a projection of $V^y(F)$ with 
fibres bounded by $M$, and the estimate works for the corresponding $|W_k^y(F)|$ 
(which we can express by Case 3).

\item To see $d=\dim(X(F)^\Zar)$:
\begin{itemize}\item Recall $V = V(F)^\Zar$.

\item From the way $V$ was obtained, $\pi : V \rightarrow  X(F)^\Zar$ has finite fibres on 
$X(F)$, so also each $\pi_k : W_k \rightarrow  X(F)^\Zar$ has generically finite 
fibres.

\item Then $d_1 = \dim(V) = \dim(X(F)^\Zar)$ and $d_k \leq  \dim(W_k) \leq  
\dim(X(F)^\Zar)$.
\item So $d = \dim(X(F)^\Zar)$.
\end{itemize}
\end{itemize}

\end{document}
