Excuses

You might have noticed that recently my posting frequency has gone down. I am full of excuses: I just got married, started a new job, and moved to the US. Now I’m dealing with mountains of bureaucracy (don’t even have an SSN yet!). I am planning to have several interesting posts once I have a bit of time, so stay tuned!

monty_hall
Taken from xkcd.

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.

UnitToUnit

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

Continue reading