Instances where an existence result precedes the constructive version - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T06:53:30Z http://mathoverflow.net/feeds/question/104731 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version Instances where an existence result precedes the constructive version Vidit Nanda 2012-08-15T00:17:16Z 2012-09-04T00:50:31Z <p>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:</p> <blockquote> <p>Are there good examples of instances in mathematics research where an existence-only result preceded - by some number of years - the corresponding constructive result?</p> </blockquote> <p>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: <a href="http://en.wikipedia.org/wiki/Tucker%27s_lemma" rel="nofollow">Tucker's Lemma</a>, which is a discrete version of the famous <a href="http://en.wikipedia.org/wiki/Borsuk%E2%80%93Ulam_theorem" rel="nofollow">Borsuk-Ulam Theorem</a>, was first proved in the following paper by contradiction:</p> <blockquote> <p>A. W. Tucker. <em>Some topological properties of disk and sphere</em>. In Proc. First Canadian Math. Congress, Montreal, 1945, pages 285–309. University of Toronto Press, Toronto, <em>1946</em>.</p> </blockquote> <p>The first <em>constructive</em> proof (which is starkly different from the original), did not appear in the literature until</p> <blockquote> <p>R. M. Freund and M. J. Todd. <em>A constructive proof of Tucker’s combinatorial lemma.</em> J. Combin. Theory Ser. A, 30(3):321–325, <em>1981</em>.</p> </blockquote> <p>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.</p> <p>Only one example per answer, please!</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104733#104733 Answer by JSE for Instances where an existence result precedes the constructive version JSE 2012-08-15T01:27:14Z 2012-08-15T01:27:14Z <p>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.)</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104734#104734 Answer by Yemon Choi for Instances where an existence result precedes the constructive version Yemon Choi 2012-08-15T01:33:15Z 2012-08-15T01:33:15Z <p>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.)</p> <p>The sort of thing I have in mind is the <a href="https://en.wikipedia.org/wiki/Johnson-Lindenstrauss_lemma" rel="nofollow">Johnson-Lindenstrauss</a> lemma, but I can think of at least two regular MO users who would be better placed than me to comment on it.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104735#104735 Answer by Lee Mosher for Instances where an existence result precedes the constructive version Lee Mosher 2012-08-15T01:34:55Z 2012-08-15T01:34:55Z <p>Steve Smale proved in 1958 that the <a href="http://en.wikipedia.org/wiki/Smale%2527s_paradox" rel="nofollow">2-sphere in 3-space could be everted.</a> <a href="http://mathworld.wolfram.com/SphereEversion.html." rel="nofollow">Afterwards</a> 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.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104736#104736 Answer by Claudio Gorodski for Instances where an existence result precedes the constructive version Claudio Gorodski 2012-08-15T01:47:30Z 2012-08-15T02:17:25Z <p>The <strong>Monster group</strong> 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 <a href="http://en.wikipedia.org/wiki/Monster_group" rel="nofollow">http://en.wikipedia.org/wiki/Monster_group</a>.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104738#104738 Answer by Claudio Gorodski for Instances where an existence result precedes the constructive version Claudio Gorodski 2012-08-15T02:28:51Z 2012-08-15T02:28:51Z <p>In his doctoral dissertation held in Koenigsberg in 1885, Minkowski proposed the conjecture that, unlike the quadratic case, <strong>nonnegative homogeneous polynomials of higher degree and more than two variables in general cannot be written as a sum of squares of real polynomials</strong>. 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 [<em>The arithmetic-geometric inequality</em>, Inequalities (Proc. Sympos. Wright-Patterson Air Force Base, Ohio, 1965), pp. 205-224", Academic Press, New York, 1967].</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104746#104746 Answer by LeBlanc for Instances where an existence result precedes the constructive version LeBlanc 2012-08-15T06:07:18Z 2012-08-17T03:07:44Z <p>One example is indeed that of Transcendental numbers, as Yoav Kallus points out in the comments. </p> <p>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:</p> <p>$$\sum_{n=1}^\infty 10^{-n!}.$$ For more information, see <a href="http://www.jstor.org/stable/1988833" rel="nofollow">here</a> and <a href="http://www-mathdoc.ujf-grenoble.fr/JMPA/PDF/JMPA_1851_1_16_A5_0.pdf" rel="nofollow">here</a>. You might need JSTOR access to read the first.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Cantor%27s_first_uncountability_proof#Is_Cantor.E2.80.99s_proof_of_the_existence_of_transcendentals_constructive_or_non-constructive.3F" rel="nofollow">Wikipedia Article</a></p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104747#104747 Answer by Alexandre Eremenko for Instances where an existence result precedes the constructive version Alexandre Eremenko 2012-08-15T07:08:42Z 2012-08-15T07:43:07Z <p>One can give literally hundreds of examples from classical analysis. usually there are 4 stages:</p> <p>a) non-conscructive proof that some universal constant exists, usually by compactness arguments (in classical function theory this is called normal families argument).</p> <p>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.</p> <p>c) Obtaining some reasonable estimate.</p> <p>On this stage, sometimes a competition starts for better and better estimates, until</p> <p>d) the exact constant is sometimes obtained. Which usually involves solving a variational problem and description of extremal configuration.</p> <p>Some stages can be skipped, of course.</p> <p>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)).</p> <p>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).</p> <p>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)</p> <p>The examples from analysis and number theory are so abundant that I don't think it is possible to catalog them.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/104829#104829 Answer by Zach Hamaker for Instances where an existence result precedes the constructive version Zach Hamaker 2012-08-16T13:04:38Z 2012-08-16T13:04:38Z <p>The <a href="http://en.wikipedia.org/wiki/Lov%25C3%25A1sz_local_lemma" rel="nofollow">Lovasz Local Lemma</a> 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 <a href="http://arxiv.org/abs/0810.4812" rel="nofollow">improved</a> 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 <a href="http://arxiv.org/abs/0903.0544/" rel="nofollow">extended</a> this result to recover every previously known application of the Local Lemma (though not quite the original statement).</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/105053#105053 Answer by Ken W. Smith for Instances where an existence result precedes the constructive version Ken W. Smith 2012-08-19T20:30:24Z 2012-08-19T20:30:24Z <p>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.)</p> <p>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.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/105078#105078 Answer by none for Instances where an existence result precedes the constructive version none 2012-08-20T06:49:12Z 2012-08-20T06:49:12Z <p>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.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/106251#106251 Answer by jbc for Instances where an existence result precedes the constructive version jbc 2012-09-03T15:27:34Z 2012-09-03T15:27:34Z <p>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.</p> http://mathoverflow.net/questions/104731/instances-where-an-existence-result-precedes-the-constructive-version/106253#106253 Answer by Karl Schwede for Instances where an existence result precedes the constructive version Karl Schwede 2012-09-03T15:57:03Z 2012-09-04T00:50:31Z <p>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. </p> <p>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.</p> <p>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. </p> <p>You can see </p> <p><a href="http://mathoverflow.net/questions/4612/hironaka-desingularisation-theorem-new-proofs-in-literature" rel="nofollow">http://mathoverflow.net/questions/4612/hironaka-desingularisation-theorem-new-proofs-in-literature</a></p> <p>for more discussion.</p>