paper | murphmath

Introduction

This is the first of a series of three posts outlining the key ideas behind my recent paper “Growth Estimates in Postive Characteristics via Collisions”, which is joint work with Esen Aksoy Yazici, Misha Rudnev, and Ilya Shkredov.

Briefly, this paper proves a number of new sum-product type estimates by expanding on the point/plane incidence approach developed in Misha’s paper “On the number of incidences between points and planes in three dimensions” and Misha and Ilya’s joint work with Olly Roche-Newton “New sum-product type estimates over finite fields”. The heart of our new paper is a bound on the number of “collisions” between images of lines.

The first post in this series describes an incidence bound, which is one of the applications of our sum-product results. The second post will give the relevant background on the sum-product problem, and the third post will describe the “collision” bound and a sum-product corollary, which implies the incidence bound.

(Acknowledgement: I must thank Adam Sheffer for pointing out that I haven’t written about my own work yet!)

Incidence bound

Perhaps the most important result in the paper is a new incidence bound for points and lines in ${\mathbb{F}_q^2}$ .

Theorem 1 Suppose ${P\subseteq{\mathbb F}_q^2}$ is a point set of the form ${P=A\times A}$ with ${|A|\ll p^{2/3}}$ , and ${L}$ is a set of lines in ${{\mathbb F}_q^2}$ . Then

$\displaystyle I(P,L)\ll |P|^{3/4}|L|^{2/3}+|P|+|L|.$

In a sense, this bound is halfway between the Szemeredi-Trotter theorem and the “trivial” Cauchy-Schwarz bound. The Szemeredi-Trotter theorem states that if ${P}$ is a set of point in ${{\mathbb R}^2}$ and ${L}$ is a set of lines in ${{\mathbb R}^2}$ , then

$\displaystyle I(P,L)\ll |P|^{2/3}|L|^{2/3}+|P|+|L|. \ \ \ \ \ (1)$

The proof of this bound relies on the ordering of the reals, and doesn’t apply to finite fields. However, there is a bound that applies over ${{\mathbb F}_q^2}$ based on the Cauchy-Schwarz inequality. This bound states that

$\displaystyle I(P,L)\ll |P|^{3/4}|L|^{3/4}+|P|+|L|. \ \ \ \ \ (2)$

(See this previous post.) In the case where ${|P|\approx |L|=N}$ , the Cauchy-Schwarz bound was improved to

$\displaystyle I(P,L)\ll N^{3/2-\epsilon} \ \ \ \ \ (3)$

by Bourgain, Katz, and Tao using a sum-product estimate, for some small ${\epsilon > 0}$ . Prior to our result, the best value for ${\epsilon}$ was roughly ${1/806}$ (due to Jones). We improve ${\epsilon}$ to ${1/12}$ , but our result only applies in case where ${P}$ is a Cartesian product, while the Cauchy-Schwarz bound and (3) apply to general points sets.

Proof of the incidence bound

The proof of Theorem 1 relies on a bound for the number ${T(A)}$ of collinear triples of a point set ${P=A\times A}$ .

If the points ${(a,a'),(b,b'),(c,c')}$ are collinear, then

$\displaystyle \det\left( \begin{array}{ccc} 1 & 1& 1\\ a & b & c\\ a' & b' & c' \end{array}\right) = 0.$

The number of solutions to this equation for ${a,a',b,b',c,c'}$ in ${A}$ is the number ${T(A)}$ of collinear triples. Later we will prove that

$\displaystyle T(A)\ll |A|^{9/2}.$

For now, let us assume this upper bound, and use it to prove the incidence bound.

Proof: Let ${L_3}$ denote the set of lines in ${L}$ that are incident to at least three points of ${P}$ . Then

$\displaystyle I(P,L)\leq I(P,L_3)+2|L|,$

so it suffices to bound ${I(P,L_3)}$ .

Now let ${P(\ell)=P\cap\ell}$ , so that ${|P(\ell)|}$ is the number of points of ${P}$ contained in the line ${\ell}$ . On one hand,

$\displaystyle I(P,L_3)=\sum_{\ell\in L_3}|P(\ell)|.$

On the other hand,

$\displaystyle 3!\sum_{\ell\in L_3}{|P(\ell)|\choose 3}\leq T(A)\ll |A|^{9/2}. \ \ \ \ \ (4)$

The sum on the left hand side counts the number of collinear triples on lines of ${L_3}$ , and this number is less than the total number of collinear triples ${T(A)}$ .

Since ${{x\choose s}}$ is convex in ${x}$ , the sum on the left side of (4) is minimized by the average of ${|P(\ell)|}$ , which is ${I(P,L_3)/|L_3|}$ :

$\displaystyle 3!\sum_{\ell\in L_3}{|P(\ell)|\choose 3}\geq |L_3|3!{I(P,L_3)/|L_3|\choose 3}\geq |L_3|\left(\frac{I(P,L_3)}{|L_3|}-3\right)^3.$

Combining the lower bound with the upper bound, we have

$\displaystyle \vert L_3\vert\left(\frac{I(P,L_3)}{|L_3|}-3\right)^3\leq T(A)\ll |A|^{9/2} = |P|^{9/4}.$

Now we solve for ${I(P,L_3)}$ :

$\displaystyle I(P,L_3)\ll |P|^{3/4}|L_3|^{2/3}+3|L_3| \leq |P|^{3/4}|L|^{2/3}+3|L|.$

Combined with initial reduction, this bound completes the proof. $\Box$

Note that this proof is similar to the proof of the Cauchy-Schwarz bound (or restricted subgraph bounds in general), but we use the non-trivial bound on ${T(A)}$ instead of general geometric information about points and lines.

Next post: background on the sum-product problem

The upper bound on ${|T(A)|}$ was one of the last things we discovered while working on this paper. We started our investigation by looking for lower bounds for a certain sum-product type set ${|A(A+A)|}$ . The next post will give the relevant background on the sum-product problem, and the final post in the series will describe the main technical innovation of the paper and give a proof of the bound ${|T(A)|\ll |A|^{9/2}}$ .