Month: May 2013

by

The Elekes-Sharir Framework (part 1)

After surveying some of the variants of the distinct distances problem (part 1, part 2), I would now like to discuss a technique that is used to study such problems. As usual, thanks to Micha Sharir for helping in the preparation of this post.

Guth and Katz’s seminal work provided an almost tight bound for Erdős’s planar distinct distances problem. One can regard the proof of this bound as consisting of four main tools:

  • A reduction from the distinct distances problem to a problem about line intersections in {\mathbb R}^3 . This part is referred to as the Elekes-Sharir reduction or as the Elekes-Sharir framework.
  • The introduction of polynomial partitioning.
  • Applying 19th century analytic geometry tools that are related to ruled surfaces, such as flecnode polynomials.
  • The polynomial technique presented in Guth and Katz’s previous paper. (That is, relying on the existence of a polynomial of a small degree that vanishes on a given point set to reduce incidence problems between points and lines to the interactions between the lines and an algebraic variety.)
This series of posts discusses the Elekes-Sharir framework from the first item. This framework already has several applications beyond its original use by Guth and Katz, and more applications for it are constantly being discovered. Recent bounds for other variants of the distinct distances problem rely on this framework (this will be discussed in the following posts), and a recent work by Bennett, Iosevich, and Pakianathanalso applies it in finite fields. The framework is also used to obtain bounds for classes of congruent and similar triangles and distinct area triangles. Currently, the main challenge might be to extend the reduction to distinct distances problems in higher dimensions. While initial work in progress indicates that this can be done, the resulting problems still seem to be hard to tackle. Still, one might hope that applying the reduction in some clever manner would lead to a more elegant problem that can be solved more easily.

Before getting to the technical details, we begin with some of the history of the Elekes-Sharir framework. Then we move describe the basics of the Elekes-Sharir framework. In the following posts we discuss other applications of the framework. We will present a variant of the reduction, reproving Szemerédi’s bound on the minimum number of distinct distances where no k points are collinear. While this alternative proof can be seen as equivalent to Szemerédi’s original proof, I think that it gives more intuition about the reduction and prepares us for more advanced applications. Afterwards, we will discuss such an advanced application — namely, the number of distinct distances between two planar sets of points, each on a different line. This result is taken from this paper.

Some history

history

Elekes and Sharir used to think about the distinct distances problem, and around the turn of the millennium Elekes communicated to Sharir the basics of a reduction from this problem to a problem of bounding the number of intersections in a set of helices in {\mathbb R}^3 (this problem can also be formulated as a point-helix incidence problem in {\mathbb R}^3 ). Although this reduction seemed elegant and somewhat surprising, the resulting problem appeared hopeless with the existing tools for solving incidence-related problems. Thus, the reduction was abandoned for nearly a decade.

Continue reading →

by

Was Disney trying to kill mathematicians during the 1930’s?

It’s time for a break from the technical posts, so the only equations in this post are in the following figure. Have you ever noticed that the deaths of two of the 20th century’s top mathematicians were related to Disney’s 1937 film “Snow White and the Seven Dwarfs”?

Disney-Math-Cinderella-Infographic
A more optimistic Disney-mathematics connection.

The more well-known story is the one of Alan Turing. It appears that Disney’s Snow White was Turing’s favorite film. Turing was especially fond of the scene where the wicked witch holds the poisoned apple, and used to chant the witch’s song

“Dip the apple in the brew / Let the Sleeping Death seep through.”

Eventually, Turing reenacted the following scene, committing suicide by taking a bite out of a poisoned apple (injected with cyanide).

alan-turing-2 goedel_small mickey 1
Alan Turing, Kurt Gödel, and Mickey Mouse.

Continue reading →

by

Distinct Distances: Open Problems and Current Bounds (part 2)

This is the second post in my attempt to survey the variants of the distinct distances problem and the best known bounds for them (for the first part click here). In this part we discuss two families of open problems: the structure of planar point sets that determine a small number of distinct distances, and distinct distances in higher dimensions. While there are still many variants that have not been covered yet, after this post I will take a break from this series to discuss other issues. My next couple of big posts will focus on the so-called Elekes-Sharir framework. Once again, thanks to Micha Sharir for helping in the preparation of this post.

Structure of the optimal solution

In this section we discuss attempts to characterize point sets that determine a small number of distinct distances. This is perhaps the class of problems on which we know the least; even after decades of study, hardly anything is known about these problems. We say that a set {\mathcal P} of n points in the plane is optimal if D({\mathcal P}) = D(n) . Since even the asymptotic value of D(n) is still unknown, we also consider sets {\mathcal P} of n points such that D({\mathcal P})=O(n/\sqrt{\log{n}}) , and refer to such sets as near-optimal. All the point sets in this section are planar.

Erdős asked whether every optimal (or near-optimal) set “has lattice structure”. To make this question clearer, let us first consider some of the known near-optimal sets. In the previous post we already mentioned that the \sqrt{n} \times \sqrt{n} integer lattice, as depicted in the following figure, determines O(n/\sqrt{\log n}) distinct distances.

intGrid

This was observed by Erdős, who noticed that this is an immediate corollary of 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}) .

Continue reading →

by

Distinct Distances: Open Problems and Current Bounds (part 1)

This is the first in a series of posts about open problems that are related to the distinct distances problem. I wish to thank Micha Sharir for helping in the preparation of this post (the mistakes are of course all mine).

