You are currently browsing the tag archive for the ‘finite fields’ tag.
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!)
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 is a set of point in and is a set of lines in , then
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 based on the Cauchy-Schwarz inequality. This bound states that
(See this previous post.) In the case where , the Cauchy-Schwarz bound was improved to
by Bourgain, Katz, and Tao using a sum-product estimate, for some small . Prior to our result, the best value for was roughly (due to Jones). We improve to , but our result only applies in case where 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 of collinear triples of a point set .
If the points are collinear, then
The number of solutions to this equation for in is the number of collinear triples. Later we will prove that
For now, let us assume this upper bound, and use it to prove the incidence bound.
Proof: Let denote the set of lines in that are incident to at least three points of . Then
so it suffices to bound .
Now let , so that is the number of points of contained in the line . On one hand,
Since is convex in , the sum on the left side of (4) is minimized by the average of , which is :
Combining the lower bound with the upper bound, we have
Now we solve for :
Combined with initial reduction, this bound completes the proof.
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 instead of general geometric information about points and lines.
Next post: background on the sum-product problem
The upper bound on 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 . 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 .