108
$\begingroup$

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?

Improve this question
$\endgroup$
10
  • 13
    $\begingroup$ It is really difficult to answer without a precise definition of "small amount". Let me give a provocative example. It was well known that the Poincare' conjecture hold in every dimension different from $3$. Then Perelman came with his very difficult proof in the case of dimension $3$, and clearly a single case can be seen as a "small amount" when compared with infinitely many :-) $\endgroup$
    – Francesco Polizzi
    Commented Sep 6, 2018 at 8:32
  • 17
    $\begingroup$ @FrancescoPolizzi It might be better considered as "a small amount of what remains to be done" rather than "a small amount of what was needed to be done at the start". So your Poincare example is 100% of what remained to be done, whereas the example in the question is ~0.3%. $\endgroup$
    – Christopher
    Commented Sep 6, 2018 at 10:32
  • 4
    $\begingroup$ This answer of John Baez seems relevant: mathoverflow.net/questions/31315/…. I'm not sure if any of the proofs he mentions are notably long or difficult, but this problem seems to have an interesting history of mathematicians making microscopic improvements on what was known before. $\endgroup$
    – Will Brian
    Commented Sep 6, 2018 at 13:03
  • 17
    $\begingroup$ en.wikipedia.org/wiki/Moving_sofa_problem $\endgroup$
    – Steve Huntsman
    Commented Sep 6, 2018 at 13:29
  • 8
    $\begingroup$ I'm not qualified to post an answer, but I think there are many such examples in combinatorics, depending on what you mean by "notably long or difficult." For example, pulling one of the first paper's from Radziszowski's Small Ramsey Number survey (pdf), Angeltveit and McKay's paper at arxiv.org/abs/1703.08768 checks ~ two trillion cases with a computer program to improve a bound by 1. $\endgroup$
    – Ben Burns
    Commented Sep 6, 2018 at 13:57

11 Answers 11

Reset to default
94
$\begingroup$

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})$

Improve this answer
$\endgroup$
8
  • 16
    $\begingroup$ It's probably worth pointing out that [according to the papers, I don't know the subject myself] the strong-but-widely-believed conjecture - analogous to the Riemann hypothesis in the example in the question - is that the asymptotic complexity is $O(n^2)$. $\endgroup$
    – Christopher
    Commented Sep 6, 2018 at 10:36
  • 24
    $\begingroup$ @Christopher $O(n^2)$ I think would be a shock, but $O(n^{2+\epsilon})$ for any $\epsilon$ is a lot more plausible. $\endgroup$
    – Steven Stadnicki
    Commented Sep 6, 2018 at 17:11
  • 3
    $\begingroup$ @StevenStadnicki, Christopher: Isn't $O(n^2 \log(n))$ a viable conjecture? $\endgroup$
    – Mitch
    Commented Sep 9, 2018 at 0:26
  • 6
    $\begingroup$ @Mitch A function in $O(n^2\log n)$ is also in $O(n^{2+\epsilon})$ for any $\epsilon>0$; that is just a more general form that includes essentially all "$n^2$ times logarithmic factors" classes. $\endgroup$
    – Federico Poloni
    Commented Sep 9, 2018 at 10:08
  • 5
    $\begingroup$ @FedericoPoloni $O(n^2 \log{n})$ is certainly in $O(n^{2+\epsilon})$ for $\epsilon > 0$ but $O(n^{2+\epsilon})$ is not in $O(n^2 \log{n})$. The question is whether $O(n^2 \log{n})$ would also be shocking. $\endgroup$
    – Simd
    Commented Sep 11, 2018 at 11:14
63
$\begingroup$

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.

