Last modified: Thursday, February 24, 2011
IU mathematician credited with solving one of combinatorial geometry's most challenging problems
Research has applications in areas as diverse as drug development, robot motion planning and computer graphics
FOR IMMEDIATE RELEASE
Feb. 24, 2011
BLOOMINGTON, Ind. -- A mathematician in the Indiana University College of Arts and Sciences is being credited with resolving a 65-year-old problem in combinatorial geometry that sought to determine the minimum number of distinct distances between any finite set of points in a plane.
The work by IU Department of Mathematics Professor Nets Hawk Katz, with Larry Guth of the Institute for Advanced Study in Princeton, N.J., achieved what many thought was unachievable: Solving Paul Erdös' 1946 Distinct Distances Problem.
"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," Katz said. "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 the finite set of points. In a historical achievement, Katz and Guth were able to reach the exponent of 1, heretofore thought to be impossible.
Building upon decades of work by others, Katz and Guth examined the problem within a group of rigid motions of the plane and used Euclidean geometry to view the distance problem as a three-dimensional linear one. Introducing two new ideas to the existing proof, the pair exponentially improved upon the most recently described lower bound of .8641, a mark Katz had previously helped obtain.
Guth and Katz were able to combine the algebraic method with a result from topology called the polynomial ham sandwich theorem, which was used to create a cell decomposition that yielded the desired results when most points were in the interiors of the cells, while the alternative case could be handled by the algebraic method.
The new proof used a geometric reformulation of the original problem that was devised by Gyorgy Elekes (Eotvos University, Hungary) and Micha Sharir (Tel Aviv University). Using that framework, Katz and Guth then implemented the polynomial ham sandwich theorem to create the new kind of cell decomposition that left points in the plane either in the interior of cells or on the walls of the cells.
"This procedure has what turns out to be the advantage of not always resulting in a decomposition," Katz said. "Instead there is a dichotomy. We either get extremely efficient decomposition that provides the incidence theorems we like, or the alternative, that the procedure fails and most of the lines lie in the zero set of a polynomial of fairly low degree. That is an acceptable alternative because it allows us to apply the algebraic method."
Fields Medal winner and UCLA math professor Terence Tao called the work "impressive" and the foundation for further advances.
"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," he wrote of the newly discovered dichotomy during a review of the proof.
Combinatorial geometry, a field that has far-reaching applications in areas as diverse as drug development, robot motion planning and computer graphics, examines discrete properties like symmetry, folding, packing, decomposition and tiling associated with combinations of geometric objects.
Janos Pach, editor in chief of the journal Discrete and Computational Geometry and one of the most frequent collaborators with Erdös, in a personal blog described the paper as "a great achievement." "Let us celebrate this fantastic development," he wrote.
Erdös created a $500 prize for anyone coming up with the solution to the distance problem, which has long considered one of the most challenging problems in geometric combinatorics. Until now that prize had gone unclaimed. But at a recent meeting of the Canadian Math Society, Ron Graham, chief scientist at the California Institute for Telecommunications and Information Technology and the person in charge of the prize since Erdös' death, agreed after an audience discussion that the discovery warranted a $250 prize.
"The sense in which our result is non-optimal is only in the logarithms," Katz noted. "The lower bound is of the order of N/(log N) instead of the optimal N/(log N)^{{1/2}}, but the exponent -- which is the power of N in the numerator -- is the sharp exponent 1."
Katz, who came to IU in 2004, has a B.A. in mathematics from Rice University and a Ph.D. in math from the University of Pennsylvania. Guth is a member of the School of Math at the Institute for Advanced Study.
The paper, "On the Erdös distinct distance problem in the plane," is currently available here at the electronic preprint archive arXiv and has been submitted for publication in the Annals of Mathematics, considered to be one of the most prestigious mathematics journals in the world. Katz's work was partially supported by the National Science Foundation.
For more information or to speak with Katz, please contact Steve Chaplin, University Communications, at 812-856-1896 or stjchap@indiana.edu.
