What are some examples of ingenious, unexpected constructions?

Question

Many famous problems in mathematics can be phrased as the quest for a specific construction. Often such constructions were sought after for centuries or even millennia and later proved impossible by taking a new, "higher" perspective. The most obvious example would be the three geometric problems of antiquity: squaring of circles, duplication of cubes and trisection of angles by ruler and compass alone. Closely related to these three is the construction of regular $n$-gons for general $n$. Later we have the solution of an arbitrary algebraic equation by means of radicals or the expression of the circumference of an ellipse by means of elementary functions. In the 20th century we have Hilbert's tenth problem: find an algorithm to determine whether a given diophantine equation has solutions.

All these constructions turned out to be impossible, but the futile search produced some new and great mathematics: Galois theory, group theory, transcendental numbers, elliptic curves ...

But I am looking for examples which are in some sense the opposite of the above: where somebody turned up with an ingenious construction in a problem where it had been generally believed that no such construction should exist. Ideally, this construction should have made new interesting questions and methods turn up, but I am also interested in isolated results that may just be counted as funny coincidences. To make my point clearer, let me present my own two favourite examples.

(1) Belyi's Theorem: If $X$ is a smooth projective algebraic curve defined over a number field, there exists a rational function on $X$ whose only singular values are $0$, $1$ and $\infty$. --- According to his Esquisse d'un programme, Grothendieck had thought about this problem shortly before but found the statement so bold that he even felt awkward for asking Deligne about it. To put the theorem into context, the converse statement (that every curve which admits a rational function with only these three singular values can be defined over a number field) had been known before by abstract nonsense and is quite straightforward to deduce from deep results in Grothendieck-style algebraic geometry. Belyi's proof, however, was completely elementary, constructive, and tricky. Also it is more important than it might seem at first sight since it opens up a very strict, and equally unexpected, connection between the topology of surfaces and number theory.

(2) Julia Robinson's theorem about the definability of integers: Suppose you want to single out $\mathbb{Z}$ as a subset of $\mathbb{Q}$, using as little structure as possible. The result in question is at least to me absolutely striking. I do not know if it was so unexpected to the experts at that time, but the construction is in any case really ingenious. It says that there exists a first-order formula $\varphi$ in the language of rings (i.e. only talking about elements, not subsets, and using only logical symbols and multiplication and addition, and the symbols $0$ and $1$) such that for a rational number $r$, $\varphi (r)$ is true if and only if $r$ is an integer. Robinson's original formula is $$\varphi (r)\equiv\forall y\forall z(\psi (0,y,z)\wedge\forall x(\psi (x,y,z)\longrightarrow \psi (x+1,y,z))\longrightarrow\psi (r,y,z))$$ with $$\psi (x,y,z) \equiv \exists a\exists b\exists c(2 + x^2yz = a^2 + yb^2-zc^2).$$ Since this is not my area of research I do not attempt to estimate the historical importance of this discovery, but it seems to me that it is of great weight in the intersection of number theory and logic.

So I hope these two examples make it clear what I am after, and I am looking forward to reading your examples.

Answer 1

I am not expert in the field, but it seems that Nash's embedding theorem is considered very unexpected for two reasons: first because at that time people thought that Riemannian manifolds were a so general object that nobody believed that they could be actually embedded (as smoothly as possible) in an Euclidean space. Second, because Nash's proof used new and unexpected techniques. If you read Gromov's interview for the Abel prize http://www.ams.org/notices/201003/rtx100300391p.pdf, at p.394, second column, third answer, he said: At first, I looked at one of Nash’s papers and thought it was just nonsense. But Professor Rokhlin said: “No, no. You must read it.” I still thought it was nonsense; it could not be true. But then I read it, and it was incredible. It could not be true but it was true.

Answer 2

Geometric Topology is full of such examples. Perhaps the most dramatic of all were Milnor's construction of exotic 7-spheres and counterexample to the Hauptvermutung.

Since Poincaré, it had been widely believed that smooth manifolds and PL manifolds were two formalisms to describe one and the same class of objects, and proving that they were equivalent seemed almost like a fiddly technical detail. Indeed, in 3-dimensional topology (where the categories do happen to coincide, by work of Whitehead, Munkres, and others), people switch from smooth to PL objects and back ten times in the same paper, or even inside the same proof, without giving the matter a second thought. Statements like "corners can be smoothed" are mentioned with hardly a wave of the hand, almost derisively. So the fact that the categories don't coincide, and that the difference between them is meaningful and interesting, was a huge shock to topology, and has shaped a large part of the research in the subsequent half-century.

