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 
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
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 
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
.
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
This result is due to Eric Bach and Jonathan Sorenson.
One Idea
The thought I have is that the equation should yield a tight bound on 
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
Open Problems
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 
for 
for some non-zero 
Trackbacks
- Possible new polymath project « The polymath blog
- Possible Polymath Project « Euclidean Ramsey Theory
- Wiki-style maths | cartesian product
- More On Coloring The Plane « Gödel’s Lost Letter and P=NP
- Mathematical Mischief Night « Gödel’s Lost Letter and P=NP
- Aubrey de Grey: The chromatic number of the plane is at least 5 | Combinatorics and more
Hi Dick,
For the polynomial equation, your approach of “look at the leading coefficient” applies to the given (supposed) identity directly, leading to a contradiction to the existence of such a polynomial.
I think the “m-vs-k” argument is that for f monotone on [0,1],
For
you get 
, so if the sum in the middle is 1 you find 
.
One can probably make this argument more accurate.
Your sum of exponentials can be summed to infinity as a further approximation leading to
k/m ~ ln 2
You could look at the next term in the approximation and see if this requires a good rational approximation to ln 2
Philip,
This sounds right. If true it would eliminate some cases in the proof from the Math Monthly paper—I think.
Sum(from n=0 to N) of n^k
is for any given integer k doable in closed form, and you can express it in terms of an
asymptotic series by using the Euler-Maclaurin summation formula EQ 23.1.30 of
Abramowitz+Stegun. (And the series converges, since it terminates.)
I get for the first 4 terms
N^k [ N/(k+1) + 1/2 + k/(12N) – (k^2-3k+2)k/(720N^3) + O(k^5 / N^5) ]
and if your diophantine is to hold then this must be equal to
(N+1)^k =
= N^k [ 1 + k/N + (k-1)k/(2N^2) + (k-2)(k-1)k/(6N^3) + (k-3)(k-2)(k-1)k/(24N^4)
+ O(k^5 / N^5) ]
where the rightmost = is from Newton binomial theorem.
If k<>N
is not possible because then (N+1)^k >> N^k+(N-1)^k+…
So this proves k must be bounded between two positive constants times N.
Given that N and k are both large and k=cN for some positive constant c, these
expressions simplify to
N^k [ 1/c + 1/2 + c/12 – c^3/720 + c^5/30240 – c^7/1209600 + c^9/47900160
– 691c^{11}/1307674368000 + c^{13}/74724249600 + … ]
and
N^k [ 1 + c + c^2/2 + c^3/6 + c^4 / 24 + … ] = N^k exp(c)
respectively.
If I solve this numerically [truncating the O(c^19) terms of the series to 0] for c, I find
that the only real root of the resulting polynomial equation is
c = 0.6931471806 to 10 decimals.
Oddly enough,
ln(2) = 0.6931471806
also.
I therefore conjecture that k must be asymptotic to ln(2)N.
Assuming this conjecture can be established, we can now use known bounds on “how irrational”
ln(2) is to make further progress.
OK, using the operator derivation of the Euler Maclaurin sum formula
[JOHN BORIS MILLER:
THE EULER-MACLAURIN SUM FORMULA
A CLOSED DERIVATION
J. Austral. Math. Soc. (Series A) 37 (1984), 128-138
but I’m sure there are better cites than this, probably N.Norlund’s book]
one can demonstrate that (i) the series converge in my derivation above and (ii) that
c=ln(2) is exactly correct.
This yields the correct leading asymptotic.
More challenging would be to determine the non-leading asymptotics, which I suspect should
also be doable in closed form at least for the first few terms.
Concerning “how irrational” ln(2) is,
see Yu.V.Nesterenko, Math’l Notes 88,4 (2010) 530-543
where he provides a new proof that
|P/Q – ln2| > Q^(-3.57455391)
for all integers P,Q except for a finite set.
So a possible strategy to almost-solve your diophantine problem would be to
show the full asymptotics would imply an infinite set of too-good diophantine
approximations to ln2, hence therefore the diophantine can have at most a finite set of
solutions. Probably this strategy will not work because the bounds won’t be strong enough,
but you cannot tell until you do it.
Dick, we have published a full paper on this. The citation is
E. Bach, D. Klyve, and J. Sorenson, Computing Prime Harmonic Sums,
Mathematics of Computation 78 (2009), 2283-2305.
Eric,
Sorry missed that. Will look at paper right away.
Another line of attack is to use modulo arithmetic. Try the case where k is prime or one less than a prime and use Fermats little theorem to add up mod k. Given that k/m ~ ln 2 you can see that these cases can be eliminated. You would need some strict inequalities to make it rigorous.
There may also be possibilities mod m, or mod factors of m.
Hi!
Jonathan Sondow and I have been making good progress on this conjecture since I discovered it in 2008 — you might find our papers useful.
In particular, they use math which is both elementary *and* simple, while obtaining some fairly spectacular results. For example, in , induction is the most difficult technique we use to [re]prove that in any solution to the more general equation
1^k + 2^k + … + (m-1)^k = am^k, a ≥ 1,
m must be odd.
We’ve got another paper in preparation which might also be of interest to you when we’re done with it.
Best regards,
Kieren.
Looks like the link got lost:
http://arxiv.org/pdf/1010.2275.pdf