!newop st
!newcal M
!newcal U
\providecommand{\dl}{\delta}
\providecommand{\bdl}{\mathbb{\dl}}
\renewcommand{\O}{\mathcal{O}}
\renewcommand{\P}{\mathbb{P}}
## 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''.
# Szemeredi-Trotter
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)$.
.
Remark:
In particular, given $<=n$ points and $<=n$ lines, the number of
incidences is $\O(n^{4/3})$.
$4/3 = 3/2 - 1/6$.
.
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.
.
Remark:
The same statement for the projective plane $\P^2(\C)$ follows
(since by applying a MÃ¶bius transformation, WLOG none of our points or
lines are at infinity).
.
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 _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 $<=k$ with respect to $b$.
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.
.
Theorem[Elekes-Szabo 2012 (symmetric version)]:
Suppose $P$, $L$, and $I (= P \times L$ are complex algebraic varieties,
or just constructible sets in $\C$, i.e. definable in $(\C;+,\cdot)$.
Let $X_P (= P$ and $X_L (= L$ with $|X_P|,|X_L| <= n$,
let $E := I \cap (X_P \times X_L)$,
and suppose $E$ has combinatorial dimension $<=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))
.
Theorem[Fox-Pack-Sheffer-Suk-Zahl 2014]:
Suppose $I (= \R^{d_p} \times \R^{d_l} =: P \times L$ is semialgebraic,
i.e. definable in $(\R;+,\cdot)$.
Let $X_P (= P$ and $X_L (= L$ with $|X_P|,|X_L| <= n$,
let $E := I \cap (X_P \times X_L)$.
**(i) 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$.
**(ii) 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)$.
*ee*
.
Theorem[Chernikov-Galvin-Starchenko, Dec 2016]:
$I (= \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$.
.
Theorem[Basu-Raz, Nov 2016]:
Same, but only for $d_l=2$.
.
# Modularity, pseudoplanes, and quasidesigns
Definition:
A strongly minimal theory $T$ is _locally modular_
if whenever $\M_0 <~ \M |= T$, the lattice of algebraically closed subsets of
$M$ containing $M_0$ satisfies the modular identity:
for $A,B,C$ with $A <= C$,
\[ A \/ (B /\ C) = (A \/ B) /\ C .\]
Equivalently, for $A,B (= M$, if $c (- \acl(M_0AB) \\ \acl(M_0A)$, then
$\acl(M_0Ac) \cap \acl(M_0B) /= \acl(M_0)$.
Equivalently, $\dim( A \/ B / B) = \dim( A / A /\ B )$ for any
algebraically closed $A,B )= M_0$.
$T$ is _trivial_ if $A \/ B = A \cup B$,
i.e. $\acl(X) = \bigcup_{x (- X} \acl(x)$ for any $X$.
.
Example:
The lattice of vector subspaces of a vector space is modular:
$c=a+b => b=c-a$
.
Definition:
A (definable) relation $I (= P \times L$ is a _quasidesign_ if all fibres
$\pi_1^{-1}(p)$ and $\pi_2^{-1}(l)$ are infinite, and it omits
$K_{t,2}$ for some $t (- \N$; it is a _pseudoplane_ if it also omits
$K_{2,s}$ for some $s (- \N$.
A (2,3,2)-pseudoplane is a pseudoplane with $\dim(P)=\dim(L)=2,
\dim(I)=3$.
.
Theorem[Zilber's Weak Trichotomy]:
$T$ strongly minimal.
**(i) $T$ is not locally modular iff $T$ interprets a (2,3,2)-pseudoplane.
**(ii) If $T$ is locally modular but non-trivial, then $x=x$ is in
finite-to-finite definable correspondence with a (1-based) abelian
group.
*ee*
.
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 (= F^n$, define $\bdl(Y) := \st(\log(|Y|) / \log(|X|))$.
For $A (= F^n$ constructible, $A(X) := A \cap X^n$.
Then $\bdl(A(X)) <= \dim(A)$.
If $\bdl(A(X)) = \dim(A)$, say $A$ is ``$X$-rich''.
Corollary[of Elekes-Szabo's Szemeredi-Trotter, k=2]:
Suppose $\"char(F_i)=0$, and $P,L,I (= P \times L$ are constructible sets
in $F$.
Suppose $I(X) (= P(X) \times L(X)$ is a quasidesign.
Then
*\[a* \bdl(I(X)) &<=
( \frac 32 - \frac 1{2(2D-1)} ) \max(\bdl(P(X)),\bdl(L(X))) \\\
&< \frac 32 \max(\bdl(P(X)),\bdl(L(X))) .*a\]*
In particular, if $\dim(P)=2=\dim(L)$ and $\dim(I)=3$,
it can not be that $P,L,I$ are all $X$-rich.
.
Hrushovski goes on to define a "probability logic" structure $(F,X)^{\"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:
Theorem[Elekes-Szabo 2012]:
Suppose $R (= 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.
.
Furthermore, Hrushovski conjectures that the underlying explanation for these
Szemeredi-Trotter results is the truth of the Zilber Trichotomy Conjecture in
this context:
Conjecture[Hrushovski]:
If $(X,F)^{\"prob}$ is not (locally) modular, it defines a subfield
$k (= 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.
.