# 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$