Sharp Hypercontractivity for Global Functions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909921582252032 |
|---|---|
| author | Keller, Nathan Lifshitz, Noam Marcus, Omri |
| author_facet | Keller, Nathan Lifshitz, Noam Marcus, Omri |
| contents | For a function $f$ on the hypercube $\{0,1\}^n$ with Fourier expansion $f=\sum_{S\subseteq[n]}\hat f(S)χ_S$, the hypercontractive inequality allows bounding norms of $T_ρf=\sum_Sρ^{|S|} \hat f(S)χ_S$ in terms of norms of $f$. If $f$ is Boolean-valued, the level-$d$ inequality allows bounding the norm of $f^{=d}=\sum_{|S|=d}\hat f(S)χ_S$ in terms of $E[f]$. These inequalities play a central role in analysis of Boolean functions and its applications. While both inequalities hold in a sharp form when the hypercube is endowed with the uniform measure, they do not hold for more general discrete product spaces, and finding a `natural' generalization was a long-standing open problem. In 2024, Keevash et al.~obtained a hypercontractive inequality for general discrete product spaces, that holds for functions which are `global' -- namely, are not significantly affected by a restriction of a small set of coordinates. This hypercontractive inequality is not sharp, which precludes applications to $S_n$ and to other settings where sharpness of the bound is crucial. Also, no sharp level-$d$ inequality for global functions over general discrete product spaces is known. We obtain sharp versions of the hypercontractive inequality and of the level-$d$ inequality for this setting. Our inequalities open the way for diverse applications to extremal set theory, group theory, theoretical computer science, and number theory. We demonstrate this by proving quantitative bounds on the size of intersecting families of sets and vectors under weak symmetry conditions and by describing numerous applications that were obtained using our results -- to the study of functions over $S_n$, including hypercontractivity and level-$d$ inequalities, character bounds, variants of Roth's theorem and of Bogolyubov's lemma and diameter bounds, and an application to the Furstenberg-S{á}rk{ö}zy problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_01356 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Sharp Hypercontractivity for Global Functions Keller, Nathan Lifshitz, Noam Marcus, Omri Combinatorics Functional Analysis Group Theory 05D05, 06E30, 47A30, 05E16, 20B30 For a function $f$ on the hypercube $\{0,1\}^n$ with Fourier expansion $f=\sum_{S\subseteq[n]}\hat f(S)χ_S$, the hypercontractive inequality allows bounding norms of $T_ρf=\sum_Sρ^{|S|} \hat f(S)χ_S$ in terms of norms of $f$. If $f$ is Boolean-valued, the level-$d$ inequality allows bounding the norm of $f^{=d}=\sum_{|S|=d}\hat f(S)χ_S$ in terms of $E[f]$. These inequalities play a central role in analysis of Boolean functions and its applications. While both inequalities hold in a sharp form when the hypercube is endowed with the uniform measure, they do not hold for more general discrete product spaces, and finding a `natural' generalization was a long-standing open problem. In 2024, Keevash et al.~obtained a hypercontractive inequality for general discrete product spaces, that holds for functions which are `global' -- namely, are not significantly affected by a restriction of a small set of coordinates. This hypercontractive inequality is not sharp, which precludes applications to $S_n$ and to other settings where sharpness of the bound is crucial. Also, no sharp level-$d$ inequality for global functions over general discrete product spaces is known. We obtain sharp versions of the hypercontractive inequality and of the level-$d$ inequality for this setting. Our inequalities open the way for diverse applications to extremal set theory, group theory, theoretical computer science, and number theory. We demonstrate this by proving quantitative bounds on the size of intersecting families of sets and vectors under weak symmetry conditions and by describing numerous applications that were obtained using our results -- to the study of functions over $S_n$, including hypercontractivity and level-$d$ inequalities, character bounds, variants of Roth's theorem and of Bogolyubov's lemma and diameter bounds, and an application to the Furstenberg-S{á}rk{ö}zy problem. |
| title | Sharp Hypercontractivity for Global Functions |
| topic | Combinatorics Functional Analysis Group Theory 05D05, 06E30, 47A30, 05E16, 20B30 |
| url | https://arxiv.org/abs/2307.01356 |