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 points and 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 points that could be at unit distance from each other. Let us denote this number as and the maximum number of incidences between points and unit circles as . Let be a set of points that spans unit distances. For every point , we consider a unit circle centered at , and denote the resulting set of circles as . Notice that every pair of points of at a distances of one corresponds to two incidences in . That is, we have ; for example, see the following figure.
In the other direction, consider a set of points and a set of unit circles such that . Let denote the union of with the set of centers of the circles of . Every incidence corresponds to a pair of points of at a distance of one from each other. Each such pair has at most two corresponding point-circle incidences. That is, we have .
The best know upper bound for incidences between points and unit circles, by Spencer, Szemerédi, and Trotter, is . The best known lower bound, by Erdős, is . Similarly to Erdős’ lower bound for point-line incidences (see the first post of this series), this bound is also implied by a integer lattice and relies on results from number theory.
Given a positive integer , we factor it into primes
where , , the primes are distinct and of the form , and the primes are distinct and of the form .
The integer can be written as a sum of two squares if and only if each element of 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 be a positive integer. In the factorization of , if at least one of is odd then is not a sum of two squares. Otherwise, the number of integer solutions to is .
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
We are now ready to describe the point-circle construction. As the point set , we once again take a integer lattice. For any positive integer we set , where is the ‘th prime of the form . We choose to be the maximum integer that satisfies . Theorem 1 implies that any point of has a distance of from exactly points of the integer lattice. Although some of these lattice points might not be in , it is not difficult to verify that at least of the points are in .
To estimate the value of , we rely on the following result of Dirichlet.
Theorem 2. Let and be relatively prime positive integers. Then the number of primes of the form that are smaller than is
(Recall that is Euler’s totient function).
By definition, we have . The first inequality implies and the second implies . By applying Theorem 2 with , , and , we obtain
This implies . By taking the logarithm of both sides we have , which in turn implies
We place a circle with a radius of around every point of , obtaining a set of circles. We then uniformly scale and by a factor of . This scaling maintains the incidences of while changing the radii of the circles of to one.
By the above, each circle of is incident to at least points of . This completes the construction, since it implies
Remark. Notice that we only relied on a special case of Theorem 1, where and each of the ‘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.