An official website of the United States government
Milliken’s tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey’s theorem and its many variants and consequences. In this sense, Milliken’s tree theorem is paradigmatic of structural Ramsey theory, which seeks to identify the common combinatorial and logical features of partition results in general. Its investigation in this area has consequently been extensive. Motivated by a question of Dobrinen, we initiate the study of Milliken’s tree theorem from the point of view of computability theory. The goal is to understand how close it is to being algorithmically solvable, and how computationally complex are the constructions needed to prove it. This kind of examination enjoys a long and rich history, and continues to be a highly active endeavor. Applied to combinatorial principles, particularly Ramsey’s theorem, it constitutes one of the most fruitful research programs in computability theory as a whole. The challenge to studying Milliken’s tree theorem using this framework is its unusually intricate proof, and more specifically, the proof of the Halpern-Laüchli theorem, which is a key ingredient. Our advance here stems from a careful analysis of the Halpern-Laüchli theorem which shows that it can be carried out effectively (i.e., that it is computably true). We use this as the basis of a new inductive proof of Milliken’s tree theorem that permits us to gauge its effectivity in turn. The key combinatorial tool we develop for the inductive step is a fast-growing computable function that can be used to obtain a finitary, or localized, version of Milliken’s tree theorem. This enables us to build solutions to the full Milliken’s tree theorem using effective forcing. The principal result of this is a full classification of the computable content of Milliken’s tree theorem in terms of the jump hierarchy, stratified by the size of instance. As usual, this also translates into the parlance of reverse mathematics, yielding a complete understanding of the fragment of second-order arithmetic required to prove Milliken’s tree theorem. We apply our analysis also to several well-known applications of Milliken’s tree theorem, namely Devlin’s theorem, a partition theorem for Rado graphs, and a generalized version of the so-called tree theorem of Chubb, Hirst, and McNicholl. These are all certain kinds of extensions of Ramsey’s theorem for different structures, namely the rational numbers, the Rado graph, and perfect binary trees, respectively. We obtain a number of new results about how these principles relate to Milliken’s tree theorem and to each other, in terms of both their computability-theoretic and combinatorial aspects. In particular, we establish new structural Ramsey-theoretic properties of the Rado graph theorem and the generalized Chubb-Hirst-McNicholl tree theorem using Zucker’s notion of big Ramsey structure.
more »
« less
The Prime Number Theorem as a Capstone in a Complex Analysis Course
We present a detailed proof of the prime number theorem suitable for a typical undergraduate- or graduate-level complex analysis course. Our presentation is particularly useful for any instructor who seeks to use the prime number theorem for a series of capstone lectures, a scaffold for a series of guided exercises, or as a framework for an inquiry-based course. We require almost no knowledge of number theory, for our aim is to make a complete proof of the prime number theorem widely accessible to complex analysis instructors and their students. In particular, we highlight the potential pitfalls and subtleties that may catch the instructor unawares when using more terse sources.
more »
« less
- Award ID(s):
- 1800123
- PAR ID:
- 10233318
- Date Published:
- Journal Name:
- Journal of Humanistic Mathematics
- Volume:
- 11
- Issue:
- 1
- ISSN:
- 2159-8118
- Page Range / eLocation ID:
- 166 to 203
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)We investigate under what conditions holomorphic forms defined on the regular locus of a reduced complex space extend to holomorphic (or logarithmic) forms on a resolution of singularities. We give a simple necessary and sufficient condition for this, whose proof relies on the Decomposition Theorem and Saito’s theory of mixed Hodge modules. We use it to generalize the theorem of Greb-Kebekus-Kovács-Peternell to complex spaces with rational singularities, and to prove the existence of a functorial pull-back for reflexive differentials on such spaces. We also use our methods to settle the “local vanishing conjecture” proposed by Mustaţă, Olano, and Popa.more » « less
-
The goal of this note is to provide yet another proof of the following theorem of Golod: there exists an infinite finitely generated groupGsuch that every element ofGhas finite order. Our proof is based on the Nielsen–Schreier index formula and is simple enough to be included in a standard group theory course.more » « less
-
Karunakaran, S. S. (Ed.)This paper reports a qualitative study of how small group problem solving was enacted differently across sections of a multi-section undergraduate introduction to proof course. Common course materials, common guidelines for instruction, and weekly instructor meetings led by a faculty course coordinator supported similar instruction across sections, including an emphasis on in-class group work. But within that shared structure, classroom observations revealed important differences in how group work was introduced, organized, and managed. Our results focus on differences in the time allotted to group work, the rationale for group work, the selection and organization of groups, and aspects of student activity and participation. We suggest that these differences shaped different opportunities to learn proof writing in small groups. These results have implications for the design and teaching of collegiate mathematics courses where group work is a regular element of classroom work.more » « less
-
Developing online courses is a complex and time-consuming process that involves organizing a course into a sequence of topics and allocating the appropriate learning content within each topic. This task is especially difficult in complex domains like programming, due to the incremental nature of programming knowledge, where new topics extensively build upon domain concepts that were introduced in earlier lessons. In this paper, we propose a course-adaptive content-based recommender system that assists course authors and instructors in selecting the most relevant learning material for each course topic. The recommender system adapts to the deep prerequisite structure of the course as envisioned by a specific instructor, while unobtrusively deducing that structure from problem-solving examples that the instructor uses to present course concepts. We assessed the quality of recommendations and examined several aspects of the recommendation process by using three datasets collected from two different courses.While the presented recommender system was built for the domain of introductory programming, our course-adaptive recommendation approach could be used in a variety of other domains.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.5642/jhummath.202101.10
