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 (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 points and unit spheres in can yield incidences.
For the requested values of and , consider a set of points and a set of lines, both in and with . We place this plane as the -plane in . We then perform an inverse gnomonic projection that takes and to a sphere in , as follows. We set and denote by the sphere that is centered and is of radius . Notice that is tangent to the -plane at the origin. The inverse projection takes a point in the -plane to the intersection point of the line segment and . One can easily verify that this mapping is a bijection between the -plane and the lower half of ; e.g., see the following figure.
In the above map, every line is mapped to the bottom half of a great circle of . Consider such a half circle and denote by the line that is incident to and orthogonal to the plane that contains . We denote by an arbitrary intersection point of and . That is, if we consider to be the equator of then is one of the poles; e.g., see the following figure.
The important observation here is that the distance between and any point on is (see the following figure depicting half of ). That is, if is the sphere of radius around , then .
Let denote the set of the projections of the points on on , and set . By the above, a point is incident to a sphere if and only if is incident to the point of that yielded . Thus, we have a set of points and a set of unit spheres, such that .
Second construction: A square lattice. Our second construction considers the case of points and unit spheres and yields the slightly improved bound of 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 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 and only added “From deep number theoretic results it follows that for suitable the same distance occurs more than 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 (where and is fixed) is one where . In the following theorem, when writing 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 is
There exist infinitely many values of that satisfy (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 ‘s with representations as (the argument of Granville and Soundararajan remains valid when considering only values of in an arithmetic progression such as ).
Consider an integer lattice in that contains the origin, and a sphere of radius that is centered at the origin. Every point of that is incident to corresponds to a representation of as . Thus, by the above there are infinitely many values of with a sphere that contains points of . We perform a uniform scaling of such that the radius of this sphere decreases to . Finally, we place a sphere of radius around every point of , and denote by the set of these unit spheres. Since each sphere of contains points of , we have , as required.