Mathematician credited with solving one of combinatorial geometry's most challenging problems

February 25, 2011

( -- 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.

Explore further: Learn math history to learn math theory

Related Stories

Learn math history to learn math theory

December 19, 2005

A Dutch scientist says she's discovered that knowing how a mathematical theory developed improves a pupil's understanding of the theory.

Chern numbers of algebraic varieties

June 10, 2009

A problem at the interface of two mathematical areas, topology and algebraic geometry, that was formulated by Friedrich Hirzebruch, had resisted all attempts at a solution for more than 50 years. The problem concerns the ...

Recommended for you


Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Feb 25, 2011
Did I miss something?

Are they trying to find the shortest distance to travel while connecting all dots?
3.2 / 5 (5) Feb 25, 2011
"the discovery warranted a $250 prize."

Damn it why didn't I dedicate my life to this, with all that money think of all the math they can now afford to do.
not rated yet Feb 25, 2011
Did I miss something?

Are they trying to find the shortest distance to travel while connecting all dots?

Yeah, you missed something. You often do.
It's a computational complexity proof. They've proven that
the problem can be solved in linear time.

1 / 5 (3) Feb 26, 2011
Meanwhile, Frajo and I have agreed about Wittenstein's adage:

die grenzen deiner sprache sind die grenzen deiner welt.

The limits of your languages are the limits of your world.

Yes, burn, scorn, and cast us out for encroaching and smearing Graffiti (Philosophy) on the holy shrines, halls and languages labeled Math... or worst still, Science.

Report abuse, report heretics, report us as a problem, that can be solved faster than linear time. We dare you. :) lol
3 / 5 (2) Feb 26, 2011
What kind of name is "Nets Hawk Katz"? That's almost as silly as "Moon Unit" and "Dweezil", but I thought the hippies gave up names like that when they switched from pot to coke, put on ties and started selling Credit Default Swaps on Wall Street.
1 / 5 (2) Feb 26, 2011
jesus christ you people have no value,

QC???? you should no better,,,i guess your bible didnt have the answer that equally easy question, your missing a brain.
not rated yet Feb 27, 2011
jesus christ you people have no value


I insisted no one rank me. To save you time.
Anyway BillFox has a value of 250 dollars and the highest ranking. Did you rank him? :)
1 / 5 (2) Feb 28, 2011
They found the shortest distance to the $250 polynomial ham sandwich!

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.