MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a set $E \subset \mathbb{R}^d$, define the distance set of $E$

$$ \Delta(E) = \lbrace|x-y| : x,y \in E \rbrace, $$ where $|\cdot |$ is the usual Euclidean distance.

$\bullet$ The Erdos-distance conjecture roughly asserts that if a set $E \subset \mathbb{R}^d$ has finite cardinality $|E| = n$, then the distance set has size at least $|\Delta(E)| \ge n^{\frac{2}{d}+ \underline{o}(1)}$ $\quad$ (where $\underline{o}(1) \to 0$ as $n \to \infty$).

The case $d = 2$ was recently solved by Guth-Katz using an ingenious adaptation of Dvir's polynomial method along with the so-called algebraic method.

$\bullet$ The Falconer-distance conjecture is a continuous analogue of the Erdos-distance problem. It asserts that if the $E \subset \mathbb{R}^d$ has Hausdorff dimension $\dim_H(E) > \frac{d}{2}$ then the corresponding distance set $\Delta(E)$ has positive Lebesgue measure.

What is the relationship between these two results? It seems that the $\frac{2}{d}$ and the $\frac{d}{2}$ are related, but how, precisely? Is it possible to turn the Guth-Katz result into a result concerning the Falconer-distance problem?

share|cite|improve this question
up vote 11 down vote accepted

Generally speaking, continuous incidence geometry problems are considered strictly harder than their discrete analogues. For instance, if (for simplicity) one replaces Hausdorff dimension with Minkowski dimension (and glosses over the distinction between upper and lower Minkowski dimension), then the Falconer problem is roughly equivalent to the following Erdos-like assertion:

If $E \subset {\bf R}^d$ has bounded diameter and $\delta$-entropy n (i.e. it requires exactly $n$ balls of radius $\delta$ to cover $E$) for some $\delta>0$, then $\Delta(E)$ has $\delta$-entropy $\gg n^{\frac{2}{d}-o(1)}$.

(EDIT: Strictly speaking, the above assertion is in fact false; see this paper of mine with Nets Katz for a simple counter-example. As discussed in that paper, the "correct" way to discretise the Falconer problem is in fact rather delicate.)

Informally, this is a relaxation of the Erdos problem in which one now considers two numbers to be equivalent if they differ by $O(\delta)$. This makes it significantly harder to apply algebraic methods (which do not react well to this sort of "fuzzy" arithmetic, especially when dividing by small non-zero denominators), although there have been some partial successes in extending the algebraic method to this setting, such as Guth's proof of the endpoint multilinear Kakeya conjecture.

The last part of this (now somewhat dated) survey of Wolff gives a detailed comparison of the Szemeredi-Trotter theorem and a variant of the Kakeya problem relating to sets of Furstenberg type, which is quite analogous to the relationship between the Erdos and Falconer conjectures.

share|cite|improve this answer
Thank you for your detailed response. It will take some time for me to fully digest the answer, but this is exactly what I was looking for. – David Oct 18 '11 at 6:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.