Unsolved Problems

Tim Roberts maintains the website http://www.unsolvedproblems.org/ in which he presents unsolved problems from mathematics, mostly conjectures that yet lack a formal proof. While working on these problems is fun, it may be useful to know that some problems might be unsolvable, so they are not worth the effort trying to solve them.

By means of formal logic we can show that some problems are probably unsolvable. If we can reformulate a statement to be of the type "there does not exist any n for which ...", it is probably unprovable. Examples:

Goldbach Conjecture

The Goldbach Conjecture states that every even number greater than 2 is the sum of two primes. A number is prime if it is divisible only by itself and 1. So, for example, 36 = 17+19.

This is equivalent to: For every integer n greater than 1, there is an integer k so that both n - k and n + k are prime numbers.

Employing the existential quantifier only, we can reformulate this to: There does not exist any integer n greater than 1 for which there does not exist an integer k so that both n - k and n + k are prime numbers. This can, if it is a false statement, easily be disproven, but it is probably impossible to prove.

Twin Primes Conjecture

The twin primes conjecture states that there are an infinite number of pairs of primes of the form 2n-1, 2n+1. That is, they differ by 2; for example, 41 and 43.

This is equivalent to: There does not exist any integer k which is larger than any pair of primes of the form 2n-1, 2n+1. "There does not exist any"... probably impossible to prove.

Collatz Conjecture

Take any positive integer: if the number is even, divide it by two; if the number is odd, triple it and add one (for example, if this operation is performed on 26, the result is 13; if it is performed on 5, the result is 16). Perform this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.

For example, starting at 11, the sequence goes 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

The Collatz conjecture is: this process will eventually reach the number 1, regardless of which positive integer is chosen initially.

This is equivalent to: There does not exist any integer n for which the given algorithm does not result in the number 1. Probably impossible to prove!

However, Fermat’s Last Theorem is also a conjecture of the "there does not exist any n for which ..." type, which should render it unprovable, but it has been proven.

So I do not claim that the problems which seem to be impossible to prove are unprovable indeed, but probably they are.

Claus Volko

Comments

Popular posts from this blog

Optimal IQ: A Speculative Model

Day of Wrath

Why I founded Prudentia