Instances where an existence result precedes the constructive version - MathOverflow

Instances where an existence result precedes the constructive version

2012-08-15T00:17:16Z

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.

Only one example per answer, please!

Answer by JSE for Instances where an existence result precedes the constructive version

2012-08-15T01:27:14Z

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

Answer by Yemon Choi for Instances where an existence result precedes the constructive version

2012-08-15T01:33:15Z

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.

Answer by Lee Mosher for Instances where an existence result precedes the constructive version

2012-08-15T01:34:55Z

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.

Answer by Claudio Gorodski for Instances where an existence result precedes the constructive version

2012-08-15T01:47:30Z

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.

Answer by Claudio Gorodski for Instances where an existence result precedes the constructive version

2012-08-15T02:28:51Z

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

Answer by LeBlanc for Instances where an existence result precedes the constructive version

2012-08-15T06:07:18Z

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

Answer by Alexandre Eremenko for Instances where an existence result precedes the constructive version

2012-08-15T07:08:42Z

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.

Answer by Zach Hamaker for Instances where an existence result precedes the constructive version

2012-08-16T13:04:38Z

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

Answer by Ken W. Smith for Instances where an existence result precedes the constructive version

2012-08-19T20:30:24Z

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.

Answer by none for Instances where an existence result precedes the constructive version

2012-08-20T06:49:12Z

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.

Answer by jbc for Instances where an existence result precedes the constructive version

2012-09-03T15:27:34Z

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.

Answer by Karl Schwede for Instances where an existence result precedes the constructive version

2012-09-03T15:57:03Z

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

http://mathoverflow.net/questions/4612/hironaka-desingularisation-theorem-new-proofs-in-literature

for more discussion.