# David Madore's WebLog: Math is hard

(Friday)

## Math is hard

One of the reason I didn't study computer science is that it is a pit of despair: as far as practical problems are concerned, nobody has yet come up with a programming language that is really usable (so everyone writes stuff in C, which is the moral equivalent of writing in English in iambic pentameters without the letter ‘e’—that is, sheer masochism—,or C++, which is worse; and high-level languages simply don't work); as for theoretical problems, they are sitting in a kind of limbo between mathematics and theology. Anyway.

But math is also a source of despair, when one reflects on how little one can prove and how many simple questions are left open and probably will remain so for a long time.

It is easy to concoct a math problem which is understandable by anyone and which is probably bound to remain unsolved for a really long time. Perhaps the simplest example is the so-called Syracuse problem (on the Collatz sequence), namely: start with a positive integer n, and, so long as it is not equal to 1, repeat the following: if it is even, divide it by two, and if it is odd, multiply it by three and add one (for example: 7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1); the conjecture states that, whatever the starting integer, the sequence will eventually reach 1 (after which it would go into the loop 1 → 4 → 2 → 1 if it is continued; the question is essentially whether there exist other loops than that which starts from 1). It has been verified experimentally for a huge number of starting values, but so far as I know, nobody has been able to come up with a proof (or, at least, a published proof which has passed peer-review: because there are certainly hundreds of crackpot-generated proofs on the Web). Of course, nobody (almost no real mathematician, I mean) is seriously interested in this particular problem, so it isn't a surprise that no progress is being made; all the same, it is probably a very hard problem.

Here's one, however, that is of much greater theoretical interest, which is “probably not false” (as I heard Swinnerton-Dyer call it), and which is hopelessly out of reach of the present techniques of mathematics. Let F1,…,Fk be k polynomials (in one variable x) with integer coefficients and positive leading coefficient, and assume the product F1·…·Fk of all the Fi is not constantly divisible by some prime p (for example, x²+x is always even—assume that sort of thing doesn't happen): then [the conjecture states that] there are infinitely many integer values of x such that the Fi(x) are all simultaneously prime. This is called Schinzel's (H) hypothesis (or sometimes the Schinzel-Sierpiński hypothesis). Even in the simple case where one takes the two polynomials x and x+2, the Schinzel hypothesis implies the twin primes conjecture, which is far from proven. Similarly, Schinzel's hypothesis implies that there are infinitely many primes of the form 6q²+1 where q itself is prime, and many other things of the same form.

Here is another conjecture, which is about of the order of difficulty of Schinzel's hypothesis (i.e., probably not false, but unattainable): assume t1,…,tr are r complex numbers that are linearly independent over the rationals, meaning that if c1,…,cr are r rationals such that c1·t1 + … + cr·tr = 0, then all the ci are zero (for example, 1, √2 and 2iπ are linearly independent over the rationals); then [the conjecture states that] out of the 2r complex numbers t1,…,tr,et1,…etr (in other words, add the exponentials of the ti to the list), there are at least r which are algebraically independent (over the rationals), meaning that if some polynomial with rational coefficients in r variables vanishes when applied to the r quantities in question, the polynomial is identically zero. This is known as Schanuel's conjecture. If applied in the particular case of 1, √2 and 2iπ, Schanuel's conjecture implies that the three quantities e, e√2 and π are algebraically independent, which in turn implies the transcendence of such quantities as e+π which is still an open problem. Schanuel's conjecture is a kind of holy grail in transcendental number theory.

In comparison to Schinzel's hypothesis or Schanuel's conjecture, the seven problems whose head is at stake for \$1000000 are presumably quite easy (in fact, at least one—namely the Poincaré conjecture—can now be considered as good as solved, thanks to Perelman).

It is not unthinkable that these problems should be undecidable; however, the tools available for proving the undecidability of a mathematical statement are even more inadequate, in this case, than those that might attempt to prove the statement… (I let those with some knowledge in logic reflect upon what happens when one iterates the construction is undecidable to transfinite heights).