% AUTOGENERATED FILE; you probably want to edit the .tex.in file, not this.
\input{preamble-article}
\pagestyle{headings}
\usepackage{amssymb,amsmath,enumerate,amsthm,url}
\usepackage{mt}
\usepackage[all,cmtip]{xy}
\usepackage{graphicx}
\providecommand{\Dashv}{\mathrel{\text{\reflectbox{$\vDash$}}}}
\bibliographystyle{alpha}
\begin{document}
\providecommand{\st}{\operatorname{st}}
\providecommand{\M}{\mathcal{M}}
\providecommand{\U}{\mathcal{U}}
\providecommand{\dl}{\delta}
\providecommand{\bdl}{\mathbb{\dl}}
\renewcommand{\O}{\mathcal{O}}
\renewcommand{\P}{\mathbb{P}}

\section{Szemeredi-Trotter and trichotomy}
Notes on various ``Szemeredi-Trotter'' results, and the interpretation in
terms of geometric stability theory given to them by Hrushovski in his paper
``On pseudo-finite dimensions''.

\subsection{Szemeredi-Trotter}

\begin{theorem}[Szemeredi-Trotter 1983]
    Given $n$ points and $m$ lines in $\R^2$,
    the number of point-line incidences is $\O(n^{2/3}m^{2/3} + n + m)$.
\end{theorem}

\begin{remark}
    In particular, given $\leq n$ points and $\leq n$ lines, the number of
    incidences is $\O(n^{4/3})$.

    $4/3 = 3/2 - 1/6$.
\end{remark}

