69
$\begingroup$

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.

$\endgroup$
25
  • 17
    $\begingroup$ Godel's thesis comes to mind. $\endgroup$ Apr 24, 2018 at 7:39
  • 81
    $\begingroup$ Don't all PhD theses solve open problems...? $\endgroup$ Apr 24, 2018 at 7:42
  • 20
    $\begingroup$ @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?”. $\endgroup$ Apr 24, 2018 at 9:04
  • 9
    $\begingroup$ @NajibIdrissi: Not always: sometimes a thesis provides a new insight into an already solved problem, or a better way to solve it. Tate's thesis is the first to come to mind. $\endgroup$
    – Alex M.
    Apr 24, 2018 at 11:27
  • 6
    $\begingroup$ 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 $\endgroup$ Apr 24, 2018 at 13:32

24 Answers 24

113
$\begingroup$

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

$\endgroup$
8
  • 2
    $\begingroup$ Thank you for this very interesting answer on George Dantzig's story. $\endgroup$ Apr 24, 2018 at 7:54
  • 9
    $\begingroup$ 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 $\endgroup$
    – JohnEye
    Apr 24, 2018 at 10:20
  • 10
    $\begingroup$ That's freaking crazy. $\endgroup$
    – iammax
    Apr 24, 2018 at 18:45
  • 5
    $\begingroup$ If the problems were solved concurrently, why were they published 11 years apart? $\endgroup$
    – Michael
    Sep 25, 2018 at 20:39
  • 3
    $\begingroup$ @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." $\endgroup$ Sep 26, 2018 at 0:31
56
$\begingroup$

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!

$\endgroup$
2
  • 7
    $\begingroup$ I’d upvote this a dozen times if I could. As I understand it, we owe the modern theory of tensor products of topological vector spaces—and hence, in particular, the theory of nuclear topological vector spaces—entirely to Grothendieck’s PhD thesis. A quick sketch can be found, for instance, in this survey chapter by Fernando Bombal. $\endgroup$ Sep 30, 2020 at 0:00
  • $\begingroup$ I just skimmed the Ph.D. thesis of Noam Elkies. I don't think that the result you mentioned is in there. He did solve that problem of Euler's around the same time that he wrote his Ph.D. thesis, but the solution doesn't appear in his Ph.D. thesis as far as I can tell. $\endgroup$ Nov 26, 2022 at 18:27
37
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Sep 26, 2018 at 2:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – none
    Sep 26, 2018 at 7:11
37
+100
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ I never heard about this very great thesis. Thank you for this answer. $\endgroup$ May 20, 2018 at 19:12
  • $\begingroup$ @AliTaghavi: You are welcome. -- And thank YOU! $\endgroup$
    – Stefan Kohl
    Sep 11, 2022 at 18:52
34
$\begingroup$

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.

$\endgroup$
31
$\begingroup$

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

$\endgroup$
28
$\begingroup$

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.

$\endgroup$
25
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you very much for your very interesting answer and your attention to my question. $\endgroup$ Sep 10, 2022 at 19:16
24
$\begingroup$

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.

$\endgroup$
3
  • 7
    $\begingroup$ Just to clarify: this is not the Rota's conjecture, but a conjecture by Rota; which apparently also is known as Rota-Heron-Welsh conjecture. $\endgroup$
    – Max Horn
    Sep 29, 2020 at 22:08
  • 1
    $\begingroup$ Is this the work for which Huh was awarded a Fields medal? $\endgroup$ Aug 28, 2022 at 1:41
  • 1
    $\begingroup$ @GerryMyerson It was indeed one of the things for which he was awarded a Fields medal, according to the short citation. $\endgroup$ Nov 26, 2022 at 18:31
22
$\begingroup$

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/

$\endgroup$
19
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ +1 (!!!). The problem of computing the homotopy groups of spheres must be as old as Witold Hurewicz's definition of homotopy groups. Every single computation was a huge success, there were very few of them. Then Serre's revolution came. $\endgroup$
    – Wlod AA
    Nov 5, 2020 at 20:04
18
$\begingroup$

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

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
15
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 26, 2018 at 1:21
  • 2
    $\begingroup$ 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.) $\endgroup$ Sep 26, 2018 at 15:13
  • $\begingroup$ @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. $\endgroup$ Sep 26, 2018 at 23:02
12
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

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

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

$\endgroup$
1
  • $\begingroup$ I just now noticed that M. Khan suggested in a 2018 comment to the OP that Bhargava should be on this list. So here he is. $\endgroup$ Aug 30, 2022 at 21:28
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That is very interesting thank you but it does not satisfy the condition of at least 25 years of openness. I give the bounty to your answer and I will give another bounty to other recent answer which satisfy (i think) this c9nditiin $\endgroup$ Sep 3, 2022 at 20:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.