# Blackbox Theorems [closed]

By a blackbox theorem I mean a theorem that is often applied but whose proof is understood in detail by relatively few of those who use it. A prototypical example is the Classification of Finite Simple Groups (assuming the proof is complete). I think very few people really know the nuts and bolts of the proof but it is widely applied in many areas of mathematics. I would prefer not to include as a blackbox theorem exotic counterexamples because they are not usually applied in the same sense as the Classification of Finite Simple Groups.

I am curious to compile a list of such blackbox theorems with the usual CW rules of one example per answer.

Obviously this is not connected to my research directly so I can understand if this gets closed.

• I have heard the resolution of singularities being mentioned as an example of this (although there seem to be simpler proofs around now). Jun 13 '12 at 21:28
• Domain of use is important here. Many theorems are invoked by physicists who have no idea of the actual proofs. Jun 13 '12 at 22:05
• @Zsbán: That theorem has nice consequences, e.g., in finite geometry. But treating it as a blackbox is just laziness, since the proof is just a couple of pages of basic graduate algebra. Jun 15 '12 at 0:19
• The classification is used by people working on permutation groups and graph theory all the time. Also they are used in profinite group theory. Jun 16 '12 at 19:21
• In my mind I was hoping for things used in at least 100 papers and understood in all technical detail by fewer than 5% of people in the general area to which the theorem belongs. But it need not be this rigid. Jun 17 '12 at 3:08

Doesn't Zorn's Lemma count? Of course in ZF this is not a Theorem (rather it is undecidable), but in ZF+AC it is a real Theorem which is often mentioned without proof, especially in classes outside of mathematical logic. For example, in commutative algebra it is quoted in order to get enough maximal ideals in rings, etc.

Of course it is not hard to understand the proof of AC => Zorn, but many students take this on faith. I don't know if this also applies to mathematicians.

• I admit that I take it on faith. Jun 14 '12 at 9:51
• Right, but besides Zorn's lemma, some tricky applications of it also count, such as proving that any vector space (over any field) has a basis, or that any Banach space (real or complex) has an orthonormal basis. Jun 14 '12 at 9:53
• @Zsban: What do you mean by "tricky"? Existence of (orthonormal) bases is a trivial consequence of Zorn's lemma and I guess that everyone knows how that works. Jun 14 '12 at 10:10
• Okay, but in ZF+Zorn's lemma it's a tautology! I don't think in practice most people use specifically the fact that AC implies Zorn's lemma but just the fact that it's generally considered okay to prove results that depend on Zorn's lemma. Jun 14 '12 at 10:30
• @Qiaochu: I agree with that. Jun 14 '12 at 11:20

For a long time, the Littlewood-Richardson rule has been a black box. See van Leeuwen's wonderful article for its history (and a rather involved, even if enlightening proof). This really changed with Stembridge's 2-pages long slick (although far from straightforward!) proof (2002) and Gasharov's 3-pages long proof (1998). (I have read Stembridge and can vouch for its good exposition; it's not short by virtue of being unreadable, but short by virtue of being short. I have not yet read Gasharov, and I am in the middle of van Leeuwen.)

In theoretical computer science, possibly the best example is the PCP Theorem: it's used all over the place, from cryptography to quantum computing, yet very few of us understand the details (especially for the strong, "modern" versions of it).

• Is Dinur's proof not really well-understood by practitioners in this area? Jun 18 '12 at 23:39
• Her proof is certainly well-understood at a high level, and it's also certainly better-understood than the algebraic proof. But by the standard of how many people could fully reconstruct her proof within (say) two months, if locked in a room by a mad scientist with only pencils and blank paper ... well, the requisite experiment hasn't been done, and I shouldn't speak for everyone else, but I wouldn't want to be put to the test. :-) Jun 19 '12 at 6:15

Recognizing hamiltonian graphs is NP-complete.

(A hamiltonian graph is a graph that has a cycle passing through every node.) Everyone likes to use this theorem for proving other NP-completeness proofs, but few people would know an actual proof. Even the simplest proof is somewhat messy. The theorem that 3-colorable graphs are NP-complete is similar.

