My question concerns the Szemerédi-Trotter theorem in $\mathbb{F}_q^2$. If we have $m$ points and $n$ lines in $\mathbb{F}_q^2$, then by Cauchy-Schwarz the number of point-line incidences is as most $$\min(mn^{1/2}+n,\ m^{1/2}n+m). \qquad\qquad (1)$$ This is the brown line in the figure below.

We also know that if $m=n$, and $q^{\delta}<m<q^{2-\delta},$ then the number of incidences is at most $$ m^{3/2-\epsilon}\qquad\qquad\qquad (2) $$ for some $\epsilon=\epsilon(\delta)>0$. This is the red dot in the figure below.

Equation $(2)$ allows us to beat the bound $(1)$ provided $m$ is very close to $n$---just increase either $m$ or $n$ slightly so that $m=n$, and then apply $(2)$. This is the red line in the figure below.

My question is: are there any results that allow us to do better than the envelope of the brown and red lines---i.e. can we obtain any sort of bound that looks like the blue line below? My hope is that we can somehow interpolate between the red dot (in the figure below) and the two endpoint cases (the brown dots at $(1/2, 1/2)$ and at $(2,2)$.

Does anyone know of a result of this form, or does anyone have ideas on how to obtain such a result?

Known and conjectured bounds for finite field Szemerédi-Trotter in finite fields

[edit: updated the picture to have correct numerology, and corrected (1)]


3 Answers 3


I believe one can deduce an improvement of the form $$I(P,L) \leq |P| |L|^{1/2-\epsilon}$$ from the symmetric case $|P|=|L|$ by using the following argument of Pudlak (see Corollary 2.5, there): Assume that $|P| > |L|$ and select a random subset $P'$ of $P$ of size $L$. The expected number of incidences will be $I(P,L) \frac{|L|}{|P|}$. Let $P'$ denote a set of points at or above the expectation. Now applying the symmetric result to the symmetric incidence problem with $P'$ and $L$, should give $$I(P,L) \frac{|L|}{|P|} \leq I(P',L) \leq |L|^{3/2-\epsilon'}. $$

In the case of large sets, there is also a result of Le Anh Vinh, which states that:

$$I(P,L) \leq q^{-1} |P| |L| + q^{1/2} |P|^{1/2} |L|^{1/2}. $$

Here, $q$ is the order of the finite field. Note, however, that this is worse than trivial when $|P|\times|L|$ is smaller than $q$.

  • $\begingroup$ Hmm, this trick (together with projective duality to interchange the roles of P and L) widens the slope of the red lines in Josh's diagram a bit (they become parallel to the brown lines), but still doesn't improve upon the trivial bounds once P and L are sufficiently far apart. $\endgroup$
    – Terry Tao
    Feb 18, 2014 at 23:58
  • $\begingroup$ Hi Mark and Terry. First, thanks for the references! If I understand correctly, the trick Mark mentioned allows us to add a line from the point $(1-2\epsilon, 3/2-2\epsilon)$ to the point $(1, 3/2-\epsilon)$. This line has slope $1/2$. (The dual of this line is already present; it is the line from $(1,3/2-\epsilon)$ to $(1+2\epsilon, 3/2+\epsilon)$, which has slope 1. I would be especially happy if there were results that gave us lines passing through $(1,3/2-\epsilon)$ that had slopes better than $1/2$ or $1$ (in the respective directions). It sounds like Terry is not optimistic about this :( $\endgroup$
    – Josh Zahl
    Feb 19, 2014 at 17:34

Currently, the only way to get non-trivial Szemeredi-Trotter bounds for medium-sized sets of points and lines in finite fields is to first reduce to a sum-product type problem, then prove a non-trivial sum-product estimate. The latter has a good chance of extending to asymmetric settings, but the former is still problematic there, basically because one is now only quasi-extremal to one trivial bound rather than to two, which allows for substantially more variability and non-rigidity in any putative counterexample to improvements over the trivial bounds. (For instance, in the Helfgott-Rudnev explicit version of this inequality at http://arxiv.org/abs/1001.1980 , they focus exclusively on the latter (in the symmetric setting) but don't improve the former beyond what Nets, Jean, and I did in http://arxiv.org/abs/math/0301343.

For very small sets (of logarithmic size or so), one can embed the configuration into the complex plane, at which point the complex Szemeredi-Trotter theorem becomes available; see this paper of Grosu, http://arxiv.org/abs/1303.2363 , for details. Unfortunately it is not clear how to push this method to larger sets.

Given that the Szemeredi-Trotter theorem over the reals (and complexes) can be proven by the polynomial method (see e.g. my survey on that method at http://arxiv.org/abs/1310.6482), and that the polynomial method has had other notable successes in finite fields, it is very natural to suspect that the polynomial method should be usable to deduce non-trivial Szemeredi-Trotter or sum-product theorems in finite fields. It is thus a bit frustrating that no such proof is currently known (the key obstacle being the lack of a substitute for the ham sandwich theorem for the finite field setting).


In case anyone stumbles across this thread, there is now a nice paper by Sophie Stevens (https://arxiv.org/abs/1609.06284) which improves upon the Cauchy-Schwarz bound for all ranges of $m$ and $n$ with $m^{1/2} \leq n \leq m^2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.