Hypercontractivity on HDX II: Symmetrization and q-Norms
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910829663748096 |
|---|---|
| author | Hopkins, Max |
| author_facet | Hopkins, Max |
| contents | Bourgain's symmetrization theorem is a powerful technique reducing boolean analysis on product spaces to the cube. It states that for any product $Ω_i^{\otimes d}$, function $f: Ω_i^{\otimes d} \to \mathbb{R}$, and $q > 1$:
$$||T_{\frac{1}{2}}f(x)||_q \leq ||\tilde{f}(r,x)||_{q} \leq ||T_{c_q}f(x)||_q$$ where $T_ρf = \sum\limits ρ^Sf^{=S}$ is the noise operator and $\widetilde{f}(r,x) = \sum\limits r_Sf^{=S}(x)$ `symmetrizes' $f$ by convolving its Fourier components $\{f^{=S}\}_{S \subseteq [d]}$ with a random boolean string $r \in \{\pm 1\}^d$.
In this work, we extend the symmetrization theorem to high dimensional expanders (HDX). Building on (O'Donnell and Zhao 2021), we show this implies nearly-sharp $(2{\to}q)$-hypercontractivity for partite HDX. This resolves the main open question of (Gur, Lifshitz, and Liu STOC 2022) and gives the first fully hypercontractive subsets $X \subset [n]^d$ of support $n\cdot\exp(\text{poly}(d))$, an exponential improvement over Bafna, Hopkins, Kaufman, and Lovett's $n\cdot\exp(\exp(d))$ bound (BHKL STOC 2022). Adapting (Bourgain JAMS 1999), we also give the first booster theorem for HDX, resolving a main open question of BHKL.
Our proof is based on two elementary new ideas in the theory of high dimensional expansion. First we introduce `$q$-norm HDX', generalizing standard spectral notions to higher moments, and observe every spectral HDX is a $q$-norm HDX. Second, we introduce a simple method of coordinate-wise analysis on HDX which breaks high dimensional random walks into coordinate-wise components and allows each component to be analyzed as a $\textit{$1$-dimensional}$ operator locally within $X$. This allows for application of standard tricks such as the replacement method, greatly simplifying prior analytic techniques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16687 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hypercontractivity on HDX II: Symmetrization and q-Norms Hopkins, Max Computational Complexity Combinatorics F.2 Bourgain's symmetrization theorem is a powerful technique reducing boolean analysis on product spaces to the cube. It states that for any product $Ω_i^{\otimes d}$, function $f: Ω_i^{\otimes d} \to \mathbb{R}$, and $q > 1$: $$||T_{\frac{1}{2}}f(x)||_q \leq ||\tilde{f}(r,x)||_{q} \leq ||T_{c_q}f(x)||_q$$ where $T_ρf = \sum\limits ρ^Sf^{=S}$ is the noise operator and $\widetilde{f}(r,x) = \sum\limits r_Sf^{=S}(x)$ `symmetrizes' $f$ by convolving its Fourier components $\{f^{=S}\}_{S \subseteq [d]}$ with a random boolean string $r \in \{\pm 1\}^d$. In this work, we extend the symmetrization theorem to high dimensional expanders (HDX). Building on (O'Donnell and Zhao 2021), we show this implies nearly-sharp $(2{\to}q)$-hypercontractivity for partite HDX. This resolves the main open question of (Gur, Lifshitz, and Liu STOC 2022) and gives the first fully hypercontractive subsets $X \subset [n]^d$ of support $n\cdot\exp(\text{poly}(d))$, an exponential improvement over Bafna, Hopkins, Kaufman, and Lovett's $n\cdot\exp(\exp(d))$ bound (BHKL STOC 2022). Adapting (Bourgain JAMS 1999), we also give the first booster theorem for HDX, resolving a main open question of BHKL. Our proof is based on two elementary new ideas in the theory of high dimensional expansion. First we introduce `$q$-norm HDX', generalizing standard spectral notions to higher moments, and observe every spectral HDX is a $q$-norm HDX. Second, we introduce a simple method of coordinate-wise analysis on HDX which breaks high dimensional random walks into coordinate-wise components and allows each component to be analyzed as a $\textit{$1$-dimensional}$ operator locally within $X$. This allows for application of standard tricks such as the replacement method, greatly simplifying prior analytic techniques. |
| title | Hypercontractivity on HDX II: Symmetrization and q-Norms |
| topic | Computational Complexity Combinatorics F.2 |
| url | https://arxiv.org/abs/2408.16687 |