\begin{theorem}[T\'oth 2003]
    Same statement, but for the complex plane $\C^2$,
    where a "line" is a coset of a 1-dimensional $\C$-subspace.
\end{theorem}

\begin{remark}
    The same statement for the projective plane $\P^2(\C)$ follows
    (since by applying a M\"obius transformation, WLOG none of our points or
    lines are at infinity).
\end{remark}

We can think of incidences as the edges $E$ of a bipartite graph between
a set of "points" and a set of "lines".
Recall Elekes-Szabo define the \underline{combinatorial dimension} of a bipartite graph,
with respect to a parameter $b$.

$E$ \defnstyle{omits $K_{b,k}$} if the common intersection of any $k$ distinct
"lines" has less than $b$ "points". This implies that $E$ has combinatorial
dimension $\leq k$ with respect to $b$.

\begin{remark}
    In the cases above, $G$ omits $K_{2,2}$ - distinct lines meet in at most
    one point (exactly one in case of $\P^2(\C)$), and dually.
\end{remark}

\begin{theorem}[Elekes-Szabo 2012 (symmetric version)]
    Suppose $P$, $L$, and $I \subseteq  P \times L$ are complex algebraic varieties,
    or just constructible sets in $\C$, i.e.\ definable in $(\C;+,\cdot)$.

    Let $X_P \subseteq  P$ and $X_L \subseteq  L$ with $|X_P|,|X_L| \leq  n$,
    let $E := I \cap (X_P \times X_L)$,
    and suppose $E$ has combinatorial dimension $\leq k$.

    Then the number of incidences $|E|$ is
    $\O(n^{\frac{2k-1}{k} - \frac{(k-1)^2 }{ k(kD-1)} + \epsilon})$
    for any $\epsilon>0$,
    where $D>0$ depends only on $\dim(L)$.

    ($k=2$: $\O(n^{\frac 32 - \frac 1{2(2D-1)} + \epsilon})$;
    in the T\'oth theorem, $D=2$ and there's no $\epsilon$.)

    % k - (k-1)(D(k-1))/(Dk-1) = Dkk-k-Dkk+2Dk-D / Dk-1 = 2Dk-D-k / Dk-1 =
    % (2k-1)D - k / kD-1 = ((2k-1)/k) - (k-1)^2 / (k(kD-1))
\end{theorem}

\begin{theorem}[Fox-Pack-Sheffer-Suk-Zahl 2014]
    Suppose $I \subseteq  \R^{d_p} \times \R^{d_l} =: P \times L$ is semialgebraic,
    i.e.\ definable in $(\R;+,\cdot)$.
    
    Let $X_P \subseteq  P$ and $X_L \subseteq  L$ with $|X_P|,|X_L| \leq  n$,
    let $E := I \cap (X_P \times X_L)$.
    
    \begin{enumerate}[(i)]\item Suppose $E$ omits $K_{k,k}$.
        Then $|E|$ is
        $\O( n^{\frac{2 d_p d_l - d_l - d_p }{ d_p d_l - 1 } + \epsilon } )$
        for any $\epsilon>0$.

    \item Suppose $I$ is algebraic and $E$ omits $K_{b,k}$.
        Then $|E|$ is
        $\O(n^{\frac{2k-1}{k} - \frac{(k-1)^2 }{ k(kD-1)} + \epsilon})$
        for any $\epsilon>0$,
        where $D = \max(d_l,d_p)$.
    \end{enumerate}
\end{theorem}

\begin{theorem}[Chernikov-Galvin-Starchenko, Dec 2016]
    $I \subseteq  \R^2 \times \R^{d_l}$ definable in an o-minimal expansion of a field.
    Then (i) of the previous theorem holds, but without the $\epsilon$.
\end{theorem}

\begin{theorem}[Basu-Raz, Nov 2016]
    Same, but only for $d_l=2$.
\end{theorem}

\subsection{Modularity, pseudoplanes, and quasidesigns}


\begin{definition}
    A strongly minimal theory $T$ is \underline{locally modular}
    if whenever $\M_0 \prec  \M \vDash  T$, the lattice of algebraically closed subsets of
    $M$ containing $M_0$ satisfies the modular identity:
    for $A,B,C$ with $A \leq  C$,
        \[ A\vee (B\wedge C) = (A\vee B)\wedge C .\]

    Equivalently, for $A,B \subseteq  M$, if $c \in \acl(M_0AB) \setminus \acl(M_0A)$, then
    $\acl(M_0Ac) \cap \acl(M_0B) \neq  \acl(M_0)$.

    Equivalently, $\dim( A\vee B / B) = \dim( A / A\wedge B )$ for any
    algebraically closed $A,B \supseteq M_0$.

    $T$ is \underline{trivial} if $A\vee B = A \cup B$,
    i.e.\ $\acl(X) = \bigcup_{x \in X} \acl(x)$ for any $X$.
\end{definition}

\begin{example}
    The lattice of vector subspaces of a vector space is modular:
    $c=a+b \Rightarrow  b=c-a$
\end{example}

\begin{definition}
    A (definable) relation $I \subseteq  P \times L$ is a \underline{quasidesign} if all fibres
    $\pi_1^{-1}(p)$ and $\pi_2^{-1}(l)$ are infinite, and it omits
    $K_{t,2}$ for some $t \in \N$; it is a \underline{pseudoplane} if it also omits
    $K_{2,s}$ for some $s \in \N$.

    A (2,3,2)-pseudoplane is a pseudoplane with $\dim(P)=\dim(L)=2,
    \dim(I)=3$.
\end{definition}

\begin{theorem}[Zilber's Weak Trichotomy]
    $T$ strongly minimal.
    \begin{enumerate}[(i)]\item $T$ is not locally modular iff $T$ interprets a (2,3,2)-pseudoplane.
    \item If $T$ is locally modular but non-trivial, then $x=x$ is in
        finite-to-finite definable correspondence with a (1-based) abelian
        group.
    \end{enumerate}
\end{theorem}

Hrushovski: The above Szemeredi-Trotter statements imply that pseudofinite
subsets of (algebraically closed) fields of internal characteristic 0 "have"
no pseudoplane (or even quasidesign), so "are modular". Making this precise
seems not to be straightforward (but even the idea seems helpful).

Let $(F,X) = \prod_i(F_i,X_i) / \U$ be an ultraproduct of fields equipped with
distinguished finite subsets.

For $Y \subseteq  F^n$, define $\bdl(Y) := \st(\log(|Y|) / \log(|X|))$.
For $A \subseteq  F^n$ constructible, $A(X) := A \cap X^n$.
Then $\bdl(A(X)) \leq  \dim(A)$.
If $\bdl(A(X)) = \dim(A)$, say $A$ is ``$X$-rich''.

\begin{corollary}[of Elekes-Szabo's Szemeredi-Trotter, k=2]
    Suppose $\operatorname{char}(F_i)=0$, and $P,L,I \subseteq  P \times L$ are constructible sets
    in $F$.
    Suppose $I(X) \subseteq  P(X) \times L(X)$ is a quasidesign.
    Then
    \begin{align*} \bdl(I(X)) &\leq 
        ( \frac 32 - \frac 1{2(2D-1)} ) \max(\bdl(P(X)),\bdl(L(X))) \\
        &< \frac 32 \max(\bdl(P(X)),\bdl(L(X))) .\end{align*}

    In particular, if $\dim(P)=2=\dim(L)$ and $\dim(I)=3$,
    it can not be that $P,L,I$ are all $X$-rich.
\end{corollary}

Hrushovski goes on to define a "probability logic" structure $(F,X)^{\operatorname{prob}}$
and a notion of modularity, such that an adaptation of the proof of the Weak
Trichotomy theorem yields firstly that this lack of pseudoplanes implies
modularity in internal characteristic 0, and furthermore a reproof of the
following version of a theorem of Elekes-Szabo:

\begin{theorem}[Elekes-Szabo 2012]
    Suppose $R \subseteq  F^3$ is an irreducible subvariety, $\dim(R)=2$, and
    $\dim((\pi_i \times \pi_j)(R)) = 2$ for $i \neq j$.
    Suppose $R$ is $X$-rich.
    Then $R$ is in co-ordinatewise correspondence with the graph of the group
    operation of a 1-dimensional algebraic group.
\end{theorem}

Furthermore, Hrushovski conjectures that the underlying explanation for these
Szemeredi-Trotter results is the truth of the Zilber Trichotomy Conjecture in
this context:
\begin{conjecture}[Hrushovski]
    If $(X,F)^{\operatorname{prob}}$ is not (locally) modular, it defines a subfield
    $k \subseteq  F$ with $\bdl(k)=1$.

    In particular, if the ultraproduct $^*F_0$ of the prime fields of the
    $F_i$ has $\bdl(^*F_0) = \infty$, then there's no $X$-rich pseudoplane.
    A positive characteristic version of Elekes-Szabo (previously conjectured
    by Bukh-Tsimerman) follows.
\end{conjecture}
\end{document}
