Incidences: Lower Bounds (part 4)

This is the fourth in my series of posts concerning lower bound for incidence problems (see the previous post here).

The previous post discussed point-circle incidences in the plane. An important special case of incidences with circles is incidences with unit circles (i.e., circles of radius one). One might argue that the even more specific case of n  points and n  unit circles is the most ”exciting” incidence problem, since it is asymptotically equivalent to the unit distances problem – one of the main and longest standing open problems in combinatorial geometry see (e.g., see Section 5.1 of the open problems book).

The unit distances problem asks for the maximum number of pairs of points in a set of n points that could be at unit distance from each other. Let us denote this number as u(n)  and the maximum number of incidences between n  points and n  unit circles as u'(n)  . Let {\cal P}  be a set of n  points that spans u(n)  unit distances. For every point p\in {\cal P}  , we consider a unit circle centered at p  , and denote the resulting set of n  circles as {\cal C}  . Notice that every pair of points of {\cal P}  at a distances of one corresponds to two incidences in {\cal P}\times{\cal C}  . That is, we have u(n) \le u'(n)/2  ; for example, see the following figure.


In the other direction, consider a set \cal P  of n  points and a set \cal C  of n  unit circles such that I({\cal P},{\cal C})=u'(n)  . Let {\cal P}'  denote the union of \cal P  with the set of centers of the circles of \cal C  . Every incidence corresponds to a pair of points of {\cal P}'  at a distance of one from each other. Each such pair has at most two corresponding point-circle incidences. That is, we have u'(n) \le 2u(2n)  .

The best know upper bound for incidences between n  points and n  unit circles, by Spencer, Szemerédi, and Trotter, is O(n^{4/3})  . The best known lower bound, by Erdős, is n^{1+\Omega(1/\log \log n)}  . Similarly to Erdős’ lower bound for point-line incidences (see the first post of this series), this bound is also implied by a \sqrt{n}\times\sqrt{n}  integer lattice and relies on results from number theory.

Given a positive integer k  , we factor it into primes

k = 2^{a_0}p_1^{a_1}p_2^{a_2}\cdots p_i^{a_\alpha}q_1^{b_1}q_2^{b_2}\cdots q_j^{b_\beta},

where \alpha=\alpha(k)  , \beta=\beta(k)  , the primes p_1,\ldots,p_\alpha  are distinct and of the form 4s+3  , and the primes q_1,\ldots,q_\beta  are distinct and of the form 4s+1  .

The integer k  can be written as a sum of two squares if and only if each element of \{a_1,\ldots,a_\alpha\}  is even (e.g., see Chapter XV of Beiler’s Recreations in the Theory of Numbers: The Queen of Mathematics Entertains). The first proofs of this statement (specifically, of a simpler variant of it) are attributed to Fermat and to Euler. We require a more general result, due to Jacobi (again, see Chapter XV of Beiler’s Recreations in the Theory of Numbers).

Theorem 1. Let k  be a positive integer. In the factorization of k  , if at least one of a_1,\ldots,a_\alpha  is odd then k  is not a sum of two squares. Otherwise, the number of integer solutions to x^2+y^2=k  is 4(b_1+1)(b_2+1)\cdots (b_\beta+1)  .

The theorem also counts squares of negative numbers and of zero. Moreover, the order of the two squares matters. For example, the theorem states that there are eight representations of 5 as a sum of two squares since

5 = (\pm 1)^2 +(\pm 2)^2 = (\pm 2)^2+ (\pm 1)^2.

We are now ready to describe the point-circle construction. As the point set \cal P  , we once again take a \sqrt{n}\times\sqrt{n}  integer lattice. For any positive integer r  we set d_r = p_1p_2 \cdots p_r  , where p_i  is the i  ‘th prime of the form 4s+1  . We choose r  to be the maximum integer that satisfies d_r < n/2  . Theorem 1 implies that any point of \cal P  has a distance of d_r  from exactly 2^{r+2}  points of the integer lattice. Although some of these 2^{r+2}  lattice points might not be in \cal P  , it is not difficult to verify that at least 2^{r-2}  of the points are in \cal P  .

To estimate the value of r  , we rely on the following result of Dirichlet.

Theorem 2. Let a  and b  be relatively prime positive integers. Then the number of primes of the form a+kb \ (>1)  that are smaller than x  is

\Theta\left(\frac{1}{\phi(b)}\cdot \frac{x}{\log x}\right).

(Recall that \phi(\cdot)  is Euler’s totient function).

By definition, we have p_1p_2\cdots p_r < n/2 \le p_1p_2\cdots p_rp_{r+1}  . The first inequality implies 2^r < n/2  and the second implies p_{r+1} > (n/2)^{1/(r+1)}  . By applying Theorem 2 with a=1  , b=4  , and x=p_{r+1}  , we obtain

r = \Theta\left(\frac{p_{r+1}}{\log p_{r+1}}\right) = \Omega\left(p_{r+1}^{1/2}\right) = \Omega\left(n^{1/(2r+2)}\right).

This implies r^{2r+2} = \Omega(n)  . By taking the logarithm of both sides we have r\log r = \Omega(\log n)  , which in turn implies

r= \Omega\left(\frac{\log n}{\log r}\right) = \Omega\left(\frac{\log n}{\log \log n}\right).

We place a circle with a radius of D_r  around every point of \cal P  , obtaining a set \cal C  of n  circles. We then uniformly scale \cal P  and \cal C  by a factor of 1/D_r  . This scaling maintains the incidences of {\cal P}\times{\cal C}  while changing the radii of the circles of \cal C  to one.

By the above, each circle of \cal C  is incident to at least 2^{r-2} = n^{\Omega(1/\log \log n)}  points of \cal P  . This completes the construction, since it implies

I({\cal P},{\cal C}) = n^{1+\Omega(1/\log \log n)}.

Remark. Notice that we only relied on a special case of Theorem 1, where \alpha(m)=0  and each of the b_i  ‘s is one. A proof of this special case can be found in two of the main discrete geometry books — the one by Pach and Agarwal and the one by Matoušek.


Leave a Reply

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

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