More Like this

1. The exact consistency strength of the generic absoluteness for the universally Baire sets

   https://doi.org/10.1017/fms.2023.127  

   Sargsyan, Grigor; Trang, Nam (January 2024, Forum of Mathematics, Sigma)

   Abstract A set of reals isuniversally Baireif all of its continuous preimages in topological spaces have the Baire property.$$\mathsf {Sealing}$$is a type of generic absoluteness condition introduced by Woodin that asserts in strong terms that the theory of the universally Baire sets cannot be changed by forcing. The$$\mathsf {Largest\ Suslin\ Axiom}$$($$\mathsf {LSA}$$) is a determinacy axiom isolated by Woodin. It asserts that the largest Suslin cardinal is inaccessible for ordinal definable bijections. Let$$\mathsf {LSA-over-uB}$$be the statement that in all (set) generic extensions there is a model of$$\mathsf {LSA}$$whose Suslin, co-Suslin sets are the universally Baire sets. We show that over some mild large cardinal theory,$$\mathsf {Sealing}$$is equiconsistent with$$\mathsf {LSA-over-uB}$$. In fact, we isolate an exact large cardinal theory that is equiconsistent with both (see Definition 2.7). As a consequence, we obtain that$$\mathsf {Sealing}$$is weaker than the theory ‘$$\mathsf {ZFC} +$$there is a Woodin cardinal which is a limit of Woodin cardinals’. A variation of$$\mathsf {Sealing}$$, called$$\mathsf {Tower\ Sealing}$$, is also shown to be equiconsistent with$$\mathsf {Sealing}$$over the same large cardinal theory. The result is proven via Woodin’s$$\mathsf {Core\ Model\ Induction}$$technique and is essentially the ultimate equiconsistency that can be proven via the current interpretation of$$\mathsf {CMI}$$as explained in the paper. 

   more » « less
2. THE TREE PIGEONHOLE PRINCIPLE IN THE WEIHRAUCH DEGREES

   https://doi.org/10.1017/jsl.2025.11  

   DZHAFAROV, DAMIR D; SOLOMON, REED; VALENTI, MANLIO (February 2025, The Journal of Symbolic Logic)

   Abstract We study versions of the tree pigeonhole principle,$$\mathsf {TT}^1$$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether$$\mathsf {TT}^1$$is$$\Pi ^1_1$$-conservative over the ordinary pigeonhole principle,$$\mathsf {RT}^1$$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination with other results, we use this to show that unlike$$\mathsf {RT}^1$$, the problem$$\mathsf {TT}^1$$is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of$$\mathsf {TT}^1$$. 

   more » « less
3. On the weight zero compactly supported cohomology of H_{g,n}

   https://doi.org/10.1017/fms.2024.53  

   Brandt, Madeline; Chan, Melody; Kannan, Siddarth (January 2024, Forum of Mathematics, Sigma)

   Abstract For$$g\ge 2$$and$$n\ge 0$$, let$$\mathcal {H}_{g,n}\subset \mathcal {M}_{g,n}$$denote the complex moduli stack ofn-marked smooth hyperelliptic curves of genusg. A normal crossings compactification of this space is provided by the theory of pointed admissible$$\mathbb {Z}/2\mathbb {Z}$$-covers. We explicitly determine the resulting dual complex, and we use this to define a graph complex which computes the weight zero compactly supported cohomology of$$\mathcal {H}_{g, n}$$. Using this graph complex, we give a sum-over-graphs formula for the$$S_n$$-equivariant weight zero compactly supported Euler characteristic of$$\mathcal {H}_{g, n}$$. This formula allows for the computer-aided calculation, for each$$g\le 7$$, of the generating function$$\mathsf {h}_g$$for these equivariant Euler characteristics for alln. More generally, we determine the dual complex of the boundary in any moduli space of pointed admissibleG-covers of genus zero curves, whenGis abelian, as a symmetric$$\Delta $$-complex. We use these complexes to generalize our formula for$$\mathsf {h}_g$$to moduli spaces ofn-pointed smooth abelian covers of genus zero curves. 

   more » « less
