You are currently browsing the tag archive for the ‘cell decomposition decomposition’ tag.
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:
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
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.
Recent Comments