\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

!newop fin
!newop tp
!newop alg
!newop Gal
!newop Zar

!newbb N
!newbb Q
!newbb R
!newbb Z
!newbb F
!newcal U
!newcal M

\let\polL\L
!renewcal 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}}

# Preliminaries
## Notation
***) $\L := \{+,\cdot\}$.
** $x,y,z,a,b,c,...$ denote tuples.
** $|x|$ denotes the length of the tuple $x$.
** $M^x := M^{|x|}$.
*e)*

## Pseudofinite cardinality
Definition:
    If $\U$ is an ultrafilter on a set $I$
    and $(X_i)_{i (- I}$ are finite sets,
    we define the \defn{pseudofinite cardinality} of the ultraproduct by
    $$|{ \prod_{i --> \U} X_i }| := \lim_{i --> \U} |X_i| (- \N^\U. $$

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

# Chatzidakis - van den Dries - Macintyre
## Finitary version
Theorem[Chatzidakis - van den Dries - Macintyre]{cdmfin}:
    Let $\phi(x,y)$ be an $\L$-formula.
    Then there are
    ***) $C (- \R_{>0}$,
    ** $G (=f (\{0,...,|x|\} \times \Q_{>0}) \cup \{(0,0)\}$, and
    ** $\L$-formulas $(\theta_{\phi,d,m}(y))_{(d,m) (- G}$,
    *e)*
    such that for any finite field $\F_q$,
    ***) $\F_q |= \fa y \\//_{(d,m) (- G} \theta_{\phi,d,m}(y)$
    ** for each $(d,m) (- G$,
    for $b (- (\F_q)^y$,
    $$ \F_q |= \theta_{\phi,d,m}(b) \\\<=> |{ | \phi(\F_q,b) | - mq^d }| <= Cq^{d-\frac12} $$
    *e)*
    .

## Asymptotic version
To prove Theorem~{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 $<=q_0$,
set
***) $C' := \max(C, q_0^{|x|+\frac12}+1)$,
so $|\phi(\F_{q_0},b)| <= q_0^{|x|} <= C'q_0^{-\frac12}$;
** $\theta'_{\phi,0,0}(y) := \theta_{\phi,0,0}(y) \/ \exsup{<=q_0}x x=x$;
** $\theta'_{\phi,d,m}(y) := \exsup{>q_0}x x=x /\ \theta_{\phi,d,m}(y)$
for $(d,m) != (0,0)$.
*e)*
}

## Pseudofinite version

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

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

    Then there are
    ***) $C (- \R$,
    ** $G (=f (\{0,...,|x|\} \times \Q_{>0}) \cup \{(0,0)\}$, and
    ** $\L$-formulas $(\theta_{\phi,d,m}(y))_{(d,m) (- G}$,
    *e)*
    such that for any infinite ultraproduct of finite fields $F$,
    ***) $F |= \fa y \\//_{(d,m) (- G} \theta_{\phi,d,m}(y)$
    ** for each $(d,m) (- G$,
    for $b (- F^y$,
    $$ F |= \theta_{\phi,d,m}(b) \;<=>\; |{ | \phi(F,b) | - m|F|^d }| <= C|F|^{d-\frac12} $$
    *e)*
    .

Remark*:
    Given $b (- F^y$, we can recover the corresponding $d,m$ from $N := 
    |\phi(F,b)|$ as
    $$ d = \"st(\log_{|F|}(N));\; m = \"st({ \frac N{|F|^d} }).$$

    Hence the $\theta_{\phi,d,m}(y)$ are pairwise inconsistent, so form a partition.
    .
Remark*:
    In fact $d = \dim(\phi(F,b)^\Zar)$. We will see that this falls out of the proof.
    .
Remark*:
    $|\phi(F,b)| < (m+1)|F|^d$ since $|F|^{\frac12} > \R -) C$.
    .
Remark*:
    Let $F |= \"Psf$ and $b (- 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 |= \theta_{\phi,d,m}(y)$ for some unique $(d,m) (- G$,
    \\\so this assigns a well-defined dimension and measure to $\phi(F,b)$.
    .

## ``Local'' version

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

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

    Let $F$ be an infinite ultraproduct of finite fields, and let $b (- F$.
    Then there are
    ***) $(C,d,m) (- \R \times (\{0,...,|x|\} \times \Q_{>0} \cup \{(0,0)\})$ 
    and
    ** an $\L$-formula $\theta(y) -) \tp^F(b)$ such that:
    *e)*
    Align*{estimate}:
        \tag{*}
        \text{for any }&\text{infinite ultraproduct of finite fields $F'$ and any $b' (- F'$,}
        \\\ &F' |= \theta(b') \;=>\; |{ | \phi(F',b') | - m|F'|^d }| <= C|F'|^{d-\frac12}
        .
    .

Proof[Sketch proof of Theorem~{cdmpsf} from Theorem~{cdmpsfloc}]:--
    ***) Let $\Xi (= \N \times \{0,...,|x|\} \times \Q_{>0} \cup \{(0,0)\} \times \L$ be the set of 4-tuples $(C,d,m,\theta)$ satisfying (\ref{a:estimate}).
    ** Theorem~{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 $<=>$ rather than just $=>$, because of the remark that distinct 
    % $(d,m)$ must be disjoint.)
    ** If not, taking an ultraproduct over finite subsets of $\Xi$ of 
    counterexamples $b (- F$,
    we obtain $b^* (- F^*$ for which $F^* |= \neg\theta(b^*)$ for any $(C,d,m,\theta) (- \Xi$,
    contradicting Theorem~{cdmpsfloc}.
    *e)*
    .

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

Let $F$ be an infinite ultraproduct of finite fields,
and let $b (- 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.

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

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

Fact[Lang-Weil]:
    There is a function $C_{LW} : \N^2 --> \R$ such that
    %Given $n,d (- \N$,
    %there exists $C (- \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,...,X_n]_{<=D}$,
    $$|{ |W(\F_q)| - q^{\dim(W)} }| <= C_{LW}(n,D)q^{\dim(W)-\frac12}.$$
    .

We deduce:
Lemma:
    If $F = \prod_{i-->\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,...,X_n]_{<=D}$,
    $$|{ |W(F)| - |F|^{\dim(W)} }| <= C_{LW}(n,D)|F|^{\dim(W)-\frac12}.$$
    .
Proof:--
    ***) Say $W = \calV(\ff(x,c))$ where $f_i (- \Z(x,y)$ and $c = \lim_{i-->\U}c_i (- F^y$.

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

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

    ** We conclude since
    $|W(F)| = \lim_{i-->\U} |W_i(\F_{q_i})|$ and $|F| = \lim_{i-->\U} q_i$.
    *e)*
    .

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

Then we can take:
***) $C := C_{LW}(|x|,D)$,
** $d := \dim(V)$,
** $m := 1$,
** $\theta(y) :=
\ex z ( A_{\ff,d}(z) /\ \fa x (\phi(x,y) <-> x (- \calV(\ff(x,z))) )$.
*e)*

## Case 2: $\phi(F,b) = V(F)$

***) Suppose $\phi(F,b) = V(F)$ where $V$ is a Zariski-closed set.
** Replacing $V$ with the Zariski closure of $V(F)$,
we may assume that $V(F)$ is Zariski dense in $V$.
** $V$ has an irreducible decomposition $V = \bigcup_{i<n} V_i$ where $V_i$ is 
an absolutely irreducible variety, and $V_i (/= V_j$ for $i/=j$.
** We show that our estimate on $|V(F)|$ holds with
    *\[a* d &:= \dim V = \max_i \dim(V_i)
    \\\ m &:= | \{ i : \dim(V_i) = d \} |.
    *a\]*
** 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$.
** So each $V_i$ is $F$-invariant, and $F$ is perfect, so each $V_i$ is defined over $F$.
** Any intersection of two or more of the $V_i$ has dimension $< d$.
** By inclusion-exclusion,
    $$ | \phi(F,b) | = |{ \bigcup_i V_i(F) }| = \sum_{ {} != I (= n } (-1)^{|I| - 1} |{ ({ \bigcap_{i (- I} V_i })(F) }| = \sum_i |V_i(F)| + ...$$
** Applying Case 1 to the $V_i$, and inductively applying the present case to the lower dimensional intersections, we conclude:
\[ |{ \phi(F,b) - m|F|^d }| <=
\sum_{i<m} C_i |F|^{d-\frac12} + C' |F|^{d-1} <= C|F|^{d-\frac12},\]
where $C' (- \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 -) C'$).

** Set
*\[a* \theta(y) := \ex{y_0,...,y_{n-1}} (&(\fa x \phi(x,y) <-> \\//_{i<n} \psi_i(x,y_i) )\\\
& /\ //\\_i \theta_i(y_i)\\\
& /\ //\\_{I (= n, |I| >= 2} \theta_I((y_i)_{i (- I})) ,*a\]*
where
    ***) $V_i(F) = \psi_i(F,b_i)$,
    ** $\theta_i$ are as in Case 1 for $\psi_i$,
    ** $\theta_I$ are obtained by inductive application of the present case to $//\\_{i (- I} \psi_i(x,y_i)$.
    *e)*
** Note that we do have $d = \dim(\phi(F,b)^\Zar)$ in this case.
*e)*

## Case 3: $\phi(F,b) = X(F)$, $X$ constructible
(\emph{Constructible} means: boolean combination of Zariski-closed.)
***)
Intersecting with $X(F)^\Zar$, we can assume $X(F)$ is Zariski-dense in $X$.
** We can write $X$ as a disjoint union $X = \dot\bigcup_i V_i \\ W_i$ where 
$V_i$ is absolutely irreducible and $W_i (!= V_i$ is a proper closed subset.
** Set $d := \max_i \dim(V_i) = \dim(X(F)^\Zar)$ and $m := |\{ i : \dim(V_i) = d \}|$.
** \[ |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} \\ 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).)}

** $\theta$ expresses that this decomposition and the estimates for the various terms hold.
*e)*

## Case 4: $\phi(F,b) = X(F)$ arbitrary
***) 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) -->> X(F)$ is 
surjective with boundedly finite fibres.

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

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

** Consider the constructible sets
$$W_k := \{ (x_1,...,x_k) : x_i (- V,\; \pi(x_i) = \pi(x_j),\; x_i /= x_j\; (\forall i/=j) \} (= V^k,$$
and maps $$\pi_{k,F} : W_k(F) --> X(F);\; (x_1,...,x_k) |-> \pi(x_1).$$

** For $a (- X_n(F)$ and $1 <= n,k <= M$,
$$ |\pi_{k,F}^{-1}(a)| = P_{kn} =
Cases:
    \frac{n!}{(n-k)!} & (k <= n) \\\
    0                 & (k > n)
    .
.$$

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

** Now \[ |X(F)| = \sum_{1<=n<=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
*\[a* d &:= \max_i d_i
\\\ m &:= \sum_{\{(n,k) \;:\; d_k = d\}} (P^{-1})_{nk} m_k (- \Q .*a\]*
** $\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).

** To see $d=\dim(X(F)^\Zar)$:
***) Recall $V = V(F)^\Zar$.

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

** Then $d_1 = \dim(V) = \dim(X(F)^\Zar)$ and $d_k <= \dim(W_k) <= 
\dim(X(F)^\Zar)$.
** So $d = \dim(X(F)^\Zar)$.
*e)*
*e)*

\end{document}
