\setlength{\paperheight}{150cm}
\usepackage[left=100px,right=100px,top=10px,bottom=10px]{geometry}

!newop eq
!newop tp
!newop dcl
!newop acl
!newop im
!newop Th
!newop ACVF
!newop fin
!newop res
!newop alg
!newop Gal
!newbb V
!newbb N
!newbb Z
!newbb Q
!newbb R
!newbb K
!newbb F
!newbb A
!newcal M
!newcal U
!newfrak C
!renewtup b
!renewtup d
!renewcal L
!renewop div

\newcommand{\Lang}{\mathcal{L}}
\newcommand{\Leq}{\mathcal{L}^{\eq}}
\newcommand{\Ldiv}{\mathcal{L}_{\"div}}
\newcommand{\Teq}{T^{\eq}}
\providecommand{\eps}{\epsilon}

\newcommand{\defn}[1]{{\bf #1}}

\begin{document}
\title{Incidence bounds in positive characteristic via valuations and distality}

\author{Martin Bays}
\date{20.05.2021}

\maketitle
%Abstract:
%    Joint work with \textbf{Jean-François Martin}.
%    The Szemerédi-Trotter theorem bounds the number of incidences between
%    finite sets of points and straight lines in the real plane, and
%    generalisations to other algebraic binary relations play an important
%    role in understanding the interaction between (pseudo)finite sets and
%    field structure in zero characteristic. In positive characteristic,
%    these incidence bounds fail drastically without further restrictions,
%    but may be expected to hold under certain conditions. We confirm this in
%    the case of fields admitting a valuation with finite residue field, e.g.
%    finitely generated extensions of $\F_p$, by seeing that the restricted
%    distality provided by the valuation suffices to trigger a result of
%    Chernikov-Galvin-Starchenko.
%    .
This talk is based on joint work with \textbf{Jean-François Martin}.
\tableofcontents

# Background
## Incidence bounds in characteristic zero
***)
Factn[Szemerédi-Trotter '83]:
    There exists $C (- \R$ such that,
    given $N$ points and $N$ lines in $\R^2$,
    the number of incidences is bounded as
    $$ |{ \{ (p,l) : p (- l \} }| <= C(N^{\frac32 - \frac16}) .$$
    .

** This has been generalised in various ways. In particular:

Factn[Elekes-Szabó '12]:
    If $(C_b)_{b (- B}$ is an algebraic family of distinct 
    irreducible plane curves over a field $K$ of characteristic 0,
    there are $C,\eps > 0$ such that
    given $N$ points in $K^2$ and $N$ curves in the family,
    $$ |{ \{ (a,b) : a (- C_b \} }| <= C(N^{\frac32-\eps}).$$
    .

** Hrushovski: this indicates a certain /modularity/ of the interaction 
between (pseudo)finite sets and field structure.

** In particular, abelian groups are the only source of relations on which 
finite sets ``maximally accumulate'':

Factnb[Elekes-Szabó '12 ($m=3$), Raz-Sharir-de Zeeuw '18 ($m=4$), B-Breuillard '20]:
    Let $V (= \A^m$ be an irreducible affine variety over a field $K$ of characteristic 0.

    Exactly one of the following holds:
    **(i) $\exists C,\eps > 0.\;\forall X_1,...,X_m (=f K.$
    $$| V(K) \cap (X_1\times...\times X_m) | <= C\max(|X_i|)^{\dim V - \eps};$$
    ** OR: up to finite correspondences on co-ordinates and taking products,
    \\\ $V$ is a subgroup of a power of a 1-dimensional algebraic group.
    *ee*
    .
*e)*

## Incidence bounds in positive characteristic

***) In positive characteristic, these bounds utterly fail:

Remarkn:
    Let $K := \F_p^{\alg}$.
    For any algebraic set $V (= K^n$,
    there is $r>0$ such that for arbitrarily large $n$,
    $$|V(\|F_{p^n})| >= r(p^n)^{\dim V}.$$
    (This follows from the Lang-Weil estimates.)
    .

** However, Hrushovski conjectures that the Zilber trichotomy applies:
\\\ infinite pseudofinite fields should be the only obstruction to modularity.
\\\ (Above it is $\prod_{n --> \U} \|F_{p^n} <= K^\U$.)

\textit{(In the case of the sum-product theorem, this is true,
i.e. failures of sum-product bounds are due to finite subfields
(Bourgain-Katz-Tao, Tao-Vu, Tao, Hrushovski, Wagner).)}

** As an extreme case, this conjecture suggests that for $K$ with 
\textbf{finite} algebraic part $K \cap \F_p^{\alg}$,
e.g. $K = \F_p(t)$,
the characteristic 0 results should go through.
*e)*

## Distality

***)
Definitionn:
  Let $\M$ be an $\Lang$-structure.
  ***)
  Let $\phi(x;y)$ be an $\Lang$ formula, let $A,B (= \M$.

  An $\Lang$-formula $\zeta_\phi(x;z)$ is a \defn{uniform strong honest 
  definition (USHD)} for $\phi$ on $A$ over $B$ if
  for any $a (- A^x$ and finite subset $B_0 (=f B$ with $|B_0| >= 2$,
  there is $d (- B_0^z$
  such that
  $$\tp(a/B_0) -) \zeta_\phi(x,d) |- \tp_\phi(a/B_0)$$
  (where
  $\tp_\phi(a/B_0) := \{ \phi(x,b)^\eps (- \tp(a/B_0) : b (- B_0^y \}$).

  ** If $A = \M$, we omit ``on $A$''.

  ** $B (= \M$ is \defn{distal in $\M$} if every $\Lang$-formula $\phi(x;y)$ 
  has a USHD on $B$ over $B$.
  *e)*
  .

** Reduction to one variable:

Factn{distal1}:
    $B (= \M$ is distal in $\M$ iff any $\Lang$-formula $\phi(x;y)$ with $|x| 
    = 1$ has a USHD on $B$ over $B$.
    .
Proofidea:
    Given $a,b (- B$ and $\phi(x,y;z)$ and $B_0 (=f B$,
    \\\say $\tp(a/bB_0) -) \zeta(x,b,c) |- \tp_{\phi(x;y,z)}(a/bB_0)$ with $c (- B_0^w$.

    Now say $\tp(b/B_0) -) \theta(y,c') |- \tp_{\forall x. (\zeta(x,y,w) -> 
    \phi(x,y,z))}(b/B_0)$.

    Then $\tp(ab/B_0) -) \zeta(x,y,c) /\ \theta(y,c') |- \tp^+_{\phi(x,y;z)}(ab/B_0)$.

    Now repeat with $\neg\phi$.
    Uniformity follows through.
    .

**
Examplen:
    If $B = (b_i)_i (= \M$ is a ${}$-indiscernible sequence,
    \\\and there is an $\Lang$-formula $\theta_<$ with $\M |= 
    \theta_<(b_i,b_j) <=> i<j$,
    \\\then $B$ is distal in $\M$.
    .
**
Factn[Chernikov-Simon]:
  $\Th(\M)$ is \defn{distal} iff $\M$ is distal in $\M$.
  .
%** Let $B (= \M$. If $(B; (\phi(B))_{\phi \text{ an $\Lang$-formula}})$ 
%admits QE, it is distal iff $B$ is distal in $\M$.

%** If $B (= \M$ is distal in $\M$, then so is any $B' (= B$.

** Distality implies incidence bounds:
Factb[Chernikov-Galvin-Starchenko, Chernikov-Starchenko '20]{distInc}:
    Suppose $B (= \M$ is distal in $\M$ and $\phi(x;y)$ is an $\Lang$-formula.

    Suppose $\phi(B;B)$ is $K_{d,s}$-free,
    \\\i.e. there is no $X_0\times Y_0 (= \phi(B;B)$ with $|X_0| = d$ and 
    $|Y_0| = s$.

    Let $\zeta_\phi(x,z)$ be a USHD for $\phi$ on $B$,
    and let $t := |z|$.

    Then there exists $C (- \R$ such that for $X_0 (=f B^x$ and $Y_0 (=f B^y$,
    $$|\phi(X_0;Y_0)| <= C(|X_0|^{\frac{(t-1)d}{td-1}} 
    |Y_0|^{\frac{td-t}{td-1}} + |X_0| + |Y_0|).$$
%
%    In particular, if $|X_0|,|Y_0| < N$ and $d=2$,
%    there is $\eps = \eps(t) = \frac1{4t-2} > 0$ such that
%    $$|\phi(X_0;Y_0)| <= O_\phi(N^{\frac32 - \eps}).$$
    .
*e)*

# The result
## Statements
***)
Theorem{main}:
    Let $k$ be a valued field with finite residue field.
    \\\Then $k$ is distal in $k^{\alg} |= \"ACVF$.
    .

(Note: a positive characteristic valued field with finite residue field is not distal as a structure, nor even NIP (by Kaplan-Scanlon-Wagner).)

**
So by Fact~{distInc}:

Corollaryn:
  Let $k$ be a valued field with finite residue field.

  Let $E (= k^n \times k^m$ be quantifier-free definable in $\Ldiv(k)$.

  Suppose $E$ is $K_{d,s}$-free, where $d,s (- \N$.

  Then there exist $t,C>0$ such that
  for $A_0 (=f k^n$ and $B_0 (=f k^m$,
  $$|E \cap (A_0 \times B_0)| <= C(|A_0|^{\frac{(t-1)d}{td-1}} 
  |B_0|^{\frac{td-t}{td-1}} + |A_0| + |B_0|).$$
  .

** In particular this yields a Szemerédi-Trotter-style result:
Corollaryn:
  Suppose $(C_b)_{b (- B (= k^m}$ is an algebraic family of distinct 
  irreducible plane curves over a field $k$ which admits a valuation with finite residue field.

  Then $E := \{ (a,b) : a (- C_b(k) \} (= k^{2+m}$ is $K_{2,s}$-free for some 
  $s (- \N$.

  So there exist $\eps_0,C>0$ such that for $A_0 (=f k^2$ and $B_0 (=f k^m$,
  $$|E \cap (A_0 \times B_0)| 
  <= C(|A_0|^{1-\eps_0} |B_0|^{\frac12(1+\eps_0)} + |A_0| + |B_0|)$$
  ($\eps_0 := \frac1{2t-1} > 0$), or in symmetric form:
  $$|E \cap (A_0 \times B_0)| <= C'(\max(|A_0|,|B_0|))^{\frac32-\eps}$$
  ($\eps := \frac{\eps_0}2 > 0$, $C' := 3C$).
  .

%**
%Moreover, it will follow from the proof that $t$ in Fact~{distInc} can be 
%bounded in terms of the size of the residue field.
*e)*

## Fields admitting finite residue field
Examplen:
    The $t$-adic valuation on $\F_p(t)$ has residue field $\F_p$.

    Similarly, any finitely generated extension of $\F_p$, i.e. any function 
    field over a finite field, admits a valuation with finite residue field.
    %(e.g. $\F_q(s,t,\sqrt{s+t}) (= \F_q((s))((t))^{\alg}$.)
    .

However:\
Proposition:
  For any prime $p$,
  there exists an algebraic extension $L >= \F_p(t)$ such that $L\cap 
  \F_p^\alg = \F_p$ but no valuation on $L$ has finite residue field.
  .
Such an $L$ can be built by recursively adjoining Artin-Schreier roots which 
force Artin-Schreier extensions of the residue fields of valuations on 
previously built fields; using the Artin-Schreier version of Kummer theory, 
one can always do this without extending the algebraic part.

# Proof of Theorem~{main}

***) Let $L |= \"ACVF$ and let $k (= L$ be a subfield with $\res(k)$ finite.

** We want to see that $k (= L$ is distal in $L$.

** By reduction to 1 variable, it suffices to see:
\\\any $\phi(x,y)$ with $|x| = 1$ has a USHD over $k$.

*e)*

## Compressing balls
***) By QE, for $a (- k$, $\phi(L,a)$ is a boolean combination of open and closed balls 
$$v(x-a') > \alpha \text{ or } v(x-a') >= \alpha$$
centred at points $a'$ with $\deg(k(a')/k)$ bounded, say dividing $d$.

** Let $B_{k,d}$ be the set of balls (closed and open) centred at points of 
degree $|d$ field extensions of $k$ within $L$.

Using the bounded size of the residue field of such extensions, we obtain:

Lemman:
    $x (- y$ has a USHD over $B_{k,d}$.
    .
Proof:
    ***) Let $a (- L$ and $B_0 (=f B_{k,d}$.
    ** Then $x (- (b \\ \bigcup_{i<s}b_i) |- \tp_{ (- }(a/B_0)$
    where
        ***) $b$ is smallest in $B_0$ such that $a (- b$ (or $b := L$).
        ** $b_1,...,b_s$ are the maximal proper subballs of $b$ in $B_0$.
        *e)*
    ** Sufficient to uniformly bound $s$.
    ** By ultrametricity, joins of finitely many balls are joins of two.

        So we may assume $B_0$ is closed under $\vee$
        \\\ (where $b' \/ b'' :=$ smallest ball containing both).
    ** Assume $s > 1$.
    ** Say $p_i (- b_i$ is of degree $|d$ over $k$, and let $\alpha (- v(L)$ be the radius of $b$.
    ** Now $$i |-> \lambda_i := \res({ \frac{p_i-p_1}{p_2-p_1} })$$
    is an injection of $\{1,...,s\}$ into $\res(L)$:
    ***) If $i/=j$ then $b_i \/ b_j = b$, so $v(p_i-p_j)=\alpha$.
    ** Now suppose $\lambda_i=\lambda_j$. 
    Then $\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$.
    *e)*

    ** Say $\res(k) = \F_q$.
    ** Since each $\lambda_i$ is in the residue field of an extension of $k$ of 
    degree $|d^3$, by the valuation inequality
    $$\lambda_i (- \F_{q^{d^3}}.$$
    ** So $s <= q^{d^3}$.
    *e)*
    .

** But this is not enough on its own.

To show that $\phi(x,y)$ has a USHD over $k$:
given $C (=f k$ we have to determine $\tp_\phi(a/C)$ using only $C$ as 
parameters -- but the balls involved will generally not be defined over $C$!

** So we need to be more careful with the QE.
*e)*

## Compressing cheeses

***) $\phi(L,a)$ has a unique-up-to-permutation ``Swiss cheese decomposition'' 
as a finite union of disjoint cheeses,
$$\phi(L,a) = \bigcup_i (b_i \\ \bigcup_j b_{ij}),$$
where each cheese is a ball $b_i$ minus a finite union of disjoint proper subballs $b_{ij}$,
\\\and no $b_i$ is equal to any hole $b_{i'j}$.

** Moreover:

Factn[Uniform Swiss Cheese Decomposition]:
    There are $N$ and $d$ depending only on $\phi$ such that for all $a (- L^y$,
    $\phi(L,a)$ has Swiss cheese decomposition involving $<=N$ balls, where each 
    ball contains a point in a degree $|d$ field extension of the subfield 
    generated by $a$.
    .

** Increasing $N$ and allowing the empty ball and its complement, we can 
assume the form of the decomposition is constant, given by a Boolean term $D$.
** Let $X (= B^N$ be the set defined by the inclusion relations required for 
$D(b_1,...,b_N)$ to be a Swiss cheese decomposition.
** So $D : X --> \text{[codes for subsets]}$ is definable with boundedly 
finite fibres,
and
$$D(X \cap (B_{k,d})^N) )= \{ \ulcorner \phi(x,c) \urcorner : c (- k^y \}.$$
*e)*

## Collapsing USHDs

***) We conclude by a general elementary model theoretic lemma on USHDs:

Lemman:
    Let $f$ be definable with boundedly finite fibres.
    Let $C (= \"im(f)$.

    If $\psi(x,f(z))$ has a USHD over $f^{-1}(C)$,
    \\\then $\psi(x,y)$ has a USHD over $C$.
    .
!newtup z
(Explicitly, to conclude:
***) apply this Lemma to $x (- D(\z)$, which has a USHD over $B_{k,d}$ by ball 
compression;
** this yields that $x (- w$ has a USHD over
$$\{ \ulcorner \phi(x,c) \urcorner : c (- k^y \},$$
** hence $\phi(x,y)$ has a USHD over $k$.)
*e)*

Proofidea:
  Compress $f^{-1}(C_0)$ with $\zeta(x,\~d)$,
  then find $C_1 (= C_0$ bounded by the fibre size
  such that if $f(\~d') = f(\~d)$ and $\zeta(x,\~d')$ implies the instances 
  for $C_1$, then it implies all.
  Then ``exists such a $\~d'$ over $f(\~d)$'' is a USHD.
%
%    More precisely:\
%    ***) Let $a (- \M^x$ and $C_0 (=f C$.
%    ** We have $\~d (- f^{-1}(C)$ such that $\tp(a/f^{-1}(C_0) -) \zeta(x,\~d) |- \tp_{\psi(x,f(z))}(a/f^{-1}(C_0))$,
%    and $f(\~d) =: d (- C^{|z|}$.
%    ** There is $C_1 (= C_0$ with $|C_1| <= |f^{-1}(d)|$,
%    such that if $f(\~d') = d$ and 
%    $\zeta(x,\~d') |- \tp_{\psi(x,y)}(a/C_1)$,
%    then already
%    $\zeta(x,\~d') |- \tp_{\psi(x,y)}(a/C_0)$.
%    ** Then $\exists \~d'. (f(\~d') = d /\ 
%    [\zeta(x,\~d') |- \tp_{\psi(x,y))}(a/C_1)])$ isolates 
%    $\tp_{\psi(x,y)}(a/C_0)$ within $\tp(a/C_0)$.
%    ** By the bound on $|C_1|$ this works uniformly.
%    *e)*
  .

**
Remarkn:
    Following the proof gives a bound on the exponent in the distal cell 
    decompositions, hence in the incidence bound for $|x| = 1$, of
    $t = 2(q^{d^3}+1)$ where $\res(k) = \F_q$.

    For $|x| > 1$ a bound can in theory be computed, but it involves QE in 
    ACVF.

    For the Szemerédi-Trotter case $\{ ((x,y),(a,b)) : y=ax+b \}$,
    we get $t = 4(q+1)$, giving an exponent in the symmetric form of $\frac32 
    - \frac1{16(q+1)-2}$.

    Question: in the Szemerédi-Trotter case with $\F_p(t)$, could there be an 
    exponent which doesn't depend on $p$? Worst lower bound I know is 
    $\frac43$ (by a similar "rectangular grid" argument as in the char 0 
    case).
    .
*e)*

% One might wonder whether the use of Swiss cheese decomposition, i.e. 
% canonical-up-to-finite boolean combinations, was really essential. I expect 
% so. The following question formulates this more precisely; I expect the 
% answer to be negative.
%Question:
%    If $\phi(x,y)$ is a boolean combination of instances of $\psi(x,f_i(y))$ 
%    where $f_i$ are algebraic quasifunctions,
%    and $\psi$ has a USHD over $\bigcup_i f_i(C)$,
%    does it follow that $\phi$ has a USHD over $C$?
%    .

# Elekes-Szabó consequences

As in the characteristic 0 case, these incidence bounds yield ``modularity of 
coherence'', and hence Elekes-Szabó bounds.

***) Let $k_0$ be a field admitting a valuation with finite residue field.
** For $r>=1$, let
$$k_r := \{ a (- (k_0)^\alg : \deg(k_0(a)/k_0) <= r  \}.$$
** From the proof for $k_0$, we get that \underline{each $k_r$ is also distal} 
in $(k_0)^\alg |= \ACVF$.

** This is sufficient for the arguments of one direction of the 1-dimensional case of the main result of B-Breuillard to go through:

Theoremn:
!renewtup a
!newop trd
!newop ccl
\providecommand{\bdl}{\boldsymbol\delta}
    Let $\U$ be a non-principal ultrafilter on $\omega$.

    Let $k' := ((k_0)^\U)^\alg <= ((k_0)^\alg)^\U =: L$,
    so $k' = \bigcup_{r (- \omega} (k_r)^\U$.

    Let $\xi (- \N^\U \\ \N$.

    $$\bdl(\prod_{i --> \U} X_i) := \"st \log_\xi \lim_{i --> \U} |X_i| (- \R \cup \{\infty\}.$$

    Equip $L$ with the structure generated by countably many internal 
    relations, including each $(k_r)^\U$, such that $\bdl$ is continuous.

    For $\a (- L^{<\omega}$,
    $$\bdl(\a) = \bdl(\tp(\a)) = \inf_{\phi (- \tp(\a)} \bdl(\phi(L)).$$

    $P (= L$ is \defn{coherent} if $\bdl(\a) = \trd(\a)$ for all $\a (- P^{<\omega}$.

    Write $\acl^0$ for field-theoretic algebraic closure.

    Let $P (= k'$ be coherent, and let $\ccl(P) := \{a (- \acl^0(P) : 
    \bdl(a) = \trd(a) \} (= k'$.

    Then $\ccl(P)$ is coherent, and $\acl^0|_{\ccl(P)}$ is a modular 
    pregeometry.
    .

Using the Evans-Hrushovski characterisation of modular subpregeometries of 
$\acl^0$ (proved by Evans-Hrushovski in arbitrary characteristic), one deduces:

Theoremn:
    Let $k_0$ be a field admitting a valuation with finite residue field.
    Let $V (= \A^m$ be an irreducible affine variety over $k_0$.

    At least one of the following holds:
    ***(i) $\exists C,\eps > 0.\;\forall X_1,...,X_m (=f k_0.$
    $$| V(k_0) \cap (X_1\times...\times X_m) | <= C\max(|X_i|)^{\dim V - \eps};$$
    **(ii) Up to finite correspondences on co-ordinates and taking products,
    \\\ $V$ is a subgroup of a power of a 1-dimensional algebraic group.
    *ee*
    .

%Remark:
%    The higher dimensional ("coarse general position") version doesn't 
%    immediately go through, since it needs better bounds (a more uniform 
%    sublinearity in $s$ where we omit $K_{2,s}$, namely not depending on $k$ 
%    where we omit $K_{k,k}$) and a positive characteristic version of higher 
%    dimensional Evans-Hrushovski. (The original ES case $m=3$ assuming general 
%    position (not just cgp) probably goes through directly, but I haven't 
%    checked.)
%
%    Getting a formulation with "exactly one" would also take some more work.
%    .
*e)*

\end{document}
