Combinatorial incidence geometry is the study of the possible combinatorial configurations between geometric objects such as lines and circles. One of the basic open problems in the subject has been the Erdős distance problem, posed in 1946:
Problem 1 (Erdős distance problem) Let 
be a large natural number. What is the least number 
of distances that are determined by points 
in the plane?
Erdős called this least number 
. For instance, one can check that 
and 
, although the precise computation of 
rapidly becomes more difficult after this. By considering points in arithmetic progression, we see that 
. By considering the slightly more sophisticated example of a 
lattice grid (assuming that is a square number for simplicity), and using some analytic number theory, one can obtain the slightly better asymptotic bound 
.
On the other hand, lower bounds are more difficult to obtain. As observed by Erdős, an easy argument, ultimately based on the incidence geometry fact that any two circles intersect in at most two points, gives the lower bound 
. The exponent 
has been slowly increasing over the years by a series of increasingly intricate arguments combining incidence geometry facts with other known results in combinatorial incidence geometry (most notably the Szemerédi-Trotter theorem) and also some tools from additive combinatorics; however, these methods seemed to fall quite short of getting to the optimal exponent of 
. (Indeed, previously to last week, the best lower bound known was approximately 
, due to Katz and Tardos.)
Very recently, though, Guth and Katz have obtained a near-optimal result:
Theorem 2 One has 
.
The proof neatly combines together several powerful and modern tools in a new way: a recent geometric reformulation of the problem due to Elekes and Sharir; the polynomial method as used recently by Dvir, Guth, and Guth-Katz on related incidence geometry problems (and discussed previously on this blog); and the somewhat older method of cell decomposition (also discussed on this blog). A key new insight is that the polynomial method (and more specifically, the polynomial Ham Sandwich theorem, also discussed previously on this blog) can be used to efficiently create cells.
In this post, I thought I would sketch some of the key ideas used in the proof, though I will not give the full argument here (the paper itself is largely self-contained, well motivated, and of only moderate length). In particular I will not go through all the various cases of configuration types that one has to deal with in the full argument, but only some illustrative special cases.
To simplify the exposition, I will repeatedly rely on “pigeonholing cheats”. A typical such cheat: if I have 
objects (e.g. points or lines), each of which could be of one of two types, I will assume that either all of the objects are of the first type, or all of the objects are of the second type. (In truth, I can only assume that at least 
of the objects are of the first type, or at least of the objects are of the second type; but in practice, having instead of only ends up costing an unimportant multiplicative constant in the type of estimates used here.) A related such cheat: if one has objects 
(again, think of points or circles), and to each object 
one can associate some natural number 
(e.g. some sort of “multiplicity” for ) that is of “polynomial size” (of size 
), then I will assume in fact that all the are in a fixed dyadic range ![{[k,2k]}](https://s0.wp.com/latex.php?latex=%7B%5Bk%2C2k%5D%7D&bg=ffffff&fg=000000&s=0 "{[k,2k]}")
for some 
. (In practice, the dyadic pigeonhole principle can only achieve this after throwing away all but about 
of the original objects; it is this type of logarithmic loss that eventually leads to the logarithmic factor in the main theorem.) Using the notation 
to denote the assertion that 
for an absolute constant 
, we thus have 
for all 
, thus is morally constant.
I will also use asymptotic notation rather loosely, to avoid cluttering the exposition with a certain amount of routine but tedious bookkeeping of constants. In particular, I will use the informal notation 
or 
to denote the statement that 
is “much less than” 
or is “much larger than” , by some large constant factor.
See also Janos Pach’s recent reaction to the Guth-Katz paper on Kalai’s blog.
Read the rest of this entry »
Recent Comments