The limitations of the Elekes-Sharir framework

In a previous series of posts, we discussed the Elekes-Sharir(-Guth-Katz) framework. By using this framework, Guth and Katz derived the bound D(n)=\Omega(n/\log n)  for the Erdős distinct distances problem (where D({\cal P})  denotes the number of distinct distances that are determined by pairs of points from \cal P  , and D(n) = \min_{|{\cal P}|=n}D({\cal P})  ). The best known upper bound is D(n)=O(n/\sqrt{\log n})  , which leaves a gap of \Theta(\sqrt{\log n})  . The common belief is that D(n)=\Theta(n/\sqrt{\log n})  , and thus, that there should exist a way to strengthen the analysis of the lower bound.

In this post we briefly discuss the existence of point sets that determine \Theta(n/\sqrt{\log n})  distinct distances, for which the Elekes-Sharir framework can only yield a bound of \Omega(n/\log n)  . Such configurations imply that to improve the Guth-Katz lower bound while by relying on the Elekes-Sharir framework, one either has to make a drastic change in the framework, or to separately handle the family of “problematic” point configurations. This observation is one of the results in a recent paper by Javier Cilleruelo, Micha Sharir, and myself. Embarrassingly, I did not notice that a similar result was added to the third version of Guth and Katz’s paper. The aforementioned paper still contains other interesting results.

JavierCilSharir2
Javier Cilleruelo and Micha Sharir.

Let us first recall the lower bound construction of Erdős. This construction relies on the following theorem from number theory.

Theorem 1. (Landau-Ramanujan) The number of positive integers smaller than n  that are the sum of two squares is \Theta(n/\sqrt{\log n})  .

intGrid

Consider a square of the integer lattice {\cal P} = \{(i,j) \mid 1\le i,j \le \sqrt{n}\}  , as depicted in the above figure. Every distance between two points of {\cal P}  is of the form \sqrt{a^2+b^2}  , where 0\le a,b \le \sqrt{n}  . Thus, Theorem 1 immediately implies that D({\cal P})=\Theta(n/\sqrt{\log n})  .

Next, we recall that the Elekes-Sharir framework is centered around double-counting the cardinality of the set

Q = \{(a,p,b,q)\in {\cal P}^4 \mid |ap|=|bq|>0 \}.

Deriving the value of |Q|  can be reduced to a problem about finding the number of pairs of intersecting lines in {\mathbb R}^3  in a given set of \Theta(n^2)  lines (e.g., see this post). Guth and Katz relied on this reduction to obtain the bound |Q|=O(n^3\log n)  (which holds for any set \cal P  of n  points in {\mathbb R}^2  , and not just in our case of a \sqrt{n}\times\sqrt{n}  integer lattice).

We denote the set of (nonzero) distinct distances that are determined by {\cal P}\times{\cal P}  as \delta_1,\ldots,\delta_x  . Also, for 1 \le i \le x  , we set

\displaystyle E_i = \left\{(p,q)\in {\cal P}^2 \mid |pq| = \delta_i \right\}. \ \ \ \

Notice that \sum_{i=1}^x|E_i|=n^2-n  since every ordered pair of {\cal P}\times{\cal P}  is contained in a unique set E_i  , except for the n  pairs of the form (p,p)  . By applying the Cauchy-Schwarz inequality, we have

|Q| = \sum_{i=1}^x 2\binom{|E_i|}{2} \ge \sum_{i=1}^x \left(|E_i| - 1\right)^2
\ge \frac{1}{x} \left(\sum_{i=1}^x |E_i| - 1\right)^2 = \frac{(n^2-n-x)^2}{x}. \ \ \ \ (1)

Combining this with Guth and Katz’s upper bound of |Q|=O(n^3\log n)  implies the bound x=\Omega(n/\log n)  which is not tight, even though the reduction to lines in {\mathbb R}^3  preserves the correct value of |Q|  . When considering this, one thought that comes to mind is that perhaps, for the specific configuration \cal P  , the upper bound of Guth and Katz is not asymptotically tight, and there is a smaller number of pairwise intersecting lines. This is not the case, and in fact the gap in the bound is a result of applying of the Cauchy-Schwarz inequality.

To see this, let us consider (1)  again. Since we know that x=\Theta(n/\sqrt{\log n})  , we have \frac{1}{x} \left(\sum_{i=1}^x |E_i| - 1\right)^2 = \frac{(n^2-n-x)^2}{x} = \Theta(n^3\sqrt{\log n})  . However, before applying the Cauchy-Schwarz inequality, we have the expression \sum_{i=1}^x \left(|E_i| - 1\right)^2  , whose value is only \Theta(n^3\sqrt{\log n})  . That is, by applying the Cauchy-Schwarz inequality, we lose a factor of \sqrt{\log n}  . The actual value of |Q|  matches Guth and Katz’s upper bound, implying that their bound is tight in this case. To derive this value of |Q|  we rely on another theorem by Ramanujan.

Theorem 2. (Ramanujan) For a positive integer k  , we set r(k) = \{(i, j) \in {\mathbb N}^2 \mid i^2 + j^2 = k\}  . Then \sum_{i=1}^k r(i)^2 = \Theta(k\log k)  .

A simple use of Theorem 2 implies the bound \sum_{i=1}^x \left(|E_i| - 1\right)^2 = \Theta(n^3\sqrt{\log n})  (see the paper for more details). Therefore, to improve Guth and Katz’s upper bound by relying on the Elekes-Sharir framework, one either has to replace the use of the Cauchy-Schwarz inequality, or to characterize the set of problematic graphs and treat them separately.

Advertisements

Leave a Reply

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

WordPress.com Logo

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