# PhD dissertations that solve an established open problem

I search for a big list of open problems which have been solved in a PhD thesis by the Author of the thesis (or with collaboration of her/his supervisor).

In my question I search for every possible open problem but I prefer (but not limited) to receive answers about those open problems which had been unsolved for at least (about) 25 years and before the appearance of the ultimate solution, there had been significant attentions and efforts for solving it. I mean that the problem was not a forgotten problem.

If the Gauss proof of the fundamental theorem of algebra did not had a gap, then his proof could be an important example of such dissertations.

I ask the moderators to consider this question as a wiki question.

• Godel's thesis comes to mind. – user2277550 Apr 24 '18 at 7:39
• Don't all PhD theses solve open problems...? – Najib Idrissi Apr 24 '18 at 7:42
• @NajibIdrissi: This was also my reaction to this question. There are of course some theses that create the problems themselves, and then solve it. – Thomas Rot Apr 24 '18 at 8:26
• @NajibIdrissi: I understood this question to be about open problems in the narrow sense of a precise mathematical question that at least some researcher(s) have previously articulated and tried to answer, e.g. “what is the dimension of such-and-such space?”. Most theses I know only solve open problems only in a much broader sense: open-ended questions that researchers may have wondered about, like “what can we say about the homology of such-and-such space?”, or “can we develop a useful theory of homotopy-coherent diagrams in such-and-such setting?”. – Peter LeFanu Lumsdaine Apr 24 '18 at 9:04
• Eric Larson proved the Maximal Rank Conjecture (a significant problem in the algebraic geometry of curves) in his MIT PhD thesis this year: math.mit.edu/research/graduate/thesis-defenses-2018.php – Sam Hopkins Apr 24 '18 at 13:32

I find George Dantzig's story particularly impressive and inspiring.

While he was a graduate student at UC Berkeley, near the beginning of a class for which Dantzig was late, professor Jerzy Neyman wrote two examples of famously unsolved statistics problems on the blackboard. When Dantzig arrived, he assumed that the two problems were a homework assignment and wrote them down. According to Dantzig, the problems "seemed to be a little harder than usual", but a few days later he handed in completed solutions for the two problems, still believing that they were an assignment that was overdue.

Six weeks later, Dantzig received a visit from an excited professor Neyman, who was eager to tell him that the homework problems he had solved were two of the most famous unsolved problems in statistics. Neyman told Dantzig to wrap the two problems in a binder and he would accept them as a Ph.D. thesis.

The two problems that Dantzig solved were eventually published in: On the Non-Existence of Tests of "Student's" Hypothesis Having Power Functions Independent of σ (1940) and in On the Fundamental Lemma of Neyman and Pearson (1951).

• Thank you for this very interesting answer on George Dantzig's story. – Ali Taghavi Apr 24 '18 at 7:54
• For those who like the story, a Snopes article contains some interesting excerpts from an interview with George Dantzig: snopes.com/fact-check/the-unsolvable-math-problem – JohnEye Apr 24 '18 at 10:20
• That's freaking crazy. – iammax Apr 24 '18 at 18:45
• If the problems were solved concurrently, why were they published 11 years apart? – Michael Sep 25 '18 at 20:39
• @Michael --- Wikipedia explains that "Years later another researcher, Abraham Wald, was preparing to publish an article that arrived at a conclusion for the second problem, and included Dantzig as its co-author when he learned of the earlier solution." – Carlo Beenakker Sep 26 '18 at 0:31

Godel's Completeness Theorem, was part of his PHD thesis.

It was definitely an active field of research, but I don't know to what degree the problem was an open one, in the way we understand it today.

.. when Kurt Gödel joined the University of Vienna in 1924, he took up theoretical physics as his major. Sometime before this, he had read Goethe’s theory of colors and became interest in the subject. At the same time, he attended classes on mathematics and philosophy as well. Soon he came in contact with great mathematicians and in 1926, influenced by number theorist Philipp Furtwängler, he decided to change his subject and take up mathematics. Besides that, he was highly influenced by Karl Menger’s course in dimension theory and attended Heinrich Gomperz’s course in the history of philosophy.