Given a set \mathcal P of n points in the real plane, let D({\mathcal P}) denote the number of distinct distances that are determined by pairs of points from \mathcal P . Let D(n) = \min_{|{\mathcal P}|=n}D({\mathcal P}) ; that is, D(n) is the minimum number of distinct distances that any set of n points in {\mathbb R}^2  must always determine. In his celebrated 1946 paper, Erdős derived the bound D(n) = O(n/\sqrt{\log n}) . More specifically, Erdős proved that an \sqrt{n} \times \sqrt{n} square lattice determines \Theta(n/\sqrt{\log n}) distinct distances (for more details, see the second post of this series). Though almost 70 years have passed since Erdős considered this lattice configuration, no configuration with o(n/\sqrt{\log n}) distinct distances was discovered.

For the celebrations of his 80’th birthday, Erdős compiled a survey of his favorite contributions to mathematics, in which he wrote

“My most striking contribution to geometry is, no doubt, my problem on the number of distinct distances. This can be found in many of my papers on combinatorial and geometric problems.”

Recently, after 65 years and a series of increasingly larger lower bounds, Guth and Katz provided the bound D(n) = \Omega(n/\log n) , almost matching the best known upper bound. (For a comprehensive list of the previous bounds, see this dedicated webpage by William Gasarch.) To derive this bound, Guth and Katz developed several novel techniques, relying on tools from algebraic geometry. Notice that a relatively small gap of O(\sqrt{\log n}) remains between the best known lower and upper bounds.

Problem 1. Find the exact asymptotic value of D(n) .

Since this problem is almost solved, one might wonder what is the purpose of these posts. The answer is that there are many interesting variants of the distinct distances problem which are still wide open (many of those were also posed by Erdős). For some of these variants (such as the ones presented in the first part of the next post of this series) even after several decades of work hardly anything is known. Papers that discuss problems from the set that is surveyed in the first part of this post contain phrases such as “Our ignorance in this area is really shocking!” and “It is rather frustrating that I got nowhere with…”. I wish to maintain a dynamic document, keeping track of the best known bounds for the various distinct distances variants, as time goes by. These posts are the first step towards this document.

Erdos guth katz Szem
Names that appear quite often in this set of posts: Paul Erdős, Larry Guth, Nets Katz, and Endre Szemerédi.

This first post of the series surveys problems in which a planar point set is constrained in some manner. The following post will discuss two families of problems: the structure of planar point sets that determine a small number of distinct distances, and distinct distances in higher dimensions. A great collection of open problems related to distinct distances can be found in the book “Research Problems in discrete Geometry” by Brass, Moser, and Pach (though due to various recent developments, the collection in this book is already somewhat outdated).

A more general version of Problem 1 asks to find the minimum value \hat{D}(n) , such that for every set {\mathcal P} of n points in the plane there exists a point p \in {\mathcal P} which determines at least \hat{D}(n) distinct distances with the other points of {\mathcal P} (e.g., see this paper by Erdős). An immediate upper bound is \hat{D}(n) \le D(n) = O(n/\sqrt{\log n}) . However, the bound of Guth and Katz does not immediately imply a matching lower bound for \hat{D}(n) . The best known lower bound, obtained by Katz and Tardos, is \hat{D}(n) = \Omega(n^{(48-14e)/(55-16e)})\approx \Omega(n^{0.864}) .

Problem 2. Find the exact asymptotic value of \hat{D}(n) .

Constrained sets of points

We now consider variants of the distinct distances problem where the point sets are constrained in some way. The best known bounds for the various variants are listed in the following table; see the figure and text below for an explanation of the notation used in the table. Unless stated otherwise, the point sets in this part are planar.

Variant Lower Bound Upper Bound
D_{\text{no3}}(n) \displaystyle \lceil (n-1)/3\rceil \displaystyle \lfloor n/2\rfloor
\hat{D}_{\text{no3}}(n) \displaystyle \lceil (n-1)/3\rceil \displaystyle \lfloor n/2\rfloor
\hat{D}_{\text{conv}}(n) \left(\frac{13}{36}+\frac{1}{22701}\right)n +O(1) \displaystyle \lfloor n/2\rfloor
D_{\text{gen}}(n) \Omega(n) \displaystyle n2^{O(\sqrt{\log n})}
\hat{D}_{\text{gen}}(n) \lceil (n-1)/3 \rceil n-O(1)
D_{\text{para}}(n) \Omega(n) \displaystyle O(n^2/\sqrt{\log n})
D_{\text{lines}}(n) \Omega(n^{4/3}) \displaystyle O(n^2/\sqrt{\log n})

RelAndConv

Continue reading →

by

First post

Hi,

I’m Adam and you can find various details about me in this link.

In this blog I plan to write about combinatorial geometry in general, and mainly about the algebraic techniques that are recently being used in it (the most famous example is probably the novel proof of Guth and Katz for the distinct distances problem). I will start by trying to clearly explain the basics of these methods, and then move to more advanced stuff, recent developments, etc.

Regarding other topics, I’m not yet sure what these will be yet, but I will perhaps discuss connections between incidence problems and other branches of mathematics (such as this famous connection to additive number theory), numbers of planar configurations that can be embedded on a point set, and various personal musings.

I hope that you will find something interesting to read here.