In an entirely different direction, Francisco Santos's Counterexample to the Hirsch Conjecture was a great surprise... the Polymath 3 Project originally had, I think, the dream-goal of proving it; and my understanding is that, since 1957, the vast majority of people had believed it to be true. The counterexample is interesting, and seems to be framing current work on the Polynomial Hirsch Conjecture at Gil Kalai's blog.

Answer 3

1. Peaucellier–Lipkin inversor: https://en.wikipedia.org/wiki/Peaucellier-Lipkin_linkage By mid-19th century it was widely believed that one cannot transform circular motion to linear motion. For instance, Chebyshev tried quite hard but gave up and invented his polynomials instead, to deal with the issue approximately. The construction of inversor is simple and ingenious.

2. Mnev's Universality Theorem dealing with configuration spaces of linear arrangements and convex polytopes. The idea is that one can encode elementary algebraic operations into elementary geometric objects (actually, this goes back to Von Staudt in 19th century).

3. Connelly's flexible polyhedron is an example of a polyhedral sphere embedded in ${\mathbb R}^3$ which admits nontrivial deformations (so that each boundary face stays rigid). Cauchy proved (with some gaps fixed over 100 years later) that there are no flexible convex polyhedra, but general rigidity problem was open for over 150 years. People tended to believe that such polyhedra do not exist (for instance, "generic" polyhedral spheres are rigid). Connelly started by trying to prove non-existence and ended up constructing a counter-example, again, simple and ingenious.

Answer 4

I notice no one mentions Godel's Incompleteness Theorems, or the basic non-computability results of Turing. Are they too obvious?

If these are not constructive enough, one that is fairly elementary is a space-filling curve. If you want something non-intuitive, how do you like a continuous surjection from a 1-dimensional space to a 2-dimensional space?

Answer 5

How about Don Zagier's one sentence proof (The American Mathematical Monthly, Vol. 97, No. 2, Feb., 1990) that every prime $\equiv 1\bmod 4$ is a sum of two squares?

Answer 6

I think the Banach-Tarski Paradox qualifies as ingenious and unexpected.

Answer 7

One of my favorite "simple ingenious constructions" in theoretical computer science from the past few decades is Barak et al.'s construction of a computer program that can never be "obfuscated": that is, for which having the code of the program is always more useful than just being able to run the program as a black box.

Such a program is constructed as follows. First, choose three "secret" n-bit strings a,b,c uniformly at random (I'll assume they're all nonzero). Then consider a program P with the following behavior:

P(0,x) = b if x=a, or 0ⁿ otherwise

P(1,<Q>) = c if Q(0,a)=b, or 0ⁿ otherwise (where Q is some other program and <Q> is its code)

Now suppose you want to learn the secret string c. If all you can do is feed various inputs to P and observe the outputs, then it's not hard to see that the best you can possibly do is "brute-force search": on average, you'll have to try ~2ⁿ inputs to P before you see any output other than 0ⁿ. By contrast, if someone gives you the actual code for P, then no matter how badly they've "obfuscated" that code, you can always learn c with just a single access. The trick, much like in Turing's original proof of the unsolvability of the halting program, is to feed P its own code as input:

P(1,<P>) = c.

Answer 8

I am very fond of Goodstein's theorem and especially of its proof, using ordinal arithmetic to prove that an integer sequence (which at first sight seems hopelessly increasing) is ultimately zero. See for instance here.

Answer 9

A couple of others have mentioned Gödel's theorem, Turing's noncomputability results, and Turing degrees below the halting problem. If I may elaborate a little, the ancestor of all these constructions was Cantor's diagonal construction, which constructs a real number different from all members of a countable list of reals.

When the diagonal argument is applied to the real numbers defined by Turing machines, it seems to compute a real number that is not computable, so one is forced to conclude that there is no algorithm for deciding which machines define real numbers, and this leads to the unsolvability of the halting problem. Then, when one thinks about machines for generating theorems (about Turing machines, say), one sees that a machine cannot generate all (and only) true theorems -- a form of Gödel's theorem.

Increasingly sophisticated versions of the diagonal construction developed in the 1950s, starting with Friedberg and Muchnik's construction of c.e. sets $A$ and $B$ with incomparable degrees of unsolvability in 1956. That is, $A$ and $B$ can each be enumerated by Turing machine, but no machine can solve the membership problem for $A$, even given complete membership information about $B$, and vice versa.

After the discovery of the Friedberg-Muchnik result, it became something of an industry to devise more and more complicated diagonal constructions, in what became known as the theory of degrees of unsolvability. I have the impression that, by around 1970, the whole raison d'etre of this theory was to devise ingenious constructions.

