Finite point configurations in Euclidean space I: an overview

In the past few years, my co-authors and I have been trying to answer the following basic question: How large does the Hausdorff dimension of a subset of ${\Bbb R}^d$ need to be to ensure that it contains “most” finite point configurations of a given type?

A classical example of this question is the Falconer distance problem. It asks how large the Hausdorff dimension of $E \subset {\Bbb R}^d$ , $d \ge 2$ need to be to ensure that the Lebesgue measure of the distance set $\Delta(E)=\{|x-y|: x,y \in E \}$ is positive. The conjectured dimensional threshold is $\frac{d}{2}$ . The best known threshold, due to Wolff in two dimensions and to Erdogan in higher dimensions is $\frac{d}{2}+\frac{1}{3}$ .

As we mention in several of the previous posts, the discrete analog of this problem is the Erdos distance problem which asks for the number of distances determined by a finite point set $E$ in ${\Bbb R}^d$ , $d \ge 2$ consisting of $n$ points. The conjecture is $\# \Delta(E) \gtrsim n^{\frac{2}{d}}$ , up to a logarithmic factor in two dimensions. The two dimensional conjecture was recently proved in a brilliant paper by Larry Guth and Nets Katz. In higher dimensions, the best known result, due to Solymosi and Vu is, roughly, $\# \Delta(E) \gtrsim n^{\frac{2}{d}-\frac{1}{d^2}}$ .

The possibility of a direct connection between the Erdos and Falconer problems is a fascinating subject that I have commented on in previous posts. It will come up again later in this post and its sequels as the question is still in many ways unresolved.

The distance set problem, whether discrete or continuous, can be viewed as the question about two point configurations. After all, a two point configuration $x,y$ is congruent to a two point configuration $x',y'$ if and only if $|x-y|=|x'-y'|$ , where $|\cdot|$ denotes the standard Euclidean distance. This begs the question of what happens with finite point configurations involving more points. In the discrete context, this questions has been explored in a series of papers by Erdos and Purdy and is exposed very nicely in a book, entitled “Research Problems in Discrete Geometry”, by Brass, Moser and Pach.

Let us fix some definitions. We say that two $k$ -simplexes $x^1,x^2, \dots, x^{k+1}$ and $y^1, y^2, \dots, y^{k+1}$ are congruent if there exists $\tau \in {\Bbb R}^d$ and $O \in O_d({\Bbb R})$ such that $y^j=Ox^j+\tau$ . The reason for the convention where a $k$ -simplex contains $k+1$ points is that a two point configuration, for example, is a triangle, which is a two-dimensional object.

In discrete geometry, one of the basic questions about finite point configurations is the following. Let $u_{k,d}(n)$ denote the maximum number of congruent copies of a given $k$ point configuration among $n$ points in ${\Bbb R}^d$ . When $k=1$ and $d=2$ , this is the classical Erdos single distance problem, which asks how many times a given distance may arise among $n$ points in ${\Bbb R}^2$ . Erdos conjectured that $u_{1,2}(n) \leq n \log(n)$ . The best result to date, which follows from a variant of the Szemeredi-Trotter incidence theorem, is $u_{1,2}(n) \leq Cn^{\frac{4}{3}}$ . No progress on this problem, in either the positive or negative direction, has been achieved, to the best of my knowledge, since the early 80s.

The problem of estimating $u_{2,2}(n)$ is quite frustrating. For a given triangle to repeat, each side-lengths has to repeat, so, in particular, $u_{2,2}(n) \leq u_{1,2}(n)$ , which we know to be bounded by $Cn^{\frac{4}{3}}$ . If the Erdos single distance conjecture is true, then $u_{2,2}(n) \leq Cn \log(n)$ , which would be essentially best possible. However, if the Erdos single distance conjecture is not true, there is a possibility that $u_{2,2}(n)$ is much smaller than $u_{1,2}(n)$ . Since for a triangle to repeat, all three sides need to repeat, one might think that it should not bee to hard to improve the $u_{2,2}(n) \leq Cn^{\frac{4}{3}}$ estimate. Unfortunately, there has been no progress on this question for general point sets to the best of my knowledge. For point sets satisfying some additional structural assumptions, such as homogeneous point sets studied by Laba, Solymosi, Vu and others. there has been some progress via analytic estimates, and this is where our narrative now takes us.