• Probably the unsolvability of Hilbert's 10th goes here as well. Jun 14 '12 at 0:30
• It's not very hard to get from colourability to 3-SAT - I don't claim that there is an obvious gadget construction, but if you play around for a bit you can find one of the (many) options easily enough. And the proof that 3-SAT is NP-complete is quite nice and conceptual. Mar 28 '17 at 13:31

C*-algebra theory has a number of good examples of this.

• Voiculescu's theorem: an ample representation of a C*-algebra essentially absorbs any nondegenerate representation
• Kasparov's technical theorem: if anybody really cares, I'll repeat the statement. The point is that anybody who works with bivariant K-theory uses this result ALL THE TIME, e.g. for excision or the existence of Kasparov products.
• Stinespring's theorem: any completely positive map into $B(H)$ dilates to a representation

I have been using Voicalescu's theorem and KTT for a about a year or so longer than I knew the proofs. I probably still wouldn't know the proofs if it hadn't become necessary. Stinespring's theorem is probably better known among the people who use it because it's not so difficult, but it could be tempting to use it as a black box.

• Nice answers. An addendum/afterthought: it probably isn't used very often by practising operator algebraists, but the equivalence of nuclearity and amenability for C*-algebras gets invoked a lot of the time by people in Banach algebras, and I rather doubt many of them have actually worked through all the details. Jun 15 '12 at 0:26

There are a lot of complicated 'motivic' statements. I would say that the Milnor Conjecture (and its generalization, the Bloch-Kato conjecture) are easy to understand and apply; yet its proof is very hard.

I've already posted this as a question on MathOverflow, but it appears that everyone working on the Ricci flow, as well as other geometric heat flows, takes it for granted the existence in short time of a solution to a nonlinear parabolic PDE on a vector bundle over a complete Riemannian manifold. I have not been able to find a complete proof for even a linear parabolic PDE.

• I understand where you're coming from, because I doubt anyone has published the details of this argument for, say, Ricci flow or mean curvature flow. BUT I expect that a lot of people who work in the field really do understand the argument, which is to reduce nonlinear existence to linear existence using approximation. Terry Tao actually sketched this in his lecture notes terrytao.wordpress.com/2008/03/28/285g-lecture-1-ricci-flow See Remark 2. As for linear parabolic existence, I'm not sure what you mean. What about Evans, for example? Jun 15 '12 at 20:30
• Dan, the reduction of nonlinear to linear is a reasonably straightforward argument. And maybe solving a linear parabolic system on a complete Riemannian manifold is, too. I haven't tried that hard but it seems like the infinite speed of propagation makes it trickier to reduce the proof to an open set in $R^n$. Or is that not so? Jun 15 '12 at 21:51
• I didn't scan the word "complete" properly and consequently misunderstood you, so I apologize for that. Frequently, one can solve a parabolic equation on a complete Riemannian manifold by taking the limit of solutions on a compact exhaustion with Dirichlet boundary conditions. For example, this works for the linear heat equation and also for Ricci-deTurck flow (with bounded curvature). Also, in the linear self-adjoint case (with time-independent coefficients), I think that general nonsense let's you construct a heat kernel via exponentiation of operators. Jun 18 '12 at 18:48
• Btw, the original purpose of Shi's Ricci flow estimates was to prove that this limit makes sense for Ricci-deTurck flow (with bounded curvature). I agree that Shi's short-time existence result is a black box that is not so widely known, but I should point out that many who work in Ricci flow don't need to quote this result, e.g. I don't believe it is needed to prove geometrization, uniformization (compact case), the differential sphere theorem, or most of Hamilton's big results. Jun 18 '12 at 18:49

Determinacy of Borel Games seems like a good example of this.

