by

Incidences: Lower Bounds (part 2)

This is the second in my series of posts concerning lower bound for incidence problems (see the first post here). This post describes Elekes’ point-line construction, which is quite different from Erdős’ construction, although it yields asymptotically the same number of incidences. While preparing this post, I was quite surprised to discover that this construction yields constants better than those that are stated as the best known ones (e.g., in the research problems book).

Update 1 (11/26/2014): Frank the Zeeuw pointed out that this bound was already noticed in Section 1.1 of Roel Apfelbaum’s Ph.D. dissertation.

Update 2 (01/01/2018): It was pointed in this paper by Balko, Cibulka, and Valtr that the analysis of Pach and Tóth leads to the much better constant 1.27. This stronger bound is not stated in that paper due to a miscalculation.

elekes
György Elekes.

Elekes’ construction is simpler and more elementary, in the sense that it only requires basic counting techniques (unlike Erdős’ construction which also relies on some number theory). As we shall see in the following posts, it is also easier to generalize to other types of planar curves. Moreover, unless I have some mistake, it seems to lead to better constants. Specifically, given m points and n lines in the plane, the maximum number of incidences, as shown by Pach and Tóth, is at least 0.42m^{2/3}n^{2/3}+m+n . In various places (such as the aforementioned open problems book) this is stated as the best known lower bound. The best known upper bound, obtained by combining a technique from the same paper of Pach and Tóth with a recent improvement by Ackerman, is about 2.44m^{2/3}n^{2/3}+m+n . Elekes’ construction leads to the improved lower bound 0.63m^{2/3}n^{2/3}+m+n .

In both constructions the point set is a subset of the integer lattice. However, Erdős’ construction is based on a square lattice (i.e., of size \sqrt{m}\times\sqrt{m} ), while Elekes’ contruction is a rather uneven lattice (except for the extreme case when m=\Theta(n^2) ).

To simply the explanation, we set r=(m^2/4n)^{1/3} and s=(2n^2/m)^{1/3} . We define the point set to be

{\cal P} = \left\{\ (i,j)\ | \ 1 \le i \le r \quad \text{ and } \quad 1 \le j \le 2rs \ \right\}.

We define the line set to be

{\cal L} = \left\{\ y=ax+b \ | \ 1 \le a \le s \quad \text{ and } \quad 1 \le b \le rs \ \right\}.

Notice that we indeed have

|{\cal P}|=2r^2s = 2\cdot \frac{m^{4/3}}{(4n)^{2/3}}\cdot \frac{(2n^2)^{1/3}}{m^{1/3}} = m,

and similarly

|{\cal L}| = rs^2 = \frac{m^{2/3}}{(4n)^{1/3}} \cdot \frac{(2n^2)^{2/3}}{m^{2/3}} = n.

Consider a line \ell\in {\cal L} that is defined by the equation y=ax+b , for some constants a,b . Notice that for any value of x in \{1,\ldots,r\} there exists a corresponding value of y in the range \{1,\ldots, 2rs\} , such that the point (x,y) is incident to \ell . That is, every line of \cal L is incident to exactly r points of \cal P , and thus

I({\cal P},{\cal L}) = r \cdot |{\cal L}| = \frac{m^{2/3}}{(4n)^{1/3}} \cdot n = 2^{-2/3}m^{2/3}n^{2/3}.

And that is the end of the construction! In the next post of the series, I plan to start surveying planar configurations of other types of curves.

10 thoughts on “Incidences: Lower Bounds (part 2)”

  1. Pingback: Incidences: Lower Bounds (part 3) | Some Plane Truths

  4. Pingback: Incidences: Lower Bounds (part 6) | Some Plane Truths

    • Right! I read your paper and saw this footnote before. Your new incidence bound for flats is very nice, and I should also have a post in the lower bounds series about it. I’ve been neglecting this series for a while…

      I just updated this post accordingly. Thank you for pointing this out.

      Reply

  7. Pingback: Configurations with many incidences and no triangles – Cosmin Pohoata

  8. Pingback: Incidences: Open Problems (part 2) – Some Plane Truths

Leave a reply to Adam Sheffer Cancel reply