PhD dissertations that solve an established open problem

Question

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.

Answer 1

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

Answer 2

I am quite surprised that nobody has mentioned Grothendieck's thesis. Apparently Laurent Schwartz gave Grothendieck a recent paper listing a number of open problems in functional analysis at one of their initial meetings. (Schwartz had just won the Fields at the time.) Grothendieck went away for a few weeks/ months and then returned with solutions to many (or all?) of the questions. In the course of the next few years Grothendieck became one of the world's leading functional analysts, before turning his attention to algebraic geometry.

This is the story I heard as part of mathematical gossip many, many years ago. Maybe someone who is more knowledgeable can chime in.

Another utterly spectacular thesis was Noam Elkies'. Among other things he settled a 200 year old problem posed by Euler!

Answer 3

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.

Answer 4

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 non-isomorphic 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.

Answer 5

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.

Answer 6

Lisa Piccirillo, who recently obtained her PhD from the University of Texas, Austin, showed that the Conway knot is not slice, answering a relatively famous open problem in topology. You can read a popular account of her work in Quanta here: https://www.quantamagazine.org/graduate-student-solves-decades-old-conway-knot-problem-20200519/. Her paper proving this result was published in the Annals of Math; but I'm pretty sure it also constituted her dissertation (see https://gradschool.utexas.edu/news/studying-knots-and-four-dimensional-spaces).

Answer 7

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.

Answer 8

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,
Addison Wesley, Reading, Massachusetts, 1968.

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

Answer 9

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 Adiprasito, Huh and Katz (2015). As the dates would suggest, the thesis covers matroids over any field, but not the result on general matroids.

Answer 10

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: https://mathshistory.st-andrews.ac.uk/Biographies/Arnold/

Answer 11

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

Answer 12

Does Serre's (Jean-Pierre) thesis qualifies ? He computed there a lot of homotopy groups of spheres. But I don't know how old was this problem in 1951.

Answer 13

John Thompson's thesis solved the famous and long-standing conjecture that a Frobenius kernel is nilpotent in the late 1950s. Not only was this noteworthy enough to be reported in the New York Times, but many of the techniques developed in the thesis played a major role in shaping finite group theory for decades to come.

Answer 14

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.

Answer 15

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

Answer 16

Does Scholze's PhD thesis count, as if I remember rightly he applied perfectoid spaces to prove some important special case of Deligne's weight-monodromy conjecture? (Not an expert, correct me if I'm wrong).

Also I believe Mirzakhani gave a proof of the Witten conjecture when she was still a student, so I don't know if that proof is incorporated into her PhD thesis. Coincidentally, Kontsevich's proof of the Witten conjecture was also given in his PhD dissertation and then published as a journal article Intersection Theory on the Moduli Space of Curves and the Matrix Airy Function.

Edit: I have not read Mirzakhani's thesis, but it does indeed seem to be the case that she gave a new proof of Witten's conjecture in that thesis. Taken from the following article:

In 2002 I received a rather apologetic letter from Maryam, then a student at Harvard, together with a rough draft thesis and a request for comments. After reading only a few pages, I was transfixed. Starting with a formula discovered by Greg McShane in his 1991 Warwick PhD, she had developed some amazingly original and beautiful machinery which culminated in a completely new proof of Witten’s conjecture, a relation between integrable systems of Hamiltonian PDEs and the geometry of certain families of 2D topological field theories.

Answer 17

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.

Answer 18

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

    Proof of a Conjecture of Gauss on Class Number Two

See: https://en.wikipedia.org/wiki/Peter_J._Weinberger

Answer 19

Since the OP mentions Gauss, this entry could be an appropriate addition to the list:

Manjul Bhargava's PhD thesis, Higher composition laws (2001), concerns a problem going back to Gauss. In the nineteenth century, Gauss had discovered a fundamental composition law for binary quadratic forms which are homogeneous polynomial functions of degree two in two variables. No formula or law of the Gauss type was known for cubic or higher degree forms. Bhargava broke the impasse of 200 years by producing a composition law for cubic and higher degree forms.

What makes Bhargava’s work especially remarkable is that he was able to explain all his revolutionary ideas using only elementary mathematics. In commenting on Bhargava’s results Andrew Wiles, his Ph.D. advisor said “He did it in a way that Gauss himself could have understood and appreciated.”

[source1 and source2]

I found this interview from 2014, after Bhargava won the Fields medal, an inspiring read: "Somehow, he extracts ideas that are completely new or are retwisted in a way that changes everything. But it all feels very natural and unforced — it’s as if he found the right way to think.”

Answer 20

A bit surprised that Leslie F. Greengard has not been mentioned. His PhD thesis from Yale was supervised by Vladimir Rokhlin, and is often cited for the development of the fast multipole method (FMM) which reduces the computation of the electrostatic or gravitational potential field/force for an N-particle system from $O(N^2)$ to $O(N)$. Together with FFT, the Monte Carlo method, the simplex method for linear programming, Quicksort, QR algorithm, etc., FMM is regarded as one of the top 10 algorithms of the 20th century. To quote from the link,

This algorithm overcomes one of the biggest headaches of $N$-body simulations: the fact that accurate calculations of the motions of $N$ particles interacting via gravitational or electrostatic forces (think stars in a galaxy, or atoms in a protein) would seem to require $O(N^2)$ computations—one for each pair of particles. The fast multipole algorithm gets by with $O(N)$ computations. It does so by using multipole expansions (net charge or mass, dipole moment, quadrupole, and so forth) to approximate the effects of a distant group of particles on a local group. A hierarchical decomposition of space is used to define ever-larger groups as distances increase. One of the distinct advantages of the fast multipole algorithm is that it comes equipped with rigorous error estimates, a feature that many methods lack.

Answer 21

Maria Chudnovsky's PhD thesis gives a proof of the Strong Perfect Graph Conjecture. This is a conjecture of Claude Berge from 1961 (hence meets the 25 year criterion), and was considered one of the hardest and most important open problems in graph theory at the time. It is joint work with Neil Robertson, Paul Seymour, and Robin Thomas and was published in the Annals in 2006. See The strong perfect graph theorem.

Answer 22

I suppose my own thesis fulfils this. Let $M$ be a monoid generated by a finite set $A$ and defined by a single defining relation $w=1$. The language of all words $v \in A^\ast$ representing the identity element in $M$ is called the congruential language for $M$. If the congruential language for $M$ is a context-free language, then Louxin Zhang [1] proved that the group of all units (two-sided invertible elements) $U(M)$ of $M$ is a virtually free group.

Zhang then asked in 1992 (conference held in 1990) the following questions:

1. If $U(M)$ is virtually free, is the congruential language of $M$ a context-free language?
2. Is it decidable, taking $w$ as input, whether the congruential language of $M$ is context-free?

In Chapter 3 of my thesis, I give an affirmative answer to both questions. In fact, I generalise the answer to Question 1 to to all monoids defined by arbitrarily many relations of the form $w_i = 1$.

My thesis can be found on my website.

${}$

[1] Zhang, Louxin, Congruential languages specified by special string-rewriting systems, Ito, Masami (ed.), Words, languages and combinatorics, Kyoto, Japan, August 28–31, 1990. Singapore: World Scientific. 551-563 (1992). ZBL0875.68589.

Answer 23

Robin Moser in his PhD thesis found a constructive proof for the Lovasz Local Lemma, a problem that was essentially open for decades. This earned him a Godel Prize.

Answer 24

Bart Plumstead's 1979 thesis at Chicago included (among other things) proofs of all three of the Eisenbud-Evans conjectures, which were widely considered to be among the most significant open questions in commutative algebra at the time.