# Instances where an existence result precedes the constructive version

The basic motivation here is to encourage and inspire - via examples - the pursuit of alternate proofs of existing results that might be more accessible and intuitive by cataloging success stories. Here's the question:

Are there good examples of instances in mathematics research where an existence-only result preceded - by some number of years - the corresponding constructive result?

I am aware of one nice example from my own field, which I hope is illustrative of the type of answer that would be nice to collect here: Tucker's Lemma, which is a discrete version of the famous Borsuk-Ulam Theorem, was first proved in the following paper by contradiction:

A. W. Tucker. Some topological properties of disk and sphere. In Proc. First Canadian Math. Congress, Montreal, 1945, pages 285–309. University of Toronto Press, Toronto, 1946.

The first constructive proof (which is starkly different from the original), did not appear in the literature until

R. M. Freund and M. J. Todd. A constructive proof of Tucker’s combinatorial lemma. J. Combin. Theory Ser. A, 30(3):321–325, 1981.

I did try just searching google for "A constructive proof of" and similar search strings. This does provide some examples, but the results are not filtered by importance of the result in question, or the extent of difference between the old existence result and the newer constructive one.

-
"In his seminal work of 1948, Shannon had characterized the highest rate (speed of transmission) at which one could reliably communicate over a discrete memoryless channel (a noise model); he called this limit the capacity of the channel. However, he used a probabilistic method in his proof and left open the problem of reaching this capacity with coding schemes of manageable complexities." From gilkalai.wordpress.com/2010/11/25/emmanuel-abbe-polar-codes –  Steve Huntsman Aug 15 '12 at 1:00
To clarify: I assume you want instances where there actually is a constructive proof. –  Nate Eldredge Aug 15 '12 at 3:01
I wonder if transcendental numbers qualify here. Does anybody know the history? –  Yoav Kallus Aug 15 '12 at 3:11
@Nate: yes. Is there another way to interpret the question? –  Vidit Nanda Aug 15 '12 at 3:23
There are existence proofs for which there is no constructive proof. The probabilistic method in combinatorics has produced many such examples, e.g., that $R(r,r)$ grows exponentially because if $n \gt c \sqrt2^r$ then the probability that a random coloring of $K_n$ has a monochromatic $K_r$ is less than $1$, or even less than $1/100$. No construction is known. –  Douglas Zare Aug 15 '12 at 6:09

Steve Smale proved in 1958 that the 2-sphere in 3-space could be everted. Afterwards the first explicit model of an eversion was discovered in 1961 by Arnold Shapiro, but it took still a few more years before such models were explained to the larger mathematical community in Tony Phillips' 1966 article in Scientific American.

-
Amazing film. It deserves a wide audience. –  Felix Goldberg Aug 15 '12 at 10:05
Yeah that's a great film. It is a continuation of the story of existence vs. construction. The construction depicted in that film was discovered by William Thurston, but in this case not as another isolated construction but as an implementation of general proof method for simple homotopy problems –  Lee Mosher Aug 15 '12 at 12:39
Oops, I meant to say "for regular homotopy problems". –  Lee Mosher Aug 15 '12 at 23:30

Expander graphs were known to exist for many years before there was any provable example (essentially because it is not hard to show that a random sequence of graphs is expander with probability 1.)

-
More generally, the probabilistic method (en.wikipedia.org/wiki/Probabilistic_method) as pioneered by Erdos comes to mind. –  Michael Lugo Aug 15 '12 at 3:04
It is pretty hard to construct a graph which is not expanding with some constant, and given a graph of a reasonable size, it is not so difficult to compute the expansion constant (the stupid algorithm is exponential, but for graphs up to around 30 vertices this should not be a problem). It is constructing an infinite family of such that is hard. –  Igor Rivin Aug 15 '12 at 4:06
Yes -- by "expander graph" I mean "infinite family of graphs with a spectral gap." Bad notation, I know. –  JSE Aug 15 '12 at 4:48

