Erdos' Combinatorial Geometry Problem Solved

eldavojohn writes "After 65 years, Paul Erdos' combinatorial problem has been solved by Indiana University professor Nets Hawk Katz. The problem involved determining the minimum number of distinct distances between any finite set of points in a plane and its applications range from drug development to robot motion planning to computer graphics. You can find a description of the problem here and the prepublication of the paper on arXiv. The researchers used the existing work on the problem and included two new ideas of their own, like using the polynomial ham sandwich theorem, to reach a solution that warranted at least half of Erdos' $500 reward posted for solving this problem way back in 1935."

Comments

Finally I can sleep!

[adeft]

Showing absolute ignorance here, but anyone else think the "polynomial ham sandwich theorem" sounds like it was perhaps concocted by someone overweight?

Re:Finally I can sleep!

[fishexe]

Showing absolute ignorance here, but anyone else think the "polynomial ham sandwich theorem" sounds like it was perhaps concocted by someone overweight?

...or someone starving.

Polynomial ham sandwich theorem?

[Anonymous Coward]

Seriously ... you're not making this up?

Re:Polynomial ham sandwich theorem?

[RevWaldo]

Doesn't sound very kosher to me....

.

Re:Polynomial ham sandwich theorem?

[_0xd0ad]

Actually it's a theorem that was postulated by a pig named Ben who ruminated for a while and realised that in 4-space pigs would be kosher because there would be a specific 3-dimensional hyperplane which would split their 4 feet precisely in halves.

Re:Polynomial ham sandwich theorem?

[gstoddart]

Doesn't sound very kosher to me....

Well, the "polynomial brisket sandwich" problem sounds more complicated, and the "polynomial reuben sandwich" actually involves a greater number of objects due to the increased number of pieces of meat, the sauerkraut and the pickle ... so it's actually higher complexity. You could wave away some of that by saying the meat is all one "piece" for purposed of discussion, but that might only appease the physicists and engineers.

It's only hypothetical ham, it's OK.

Re:Polynomial ham sandwich theorem?

[_0xd0ad]

You could wave away some of that by saying the meat is all one "piece" for purposed of discussion, but that might only appease the physicists and engineers.

No, the physicists have already approximated the pieces as point masses and they are all trying to figure out why you want to cut them in half.

Re:Polynomial ham sandwich theorem?

[Dog-Cow]

Except, of course, it isn't their feet that make them not-Kosher. /feels a strange blast of air over-head.

Re:Polynomial ham sandwich theorem?

[_0xd0ad]

Yeah... of the two applicable requirements for kosher (cloven hooves and ruminating), pigs actually do have cloven hooves.

It was kinda backward but I don't know how to make it into a proper joke the correct way. :/

Re:Polynomial ham sandwich theorem?

[Anonymous Coward]

Not in 3-space, you insensitive hyperclod.

Re:Polynomial ham sandwich theorem?

[_0xd0ad]

What's more, they've applied the known fact that any 3 points define a plane in 3-space and if you could "cut" a point in half with a plane, obviously its two halves on the two sides of the plane would have equal masses, so it's quite bleedingly obvious that any plane that cuts all 3 points also bisects the 3 objects they represent.

Re:Polynomial ham sandwich theorem?

[billstewart]

Isn't brisket topologically congruent to ham? Reubens, yeah, they're more complex, especially with the potential for knots in the sauerkraut, but ham and brisket are usually just slices....

Re:Polynomial ham sandwich theorem?

[Anonymous Coward]

Ham can be cut along or across the grain, or it can be processed and pressed into a "ham loaf" that has no grain at all. Brisket is generally cut against the grain.

Ham sandwich???

[gstoddart]

like using the polynomial ham sandwich theorem

Really? That's the coolest name for something I don't understand ever.

Hell, I'd have posted some of the google links to try to explain WTF it means ... but, quite frankly, I have no idea what any of them say. Can anybody put this wonderful sounding theorem into something that a layman has at least a passing chance of getting the gist of?

I'm sure whatever else the authors did was cool, but frickin' ham sammiches ... in math!! Awesome!

Re:Ham sandwich???

[Anonymous Coward]

Ham Sandwich theorem says that if you have n objects in n dimensional space, you can cut them all in half with a cut using an n-1 dimensional surface.

It's called Ham Sandwich because the analogy says if you have a chunk of ham, a chunk of cheese, and a chunk of bread (n = 3) in 3-D space, you can make a single "cut" to cut them all in exactly half. This single cut is achieved by finding the plane (3-1 = 2 dimensions) that goes through all of them.

Alternately, there's Pancake theorem that says if you have two flat pancakes on a 2-D surface (like on your countertop), there's a single line (1-D) that can cut both pancakes exactly in half. That might be easier to think of.

Re:Ham sandwich???

[slimjim8094]

You know, I was considering posting a snarky comment to that effect when it occurred to me that they probably couldn't. I barely appreciate the subtleties of the problem (that is, why it's hard).

This is the kind of proof I could maybe understand in my Algorithms class, given a week and a very good explanation. But I'm not exactly a 'layman' in that context...

Though I will agree - the polynomial ham sandwich theorem sounds badass.

Re:Ham sandwich???

[Anonymous Coward]

Erdos is a cool name for a mathematician. Er and dos are the mandarin and spanish respectively for 2. Though Yidos would be better.

Re:Ham sandwich???

[werepants]

As a really (really) rough idea: For any 3d objects of finite size, there exists a plane which could bisect all three of them.

Disclaimer:
IANAMBITCO (I am not a mathemetician, but I took calculus once)

Re:Ham sandwich???

[Anonymous Coward]

The general version states that for n objects in n-dimensional space, there is an (n-1)-dimensional hyperplane that can partition each object into two pieces of equal measure. Note: The measure can be thought as volume (hypervolume?), but measure theory allows for many other choices. Also, it should be surprising that a hyperplane ( a copy of R^(n-1) living in R^n given by fixing one coordinate) is enough freedom to make the cut, and you don't need anything more complicated.

In the case for 3D, we have three objects (slice of ham and two pieces of bread) and we have a 2D plane (knife) that, in one slice, can cut each in half, no matter their orientation or shape.

Now, if they used the Hairy Ball Theorem...

Re:Ham sandwich???

[GlobalEcho]

You also encounter the ham sandwich in some logic / philosophy classes, as follows.

