More Like this

1. Games with filters I

   https://doi.org/10.1142/S021906132450003X  

   Foreman, Matthew; Magidor, Menachem; Zeman, Martin (August 2023, Journal of Mathematical Logic)

   Chong, Chita; Feng, Qi; Slaman, Theodore_A; Woodin, W_Hugh (Ed.)

   This paper has two parts. The first is concerned with a variant of a family of games introduced by Holy and Schlicht, that we call Welch games. Player II having a winning strategy in the Welch game of length [Formula: see text] on [Formula: see text] is equivalent to weak compactness. Winning the game of length [Formula: see text] is equivalent to [Formula: see text] being measurable. We show that for games of intermediate length [Formula: see text], II winning implies the existence of precipitous ideals with [Formula: see text]-closed, [Formula: see text]-dense trees. The second part shows the first is not vacuous. For each [Formula: see text] between [Formula: see text] and [Formula: see text], it gives a model where II wins the games of length [Formula: see text], but not [Formula: see text]. The technique also gives models where for all [Formula: see text] there are [Formula: see text]-complete, normal, [Formula: see text]-distributive ideals having dense sets that are [Formula: see text]-closed, but not [Formula: see text]-closed. 

   more » « less
2. Coarse computability, the density metric, Hausdorff distances between Turing degrees, perfect trees, and reverse mathematics

   https://doi.org/10.1142/S0219061323500058  

   Hirschfeldt, Denis R; Jockusch, Carl G; Schupp, Paul E (August 2024, Journal of Mathematical Logic)

   For [Formula: see text], the coarse similarity class of A, denoted by [Formula: see text], is the set of all [Formula: see text] such that the symmetric difference of A and B has asymptotic density 0. There is a natural metric [Formula: see text] on the space [Formula: see text] of coarse similarity classes defined by letting [Formula: see text] be the upper density of the symmetric difference of A and B. We study the metric space of coarse similarity classes under this metric, and show in particular that between any two distinct points in this space there are continuum many geodesic paths. We also study subspaces of the form [Formula: see text] where [Formula: see text] is closed under Turing equivalence, and show that there is a tight connection between topological properties of such a space and computability-theoretic properties of [Formula: see text]. We then define a distance between Turing degrees based on Hausdorff distance in the metric space [Formula: see text]. We adapt a proof of Monin to show that the Hausdorff distances between Turing degrees that occur are exactly 0, [Formula: see text], and 1, and study which of these values occur most frequently in the senses of Lebesgue measure and Baire category. We define a degree a to be attractive if the class of all degrees at distance [Formula: see text] from a has measure 1, and dispersive otherwise. In particular, we study the distribution of attractive and dispersive degrees. We also study some properties of the metric space of Turing degrees under this Hausdorff distance, in particular the question of which countable metric spaces are isometrically embeddable in it, giving a graph-theoretic sufficient condition for embeddability. Motivated by a couple of issues arising in the above work, we also study the computability-theoretic and reverse-mathematical aspects of a Ramsey-theoretic theorem due to Mycielski, which in particular implies that there is a perfect set whose elements are mutually 1-random, as well as a perfect set whose elements are mutually 1-generic. Finally, we study the completeness of [Formula: see text] from the perspectives of computability theory and reverse mathematics. 

   more » « less
3. Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective

   https://doi.org/10.1090/memo/1457  

   Anglès_d’Auriac, Paul-Elliot; Cholak, Peter; Dzhafarov, Damir; Monin, Benoît; Patey, Ludovic (January 2024, Memoirs of the American Mathematical Society)

   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
4. Primitivity index bounds in free groups, and the second Chebyshev function

   https://doi.org/10.1142/S021819672350008X  

   Kapovich, Ilya; Simon, Zachary (February 2023, International Journal of Algebra and Computation)

   Motivated by results about “untangling” closed curves on hyperbolic surfaces, Gupta and Kapovich introduced the primitivity and simplicity index functions for finitely generated free groups, [Formula: see text] and [Formula: see text], where [Formula: see text], and obtained some upper and lower bounds for these functions. In this paper, we study the behavior of the sequence [Formula: see text] as [Formula: see text]. Answering a question from [17], we prove that this sequence is unbounded and that for [Formula: see text], we have [Formula: see text]. By contrast, we show that for all [Formula: see text], one has [Formula: see text]. In addition to topological and group-theoretic arguments, number-theoretic considerations, particularly the use of asymptotic properties of the second Chebyshev function, turn out to play a key role in the proofs. 

   more » « less
5. Finite State Mean Field Games with Wright-Fisher Common Noise as Limits of $$N$$-Player Weighted Games

   https://doi.org/10.1287/moor.2021.1230  

   Bayraktar, Erhan; Cecchin, Alekos; Cohen, Asaf; Delarue, François (March 2022, Mathematics of Operations Research)

   Forcing finite state mean field games by a relevant form of common noise is a subtle issue, which has been addressed only recently. Among others, one possible way is to subject the simplex valued dynamics of an equilibrium by a so-called Wright–Fisher noise, very much in the spirit of stochastic models in population genetics. A key feature is that such a random forcing preserves the structure of the simplex, which is nothing but, in this setting, the probability space over the state space of the game. The purpose of this article is, hence, to elucidate the finite-player version and, accordingly, prove that N-player equilibria indeed converge toward the solution of such a kind of Wright–Fisher mean field game. Whereas part of the analysis is made easier by the fact that the corresponding master equation has already been proved to be uniquely solvable under the presence of the common noise, it becomes however more subtle than in the standard setting because the mean field interaction between the players now occurs through a weighted empirical measure. In other words, each player carries its own weight, which, hence, may differ from [Formula: see text] and which, most of all, evolves with the common noise. 

   more » « less