4. Almost Everywhere Behavior of Functions According to Partition Measures

   https://doi.org/10.1017/fms.2023.130  

   Chan, William; Jackson, Stephen; Trang, Nam (January 2024, Forum of Mathematics, Sigma)

   Abstract This paper will study almost everywhere behaviors of functions on partition spaces of cardinals possessing suitable partition properties. Almost everywhere continuity and monotonicity properties for functions on partition spaces will be established. These results will be applied to distinguish the cardinality of certain subsets of the power set of partition cardinals. The following summarizes the main results proved under suitable partition hypotheses.•If$$\kappa $$is a cardinal,$$\epsilon < \kappa $$,$${\mathrm {cof}}(\epsilon ) = \omega $$,$$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$$and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the almost everywhere short length continuity property: There is a club$$C \subseteq \kappa $$and a$$\delta < \epsilon $$so that for all$$f,g \in [C]^\epsilon _*$$, if$$f \upharpoonright \delta = g \upharpoonright \delta $$and$$\sup (f) = \sup (g)$$, then$$\Phi (f) = \Phi (g)$$.•If$$\kappa $$is a cardinal,$$\epsilon $$is countable,$$\kappa \rightarrow _* (\kappa )^{\epsilon \cdot \epsilon }_2$$holds and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the strong almost everywhere short length continuity property: There is a club$$C \subseteq \kappa $$and finitely many ordinals$$\delta _0, ..., \delta _k \leq \epsilon $$so that for all$$f,g \in [C]^\epsilon _*$$, if for all$$0 \leq i \leq k$$,$$\sup (f \upharpoonright \delta _i) = \sup (g \upharpoonright \delta _i)$$, then$$\Phi (f) = \Phi (g)$$.•If$$\kappa $$satisfies$$\kappa \rightarrow _* (\kappa )^\kappa _2$$,$$\epsilon \leq \kappa $$and$$\Phi : [\kappa ]^\epsilon _* \rightarrow \mathrm {ON}$$, then$$\Phi $$satisfies the almost everywhere monotonicity property: There is a club$$C \subseteq \kappa $$so that for all$$f,g \in [C]^\epsilon _*$$, if for all$$\alpha < \epsilon $$,$$f(\alpha ) \leq g(\alpha )$$, then$$\Phi (f) \leq \Phi (g)$$.•Suppose dependent choice ($$\mathsf {DC}$$),$${\omega _1} \rightarrow _* ({\omega _1})^{\omega _1}_2$$and the almost everywhere short length club uniformization principle for$${\omega _1}$$hold. Then every function$$\Phi : [{\omega _1}]^{\omega _1}_* \rightarrow {\omega _1}$$satisfies a finite continuity property with respect to closure points: Let$$\mathfrak {C}_f$$be the club of$$\alpha < {\omega _1}$$so that$$\sup (f \upharpoonright \alpha ) = \alpha $$. There is a club$$C \subseteq {\omega _1}$$and finitely many functions$$\Upsilon _0, ..., \Upsilon _{n - 1} : [C]^{\omega _1}_* \rightarrow {\omega _1}$$so that for all$$f \in [C]^{\omega _1}_*$$, for all$$g \in [C]^{\omega _1}_*$$, if$$\mathfrak {C}_g = \mathfrak {C}_f$$and for all$$i < n$$,$$\sup (g \upharpoonright \Upsilon _i(f)) = \sup (f \upharpoonright \Upsilon _i(f))$$, then$$\Phi (g) = \Phi (f)$$.•Suppose$$\kappa $$satisfies$$\kappa \rightarrow _* (\kappa )^\epsilon _2$$for all$$\epsilon < \kappa $$. For all$$\chi < \kappa $$,$$[\kappa ]^{<\kappa }$$does not inject into$${}^\chi \mathrm {ON}$$, the class of$$\chi $$-length sequences of ordinals, and therefore,$$|[\kappa ]^\chi | < |[\kappa ]^{<\kappa }|$$. As a consequence, under the axiom of determinacy$$(\mathsf {AD})$$, these two cardinality results hold when$$\kappa $$is one of the following weak or strong partition cardinals of determinacy:$${\omega _1}$$,$$\omega _2$$,$$\boldsymbol {\delta }_n^1$$(for all$$1 \leq n < \omega $$) and$$\boldsymbol {\delta }^2_1$$(assuming in addition$$\mathsf {DC}_{\mathbb {R}}$$). 

   more » « less