Proposition
A ham sandwich is better than eternal happiness

Proof
- A ham sandwich is better than nothing.
- Nothing is better than eternal happiness.
- Therefore, a ham sandwich is better than eternal happiness. QED.

Re:Ham sandwich???

[neep]

The Polynomial Ham Sandwich Theorem!
The ham sandwich theorem, states that given n measurable "objects" in n-dimensional space, it is possible to divide all of them in half (according to volume) with a single (n - 1)-dimensional hyperplane.

The ham sandwich theorem takes its name from the case when n = 3 and the three objects of any shape are a chunk of ham, a hunk of cheese, and a piece of bread -- notionally, a sandwich -- which can then each be bisected with a single cut (i.e., a plane). The theorem then states that it is possible to slice the sandwich in half such that each half contains the same amount of bread, cheese, and ham.
              -- paraphrased from Wikipedia
-----

Basically, given a bunch of objects (N) in an N-dimensional space, you can divide it into two halves both containing the same amount of stuff in both halves using a single cut (an N-1object).

Definitely beyond my mathematics skills nowadays to use it, but I hope the explanation helps.

Re:Ham sandwich???

[drooling-dog]

Assuming that "cutting in half" means cutting through the center of mass, doesn't that boil down to saying that two points define a line (1D) in 2-space, three points define a plane (2D) in 3-space, etc? Or is there a subtlety I'm missing here?

Re:Ham sandwich???

[CyberDragon777]

Actually it's Erdo"s.
(Support Unicode already Slashdot!)

Erdo" is Forest in Hungarian, and Erdo"s would be "Foresty".

http://en.wikipedia.org/wiki/Paul_Erd%C5%91s

Re:Ham sandwich???

[_0xd0ad]

If the subjective states of "better" and "worse" are defined in such a way that "nothing" is, in fact, preferred over "eternal happiness", then yes, a ham sandwich is "better" than eternal happiness.

For instance, if the problem is referring to someone you hate, you'd prefer them to have a ham sandwich instead. Especially if they can't eat pork.

Re:Ham sandwich???

[sgunhouse]

The Sandwich Theorem in common terms:

If you have a function (the "ham") whose known values lie between two other functions (the "bread") and you are taking a limit at a point, then the limit of the "ham" is bounded by the limits of the "bread". They'll usually make some reference about the point you're taking the limit at as being where you're biting (or squeezing) the sandwich at.

Of course, it is nicest when the two limits for the bread are the same (hence the "squeezing"), but the bounds could still be useful even if they are not the same.

Re:Ham sandwich???

[Anonymous Coward]

Why assume such an obviously wrong thing? Cutting in half means splitting in two parts of equal volume.

Re:Ham sandwich???

[_0xd0ad]

Cutting in half means splitting in two parts of equal volume.

So the "top half" of Mt. Everest is obviously of equal volume to the "bottom half"?

Re:Ham sandwich???

[Jake Griffin]

Actually "Nothing is better than eternal happiness" is a way of saying "Eternal happiness is at least as good as anything else". It doesn't have to be better.

BUSTED! IN YOUR FACE!

Re:Ham sandwich???

[Anonymous Coward]

"Cutting in half" means cutting something into two pieces with the same volume.

The trick is that the ham and bread don't need to be lined up in a nice sandwich shape. If you take *any* three (measurable, three-dimensional) objects in (three-dimensional) space, located *anywhere*, you can find a single plane which simultaneously cuts all three in half. (And if you replace all those threes with some other number, you can do the same thing.)

Of course, this paper uses the "polynomial ham sandwich theorem," in which you add more objects than dimensions and make up the difference by using a general algebraic surface instead of a plane. Using polynomials allows the slice to curve around, giving more freedom.

Re:Ham sandwich???

[khallow]

Once you've defined what Mt. Everest is as an object with a fixed, finite volume, then yes, you can split it in that way.

Re:Ham sandwich???

[_0xd0ad]

Of course you can bisect anything by volume. But is it obvious that you ought to? Most people, I suspect, would logically bisect Mt. Everest into "top" and "bottom" halves by altitude, not by volume. I was countering Anonymous Coward's claim that the "obvious" way to bisect something is by volume.

If we approximated Mt. Everest as a perfect sphere of constant density, it wouldn't matter how you bisected it, because no matter which method you selected (height, cross-sectional area, volume, or mass) they would all give exactly identical results. But real-world objects usually aren't perfect spheres, and often don't have a reasonably-constant density.

Re:Ham sandwich???

[Kyont]

So the "top half" of Mt. Everest is obviously of equal volume to the "bottom half"?

Sure, if you make the cut in the right place!

Re:Ham sandwich???

[ClickOnThis]

A mathematician is a machine that turns ham sandwiches into ... uh, never mind.

Re:Ham sandwich???

[Anonymous Coward]

Hmm... I think you're saying what drooling-dog said earlier, but in a way that makes sense to me even when I'm drunk. You're getting a +1 informative for this.
- fractoid-with-mod-points

Re:Ham sandwich???

[_0xd0ad]

There's no "right" or "wrong" place to cut it. There is only a "correct" place to cut it if you want to bisect it by volume, which most people don't want to do, and therefore it's quite wrong to do that in most situations.

There's a million different ways to cut it, and all of them are "right" answers to different questions. So what's the right question?

Suppose you're trying to divide an apple and an orange between two children, giving them equal portions. The boy says apples and oranges are both fruit, so it would be fair to give one of them the apple and the other the orange since they'll have equal amounts of fruit. The girl contradicts that and says that apples and oranges are not really the same and she likes both kinds, so in order to really be fair they should each get half an apple and half an orange. Then the boy retorts that he doesn't like oranges and she likes both kinds, and it wouldn't be fair for her to have two kinds of fruit that she likes while he only gets one kind that he likes and one that he doesn't... so to really be fair she should have to eat the orange and let him eat the apple. And then the girl suggests that to be fair they should be allowed to take turns on alternating days to decide how to divide their fruit!

Even in such a very simple situation there's more than one way that you could divide things to be "equal", and the only "obvious" answer is that there is no "obvious" answer. Also, I'd hate being a parent.

Re:Ham sandwich???

[Anonymous Coward]

Maybe you'd also go nuts for "Hairy ball theorem" then? http://en.wikipedia.org/wiki/Hairy_ball_theorem

