Simple to state and hard to solve…

Probably the most widely publicised mathematical result of the last few decades was Andrew Wiles’s proof of Fermat’s Last Theorem. What Wiles in fact proved was a far more significant result from which Fermat’s theorem follows, but what caught the public imagination was a result that could be stated in terms that a high-school maths student could understand, but that had resisted all attempts to solve it for over three centuries:

The equation x^n + y^n = z^n has no solutions for integers x, y, z, for any natural number n with n > 2.

How you feel about problems like this depends on your personality as a mathematician. Gauss is supposed to have said that Fermat’s problem was uninteresting since he could easily write down plenty of other “isolated statements” that were equally hard to prove but which didn’t have any great significance for the wider mathematical landscape. G. H. Hardy, writing about Goldbach’s conjecture, sniffed that “there are theorems… which have never been proved and which any fool could have guessed”.

For most of us, though, problems that are simple to state and desperately hard to solve have an enduring appeal — no matter how well we know we’re unlikely to make progress with them ourselves. Fortunately, the supply of these problems hasn’t run out. Here are a few of the ones that remain open…

Goldbach’s conjecture

Goldbach’s conjecture was first posed in a letter from Goldbach to Euler in 1742:

Any positive even number n \geq 4 can be expressed as the sum of two primes.

To date, this has been shown to be true for numbers n up to 12\times10^{17}, and most mathematicians would bet on it being true, but nobody’s found a way to prove it — although the heuristic evidence is pretty good, as the figure shows.

The number of ways to write an even number x as the sum of two primes. A counterexample to the conjecture would be a point on the x-axis.

There are a few partial results that nibble around the edges of the problem:

1. A theorem due to Schnirelman in 1939 shows that any n can be expressed as the sum of not more than 300 000 primes, so at least there is a bound.

2. A weaker conjecture is that any positive odd number n \geq 9 can be written as the sum of three primes. In 1937, Vinogradov showed that this is true for all “sufficiently large” values of n, and this upper bound has since been reduced further. In principle, this means that the weak conjecture could be proved by brute force by checking every number lower than the upper bound. However, Vinogradov’s original upper bound was 3^{3^{15} }\approx 3.25\times 10^{6846168}, while even the improved upper bound is roughly 3\times10^{43000} — so it’s unlikely that the problem will be solved by brute force any time soon!

3. There is also a variation called Levy’s conjecture, but sadly this doesn’t seem to be any easier to tackle than the original. Ho hum.

The twin prime conjecture

The twin prime conjecture has nothing whatsoever to do with these two. Phew.

The twin prime conjecture states that:

There are infinitely many numbers p such that both p and p+2 are prime.

This is another conjecture that just about everybody believes to be true, and there have been recent attempts to prove it, but so far they’ve been unsuccessful. The catch, as with Goldbach and so many other problems involving primes, is that “twinness” is a property connected with addition, while primality is a property connected with multiplication — this seems to be just about enough to make elementary approaches impossible.

There’s also evidence that the conjecture comes rather close to being false. It’s known (from Merten’s second theorem) that the sum of the reciprocals of the primes diverges:

\sum_{i=1}^n \dfrac{1}{p_i} \to \infty \quad \mbox{as} \quad n \to \infty,

where p_i is the ith prime number. However, Brun’s theorem states that Brun’s constant B is finite, where

B = \sum_{i=1}^{\infty} \dfrac{1}{p_i} where the sum is over twin primes only.

This shows that as i increases, twin primes must become scarce rather more rapidly than the primes themselves do.

Surprisingly, although the twin prime conjecture has resisted attack, some other results concerning equally spaced primes have been proved. A notable recent result is the Green–Tao theorem (proved in 2004), which states that for any k, there exists an arithmetic sequence of k primes. Unfortunately this theorem isn’t constructive, so although we know that (for example), a sequence of 1729 equally spaced primes exists, we have no way at present to find it. The current record seems to be the sequence

43 142 746 595 714 191 + 23 681 770\times 223 092 870\times n,

which produces primes for n = 0 \ \hbox{to} \ 25. A generalisation of this, due to Erdős (who else?) is still open…

The Collatz conjecture

The Collatz problem was first posed in 1937.

Start with any positive integer a_0 and construct a sequence a_i as follows. If a_{n-1} is even, then a_n = \dfrac{1}{2}a_{n-1}. If a_{n-1} is odd, then a_n = 3a_{n-1}+1. The conjecture states that the sequence a_i will eventually reach 1.

It’s very easy to verify for yourself that for small values of a_0 the conjecture holds. For example, if a_0=7 then the sequence is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, and after this point the cycle 4, 2, 1 repeats indefinitely. Brute-force checking has shown that it holds for all a_0 \leq 19\times 2^{58}, and there are lower bounds on the length of any repeating cycle that doesn’t reach 1; but generally this problem is still wide open. Erdős’s rather sad conclusion was simply that “mathematics is not yet ready for such problems”. Boo.

Working backwards: all the numbers that lie within 20 iterations of 1.

Irrationality problems

The proof that \sqrt{2} is irrational (that is, that it can’t be written in the form p/q for integers p and q) is well known and elegant, even if its originator did get drowned for causing trouble as some stories claim. Surprisingly, it wasn’t until the 18th century that two of our other favourite numbers were shown to be irrational: the irrationality of \pi was proved by Lambert in 1760, while e was proved irrational by Euler in 1737. There are some surprisingly simple numbers which haven’t yet been shown to be rational or irrational: in particular, it hasn’t yet been shown for 2^e, \pi^e or \pi^{\sqrt{2}}.

A powerful result called Gelfond’s theorem allows us to clear up some examples: it states that a^b is transcendental, and thus irrational, if a is an algebraic number not equal to 0 or 1 and b is both algebraic and irrational. We can, for example, use this to show that 2^{\sqrt{2}} is irrational.

There’s also a nice indirect proof that it’s possible to raise an irrational number to an irrational power, and get a rational number as a result. Consider the number x = \sqrt{2}^{\sqrt{2}}. If x is rational, we’re done. On the other hand, if x is irrational, consider

x^{\sqrt{2}} = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2}\sqrt{2}} = \sqrt{2}^2 = 2

and since 2 is rational, we’re done. (A little self-test: what does Gelfond’s theorem say about the irrationality of x?)

And more…

Eric Weisstein’s World of Mathematics site has a nice list of unsolved problems, including those described above. Many of them are more “significant” than the ones we’ve looked at here, and also rather harder to state, but they’re worth visiting even just to gawp at them as a mathematical tourist. Have fun — and if you manage to prove any of these conjectures, do let me know. (In the words of Stefan Bergman, “let’s make it a joint paper, and I’ll write the next one”…)


This entry was posted in Articles. Bookmark the permalink.

One Response to Simple to state and hard to solve…

  1. Pingback: Not quite Goldbach but… | Degree of Freedom

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.