# 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.

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.

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$.

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.