% 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}