In his doctoral dissertation held in Koenigsberg in 1885, Minkowski proposed the conjecture that, unlike the quadratic case, nonnegative homogeneous polynomials of higher degree and more than two variables in general cannot be written as a sum of squares of real polynomials. The problem attracted the attention of Hilbert who in 1888 proved nonconstructively the existence of such polynomials. However, the first concrete example of a nonnegative polynomial which is not a sum of squares seems to have been given only in 1967 by T. S. Motzkin [The arithmetic-geometric inequality, Inequalities (Proc. Sympos. Wright-Patterson Air Force Base, Ohio, 1965), pp. 205-224", Academic Press, New York, 1967].

-

As I understand it, Hilbert's original solution to Gordan's Problem was nonconstructive, proving that every algebraic variety over a field had a finite generating set. (His result is now generally cited as "Hilbert's Basis Theorem", that polynomial rings over Noetherian rings are Noetherian.)

In modern day algebraic geometry, Hilbert's nonconstructive argument is replaced by a very constructive process in which one generates a Groebner Basis for the algebraic set.

-
Didn't Hilbert himself produce a constructive proof a few years after his non-constructive one? –  Arthur Fischer Aug 20 '12 at 17:24

One example is indeed that of Transcendental numbers, as Yoav Kallus points out in the comments.

Liouville showed in 1844 that numbers which do not satisfy a polynomial equation with integer coefficients exist, but he only gave an example in 1851, the famed Liouville constant, a celebrity among Transcendental numbers:

$$\sum_{n=1}^\infty 10^{-n!}.$$ For more information, see here and here. You might need JSTOR access to read the first.

Cantor however, whose proof of the existence of Transcendental numbers follows directly from the uncountability of the Reals, only came up with his proof in 1874. Whether his proof of the Uncountability of the Reals is constructive or not is something people are still debating, so I will not comment on that. For more information on this, see this Wikipedia Article

-
Your link entitled "Wikipedia Article" is broken. –  Lee Mosher Aug 16 '12 at 13:40
@LeeMosher Thanks! Fixed it. –  LeBlanc Aug 17 '12 at 3:08
The Cantor-style proof of the existence of transcendental numbers is certainly constructive. (I didn't see any coherent argument to the contrary on that Wikipedia talk page.) See for instance the comment of Joel David Hamkins here: mathoverflow.net/questions/10334/…, the Monthly article he cites, and my own answer here: mathoverflow.net/questions/20430/… –  Tom Leinster Aug 20 '12 at 18:42

One can give literally hundreds of examples from classical analysis. usually there are 4 stages:

a) non-conscructive proof that some universal constant exists, usually by compactness arguments (in classical function theory this is called normal families argument).

b) a proof which is constructive "in principle", and gives SOME numerical estimate. Sometimes this estimate is ridiculoisly large (or small), and the author does not even care to write it.

c) Obtaining some reasonable estimate.

On this stage, sometimes a competition starts for better and better estimates, until

d) the exact constant is sometimes obtained. Which usually involves solving a variational problem and description of extremal configuration.

Some stages can be skipped, of course.

Some famous examples include "K\"obe constant", which turned out to be 1/4. Bloch's and Landau constants (they are almost century old, and currently they are on stage c)).

Often the time between a) and b) is small. The largest time usually passes from c) to d), and many problems stop on stage c).

Here are two examples from my own work: arXiv:math/0607743, the time lag between a) and b) was 65 years. arXiv:math/0510502, a problem still in stage a)

The examples from analysis and number theory are so abundant that I don't think it is possible to catalog them.