Answer 10

Another example that just came to my mind is the "set of all sets that do not contain themselves" in Russell's paradox - it was very simple, as unexpected as anything and turned the ideas about sets completely topsy-turvy.

Answer 11

The Thom-Pontryagin construction is ingenious and unexpected, and turns out to be tremendously important. To construct an oriented cobordism group, consider the set of oriented compact $n$-manifolds, modulo the equivalence relation that two such manifolds are considered equivalent if they together bound an oriented compact $(n+1)$-manifold. This is seen to have the structure of an abelian group, where the inverse of a manifold is that manifold with the opposite orientation. The oriented cobordism group of points is isomorphic to $\mathbb{Z}$, where a pair of points oriented "+" and "-" cobound an oriented interval. The oriented cobordism group of circles is $\{0\}$, because any set of circles together cobound a surface, and the oriented cobordism group of compact surfaces is also $\{0\}$ because any oriented surface bounds a handlebody.

Cobordism groups had been in the air for a long time, with Poincaré having considered them as a first (failed) attempt to define homology. In general, there are an uncountable number of $n$--manifolds, so one would have expected oriented cobordism groups to be hopelessly untractable for large $n$. But, by a simple ingenious construction for which he won the Field's medal, René Thom showed that the oriented cobordism group $\mathcal{N}^+_{d-1}$ is isomorphic to $\pi_{d-1}\Omega^\infty MSO$, which are homotopy groups of the infinite loop space of the Thom spectrum. This is a very large space, but calculating its homotopy turns out to be quite simple, and it turns out to be the case that $\mathcal{N}^+_{d-1}$, modulo torsion is nothing more than a polynomial algebra $\mathbb{Q}[y_{4i}]_{i\geq 1}$ where $y_{4i}$ is a formal variable which can be represented by the complex projective space $\mathbb{CP}^{2i}$.

The Thom-Pontryagin construction itself is explained very nicely in an MO answer of Greg Kuperberg. A short lucid introduction to this story, on which this answer is loosely based, is given in the first few minutes of Ulrike Tillman's talk at the recent IMA conference in honour of John Milnor.

Answer 12

There are a lot of interesting examples in what might be dubbed classical surface theory (this refers to the question the example answers if not the method of construction).

1. The sphere eversion. In the 60's Smale showed (indirectly) that if $f_1:\mathbb{S}^2\to \mathbb{R}^3$ was an immersion then there was a regular homotopy $f_t:\mathbb{S}^2\to \mathbb{R}^3$ so that $f_{-1}=-f$ (i.e. you can turn the sphere inside out). This was is very difficult to visualize and so is highly unexpected. There are now a number of explicit constructions (using for instance the Willmore energy). You can see one here.

2. The Wente Torus. Alexandrov showed that there is no compact embedded surface in $\mathbb{R}^3$ with constant mean curvature (CMC) other than the round sphere. Hopf conjectured that there was no immersed CMC surfaces in $\mathbb{R}^3$ other than the round sphere and showed this was true for topological spheres. Wente showed (using integrable system techniques) that there existed a CMC torus (necessarily possessing self-intersections) here. By "gluing" Wente's torus you can produce CMC surfaces of arbitrarily genus.

3. The Costa-Hoffman-Meeks surface. For a long time the only examples of complete, embedded minimal (i.e. zero mean curvature) surfaces in $\mathbb{R}^3$ of finite topology where the plane, helicoid and catenoid (all known in the 18th century). In the mid-80's Costa constructed an explicit complete minimal immersion of a thrice-punctured torus. The immersion appeared to be embedded, and was rigorously shown to be embedded by Hoffman and Meeks. This was apparently quite unexpected (I have been told that proofs circulated that such a surface could not exist). Many further examples with higher genus and number of punctures now exist.

4. Nadirashvilli's example. Nadirashvilli constructed (here) a complete minimal immersion of the plane that lies entirely within the unit ball of $\mathbb{R}^3$ (this answered a question of Calabi on whether such an immersion could exist). Colding and Minicozzi showed that this cannot be done with a minimal embedding (and finite topology) (see here)

Answer 13

1) Alexander's horned sphere, disproving the Jordan curve theorem in high dimensions.

2) Maybe not a watershed construction as some others named, but certainly high up on the "awesome" list: Higman's universal group.

Answer 14

