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 integer grid in . It is easy to prove that any constant-degree algebraic curve passes through points of . This bound is tight, since a line can pass through points of . Somewhat surprisingly, every other constant-degree algebraic curve passes through an asymptotically smaller number of grid points.

**Lemma 1.**

*Let be a integer grid in .*

(a) Let be a constant-degree algebraic curve which is not a line. Then contains points of (recall that little- notation implies asymptotically smaller).

(b) Let be a strictly convex curve (not necessarily algebraic). Then contains points of .

(a) Let be a constant-degree algebraic curve which is not a line. Then contains points of (recall that little- notation implies asymptotically smaller).

(b) Let be a strictly convex curve (not necessarily algebraic). Then contains points of .

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

Some of the translated copies of might contain fewer than points of . To fix this, we also apply each translation of on the points of . Notice that this results in less than distinct grid points.

After inserting the additional points, each of the copies of contains at least points of the grid. That is, we have a planar configuration with curves, points, and 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 , a set of simlpe curves , both in , and two constant positive integers and , such that*

- For every points of there are at most curves of that are incident to each of the points.

- Every two curves of intersect in at most points.

In our case , which implies . That is, , as asserted. For part (a) of the lemma, denote the degree of as , 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 points in common. Applying Theorem 2 for this case, we obtain the bound . This immediately implies , completing the proof of the theorem.

Advertisements

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