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 ${1}$ apart have the same color?

The value is known to be either ${4}$, ${5}$, ${6}$, or ${7}$; 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

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

$\displaystyle 1^{k} + 2^{k} + \cdots + (m-1)^{k} = m^{k},$

where ${k \ge 2}$ and ${k,m}$ 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 ${k \ge 2}$ must have ${m > 10^{10^{6}}}$.

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 ${k \ge 2}$, must have ${m > 10^{10^{9}}}$.

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

$\displaystyle \sum_{k=1}^{m} \frac{1}{p_{k}}$

is never an integer if ${p_{1},\dots, p_{m} }$ are distinct primes. Do you see why?

• The behavior of the function ${p(\alpha)}$, which is defined to be the smallest ${x}$ so that

$\displaystyle \sum_{p \le x} \frac{1}{p} \ge \alpha.$

The sum is over primes.

The latter function is well defined since Leonhard Euler proved that

$\displaystyle \sum_{p \le x} \frac{1}{p} = \ln\ln x + O(1).$

Since the sum grows very slowing, computing the function ${p(\alpha)}$ exactly is a serious computational challenge. For example, the record appears to be

$\displaystyle p(4) = 1801241230056600467.$

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 ${k}$ vs ${m}$. This will not solve the problem, but may allow us to get some additional insights into the possible solutions. Assume that ${(k,m)}$ is a solution, then

$\displaystyle \frac{1^{k}}{m^{k}} + \frac{2^{k}}{m^{k}} + \cdots + \frac{(m-1)^{k}}{m^{k}} = 1.$

This is equal to,

$\displaystyle \sum_{\ell =1}^{m-1} (\frac{m-\ell}{m})^{k},$

and this is the same as,

$\displaystyle \sum_{\ell =1}^{m-1} (1-\frac{\ell}{m})^{k}.$

The latter should show that

$\displaystyle \sum_{\ell =1}^{m-1} \exp(-k\ell/m) \approx 1.$

The thought I have is that the equation should yield a tight bound on ${k}$ vs ${m}$. This will not solve the problem, but it should imply that ${k}$ must be almost equal to ${m}$, 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.

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 ${f(x)}$ so that

$\displaystyle f(x-1)^{k} + f(x-2)^{k} + \cdots + f(x-(m-1))^{k} = f(x)^{k},$

for ${k \ge 2}$? This appears to be easy to resolve: there are no solutions. Just repeatedly differentiate the equation with respect to ${x}$. Divide out by ${f'(x)}$ as long as it is non-zero. It seems that this must lead to

$\displaystyle g(x-1) + g(x-2) + \cdots + g(x-(m-1)) = g(x),$

for some non-zero ${g(x)}$. But this is impossible—look at the leading term of ${x}$.

1. May 12, 2011 2:26 pm

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.

May 12, 2011 2:54 pm

I think the “m-vs-k” argument is that for f monotone on [0,1], $\frac{1}{m}\sum_{l=0}{m-1}f\left(\frac{l}{m}\right) \leq \int_0^1 f(x) dx \leq \frac{1}{m}\sum_{l=1}{m}f\left(\frac{l}{m}\right).$

For $f(x) = x^k$ you get $\frac{m}{k+1} - 1 \leq \sum_{l=0}{m-1}\left(\frac{l}{m}\right)^k \leq \frac{m}{k+1}$, so if the sum in the middle is 1 you find $k+1 \leq m \leq 2(k+1)$.

One can probably make this argument more accurate.

May 13, 2011 3:57 am

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

May 13, 2011 8:11 am

Philip,

This sounds right. If true it would eliminate some cases in the proof from the Math Monthly paper—I think.

4. May 13, 2011 11:12 am

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.

• May 13, 2011 1:42 pm

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.

May 13, 2011 4:04 pm

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.

May 13, 2011 4:40 pm

Eric,

Sorry missed that. Will look at paper right away.

May 14, 2011 1:25 am

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.

April 14, 2012 3:05 pm

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.