• Is this really a good example? The proof, especially the inductive version, is not particularly difficult, and my understanding is that descriptive set theorists - i.e., the ones who would use it - do tend to know it. Jun 13 '12 at 22:01
• In fact I was more thinking of computer scientists and game theorists, who often use this as a hammer to have determinacy, although I think few know the proof. But you are right that this would probably not qualify as a "blackbox theorem" for people of set theory. Jun 14 '12 at 12:43
• I didn't know cs people used Borel determinacy. Are there any easy-to-understand examples of this? Jun 14 '12 at 23:16
• For instance in automata theory, models of alternating automata on infinte structures (like words or trees) are often used. The accepting condition is typically Borel (see for instance en.wikipedia.org/wiki/Parity_game), so thanks to Martin's Theorem, we can define in a sound way the language recognized by such an automaton as the sets of inputs where Player I wins, and the complement is the set of inputs where Player II wins. Jun 16 '12 at 13:40

Most mathematicians can recite the construction of a Vitali set and state that the axiom of choice is needed. Very few of them would know to describe the proof that the axiom of choice is really needed, i.e. Solovay's model (or even the Feferman-Levy in which every set is Borel).

• But how much is the necessity of AC actually used? Within set theory it is used, but I would imagine set theorists could describe Solovay's model. Is the necessity of AC used outside of set theory? Jun 13 '12 at 23:17
• By using the consistency of these exotic models, you can conclude that all sets are measurable, which sounds convenient. I'm not sure I've ever seen anyone do this, but Thurston does something more extreme in his notes: he uses the consistency of constructive math, in which all functions are continuous, to conclude that a particular function is continuous. Not only do I not know this black box, I don't know how to check that the rest of the argument is actually constructive. I'd be (less) nervous about checking that an argument doesn't use the axiom of choice. Jun 14 '12 at 1:47
• Noah S, I cannot say about actual research but I can testify about teaching (from the studential side) that I saw this argument (and similar AC uses) in several courses. While not "active research" I do think that teaching is part of the work of most mathematicians. Jun 14 '12 at 5:40
• Fair, but is the specific result (that AC is needed to construct a Vitali set) important, or is it the general fact that constructing "pathological" objects often cannot be done within ZF that the teacher actually cares about? (And I agree with you wholeheartedly re: teaching as part of mathematics.) Jun 14 '12 at 9:43
• Noah, the importance of non-measurable sets is - in my view - the same importance of Russell's paradox. These things tell us that we cannot always talk about "everything" and we must limit ourselves to smaller and better-behaved objects. Jun 14 '12 at 10:21

