Lemoine's Conjecture

number-theory

Definition

Lemoine's Conjecture

The Lemoine conjecture states that every odd integer $n>5$ can be expressed as the sum of a prime number and twice a prime number:

$$\forall n\in 2\mathbb{N}+1,n>5⟹\exists p,q\in \mathbb{P}:n=p+2q$$

where $\mathbb{P}$ denotes the set of prime numbers.

Relation to the Halting Problem

Assume there exists an algorithm that decides the halting problem, i.e. given a program together with an input, it determines whether that program halts on that input.

Then one can write a program that searches for a counterexample to the Lemoine conjecture:

bool satisfiesLemoine(int n) {
	for all (p <= n, q <= n) {
		if (isPrime(p) and isPrime(q) and p + 2*q == n) {
			return true;
		}
	}
	return false;
}

void searchCounterexample() {
	n := 7;
	while (satisfiesLemoine(n) == true) {
		n := n + 2;
	}
}

The program searchCounterexample() halts if and only if there exists an odd integer $n>5$ that cannot be written as the sum of a prime number and twice a prime number. Therefore:

• if searchCounterexample() halts, then the Lemoine conjecture is false;
• if searchCounterexample() does not halt, then the Lemoine conjecture is true.

Hence, a decider for the halting problem would decide the Lemoine conjecture by checking whether this search program halts.

Limitation

Since the halting problem is undecidable, this does not yield an effective general decision procedure.