Re:Ham sandwich???

[khallow]

But is it obvious that you ought to?

Depends how you define "bisect". A usable definition gets you one or more "obvious optimizations" for free.

This is a subtle issue in mathematics. Vaguely defined operations on vague objects generally go nowhere. Concrete, well-defined stuff gives you both a working problem and insight in what are the real issues.

Nothing aside from your own diligence keeps you from making thousands or millions of rival mathematical definitions of objects and bisections. These are all valid and all just as "obvious".

The thing about bisections into equal volumes, is that it happens to be particularly parsimonious. That is, it requires very little information to define the concept and design an algorithm which yields the desired bisection. Further, it is stable, that is, you can tweak the definitions a little (there are concrete ways in which you can define that) and get bisections which are close (again defined in concrete ways) to the equal volume bisections.

Re:Ham sandwich???

[_0xd0ad]

The thing about bisections into equal volumes, is that it happens to be particularly parsimonious. That is, it requires very little information to define the concept and design an algorithm which yields the desired bisection.

What you're saying amounts to "but it's easier this way".

By the same argument it makes the most sense to bisect Mt. Everest into top and bottom halves of equal height, because I can do that with a single picture and a ruler (very little information), whereas bisecting it into halves of equal volume would require, at the least, two pictures from different angles to give me a rough idea of its 3-dimensional shape.

It makes the most sense to take into consideration as many different properties as possible, because you can always just assign them constant values later and they'll fall out of the equation. If you define bisection in terms of bisecting something by mass, you can always simply assume that the density is near-uniform... lo and behold, now you're bisecting by volume.

Re:Ham sandwich???

[johanatan]

Center of mass *or* center of volume; but, yea, that's the way I am seeing it too.

Re:Ham sandwich???

[khallow]

What you're saying amounts to "but it's easier this way".

Yes, to such a degree that it is the difference between impossible and possible.

bisecting it into halves of equal volume would require, at the least, two pictures from different angles to give me a rough idea of its 3-dimensional shape.

You only know part of its shape. What is the shape of the part you can't see from the surface? does it get lopped off at the base, where the crust begins a few dozen km down, or is it a wedge straight to the core of the Earth?

Second, do you have a consist way to bisect this object? Or do you cut it differently each time you try?

It makes the most sense to take into consideration as many different properties as possible, because you can always just assign them constant values later and they'll fall out of the equation. If you define bisection in terms of bisecting something by mass, you can always simply assume that the density is near-uniform... lo and behold, now you're bisecting by volume.

And if you're bisecting by mood, you can just hang it up, until you get rid of that variable. You can always generalize an overly simple model and sure, you generally can simplify a complex model, but you can't always derive a complex model to simplify.

Re:Ham sandwich???

[_0xd0ad]

Yes, to such a degree that it is the difference between impossible and possible.

What you're saying amounts to "but it's too hard".

And if you're bisecting by mood, you can just hang it up, until you get rid of that variable. You can always generalize an overly simple model and sure, you generally can simplify a complex model, but you can't always derive a complex model to simplify.

Yes... because it's extremely hard to define a theoretical model to describe how you bisect something by mass. So hard, in fact, that scientists should just pretend mass doesn't exist and approximate everything as a uniform-density solid of a particular volume and shape.

Re:Ham sandwich???

[Anonymous Coward]

A mathematician is a machine that turns ham sandwiches into ...

More mathematicians?

Re:Ham sandwich???

[khallow]

What you're saying amounts to "but it's too hard".

And what makes you think that's not a valid excuse? Too hard problems whip my ass all the time. I can beat my head on the immovable wall or I can try simplifications to see if I can get anywhere with that strategy.

Yes... because it's extremely hard to define a theoretical model to describe how you bisect something by mass. So hard, in fact, that scientists should just pretend mass doesn't exist and approximate everything as a uniform-density solid of a particular volume and shape.

Let's give a counterexample. We have three bounded measurable objects in three dimensional space which are not constant density. If they were, a plane could bisect them, splitting them into equal volume sets.

Now it turns out that I can use this result directly to prove the same for objects with variable density by adding a fourth dimension for density. The object becomes a 4-dimensional constant density object with the shadow onto 3 dimensions being the objects actual 3-D shape and the width of the object from the 3-D plane out being its density at that 3-D point. Think of the objects as buildings with the floor resting on the 3-D world and the height at a point on the floor of that building being the density of the solid at that point.

Now take a very small, very distant ball and move it around. By the Ham Sandwich theorem, there's always a 3-dimensional hyperplane which cuts through all four shapes, Because we can move it around, we eventually can orient the cutting plane so that it is parallel to the density axis. The projection of this hyperplane into 3-D space then is a plane that bisects my original three objects into equal mass pieces.

Alternately, we could modify the proof of the Ham Sandwich theorem so that the measure is not constant but is the density of the three objects when we're inside any of them and an arbitrary constant everywhere else. As the original proof, you get that there is a unique plane which bisects these shapes into equal "volume" pieces. But because our choice of metric turned out to be equal to the density of the objects while inside the objects, we then get that we've bisected each of our three objects into equal mass pieces.

So I've handwaved a couple of approaches. The first set up the original variable density problem in 3-D as a constant density problem in 4-D and found a 3-D hyperplane cut that projected down to the desired 2-D plane cut. Second attempt changed how I measured volume so that my new volume just so happened to agree with mass when I was inside the objects of variable mass.

That's two approaches for how you can extend the power of the original proof to more complex examples.

Sometimes it makes sense to come up with a very general version of the problem and then collapse it, but the strategy of developing simple examples and then extending those examples is usually a very effective strategy.

Re:Ham sandwich???

[_0xd0ad]

We've grown rather off-topic from the original point.

My original point was that "cutting through the center of mass" isn't any more "obviously wrong" than "splitting in two parts of equal volume" when you're trying to define the ambiguous phrase "cutting in half". Both of them are "obviously wrong" if you're talking about the most obvious way to split Mt. Everest into top and bottom halves.

Furthermore, there's absolutely no reason to define the problem as "divide x into two parts of equal volume" when you can just as easily define the problem as "divide x into two parts of equal mass", particularly since you can convert the latter into the former just by assuming constant density.

Re:Ham sandwich???

[bill_mcgonigle]

