Examples of notably long or difficult proofs that only improve upon existing results by a small amount I was recently reading Bui, Conrey and Young's 2011 paper "More than 41% of the zeros of the zeta function are on the critical line", in which they improve the lower bound on the proportion of zeros on the critical line of the Riemann $\zeta$-function. In order to achieve this, they define the (monstrous) mollifier:
$$
\psi=\sum_{n\leq y_1}\frac{\mu(n)P_1[n]n^{\sigma_0-\frac{1}{2}}}{n^s}+\chi(s+\frac{1}{2}-\sigma_0)\sum_{hk\leq y_2}\frac{\mu_2(h)h^{\sigma_0-\frac{1}{2}}k^{\frac{1}{2}-\sigma_0}}{h^sk^{1-s}}P_2(hk).
$$
This is followed by a nearly 20-page tour-de-force of grueling analytic number theory, coming to a grinding halt by improving the already known bounds from $40.88\%$ to... $41.05\%$.
Of course any improvement of this lower bound is a highly important achievement, and the methods and techniques used in the paper are deeply inspirational. However, given the highly complex nature of the proof and the small margin of improvement obtained over already existing results, I was inspired to ask the following question: 
What are other examples of notably long or difficult proofs that only improve upon existing results by a small amount?
 A: This 28-page paper by Le Gall lowers the best-known estimate for the asymptotic complexity of matrix multiplication from $O(n^{2.3728642})$ to $O(n^{2.3728639})$, a reduction by 0.00001%. However, it simplifies the previous method, so it does not really qualify as "notably long or difficult proof". Maybe this definition applies more to the previous improvement in a 73-page paper by Vassilevska-Williams, which brought down the exponent from $O(n^{2.374})$ to $O(n^{2.3728642})$
