A Possible Polymath Project?
An interesting old problem of Erdős
Leo Moser was a mathematician who worked in combinatorics. He created, among many other things, a notation for extremely large numbers, and worked on the problem of coloring the plane.
Today I want to talk about an old Diophantine problem he worked on that may be ripe for some progress.
The other problem, which is probably not ripe for progress, is the the plane coloring problem first stated by Ed Nelson:
How many colors are needed to assign each point of the plane a color so that no two points exactly distance apart have the same color?
The value is known to be either , , , or ; the lower bound is due to Moser and the upper bound is due to John Isbell.
The following graphic used by Wikipedia shows both.
The graph is called the Moser spindle, and its seven vertices with unit-distance edges shown require four colors. The hexagons are somewhat less than unit-distance across, but with more than unit distance to the nearest of the same color, so seven colors suffice. The seven color sets are translations of each other, and Hugo Hadwiger in 1945 had used the same pattern to give an upper bound of 7 on the related problem of tessellating the plane by congruent sets, whose best-known lower bound is 5. Paul Erdős and Nicolaas de Bruijn employed the Axiom of Choice to show that the true value is enforced by some finite unit-distance graph—which need not be a planar graph, though the Moser spindle is planar. It is known that any 4-coloring of the plane must involve color set(s) that are not Lebesgue measurable, while recent work indicates that forms of choice would be required for any 4-coloring. Thus this problem goes deep in a hurry.
I cannot resist to add that I knew Isbell, since I once took a course on projective geometry from him when I was an undergraduate at Case Western Reserve. He later moved from Case in 1969 to the University at Buffalo, where he stayed until he retired in 2002. Ken did not know him there—it is a small world—but not that small. I will write soon about him and my adventure into projective geometry, which was one of the hardest courses I have ever taken. But that is another story, for another day.
The problem is a Diophantine conjecture, raised by Erdős around 1950 in a letter to Moser. The conjecture is that there are no solutions to the equation
where and are natural numbers. This is a typical style of question that Erdős would raise over and over. In 1953 Moser made partial progress on it, and proved that there is no “small” solution:
Theorem: Any solution with must have .
A recent paper by Pieter Moree in the American Mathematical Monthly explains the conjecture’s history, gives a improved bound, and explains in detail how it is proved. The best known lower bound now is:
Theorem: Any solution with , must have .
The paper of Moree shows how to prove a weaker bound via elementary means. As usual “elementary” does not mean simple, but means that only basic number-theory tools are used. The main ingredients are:
- Basic properties of congruences.
- The Chinese Remainder Theorem.
- The simple fact that
is never an integer if are distinct primes. Do you see why?
- The behavior of the function , which is defined to be the smallest so that
The sum is over primes.
The latter function is well defined since Leonhard Euler proved that
Since the sum grows very slowing, computing the function exactly is a serious computational challenge. For example, the record appears to be
This result is due to Eric Bach and Jonathan Sorenson.
The thought I have is that the equation should yield a tight bound on vs . This will not solve the problem, but may allow us to get some additional insights into the possible solutions. Assume that is a solution, then
This is equal to,
and this is the same as,
The latter should show that
The thought I have is that the equation should yield a tight bound on vs . This will not solve the problem, but it should imply that must be almost equal to , and I hope that this inequality will allow us to make some progress on the conjecture. I have not tried to work out the approximation, but I believe that some useful information could come from this. The reason we feel it is a good candidate for a PolyMath project is that investigating these equations and approximations may require computer algebra, with cases that can be worked on in parallel by different teams.
Is this a possible problem? Can we at least improve the bound somewhat?
Whenever we see a hard Diophantine problem we should think about what happens over polynomials instead of the integers. That is are there polynomials so that
for ? This appears to be easy to resolve: there are no solutions. Just repeatedly differentiate the equation with respect to . Divide out by as long as it is non-zero. It seems that this must lead to
for some non-zero . But this is impossible—look at the leading term of .