Can I sue a polynomial ham sandwich?

Really though, I was just posting to point out how many Maths geeks point to /. as AC. Interesting correlation.

Or maybe it's one Nash-type genius, I dunno.

Re:Ham sandwich???

[GlobalEcho]

While you are correct, the logic problem in the proof is not quite so recondite. Think set theory.

Re:Ham sandwich???

[_0xd0ad]

Yes, I'm well aware that the 2nd assertion doesn't grammatically mean what it's logically asserted to mean.

Re:Ham sandwich???

[khallow]

Ok, going way to the beginning, if you cut through the center of mass, you usually aren't cutting into two equal volumes or masses. I believe the original claim that the cut through the center of mass was "wrong" because it would not normally cut into equal volumes. That's all.

If the problem is to cut objects into equal volumes, then it doesn't make sense to define bisection in some way that is irrelevant to the problem.

Now maybe they were claiming that there was a "right way" to bisect (though that's not my impression), but I don't support that. I don't believe that there is any sense in which things are "right" or "wrong" mathematically, except for logical truth of statements.

As to splitting Mt. Everest, you have yet to tell me what it is. The part we see is only a partial surface of it. The hidden part can be relatively small or large depending on what you decide it is.

Finally, the equal volume bisection is interesting because it's something we might want to do on occasion and you can come up with significant theorems about equal volume bisection.

Re:Ham sandwich???

[_0xd0ad]

Ok, going way to the beginning, if you cut through the center of mass, you usually aren't cutting into two equal volumes or masses.

What? By definition if you cut through the center of mass you're cutting into two equal masses.

I don't believe that there is any sense in which things are "right" or "wrong" mathematically, except for logical truth of statements.

"There's no failure quite as dissatisfying as a complete and total solution to the wrong problem." - Slashdot footer quotation.

Re:Ham sandwich???

[_0xd0ad]

Crap. Never mind, you're right. Cutting through an object's center of mass doesn't necessarily result in two equal masses.

Re:Ham sandwich???

[Anonymous Coward]

The corollary I heard for the 3-D case was that if you spread mustard on the ham-cheese-bread sandwich, although you can cut the ham, cheese, and bread exactly in half, you just can't cut the mustard.

Re:Ham sandwich???

[Geminii]

Into coffee, thus reducing it to a previously solved joke.

Mathematics

[Nerdfest]

As someone not well versed in the field of mathematical proofs, all I can really add to this discussion is that "Nets Hawk Katz" is a really cool name.

Re:Mathematics

[Anonymous Coward]

If they make a movie of this, the part of Nets Hawk Katz should be played by Lex Shrapnel.

Re:Mathematics

[Webs 101]

I was friends with Nets when we were undergrads. He was just Nets Katz, then. Hawk is a translation of his Hebrew name "Nets".

Re:Mathematics

[SAU!]

Team Wiess!

Re:Mathematics

[Webs 101]

Lance?

Re:Mathematics

[Ginger Unicorn]

Nets Hawk Katz looked to me like an anagram. But the only anagram I could find of this was Hawk Tank Zest.

Re:Mathematics

[SAU!]

Yes, it's me. I thought throwing that in there might shake a few people out of the hedges....

Real-world applications?

[Jugalator]

The problem involved determining the minimum number of distinct distances between any finite set of points in a plane

So will this assist me in traversing a crowded pub more effeciently to get me more quickly to a well-defined set of interesting girls, according to my parameters?

Re:Real-world applications?

[intellitech]

Yes, but you'll have to refer to Nash theory in order for everybody in your group to get one in the first place.

Re:Real-world applications?

[pittaxx]

Most likely, however the process of entering all of those parameters into a computer might have an undesired side effect on the set of girls in question.

Re:Real-world applications?

[gstoddart]

Yes, but you'll have to refer to Nash theory in order for everybody in your group to get one in the first place.

Ignore the hot blond, go for her plainer friends.

Words to live by.

Re:Real-world applications?

[margeman2k3]

When you define your set of interesting girls, you need to watch out for the Axiom of Choice. It's known to make things like this quite complicated.

Re:Real-world applications?

[Burdell]

Yeah, but if you accept the Axiom of Choice, you can decompose the hot girl and recompose the non-discrete pieces into two hot girls, each equal to the original!

Re:Real-world applications?

[StuartHankins]

+1 Insightful. They want attention too and are usually more willing to work for it.

Re:Real-world applications?

[gstoddart]

+1 Insightful. They want attention too and are usually more willing to work for it.

And, if you all go for the hot blond, get shot down, and then go for her friends ... they'll all know they were second choices and be unhappy about it.

Pretty much what the poster meant when he said the Nash theorem.

Re:Real-world applications?

[aardwolf64]

Yes yes, we all saw the movie too.

Re:Real-world applications?

[lsatenstein]

I presume the solution method would allow optimizing the travelling salesman problem, or even in shipments of products from a sales organization to multiple clients in one truckload. Or do I not understand the practical solutions.

Nets Hawk Katz

[Anonymous Coward]

The Professor's name, unfortunately, sounds like a sports headline. Should be "Katz Wins over Erdos in Second Half".

Next problem on his list

[paiute]

He is working on Einstein's Tonsorial Problem:

http://www.math.indiana.edu/people/profile.phtml?id=nhkatz

Re:Next problem on his list

[Fnord666]

Next problem on his list :
He is working on Einstein's Tonsorial Problem

Really? There is a more generalized version of this problem that extends into higher dimensions. I figured he would have been working on extending the solution into dimensions >= 3. Maybe it's only tenured academics that milk such things for all they're worth.

Erdos'

[Anonymous Coward]

Can we finally kill this awful grammar meme? Proper names that end in "s" still get the apostrophe-s treatment. You only drop the final "s" if the word is plural. You would go to Mr. Jones's used car lot, and you might mow the Joneses' lawn. It's gotten ridiculous.

Re:Erdos'

[jdpars]

Mod parent up. It's not a commonly known grammar fact, but it is an important one. Of course, I may be biased with a last name that ends in "s."

Re:Erdos'

[fmobus]

also, his name is not written like that. I would write the correct spelling, but this frakup called slashcode can't get utf-8 right in 2011.

Re:Erdos'

[gstoddart]

It's not a commonly known grammar fact, but it is an important one.

Sadly, some of us know this, but apparently even grammar experts seem to think it doesn't apply anymore. I actually disagreed out loud to my copy of Eats, Shoots, and Leaves when she said to not do it that way.

Given how thoroughly drilled into my be rather stern old teachers, I still cringe when I see it used wrong.

Re:Erdos'

[Anonymous Coward]

Yep. The first bloody paragraph of Strunk and bloody White. Learn it by heart, motherfuckers!

1. Form the possessive singular of nouns with 's.

Follow this rule whatever the final consonant. Thus write,

• Charles's friend
• Burns's poems
• the witch's malice

This is the usage of the United States Government Printing Office and of the Oxford University Press.

Exceptions are the possessives of ancient proper names in -es and -is, the possessive Jesus', and such forms as for conscience' sake, for righteousness' sake. But such forms as Achilles' heel, Moses' laws, Isis' temple are commonly replaced by:

• the heel of Achilles
• the laws of Moses
• the temple of Isis

The pronominal possessives hers, its, theirs, yours, and oneself have no apostrophe.

Re:Erdos'

[pjt33]

Can we finally kill the idea that orthography is part of grammar?

Re:Erdos'

[Xtifr]

The first bloody paragraph of Strunk and bloody White.

Yes, and that's only one of the many many things that misguided and horribly out-of-date book is wrong about.

This post by Prof. Arnold Zwicky (Linguistics, Stanford) only gives a hint of how much that little book is loathed by people who actually know something about language and style. Especially on the other side of the pond where many of its "rules" were never ever considered correct.

Strunk & White is to language as BASIC is to programming--you can learn something from it, but it's likely to cause damage that will take years to repair.

Re:Erdos'

[Xtifr]

According to whom? From the Chicago Manual of Style FAQ:

Q. Which is the correct singular possessive form? “Professor Davis’ class” or “Professor Davis’s class”? [...]
A. In its 15th edition, CMOS allowed the style shown in your first example, but the new 16th edition (7.21) no longer recommends it, although it is not incorrect...

Re:Erdos'

[Anonymous Coward]

Granted, the book is outdated, misguided at places, and American-centric. But that is most certainly not one of the things it's wrong about. Most style/orthography/whatever guides I've seen give advice remarkably consistent with this little paragraph.

Re:Erdos'

[Xtifr]

There are so many bad/clueless style guides out there that sheer quantity doesn't really say much. The Chicago Manual of Style—one of the few really widely-respected guides to American English style and usage—recommends using the apostrophe with 's', but explicitly says that just the apostrophe is not incorrect. (This is a change from the previous edition where they didn't even state a preference.)