I think Elkies' construction of numbers $a,b,c,d$, such that $a^4 + b^4 + c^4 = d^4$, disproving Euler's sum of powers conjecture, is quite impressive. Another nice construction from number theory is Mahler's construction of numbers $n$ such that $r_{3,3}(n) > cn^{1/12}$, where $r_{3,3}(n)$ denotes the number of representations of $n$ as sum of three non-negative cubes, which disproved Hypothesis K of Hardy and Littlewood.

Answer 15

The construction of finitely generated infinite torsion groups (especially of bounded exponent), i.e., the Burnside problem. Schur, building on work of Burnside, proved finitely generated torsion linear groups were finite. Golod constructed the first finitely generated infinite torsion group (a p-group with unbounded exponent) using the Golod-Shafarevich theorem. Adian and Novikov proved that finitely generated free groups of exponent n are infinite for n sufficiently large and odd. Relatively simple to understand examples of finitely generated groups (with unbounded exponent) were constructed by Grigorchuk, Suschanskii, Gupta-Sidki using groups acting on rooted trees (or automata) (I believe Aleshin first suggested using automata for the Burnside problem, but I don't know if he proved any of his constructions worked).

Answer 16

The best one I can think of would be: The Attempts to Resolve The Continuum Hypothesis, and The Souslin Hypothesis.

The list of tools developed to deal with the new and subtle problems that cropped up while trying to either affirm or refute these two classical problems is almost unending. The main take away from all of this work was that the universe is much more flexible than we had ever dreamed.

A short list:

1. Forcing ( wiki )
2. http://en.wikipedia.org/wiki/List_of_forcing_notions
3. Model Theory ( wiki model theory )
4. Inner Model Theory ( inner model theory )
5. The Original Inner Model
6. The Various Large Cardinal Hypothesis which have been developed ( cantors attic ) and Kunen's delimiting result ( Kunen's inconsistency theorem )

Answer 17

Drinfel'd modules: Constructing explicitly abelian extensions of global function fields.

Answer 18

I think Weierstrass's construction of a continuous, nowhere differentiable function, was quite a surprise at the time.

Answer 19

Disproving an old A. D. Alexandrov's hypothesis on a characterization of the 2-sphere, Y. Martinez-Maure constructed a curious object in Euclidean 3-space $R^3$: a closed oriented surface M that has the following properties:

1) M is a smooth saddle surface at each of its points (except for four points called ‘horns’): every point x of M distinct from a horn is a hyperbolic point of M (the Gaussian curvature of M is negative at x).

2) M possesses (as smooth strictly convex surfaces) a well-defined smooth support function on $S^2$. In particular, its Gauss map $M → S^2$ is injective.

See :

M G Knyazeva and Gayane Yu Panina, Russian Mathematical Surveys Volume 63, 2008.

and/or

Y. Martinez-Maure, Contre-exemple à une caractérisation conjecturée de la sphère, Comptes Rendus de l'Académie des Sciences de Paris 332, Série I, 2001, 41-44.

Answer 20

There is an absolutely unexpected (to me, anyway) construction of Mikhalev--Umirbaev--Zolotykh of a Lie algebra $L$ in characteristic $p$ which is not free but whose universal enveloping $U(L)$ is a free Lie algebra. The definition is very simple: it has three generators $a,b,c$ and one relation $a=[b,c]+\mathrm{ad}(a)^p(c)$.

[The universal enveloping is obviously free since $\mathrm{ad}(a)^p=\mathrm{ad}(a^p)$, so the relation becomes $a=[b+a^p,c]$, and after applying the automorphism $a\mapsto a'=a, b\mapsto b'=b+a^p, c\mapsto c'=c$, we have $a'=[b',c']$, hence the universal enveloping algebra is obviously freely generated by $b'$ and $c'$. The proof of non-freeness of $L$ is much more subtle, using Fox derivatives and stuff like that.]

Answer 21

Listing examples is easy in Banach space theory.

1. (1950) R.C.James' construction of non-reflexive (Banach) space isometric to its bidual.

2. (1972) P. Enflo's example of a separable space without approximation property and thus without Schauder basis.

3. (1974) R.C.James' construction of a space whose dual is non-separable and all of its subspaces contain a copy of $\ell_2$.

4. (1974) B. Tsirelson's space without $c_0$ and $\ell_p$.

5. (1975) P. Enflo's example of an operator without non-trivial invariant subspaces.

6. (1993) Gowers and Maurey's construction of a space such that no infinite dimensional subspace has a non-trivial complemented subspace (hereditarily indecomposable).

7. (2010) Argyros and Haydon's construction of a space on which every operator is a scalar multiple of the identity plus a compact operator (see Gowers' blog).

Answer 22

