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

.

Continue reading →