Also in 1926, he entered the Vienna Circle, a group of positivist philosophers formed around Moritz Schlick, and until 1928, attended their meetings regularly. After graduation, he started working for his doctoral degree under Hans Hahn. His dissertation was on the problem of completeness.

In the summer of 1929, Gödel submitted his dissertation, titled ‘Über die Vollständigkeit des Logikkalküls’ (On the Completeness of the Calculus of Logic). Subsequently in February 1930, he received his doctorate in mathematics from the University of Vienna. Sometime now, he also became an Austrian citizen.

• I don't know whether this specific question was open, but it is certainly in the family of open problems highlighted by Hilbert's 2nd Problem and the Entscheidungsproblem. – Joshua Grochow Sep 26 '18 at 2:37
• It was an open problem (posed by Hilbert and Ackermann) but only a few years earlier. It also falls out of earlier results by Skolem. – none Sep 26 '18 at 7:11

Scott Aaronson's thesis, Limits on Efficient Computation in the Physical World, refuted some popular wisdom.

In the first part of the thesis, I attack the common belief that quantum computing resembles classical exponential parallelism, by showing that quantum computers would face serious limitations on a wider range of problems than was previously known. In particular, any quantum algorithm that solves the collision problem -- that of deciding whether a sequence of $n$ integers is one-to-one or two-to-one -- must query the sequence $\Omega(n^{1/5})$ times. This resolves a question that was open for years; previously no lower bound better than constant was known. A corollary is that there is no "black-box" quantum algorithm to break cryptographic hash functions or solve the Graph Isomorphism problem in polynomial time.

There was even a second part to that thesis...

...Next I ask what happens to the quantum computing model if we take into account that the speed of light is finite -- and in particular, whether Grover's algorithm still yields a quadratic speedup for searching a database. Refuting a claim by Benioff, I show that the surprising answer is yes.

John von Neumann's dissertation seems to be an example with just the right timing.

But at the beginning of the 20th century [in 1901, to be precise], efforts to base mathematics on naive set theory suffered a setback due to Russell's paradox (on the set of all sets that do not belong to themselves). The problem of an adequate axiomatization of set theory was resolved implicitly about twenty years later by Ernst Zermelo and Abraham Fraenkel [i.e. there was active research on the question]. Zermelo–Fraenkel set theory provided a series of principles that allowed for the construction of the sets used in the everyday practice of mathematics, but they did not explicitly exclude the possibility of the existence of a set that belongs to itself. In his doctoral thesis of 1925, von Neumann demonstrated two techniques to exclude such sets—the axiom of foundation and the notion of class.

The axiom of foundation proposed that every set can be constructed from the bottom up in an ordered succession of steps by way of the principles of Zermelo and Fraenkel. If one set belongs to another then the first must necessarily come before the second in the succession. This excludes the possibility of a set belonging to itself. To demonstrate that the addition of this new axiom to the others did not produce contradictions, von Neumann introduced a method of demonstration, called the method of inner models, which later became an essential instrument in set theory.

The second approach to the problem of sets belonging to themselves took as its base the notion of class, and defines a set as a class which belongs to other classes, while a proper class is defined as a class which does not belong to other classes. Under the Zermelo–Fraenkel approach, the axioms impede the construction of a set of all sets which do not belong to themselves. In contrast, under the von Neumann approach, the class of all sets which do not belong to themselves can be constructed, but it is a proper class and not a set.

Van Heijenoort, Jean (1967). From Frege to Gödel: a Source Book in Mathematical Logic, 1879–1931. Cambridge, Massachusetts: Harvard University Press. ISBN 978-0-674-32450-3. OCLC 523838.

A question, a book, and a couple of dissertations; the most relevant, I think, is the thesis by Petkovšek. Hopefully this is an acceptable MO answer. First, the question comes from Knuth in The Art of Computer Programming:

[50] Develop computer programs for simplifying sums that involve binomial coefficients.

Exercise 1.2.6.63 in
The Art of Computer Programming, Volume 1: Fundamental Algorithms
by Donald E. Knuth,