A: In the context of the Millenium problem for the Navier-Stokes equations, there is a long history of results along the lines of "if global regularity fails, then such and such norm has to blow up." There are numerous results on minimal improvements in the specification of "such and such." Of course, no one knows at this point whether any norm really blows up or not.
A: Almost any paper on the Gauss Circle Problem written in the last 70 years qualifies.
A: Here is another realm where improvements are small and tend towards an unknown but existing limit $S$ with currently known bounds $1.2748 ≤ S ≤ 1.5098$ where the upper bound seems not too far from the actual value of $S$.  
It is about the smallest possible supremum of the autoconvolution of a nonnegative function supported in a compact interval. The discrete version of those (i.e. restricting to functions that are piecewise constant) yields optimal functions which are closely related to Generalized Sidon sets.
A fascinating article is Improved bounds on the supremum of autoconvolutions. As a teaser, have a look at the diagram on page 10.
If the condition "nonnegative" on the function is removed, surprisingly the new supremum may be even smaller.
A: The following example is described in The Man Who Loved Only Numbers by Paul Hoffman. 
There is a reasonably short proof, found by Esther Klein (later Szekeres) in 1932, that given 5 points in the plane, there exist 4 of them that form a convex quadrilateral. The minimum number of points needed such that there always exists 5-element subset forming a convex pentagon is 9. There is a conjecture that the minimum number of points needed such that there exists an $n$-element subset forming a convex $n$-gon is $2^{n-2} + 1$. It is known it has to be at least that. This is called the "Happy Ending Problem" (apparently because George Szekeres had impressed Esther so much with his proof that there is a minimum finite number for each $n$ that he won her hand in marriage). 
For the case $n = 6$, the best that Erdős achieved was 71 points, a somewhat distant cry from the conjectured 17. This was sometime in the 1930's. After the memorial service for Erdős in 1996, Ronald Graham and his wife Fan Chung thought it was high time that someone have another crack at it, after 60 years -- and were very excited that during a long flight to New Zealand, they managed to lower it down by just a single point, to 70. This required introducing new ideas. 
(As Graham explains, Kleitman and Pachner soon lowered it further to 65. There were subsequent further improvements until finally George Szekeres and his collaborator Peters reached 17, with the help of computers, in a paper published in 2006.) 
A: The De Bruijn-Newman constant $\Lambda$ was defined and upper bounded by $\Lambda \leq 1/2$ in 1950. After 58 years of work, in 2008 this upper bound was finally improved to ... $\Lambda < 1/2$ (a 0% improvement) in a 26-page paper. The best known upper bound is currently $\Lambda \leq 0.22$. The Riemann hypothesis is equivalent to $\Lambda = 0$, so if it's true then we've got quite a ways to go.
A: Recently Konyagin and Shkredov improved the exponent of $4/3$ in the sum-products estimate in $\mathbb{R}$, namely that $|A+A|+|A\cdot A|\gg |A|^{4/3-o(1)}$ for every $A\subset \mathbb{R}$, to $4/3+5/9813$. This appears to be much harder than the short proof for $4/3-o(1)$ by Solymosi. 
The conjecture of Erdős is that the exponent approaches 2.
A: One example could be the sphere packing problem in $\mathbb{R}^8$, recently finished by Viazovska. It was a well-known conjecture that $E_8$-lattice packing gives the maximum density for sphere packings in $\mathbb{R}^8$. In 2003, Cohn and Elkies have shown using linear programming that the optimal density is less or equal to 1.000001 times the density of $E_8$ packing. Viazovska's paper finally removed this 1.000001 factor. While I would not call her paper very long, it definitely has some highly non-trivial ideas in it (the appearance of modular forms is pretty surprising to me, for example). 
A: The Dirichlet divisor problem has a history of such minor improvements, each with progressively longer proof. The problem asks for possible exponents $\theta$ for which we have $\sum_{n\leq x}d(n)=x\log x+(2\gamma-1)x+O(x^\theta)$, where $d$ is the divisor-counting function. It is known $\theta<\frac{1}{4}$ can't work, and it's conjectured any $\theta>\frac{1}{4}$ does.
Progress towards showing this has been rather slow: Dirichlet has shown $\theta=\frac{1}{2}$ works, Voronoi has improved it to $\theta>\frac{1}{3}$ and since then we had around a dozen of papers, each more difficult than the previous one, none of which has improved $\theta$ by more than $0.004$, see here for details.
Similar story happens with Gauss circle problem, see the table here.
A: In the 65-page paper A Randomized Rounding Approach to the Traveling Salesman Problem, Oveis Gharan, Saberi, and Singh acquire a $(1.5 - 10^{-52})$-approximation algorithm for the Traveling Salesman Problem on graphical metrics, a problem for which a $1.5$ approximation can be explained and analyzed in under 5 minutes. I have heard that the constant can be improved to $1.5 - 10^{-6}$ with little change to the paper.
Since then, a sequence of simpler works has brought the constant down to 1.4 (which I believe is the latest result).
A: Let $\phi$ be a univalent (i .e., holomorphic and injective) function on the unit disc. Consider the growth rate of the lengths of the images of circles $|z|=r$ as $r$ goes to 1:
$$
\limsup_{r\to 1-}\frac{\log \int_0^{2\pi}|\phi'(re^{i\theta})|d\theta}{|\log(1-r)|},
$$ 
and denote by $\gamma$ the supremum of this quantity over all bounded univalent $\phi$.
Beliaev and Smirnov describe the work on upper bounds for $\gamma$, as of 2004:

Conjectural value of $\gamma=B(1)$
   is $1/4$, but existing estimates are
  quite far. The first result in this direction is due to Bieberbach [7] who in 1914
  used his area theorem to prove that
  $\gamma\leq 1/2$.  <...> Clunie and Pommerenke in [16] proved that
  $\gamma
\leq 
1
/
2
−
1
/
300$ <...> Carleson and Jones [13] <...> used
  Marcinkiewicz integrals to prove
  $\gamma<
0.49755$. This estimate was improved
  by Makarov and Pommerenke [43] to
  $\gamma<
0.4886$ and then by Grinshpan and
  Pommerenke [21] to
  $γ<0.4884$. The best current estimate is due to Hedenmalm
  and Shimorin [24] who quite recently proved that
  $B(1)<0.46.$

I guess the latter estimate is still the best as of now.
