# Why are conjectures about the primes so hard to prove?

I recently started learning number theory, and I've noticed there are many conjectures about the prime numbers that are unproven. Some examples would be whether there are infinite Mersenne, Sophie-Germain, or Fermat primes. There are also problems like the Goldbach conjecture. Yet, primes are defined so simply. Why are they so hard to work with? I am very new to number theory, so I am looking for a simple, intuitive answer.

-
You didn't even mention twin prime conjecture. –  Tim Ratigan Dec 22 '13 at 22:25
One of the problems with these questions about primes is that primes are defined purely in terms of multiplication, but Goldbach and Twin Primes depend on addition. Not sure if my intuition is perfectly valid here, but the only axiom connecting multiplication and addition in this context is the distributive law, and that is not a great lever for attacking problems of such depth. –  Old John Dec 22 '13 at 22:29
they're not really defined simply. They are defined as not being divisible by an infinite set of other numbers. This becomes finite once you point out that a divisor must be smaller in absolute value than the original number, but still. –  Will Jagy Dec 22 '13 at 22:30
I'm with @OldJohn - combining multiplication and addition is surprisingly complicated –  Mark Bennet Dec 22 '13 at 22:31
If those things were not hard to prove, they won't be conjectures anymore ... –  Hagen von Eitzen Dec 22 '13 at 22:45

The prime numbers are an odd set of numbers.

The crux of the problem lies in the following fact:

the function $P(n)$ that outputs the n'th prime is still only known to be defined using the idea "the nth prime is not divisible by any primes below it" and "the first prime is 2". This sort of definition means any question involving prime numbers cannot be solved easily. An example is the twin prime conjecture. The question quite simply asks:

are there infinitely many n such that

$$P(n) - P(n-1) = 2?$$

If we had a non-recursive (ie an explicit formula no matter how complicated) for describing the function then suddenly many many tools like calculus (think Newton's Method), functional analysis, theory of solvability of equations etc... can be used to tackle this problem.

But WE DONT HAVE AN EXPLICIT DEFINITION.

So all of that goes out the door and is essentially what makes Number Theory so brutally challenging yet so wonderfully rewarding.

-
I heard that there are explicit formulas for the nth prime, is this not true? –  user117301 Dec 22 '13 at 22:42
@user117301 Not any useful ones. There are formulas like Mills' formula but these require putting in more knowledge about the distribution of the primes than you get out. –  user7530 Dec 22 '13 at 22:46
@user117301 there is no reason to believe its impossible but it will be extremely hard since so many have already failed to characterize it. A lot more work needs to be done to understand the distribution of the primes (Example: Riemann Hypothesis, and others...) before such a function can be constructed. –  frogeyedpeas Dec 22 '13 at 22:56
Or simply someone with Ramanujan-esque intuition. –  frogeyedpeas Dec 22 '13 at 22:58
@frogeyedpeas I agree that problems would be easier to solve if $P(n)$ were known explicitly - but your answer suggests the inverse, that the problem is hard to solve because $P(n)$ is not known explicitly, and that's the assessment that I'm disagreeing with. (That said, I want to emphasize that the downvote isn't mine; I don't think this answer is -that- bad!) –  Steven Stadnicki Dec 22 '13 at 23:22

Here's a brief, vague, and incomplete answer but one that relates to many open problems (and both the Goldbach and Twin Prime conjectures): primality is a multiplicative condition, not an additive one. Understanding how they are distributed in an arithmetic sequence (e.g. in the natural numbers or for use in problems involving prime gaps (roughly what's needed in the above two conjectures)) is attempting to understand how the notion of primality relates to something defined in terms of addition, and there's no obvious way to understand the definition of a prime number in terms of addition.

Edit: I just noticed that this was already mentioned in the comments but may as well leave it here. frogeyedpeas's answer brings up another very good point.

-
I've often wondered about this: how much of number theory can be carried over to rings $R$ that are isomorphic to $\mathbb{Z}$ as multiplicative monoids, but have different additive structure? –  user7530 Dec 22 '13 at 22:41
@user7530 It is probably possible to classify such rings. Immediately it is seen that such a ring must be commutative, unital, and be a domain, with characteristic either $0$ or $3$. –  anon Dec 22 '13 at 22:53

I'm surprised that the other answers have not touched on the distribution of prime numbers. It is well-known that $\pi(n)$, or the number of primes $p\le n$, is asymptotic to $\int_2^n\frac1{\log x}\text dx\approx\frac{n}{\log n}$, which turns out to be a decent approximation. This leads us to believe through probabilistic models that primes are randomly distributed across the natural numbers. This heuristic tends to be extremely accurate when describing properties of primes, including very good predictions on how many twin primes there should be before a given $n$. Terence Tao has a lot of literature on this directed toward the layman.

In short, primes behave pseudorandomly and this makes them difficult to work with in a rigorous sense.

-
You say this is derived by assuming the primes are randomly distributed. What grounds are there for this assumption? –  user117301 Dec 22 '13 at 22:57
As I understand it, it is the other way around: one uses the numerical prediction of the prime number theorem to create a probabilistic model of the primes (a sum of random variables taking value $1$ with probability $1/\log n$ and $0$ otherwise) which is then used to predict more complicated behavior heuristically. To answer the above comment, the grounds for using the heuristic is that it is intuitive and often works, if it's augmented or adapted cleverly enough in each situation. –  anon Dec 22 '13 at 23:00
This relates to back to my point where $\pi^{-1}(n) = p(n)$ we do indeed have an asymptotic formula but it has unknown additive accuracy (the difference between the formula and actual values is very complex) and therefore doesn't allow us to algebraically attack problems like the twin prime conjecture. Still this is an important development which suggests the problem isn't impossibly difficult and that we know a thing or two about the structure of the function. –  frogeyedpeas Dec 22 '13 at 23:02