What are the obstructions to showing that $\zeta$ doesn't vanish on the strip $1- \varepsilon < {\rm Re}(s) \leq 1$ Most (if not all) of the proofs of the Prime Number Theorem that I have seen in the
literature rely on the fact that the Riemann zeta function, $\zeta(s)$, does not vanish
on the line ${\rm Re}(s) = 1$.  Since we have a lot of numerical evidence for the validity of RH, one would suspect that for small $\varepsilon$ (to start with) we have that $\zeta(s) \neq 0$ on the strip $1- \varepsilon < {\rm Re}(s) \leq 1$.  Does anyone know what are the main difficulties for proving such a result?
 A: The answer above by KConrad above gives a very good 'big picture' explanation.  I can think of three different 'nuts and bolts'  explanations, which might be of interest. 
The first looks at the classical proof that $\zeta(s)\ne 0$ on $\text{Re}(s)=1$, and investigates what fails when one tries to extend the proof to $\text{Re}(s)=\beta<1$.  Plagarizing myself shamelessly:
"This deep result begins with the trivial trig identity that for any angle $\theta$,
$$
3+4\cos(\theta)+\cos(2\theta)=2(1+\cos(\theta))^2\ge0.
$$
We  make use of this in the series expansion for $\text{Re}(\log(\zeta(s)))$:
$$
\text{Re}(\log(\prod_p(1-p^{-s})^{-1})))=\text{Re}(\sum_p\sum_{k=1}^\infty\frac{1}{k}p^{-ks})
=\sum_p\sum_{k=1}^\infty\frac{1}{k}p^{-k\sigma}\cos(kt\log(p)).
$$
We apply this to $\zeta(1+\epsilon)$, to $\zeta(1+\epsilon+it)$ and to $\zeta(1+\epsilon+2it)$ and take the following clever linear combination
$$
3\text{Re}(\log(\zeta(1+\epsilon)))+4\text{Re}\log(\zeta(1+\epsilon+it)))+\text{Re}(\log(\zeta(1+\epsilon+2it)))
$$
which is equal
$$
\sum_p\sum_{k=1}^\infty\frac{1}{k}p^{-k(1+\epsilon)}\left(3+4\cos(kt\log(p))+\cos(k2t\log(p))\right).
$$
By the trig identity this mess is $\ge 0$.  But  properties of the complex logarithm  imply the left side is actually
$$
3\log(|\zeta(1+\epsilon)|)+4\log(|\zeta(1+\epsilon+it)|)+\log(|\zeta(1+\epsilon+2it)|).
$$
So when we exponentiate,
$$
|\zeta(1+\epsilon)|^3|\zeta(1+\epsilon+it)|^4|\zeta(1+\epsilon+2it)|\ge 1.
$$
So far we have not assumed anything about $t$.   But now suppose $t$ is the imaginary part of a zero of the form $1+i\gamma$.  Then a Taylor series
expansion at $1+i\gamma$ has no constant term
$$
\zeta(1+\epsilon+i\gamma)=O(\epsilon)\quad\text{ as }\epsilon\to 0\quad\text{ so }\quad
\zeta(1+\epsilon+i\gamma)^4=O(\epsilon^4).
$$
Meanwhile, 
$$
\zeta(1+\epsilon)=\frac{1}{\epsilon}+O(1)\quad\text{ so }\quad
\zeta(1+\epsilon)^3=\frac{1}{\epsilon^3}+O(\epsilon^{-2}).
$$
And since $\zeta(s)$ has no poles except at $s=1$, 
$$
\zeta(1+\epsilon+2it)=O(1).
$$
Combining these, we see that
$$
\zeta(1+\epsilon)^3\zeta(1+\epsilon+it)^4\zeta(1+\epsilon+2it)=O(\epsilon)
$$
goes to zero as $\epsilon\to 0$, which contradicts the fact that the absolute value must be $\ge 1$."
What is the obstruction to doing this with a zero $\rho=\beta+i\gamma$ with $\beta<1$?  Could one still consider the three points $\beta+\epsilon$, $\beta+\epsilon+i\gamma$, and $\beta+\epsilon+i2\gamma$, and apply the trig identity?  
In fact, the classic proof depends on the fact that $\zeta(s)\ne0$ for $\text{Re}(s)>1$, in order that $\log(\zeta(s))$ be well defined.  Note how the proof above dodged any mention of this subtlety.  The fact that we have a convergent Euler product for $\text{Re}(s)>1$ means, by some graduate level complex analysis, that $\zeta(s)$ is nonzero in this region.  (A low tech proof adapted from Titchmarsh, can be found at https://math.stackexchange.com/questions/265289/question-about-riemann-zetas-function-zeroes/272963#272963)  
So we're in kind of a chicken and egg situation.  To adapt this to show that $\beta+i\gamma$ is not a zero, we would need to know that there are no zeros to the right of $\beta+i2\gamma$.  If you have ideas to get around this, ask yourself how you would avoid proving there's no zeros with real part $\beta=1/2$, which we know do, in fact exist.
A: For a second approach, we could look at what is known about zeros of $\zeta(s)$ to the right of a vertical line $\text{Re}(s)=\sigma_0$.  These are known as 'zero density results' and  take the form of a bound on the number of such zeros to height $T$.
(See this question, for example: Zeta Function: Zero Density Theorems.)
I'll need to explain a lot just for the setup, and it will be clear there's no hope of getting a zero free region this way, but that's kind of the point.
We start with Littlewood's Lemma (Titchmarsh S. 9.9 p.220, specialized to the situation at hand.)  Since $\zeta(s)$ is nonzero on $\text{Re}(s)=2$, we can define $\log(\zeta(s))$ inside the rectangle $R$ bounded by $t=0$, $t=T$, $\sigma=\sigma_0$, and $\sigma=2$ by choosing any branch along the line $\sigma=2$, and by continuous variation along the line $t=\text{const.}$ from $2+it$ to $\sigma_0+it$ as long as the path does not cross a zero of $\zeta(s)$; if it does we use limiting value as $\epsilon\to 0$ of $\log(\zeta(\sigma+it+i\epsilon))$.  Let $N(\sigma^\prime,T)$ denote the number of zeros of $\zeta(s)$ in the part of the rectangle with $\sigma>\sigma^\prime)$.  Littlewood shows that
$$
\int_{\partial R}\log(\zeta(s))\, ds=-2\pi i\int_{\sigma_0}^2 N(\sigma,T)\, d\sigma.
$$
The key fact is that the two vertical sides of the rectangle contribute
$$
\int_0^T\log(\zeta(2+it))-\log(\zeta(\sigma_0+it)) idt=\int_0^T\left(\int_{\sigma_0}^2\frac{\zeta^\prime(\sigma+it)}{\zeta(\sigma+it)}d\sigma\right)idt.
$$
Changing the order of integration and using the Residue Theorem gives the lemma.  
Note the right side of Littlewood's Lemma is purely imaginary, only the imaginary part of the line integral on the left contributes.  So we can say
$$
2\pi\int_{\sigma_0}^2N(\sigma,T)d\sigma=-\text{Im}\left(\int_{\partial R}\log(\zeta(s))\, ds\right).
$$
The easiest, weakest zero density result gives that
$$
N(\sigma_0,T)\ll T.
$$
The proof is in two stages; the first  stage is to bound the line integral in Littlewood's Lemma.

It's worth noting that to get $N(\sigma_0,T)=0$, we would need to show this integral is $0$, which seems out of reach.  There's no apparent symmetry here to make it obviously $0$.

Separating out the four sides of the rectangle $\partial R$, and using some bounds on $\arg(\zeta(s))$ (omitted) one can show the left side of the rectangle is the main term, so
$$
2\pi\int_{\sigma_0}^2N(\sigma,T)d\sigma=\int_0^T\log|\zeta(\sigma_0+it)|dt +O(\log(T)).
$$
An important convexity inequality for non-negative continuous functions $f(t)$ is that
$$
\frac{1}{b-a}\int_a^b\log f(t)dt\le \log\left(\frac{1}{b-a}\int_a^b f(t)dt\right),
$$
which means (taking $a=0$ and $b=T$)  that
$$
\frac{1}{2}\int_0^T\log|\zeta(\sigma_0+it)|^2dt\le \frac{T}{2}\log\left(\frac{1}{T}\int_0^T|\zeta(\sigma_0+it)|^2dt\right)\ll T,
$$
the latter bound again following from some omitted results on $\zeta(s)$.
Having bounded the integral, we next let $\sigma_0^\prime=(\sigma_0+1/2)/2$.  Since $N(\sigma,T)$ is a decreasing function of $\sigma$, we have that
$$
N(\sigma_0,T)\le\frac{1}{\sigma_0-\sigma_0^\prime}\int_{\sigma_0^\prime}^{\sigma_0}N(\sigma,T)dt\le \frac{1}{\sigma_0-\sigma_0^\prime}\int_{\sigma_0^\prime}^2N(\sigma,T)dt\ll T.
$$
Edit:
Although this estimate allows up to order $T$ zeros at height $T$, the total number of zeros at this height is asymptotic to $T/(2\pi)\log(T/2\pi)$, so the proportion to the right of $\text{Re}(s)=\sigma$ must tend to $0$ as $T\to\infty$.  The real strength of the theorem is that (except for the implied constant) this result is independent of $\sigma$.  But this also argues for the difficulty of getting a zero free region via this approach:  any such would seem to give you the full Riemann Hypothesis.
A: As long as a result remains unproved it can be pure speculation about whether it is really hard or just nobody has found the right simple idea, though in this case it seems plausible that the desired nonvanishing is going to be require a profound new idea. (For more on the task of deciding if a problem is hard before it has been solved, look at the answers to the question https://math.stackexchange.com/questions/88709/complex-math-problem-that-is-easy-to-solve.) That the substantial numerical evidence behind RH should somehow be related to mathematicians being able to establish a uniform zero-free strip $1-\varepsilon < {\rm Re}(s) \leq 1$ is sort of like living in a dream world: mere numerical evidence in this case doesn't suggest any idea of how to create a zero-free vertical strip. It doesn't even suggest how to create a zero-free vertical line: look at any proof that $\zeta(s) \not= 0$ on the line ${\rm Re}(s) = 1$ and tell us how numerical data would lead you to such a proof!
If I had to give one simple reason that it's not (apparently) easy to construct a zero-free vertical strip, I'd say it's because the line ${\rm Re}(s) = 1$ is not compact. That is, although we know $\zeta(s) \not= 0$ on ${\rm Re}(s) = 1$, it doesn't immediately follow that $\zeta(s) \not= 0$ on a uniform strip $1-\varepsilon < {\rm Re}(s) \leq 1$ because the line ${\rm Re}(s) = 1$ is not compact.
To see why lack of compactness is relevant, consider the analogues of $\zeta(s)$  defined over finite fields. (Their values are complex, but the data used to construct them relies on geometry in characteristic $p$.) They are power series in $p^{-s}$ where $p$ is the characteristic of the finite field and ${\rm Re}(s) > 1$, and they are in fact rational functions in $p^{-s}$, which provides a meromorphic continuation to $\mathbf C$. Being series in $p^{-s}$, these zeta-functions are periodic in $s$ with period $2\pi{i}/\log p$ and therefore they can be regarded equivalently as power series in the variable $z = p^{-s}$.  In the $z$-world, the line ${\rm Re}(s) = 1$ corresponds to the circle $|z| = 1/p$ and the right half-plane ${\rm Re}(s) \geq 1$ corresponds to the disc $|z| \leq 1/p$. (It really corresponds to the punctured disc $0 < |z| \leq 1/p$, but we can fill in the value of the function at the origin using its  constant term.) Any circle $|z| = r$ or disc $|z| \leq r$ is compact, so a continuous function on ${\mathbf C}$ that is nonvanishing on $|z| \leq r$ is necessarily nonvanishing on $|z| \leq r+\varepsilon$ for some $\varepsilon > 0$.  That extra uniformly larger disc  translates back in the $s$-world into an added uniform strip where the function is nonvanishing.  
Returning to $\zeta(s)$, since it is nonvanishing on the line ${\rm Re}(s) = 1$ there must be some open set containing that line where $\zeta(s)$ is nonvanishing, but there's no reason you can deduce without some new idea that this open set containing ${\rm Re}(s) = 1$ must contain a strip $1 - \varepsilon < {\rm Re}(s) \leq 1$ for some $\varepsilon > 0$. If ${\rm Re}(s) = 1$ were compact then that deduction would be easy: all open sets containing that line would contain such a strip. (You could make the same argument using the closed half-plane ${\rm Re}(s) \geq 1$ in place of the line ${\rm Re}(s) = 1$: an open set containing ${\rm Re}(s) \geq 1$ doesn't have to contain a half-plane ${\rm Re}(s) > 1-\varepsilon$ for some $\varepsilon > 0$, although it would if ${\rm Re}(s) \geq 1$ were compact.)
Here's another reason that the existence of zero-free vertical strips will probably be hard to prove: there are Dirichlet series that look similar to the $\zeta$-function (e.g., they converge on ${\rm Re}(s) > 1$ and have an analytic continuation and  functional equation of a similar type) but they have lots of zeros to the right of the critical line, and can even have zeros in the half-plane ${\rm Re}(s) > 1$. These examples are called Epstein zeta-functions, and unlike $\zeta(s)$ they do not have any known Euler product. Somehow the Euler product for $\zeta(s)$ is probably going to play a crucial role in making progress on an understanding of its zero-free vertical regions.
A: The third approach looks at a known zero free region. The simplest such theorem is that there is some $A$ such that
$$
\zeta(s)\ne0\quad\text{for}\quad \sigma>1-A/\log(t).
$$
What prevents us from 'straightening it out' so the  boundary is a vertical line?
The proof begins like the proof that $\zeta(1+it)\ne0$ (see previous answer), but considers instead of $\log(\zeta(s))$, rather $\log(\zeta(s))^\prime=\zeta^\prime(s)/\zeta(s)$, again expanded as a sum over primes.  For $\sigma>1$, and any $t$, taking real parts and using the same trig identity shows that
$$
0\le -3\frac{\zeta^\prime}{\zeta}(\sigma)-4\text{Re} \frac{\zeta^\prime}{\zeta}(\sigma+it)-\text{Re}\frac{\zeta^\prime}{\zeta}(\sigma+2it).
$$
We will estimate each of the three terms on the left side.  The first is easy:
$$
-3\frac{\zeta^\prime}{\zeta}(\sigma)=\frac{3}{\sigma-1}-3C+O(\sigma-1)<\frac{3}{\sigma-1},
$$
where $C$ is the Euler constant.
For the other two, we need the expression of $\zeta(s)$ as a product over nontrivial zeros $\rho=\beta+i\gamma$.  Taking logarithmic derivatives gives
$$
-\frac{\zeta^\prime(s)}{\zeta(s)}=-\log(2\pi)+1+C+\frac{1}{s-1}+\frac12\frac{\Gamma^\prime(s/2+1)}{\Gamma(s/2+1)}-\sum_\rho\left(\frac{1}{s-\rho}+\frac{1}{\rho}\right).
$$
Via Stirling's formula, for $s\to\infty$ in a vertical strip
$$
\frac{\Gamma^\prime(s)}{\Gamma(s)}\sim \log(s)\sim\log(t).
$$
This is where the $\log(t)$ in our zero free region will come from, but so far
$$
-\frac{\zeta^\prime(s)}{\zeta(s)}+\sum_\rho\left(\frac{1}{s-\rho}+\frac{1}{\rho}\right)\sim\frac12\log(t/2).
$$
Taking real parts, the asymptotic relation above gives that
$$
-\text{Re}\frac{\zeta^\prime(s)}{\zeta(s)}+\sum_\rho\left(\frac{\sigma-\beta}{(\sigma-\beta)^2+(t-\gamma)^2}+\frac{\beta}{\beta^2+\gamma^2}\right)<\log(t).
$$
Recalling that $\sigma>1$, every term in the sum over $\rho$ is positive, so we estimate the last of our three terms as
$$
-\text{Re}\frac{\zeta^\prime(\sigma+2it)}{\zeta(\sigma+2it)}<\log(2t).
$$
To get  a zero free region, we now fix a zero $\rho_0=\beta_0+i\gamma_0$, and set $t=\gamma_0$ in the $s$ parameter.  In estimating the middle of our three terms, we drop every term in the sum except that corresponding to $\rho=\rho_0$. This gives
$$
-4\text{Re}\frac{\zeta^\prime(\sigma+i\gamma_0)}{\zeta(\sigma+i\gamma_0)}<4\log(\gamma_0)-\frac{4}{\sigma-\beta_0}.
$$
Combining the three estimates, we now have
$$
0\le \frac{3}{\sigma-1}+4\log(\gamma_0)-\frac{4}{\sigma-\beta_0}+\log(2\gamma_0)\le\frac{3}{\sigma-1}-\frac{4}{\sigma-\beta_0}+5\log(\gamma_0).
$$
Thus
$$
\frac{3}{\sigma-1}+5\log(\gamma_0)\ge \frac{4}{\sigma-\beta_0}
$$
$$
\sigma-\beta_0\ge \frac{4(\sigma-1)}{3+5(\sigma-1)\log(\gamma_0)},
$$
and
$$
1-\beta_0\ge \frac{4(\sigma-1)}{3+5(\sigma-1)\log(\gamma_0)}+1-\sigma.
$$
Finally setting the parameter $\sigma=1+1/(10\log(\gamma_0))$, the right side of the inequality simplifies and we obtain
$$
1-\beta_0\ge\frac{1}{70\log(\gamma_0)}.
$$

How might we do better?  As mentioned above, the $\log(t)$ arises from the contribution of the logarithmic derivative of the $\Gamma$ function.  Except for the factor of $1/2$ we dropped, this is the best estimate possible.  But we lost a lot by first introducing all the zeros of $\zeta(s)$, and then throwing out all but one.  A better zero free region may be obtained by subtracting off from the logarithmic derivative only the contribution of the nearby zeros.  The best known bounds replace $1/\log(t)$ with $1/(\log(t)^{2/3}\log\log(t)^{1/3})$.
