Incidences: Lower Bounds (part 7)

In this post we continue our survey of the known lower bounds for incidence problems (click here for the previous post in the series). In the current post we finally start discussing incidences with objects of dimension larger than one. The simplest such case seems to be incidences with unit spheres in {\mathbb R}^3  (i.e., spheres of radius one). We present two rather different constructions for this case. I am not aware of any paper that describes either of these constructions, and they appear to be folklore. If you are aware of a relevant reference, I will be happy to hear about it.

First construction: Inverse gnomonic projection. Our first construction is based on lower bounds for the Szemerédi-Trotter problem (e.g., see the first two posts of this series). It shows that m  points and n  unit spheres in {\mathbb R}^3  can yield \Omega(m^{2/3}n^{2/3}+m+n)  incidences.

For the requested values of m  and n  , consider a set \cal P  of m  points and a set \cal L  of n  lines, both in {\mathbb R}^2  and with I({\cal P},{\cal L})=\Theta(m^{2/3}n^{2/3}+m+n)  . We place this plane as the xy  -plane in {\mathbb R}^3  . We then perform an inverse gnomonic projection that takes \cal P  and \cal L  to a sphere in {\mathbb R}^3  , as follows. We set p=(0,0,1/\sqrt{2})  and denote by S  the sphere that is centered p  and is of radius 1/\sqrt{2}  . Notice that S  is tangent to the xy  -plane at the origin. The inverse projection takes a point q  in the xy  -plane to the intersection point of the line segment pq  and S  . One can easily verify that this mapping is a bijection between the xy  -plane and the lower half of S  ; e.g., see the following figure.

Gnomonic

In the above map, every line \ell\in {\cal L}  is mapped to the bottom half of a great circle c_\ell  of S  . Consider such a half circle c_\ell  and denote by r_\ell  the line that is incident to p  and orthogonal to the plane that contains c_\ell  . We denote by p_\ell  an arbitrary intersection point of r_\ell  and S  . That is, if we consider c_\ell  to be the equator of S  then p_\ell  is one of the poles; e.g., see the following figure.

GnomonicPole

The important observation here is that the distance between p_\ell  and any point on c_\ell  is 1  (see the following figure depicting half of c_\ell  ). That is, if S_\ell  is the sphere of radius 1  around p_\ell  , then c_\ell \subset S_\ell  .

QuarterCircle

Let {\cal P}'  denote the set of the projections of the points on \cal P  on S  , and set {\cal S} = \{S_\ell :\, \ell\in {\cal L}\}  . By the above, a point p'\in {\cal P}'  is incident to a sphere S_\ell  if and only if \ell  is incident to the point of \cal P  that yielded p'  . Thus, we have a set {\cal P}'  of m  points and a set \cal S  of n  unit spheres, such that I({\cal P}',{\cal S})=I({\cal P},{\cal L})=\Theta(m^{2/3}n^{2/3}+m+n)  .

Second construction: A square lattice. Our second construction considers the case of n  points and n  unit spheres and yields the slightly improved bound of \Theta(n^{4/3}\log\log n)  incidences. The case where the number of points is equivalent to the number of spheres is arguably the most interesting one, since it is equivalent to the {\mathbb R}^3  variant of the unit distances problem. The following construction was mentioned briefly and without any details by Erdős. Erdős derived the straightforward bound \Theta(n^{4/3})  and only added “From deep number theoretic results it follows that for suitable r  the same distance occurs more than c n^{4/3} \log\log n  times.” We now hopefully recreate the argument that Erdős had in mind (with the help of “Lucia” and “GH from MO” from Mathoverflow).

A primitive solution to the equation x^2+y^2+z^2=n  (where x,y,z,n\in {\cal\mathbb Z}  and n  is fixed) is one where \gcd(x,y,z)=1  . In the following theorem, when writing \left(\frac{a}{b}\right)  we refer to the Kronecker symbol rather than to division. For a proof of this theorem, see for example Theorem 4 of Chapter 4 in Grosswald’s “Representations of integers as sums of squares”.

Theorem 1.The number of primitive solutions to x^2 + y^2 + z^2 = n  is

\frac{A}{\pi}\sqrt{n}\sum_{m=1}^\infty \left(\frac{-4n}{m} \right)m^{-1},

\text{ where } A = \left\{    \begin{array}{ll}     0 & \text{ if } n \equiv 0,4,7 \mod 8, \\     16 & \text{ if } n \equiv 3 \mod 8, \\     24 & \text{ if } n \equiv 1,2,5,6 \mod 8.    \end{array}  \right.

There exist infinitely many values of n  that satisfy \sum_{m=1}^\infty \left(\frac{-4n}{m} \right)m^{-1} = \Omega(\log \log n)  (e.g., see Theorem 5b of Granville and Soundararajan). Littlewood showed that under the generalized Riemann hypothesis this bound is tight. Combining this with Theorem 1 implies that there are infinitely many n  ‘s with \Omega(\sqrt{n}\log\log n)  representations as x^2 + y^2 + z^2  (the argument of Granville and Soundararajan remains valid when considering only values of n  in an arithmetic progression such as n \equiv 3 \mod 8  ).

Consider an n^{1/3}\times n^{1/3}\times n^{1/3}  integer lattice \cal P  in {\mathbb R}^3  that contains the origin, and a sphere S  of radius d  that is centered at the origin. Every point of \cal P  that is incident to S  corresponds to a representation of d^2  as x^2 + y^2 + z^2  . Thus, by the above there are infinitely many values of n  with a sphere that contains \Omega(n^{1/3}\log \log n)  points of \cal P  . We perform a uniform scaling of {\mathbb R}^3  such that the radius of this sphere decreases to 1  . Finally, we place a sphere of radius 1  around every point of \cal P  , and denote by \cal S  the set of these n  unit spheres. Since each sphere of \cal S  contains \Omega(n^{1/3}\log \log n)  points of \cal P  , we have I({\cal P}, {\cal S})=\Omega(n^{4/3}\log \log n)  , as required.

Advertisements

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

  1. Pingback: Incidences: Lower Bounds (part 8) | 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