Jump to content

Erdős–Moser equation

From Wikipedia, the free encyclopedia
Unsolved problem in mathematics:
Does the Erdős–Moser equation have solutions other than 11+21=31?

In number theory, the Erdős–Moser equation is

where m and k are restricted to the positive integers—that is, it is considered as a Diophantine equation. The only known solution is 11 + 21 = 31, and Paul Erdős conjectured that no further solutions exist. Any further solutions must have m > 10109.[1]

Some care must be taken when comparing research papers on this equation, because some articles[2] express it in the form 1k + 2k + ⋯ + mk = (m + 1)k instead.

Throughout this article, p refers exclusively to prime numbers.

Constraints on solutions

[edit]

In 1953, Leo Moser proved that, in any further solutions,[3]

  1. k is even,
  2. p | (m − 1) implies (p − 1) | k,
  3. p | (m + 1) implies (p − 1) | k,
  4. p | (2m + 1) implies (p − 1) | k,
  5. m − 1 is squarefree,
  6. m + 1 is either squarefree or 4 times an odd squarefree number,
  7. 2m − 1 is squarefree,
  8. 2m + 1 is squarefree,
  9. and
  10. m > 10106.

In 1966, it was additionally shown that[2]

  1. 6 ≤ k + 2 < m < 3 (k + 1) / 2, and
  2. m – 1 cannot be prime.

In 1994, it was shown that[4]

  1. lcm(1,2,…,200) divides k,
  2. m ≡ 3 (mod 2ord2(k) + 3), where ord2(n) is the 2-adic valuation of n; equivalently, ord2(m − 3) = ord2(k) + 3,
  3. for any odd prime p divding m, we have k ≢ 0, 2 (mod p − 1),
  4. any prime factor of m must be irregular and > 10000.

In 1999, Moser's method was refined to show that m > 1.485 × 109,321,155.[5]

In 2002, it was shown[6]: §4  that k must be a multiple of 23 · 3# · 5# · 7# · 19# · 1000#, where the symbol # indicates the primorial; that is, n# is the product of all prime numbers n. This number exceeds 5.7462 × 10427.

In 2009, it was shown that 2k / (2m – 3) must be a convergent of ln(2); in what the authors of that paper call "one of very few instances where a large scale computation of a numerical constant has an application", it was then determined that m > 2.7139 × 101,667,658,416.[1]

In 2010, it was shown that[7]

  1. m ≡ 3 (mod 8) and m ≡ ±1 (mod 3), and
  2. (m2 – 1) (4m2 – 1) / 12 has at least 4,990,906 prime factors, none of which are repeated.

The number 4,990,906 arises from the fact that 4990905
n=1
1/pn < 19/6 < 4990906
n=1
1/pn,
where pn is the nth prime number.

Moser's method

[edit]

First, let p be a prime factor of m − 1. Leo Moser showed[3] that this implies that p − 1 divides k and that

(1)

which upon multiplying by p yields

This in turn implies that m − 1 must be squarefree. Furthermore, since nontrivial solutions have m − 1 > 2 and since all squarefree numbers in this range must have at least one odd prime factor, the assumption that p − 1 divides k implies that k must be even.

One congruence of the form (1) exists for each prime factor p of m − 1. Multiplying all of them together yields

Expanding out the product yields

where the higher-order terms are products of multiple factors of the form (m − 1) / p, with different values of p in each factor. These terms are all divisible by m − 1, so they all drop out of the congruence, yielding

Dividing out the modulus yields

(2)

Similar reasoning yields the congruences

(3)
(4)
(5)

The congruences (2), (3), (4), and (5) are quite restrictive; for example, the only values of m < 1000 which satisfy (2) are 3, 7, and 43, and these are ruled out by (4).

We now split into two cases: either m + 1 is even, or it is odd.

In the case that m + 1 is even, adding the left-hand sides of the congruences (2), (3), (4), and (5) must yield an integer, and this integer must be at least 4. Furthermore, the Euclidean algorithm shows that no prime p > 3 can divide more than one of the numbers in the set {m − 1, m + 1, 2m − 1, 2m + 1}, and that 2 and 3 can divide at most two of these numbers. Letting M = (m − 1) (m + 1) (2m − 1) (2m + 1), we then have

(6)

Since there are no nontrivial solutions with m < 1000, the part of the LHS of (6) outside the sigma cannot exceed 0.006; we therefore have

Therefore, if , then . In Moser's original paper,[3] bounds on the prime-counting function are used to observe that

Therefore, M must exceed the product of the first 10,000,000 primes. This in turn implies that m > 10106 in this case.

In the case that m + 1 is odd, we cannot use (3), so instead of (6) we obtain

where N = (m − 1) (2m − 1) (2m + 1). On the surface, this appears to be a weaker condition than (6), but since m + 1 is odd, the prime 2 cannot appear on the greater side of this inequality, and it turns out to be a stronger restriction on m than the other case.

Therefore any nontrivial solutions have m > 10106.

In 1999, this method was refined by using computers to replace the prime-counting estimates with exact computations; this yielded the bound m > 1.485 × 109,321,155.[5]: Thm 2 

Bounding the ratio m / (k + 1)

[edit]

Let Sk(m) = 1k + 2k + ⋯ + (m – 1)k. Then the Erdős–Moser equation becomes Sk(m) = mk.

Method 1: Integral comparisons

[edit]

By comparing the sum Sk(m) to definite integrals of the function xk, one can obtain the bounds 1 < m / (k + 1) < 3.[1]: §1¶2 

The sum Sk(m) = 1k + 2k + ⋯ + (m – 1)k is the upper Riemann sum corresponding to the integral in which the interval has been partitioned on the integer values of x, so we have

