Abstract Using the calculus of variations, we prove the following structure theorem for noise-stable partitions: a partition of n -dimensional Euclidean space into m disjoint sets of fixed Gaussian volumes that maximise their noise stability must be $(m-1)$ -dimensional, if $m-1\leq n$ . In particular, the maximum noise stability of a partition of m sets in $\mathbb {R}^{n}$ of fixed Gaussian volumes is constant for all n satisfying $n\geq m-1$ . From this result, we obtain: (i) A proof of the plurality is stablest conjecture for three candidate elections, for all correlation parameters $\rho $ satisfying $0<\rho <\rho _{0}$ , where $\rho _{0}>0$ is a fixed constant (that does not depend on the dimension n ), when each candidate has an equal chance of winning. (ii) A variational proof of Borell’s inequality (corresponding to the case $m=2$ ). The structure theorem answers a question of De–Mossel–Neeman and of Ghazi–Kamath–Raghavendra. Item (i) is the first proof of any case of the plurality is stablest conjecture of Khot-Kindler-Mossel-O’Donnell for fixed $\rho $ , with the case $\rho \to L1^{-}$ being solved recently. Item (i) is also the first evidence for the optimality of the Frieze–Jerrum semidefinite program for solving MAX-3-CUT, assuming the unique games conjecture. Without the assumption that each candidate has an equal chance of winning in (i), the plurality is stablest conjecture is known to be false.
more »
« less
DETERMINACY OF SCHMIDT’S GAME AND OTHER INTERSECTION GAMES
Abstract Schmidt’s game and other similar intersection games have played an important role in recent years in applications to number theory, dynamics, and Diophantine approximation theory. These games are real games, that is, games in which the players make moves from a complete separable metric space. The determinacy of these games trivially follows from the axiom of determinacy for real games, $\mathsf {AD}_{\mathbb R}$ , which is a much stronger axiom than that asserting all integer games are determined, $\mathsf {AD}$ . One of our main results is a general theorem which under the hypothesis $\mathsf {AD}$ implies the determinacy of intersection games which have a property allowing strategies to be simplified. In particular, we show that Schmidt’s $(\alpha ,\beta ,\rho )$ game on $\mathbb R$ is determined from $\mathsf {AD}$ alone, but on $\mathbb R^n$ for $n \geq 3$ we show that $\mathsf {AD}$ does not imply the determinacy of this game. We then give an application of simple strategies and prove that the winning player in Schmidt’s $(\alpha , \beta , \rho )$ game on $\mathbb {R}$ has a winning positional strategy, without appealing to the axiom of choice. We also prove several other results specifically related to the determinacy of Schmidt’s game. These results highlight the obstacles in obtaining the determinacy of Schmidt’s game from $\mathsf {AD}$ .
more »
« less
- Award ID(s):
- 1800323
- PAR ID:
- 10464196
- Date Published:
- Journal Name:
- The Journal of Symbolic Logic
- Volume:
- 88
- Issue:
- 1
- ISSN:
- 0022-4812
- Page Range / eLocation ID:
- 1 to 21
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Assume $\mathsf {ZF} + \mathsf {AD}$ and all sets of reals are Suslin. Let $\Gamma $ be a pointclass closed under $\wedge $ , $\vee $ , $\forall ^{\mathbb {R}}$ , continuous substitution, and has the scale property. Let $\kappa = \delta (\Gamma )$ be the supremum of the length of prewellorderings on $\mathbb {R}$ which belong to $\Delta = \Gamma \cap \check \Gamma $ . Let $\mathsf {club}$ denote the collection of club subsets of $\kappa $ . Then the countable length everywhere club uniformization holds for $\kappa $ : For every relation $R \subseteq {}^{<{\omega _1}}\kappa \times \mathsf {club}$ with the property that for all $\ell \in {}^{<{\omega _1}}\kappa $ and clubs $C \subseteq D \subseteq \kappa $ , $R(\ell ,D)$ implies $R(\ell ,C)$ , there is a uniformization function $\Lambda : \mathrm {dom}(R) \rightarrow \mathsf {club}$ with the property that for all $\ell \in \mathrm {dom}(R)$ , $R(\ell ,\Lambda (\ell ))$ . In particular, under these assumptions, for all $n \in \omega $ , $\boldsymbol {\delta }^1_{2n + 1}$ satisfies the countable length everywhere club uniformization.more » « less
-
null (Ed.)We prove that, given any ordinal $\delta < \omega_2$, there exists a transfinite $\delta$-sequence of separable Banach spaces $(X_\alpha)_{\alpha < \delta}$ such that $X_\alpha$ embeds isomorphically into $X_\beta$ and contains no subspace isomorphic to $X_\beta$ for all $\alpha < \beta < \delta$. All these spaces are subspaces of the Banach space $E_p = \bigl( \bigoplus_{n=1}^\infty \ell_p \bigr)_2$, where $1 \leq p < 2$. Moreover, assuming Martin's axiom, we prove the same for all ordinals $\delta$ of continuum cardinality.more » « less
-
more » « less
Abstract We prove that among all 1-periodic configurations $\Gamma $ of points on the real line $\mathbb{R}$ the quantities $\min _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$ and $\max _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$ are maximized and minimized, respectively, if and only if the points are equispaced and whenever the number of points $n$ per period is sufficiently large (depending on $\alpha $). This solves the polarization problem for periodic configurations with a Gaussian weight on $\mathbb{R}$ for large $n$. The first result is shown using Fourier series. The second result follows from the work of Cohn and Kumar on universal optimality and holds for all $n$ (independent of $\alpha $).
-
This paper studies structural consequences of supercompact- ness of ω1 under ZF. We show that the Axiom of Dependent Choice (DC) follows from “ω1 is supercompact”. “ω1 is supercompact” also implies that AD+, a strengthening of the Axiom of Determinacy (AD), is equiv- alent to ADR. It is shown that “ω1 is supercompact” does not imply AD. The most one can hope for is Suslin co-Suslin determinacy. We show that this follows from “ω1 is supercompact” and Hod Pair Capturing (HPC), an inner-model theoretic hypothesis that imposes certain smallness con- ditions on the universe of sets. “ω1 is supercompact” on its own implies that every Suslin co-Suslin set is the projection of a determined (in fact, homogenously Suslin) set. “ω1 is supercompact” also implies all sets in the Chang model have all the usual regularity properties, like Lebesgue measurability and the Baire property.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/jsl.2022.41