Subtraction

[bunratty]

The reward was posted in 1935 but it's been solved after 65 years? Someone needs to brush up on their subtraction or current events -- the year is currently 2011. I don't think I would trust the person who made that mistake to accurately explain this advanced mathematical research.

Re:Subtraction

[Anonymous Coward]

Summary is incorrect. TFA says 1946, which would be 65 years.

Re:Subtraction

[olsmeister]

According to TFA, the problem was originally posed by Erdos in 1946.

Re:Subtraction

[bunratty]

Ah, eldavojohn, posting math research stories but unable to do subtraction.

Re:Subtraction

[Anonymous Coward]

A mathematician would point out that you're right. An English professor would point out that the article is also right.

Times...?

[Anonymous Coward]

So he offered up a reward 11 years before he created the problem?

Nets Hawk Katz?

[Anonymous Coward]

Isn't he one of the Harlem Globetrotters from Futurama?

Mildly Ambiguous

[mathcam]

Saying "Paul Erdos' combinatorial problem" is like saying "Michael Jordan's dunk he made that one time."

Re:Mildly Ambiguous

[zaxus]

I'm sorry, I'm a geek; I don't understand sports metaphors. :-)

Re:Mildly Ambiguous

[Anonymous Coward]

Saying "Michael Jordan's dunk he made that one time." is a little bit like saying "Paul Erdos' combinatorial problem".

Re:Mildly Ambiguous

[digitalsushi]

that's the funniest thing on here in 9 years.

Re:Mildly Ambiguous

[_0xd0ad]

And... for those of us who are neither scientists nor athletes (which should be pretty much all of us)... it's a bit like saying "Ford's truck model they built that one year".

Re:Mildly Ambiguous

[pjt33]

Thank you. It's sad that I had to get 70% of the way through the comments before I found one which actually recognised this obvious fact.

Re:Mildly Ambiguous

[Anonymous Coward]

you just spoiled a brilliant joke, you fucking retard.

Example of It in Use

[eldavojohn]

The Fields Medal winner named in the article has a blog about using it to prove the Szemeredi-Trotter theorem and of course there's the wikipedia article on the generalized form of it. Also, I screwed up the summary, the reward was offered in '46 not '35.

Re:Example of It in Use

[gstoddart]

The Fields Medal winner named in the article has a blog about using it to prove the Szemeredi-Trotter theorem and of course there's the wikipedia article on the generalized form of it.

You know, when I googled for "Ham Sandwich Theorem", wiki didn't even show up in the first page, so I assumed there wasn't one.

Oddly enough, the first paragraph nicely summarized what it boils down to:

In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone-Tukey theorem after Arthur H. Stone and John Tukey, states that given n measurable "objects" in n-dimensional space, it is possible to divide all of them in half (according to volume) with a single (n - 1)-dimensional hyperplane. Here the "objects" should be sets of finite measure (or, in fact, just of finite outer measure) for the notion of "dividing the volume in half" to make sense.

