Problems

In order to calibrate any busy beaver gauge, we must first define a common set of problems. A problem must be:

  • Semidecidable: either proof search or disproof search must terminate once the first theorem or counterexample is found
  • Arithmetic: it is either true or false of the natural numbers
  • Encodable: we know how to express it as a low-level bookkeeping computation
  • Meaningful: an affirmative or negative answer to the problem would advance the art of mathematics

Solved problems

Some problems are no longer open, but they are still useful as gauges since they can give bounds for busy beavers.

Pólya's problem

Let n be some upper bound. Do more than half of the natural numbers less than n have an odd number of prime factors? Pólya noticed in 1919 that, if true, this statement would imply the Riemann hypothesis. Haselgrove showed in 1958 that the statement is false, and Tanaka found that it is first false for n = 906,150,257 in Tanaka 1980.

See also WP.

Natural Numbers

We will always have open questions about the natural numbers.

Catalan–Mersenne conjecture

Are there a finite number of Catalan–Mersenne primes; does OEIS A7013 contain any composite numbers? Catalan conjectured this in 1876 while editing a letter from Lucas.

See also WP.

Collatz conjecture

Does the graph of the Collatz function have multiple strongly-connected components? Equivalently, does every natural number map to one under some number of iterations of the Collatz function? Collatz may have first introduced the function in 1937.

See also WP.

Erdős–Lagarias conjecture

Let k > 8. Can any k'th power of two be written as a sum of distinct powers of three; is any k'th power of two expressible in ternary with only the digits 0 and 1? Erdős conjectured that there is no such k and Lagarias studied the problem in Lagarias 2005.

Fermat prime conjecture

Is there a sixth Fermat prime? Fermat conjectured that all Fermat numbers are prime, but Euler showed that the sixth Fermat number F₅ is composite in 1732.

See also WP.

Goldbach conjecture

Aside from two, is every even number a sum of two prime numbers? Goldbach claimed this in a 1742 letter to Euler.

See also WP.

Weak Goldbach conjecture

Aside from one, three, and five; is every odd number a sum of three prime numbers? This statement is a strict weakening of the Goldbach conjecture. A proof was proposed in Helfgott 2013 but has not yet been accepted by the community.

Legendre conjecture

For all positive n, is there a prime number between n² and (n + 1)²? Legendre investigated this question.

See also WP.

Odd perfect number

Are any perfect numbers odd? The earliest examination of this question is unknown but may have been by Euclid or Nicomachus of Gerasa.

See also WP.

Period 32 Laver table

Is there a Laver table with period 32; does 32 appear in OEIS A98820? Laver showed in Laver 1995 that a Laver table exists for any power-of-two period, given ZFC plus the axiom that an I3 rank-into-rank cardinal exists.

See also WP. A collection of attempts at encoding this problem can be found at Code Golf Stack Exchange.

Riemann hypothesis

Do all non-trivial zeros of Riemann's zeta function have real part 1/2? Riemann guessed that all non-trivial zeros are real in 1859, and it is known that all non-trivial zeros have real parts in [0,1].

Equivalently, as given by Robin in 1984 and explained by Lagarias 2001, let H(n) denote the n'th harmonic number; is the sum of divisors of n always smaller than H(n) + exp(H(n)) × ln(H(n))?

See also WP, nLab.

Consistency

For any formal system with a notion of negation, antimony, or contradiction; we may ask whether it is consistent: whether the system fails to prove any pair of mutually-exclusive statements. When phrased in terms of semidecidability, consistency problems are often a form of proof search, since it can be shown that searching for one specific sort of contradiction can be sufficient to find all contradictions.

Theories which have been investigated include:

Notes

Style

  • We denote open conjectures and hypotheses with non-possessive labels. This is both to recognize a lack of primacy, as anybody can speculate on interesting matters, and a lack of proof, as we normally celebrate the effort required to prove a statement above the effort required merely to state it.
  • Some conjectures are attached to those who studied or documented them, rather than the original conjecturer, as in the case of Firoozbakht's second conjecture. Look, they have to come from somewhere. We can only hope that Firoozbakht is not upset.
  • It is tempting to over-generalize and define e.g. perfect numbers in terms of sum-of-divisors functions which are then introduced at the top of the page. However, this obscures the history of the problems, as in the case of odd perfect numbers.