(For those unfamiliar, there is a pseudo log scale to rate each problem such that [50], as above, is the most difficult exercise, expected to take some years to answer).

A solution to this exercise is given by the book A = B by Marko Petkovsek, Herbert Wilf, and Doron Zeilberger (fully availble from the linked page).

On page 29 of the book, the authors mention a Ph.D. dissertation, and one of the author's Ph.D. thesis (among a few other works) that provide the main content of the book:

[Fase45] is the Ph.D. dissertation of Sister Mary Celine Fasenmyer, in 1945. It showed how recurrences for certain polynomial sequences could be found algorithmically. (See Chapter 4.)

...

[Petk91] is the Ph.D. thesis of Marko Petkovšek, in 1991. In it he discovered the algorithm for deciding if a given recurrence with polynomial coefficients has a "simple" solution, which, together with the algorithms above, enables the automated discovery of the simple evaluation of a given definite sum, if one exists, or a proof of nonexistence, if none exists (see Chapter 8). A definite hypergeometric sum is one of the form $f(n) = \sum^{\infty}_{k=-\infty} F(n, k)$, where $F$ is hypergeometric.

Sources are

[Fase45] Fasenmyer, Sister Mary Celine, Some generalized hypergeometric polynomials, Ph.D. dissertation, University of Michigan, November, 1945.

[Petk91] Petkovšek, M., Finding closed-form solutions of difference equations by symbolic methods, Ph.D. thesis, Carnegie-Mellon University, CMU-CS-91-103, 1991.

June Huh's recent proof of Rota's conjecture (stated by Read in 1968 for graphical matroids and Rota in 1971 for all matroids) formed his 2014 Ph. D. thesis. For matroids over $$\mathbb{C}$$, this appeared first in Huh's 2010 preprint; for matroids over any field, this appeared in his work with Eric Katz (2011); for arbitrary matroids, see Adaprasito, Huh and Katz (2015). As the dates would suggest, the thesis covers matroids over any field, but not the result on general matroids.

The thesis of Martin Hertweck answered the at that time 60-years-old isomorphism problem for integral group rings in the negative, by constructing a counterexample. That is, a pair of finite groups $G$ and $H$ such that the group rings $\mathbb{Z}G$ and $\mathbb{Z}H$ are isomorphic. This result has been published afterwards in the Annals of Mathematics.

A very recent example is Eric Larson's 2018 dissertation The maximal rank conjecture [Lar1], which proves the following old conjecture:

Conjecture. (Maximal rank conjecture) Let $$C \subseteq \mathbb P^r$$ be a general Brill-Noether¹ curve. Then the restriction map $$H^0(\mathbb P^r, \mathcal O_{\mathbb P^r}(k)) \to H^0(C, \mathcal O_C(k))$$ has maximal rank, i.e. is injective if $$h^0(\mathbb P^r, \mathcal O(k)) \leq h^0(C, \mathcal O(k))$$ and surjective otherwise.

Historical remarks. Although I have been unable to find a definite place where this conjecture was stated, it is attributed to M. Noether by Arbarello and Ciliberto [AC83, p. 4]. Cases of the problem have been studied by M. Noether [Noe82, §8], Castelnuovo [Cas93, §7], and Severi [Sev15, §10].

In modern days, the conjecture had regained attention by 1982 [Har82, p. 79]. Partial results from around that time are mentioned in the introduction to [Lar2].

Larson's work culminates a lot of activity, including many papers by himself with other authors. An overview of the proof and how the different papers fit together is given in [Lar3].

References.

[AC83] E. Arbarello and C. Ciliberto, Adjoint hypersurfaces to curves in $$\mathbb P^n$$ following Petri. In: Commutative algebra (Trento, 1981). Lect. Notes Pure Appl. Math. 84 (1983), p. 1-21. ZBL0516.14024.

[Cas93] G. Castelnuovo, Sui multipli di una serie lineare di gruppi di punti appartenente ad una curva algebrica. Palermo Rend. VII (1893), p. 89-110. ZBL25.1035.02.

