\section{#1}\setcounter{equation}{0}}
\newcommand{\subsect}[1]{\subsection{#1}}
\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\font\mbn=msbm10 scaled \magstep1
\font\mbs=msbm7 scaled \magstep1
\font\mbss=msbm5 scaled \magstep1
\newfam\mbff
\textfont\mbff=\mbn
\scriptfont\mbff=\mbs
\scriptscriptfont\mbff=\mbss\def\fam\mbff{\fam\mbff}
\def{\mbf T}{{\fam\mbff T}}
\def{\mbf P}{{\fam\mbff P}}
\def{\mbf F}{{\fam\mbff F}}

\newcommand{{\mbf D}}      {\mathbb{D}}
\newcommand{{\mbf R}}       { \mathbb{R}}
\newcommand{\cH}      {{\mathcal H}}
\newcommand{\cP}      {{\mathcal P}}
\newcommand{{\mbf N}}       { \mathbb{N}}
\newcommand{{\mbf Z}}        {\mathbb{Z}  }
\newcommand{\mbf C}           {{\mathbb C}}
\newcommand {\mbf Q}             {{\mathbb Q}}
\newtheorem{Th}{Theorem}[section]
\newtheorem{Lm}[Th]{Lemma}
\newtheorem{C}[Th]{Corollary}
\newtheorem{D}[Th]{Definition}
\newtheorem{Proposition}[Th]{Proposition}
\newtheorem{R}[Th]{Remark}
\newtheorem{E}[Th]{Example}
\newtheorem*{RV}{Rolle-Voorhoeve lemma}
\begin{document}
\title[Banach spaces of polynomials]{Banach spaces of polynomials as ``large'' subspaces of ${\mathbf \ell^\infty}$-spaces}

\author{Alexander Brudnyi}
\address{Department of Mathematics and Statistics\newline
\hspace*{1em} University of Calgary\newline
\hspace*{1em} Calgary, Alberta\newline
\hspace*{1em} T2N 1N4}
\email{<EMAIL>}
\keywords{Banach-Mazur compactum,  filtered algebra, entropy}
\subjclass[2010]{Primary 46B20, Secondary 46E15}

\thanks{Research supported in part by NSERC}

\begin{abstract}
In this note we study Banach spaces of traces of real polynomials on $\mathbb R^n$ to compact subsets equipped with supremum norms from the point of view of Geometric Functional Analysis.
\end{abstract}

\date{}

\maketitle

\sect{Main Results}
Recall that the {\em Banach-Mazur distance} between two $k$-dimensional real Banach spaces $E,F$ is defined as
\[
d_{BM}(E,F):=\inf\{\|u\|\cdot\|u^{-1}\|\},
\]
where the infimum is taken over all isomorphisms $u:E\rightarrow F$. We say that $E$ and $F$ are equivalent if they are isometrically isomorphic (i.e., $d_{BM}(E,F)=1$).  Then
$\ln d_{BM}$  determines a metric on the set $\mathcal B_k$ of equivalence classes of isometrically isomorphic $k$-dimensional Banach spaces (called the {\em Banach-Mazur compactum}). It is known that $\mathcal B_k$ is compact of $d_{BM}$-``diameter'' $\sim k$, see \cite{G}.

Let $C(K)$ be the Banach space of real continuous functions on a compact Hausdorff space $K$ equipped with the supremum norm.  Let $F\subset C(K)$ be a filtered subalgebra with filtration $\{0\}\subset F_0\subseteq F_1\subseteq\cdots\subseteq F_d\subseteq\cdots\subseteq F$ (that is, $F=\cup_{d\in{\mbf Z}_+}F_i$ and $F_i\cdot F_j\subset F_{i+j}$ for all $i,j\in{\mbf Z}_+$) such that $n_d:={\rm dim}\, F_d<\infty$ for all $d$.
In what follows we assume that $F_0$ contains constant functions on $K$. Our main result is

\begin{Th}\label{te1}
Suppose there are $c\in\mathbb R$ and $\{p_d\}_{d\in{\mbf N}}\subset{\mbf N}$ such that
\begin{equation}\label{e2}
\frac{\ln n_{d\cdot p_d}}{p_d}\le c\quad\text{for all}\quad d\in{\mbf N}.
\end{equation}
Then there exist linear injective maps $i_d: F_d\hookrightarrow \ell_{n_{d\cdot p_d}}^\infty$ such that
\[
d_{BM}(F_d, i_d(F_d))\le e^{c},\quad d\in\mathbb N.
\]
\end{Th}
As a corollary we obtain:
\begin{C}\label{c1}
Suppose $\{n_d\}_{d\in{\mbf N}}$ grows at most polynomially in $d$, that is,
\begin{equation}\label{eq1.2}
\exists\, k, \hat c\in\mathbb R_+ \ \text{such that}\ \forall\, d\quad n_d\le \hat c d^k.
\end{equation}
Then for each natural number $s\ge 3$ there exist linear injective maps $i_{d,s}: F_d\hookrightarrow \ell_{N_{d,s}}^\infty$, where $N_{d,s}:= \left\lfloor \hat cd^k\cdot s^k\cdot \left(\lfloor\ln(\hat cd^k)\rfloor +1\right)^k\right\rfloor$,  such that
\[
d_{BM}(F_d, i_{d,s}(F_d))\le \left(es^k\right)^{\frac 1s},\quad k\in\mathbb N.
\]
\end{C}
Let $\mathcal F_{\hat c,k}$ be the family of all possible filtered algebras $F$ on compact Hausdorff spaces $K$ satisfying condition \eqref{eq1.2}.
By $\mathcal B_{\hat c, k, \bar n_d}\subset\mathcal B_{\bar n_d}$ we denote the closure in $\mathcal B_{\bar n_d}$ of the set formed by all subspaces $F_d$ of algebras $F\in\mathcal F_{\hat c,k}$
having a fixed dimension $\bar n_d\in\mathbb N$.

Corollary \ref{c1} allows to estimate the metric entropy of $\mathcal B_{\hat c, k, \bar n_d}$. Recall that for a compact subset $S\subset  \mathcal B_{\bar n_{d}}$ its {\em $\varepsilon$-entropy} ($\varepsilon>0$) is defined as
$H(S,\varepsilon):=\ln N(S,d_{BM}, 1+\varepsilon)$,
where $N(S,d_{BM}, 1+\varepsilon)$ is the smallest number of open $d_{BM}$-``balls'' of radius $1+\varepsilon$ that cover $S$.
\begin{C}\label{c2}
For $k\ge 1$ there exists a numerical constant $C$ such that for each $\varepsilon\in (0,\frac{1}{2}]$
\[
H\bigl(\mathcal B_{\hat c, k, \bar n_d},\varepsilon\bigr)\le (Ck\cdot\ln(k+1))^{k}\cdot (\hat cd^{k})^2\cdot (\ln (\hat cd^k)+1)^{k+1}\cdot\left(\frac{1}{\varepsilon}\right)^k\cdot \left(\ln\left(\frac{1}{\varepsilon}\right)\right)^{k+1}.
\]
\end{C}

\sect{Basic Example: Banach Spaces of Polynomials}
Let  $\mathcal P_d^n$ be the space of real polynomials on $\mathbb R^n$ of degree at most $d$.  For a compact subset $K\subset\mathbb R^n$ by $\mathcal P_d^n|_K$ we denote the trace space of restrictions of polynomials in  $\mathcal P_d^n$  to $K$ equipped with the supremum norm. Applying Corollary \ref{c1} to algebra $\mathcal P^n|_K:=\cup_{d\ge 0}\,\mathcal P_d^n|_K$ we obtain:\medskip

\noindent (A) {\em There exist  linear injective maps $i_{d, K}: \mathcal P_d^n|_K\hookrightarrow \ell_{N_{d,n}}^\infty$, where
\begin{equation}\label{ndn}
N_{d,n}:=\left\lfloor e^{2n}\cdot (n+2)^{2n}\cdot d^n\cdot \left(2n+1+\lfloor n\ln d\rfloor\right)^n\right\rfloor,
\end{equation}
such that}
\begin{equation}\label{bmdn}
d_{BM}\left(\mathcal P_d^n|_K, i_{d,K}( \mathcal P_d^n|_K)\right)\le\left(e\cdot (n+2)^2\right)^{\frac{1}{n+2}}\, (< 2.903).
\end{equation}
\smallskip

Indeed,
\begin{equation}\label{ind}
\widetilde N_{d,n}:={\rm dim}\,\mathcal P_d^n|_K\le {d+n \choose n}<\left(\frac{e\cdot (d+n)}{n}\right)^n\le\left(\frac{e\cdot (1+n)}{n}\right)^n\cdot d^n<e^{2n}\cdot d^n.
\end{equation}
Hence, Corollary \ref{c1} with $c=e^{2n}$, $k:=n$ and $s:=(n+2)^2$ implies the required result.\smallskip

If $K$ is $\mathcal P^n$-{\em determining} (i.e., no nonzero polynomial vanish on $K$), then $\widetilde N_{d,n}={d+n \choose n}$ and so for some constant $c(n)$ (depending on $n$ only) we have
\begin{equation}\label{e3.2}
\widetilde N_{d,n}<N_{d,n}\le c(n)\cdot \widetilde N_{d,n}\cdot\bigl(1+\ln\widetilde N_{d,n}\bigr)^n.
\end{equation}
Hence, $V_{d,n}(K):=i_{d,K}( \mathcal P_d^n|_K)$ is a {\em ``large'' subspace} of $\ell_{N_{d,n}}^\infty$ in terminology of \cite{B}. Therefore from (A) and  \cite[Prop.~8]{B} applied to $V_{d,n}(K)$ we obtain:
\medskip

\noindent (B) {\em There is a constant $c_1(n)$ (depending on $n$ only) such that for each $\mathcal P^n$-determining compact set $K\subset\mathbb R^n$ there exists an $m$-dimensional subspace $F\subset \mathcal P_d^n|_K$ with }
\begin{equation}\label{e3.3}
m:={\rm dim}\,F>c_1(n)\cdot\bigl(\widetilde N_{d,n}\bigr)^{\frac 12}\quad\text{ and}\quad
d_{BM}(F,\ell_m^\infty)\le 3.
\end{equation}

{\em In turn, if $\hat d\in{\mbf N}$ is such that $N_{\hat d,n}\le c_1(n)\cdot\bigl(\widetilde N_{d,n}\bigr)^{\frac 12}$, then due to property (A) for each $\mathcal P^n$-determining compact set $K'\subset\mathbb R^n$ there exists a $\widetilde N_{\hat d,n}$-dimensional subspace $F_{\hat d,n,K'}\subset F$ such that}
\begin{equation}\label{star}
d_{BM}\bigl(F_{\hat d,n,K'},\mathcal P_{\hat d}^n|_{K'}\bigr)<9.
\end{equation}
\smallskip

Further, the dual space $(V_{d}^n(K))^*$ of $V_{d}^n(K)$ is the quotient space of $\ell_{N_{d,n}}^1$. In particular, the closed ball of $(V_{d}^n(K))^*$
contains at most $c(n)\cdot \widetilde N_{d,n}\cdot\bigl(1+\ln\widetilde N_{d,n}\bigr)^n$ extreme points, see \eqref{e3.2}. Thus the balls of $(V_{d}^n(K))^*$ and $V_{d}^n(K)$ are ``quite different'' as convex bodies. This is also expressed in the following property (similar to the celebrated John ellipsoid theorem but with an extra logarithmic factor) which is a consequence of property (A) and \cite[Prop.~1]{DMTJ}:
\medskip

\noindent (C) {\em There is a constant $c_2(n)$ (depending on $n$ only) such that for all $\mathcal P^n$-determining compact sets $K_1, K_2\subset\mathbb R^n$}
\begin{equation}\label{e3.4}
d_{BM}\bigl(\mathcal P_d^n|_{K_1},(\mathcal P_d^n|_{K_2})^*\bigr)\le c_2(n)\cdot (\widetilde N_{d,n}\cdot (1+\ln \widetilde N_{d,n}))^{\frac 12}.
\end{equation}
\smallskip

A stronger inequality is valid if we replace $(\mathcal P_d^n|_{K_2})^*$ above by $\ell_{\widetilde N_{d,n}}^1$, see \cite[Th.~2]{DMTJ}.
\begin{R}\label{re3.1}
{\rm Property (C) has the following geometric interpretation. By definition, $(\mathcal P_d^n|_{K_2})^*$ is a
$\widetilde N_{d,n}$-dimensional real Banach space generated by evaluation functionals $\delta_x$ at points $x\in K_2$ with the closed unit ball being the balanced convex hull of the set $\{\delta_x\}_{x\in K_2}$. Thus $K_2$ admits a natural isometric embedding into the unit sphere of  $(\mathcal P_d^n|_{K_2})^*$. Moreover, the Banach space of linear maps $(\mathcal P_d^n|_{K_2})^*\rightarrow \mathcal P_d^n|_{K_1}$ equipped with the operator norm is isometrically isomorphic to the Banach space of real polynomial maps $p:{\mathbb R}^n\rightarrow \mathcal P_d^n|_{K_1}$ of degree at most $d$ (i.e., $f^*\circ p\in\mathcal P_d^n$ for all $f^*\in (\mathcal P_d^n|_{K_1})^*$) with norm $\|p\|:=\sup_{x\in K_2}\|p(x)\|_{\mathcal P_d^n|_{K_1}}$.
Thus property (C) is equivalent to the following one:}\smallskip

\noindent {\rm (C$'$)} There exists a polynomial map $p:{\mathbb R}^n\rightarrow \mathcal P_d^n|_{K_1}$ of degree at most $d$ such that the balanced convex hull of $p(K_2)$ contains the closed unit ball of $\mathcal P_d^n|_{K_1}$ and is contained in the closed ball of radius
$c_2(n)\cdot (\widetilde N_{d,n}\cdot (1+\ln \widetilde N_{d,n}))^{\frac 12}$ of this space (both centered at $0$).
\end{R}

Our next property, a consequence of Corollary \ref{c2} and \eqref{ind}, estimates the metric entropy of the closure of the set $\widetilde{\mathcal P}_{d,n}\subset\mathcal B_{\widetilde N_{d,n}}$ formed by all $\widetilde N_{d,n}$-dimensional spaces $\mathcal P_d^n|_{K}$ with $\mathcal P^n$-determining compact subsets $K\subset\mathbb R^n$.\medskip

\noindent (D) {\em There exists a numerical constant $c>0$ such that for each $\varepsilon\in (0,\frac{1}{2}]$,}
\begin{equation}\label{entro}
H\bigl({\rm cl}(\widetilde{\mathcal P}_{d,n}),\varepsilon\bigr)\le (cn^{2}\cdot\ln(n+1))^{n}\cdot d^{2n}\cdot (1+\ln d)^{n+1}\cdot\left(\frac{1}{\varepsilon}\right)^n\cdot \left(\ln\left(\frac{1}{\varepsilon}\right)\right)^{n+1}.
\end{equation}

\begin{R}\label{rem3.2}
{\rm The above estimate shows that  $\widetilde{\mathcal P}_{d,n}$ with sufficiently large $d$ and $n$ is much less massive than $\mathcal B_{\widetilde N_{d,n}}$. Indeed, as follows from \cite[Th.~2]{Br}
\[H(\mathcal B_{\widetilde N_{d,n}},\varepsilon)\sim \left(\frac{1}{\varepsilon}\right)^{\frac{\widetilde N_{d,n}-1}{2}}\quad \text{as}\quad \varepsilon\rightarrow 0^+
\]
(here the equivalence depends on $d$ and $n$ as well). On the other hand, \cite[Th.~1.1]{P} implies that for any $\varepsilon>0$,}
\[
0<\liminf_{\widetilde N_{d,n}\rightarrow\infty}\frac{\ln H(\mathcal B_{\widetilde N_{d,n}},\varepsilon)}{\widetilde N_{d,n}}\le \limsup_{\widetilde N_{d,n}\rightarrow\infty}\frac{\ln H(\mathcal B_{\widetilde N_{d,n}},\varepsilon)}{\widetilde N_{d,n}} <\infty.
\]

{\rm It might be of interest to} find sharp asymptotics of $H\bigl({\rm cl}(\widetilde{\mathcal P}_{d,n}),\varepsilon\bigr)$ as $\varepsilon\rightarrow 0^+$ and $d\rightarrow\infty$, {\rm and to} compute (up to a constant depending on $n$) $d_{BM}$-``diameter'' of $\widetilde{\mathcal P}_{d,n}$.
\end{R}

Similar results are valid for $K$ being a compact subset of a real algebraic variety $X\subset\mathbb R^n$ of dimension $m<n$ such that if a polynomial vanishes on $K$, then it vanishes on $X$ as well. In this case there are positive constants $c_X, \tilde c_X$ depending on $X$ only such that $\tilde c_X d^m\le {\rm dim}\,\mathcal P_d^n|_K\le c_X d^m$. For instance,
Corollary \ref{c1}  with  $c=c_X$, $k:=m$ and $s:=(m+2)^2$ implies that $\mathcal P_d^n|_K$ is linearly embedded into $\ell_{N_{d,X}}^\infty$, where $N_{d,X}:= \left\lfloor c_X d^m\cdot (m+2)^{2m}\cdot \left(\lfloor\ln(c_Xd^m)\rfloor +1\right)^m\right\rfloor$,
with distortion $<2.903$. We leave the details to the reader.\smallskip

\section{Proofs}

\begin{proof}[Proof of Theorem \ref{te1}]
Since ${\rm dim}\, F_i=n_i$, $i\in{\mbf N}$, and evaluations $\delta_z$ at points $z\in K$ determine bounded linear functionals on $F_i$, the Hahn-Banach theorem implies easily that ${\rm span}\,\{\delta_z\}_{z\in K}= F_i^*$. Moreover, $\|\delta_z\|_{F_i^*}=1$ for all $z\in K$ and the closed unit ball of $F_i^*$ is the balanced convex hull of the set $\{\delta_z\}_{z\in K}$. Let $\{f_{1i},\dots,f_{n_i i}\}\subset F_i$ be an Auerbach basis with the dual basis $\{\delta_{z_{1i}},\dots,\delta_{z_{n_i i}}\}\subset F_i^*$, that is, $f_{ki}(\delta_{z_{li}}):=f_{ki}(z_{li})=\delta_{kl}$ {\rm (the\ Kronecker-delta)} and
$\|f_{ki}\|_K=1$ for all $k$. (Its construction is similar to that of the fundamental Lagrange interpolation polynomials for $F_i=\mathcal P_i^n|_K$, see, e.g., \cite[Prop.~2.2]{BY}.)

Now, we use a ``method of  E.~Landau''  (see, e.g., \cite[Ch.\,3,  \S\,2]{PS}).

By the definition, for each $g\in F_i$ we have $g(z)=\sum_{k=1}^{n_i}f_{ki}(z)g(z_{ki})$, $z\in K$. Hence,
$\|g\|_K\le n_i\|g\|_{\{z_{1i},\dots, z_{n_i i}\}}$. Applying the latter inequality to $g=f^{p_d}$, $f\in F_d$, containing in $F_{i}$, $i:=d\cdot p_d$, and using condition \eqref{e2} we get
for $A_d:=\{z_{1 i},\dots, z_{n_{i} i}\}\subset K$
\[
\|f\|_K=\left(\|g\|_K\right)^{\frac{1}{p_d}}\le \left(n_{d\cdot p_d}\right)^{\frac{1}{p_d}}\cdot \left(\|g\|_{A_d}\right)^{\frac{1}{p_d}}\le
e^{c}\cdot\|f\|_{A_d}.
\]

Thus, restriction $F_d\mapsto F_d|_{A_d}$ determines the required map $i_d: F_d\hookrightarrow\ell_{n_{d\cdot p_d}}^\infty$.
\end{proof}
\begin{proof}[Proof of Corollary \ref{c1}]
We set $p_d:=s\cdot(\lfloor\ln(\hat cd^k)\rfloor +1)$, $d\in{\mbf N}$. Then the condition of the corollary implies
\[
\frac{\ln n_{d\cdot p_d}}{p_d}\le \frac{\ln (\hat cd^k)+k\ln p_d}{p_d}\le \frac 1s+\frac{k\ln s}{s}=:c.
\]
Thus the result follows from Theorem \ref{te1}.
\end{proof}

\begin{proof}[Proof of Corollary \ref{c2}]
We make use of \cite[Lm.~1.2]{P} adapted to our setting:
\begin{Lm}\label{le3.2}
Let $S_{\bar n_d}\subset {\mathcal B}_{\bar n_d}$ be the subset formed
by all $\bar n_d$-dimensional subspaces of $\ell_{N_{d,s}}^\infty$. Consider $0 <\xi < \frac{1}{\bar n_d}$ and let $R =\frac{1 + \xi \bar n_d}{1 -\xi \bar n_d}$.
Then $S_{\bar n_d}$ admits an $R$-net $T_R$ of cardinality at most $\left(1 + \frac{2}{\xi}\right)^{N_{d,s}\cdot \bar n_d}$.
\end{Lm}
Now given $\varepsilon\in (0,\frac 12]$ we choose $s=\lfloor s_\varepsilon\rfloor$ with $s_\varepsilon$ satisfying
$(es_\varepsilon^k)^{\frac{1}{s_\varepsilon}}=\sqrt[4]{1+\varepsilon}$ and $\xi$ such that $R=R_\varepsilon=\sqrt[4]{1+\varepsilon}$. Then according to Corollary \ref{c1} and Lemma \ref{le3.2}, ${\rm dist}_{BM}\bigl(T_{R_{\varepsilon}},\mathcal B_{\hat c, k, \bar n_d}\bigr)< \sqrt{1+\varepsilon}$.
For each $p\in T_{R_{\varepsilon}}$ we choose $q_p\in \mathcal B_{\hat c, k, \bar n_d}$ such that $d_{BM}(p,q_p)<\sqrt{1+\varepsilon}$. Then the multiplicative triangle inequality for $d_{BM}$ implies that open $d_{BM}$-``balls'' of radius $1+\varepsilon$ centered at points $q_p$, $p\in T_{R_{\varepsilon}}$, cover $\mathcal B_{\hat c, k, \bar n_d}$. Hence,
\begin{equation}\label{e3.6}
N(\mathcal B_{\hat c, k, \bar n_d},d_{BM}, 1+\varepsilon)\le {\rm card}\, T_{R_{\varepsilon}}\le \left(1 + \frac{2}{\xi}\right)^{N_{d,s}\cdot \bar n_d}.
\end{equation}

Next, the function $\varphi(x)=\ln (ex^k)^{\frac{1}{x}}$ decreases for $x\in [e^{\frac{k-1}{k}},\infty)$ and $\lim_{x\rightarrow\infty}\varphi(x)=0$. Its inverse $\varphi^{-1}$ on this interval has domain $(0,e^{-\frac{k-1}{k}}]$, increases and is easily seen (using that $\varphi\circ\varphi^{-1}={\rm id}$) to satisfy
\[
\varphi^{-1}(x)\le \frac{3k}{x}\cdot\ln\left(\frac{3k}{x}\right), \qquad x\in (0,e^{-\frac{k-1}{k}}].
\]
Since $\frac{1}{4}\ln(1+\varepsilon)<e^{-\frac{k-1}{k}}$ for $\varepsilon\in (0,\frac 12]$, the required $s_\varepsilon$ exists and the previous inequality implies that
\begin{equation}\label{e3.7}
s_\varepsilon \le  \frac{12k}{\ln(1+\varepsilon)}\cdot\ln\left(\frac{12k}{\ln(1+\varepsilon)}\right).
\end{equation}

Further, we have
\begin{equation}\label{e3.8}
\frac{1}{\xi}=\frac{\bar n_d(1+R_\varepsilon)}{R_\varepsilon-1}=\frac{\bar n_d(\sqrt[4]{1+\varepsilon}+1)}{\sqrt[4]{1+\varepsilon}-1}=
\frac{\bar n_d(\sqrt[4]{1+\varepsilon}+1)^2\cdot (\sqrt{1+\varepsilon}+1)}{\varepsilon}.
\end{equation}
From \eqref{e3.6}, \eqref{e3.7}, \eqref{e3.8} invoking the definition of $N_{d,s}$ we obtain
\[
\ln N(\mathcal B_{\hat c, k, \bar n_d},d_{BM}, 1+\varepsilon)\le  \bar n_d\hat cd^k\left(\ln(\hat cd^k)+1\right)^k\ln\left(\frac{21\bar n_d}{\varepsilon}\right) \left(\frac{12k}{\ln(1+\varepsilon)}\ln\left(\frac{12k}{\ln(1+\varepsilon)}\right)\right)^k.
\]
Using that $\bar n_d\le\hat cd^k$ and the inequality $\frac 23 \cdot\varepsilon\le\ln(1+\varepsilon)$, $\varepsilon\in (0,\frac 12]$, we get the required estimate.
\end{proof}


\section{Introduction}

We obtain the following incidence bound.
\begin{theorem} \label{t:SzTBasic}
  Let $p$ be a prime, and let $K$ be a finitely generated extension of
  ${\mathbb{F}}_p$.
  Let $E \subseteq  K^n \times K^m$ be the zero set of a set of polynomials in
  $K[x_1,\ldots ,x_{n+m}]$.
  Let $d,s \in {\mathbb{N}}$ and suppose $E$ is $K_{d,s}$-free, i.e.\ if $A\times B \subseteq  E$
  then $|A| < d$ or $|B| < s$.

  Then there exists $\epsilon > 0$ (which can in principle be calculated as a
  function of the number and degrees of the polynomials defining $E$) and $C >
  0$ such that for any finite subsets $A \subseteq  K^n$ and $B \subseteq  K^m$,
  $$|E \cap (A \times B)| \leq  C(|A|^{1-\epsilon}
  |B|^{\frac{d-1}d(1+\epsilon)} + |A| + |B|).$$
\end{theorem}

\subsection{Background and motivation}
The Szemerédi-Trotter theorem bounds the number of point-line incidences
between a set $P$ of points and a set $L$ of lines in the real plane.
We state a version with an explicit bound, \cite[Theorem~8.3]{TaoVu}:
\begin{fact} \label{f:STOrig}
  For any finite $P$ and $L$,
  $$|\{ (p,l) \in P \times L : p \in l\}|
  \leq  4|P|^{\frac23}|L|^{\frac23}+4|P|+|L|.$$
\end{fact}

Statements of the form of Theorem~\ref{t:SzTBasic} can be seen as generalisations of
this, replacing the point-line incidence relation with other algebraic binary
algebraic relations. Such results were proven for characteristic 0 fields
first in \cite[Theorem~9]{ES}, and subsequently strengthened in
\cite[Theorem~1.2]{FoxEtAl}. Using such bounds for binary relations,
Elekes-Szabó \cite{ES} obtained somewhat analogous bounds for ternary
algebraic relations.

In positive characteristic, versions of Fact~\ref{f:STOrig} have been proven
(\cite{BKT},\cite{SZ}) where one restricts to sets which are small compared to
the characteristic. This is related to the sum-product phenomenon in fields,
where finite fields are known to be the only obstruction (\cite{BKT},
\cite[Theorem~2.55]{TaoVu}).

Meanwhile, a special case of results in \cite{CGS} and \cite[Section~2]{CS}
yields a version of Theorem~\ref{t:SzTBasic} in characteristic 0 by seeing it as a
consequence of the fact that the complex field is a reduct of a distal
structure, namely the real field.
The notion of distality and these incidence theoretic implications are
summarised in Section \ref{s:CSbackground} below.
It would be surprising if the positive characteristic results mentioned in the
previous paragraph, which require an unbounded characteristic, could be seen
as instances of distality. We consider instead the orthogonal situation of a
function field over a finite field, and we prove Theorem~\ref{t:SzTBasic} by finding
sufficient distality to trigger the incidence bounds of \cite{CGS}. We obtain
this distality using elementary notions from the model theory of valued
fields, and in fact our results apply more generally to any valued field with
finite residue field. Note that it follows from \cite{KSW} that a positive
characteristic valued field with finite residue field is not NIP, and so is
not the reduct of a distal structure; this forces us to use a more local
notion of distality.

Our motivation for considering these fields is \cite[Section~5]{Hr-psfDims},
which suggests a unifying explanation for all the results on existence of
bounds described above: they are all incarnations of {\em modularity} in the
model-theoretic sense, and they are consistent with a Zilber dichotomy
statement of the form ``any failure of modularity arises from an infinite
pseudofinite field''. In other words, finite fields should be the cause of any
failure of the bounds. As a special case, this would suggest that for a field
$K$ of characteristic $p > 0$ which has finite \defn{algebraic part} ${\mathbb{K}} \cap
{\mathbb{F}}_p^{\operatorname{alg}}$, incidence bounds and Elekes-Szabó results should go through as in
characteristic 0.

We partially confirm this only in the special\footnote{See
Proposition~\ref{p:latentFields}} case of fields admitting finite residue field.
However, in Theorem~\ref{t:ES} we do confirm for such $K$ that an Elekes-Szabó
result applies: a mild strengthening of Theorem~\ref{t:SzTBasic} suffices as input
to the proof of one of the main results of \cite{BB-cohMod}, yielding
Elekes-Szabó bounds for arbitrary arity algebraic relations in $K^n$ which do
not arise from 1-dimensional algebraic groups.

\subsection{Acknowledgements}
Thanks to Artem Chernikov and Sergei Starchenko for conversation which
launched the project, to Sylvy Anscombe, Philipp Dittmann, Udi Hrushovski, and
Silvain Rideau-Kikuchi for miscellaneous helpful conversation, and to
Elisabeth Bouscaren for matchmaking and sanity checking.

\emph{\small{Bays was supported in part by the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) under Germany's Excellence Strategy EXC
2044–390685587, Mathematics Münster: Dynamics–Geometry–Structure.}}

\section{Preliminaries}

We use basic notions and notation from model theory.

Let $\mathcal{L}$ be a (possibly many-sorted) first order language and $T$ a a
complete $\mathcal{L}$-theory.

\begin{notation}
  If ${\mathcal{M}} \vDash  T$ and $B \subseteq  {\mathcal{M}}$ and $x=(x_1,\ldots ,x_n)$ is a tuple of variables of
  sorts $S_1,\ldots ,S_n$, we write $B^x$ for $\prod_i (S_i({\mathcal{M}}) \cap B)$.
  We write $|x|$ for the length $|x| = n$ of the tuple.

  For a set $B$,
  we write $B_0 \subseteq_{{\operatorname{fin}}}  B$ to mean that $B_0$ is a finite subset of $B$.

  For a formula $\phi$, we define $\phi^0 := \neg\phi$ and $\phi^1 := \phi$.

  If $\phi(x;y)$ is a partitioned formula and $b \in {\mathcal{M}}^x$ and $A \subseteq  {\mathcal{M}}$, we
  set ${\operatorname{tp}}_\phi(b/A) := \{ \phi(x,c)^\epsilon : c \in A^y;\; \epsilon \in \{0,1\};\; {\mathcal{M}}
  \vDash  \phi(b,c)^\epsilon \}$. The partitioning will often be left implicit.
\end{notation}

\section{Distality}
\subsection{Distal cell decompositions}
\label{s:CSbackground}
We recall the following definition from \cite{CGS}:

\begin{definition}
  Let $A$ and $B$ be sets.
  A binary relation $E \subseteq  A \times B$ {\em admits a distal cell decomposition}
  with exponent $t \in {\mathbb{R}}$ if there exist $s \in {\mathbb{N}}$ and finitely many relations
  $\Delta_i \subseteq  A \times B^s$ and $C \in {\mathbb{R}}$ such that for every $B_0 \subseteq_{{\operatorname{fin}}}  B$,
  $A$ can be written as a (not necessarily disjoint) union of $\leq  C|B_0|^t$
  subsets of the form $\Delta_i(c)$ for $c \in B_0^s$, each of which {\em cuts} no
  $E(b)$ for $b \in B_0$, i.e.\ $E(b) \subseteq  \Delta_i(c)$ or $E(b) \cap \Delta_i(c)
  = \emptyset $.
\end{definition}

It was proven in \cite{CGS} that relations admitting distal cell
decompositions enjoy certain incidence bounds. For our purposes, the following
version of this deduced in \cite[Theorem~2.6,2.7(2)]{CS-ES1d} is most
relevant.

A binary relation $E \subseteq  A \times B$ is \defn{$K_{d,s}$-free} if it contains no
subset $A_0 \times B_0$ with $|A_0| = d$ and $|B_0| = s$.

\begin{fact} \label{f:distInc}
  Let $E \subseteq  A \times B$ be $K_{d,s}$-free and admit a distal cell
  decomposition with exponent $t$. Then for $A_0 \subseteq_{{\operatorname{fin}}}  A$ and $B_0 \subseteq_{{\operatorname{fin}}}  B$,
  $$|E \cap (A_0 \times B_0)| \leq  O_E(|A_0|^{\frac{(t-1)d}{td-1}}
  |B_0|^{\frac{td-t}{td-1}} + |A_0| + |B_0|).$$
\end{fact}

\subsection{Distal subsets}

\begin{definition}
  Let ${\mathcal{M}} \vDash  T$.
  Let $\phi(x;y)$ be an $\mathcal{L}({\mathcal{M}})$ formula, and let $A,B \subseteq  {\mathcal{M}}$ be subsets.
  \begin{itemize}\item An $\mathcal{L}$-formula $\zeta_\phi(x;z)$ is a \defn{uniform strong honest
  definition} (\defn{USHD}) for $\phi$ on $A$ over $B$ if
  for any $a \in A$ and finite subset $B_0 \subseteq_{{\operatorname{fin}}}  B$ with $|B_0| \geq  2$,
  there is $d \in B_0^z$
  such that ${\operatorname{tp}}(a/B_0) \ni \zeta_\phi(x,d) \vdash  {\operatorname{tp}}_\phi(a/B_0)$.

  \item We omit ``on $A$'' in the case $A = {\mathcal{M}}$.

  \item We omit ``over $B$'' in the case $B=A$.

  \item $A$ is \defn{distal in} ${\mathcal{M}}$ if every $\mathcal{L}(A)$-formula $\phi(x;y)$ has
  a USHD on $A$.
  \end{itemize}
\end{definition}

The notion of a strong honest definition comes from \cite{CS-extDefII}. We
work with USHDs rather than directly with distal cell decompositions in order
to be able to reduce to one variable (Lemma~\ref{l:distal1}), and because dealing
with a single formula is more convenient for many purposes. As the following
remark makes explicit, there is little difference between the two notions.

\begin{remark} \label{r:distDist}
  An $\mathcal{L}$-formula $\phi(x;y)$ has a USHD on $A$ over $B$ if and only if the
  binary relation $E := \phi(A;B) \subseteq  A^x\times B^y$ admits a distal cell
  decomposition where the $\Delta_i$ are themselves defined by
  $\mathcal{L}$-formulas. The restriction $|B_0| \geq  2$ allows multiple $\Delta_i$ to
  be coded as one formula, a trick we will use repeatedly; explicitly, if
  $\delta_i(x,z_i)$ define $\Delta_i$, then
  $$\zeta(x,z_1,\ldots ,z_s,w_1,\ldots ,w_s,w'_1,\ldots ,w'_s) :=
  \bigwedge_i (\delta_i(x,z_i) \leftrightarrow  w_i = w'_i)$$
  is a USHD for $\phi$ on $A$ over $B$.

  In particular, if $A \subseteq  {\mathcal{M}}$ is distal in ${\mathcal{M}}$, then the trace on $A$ of any
  $\mathcal{L}(A)$-formula $\phi(x,y)$ admits a distal cell decomposition.
\end{remark}

\subsection{Reductions}

\begin{lemma} \label{l:distal1}
  A subset $A \subseteq  {\mathcal{M}}$ is distal in ${\mathcal{M}}$ if and only if any $\mathcal{L}$-formula
  $\phi(x;y)$ with $|x| = 1$ has a USHD on $A$.
\end{lemma}
\begin{proof}
  First, it follows by an inductive argument from the 1-variable case that any
  $\mathcal{L}$-formula has a USHD on $A$; we refer to the proof of
  \cite[Proposition~1.9]{ACGZ} for this argument.

  It remains to deduce that any $\mathcal{L}(A)$-formula has a USHD on $A$, but it
  follows directly from the definition that if $\phi(x;y,z)$ has a USHD on $A$
  and $a \in A^z$, then $\phi(x;y,a)$ has a USHD on $A$.
\end{proof}

\begin{lemma} \label{l:dd-feq}
  Let ${\mathcal{M}}$ be an $\mathcal{L}$-structure.
  Let $S$ and $\widetilde {S}$ be $\mathcal{L}$-sorts and let $f : \widetilde {S} \rightarrow  S$ be an
  $\mathcal{L}$-definable function with uniformly finite fibres,
  say $|f^{-1}(b)| \leq  N$ for all $b \in f(S)$.
  Suppose $B \subseteq  f(S({\mathcal{M}}))$, and let $\widetilde {B} := f^{-1}(B) \subseteq  \widetilde {S}$.

  Let $A \subseteq  {\mathcal{M}}^x$ and
  let $\phi(x,y)$ be an $\mathcal{L}$-formula
  such that $\phi(x;f(z))$ has a USHD on $A$ over $\widetilde {B}$.
  Then $\phi(x;y)$ has a USHD on $A$ over $B$.
\end{lemma}
\begin{proof}
  Say $\zeta(x,w)$ is a USHD for $\phi(x;f(z))$ over $\widetilde {B}$.

  Let $B_0 \subseteq_{{\operatorname{fin}}}  B$ and $a \in A$. Then $\widetilde {B}_0 := f^{-1}(B_0)$ is a finite subset
  of $\widetilde {B}$, so there is $\widetilde {d}$ such that ${\operatorname{tp}}(a/\widetilde {B}_0) \ni \zeta(x,\widetilde {d}) \vdash
  {\operatorname{tp}}_{\phi(x;f(z))}(a/\widetilde {B}_0) \vdash  {\operatorname{tp}}_{\phi(x;y)}(a/B_0)$.

  \newcommand{\overline{\eps}}{\overline{\epsilon}}
  Let $d := f(\widetilde {d})$. Then $|f^{-1}(d)| \leq  N^{|w|}$, and so there is $M <
  N^{|w|}$ and $\overline{\eps}_0 \in \{0,1\}^M$ and $\b_0 \in (B_0)^M$ such that
  $\theta_{M,\overline{\eps}_0}(w,d,\b_0)$ has the minimal number of realisations
  amongst the formulas
  $$\theta_{n,\overline{\eps}}(w,d,\b) := (f(w) = d \wedge \forall x. (\zeta(x,w) \rightarrow
  \bigwedge_{i=1}^n \phi(x,b_i)^{\epsilon_i}))$$
  which hold of $\widetilde {d}$, with $n \in {\mathbb{N}}$ and $\overline{\eps} \in \{0,1\}^n$ and $\b \in
  (B_0)^n$. The bound $M < N^{|w|}$ follows from the observation that if such
  a formula does not have the minimal number of realisations, then a single
  new instance of $\phi$ can be added to reduce the number of realisations.
  By the minimality, we have for any $b \in B_0$ that
  $\theta_{M,\overline{\eps}_0}(w,d,\b_0) \vdash  \forall x. (\zeta(x,w) \rightarrow
  \phi(x,b)^\epsilon)$ for some $\epsilon \in \{0,1\}$.

  So ${\operatorname{tp}}(a/B_0) \ni \exists w. (\theta_{M,\overline{\eps}_0}(w,d,\b_0) \wedge \zeta(x,w))
  \vdash  {\operatorname{tp}}_{\phi(x;y)}(a/B_0)$. Coding the finitely many such formulas with $M <
  N^{|w|}$ and $\overline{\eps}_0 \in \{0,1\}^M$ into a single formula,
  we therefore obtain a USHD for $\phi(x;y)$ on $A$ over $B$.

\end{proof}

\begin{remark}
  The finiteness assumption in Lemma~\ref{l:dd-feq} is necessary.
  Consider for example the structure $(X,O_X;<)$ where $X$ is a set, $O_X$ is
  the set of linear orders on $X$, and $x<_ox'$ is the corresponding ternary
  relation. Let $\pi_1 : X \times O_X \rightarrow  X$ be the projection.
  As one may see by considering automorphisms, the induced structure on $X$ is
  trivial, so $x = y$ has no USHD on $X$ over $X$.
  But $x = \pi_1(z)$ has a USHD on $X$ over $X\times O_X$ (since if $X_0 \subseteq_{{\operatorname{fin}}}
  X$ and $o \in O_X$, then ${\operatorname{tp}}_=(x/X_0)$ is implied by the $<_o$-cut of $x$ in
  $X_0$).
\end{remark}

\subsection{Remarks}
We add some further remarks concerning these definitions, which will not be
used subsequently.

\begin{remark} \label{r:distalElem}
  Suppose $B$ is distal in an $\mathcal{L}$-structure ${\mathcal{M}}$.
  Then this is expressed in the $\mathcal{L}_P$-theory of $({\mathcal{M}};B)$, where $P$ is a
  new predicate interpreted as $B$;
  i.e.\ if $({\mathcal{M}}';B') \equiv  ({\mathcal{M}};B)$,
  then $B'$ is distal in ${\mathcal{M}}'$.
\end{remark}

\begin{remark}
  By \cite[Theorem~21]{CS-extDefII}, ${\operatorname{Th}}({\mathcal{M}})$ is distal if and only if ${\mathcal{M}}$
  is distal in ${\mathcal{M}}$.
  (No saturation assumption is needed here, thanks to
  Remark~\ref{r:distalElem}.)
\end{remark}

\begin{remark}
  Distality in ${\mathcal{M}}$ of a subset $B \subseteq  {\mathcal{M}}$ is equivalent to distality of the
  induced structure $(B;(\phi(B)_{\phi \text{ an $\L$-formula}})$ if this
  structure admits quantifier elimination, but in general is much weaker. We
  could say that distality of a subset means that it has ``quantifier-free
  distal induced structure''.
\end{remark}

\begin{example} \label{e:indSeq}
  If $B = (b_i)_i \subseteq  {\mathcal{M}}$ is an $\emptyset $-indiscernible sequence which is not
  totally indiscernible, and this is witnessed by an $\mathcal{L}$-formula
  $\theta_<$ with ${\mathcal{M}} \vDash  \theta_<(b_i,b_j) \Leftrightarrow  i<j$,
  then $B$ is distal in ${\mathcal{M}}$.
\end{example}

\begin{remark}
  The argument of \cite{CS-extDefII} to obtain uniformity of honest
  definitions goes through in this setting.
  Namely, if $B$ is a subset of a model ${\mathcal{M}}$ of a complete NIP $\mathcal{L}$-theory
  $T$,
  and the $\mathcal{L}_P$-structure $({\mathcal{M}};B)$ is $|T|^+$-saturated,
  then $B$ is distal in ${\mathcal{M}}$ if and only if
  for any singleton $b \in B$ and any subset $A \subseteq  B$, ${\operatorname{tp}}^{{\mathcal{M}}}(b/A)$ is
  compressible in the sense of \cite{simon-decomposition}. This follows from a
  ``$(p,q)$-argument'' and transitivity of compressibility.

  It follows in particular that Example~\ref{e:indSeq} can be generalised slightly
  when ${\mathcal{M}}$ is NIP: any $\emptyset $-indiscernable sequence which is not totally
  indiscernable is distal in ${\mathcal{M}}$.
\end{remark}

\begin{question}
  The following question was asked by Hrushovski and Pillay. By a result of
  Simon, an NIP theory is distal if and only if every generically stable
  Keisler measure is smooth. Does a version of this result go through for
  distality of subsets of NIP structures? Is $B$ distal in ${\mathcal{M}}$ if and only if
  every generically stable Keisler measure on ${\operatorname{Th}}_{\mathcal{L}_P}({\mathcal{M}},B)$ with
  $\mu(\neg P)=0$ is smooth?
  This might provide an alternative route to Theorem~\ref{t:fin-res-distal}.
\end{question}

\section{Fields admitting valuations with finite residue field}
By classical results in valuation theory, a valuation on a field $K$ can be
extended to any finite extension of $K$ with a finite extension of the residue
field \cite[Theorem~3.1.2, Corollary~3.2.3]{EnglerPrestel}, and can be
extended to the transcendental extension $K(X)$ without extending the residue
field \cite[Corollary~2.2.3]{EnglerPrestel}. Since ${\mathbb{F}}_p$ and ${\mathbb{Q}}$ admit
valuations with finite residue field (respectively trivial and $p$-adic), we
inductively obtain:\

\begin{lemma} \label{l:fgRes}
  Let $K$ be a finitely generated field.
  Then $K$ admits a valuation with finite residue field.
\end{lemma}

If $K$ is a valued field of characteristic $p>0$, then the induced valuation
on the algebraic part $K\cap {\mathbb{F}}_p^{\operatorname{alg}}$ is trivial. So a positive
characteristic field which admits a valuation with finite residue field has
finite algebraic part.
However, the converse fails.

\begin{proposition} \label{p:latentFields}
  For any prime $p$,
  there exists an algebraic extension $L \geq  {\mathbb{F}}_p(t)$ such that $L\cap
  {\mathbb{F}}_p^{\operatorname{alg}} = {\mathbb{F}}_p$ but no valuation on $L$ has finite residue field.
\end{proposition}
\begin{proof}
  We work in an algebraic closure ${\mathbb{F}}_p(t)^{\operatorname{alg}}$ of ${\mathbb{F}}_p(t)$.
  Let $\wp : {\mathbb{F}}_p(t)^{{\operatorname{alg}}} \rightarrow  {\mathbb{F}}_p(t)^{\operatorname{alg}}$ be the Artin-Schreier map
  $\wp(x) := x^p-x$, an additive homomorphism with kernel ${\mathbb{F}}_p$.

  \begin{claim*}
    $\deg({\mathbb{F}}_p(t,(\wp^{-1}(t^a))_{a > 0}) / {\mathbb{F}}_p(t))$ is infinite.
  \end{claim*}
  \begin{proof}
    By \cite[Theorem~8.3]{Lang-algebra},
    it suffices to see that $\{ t^a | a > 0\}$ is not contained in any finite
    union of additive cosets of $\wp({\mathbb{F}}_p(t))$.
    Let $a,b \in {\mathbb{N}} \setminus p{\mathbb{N}}$ be distinct. Let $\beta_{a,b} := \sum_{i \geq  0}
    (t^{ap^i} - t^{bp^i}) \in {\mathbb{F}}_p[[t]]$. Then $\wp(\beta_{a,b}) = t^b - t^a$.
    Now $\beta_{a,b} \notin {\mathbb{F}}_p(t)$, since there are arbitrarily long intervals
    between exponents with non-zero coefficient in this power series.
    So $(t^a)_{a \in {\mathbb{N}} \setminus p{\mathbb{N}}}$ lie in distinct cosets of $\wp({\mathbb{F}}_p(t))$.
  \end{proof}

  We write ${\operatorname{res}}$ for the residue field map associated to a chosen valuation
  $v$ on a field $K$, and ${\operatorname{res}}(K)$ for the corresponding residue field.

  \begin{claim*}
    Let $K' \geq  K \geq  {\mathbb{F}}_p(t)$ be finite field extensions, and suppose $K' \cap
    {\mathbb{F}}_p^{\operatorname{alg}} = {\mathbb{F}}_p$.
    Let $v$ be a valuation on $K$ with ${\operatorname{res}}(K)$ finite.

    Then there exists a finite field extension $K'' \geq  K'$ such that
    $K'' \cap {\mathbb{F}}_p^{\operatorname{alg}} = {\mathbb{F}}_p$
    but for any extension of $v$ to $K''$, ${\operatorname{res}}(K'') \gneq  {\operatorname{res}}(K)$.
  \end{claim*}
  \begin{proof}
    The valuation $v$ is non-trivial, so say $v(s) > 0$.
    So $v$ induces the $s$-adic valuation on ${\mathbb{F}}_p(s) \leq  K$.
    Now $s$ is transcendental, so $t$ is algebraic over $s$, so $K$ is also a
    finite extension of ${\mathbb{F}}_p(s)$.
    So we may assume without loss that $v$ restricts to the $t$-adic valuation
    on ${\mathbb{F}}_p(t)$.

    Since ${\operatorname{res}}(K)$ is finite, it is not Artin-Schreier closed;
    say $\alpha \in {\operatorname{res}}(K) \setminus \wp({\operatorname{res}}(K))$.
    Say ${\operatorname{res}}(\bar\alpha) = \alpha$.

    Since $\deg(K'/{\mathbb{F}}_p(t))$ is finite, it follows from the above Claim that
    $$\deg(K'(\wp^{-1}(\bar\alpha),(\wp^{-1}(\bar\alpha + t^a))_{a > 0})/K')$$
    is infinite.
    So say $a>0$ is such that $K'' := K(\wp^{-1}(\bar\alpha+t^a)) \not\subseteq
    K'({\mathbb{F}}_{p^p})$.
    Then by considering degrees, $K'' \cap {\mathbb{F}}_p^{\operatorname{alg}} = {\mathbb{F}}_p$.
    But for any extension of $v$ to $K''$,
    $$\wp({\operatorname{res}}(\wp^{-1}(\bar\alpha+t^a))) = {\operatorname{res}}(\bar\alpha+t^a) = \alpha \notin
    \wp({\operatorname{res}}(K)),$$
    so ${\operatorname{res}}(K'') \gneq  {\operatorname{res}}(K)$.
  \end{proof}

  Now we recursively construct a chain $K_0 := {\mathbb{F}}_p(t) \leq  K_1 \leq  \ldots $
  of finite extensions of ${\mathbb{F}}_p(t)$.
  Let $\eta : \omega \times \omega \rightarrow  \omega$ be a bijection such that
  $\eta(i,j) \geq  i$ for all $i,j$.

  Note that ${\mathbb{F}}_p(t)$ admits only countably many valuations (identifying a
  valuation with its valuation ring); indeed, as above, each non-trivial
  valuation is a finite extension of the $s$-adic valuation on some ${\mathbb{F}}_p(s)
  \leq  {\mathbb{F}}_p(t)$; there are only countably many choices for $s$, and only
  finitely many ways to extend a valuation to a finite extension
  (\cite[Theorem~3.2.9]{EnglerPrestel}).
  Hence also there are also only countably many valuations on each $K_i$.
  Once $K_i$ is constructed, let $\{v_{i,j} : j \in \omega\}$ be the set of
  valuations on $K_i$ with finite residue field.

  Suppose $k=\eta(i,j)$ and $K_k$ has been constructed. Let $K_{k+1} \geq  K_k$
  be an extension as in the second Claim for the extensions $K_k \geq  K_i \geq
  {\mathbb{F}}_p(t)$ and the valuation $v_{i,j}$ on $K_i$.

  Now let $K_\omega := \bigcup_{k < \omega} K_k$.
  We have $K_\omega \cap {\mathbb{F}}_p^{\operatorname{alg}} = {\mathbb{F}}_p$ since this holds for each $K_k$.

  Suppose $v$ is a valuation on $K_\omega$ with finite residue field.
  Then ${\operatorname{res}}(K_\omega) = {\operatorname{res}}(K_i)$ say, and the restriction of $v$ to $K_i$
  is $v_{i,j}$ say.
  Then ${\operatorname{res}}(K_{\eta(i,j)+1}) = {\operatorname{res}}(K_i)$, contradicting the construction.
\end{proof}

\begin{remark}
  One might expect that a Zorn argument could replace the recursive
  construction of the previous Proposition, i.e.\ that any maximal regular
  extension of ${\mathbb{F}}_p(t)$ has no valuation with finite residue field. But
  ${\mathbb{F}}_p((t^{\mathbb{Q}})) \cap {\mathbb{F}}_p(t)^{\operatorname{alg}}$ is a counterexample. Thanks to Zoé
  Chatzidakis for pointing this out.
\end{remark}

\section{Distality in ${\operatorname{ACVF}}$ of subfields with finite residue field}
\subsection{Uniform Swiss cheese decompositions}
Let $L$ be a non-trivially valued algebraically closed field.
Write $v$ for the valuation map and ${\operatorname{res}}$ for the residue field map.
We consider $L$ as an $\mathcal{L}_{\operatorname{div}} := \{+,-,\cdot,|,0,1\}$-structure, where $x|y \Leftrightarrow
v(x) \leq  v(y)$; by a result of Robinson, $L$ has quantifier elimination in this
language.
An open resp.\ closed \defn{ball} in $L$ is a definable set of the form $\{ x :
v(x-a) > \alpha \}$ resp.\ $\{ x : v(x-a) \geq  \alpha \}$, where $a \in L$ and
$\alpha \in v(L) \cup \{-\infty,+\infty\}$.

\begin{fact}[Canonical Swiss cheese decomposition] \label{f:swiss}
  Any boolean combination of balls can be represented as a finite disjoint
  union of ``Swiss cheeses'' $\dot\bigcup_{i<k} (b_i \setminus \dot\bigcup_{j<k_i}
  b_{ij})$, where the $b_i$ are balls, each $b_{ij}$ is a proper sub-ball of
  $b_i$, for each $i$ the $b_{ij}$ are disjoint, and no $b_i$ is equal to any
  $b_{i'j}$. This representation is unique up to permutations.
\end{fact}

We call the $b_i$ the ``rounds'' and the $b_{ij}$ the ``holes'' of a Swiss
cheese decomposition, and we say such a decomposition has \defn{complexity}
$\leq N$ if there are $k\leq N$ rounds each with $k_i\leq N$ holes.
Let $\phi(x,y)$ be an $\mathcal{L}_{\operatorname{div}}$-formula with $|x| = 1$.
For any $a \in L$, it follows directly from quantifier elimination that
$\phi(L,a)$ is a boolean combination of balls. We will need the following form
of uniformity in $a$ of the Swiss cheese decompositions.

\begin{lemma} \label{l:ACVFQE-uniformity}
  There are $N$ and $d$ depending only on $\phi$ such that for all $a \in L^y$,
  $\phi(L,a)$ has a Swiss cheese decomposition of complexity $\leq N$, each round
  and each hole of which contains a point in a field extension of the subfield
  generated by $a$ of degree dividing $d$.
\end{lemma}
\begin{proof}
  By quantifier elimination,
  $\phi(x,y)$ is equivalent to a boolean combination of formulas of the form
  $\phi_i(x,y) := v(f_i(x,y)) < v(g_i(x,y))$
  for polynomials $f_i,g_i \in {\mathbb{Z}}[x,y]$.

  Given $i$ and $a \in L$, let $\alpha_j$ resp.\ $\beta_j$ be the roots of
  $f_i(x,a)$ resp.\ $g_i(x,a)$ in $L$.
  Then $\phi_i(x,a) \Leftrightarrow  \sum_j v(x-\alpha_j) < \sum_j v(x-\beta_j)$.

  \begin{claim}
    $\phi_i(x,a)$ is a boolean combination of balls centred at the $\alpha_j$
    and $\beta_j$.
  \end{claim}
  \begin{proof}
    We show more generally, by induction on $s$, that any affine linear
    constraint $\sum_{i=1}^s n_i v(x-\gamma_i) < \nu$ is equivalent to a
    boolean combination of balls centred at the $\gamma_i$. Conditioning on
    the finitely many cases, it suffices to show this for a given order type
    of $\epsilon := v(x-\gamma_1)$ over $\{ v(\gamma_1-\gamma_i) : i > 1 \}$. If
    $\epsilon = v(\gamma_1-\gamma_i)$ for some $i>1$, we conclude by the inductive
    hypothesis. Otherwise, by the ultrametric triangle inequality,
    $v(x-\gamma_i) = \epsilon$ if $\epsilon < v(\gamma_1-\gamma_i)$, and
    $v(x-\gamma_i) = v(\gamma_1-\gamma_i)$ otherwise, so the affine constraint
    is equivalent to $\epsilon < \nu'$ or $\epsilon > \nu'$ for some $\nu'$.
  \end{proof}

  We may assume $L$ is $\aleph_0$-saturated, and so by compactness we obtain a
  bound on the number of balls involved in this boolean combination which is
  uniform in $a$.

  So $\phi(x,a)$ is a boolean combination of boundedly many balls each having
  a point in an extension of the subfield generated by $a$ of degree dividing
  $$d := {\operatorname{lcm}}_i ({\operatorname{lcm}}(\deg_x f_i, \deg_x g_i)),$$
  and it follows that the rounds and holes in the Swiss cheese decomposition
  also have this property and are bounded in number.
\end{proof}

\subsection{Compressing cheeses}
Let $B$ be the imaginary sort of $L$ consisting of balls, both open and
closed, including the empty ball and its complement. We write $x \in b$ for the
corresponding $\emptyset $-definable (in $\mathcal{L}^{\eq}$) element relation $( \in ) \subseteq  L \times
B$.

Given $N \in {\mathbb{N}}$, let $S_N$ be the imaginary sort of $L$ which codes Swiss
cheese decompositions of complexity at most $N$. This means that we have an
associated $\emptyset $-definable element relation, which we also write as $( \in ) \subseteq
L \times S_N$, such that $c_1 = c_2$ iff $\{ x : x \in c_1 \} = \{ x : x \in c_2
\}$, and
setting $$X_N := \{(b_i)_{i<N},(b_{ij})_{i,j<N} : b_i,b_{ij} \in B \textrm{ are
as in Fact~\ref{f:swiss}}\} \subseteq  B^{N(N+1)}$$
we obtain a $\emptyset $-definable surjection $f_{S_N} : X_N \twoheadrightarrow  S_N$ defined by
$f_{S_N}((b_i)_i,(b_{ij})_{ij}) := [{ \textrm{code of } \bigcup_i (b_i \setminus
\bigcup_j b_{ij}) }]$.
By Fact~\ref{f:swiss}, any $c \in S_N$ has a unique-up-to-permutation representation
as a Swiss cheese decomposition of complexity $\leq N$, so $f_{S_N}$ has finite
fibres.

With a view to proving Theorem~\ref{t:fin-res-distal}, for $K$ a valued subfield of
$L$ with finite residue field and $d \in {\mathbb{N}}$, define $B_{K,d} \subseteq  B$ to be the
set of balls which contain an element of some finite field extension of $K$
within $L$ of degree dividing $d$ over $K$.
Let $X_N(B_{K,d}) := X_N \cap B_{K,d}^{N(N+1)}$
and $S_N(B_{K,d}) := f_{S_N}(X_N(B_{K,d}))$.

\begin{lemma} \label{l:B-rel-distal-local}
  Let $N,d \in {\mathbb{N}}$.
  \begin{enumerate}[(i)]\item $x \in y$ has a USHD over $B_{K,d}$.
  \item $x \in f_{S_N}(y)$ has a USHD over $B_{K,d}$.
  \item $x \in z$ has a USHD over $S_N(B_{K,d})$.
  \end{enumerate}
\end{lemma}
\begin{proof}
  \begin{enumerate}[(i)]\item
  By assumption, the residue field of $K$ is a finite field, say ${\mathbb{F}}_q$.

  Let $B_0 \subseteq_{{\operatorname{fin}}}  B_{K,d}$.
  Let $B_0' := \{ b \vee b' : b,b' \in B_0 \}$ where the join $b \vee b'$ is the
  smallest ball containing both $b$ and $b'$. By the ultrametric triangle
  inequality, $B_0'$ is then closed under join. Note that $B_0' \subseteq  B_{K,d}$,
  since $B_{K,d}$ is upwards-closed.

  Let $p \in L$.
  Let $b \in B_0' \cup \{L\}$ be minimal such that $p \in b$,
  and let $b_1,\ldots ,b_s \in B_0'$ be the maximal proper subballs (if any) of $b$
  in $B_0'$.
  Then
  $$(x \in b \wedge \bigwedge_{i=1}^s x \notin b_i) \vdash  {\operatorname{tp}}_{x \in y}(p/B_0),$$
  and each $b_i$ is the join of two balls in $B_0$, and either the same goes
  for $b$ or $b=L$. So coding the finitely many possibilities yields a USHD as
  required if we can bound $s$ independently of $p$.

  Assume $s > 1$.
  Say $p_i \in b_i$ is of degree dividing $d$ over $K$, and let $\alpha \in
  v(L)$ be the valuative radius of $b$.
  Then $v(p_i-p_j)=\alpha$ for $i\neq j$, since $b_i \vee b_j = b$ (in particular,
  $b \neq  L$).

  Then $i \mapsto  \lambda_i := {\operatorname{res}}(\frac{p_i-p_1}{p_2-p_1})$ is an injection of
  $\{1,\ldots ,s\}$ into ${\operatorname{res}}(L)$.
  Indeed, if $\lambda_i=\lambda_j$ then ${\operatorname{res}}(\frac{p_i-p_j}{p_2-p_1}) = 0$,
  so $v(p_i-p_j) > v(p_2-p_1) = \alpha$, so $i=j$.

  Since each $\lambda_i$ is in the residue field of an extension of $K$ of
  degree dividing $d^3$,
  we have $\lambda_i \in {\mathbb{F}}_{q^{d^3}}$ by the valuation inequality
  (\cite[Corollary~3.2.3]{EnglerPrestel}).
  So $s \leq  q^{d^3}$.

  \item
  $x \in f_{S_N}(y)$ is equivalent, by the definition of $f_{S_N}$, to a
  certain boolean combination of the formulas $(x \in y_i)_{i < N(N+1)}$.
  So by (i), coding these formulas yields a formula which is a USHD for $x \in
  f_{S_N}(y)$ over $B_{K,d}$.

  \item
  Considering now $X_N$ as a sort and $y$ as a variable of sort $X_N$,
  it follows from (ii) that $x \in f_{S_N}(y)$ has a USHD over $X_N(B_{K,d})$.
  Then we conclude by Lemma~\ref{l:dd-feq}.
  \end{enumerate}
\end{proof}

\subsection{Concluding distality}
\begin{lemma} \label{l:fin-res-comp}
  Let $L$ be a non-trivially valued algebraically closed field.
  Let $K \leq  L$ be a subfield and suppose ${\operatorname{res}}(K)$ is finite.
  Let $\phi(x;y)$ be an $\mathcal{L}_{\operatorname{div}}$-formula with $|x| = 1$.
  Then $\phi$ has a USHD over $K$.

  Moreover, for any $r \geq  1$, $\phi$ has a USHD over the set $K_r \subseteq  K^{{\operatorname{alg}}}
  \subseteq  L$ of points with degree over $K$ dividing $r$,
  $$K_r := \{ a \in L : \deg(K(a)/K) | r \}$$
\end{lemma}
\begin{proof}
  Let $N$ and $d$ be as in Lemma~\ref{l:ACVFQE-uniformity} for $\phi$.
  Then there is a $\emptyset $-definable function $h : L^{|y|} \rightarrow  S_N$ such that
  $L^{{\operatorname{eq}}} \vDash  \forall x,y. (\phi(x,y) \leftrightarrow  x \in h(y))$,
  and $h(K_r) \subseteq  S_N(B_{K,dr})$.

  By Lemma~\ref{l:B-rel-distal-local}(iii),
  say $\zeta(x,z'_1,\ldots ,z'_s)$ is a USHD for $x \in y$ over $S_N(B_{K,dr})$.
  Then (an $\mathcal{L}_{\operatorname{div}}$-formula equivalent to) $\zeta(x,h(z_1),\ldots ,h(z_s))$ is a
  USHD for $\phi(x;y)$ over $K_r$.
\end{proof}

\begin{theorem} \label{t:fin-res-distal}
  Let $K$ be a valued field with finite residue field.

  Let $L \geq  K$ be an algebraically closed valued field extension.

  Then $K$ is distal in $L$,
  as is each $K_r$ defined as in Lemma~\ref{l:fin-res-comp}.
\end{theorem}
\begin{proof}
  We may assume that $L$ is non-trivially valued, as otherwise $K$ is finite
  and the result is trivial.

  The result then follows from Lemma~\ref{l:fin-res-comp} and Lemma~\ref{l:distal1}.
\end{proof}

\begin{remark}
  This does not reprove distality of ${\mathbb{Q}}_p$, because ${\mathbb{Q}}_p$ does not eliminate
  quantifiers in $\mathcal{L}_{\operatorname{div}}$.
\end{remark}

\section{Incidence theory consequences}

\begin{theorem} \label{t:SzT}
  Let $K$ be a valued field with finite residue field.
  Let $E \subseteq  K^n \times K^m$ be quantifier-free definable in $\mathcal{L}_{\operatorname{div}}(K)$.
  Suppose $E$ omits $K_{d,s}$, where $d,s \in {\mathbb{N}}$.
  Then there exist $t$ (see Remark~\ref{r:bounds}) and $C>0$ such that
  for $A_0 \subseteq_{{\operatorname{fin}}}  K^n$ and $B_0 \subseteq_{{\operatorname{fin}}}  K^m$,
  $$|E \cap (A_0 \times B_0)| \leq  C(|A_0|^{\frac{(t-1)d}{td-1}}
  |B_0|^{\frac{td-t}{td-1}} + |A_0| + |B_0|).$$

  The same holds if $K$ is replaced by $K_r \subseteq  K^{{\operatorname{alg}}}$ defined as in
  Lemma~\ref{l:fin-res-comp}.
\end{theorem}
\begin{proof}
  By Theorem~\ref{t:fin-res-distal} and Remark~\ref{r:distDist},
  $E$ admits a distal cell decomposition, and we conclude by Fact~\ref{f:distInc}.
\end{proof}

The version of this stated in the introduction, Theorem~\ref{t:SzTBasic}, follows by
considering Lemma~\ref{l:fgRes} and the special case that $E$ is defined as the zero
set of polynomials over $K$, and setting $\epsilon := \frac1{dt-1}$.

\begin{remark} \label{r:bounds}
  By examining the proof, in the case $n=1$ one can obtain a bound on the
  exponent of the resulting distal cell decomposition giving $t \leq
  2(q^{d^3}+1)$ where $q = |{\operatorname{res}}(K)|^r$ and $d$ is as in the proof of
  Lemma~\ref{l:fin-res-comp}. Indeed, this is the exponent arising from bounding the
  number of balls used in Lemma~\ref{l:B-rel-distal-local}(i), and neither
  Lemma~\ref{l:B-rel-distal-local}(ii) nor Lemma~\ref{l:dd-feq} increase the exponent (for
  the latter case, this follows from the structure of the proof, since each
  instance $\zeta(x,\widetilde {d})$ gives rise to a single instance of the eventual
  formula).

  So we obtain the corresponding explicit bounds in Fact~\ref{f:distInc}. However,
  we have no reason to expect these bounds to be anything like optimal.

  For $n>1$, calculating explicit bounds is complicated by the fact that when
  reducing to one variable a USHD for a quantified formula is used, so one
  needs a bound on the degrees in the quantifier-free formula obtained by
  quantifier elimination in ACVF. This quantifier elimination is primitive
  recursive \cite{Weispfenning}, so in principle this could be done, yielding
  an effective algorithm for computing an exponent $t$ for a given $E$
  (uniform in definable families). But we do not attempt to make this explicit
  here.

  Instead, we illustrate the idea by showing that in the special case of
  Szemerédi-Trotter, $E = \{ ((x,y),(a,b)) : y=ax+b \}$, we can take $t :=
  4(q+1)$.

\newcommand{{\overline{y}}}{{\overline{y}}}
\newcommand{{\overline{z}}}{{\overline{z}}}
\newcommand{{\overline{w}}}{{\overline{w}}}
  The proof of Lemma~\ref{l:B-rel-distal-local}(i) in this case gives a USHD
  $\zeta(y,x,{\overline{z}})$ for $\phi(y;x,(a,b)) := (x,y)E(a,b)$ over $K$, expressing
  that $y$ is an element of a boolean combination of the points
  $z_{i,1}x+z_{i,2}$ and the balls spanned by pairs of such points, with at
  most $2(q+1)$ such points involved. Using coding to choose the form of the
  boolean combination, this has exponent $\leq 2(q+1)$.

  By \cite[Theorem~2.1]{Weispfenning}, if an $\mathcal{L}_{\operatorname{div}}$ qf-formula
  $\psi(x,{\overline{y}},{\overline{z}})$ is linear in $x,{\overline{y}}$, i.e.\ each polynomial has degree 1 in
  $x$ and each $y_i$, then $\exists x. \psi(x,{\overline{y}},{\overline{z}})$ is equivalent modulo
  ${\operatorname{ACVF}}$ to a qf-formula linear in ${\overline{y}}$.

  Now the formula $\zeta(y,x,{\overline{z}}) \rightarrow  (x,y)Ew$ is linear in $x,y$,
  so $\forall y. (\zeta(y,x,{\overline{z}}) \rightarrow  (x,y)Ew)$ is equivalent to a qf-formula
  which is linear in $x$.
  Similarly $\forall y. (\zeta(y,x,{\overline{z}}) \rightarrow  \neg(x,y)Ew)$ is equivalent to a
  qf-formula linear in $x$, and the two can be coded into a single qf-formula
  linear in $x$. This then itself admits (by the $n=1$ case of the present
  Remark with $d=1$) a USHD $\xi(x,{\overline{w}})$ over $K$ of exponent $\leq 2(q+1)$.
  Then $\xi(x,{\overline{w}}) \wedge \zeta(y,x,{\overline{z}})$ is a USHD for $E$ over $K$ of exponent
  $\leq 2(q+1) + 2(q+1) = 4(q+1)$.
  In symmetric form, this gives a bound of $O(N^{\frac32 -
  \frac1{16(q+1)-2}})$ on the number of incidences of $N$ lines and $N$
  points.

  As a final remark, note that although Theorem~\ref{t:SzT} does apply in
  characteristic 0, e.g.\ to $K={\mathbb{Q}}_p$, the bounds we obtain in this way are
  worse than those obtained from \cite{FoxEtAl} by embedding ${\mathbb{Q}}_p$ in
  ${\mathbb{C}}={\mathbb{R}}^2$, even for $p=2$.
\end{remark}

\begin{question}
  Is the dependence on $q$ in these bounds necessary?
  For example, does there exist $\epsilon>0$ such that for all primes $p$
  there exists $C$ such that for all $X,A \subseteq  {\mathbb{F}}_p(t)^2$ we have
  $|\{((x,y),(a,b)) \in X\times A : y=ax+b\}| \leq
  C\max(|X|,|A|)^{\frac32-\epsilon}$?
  (Remark~\ref{r:bounds} yields a bound depending on $p$ of $\epsilon =
  \frac1{16p+14}$ in this case. Meanwhile one can obtain a lower bound
  exponent of $\frac43$ by considering a rectangular example with bounded
  degree polynomials, ${\mathbb{F}}_p[t]_{<n} \times {\mathbb{F}}_p[t]_{<2n}$.)
\end{question}

\section{Elekes-Szabó consequences}
\newcommand{{\operatorname{ccl}}}{{\operatorname{ccl}}}
\newcommand{{\operatorname{trd}}}{{\operatorname{trd}}}
\providecommand{\bdl}{\boldsymbol\delta}
Elekes-Szabó \cite{ES} exploit incidence bounds in characteristic zero to find
that commutative algebraic groups are responsible for ternary algebraic
relations with asymptotically large intersections with finite grids.
In \cite{BB-cohMod}, this is generalised to relations of arbitrary arity. In
this section, we remark that these arguments go through in the present
positive characteristic context, at least if we restrict to the 1-dimensional
situation of \cite[Theorem~1.4]{BB-cohMod}.

Let $K_0$ be a field admitting a valuation with finite residue field (e.g.\ a
function field over a finite field).
Let ${\mathcal{U}}$ be a non-principal ultrafilter on $\omega$.
Define
$$K' := ((K_0)^{\mathcal{U}})^{\operatorname{alg}} \leq  ((K_0)^{\operatorname{alg}})^{\mathcal{U}} =: K.$$
For $r\geq 1$, let
$$K_r := \{ a \in (K_0)^{\operatorname{alg}} : \deg(K_0(a)/K_0) | r  \}.$$
\newcommand{\polL{}o\'s}{\polL{}o\'s}
So (by \polL{}o\'s's theorem) we have $K' = \bigcup_{r \in \omega} (K_r)^{\mathcal{U}}$.

We work with the setup of \cite[2.1]{BB-cohMod}, with $(K_0)^{\operatorname{alg}}$ in place of
${\mathbb{C}}$, and in a countable language in which each of these internal sets
$(K_r)^{\mathcal{U}} \subseteq  K$ is definable.

\begin{theorem} \label{t:ES}
  Let $K_0$ be a field admitting a valuation with finite residue field.
  Let $V \subseteq  {\mathbb{A}}^n$ be an affine algebraic variety defined over $K_0$ of
  dimension $d$.
  Then at least one of the following holds:
  \begin{enumerate}[(i)]\item $V$ admits a powersaving on $K_0$: there exist $C,\epsilon > 0$ such that
  for all $X_i \subseteq_{{\operatorname{fin}}}  K_0$, $i=1,\ldots ,n$, we have
  $$|V(K_0) \cap \prod_i X_i| \leq  C(\max_i |X_i|)^{d-\epsilon}.$$
  \item $V$ is \emph{special}: $V$ is in co-ordinatewise
  correspondence\footnote{As defined in \cite[Definition~1.1]{BB-cohMod}} with
  a product $\prod_i H_i \leq  \prod G_i^{n_i}$ of connected subgroups of $H_i$
  of powers $G_i$ of 1-dimensional algebraic groups.
  \end{enumerate}
\end{theorem}
\begin{proof}
\renewcommand{\a}{{\overline{a}}}
  Let $K' \leq  K$ be as above. Also let $C_0 \leq  K'$ be a countable algebraically
  closed subfield over which $V$ is defined.

  The proof in \cite{BB-cohMod} goes through, but using Theorem~\ref{t:SzT} in place
  of \cite[Theorem~2.14]{BB-cohMod}, and with
  \cite[Theorem~3.3.1]{EvansHrushovski} replacing \cite[Proposition
  A.4]{BB-cohMod}. We describe the necessary changes.

  Firstly, \cite[Theorem~2.15]{BB-cohMod} goes through in the case that $X_i
  \subseteq  ((K_r)^{\mathcal{U}})^{n_i}$ for some $r$ ($i=1,2$). The proof is identical, using
  Theorem~\ref{t:SzT}; the sublinearity of the dependence on $s$ where $K_{2,s}$ is
  omitted, discussed after \cite[Theorem~2.14]{BB-cohMod}, also holds here:
  this is described in \cite[Remark~2.7(2),Corollary~2.8]{CS-ES1d}, and is
  proven explicitly in \cite[Theorem~2.6]{CPS-ES}. (In fact this sublinearity
  isn't necessary for the present 1-dimensional case.)

  Now \cite[Theorem~5.9]{BB-cohMod} goes through for $P \subseteq  (K')^{<\omega}$.
  The proof is identical, except that in the proof of
  \cite[Proposition~5.14]{BB-cohMod}, since $\a,\d \in (K')^{<\omega}$, already
  $\a,\d \in ((K_r)^{\mathcal{U}})^{<\omega}$ for some $r$, and this passes through to the
  types $X_i$ since $(K_r)^{\mathcal{U}}$ is definable, so the above restricted form of
  \cite[Theorem~2.15]{BB-cohMod} applies.

  Next, ${\operatorname{End}}^0_{C_0}(G)$ must be redefined as the skew-field of quotients of
  ${\operatorname{End}}_{C_0}(G)$ (this agrees with ${\mathbb{Q}}\otimes{\operatorname{End}}_{C_0}(G)$ in characteristic
  0); see \cite[3.1]{EvansHrushovski} for discussion of the possibilities.

\newcommand{{\mathcal{G}}}{{\mathcal{G}}}
\newcommand{{\overline{x}}}{{\overline{x}}}
\newcommand{{\overline{h}}}{{\overline{h}}}
  Finally, we indicate how to circumvent the use of \cite[Proposition
  A.4]{BB-cohMod}, which is proven only in characteristic 0, in the
  1-dimensional case. Where this is applied in
  \cite[Proposition~6.1]{BB-cohMod},
  we have $a_i \in K'$ ($i=1,\ldots ,n$) such that ${\mathcal{G}}_\a = \{ {\operatorname{acl}}^0(a_i) : i \}$
  embeds in a projective subgeometry of the ${\operatorname{acl}}^0$-geometry ${\mathcal{G}}_K$ of $K$.
  (Here we have $a_i \in K'$ rather than $a_i \in K^{<\omega}$, as this is what
  arises in the proof, via \cite[Theorem~7.4]{BB-cohMod}, in the 1-dimensional
  case corresponding to the statement of the current theorem.)
  By \cite[Theorem~3.3.1]{EvansHrushovski}, there is a 1-dimensional algebraic
  group $G$ over $C_0$ and generic ${\overline{x}} \in G^m$ over $C_0$ (where
  $m=\dim({\mathcal{G}}_\a)$) and $A \in \operatorname{Mat}_{n,m}({\operatorname{End}}(G))$ such that, setting ${\overline{h}} :=
  A{\overline{x}}$, we have ${\operatorname{acl}}^0(h_i) = {\operatorname{acl}}^0(a_i)$. Then $\operatorname{loc}^0({\overline{h}}) = AG^m$ is a
  connected algebraic subgroup of $G^n$, as required.

  The rest of the proof goes through unchanged.
\end{proof}

\begin{remark}
  The only obstruction to pushing this to higher dimension, i.e.\ to a version
  of \cite[Theorem~1.11]{BB-cohMod}, is the need to generalise the higher
  dimensional version of Evans-Hrushovski \cite[Proposition A.4]{BB-cohMod} to
  positive characteristic.

  Meanwhile, the proof of the converse direction (showing that every special
  variety admits no powersaving) makes essential use of the characteristic 0
  assumption in \cite[Proposition~7.10]{BB-cohMod}; this may not be so easy to
  generalise, and the statement may need to change.

  For these reasons, we leave positive characteristic analogues of
  \cite[Theorem~1.11]{BB-cohMod} to future work.
\end{remark}

\bibliographystyle{amsalpha}