Incidences and Planar Curves Containing Many Grid Points

Alex Iosevich just visited us here at Tel Aviv University. Alex gave a wonderful talk about “Distribution of simplexes in discrete and continuous settings”, though his talk is not the topic of this post.


Alex showed me a cute proof concerning how many points of a planar integer grid can be contained in an irreducible curve. (If I am not mistaken, Nets Katz showed me a variant of the same proof a while ago.) With Alex’s permission, I now present my own variant of this proof.

Consider a \sqrt{n}\times\sqrt{n}  integer grid {\cal G}  in {\mathbb R}^2  . It is easy to prove that any constant-degree algebraic curve passes through O(\sqrt{n})  points of {\cal G}  . This bound is tight, since a line can pass through \Theta(\sqrt{n})  points of {\cal G}  . Somewhat surprisingly, every other constant-degree algebraic curve passes through an asymptotically smaller number of grid points.

Lemma 1. Let {\cal G}  be a \sqrt{n}\times\sqrt{n}  integer grid in {\mathbb R}^2  .
(a) Let C  be a constant-degree algebraic curve which is not a line. Then C  contains o(\sqrt{n})  points of {\cal G}  (recall that little-o()  notation implies asymptotically smaller).
(b) Let C  be a strictly convex curve (not necessarily algebraic). Then C  contains O(n^{1/3})  points of {\cal G}  .


Proof.     The beginning of the proof is identical for both parts of the lemma. Let x  denote the number of points of \cal G  that are incident to C  , let p  be a point of \cal G  that is incidence to C  , and let \cal T  denote the set of translations of the plane that take p  to another point of \cal G  . We apply each of the translations of {\cal T}  on C  to obtain n  copies of C  . The following figure is obtained by choosing p  to be the second leftmost point of the bottom row in the above figure.


Some of the translated copies of C  might contain fewer than x  points of \cal G  . To fix this, we also apply each translation of {\cal T}  on the points of \cal G  . Notice that this results in less than 4n  distinct grid points.


After inserting the additional points, each of the n  copies of C  contains at least x  points of the grid. That is, we have a planar configuration with n  curves, O(n)  points, and \Omega(nx)  incidences. We now consider part (b) of the lemma, and notice that two translated copies a a convex curve can intersect in at most two points. Therefore, we can apply the Pach-Sharir incidence bound.

Theorem 2. Consider a point set \cal P  , a set of simlpe curves \Gamma  , both in {\mathbb R}^2  , and two constant positive integers k  and s  , such that
  • For every k  points of \cal P  there are at most s  curves of \Gamma  that are incident to each of the k  points.
  • Every two curves of \Gamma  intersect in at most s  points.
Then I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|),  where the constant of proportionality depends on k  and s  .

In our case k=2  , which implies \Omega(xn) = O(n^{4/3})  . That is, x=O(n^{1/3})  , as asserted. For part (a) of the lemma, denote the degree of C  as D  , and notice that two translated copies of an irreducible curve cannot share a common component. By Bézout’s theorem, any two such curves have at most D^2  points in common. Applying Theorem 2 for this case, we obtain the bound \Omega(xn) = O(n^{(3D-2)/(2D-1)}|) = o(n^{3/2})  . This immediately implies x=o(n^{1/2})  , completing the proof of the theorem.     \Box


One thought on “Incidences and Planar Curves Containing Many Grid Points

  1. Pingback: Incidences and the Sum-Product Problem | Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s