5. On approximability of satisfiable $$\boldsymbol {k}$$-CSPs: II

   https://doi.org/10.1017/S0963548325100114  

   Bhangale, Amey; Khot, Subhash; Minzer, Dor (November 2025, Combinatorics, Probability and Computing)

   Abstract Let$$\Sigma$$be an alphabet and$$\mu$$be a distribution on$$\Sigma ^k$$for some$$k \geqslant 2$$. Let$$\alpha \gt 0$$be the minimum probability of a tuple in the support of$$\mu$$(denoted$$\mathsf{supp}(\mu )$$). We treat the parameters$$\Sigma , k, \mu , \alpha$$as fixed and constant. We say that the distribution$$\mu$$has a linear embedding if there exist an Abelian group$$G$$(with the identity element$$0_G$$) and mappings$$\sigma _i : \Sigma \rightarrow G$$,$$1 \leqslant i \leqslant k$$, such that at least one of the mappings is non-constant and for every$$(a_1, a_2, \ldots , a_k)\in \mathsf{supp}(\mu )$$,$$\sum _{i=1}^k \sigma _i(a_i) = 0_G$$. In [Bhangale-Khot-Minzer, STOC 2022], the authors asked the following analytical question. Let$$f_i: \Sigma ^n\rightarrow [\!-1,1]$$be bounded functions, such that at least one of the functions$$f_i$$essentially has degree at least$$d$$, meaning that the Fourier mass of$$f_i$$on terms of degree less than$$d$$is at most$$\delta$$. If$$\mu$$has no linear embedding (over any Abelian group), then is it necessarily the case that\begin{equation*}\left | \mathop {\mathbb{E}}_{({\textbf {x}}_1, {\textbf {x}}_2, \ldots , {\textbf {x}}_k)\sim \mu ^{\otimes n}}[f_1({\textbf {x}}_1)f_2({\textbf {x}}_2)\cdots f_k({\textbf {x}}_k)] \right | = o_{d, \delta }(1),\end{equation*}where the right hand side$$\to 0$$as the degree$$d \to \infty$$and$$\delta \to 0$$? In this paper, we answer this analytical question fully and in the affirmative for$$k=3$$. We also show the following two applications of the result.1.The first application is related to hardness of approximation. Using the reduction from [5], we show that for every$$3$$-ary predicate$$P:\Sigma ^3 \to \{0,1\}$$such that$$P$$has no linear embedding, anSDP (semi-definite programming) integrality gap instanceof a$$P$$-Constraint Satisfaction Problem (CSP) instance with gap$$(1,s)$$can be translated into a dictatorship test with completeness$$1$$and soundness$$s+o(1)$$, under certain additional conditions on the instance.2.The second application is related to additive combinatorics. We show that if the distribution$$\mu$$on$$\Sigma ^3$$has no linear embedding, marginals of$$\mu$$are uniform on$$\Sigma$$, and$$(a,a,a)\in \texttt{supp}(\mu )$$for every$$a\in \Sigma$$, then every large enough subset of$$\Sigma ^n$$contains a triple$$({\textbf {x}}_1, {\textbf {x}}_2,{\textbf {x}}_3)$$from$$\mu ^{\otimes n}$$(and in fact a significant density of such triples). 

   more » « less