So, cutting a sandwich in half, but expanded to a higher number of dimensions. Specifically, where the number of objects corresponds to the number of dimensions -- so, by crude extension, add lettuce, tomato and cheese to your sandwich and do it in six dimensions (yes, I know, that is a horrible over-simplification and I can't think of a car analogy).

Re:Example of It in Use

[WhirlwindMonk]

Specifically, where the number of objects corresponds to the number of dimensions -- so, by crude extension, add lettuce, tomato and cheese to your sandwich and do it in six dimensions (yes, I know, that is a horrible over-simplification and I can't think of a car analogy).

When expanding beyond three dimensions, you have to prefix the word "hyper" onto all objects. So you would add "hyper-lettuce," "hyper-tomato," and "hyper-cheese." Or if you really want to be exact, "six-dimensional hyper-lettuce," etc.

Re:Example of It in Use

[gstoddart]

When expanding beyond three dimensions, you have to prefix the word "hyper" onto all objects.So you would add "hyper-lettuce," "hyper-tomato," and "hyper-cheese." Or if you really want to be exact, "six-dimensional hyper-lettuce," etc.

Six-dimensional hyper-ham ... I know people who would weep tears of joy at those words.

Re:Example of It in Use

[swfranklin]

Six-dimensional hyper-ham

I don't think that's a kosher example...

Re:Example of It in Use

[Anonymous Coward]

Its call the Ham Sandwich theorem because it is easier to visualize slicing a ham sandwich than it is to slice a Turkey and a Stone...

?What?

Re:Example of It in Use

[CraftyJack]

I think we all know where this is heading, so I'm just going to say it: Seven-dimensional hyper-bacon.
Dare to dream.

Re:Example of It in Use

[gstoddart]

I think we all know where this is heading, so I'm just going to say it: Seven-dimensional hyper-bacon.
Dare to dream.

Sorry, but I think that might open up a rift in the pork-time continuum.

Re:Example of It in Use

[Anonymous Coward]

Why isn't this comment +5 Funny?! Injustice!

Re:Example of It in Use

[Anonymous Coward]

Also, you left Larry Guth out of the discussion. He is an author on the paper, too!

Re:Example of It in Use

[davester666]

to go along with the six degree's of bacon!

Guth

[Anonymous Coward]

The summary here doesn't mention the other author Larry Guth, who pioneered the use of the polynomial ham sandwich theorem in this context.

Can they still cash that in?

[atari2600a]

$500 in 1935 would be roughly $8K today...

Re:Can they still cash that in?

[Anonymous Coward]

I was thinking that too. What does "posted" mean. Does it mean that $500 was pledged? In that case the guy might be dead, and his estate disolved. Forget about it. OTOH, if "posted" means "deposited in an interest bearing account with legal instructions to only release the money under given circumstances" then it could be a nice sum. Interest rates are terrible now, but for much of the period in question they were 5%. Over the course of a few decades, compounding does some nice things.

Since I live in Abstract Hilbert Space

[PolygamousRanchKid]

I have no idea how to cut the sandwich . . . I can't even manage to find the bugger: http://en.wikipedia.org/wiki/Hilbert_space

Ham Sandwich theorem says that if you have n objects in n dimensional space, you can cut them all in half with a cut using an n-1 dimensional surface.

It's called Ham Sandwich because the analogy says if you have a chunk of ham, a chunk of cheese, and a chunk of bread (n = 3) in 3-D space, you can make a single "cut" to cut them all in exactly half. This single cut is achieved by finding the plane (3-1 = 2 dimensions) that goes through all of them.

Alternately, there's Pancake theorem that says if you have two flat pancakes on a 2-D surface (like on your countertop), there's a single line (1-D) that can cut both pancakes exactly in half. That might be easier to think of.

Does the pancake come with bacon?

Contingent on my alcohol intake, my counter-top can have 3-D, 4-D and 5-D dimensions. And scary green monsters on top. I guess that they like ham sandwiches . . . and pancakes,

Re:Since I live in Abstract Hilbert Space

[gstoddart]

Contingent on my alcohol intake, my counter-top can have 3-D, 4-D and 5-D dimensions. And scary green monsters on top.

That's not alcohol ... that's something out of a Hunter S. Thompson novel. :-P

Re:Since I live in Abstract Hilbert Space

[Anonymous Coward]

So what's the difference between Hilbert Spaces and Eucli... oh.

Wiki says: Apart from the classical Euclidean spaces, examples of Hilbert spaces include spaces of square-integrable functions, spaces of sequences, Sobolev spaces consisting of generalized functions, and Hardy spaces of holomorphic functions.

God damn, if I could fork() I'd spend at least a lifetime studying pure maths. It's crazy how this stuff just pops up and says "oh btw your universe is like X because Y, it's self evident" and disappears, leading to six months going "wtf" followed by a moment of "oh for fuck's sake, of COURSE".

Re:Since I live in Abstract Hilbert Space

[PolygamousRanchKid]

examples of Hilbert spaces include spaces of square-integrable functions, spaces of sequences, Sobolev spaces consisting of generalized functions, and Hardy spaces of holomorphic functions.

Well, that pretty much describes the closet where my girlfriend keeps her shoes. I call it Fibber McGee's closet, but she is German, and doesn't understand the joke: http://en.wikipedia.org/wiki/Fibber_McGee_and_Molly#The_Closet

It is a simple radio gag, but I still laugh my ass off whenever I hear it. "Oh, Molly, I'll get that, it must be here in my closet . . ."

Actual authors

[domulys]

After 65 years, Paul Erdos' combinatorial problem has been solved by Indiana University professor Nets Hawk Katz.

It was actually solved by Larry Guth and Nets Hawk Katz. Not sure how it is that authors magically disappear from press releases, especially principal authors...

Re:Actual authors

[Infiniti2000]

It was actually solved by Larry Guth and Nets Hawk Katz. Not sure how it is that authors magically disappear from press releases, especially principal authors...

Larry Guth seems to be some sort of graduate student, though it's not clear that that's so. That would certainly explain it, however. Graduate students are scum compared to the professors. Didn't you know that?

Re:Actual authors

[swfranklin]

The article is about Katz, published by Indiana University.

Re:Actual authors

[eulerizeit]

In mathematics they alphabetize authors so there is no assumption of primary, secondary, etc.

Re:Actual authors

[Anonymous Coward]

Guth got his Ph.D. in 2005; he's a member of the School of Mathematics at the Institute for Advanced Study, which doesn't have any students at all, graduate or undergrad. And in math there are no principal or secondary authors: you're either a coauthor or you're not, and all names appear in alphabetical order. It isn't some sort of lab science where the grad students spend 60+ hours a week doing their advisors' bitch work and getting little or no credit for it.

In any case, the article is a press release from Katz's home institution, which is why it credits him in the title. The main text repeatedly credits "Katz and Guth" for their joint work, though, so I don't see a problem here.

taking back our hearts, minds, ability to thrive

[Anonymous Coward]

never a better time? see you there? check the #'s. it's 100% legit. probably can be marked by an outbreak of spontaneous care for one another/our young. you can feel it?

Ham Sandwich Theorem

[anwaya]

The Stone–Tukey version of this theorem is a generalization of a simple case.

Consider a ham sandwich, with two slices of bread around a slice of ham. Each of these components has a center of gravity, and if you slice any one of these with a plane that passes through the center of gravity, then the two halves will be equal in mass.

Three points in 3-space define a plane, so the unique plane that passes through the three centers of gravity divides both slices of bread and the ham in half.

The general case states that you can divide n finitely measurable objects in n-space with an n-1 dimensional hyperplane.

Re:Ham Sandwich Theorem

[Anonymous Coward]

Are planes allowed to curve or do they have to be "flat"? Because the only way a flat plane is going to perfectly bisect 2 pieces of bread and a piece of ham is if their centers of volume (or mass, gravity or however you're quantifying the bisection units) were all perfectly aligned in the first place, which makes (at least to me) the theorem self-evident.

Re:Ham Sandwich Theorem

[Anonymous Coward]

Warning: I have no idea what I'm talking about.

I believe that's the nonintuitive part that makes it an interesting theorem: It's apparently true even when they're not aligned, using a single flat plane.
Consider the 2D/1D version - pancakes lying flat on a desk, and you get one straight line. Can you align the pancakes in a (non-overlapping, I believe) way such that it's not possible to split both in equal-weight halves with the line? (The answer is apparently "no".)

The "three 3D objects, one 2D plane"-version is the same thing, scaled up one dimension. Imagine three objects, and a triangle between their centers of mass - a plane with the same orientation as that triangle would obviously split them in two. The surprising thing is that it seems those halves would have the same mass.

Re:Ham Sandwich Theorem

[CyberDragon777]

A plane is a 2D surface, therefore it is flat.

Re:Ham Sandwich Theorem

[mapkinase]

Seems like you know what you are doing. What the heck is "distinct distance"? Is it the number of distances larger than some characteristic distance of this set (average, diameter, etc.)?

Re:Ham Sandwich Theorem

[Anonymous Coward]

You need to split stuff in two parts of equal volume. This doesn't necessarily involve cutting trough center of gravity of anything.

Re:Ham Sandwich Theorem

[_0xd0ad]

Why would you want to divide a sandwich by volume? To check you'd have to dunk it in water and then it'd be all soggy. Gross.

You divide it into halves by weight, and then you check it with a grocer's scale, dummy.

Re:Ham Sandwich Theorem

[anwaya]

A volume of uniform (non-zero) density has a center of volume at the same place as the center of mass.

Re:Ham Sandwich Theorem

[anwaya]

The centers of mass do not have to be aligned, if by aligned you mean that they lie on a straight line. They just all have to lie on a plane, which is always true of any three points - unless they all lie on a straight line or coincide, and in either of these cases there is an infinite number of planes that bisect.

Re:Ham Sandwich Theorem

[_0xd0ad]

center of gravity ... mass

I'm not sure which makes me want to slap you more... the fact that you needlessly restricted the attribute of matter to its "center of gravity" instead of its "center of mass", or the fact that you then relaxed back to the general word "mass" in referring to the property which you'd just indicated was specifically its gravitational mass.

/pedant

Re:Ham Sandwich Theorem

[Noughmad]

Actually, the correct term in this case would be center of volume.

Re:Ham Sandwich Theorem

[_0xd0ad]

Actually, no it wouldn't be.

Re:Ham Sandwich Theorem

[larsbars]

What you call the Ham Sandwich Theorem is true, trivial, and most definitely _not_ the Ham Sandwich Theorem. The theorem states that there is a plane that has equal portions of ham and of each slice of bread on either side. If you cut a body by a plane through its center of gravity you _do not_ necessarily have equal volumes on either side of the plane.

Re:Ham Sandwich Theorem

[sxeraverx]

Excellent description, and it helped me understand it, but I have a minor correction.

The plane that cuts the three pieces (or the nth-dimension generalization that cuts n pieces) isn't necessarily unique, specifically in the case where the three points are colinear (or the nth-dimension generalization thereof).

Re:Ham Sandwich Theorem

[Anonymous Coward]

A Square has two distinct distances. The side and the diagonal. Those are the only two distances between the points of a square. An even pentagram also has two, a hexagon three and so on.

Re:Ham Sandwich Theorem

[SleazyRidr]

So... does that change the meaning of what he said? The centre of gravitational mass will be the same point as the centre of mass.

In reference to your reply to Noughmad, the ham sandwich theorem deals with volume rather than with mass, so referring to the centre of volume would be more directly attributable to the topic at hand.

Re:Ham Sandwich Theorem

[_0xd0ad]

What you call the Ham Sandwich Theorem is true, trivial, and most definitely _not_ the Ham Sandwich Theorem.

So? He added another dimension (density) and called it the ham sandwich theorem.

If you cut a body by a plane through its center of gravity you _do not_ necessarily have equal volumes on either side of the plane.

He didn't say you have equal volumes. He said you have equal masses.

Re:Ham Sandwich Theorem

[_0xd0ad]

The centre of gravitational mass will be the same point as the centre of mass.

So? Just because they coincide doesn't make them the same concept. That's like calling the kilogram a unit of weight.

the ham sandwich theorem deals with volume rather than with mass

Why? That's dumb. I want to slap whoever decided that, too. If you want to approximate ham and bread as uniform-density solids, fine... I'd rather leave density in the equation. I damn well know that if the ham has a big chunk of fat on one side I still don't want one half of the sandwich being mostly fat.

Re:Ham Sandwich Theorem

[larsbars]

If you cut a body by a plane through its center of gravity you _do not_ necessarily have equal volumes on either side of the plane.

He didn't say you have equal volumes. He said you have equal masses.

Cutting a body through it's center of mass doesn't still doesn't necessarily leave equal masses on either side of the (hyper-)plane. The center of mass lets you ignore the distribution of mass as a function of position (density) for certain types of problems. This is not one of them. What you are saying is still trivial, still wrong, and still not the ham sandwich theorem.

Re:Ham Sandwich Theorem

[_0xd0ad]

Cutting a body through it's center of mass doesn't still doesn't necessarily leave equal masses on either side of the (hyper-)plane.

You're right. I don't know why I had that stuck in my head.

Re:Ham Sandwich Theorem

[Anonymous Coward]

Try an L shape. The center of gravity is at coordinates (1/4,1/4). Cutting vertically through it would split the volume into a 5:3 ratio. A "center of volume" doesn't exist. Normally when someone points out a mistake you should consider you might be wrong and not merely repeat your original post.

Don't Run!

[Anonymous Coward]

It's only Ham!!!! hahahaha

whooshi

[Anonymous Coward]

doesn't this touch the border of whats possible with a computer? isn't this somehow a generalization of dependency graph models? dealing with how to put points in a hierarchical tree, where there are many different ways to base the tree, a very amorphous situation in a phathomed incremental algorithm? it feels like a generalization of graph models to the plane, a generalization of the graph (points = nodes). or, more harsh, it feels like a modulo-type of equality of point sets. i don't know how to put it, but it deals with a fundamental aspect when thinking together with modern day computers, a useful framework on the purpose and the limits of orderings in program text / memory arrays.

Prank

[Anonymous Coward]

This sounds like a prank. Graph theory 101 covers this: http://en.wikipedia.org/wiki/Handshaking_lemma

These names

[Even on Slashdot FOE]

What is it with scientists and mathematicians and their crazy names? Nets Hawk Catz? Ham Sandwich Theorem?

What's next, a Ninja Pirate Zombie Fractal theorem written by Buster Rabbits?

Re:These names

[Anonymous Coward]

Nets in Hebrew translates to "Hawk". This is actually not an uncommon pattern with Hebrew. One of the most common example names is "Dov Ber", where Dov in Hebrew means "Bear" and Ber in Yiddish means, well, Bear.

Either way, I imagine that seeing the name Nets Hawk truly confuses basketball fans.

NB: I tried to write out the Hebrew, but slashcode seems to eat the characters.

Re:These names

[Anonymous Coward]

LOLOLOL OMG ur so randome!!! Idiot.

Re:These names

[Geminii]

Oh, you've read the synopsis? :)

Erdos Prizes

[SoVeryTired]

Erdos offered many prizes for the solution of problems that he thought were difficult or out of reach of the mathematics of his time. These prizes were sometimes huge, worth tens or even hundreds of thousands of US dollars in today's money.

Erdos used to joke that he would get in trouble for violating minimum wage laws.

Re:Erdos Prizes

[afabbro]

Erdos offered many prizes for the solution of problems that he thought were difficult or out of reach of the mathematics of his time. These prizes were sometimes huge, worth tens or even hundreds of thousands of US dollars in today's money.

Erdos used to joke that he would get in trouble for violating minimum wage laws.

Too bad he didn't put that $500 in some kind of long-term savings instrument. $500 in 1935 at 5% compounded annually = $20,387.16 in 2011.

If you believe the stock market truly compounds at 10.5% annually over the long haul, then $500 in 1936 at 10.5% compounded annually = $987,422.76 in 2011.

Of course, he could have just waited a few years and bought 5,000 copies of Superman's first appearance in Action #1 and encased them in argon.

Oblig. Homer Simpson

[Anonymous Coward]

Mmmmm... ham sandwhich.... /slobbers

Bonus!

[WDancer]

He should get bonus points for style with the name "Nets Hawk Katz"

Show me the money!

[Xer0ss]

Well shit. If I had known there was 500 bucks on the line I would have given it a shot!

Elegant Simplicity

[MacGyver2210]

For being such a complex problem, the solution seems rather simple.

Guess it's one of those "Right in front of us the whole time" answers.

Thanks for the Reminder

[eldavojohn]

Ah, eldavojohn, posting math research stories but unable to do subtraction.

Don't worry, I only posted it here because I was unable to post it to reddit due to heavy usage. You won't have to put up with me or my apologies anymore.

Re:Thanks for the Reminder

[EMeta]

I hope you're joking. You provide a sizable fraction of the interesting stories here.

Graphics?

[DissociativeBehavior]

It's supposed to be a 2D problem yet there is not a single graph in the proof. I don't think they found the theorem using mathemical formulas alone. I wish they were more graphics to show the origin of the problem and its connection to the real world.

Re:Graphics?

[St.Creed]

A lot of computer graphics, especially the field of Computational Geometry, deals with sorting points and lines, finding the closest convex shape around a set of points and stuff like that. All these things are used in algorithms to draw 3D-objects faster, or detect collisions between objects, etc.

You'd need a specialist to answer the question as to what actual use this will be put - but theorems like this form the underpinnings of all computer graphics beyond just putting a few pixels on a 2D-plane.

Re:Graphics?

[Prune]

I have an MSc in CS specializing in computer graphics, but my specific area is in rendering, not computational geometry. My real question is then, is this useful for rendering specifically?

Like

[davemurphy]

I like

Hairy Ball Theorem

[Anonymous Coward]

The ham sandwich theorem sounds cool, but not quite as cool as the Hairy Ball Theorem (see wikipedia).

Graphics?

[Prune]

The summary mentions that this is useful for computer graphics. Can someone elaborate?

questions, queries, posers

[eyenot]

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

The way this reads for me is that anybody can fly into the room where some people have been sitting for decades, brows in their heads, trying hard to solve some math problem but only successfully attracting cobwebs, and just plough through it with the pOlyNoMIal hAm SaNdwIch method.

It seems like all the time in the news there is some huge problem with some totally, barf-ass, simplistic way of solving it that makes you slap the hell out of your forehead and scream "any first year student could have solved that if they were actually interested in the problem in the first place!"

Q: How many distinct math/chemistry/physics/logic problems are out there, waiting for somebody to say "just dangle a string in it dummy" or "hey you could've just evaporated it across the surface of grape juice" or whatever? Given progress of science "n" can we predict how many loose-ends there are waiting around for somebody to show half an interest in and solve immediately?

That's an insult!

[Anonymous Coward]

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.

Good thing that the winners weren't Chinese.

old news, and terrific summary

[Anonymous Coward]

This story is from NOVEMBER and it just gets on slashdot today???

Anyway, Terry Tao made a fantastic expository blog post explaining the result and the new ideas in it, not suitable for math-phobes but less technical than reading the actual research paper:

http://terrytao.wordpress.com/2010/11/20/the-guth-katz-bound-on-the-erdos-distance-problem/

Aphorism Update

[hutsell]

"My brain is open." -- Paul Erdos.
"My stomach is empty." -- Nets Hawk Katz.