I don't know how fruitful it proved, but my impression of Pisier's counterexample to a conjecture of Grothendieck (a Banach space on whose tensor square all reasonable cross-norms coincide) is that it was unexpected at the time. Perhaps Bill Johnson can correct me on this if I am mistaken? It certainly qualifies as ingenious, in my book.

The article is

G. Pisier, Counterexamples to a conjecture of Grothendieck. Acta Math. 151 (1983), no. 3-4, 181--208.

Since the MathReview explains things quite well, and people may not have easy access, here are some selected parts of the review:

A. Grothendieck posed the following problem ... if $X$ and $Y$ are Banach spaces such that $X\check\otimes Y$ and $X\hat\otimes Y$ coincide, then is one of them necessarily finite-dimensional? Grothendieck conjectured a positive answer [Bol. Soc. Mat. Sao Paulo 8 (1953), 1--79; MR0094682 (20 #1194) ]. The author solves this problem in the negative by giving an example of a separable infinite-dimensional Banach space $X$ such that $X\check\otimes X= X\hat\otimes X$.

... any (separable) Banach space $E$ of cotype 2 can be imbedded isometrically into a (separable) Banach space $X$ such that (a) $X$ and $X^*$ are both of cotype 2 and they "verify Grothendieck's theorem'' (every operator into a Hilbert space is absolutely summing), and (b) $X\check\otimes X=X\hat\otimes X$.

... Any infinite-dimensional space $X$ satisfying (a) cannot be isomorphic to a Hilbert space, although $X$ and $X^*$ are of cotype 2...

... the natural map $X^* \hat\otimes X\rightarrow X^*\check \otimes X$ is not injective. However, it is shown that for any Banach space $X$ satisfying (a) this map is surjective. In other words: every operator in $X$ which is a uniform limit of finite-rank operators is nuclear.

Answer 23

Friedberg's and (independently) Muchnik's solution to Post's problem, showing there are Turing degrees between 0 and 0', by inventing the priority-injury method.

Barrington's theorem in complexity theory, about width-5 branching programs being more powerful than people had expected. The "5" is special because the alternating group A5 is unsolvable, but A4 is not.

Answer 24

Kontsevich's construction of a universal rational-valued Vassiliev invariant via the Kontsevich integral. It is a truly ingenious construction; it as an integral over a configuration space of an embedded knot. It used completely different techniques than were available in the field at the time, and opened up a whole area of research for many mathematicians.

Answer 25

In control theory we often wish to find a feedback control $u$ to stabilize a given linear system $\dot{x} = A x + B u, y= Cx$. The problem of linear adaptive control consists in constructing such a controller, using measurements of $y$ only, without precise a priori knowledge about the matrices $A$, $B$, and $C$.

During the 1970s and 1980s several adaptive control algorithms appeared, under restrictive assumptions on the matrices. Notably the transfer function $c (sI - A)^{-1}b$, in the single-input, single-output case, was required to be minimum-phase (have stable zeroes). It was thought that some of those assumptions were indeed necessary.

In 1986 Bengt Mårtensson in his Lund PhD thesis "Adaptive Stabilization" showed that essentially all one needs to know are the dimensions of the matrices. For effective practical algorithms of course more a priori information is crucial. This discovery of "universal stabilizers" came as a great surprise to the adaptive control community. The techniques used, involving switching and dense search, were also rather unexpected.

Answer 26

I think the Besicovitch sets are really unexpected, and then also Kakeya sets. The first type of sets are sets of measure 0 in the plane, with a line segment of unit length in every direction. The latter sets are sets where a needle of unit length can be rotated a full turn (moving back and forth is also admitted). Kakeya sets are naturally Besicovitch sets, and surprisingly, there is a Kakeya set of any positive Lebesgue measure.

https://en.wikipedia.org/wiki/Kakeya_set#Besicovitch_needle_sets

Answer 27

work of Tits on BN pair is the perfect one

Answer 28

The discovery and construction of Schramm-Loewner evolutions by Oded Schramm, and the subsequent proofs that many random discrete curves (self-avoiding walk (still open), interface of critical percolation, contour curves of uniform spanning trees, interface of critical Ising model, loop-erased random walk) converge to them with various parameters, is perhaps the most celebrated result in probability theory today.

Answer 29

My favourite construction is Néron models. I think it was unexpected to have such a type of model, and it has been really very useful in proving some of the big results in arithmetic geometry these recent years...

Answer 30

After it was understood that the complex numbers could be understood geometrically as the points on a plane there was a search for a 3d generalisation of these numbers.

This led to Hamilton's discovery of the quaternions. The surprise here that they had a 1d real part and a 3d vector part and furthermore they were anti-symmetric.