In one of the previous posts, I described my recent result with Allan Greenleaf, entitled “On three point configurations determined by subsets of the Euclidean plane, the associated bilinear operator and applications to discrete geometry” (http://arxiv.org/pdf/1009.2471.pdf), where we prove that if $\mu$ is a Frostman measure on a compact set $E \subset {\Bbb R}^2$ of Hausdorff dimension $>\frac{7}{4}$ , then

$\mu \times \mu \times \mu \{(x^1,x^2,x^3): t_{ij} \leq |x^i-x^j| \leq t_{ij}+\epsilon \} \leq C \epsilon^3$ for any non-zero $\{t_{ij}\}$ satisfying the triangle inequality. From this one can easily deduce that if the Hausdorff dimension of $E \subset {\Bbb R}^2$ is greater than $\frac{7}{4}$ , then the three dimensional Lebesgue measure of $T_2(E)$ , the set of non-congruent triangles determined by $E$ is positive.

Using a variant of a conversion mechanism I developed with S. Hofmann and I. Laba a few years ago, one can use this result to improve the upper bound for $u_{2,2}(n)$ restricted to finite subsets of the plane satisfying certain additional structural assumptions. The result applies to homogeneous sets, but the range of usefulness is actually much wider. Here is the basic idea, introduced by Iosevich, Rudnev and Uriarte-Tuero in “Theory of dimension for large discrete sets and applications” (http://arxiv.org/pdf/0707.1322.pdf). Let $E$ be a set of $n$ points in the unit square in the plane. Thicken each point by $n^{-\frac{1}{s}}$ , $1<s<2$ , and let $\mu_n$ denote the obvious probability measure on the resulting union of disks. Assume that the disks are disjoint. We say that $E$ is $s$ -adaptable, if

$\int \int {|x-y|}^{-s} d\mu_n(x) d\mu_n(y) \approx 1$ , which is the quantitative way of capturing the idea that the Hausdorff dimension of the set of disks above is $s$ uniformly in $n$ .

If we consider $s$ -adaptable sets with $s \ge \frac{7}{4}$ , we can improve that bound for $u_{2,2}(n)$ in this context to

$u_{2,2}(n) \leq Cn^{\frac{9}{7}}$ .

In the cases when $k>2$ , almost nothing is known in the discrete context about $u_{k,d}(n)$ . This is one of the motivations for my paper in preparation with Loukas Grafakos, Allan Greenleaf and Eyvindur Palsson on multi-linear generalized Radon transforms and applications to geometric measure theory/combinatorics. In this paper, to be described in the next installment of this post, we prove certain multi-linear inequalities and use them to prove inequalities of the type

$\mu \times \mu \times \dots \times \mu \{(x^1, \dots, x^{k+1}): t_{ij} \leq |x^i-x^j| \leq t_{ij}+\epsilon \} \leq C\epsilon^{k+1 \choose 2}$ , where $\mu$ is a Frostman measure on a subset of ${\Bbb R}^d$ of a Hausdorff dimension exceeding

$d-\frac{d-1}{2d}=d-\frac{1}{2}+\frac{1}{2d}$ .

We then use this inequality to contain non-trivial upper bounds for $u_{d,d}(n)$ in the context of $s$ -adaptable point sets. This and much more is subject of “Finite point configurations in Euclidean space II: multi-linear generalized Radon transforms”, to be posted in the coming days.

We should also note that much work has been done on this problem in the vector spaces over finite fields, requiring some very different tools. For example, Michael Bennett, Jonathan Pakianathan and I recently obtained a non-trivial exponent for the distribution of triangles in two-dimensional vector spaces over finite fields by following the Elekes-Sharir paradigm used by Guth and Katz to resolve the Erdos distance conjecture in the plane. This will be a subject of a separate post in this series.

Some links to related papers not explicitly mentioned above:

On the Mattila-Sjolin theorem for distance sets by Alex Iosevich, Mihalis Mourgoglou, Krystal Taylor (http://arxiv.org/pdf/1110.6805.pdf)

–

On angles determined by fractal subsets of the Euclidean space via Sobolev bounds for bi-linear operators by Alex Iosevich, Mihalis Mourgoglou, Eyvindur Palsson (http://arxiv.org/pdf/1110.6792.pdf)

–

On volumes determined by subsets of Euclidean space by Allan Greenleaf, Alex Iosevich, Mihalis Mourgoglou (http://arxiv.org/pdf/1110.6790.pdf)

–

Multi-parameter projection theorems with applications to sums-products and finite point configurations in the Euclidean setting by B. Erdoğan, D. Hart, A. Iosevich (http://arxiv.org/pdf/1106.5544.pdf)

–

On sets of directions determined by subsets of ${\Bbb R}^d$ by Alex Iosevich, Mihalis Mourgoglou, Steven Senger (http://arxiv.org/pdf/1009.4169.pdf)

–

Sharpness of Falconer’s estimate in continuous and arithmetic settings, geometric incidence theorems and distribution of lattice points in convex domains Alex Iosevich, Steven Senger (http://arxiv.org/pdf/1006.1397.pdf)

Rate this:

Like this:

Be the first to like this post.

Finite point configurations in Euclidean space I: an overview

Rate this:

Like this:

Leave a Reply Cancel reply

Search It!

Recent Entries

Links

Follow “Change of clothes in a backpack”