Incidences: Lower Bounds (part 6)

Last year I surveyed the known lower bounds for incidence problems in the plane (click here for the previous post in the series). I now return to this series of posts to survey the lower bounds that are known in higher dimensions.

From what is already known about incidences with curves in {\mathbb R}^d  , it seems likely that the maximum number of incidences is usually obtained when the points and curves lie in a constant-degree two-dimensional surface. For example, Guth and Katz proved that the maximum number of point-line incidences in {\mathbb R}^3  is obtained when the points and lines are in a common plane. While incidences with general curves are not fully understood even in the plane, various recent results hint that this is also the case for general curves in {\mathbb R}^d  (for example, see here and here).

Due to the above, incidences with curves in {\mathbb R}^d  are usually studied with a restriction on the number of curves that can be contained in various types of constant-degree surfaces; another reason for studying such restrictions is that they arise from interesting problems. For example, Guth and Katz proved the following theorem.

Theorem 1. Let \cal P  be a set of m  points and let \cal L  be a set of n lines, both in {\mathbb R}^3  , such that every plane contains O(\sqrt{n})  lines of \cal L  . Then

I({\cal P},{\cal L}) = O\left(m^{1/2}n^{3/4}+n+m\right).

Currently, all of the known lower bounds for incidences with curves in {\mathbb R}^d  are simple extensions of the planar bounds that we studied in the previous posts. In the current post we only present one such bound. Specifically, we extend Elekes’ planar construction to show that Theorem 1 is tight. The following posts will focus on the more challenging issues that arise for incidences with higher-dimensional objects.

Claim 1. Consider integers m  and n  that satisfy m \ge 4\sqrt{n}  and m\le n^{3/2}  . Then there exist a set \cal P  of m  points and a set \cal L  of n  lines, both in {\mathbb R}^3  , such that every plane contains O(\sqrt{n})  lines of \cal L  and

I({\cal P},{\cal L})= \Theta\left(m^{1/2}n^{3/4} \right).

Proof.     Set k = m^{1/2}/(2n^{1/4})  and \ell = \sqrt{2}n^{3/8}/m^{1/4}  , and let

{\cal P} = \left\{(r,s,t)\in {\mathbb N}^3 : 1\le r \le k \ \text{ and } \ 1\le s,t \le 2k\ell \right\}.

For our set of lines, we take

{\cal L} = \left\{y-ax-b,z-cx-d : 1 \le a,c \le \ell \ \text{ and } \ 1\le b,d \le k\ell \right\}.

First, notice that we indeed have

|{\cal P}| = k (2k\ell)^2 = 4k^3 \ell^2 = 4 \cdot \frac{m^{3/2}}{8n^{3/4}} \cdot \frac{2n^{3/4}}{m^{1/2}} = m,
|{\cal L}| = k^2\ell^4 = \frac{m}{4n^{1/2}} \cdot \frac{4n^{3/2}}{m} = n.

For any line \gamma \in {\cal L}  and 1\le r \le k  , there exists a unique point in \cal P  that is incident to \gamma  and whose x  -coordinate is r  . That is, every line of \cal L  is incident to exactly k  points of \cal P  . Thus, we have

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

It remains to verify that every plane contains O(\sqrt{n})  lines of \cal L  . We first consider a plane h  that is defined by an equation of the form y=sx+t  (that is, a plane that contains lines that are parallel to the z  -axis). Such a plane h  contains exactly the lines that have a=s  and b=t  in their definition in \cal L  . There are k\ell^2= \Theta(\sqrt{n})  such lines.

Next, consider a plane h  that is not defined by an equation of the form y=sx+t  . In this case, for every choice of a,b  , the plane h' =Z(y-ax-b)  intersects h  in a unique line. That is, for every choice of a,b  as in the definition of \cal L  , there is at most one line of \cal L  with these parameters that is contained in h  . Thus, h  contains k\ell^2= \Theta(\sqrt{n})  lines of \cal L  .

Advertisements

One thought on “Incidences: Lower Bounds (part 6)

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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