-
Alexandre, this question is only about getting from a) to d). There are "literally hundreds of examples" because you have over-estimated the scope of the question. In particular, getting to stage c) is no guarantee whatsoever that stage d) will actually be reached and without that you are including all possible existence results for which no constructive version is known, rather than examples where the constructive version is known and came after many years. That being said, the K\'obe constant example sounds interesting and relevant. –  Vidit Nanda Aug 15 '12 at 17:20
Is these a misprint in your message: did you mean to write "from a) to b)" in the first line? This is how I understood the original question: from a) to b) from non-constructive to constructive. Yes, I widened the scope:-) But the two examples I gave from my work are indeed related to a) and b). –  Alexandre Eremenko Aug 15 '12 at 21:46
You're quite right, I had mis-read. Apologies! –  Vidit Nanda Aug 17 '12 at 17:09

The Lovasz Local Lemma establishes under certain assumptions that a collection of events can simultaneously fail to occur. The initial proofs from the 1970's were used the techniques of probabilistic techniques, hence were non-constructive. People worked on providing a constructive proof and had partial results based on substantially weaker assumptions about the relationship of the events. In 2008, Robin Moser greatly improved on these results, demonstrating an algorithm running in polynomial time that produces such an outcome for a standard case. With Gabor Tardos in 2009, he extended this result to recover every previously known application of the Local Lemma (though not quite the original statement).

-

Hironaka's original desingularization algorithm had constructive aspects but as I understand, also had aspects / computations which are not constructive and could not be done by hand or with a computer.

Resolution algorithms now typically are based upon blowing up the strata of some invariant (where heuristically the singularities are at their worst) and so they are constructive if you can compute the invariant. But these invariants might be for all intents and purposes completely incomputable, for example based on infinite amounts of data.

New algorithms have simplified many aspects on this, and indeed, algorithms have been implemented in computers, and it isn't so hard to write down all the various invariants as you follows modern algorithms.

You can see

Hironaka desingularisation theorem -- new proofs in literature?

for more discussion.

-

Gauss proved the Euclidean constructibality of the 257-gon (as well as the 17-gon and others) in 1796. In 1832, Friedrich Julius Richelot actually gave an explicit construction.

-
Hm, I was under the impression a construction was extractable from the original proof, even if it wasn't actually extracted (making this not really an answer to the original question). Is that mistaken? –  Harry Altman Aug 20 '12 at 7:29
Indeed, we now have a construction for the regular $n$-gon for any Fermat prime $n$ - all we're lacking is the existence proof for Fermat primes exceeding 65537. –  Gerry Myerson Sep 4 '12 at 5:39

The Monster group is a finite simple group of order approx. $8\cdot 10^{53}$ whose existence was predicted by Fischer and Griess in about 1973. An explicit construction of a representation of dimension 196882 over $\mathbf Z_2$ was obtained by Robert Wilson with the aid of a computer (published in 1998); see Wikipedia article http://en.wikipedia.org/wiki/Monster_group.

-
Claudio, I believe this has already been covered in Lee Mosher's answer. –  Vidit Nanda Aug 15 '12 at 1:58
@Vel Nias: Sorry, I was beaten by Lee Mosher by 12 min or so and didn notice. I am replacing my answer by another now. –  Claudio Gorodski Aug 15 '12 at 2:18

There are certain "probabilistic constructions" in Banach space theory where one shows that something happens with positive probability, but where explicit examples still aren't known. (That said, I am not up to speed with the developments here, and I seem to recall reading that in several cases, via derandomization techniques one can turn the existence proofs into reasonable algorithms for producing examples.)

The sort of thing I have in mind is the Johnson-Lindenstrauss lemma, but I can think of at least two regular MO users who would be better placed than me to comment on it.

-
I think the question is asking for instances where existence < construction < now. Otherwise every nonconstructive result would be a candidate for an answer. –  Nate Eldredge Aug 15 '12 at 3:00

A striking example is the use of Buchberger's algorithm to construct Gröbner bases. The latter concept goes back to the end of the 19th century but it was only on the arrival of Buchberger's algorithm that it became the omnipresent computational tool that it is today.

-