By hypothesis, Sk(m) = mk, so

which leads to

(7)

Similarly, Sk(m) is the lower Riemann sum corresponding to the integral in which the interval has been partitioned on the integer values of x, so we have

By hypothesis, Sk(m) = mk, so

and so

(8)

Applying this to (7) yields

Computation shows that there are no nontrivial solutions with m ≤ 10, so we have

Combining this with (8) yields 1 < m / (k + 1) < 3, as desired.

Method 2: Algebraic manipulations

[edit]

The upper bound m / (k + 1) < 3 can be reduced to m / (k + 1) < 3/2 using an algebraic method:[2]: Lemat 4 

Let r be a positive integer. Then the binomial theorem yields

Summing over yields

Reindexing on the left and rearranging on the right yields

(9)

Taking r = k yields

By hypothesis, Sk = mk, so

(10)

Since the RHS is positive, we must therefore have

(11)

Returning to (9) and taking r = k − 1 yields

Substituting this into (10) to eliminate mk yields

Reindexing the sum on the right with the substitution i = s + 1 yields

(12)

We already know from (11) that k + 1 < m. This leaves open the possibility that m = k + 2; however, substituting this into (12) yields

which is impossible for k > 1, since the sum contains only positive terms. Therefore any nontrivial solutions must have mk + 2; combining this with (11) yields

We therefore observe that the left-hand side of (12) is positive, so

(13)

Since k > 1, the sequence is decreasing. This and (13) together imply that its first term (the term with s = 1) must be positive: if it were not, then every term in the sum would be nonpositive, and therefore so would the sum itself. Thus,

which yields

and therefore

as desired.

Continued fractions

[edit]

Any potential solutions to the equation must arise from the continued fraction of the natural logarithm of 2: specifically, 2k / (2m − 3) must be a convergent of that number.[1]

By expanding the Taylor series of (1 − y)k eky about y = 0, one finds

More elaborate analysis sharpens this to

(14)

for k > 8 and 0 < y < 1.

The Erdős–Moser equation is equivalent to

Applying (14) to each term in this sum yields

where and z = ek/m. Further manipulation eventually yields

(15)

We already know that k/m is bounded as m → ∞; making the ansatz k/m = c + O(1/m), and therefore z = ec + O(1/m), and substituting it into (15) yields

therefore c = ln(2). We therefore have

(16)

and so

Substituting these formulas into (15) yields a = −3 ln(2) / 2 and b = (3 ln(2) − 25/12) ln(2). Putting these into (16) yields

The term O(1/m3) must be bounded effectively. To that end, we define the function

The inequality (15) then takes the form

(17)

and we further have

for x ≤ 0.01. Therefore

Comparing these with (17) then shows that, for m > 109, we have

and therefore

Recalling that Moser showed[3] that indeed m > 109, and then invoking Legendre's theorem on continued fractions, finally proves that 2k / (2m – 3) must be a convergent to ln(2). Leveraging this result, 31 billion decimal digits of ln(2) can be used to exclude any nontrivial solutions below 10109.[1]

See also

[edit]

References

[edit]
  1. ^ a b c d e Gallot, Yves; Moree, Pieter; Zudilin, Wadim (2010). "The Erdős–Moser Equation 1k + 2k + ⋯ + (m – 1)k = mk Revisited Using Continued Fractions" (PDF). Mathematics of Computation. 80: 1221–1237. arXiv:0907.1356. doi:10.1090/S0025-5718-2010-02439-1. S2CID 16305654. Archived from the original on 2024-05-08. Retrieved 2017-03-20.
  2. ^ a b c Krzysztofek, Bronisław (1966). "O Rówaniu 1n + ... + mn = (m + 1)n·k" (PDF). Zeszyty Naukowe Wyżsej Szkoły Pedagogicznej w Katowicach—Sekcja Matematyki (in Polish). 5: 47–54. Archived from the original (PDF) on 2024-05-13. Retrieved 2024-05-13.
  3. ^ a b c d Moser, Leo (1953). "On the Diophantine Equation 1k + 2k + ... + (m – 1)k = mk". Scripta Mathematica. 19: 84–88.
  4. ^ Moree, Pieter; te Riele, Herman; Urbanowicz, Jerzy (1994). "Divisibility Properties of Integers x, k Satisfying 1k + 2k + ⋯ + (x – 1)k = xk" (PDF). Mathematics of Computation. 63: 799–815. doi:10.1090/s0025-5718-1994-1257577-1. Archived from the original on 2024-05-08. Retrieved 2017-03-20.
  5. ^ a b Butske, William; Jaje, Lynda M.; Mayernik, Daniel R. (1999). "The Equation Σp|N 1/p + 1/N = 1, Pseudoperfect Numbers, and Partially Weighted Graphs" (PDF). Mathematics of Computation. 69: 407–420. doi:10.1090/s0025-5718-99-01088-1. Archived from the original on 2024-05-08. Retrieved 2017-03-20.
  6. ^ Kellner, Bernd Christian (2002). Über irreguläre Paare höherer Ordnungen (PDF) (Thesis) (in German). University of Göttingen. Archived from the original (PDF) on 2024-03-12. Retrieved 2024-03-12.
  7. ^ Moree, Pieter (2013-10-01). "Moser's mathemagical work on the equation 1k + 2k + ⋯ + (m – 1)k = mk". Rocky Mountain Journal of Mathematics. 43 (5): 1707–1737. arXiv:1011.2940. doi:10.1216/RMJ-2013-43-5-1707. ISSN 0035-7596.