F. Conjectures

Number Theory, Math 413, Fall 1998

A collection of easily stated number theory conjectures which are still open. Each conjecture is stated along with a collection of accessible references.

1. The Riemann Hypothesis
2. Perfect & Mersenne Numbers
3. The Twin Primes Conjecture & Prime Gaps
4. Fermat Numbers
5. Goldbach's Conjecture
6. Catalan's Conjecture
7. Totient Function Conjectures
8. The Collatz Problem

The Riemann Hypothesis

Def: Riemann's Zeta function, Z(s), is defined as the analytic extension of sum_n=1^infty1/(n^s).

Thm: Z(s)=prod_i=1^infty (1-(1/p_i^s)), where p_i is the ith prime.

Thm: The only zeros of Z(s) are at s=-2, -4, -6, ... and in the strip 0<Re(s)<1.

Conj: The only zeros of Z(s) are at s=-2, -4, -6, ... and on the line Re(s)=1/2.

Thm: The Riemann Conjecture is equivalent to the conjecture that for some constant c, |pi(x)-li(x)| < csqrt(x)ln(x) where pi(x) is the prime counting function.

Refs:
• Unsolved Problems, Klee & Wagon, 1991, Sect 17
• Elementary Number Theory, Jones & Jones, 1998, Chap 9
• http://www.utm.edu/research/primes/notes/rh.html (notes in Chris Caldwell's Prime Pages)
• http://match.stanford.edu/rh/ (Dan Bump's notes)

Perfect & Mersenne Numbers

Def: n is perfect if it is equal to the sum of its divisors (except itself). Examples are 6=1+2+3, 28, 496, 8128, ...

Def: The nth Mersenne Number, M_n, is defined by M_n=2ⁿ-1.

Thm:

• M_n is prime implies that 2^n-1(2ⁿ-1) is perfect. (Euclid)
• All even perfect numbers are derived from Mersenne primes in this way. (Euler)

Conj: There are infinitely many Mersenne primes (equiv perfect numbers) and infinitely many Mersenne non-primes.

Conj: There are no odd perfect numbers.

The search for Mersenne primes is a hobby that anyone can participate in. Assistance, code and results are available from GIMPS (the Great Internet Mersenne Primes Search).

Refs:
• Unsolved Problems, Klee & Wagon, 1991, Sect 16
• Number Theory, Shanks, 1985, Chap 1
• Elementary Number Theory, Jones & Jones, 1998, Sects 2.3 & 8.2
• http://www.utm.edu/research/primes/mersenne.shtml (notes in Chris Caldwell's Prime Pages)

The Twin Primes Conjecture & Prime Gaps

Def: Twin primes are a pair of primes of the form {n, n+2}. Examples are {n, n+2} = {3, 5}, {5, 7}, {11, 13}, {17, 19}, {29, 31}, ...

Conj: There are an infinite number of twin primes.

Def: A prime gap is the difference p_i+1-p_i, where the p's are consecutive primes.

Various conjectures about the distribution of prime gaps are current. Tables of the earliest occurrence of each prime gap up to at least 804 have also been tabulated (and can be added to). There is also a distributed search for larger twin primes which has a page at http://www.serve.com/cnash/twinsearch.html.

Refs:
• Unsolved Problems, Klee & Wagon, 1991, Prob 16.1
• Number Theory, Shanks, 1985, pp30
• Unsolved Problems in Number Theory, Guy, 1994, Sect A.8
• The Book of Prime Number Records, Ribenboim, 1989, Sect 4.III
• Chris Caldwell's Prime Pages:
  • Prime Gaps
  • Twin Primes

Fermat Numbers

Def: The nth Fermat number, F_n, is defined is F_n=2^{2^n+1}.

Conj: Only a finite number of Fermat numbers are prime. A stronger conjecture is that the only prime Fermat numbers are F₀=3, F₁=5, F₂=17, F₃=257, and F₄=65537.

Refs:
• Number Theory, Shanks, 1985, Chap 2
• Unsolved Problems in Number Theory, Guy, 1994, Sect A.3
• The Book of Prime Number Records, Ribenboim, 1989, Sect 2.VI

Goldbach's Conjecture

Conj: n even and greater than or equal to 4 implies that there are primes a and b such that n=a+b.

Refs:
• Number Theory, Shanks, 1985, pp30
• Unsolved Problems in Number Theory, Guy, 1994, Sect C.1
• The Book of Prime Number Records, Ribenboim, 1989, Sect 4.VI
• Verifying Goldbach's Conjecture up to 4 x 10¹⁴

Catalan's Conjecture

Conj: The only consecutive prime powers are 8=2³ and 9=3².

Langevin and Tijdeman showed that any counterexamples must be smaller than exp(exp(exp(exp(730)))), so in theory it can be proved with a computation. This bound is so large that some major cutdown in possible counterexamples is still needed.

Refs:
• Unsolved Problems in Number Theory, Guy, 1994, Sect D.9
• Catalan's Conjecture, Ribenboim, 1994

Totient Function Conjectures

Def: Euler's totient function, phi(n) is the number of integers less than n which are coprime to n.

Conj: For no composite n does phi(n) divide (n-1). (Such a number would be a Carmichael number.) (Lehmer)

Conj: (Carmichael's Conjecture) For all m there is an n such that phi(m)=phi(n).

Def: The multiplicity of n is the number of integers k such that phi(k)=n.

Conj: All integers greater than 1 have occur as multiplicities. (Sierpinski)

Refs:
• Unsolved Problems in Number Theory, Guy, 1994, Sect B.37

The Collatz Problem

Consider the function f(x)=

• x/2 if x even
• 3x+1 if x odd}

Conj: For any integer n there is an integer d such that f^d(n)=1.

This conjecture is variously referred to as the Collatz problem (for the original worker in the field), the Syracuse problem, or the 3x+1 problem.

Refs:
• Unsolved Problems, Klee & Wagon, 1991, Prob 19
• Unsolved Problems in Number Theory, Guy, 1994, Sect E.16
• The 3x+1 Problem, 1985 paper by Jeff Lagarias, originally in MAA Monthly
• Notes by Eric Roosendaal