[Har82] J. D. Harris, Curves in projective space. Séminaire de mathématiques supérieures, 85 (1982). Les Presses de l’Université de Montréal. ZBL0511.14014.

[Lar1] E. K. Larson, The maximal rank conjecture. PhD dissertation, 2018.

[Lar2] E. K. Larson, The maximal rank conjecture. Preprint, arXiv:1711.04906.

[Lar3] E. K. Larson, Degenerations of Curves in Projective Space and the Maximal Rank Conjecture. Preprint, arXiv:1809.05980.

[Noe82] M. Nöther, Zur Grundlegung der Theorie der algebraischen Raumcurven. Abh. d. K. Akad. d. Wissensch. Berlin (1882). ZBL15.0684.01.

[Sev15] F. Severi, Sulla classificazione delle curve algebriche e sul teorema d’esistenza di Riemann. Rom. Acc. L. Rend. 24.5 (1915), p. 877-888, 1011-1020. ZBL45.1375.02.

¹ Brill-Noether curves form a suitable component of the Kontsevich moduli space $$\overline M_g(\mathbb P^r, d)$$ of stable maps $$\phi \colon C \to \mathbb P^r$$ from a genus $$g$$ curve whose image has degree $$d$$.

• Unfortunately, the references given in [Larson2] (which I blindly copied) are not accurate. I have been unable to find the conjecture in either [Harris] or the Severi reference given therein. I spent a few hours trying to sort this out, which got me a bit closer, but I still didn't really find the original sources. I would be grateful if someone could clear this up. – R. van Dobben de Bruyn Sep 26 '18 at 1:21
• In arxiv.org/abs/1505.05460 Jensen and Payne cite "F. Severi. Sulla classificazione delle curve algebriche e sul teorema di esistenza di Riemann. Rend. R. Acc. Naz. Lincei, 24(5):887–888, 1915." and " J. Harris. Curves in projective space, volume 85 of Séminaire de Mathématiques Supérieures. Presses de l’Université de Montréal, Montreal, Que., 1982. With the collaboration of David Eisenbud" as sources for the Maximal Rank Conjecture. (By the way, I posted this example as a comment earlier- glad to see it upgraded into an answer.) – Sam Hopkins Sep 26 '18 at 15:13
• For anyone interested in what Brill-Noether theory is more generally, this expository article by Harris is really excellent: birs.ca/workshops/2014/14w5133/files/Osserman-reference.pdf – Sam Hopkins Sep 26 '18 at 15:14
• @SamHopkins: Thanks, I had found those as well. But they do not settle the question of the origin of the conjecture. If I understand the paper correctly, Severi does not state the general case as a conjecture. – R. van Dobben de Bruyn Sep 26 '18 at 23:02

Richard Laver's dissertation proved a long-standing conjecture of Fraïssé, that the scattered order types are well-quasi-ordered. But maybe that was not quite 25 years old at the time.

Vladimir Arnold's thesis was about his solution to Hilbert's 13th problem, which he had done a few years earlier. This info is missing from Wikipedia but some details are in Mactutor: http://www-history.mcs.st-and.ac.uk/Biographies/Arnold.html.

Stephen Bigelow showed that braid groups are linear in his thesis at Berkeley in 2000 (the paper had already appeared in 1999 in JAMS, but he included it in his thesis).

A recent and rather spectacular quasi-example is the Ph.D. thesis of María Pe (advisor Javier Fernández de Bobadilla), entitled “On the Nash Problem for Quotient Surface Singularities” (2011).

While it was not was the full solution of the Nash problem (dated back to 1968) it included great steps towards the full solution, eventually presented by María and Javier themselves in Annals of Math. in 2012.

Peter Weinberger's Ph.D. thesis is a superb example:

Proof of a Conjecture of Gauss on Class Number Two

• I couln't find this PhD thesis online. How is his strategy of proof? – user19475 Sep 27 '18 at 3:06
• @TKe, sorry, you need to ask a specialist, I am not (too bad). – Wlod AA Sep 27 '18 at 7:29