A Conjecture Of Ulam
A pointed question about the plane
Stanisław Ulam was one of the great mathematicians of the last century. We talked about him in a recent post on his prime spiral and other strange mathematical facts. He is associated with several famous problems, including the 3n+1 problem and the Graph Reconstruction conjecture.
Today we want to talk about one of his oldest conjectures.
The conjecture was first stated in 1945. It is simple to state, seems plausible that it is true, but so far has resisted all attempts at resolution. René Descartes could have stated in the 1600s—well almost.
Ulam
You can skip this and the next section on Ulam and get right to his conjecture. But its been open almost sixty years, so it can wait a minute or two.
Ulam did amazing work that impacted a vast part of mathematics and physics. He also wrote popular articles that were wonderful to read. The areas include: set theory, topology, transformation theory, ergodic theory, group theory, projective algebra, number theory, combinatorics, and graph theory. One particular example is his invention of the Monte Carlo method in the 1940’s, while working at the Los Alamos National Laboratory. The name, Monte Carlo, is due to Nicholas Metropolis, after the casino, where Ulam’s uncle, Michał Ulam, was supposed to have frequently played.
The reconstruction conjecture states roughly that every undirected non-trivial graph is determined up to isomorphism by its subgraphs. Paul Kelly also gets credit for his slightly earlier work. This conjecture is wonderful in that it seems so plausible: Take a graph and give us all the subgraphs. How can that not yield the original graph? Yet it is still open since around 1960. One aspect that is especially teasing is that it has been solved in the affirmative for regular graphs, which are the hardest case for graph isomorphism, but this does not tell us much about the general case.
His Book
In 1976 Ulam published his autobiography: Adventures of a Mathematician. Here is the cover of the 1991 version:
When the book was first published, we in the theory community all read it. It was quite successful, on all measures, since Ulam was a wonderful writer. He mixed stories of people, events, and mathematics; all put together in an engaging way.
The book had another hook: Ulam included an easy-to-state puzzle that many immediately begin to work on and try to solve.
He asked for the maximum number of questions required to determine an integer between one and a million, where the questions are answered “Yes” or “No” only, and where one untruthful answer is allowed.
This is binary search with one lie allowed.
There is a strategy that is not too bad. At worst we could just do binary search asking each question twice. If we get the same answers to a question we know all is well; and if we get two different answers we know one is a lie. So this works in 
The trick is that it is possible to avoid such a brute force method and come much closer to the usual binary search bound of 
The problem became a race among many of us and the finish line was hit quickly. His original problem can be done in exactly 
The 
The Problem
Let’s now state Ulam’s really old problem. Not the reconstruction conjecture from the 60’s nor his search problem which was solved quickly in the ’70s, but his question about points in the plane.
Say a subset 
It is easy to construct an infinite set 
This can be done for any line and the same idea can be made to work for circles.
Notice that every line and every circle is a sparse subset of the plane. So Ulam made the natural conjecture:
If
is an RD set then it is not dense in the plane.
Recall that a set is dense provided every open disk in the plane contains at least one point from the set. Paul Erdős conjectured that if a set
Open Problems
Do RD sets exist? What about restricting the distances to lie in other subfields of the reals? I believe that it should be easy to prove there is a proper subfield of the reals so that there is an infinite set of points whose distances all lie in this field. However, to classify these subfields is clearly very hard, since it would solve the Ulam conjecture and more.
Reblogged this on Pink Iguana and commented:
Binary search with lies
On the subfield problem — not sure this is very well posed. The generalisation from 1 dimension is simply to use all points with both coordinates rational. Now all distances lie in Q extended by the square root of every positive integer. Perhaps the interesting question is whether it can be done with a finite extension of Q — but then this does come very close to the original problem.
The first sentence of the open problems section reads “Do RD sets exist?” but should probably say “Do dense RD sets exist?”
Ulam’s problem sounds similar to a problem of Falconer that I learned about recently. Falconer’s problem asks for the largest Hausdorff dimension of a set
in 
such that the set of pairwise distances 
has zero Lebesgue measure. This is a continuous analogue of the Erdos distinct distances problem: if the set 
is “large” (in Hausdorff dimension), then it must determine a “large” set of distances (in Lebesgue measure). The wiki page has some references http://en.wikipedia.org/wiki/Falconer%27s_conjecture.
Coming back to Ulam’s problem, the rationals are a mesure zero set, so if a set of points has only rational distances, then it must have low Hausdorff dimension. The best results for Falconer’s problem give a bound of 4/3 on the Hausdorff dimension. Unfortunately this says nothing because every countable set has Hausdorff dimension zero, but, of course, there are many examples of dense countable sets in the plane. Which is no big surprise since we only used the measure zero property of the rationals.