You are here

"Distinct Distance Problem in the Plane" Solved

March 2, 2011

Nets H. Katz (Indiana University) and Larry Guth (Institute for Advanced Study) have solved Paul Erdős' "Distinct Distances Problem," which he posed in 1946.

"If someone hands you some distinct set of points, you can figure out what is the set of differences. The problem is to determine what the minimum possible set of distances is," said Katz. "What we did is to show that no matter how you place the N points, the number of distances is at least a constant times N/log N."

Here, N represents the number of finite set of points.

First, the mathematicians noted that the work of Gyorgy Elekes (Eötvös University) and Micha Sharir (Tel Aviv University) spurred them to investigate the problem in the group of rigid motions of the plane.

In order to control points where many lines are incident, they created a cell decomposition using the polynomial ham sandwich theorem. That led to a so-called dichotomy. Either most of the points were in the interiors of the cells, in which case they got sharp results; or the points were on the walls of the cells, in which case they were in the zero set of a polynomial of low degree, which allowed them to apply the algebraic method.

Then, in order to control points where only two lines were incident, they used the flecnode polynomial of George Salmon to conclude that most of the lines were on a ruled surface. The use of the geometry of ruled surfaces completed the proof.

Fields medalist Terence Tao (UCLA) said, "Now that we know that two of the most powerful tools in combinatorial incidence geometry—the cell decomposition and the polynomial method—can be combined to give nearly sharp results that were out of reach of each of the methods separately, it seems worthwhile to revisit all of the other standard problems in the subject and see if we can advance the partial results for these problems a bit more."

The paper, "On the Erdős Distinct Distance Problem in the Plane," has been submitted for publication in the Annals of Mathematics.

Source: PhysOrg (February 25, 2011)

Id: 
1062
Start Date: 
Wednesday, March 2, 2011