Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics
There is a common theme to some research questions in additive combinatorics and noise stability. Both study the following basic question: Let $\mathcal{P}$ be a probability distribution over a space $\Omega^\ell$ with all $\ell$ marginals equal. Let $\underline{X}^{(1)}, \ldots, \underline{X}^{(...
| Príomhchruthaitheoirí: | , , |
|---|---|
| Rannpháirtithe: | |
| Formáid: | Alt |
| Teanga: | English |
| Foilsithe / Cruthaithe: |
Alliance of Diamond Open Access Journals
2021
|
| Rochtain ar líne: | https://hdl.handle.net/1721.1/137506 |
| _version_ | 1826217246680154112 |
|---|---|
| author | Hązła, Jan Holenstein, Thomas Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology. Institute for Data, Systems, and Society |
| author_facet | Massachusetts Institute of Technology. Institute for Data, Systems, and Society Hązła, Jan Holenstein, Thomas Mossel, Elchanan |
| author_sort | Hązła, Jan |
| collection | MIT |
| description | There is a common theme to some research questions in additive combinatorics
and noise stability. Both study the following basic question: Let $\mathcal{P}$
be a probability distribution over a space $\Omega^\ell$ with all $\ell$
marginals equal. Let $\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)}$
where $\underline{X}^{(j)} = (X_1^{(j)}, \ldots, X_n^{(j)})$ be random vectors
such that for every coordinate $i \in [n]$ the tuples $(X_i^{(1)}, \ldots,
X_i^{(\ell)})$ are i.i.d. according to $\mathcal{P}$.
A central question that is addressed in both areas is:
- Does there exist a function $c_{\mathcal{P}}()$ independent of $n$ such
that for every $f: \Omega^n \to [0, 1]$ with $\mathrm{E}[f(X^{(1)})] = \mu >
0$: \begin{align*} \mathrm{E} \left[ \prod_{j=1}^\ell f(X^{(j)}) \right]
\ge c(\mu) > 0 \, ? \end{align*}
Instances of this question include the finite field model version of Roth's
and Szemer\'edi's theorems as well as Borell's result about the optimality of
noise stability of half-spaces.
Our goal in this paper is to interpolate between the noise stability theory
and the finite field additive combinatorics theory and address the question
above in further generality than considered before. In particular, we settle
the question for $\ell = 2$ and when $\ell > 2$ and $\mathcal{P}$ has bounded
correlation $\rho(\mathcal{P}) < 1$. Under the same conditions we also
characterize the _obstructions_ for similar lower bounds in the case of $\ell$
different functions. Part of the novelty in our proof is the combination of
analytic arguments from the theories of influences and hyper-contraction with
arguments from additive combinatorics. |
| first_indexed | 2024-09-23T17:00:20Z |
| format | Article |
| id | mit-1721.1/137506 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T17:00:20Z |
| publishDate | 2021 |
| publisher | Alliance of Diamond Open Access Journals |
| record_format | dspace |
| spelling | mit-1721.1/1375062023-01-10T15:45:59Z Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics Hązła, Jan Holenstein, Thomas Mossel, Elchanan Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Department of Mathematics There is a common theme to some research questions in additive combinatorics and noise stability. Both study the following basic question: Let $\mathcal{P}$ be a probability distribution over a space $\Omega^\ell$ with all $\ell$ marginals equal. Let $\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)}$ where $\underline{X}^{(j)} = (X_1^{(j)}, \ldots, X_n^{(j)})$ be random vectors such that for every coordinate $i \in [n]$ the tuples $(X_i^{(1)}, \ldots, X_i^{(\ell)})$ are i.i.d. according to $\mathcal{P}$. A central question that is addressed in both areas is: - Does there exist a function $c_{\mathcal{P}}()$ independent of $n$ such that for every $f: \Omega^n \to [0, 1]$ with $\mathrm{E}[f(X^{(1)})] = \mu > 0$: \begin{align*} \mathrm{E} \left[ \prod_{j=1}^\ell f(X^{(j)}) \right] \ge c(\mu) > 0 \, ? \end{align*} Instances of this question include the finite field model version of Roth's and Szemer\'edi's theorems as well as Borell's result about the optimality of noise stability of half-spaces. Our goal in this paper is to interpolate between the noise stability theory and the finite field additive combinatorics theory and address the question above in further generality than considered before. In particular, we settle the question for $\ell = 2$ and when $\ell > 2$ and $\mathcal{P}$ has bounded correlation $\rho(\mathcal{P}) < 1$. Under the same conditions we also characterize the _obstructions_ for similar lower bounds in the case of $\ell$ different functions. Part of the novelty in our proof is the combination of analytic arguments from the theories of influences and hyper-contraction with arguments from additive combinatorics. 2021-11-05T15:07:51Z 2021-11-05T15:07:51Z 2018 2021-05-25T11:59:31Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/137506 Hązła, Jan, Holenstein, Thomas and Mossel, Elchanan. 2018. "Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics." Discrete Analysis, 20. en 10.19086/da.6513 Discrete Analysis Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf Alliance of Diamond Open Access Journals Discrete Analysis |
| spellingShingle | Hązła, Jan Holenstein, Thomas Mossel, Elchanan Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics |
| title | Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics |
| title_full | Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics |
| title_fullStr | Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics |
| title_full_unstemmed | Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics |
| title_short | Product Space Models of Correlation: Between Noise Stability and Additive Combinatorics |
| title_sort | product space models of correlation between noise stability and additive combinatorics |
| url | https://hdl.handle.net/1721.1/137506 |
| work_keys_str_mv | AT hazłajan productspacemodelsofcorrelationbetweennoisestabilityandadditivecombinatorics AT holensteinthomas productspacemodelsofcorrelationbetweennoisestabilityandadditivecombinatorics AT mosselelchanan productspacemodelsofcorrelationbetweennoisestabilityandadditivecombinatorics |