Fixed point theorems (such as Brouwer and Kakutani's) are very frequently invoked, specially in Econ. I am not sure how many people are familiar with the proofs. There are many nice proofs available, by the way.

• Is Brouwer's fixed point theorem not taught in nearly every introductory algebraic topology course as a rather simple application of homology? Jun 19 '12 at 23:05

The Borel isomorphism theorem says that any two Polish (complete and separable metrizable) spaces endowed with their Borel $\sigma$-algebra are isomorphic as measurable spaces if and only if they have the same cardiality and this cardinality is either countable or the cardinality of the continuum.

The result is extremely useful and widely applied in probability theory. It allows one to prove many results for general Polish spaces by proving them for the real line or the unit interval. The proof is actually not that hard, but somewhat messy and gives little useable insight for those not working in descriptive set theory.

• Isn't the proof for $\Rightarrow$ the usual back-and-forth trick? Jun 14 '12 at 8:30
• Pretty much, but one usually does this with respect to the Baire space $\mathbb{N}^\mathbb{N}$, that one doesn't use much as a probabilist. Jun 14 '12 at 16:30

The Lovasz Local Lemma gives a very simple criterion for when certain random events have positive probability. Almost all applications of the Lemma automatically have an algorithm to find such events. The details of these proofs (especially in their most general forms) can be messy, but the LLL criterion is so simple you can use it basically as a black box.

Chevalley's theorem: any algebraic group is the extension of a linear algebraic group by an abelian variety.

The sharp Sobolev inequality of Aubin and Talenti plays a critical role in many important theorems in geometric analysis, including the Yamabe problem. Using the co-area formula, it is easy to reduce the proof to proving the inequality for functions on $R^n$ that are a function of the distance to the origin only. This is a $1$-dimensional inequality. But the proofs of this 1-d inequality given by Aubin and Talenti are extremely hard to follow. At least one of them simply cites a paper by Bliss that uses techniques of calculus of variations that I find rather obscure. For this reason, I believe very few people who have used and cited the Aubin-Talenti inequality have ever understood its full proof.

The situation, however, has improved. For those who know the details of the construction of the so-called Brenier map in optimal transportation, there is a full proof of the Aubin-Talenti inequality in a beautiful paper by Cordero-Nazaret-Villani.

For those who do not want to learn the full details of the Brenier map, my collaborators and I have included our paper titled "Sharp Affine $L_p$ Sobolev Inequalities" the full details of the Cordero-Nazaret-Villani proof applied to the 1-dimensional Bliss inequality. In this case, the Brenier map can be constructed using only the fundamental theorem of calculus.

What about Carleson's theorem that Fourier series of $L^2$ functions converge almost everywhere? I don't read the right literature to see whether this is frequently invoked, but it seems like a useful tool to have.

• I have a feeling that it isn't used that much per se, but rather is there to set the limits/scope of various theorems, and to motivate generalizations. However, I'm not really in the right circles to make an adequate judgment Jun 17 '12 at 9:10

The Cohen-Structure theorem in commutative algebra (classifying complete local rings in some sense).

I've got to put in 2c for ergodic theory: the Multiplicative Ergodic Theorem is widely quoted, but locating a complete proof is hard.

Saharon Shelah has a series of results he actually calls "black boxes," and uses accordingly (see his paper, "Black Boxes," http://arxiv.org/abs/0812.0656); my understanding is that these are Diamond-like theorems that are provable in ZFC.

(Diamond, for clarification, is a sort of guessing principle: it asserts that there exists a single sequence $(A_\alpha)_{\alpha\in\omega_1}$ such that $A_\alpha\subseteq\alpha$ such that, for any $A\subseteq \omega_1$, the set $$\lbrace \alpha: A_\alpha=A\cap\alpha\rbrace$$ is "large" (specifically, stationary - intersects every closed unbounded subset of $\omega_1$). This principle is not provable in ZFC; it follows from $V=L$ and implies $CH$, but both of these implications are strict. My understanding, which is quite limited, is that Diamond is used in constructions of $\omega_1$-sized structures where one needs to "guess correctly" stationarily often, and that Shelah developed the black boxes to perform many of these same constructions in ZFC alone.)

• I'm not sure whether Shelah's result about undecidability of MSO over reals is concerned by your post, but it's another good example. Jun 14 '12 at 12:45
• Another result of Shelah which may fit in this list is the Main Gap Theorem.
– Haim
Jun 14 '12 at 15:44
• Also the whole family of preservation theorems for countable support iterations of proper forcings can be used without understanding their proofs, and I suspect several people doing forcing (myself included) do use them extensively before feeling the need to actually go and check/understand the proofs. May 16 '16 at 12:05

I think the solution to Hilberts 5th problem is an example. For a while Gromov's polynomial growth theorem was an example because the proof invoked Hilberts 5th.

• This is a good example (I learned Gromov's proof as a student, but not Montgomery-Zippin/Gleason), but I'm not sure how many applications it's had. Recently, though, Green and Tao have had to generalize Montgomery-Zippin for applications, but they've had to delve into the details of the proof, so maybe the situation will be rectified. Jun 14 '12 at 17:27
• There are some theorems in "abstract" non-commutative harmonic analysis, where people use approximation of connected groups by Lie groups, in order to then make use of structure theory. I think one example might be the result of Dixmier-as-written-up-by-Connes that the von Neumann algebra of a connected group is injective. Whether or not this counts as an "application" is I guess debatable Jun 15 '12 at 8:34

The proof for Hilbert's tenth problem, that is, that there is no algorithm to solve general Diophantiane equations.

Benjamin Steinberg has mentioned this above in a comment. I believe the proof is complicated.

• Does this really qualify? Benjamin writes: "I mean a theorem that is often applied". How can you apply a Theorem which says that you cannot solve some general equation? In specific situations, you might be able to do so (perhaps even via algebraic stacks mathoverflow.net/questions/96957). Jun 14 '12 at 10:13
• @Martin: The MRDP theorem says much more, namely that every r.e. set is Diophantine, and it (and its formalized versions in fragments of arithmetic) does in fact have useful applications in logic. Jun 14 '12 at 11:01
• In a similar vein, the word problem for groups? Jun 14 '12 at 11:48
• @Emil: Thank you, I didn't know that. I was only refering to the content of the answer. Jun 14 '12 at 14:18
• It is quite common in group theory to reduce algorithmic problems involving nilpotent groups to Hilberts 10th Jun 14 '12 at 23:49

Fundamental lemma (Langlands program) which Ngô Bảo Châu proved and got the Fields medal in 2010.

Slightly debatable, but my impression is that the fact that injectivity, Property (P), and hyperfiniteness define the same class of von Neumann algebras is used by many people without feeling the need to learn the proofs.

In several complex variables it is often desired to be able to solve the $\bar\partial$ equation. The standard tool for that is Hörmander's $L^2$ method and though I suppose that most who use it have at some point read at least a sketch of the proof, most probably aren't familiar with the tedious details that go into the proof.

Two results I have seen used without proof in undergraduate lectures were:

In both cases the proofs are not long, but were deemed not useful enough to be taught. I am wondering whether this is special to the courses I had or generally common.

Also, various courses on graph theory use some versions of the Jordan curve theorem; even the ones not requiring analysis (speaking of piecewise linear paths) are usually not proven. And several analysis courses don't prove the basic properties of real numbers, instead treating them as axioms.

• I agree with Tychonoff, but don't agree with Caratheodory. Jun 14 '12 at 18:04
• I don't think that Tychonoff is a good example. After all, the professor surely knew the proof(s). He just chose not to show them to the students. Jun 15 '12 at 9:10

The Open Mapping Theorem (known as Banach-Schauder Theorem) is used daily by zillions of analysts. But its proof is far from trivial and is often overlooked by users. It is not just a straightforward consequence of Baire's Theorem.

• I think you are overestimating the difficulty of its proof. While it is not trivial, it is something standard and covered without any problem in a functional analysis course. If the proof is overlooked, that's probably usually because of, well, oversight, not because it is too complicated to be understood by the ordinary analyst. Jun 14 '12 at 16:49
• Certainly this was a standard part of the graduate analysis sequence at Stanford. Jun 14 '12 at 23:47
• Slightly contrary to the previous comments: although this does not quite fit the OP's original description as something whose proof is understood by relatively few who use it, it (or the closed graph theorem) get used all the time by algebraic functional analysts with no thought whatsoever for the two-step process used in its proof, or for its generalizations to other TVS. In that sense it is treated as a black box. Jun 15 '12 at 4:04

Many people apply the theorem $1+1=2$, but how many understand in detail the proof given by Russell and Whitehead in Principia Mathematica? Well, I suppose there are other proofs available....

• Does "by definition of the interpretation o the symbol $2$." counts as a proof? Jun 15 '12 at 16:32

How about Haynes Miller's theorem resolving the Sullivan conjecture?

The fact that every von Neumann algebra is the direct integral of factors. Every operator algebraist knows this, and could probably more or less explain the proof, but the details are tedious (and kind of useless in practice.) There are similar facts about decomposition of non-singular actions into ergodic ones and representation into irreducible representations.

• Separable predual? Jun 30 '12 at 1:05

Does FLT count?

• Maybe the modularity theorem counts, but I wouldn't say FLT does. Jun 13 '12 at 21:32
• Sounds reasonable; Feel free to edit.
– Dirk
Jun 14 '12 at 9:45
• Dirk, the reason FLT doesn't count is that it is almost never used.
– Joël
Jun 14 '12 at 23:14