Bourgain's symmetrization theorem is a powerful technique reducing boolean analysis on product spaces to the cube. It states that for any product $\Omega_i^{ \otimes d}$, function $f: \Omega_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_{ \rho}f = \sum\limits \rho^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.
Categories: cs.CC math.CO