Improve this answer
$\endgroup$
11
  • 13
    $\begingroup$ I think this is a winner when it comes to both relative and absolute smallest improvement! $\endgroup$
    – Wojowu
    Commented Sep 7, 2018 at 17:12
  • 1
    $\begingroup$ Rogers and Tao have proved that constant is non-negative. See arxiv.org/abs/1801.05914. $\endgroup$
    – M. Khan
    Commented Sep 7, 2018 at 19:19
  • 2
    $\begingroup$ @M.Khan Indeed. The Riemann hypothesis was already known to be equivalent to the statement $\Lambda \leq 0$, so their proof tightened the equivalence to the statement $\Lambda = 0$. $\endgroup$
    – tparker
    Commented Sep 7, 2018 at 19:51
  • 7
    $\begingroup$ Apparently if one thinks about the De Bruijn-Newman constant in isolation, without its connection to the Riemann hypothesis, then it's arguably more natural to conjecture that $\Lambda > 0$ than $\Lambda = 0$. This is considered one of the strongest heuristic arguments against the Riemann hypothesis (although of course not nearly as strong as the many heuristic arguments for it). $\endgroup$
    – tparker
    Commented Sep 7, 2018 at 19:53
  • 14
    $\begingroup$ From $\Lambda\leq1/2$ to $\Lambda<1/2$ I would not say that is a 0% improvement but instead a "0$^{+}$"% improvement. $\endgroup$
    – Matemáticos Chibchas
    Commented Sep 8, 2018 at 23:11
59
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 8
    $\begingroup$ One other notable example from the same area, already mentioned in the very first section 1.1.1 of Tao and Vu's book. Erdos showed that any finite set $A \subset \mathbb{Z}$ of integers contains a subset $B \subset A$ with $|B| > (|A| + 1)/3$ and free of solutions to $x+y = z$. In Estimates related to sumfree subsets of sets of integers (Israel J. Math., 1997), Bourgain applies an ingenious harmonic analysis to strengthen this bound to... $(|A| + 2)/3$. Then again, this establishes the non-sharpness of a classical result, so who judges whether the improvement is "only by a short amount?" $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 7, 2018 at 22:13
  • 7
    $\begingroup$ @VesselinDimitrov I would say this deserves a separate answer. Regardless of how one judges this result, I think it fits well with the spirit of the question. $\endgroup$
    – Wojowu
    Commented Sep 8, 2018 at 12:33
  • $\begingroup$ Does this Quanta article on the problem and of Shakan's recent paper claiming $4/3+5/5277$ further the story? $\endgroup$
    – Mark S
    Commented Feb 8, 2019 at 13:34
  • 1
    $\begingroup$ @MarkS probably it does (I did not check the Shakan's proof myself). The Quanta article somehow misses the Konyagin-Shkredov result in the brief historical survey, I hope that it was not intentional. $\endgroup$
    – Fedor Petrov
    Commented Feb 10, 2019 at 19:58
  • $\begingroup$ In the comments in the Quanta article Thomas Bloom states: "Actually it was Shkredov and Konyagin who were the first to improve the 4/3 exponent of Solymosi, and it was their approach that was subsequently improved by Rudnev, Shkredov, and Stevens." $\endgroup$
    – Mark S
    Commented Feb 11, 2019 at 0:35
41
$\begingroup$

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.

Improve this answer
$\endgroup$
41
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • 28
    $\begingroup$ This is not really a "small amount" since it reduces the approximation to a tight bound. $\endgroup$
    – Ethan Bolker
    Commented Sep 7, 2018 at 16:55
  • $\begingroup$ @EthanBolker I am pretty sure that the notion of "small amount" was not defined in the question when I was answering it. I respect your opinion about what "small amount" is, but I have a somewhat different opinion, which I believe is also reasonable. If you think there is a universally agreed upon notion of "small amount", I would gladly hear about that. $\endgroup$
    – user74900
    Commented Apr 30, 2019 at 6:10
26
$\begingroup$

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).

Improve this answer
$\endgroup$
13
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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.)

Improve this answer
$\endgroup$
8
$\begingroup$

Almost any paper on the Gauss Circle Problem written in the last 70 years qualifies.

Improve this answer
$\endgroup$
1
  • 6
    $\begingroup$ I have already mentioned that in my answer about Dirichlet divisor problem. $\endgroup$
    – Wojowu
    Commented Sep 8, 2018 at 12:27
8
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .