Harmonicity and invariance on slices of the Boolean cube
© 2019, Springer-Verlag GmbH Germany, part of Springer Nature. In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree harmonic multilinear polynomials (a polynomial in x1, … , xn is harmonic if it is annihilated by ∑i=1n∂∂xi). Here we p...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Science and Business Media LLC
2022
|
| Online Access: | https://hdl.handle.net/1721.1/135873.2 |
| _version_ | 1811069054456168448 |
|---|---|
| author | Filmus, Yuval Mossel, Elchanan |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Filmus, Yuval Mossel, Elchanan |
| author_sort | Filmus, Yuval |
| collection | MIT |
| description | © 2019, Springer-Verlag GmbH Germany, part of Springer Nature. In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree harmonic multilinear polynomials (a polynomial in x1, … , xn is harmonic if it is annihilated by ∑i=1n∂∂xi). Here we provide an alternative proof for general low-degree harmonic multilinear polynomials, with no constraints on the influences. We show that any real-valued harmonic multilinear polynomial on the slice whose degree is o(n) has approximately the same distribution under the slice and cube measures. Our proof is based on ideas and results from the representation theory of Sn, along with a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversible Markov chains, our decomposition is applied in a non-stationary non-reversible setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the known facts that (1) one cannot distinguish between the slice and the cube based on functions of o(n) coordinates and (2) Boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is o(n). |
| first_indexed | 2024-09-23T08:04:58Z |
| format | Article |
| id | mit-1721.1/135873.2 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:04:58Z |
| publishDate | 2022 |
| publisher | Springer Science and Business Media LLC |
| record_format | dspace |
| spelling | mit-1721.1/135873.22022-09-22T07:07:56Z Harmonicity and invariance on slices of the Boolean cube Filmus, Yuval Mossel, Elchanan Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Institute for Data, Systems, and Society © 2019, Springer-Verlag GmbH Germany, part of Springer Nature. In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree harmonic multilinear polynomials (a polynomial in x1, … , xn is harmonic if it is annihilated by ∑i=1n∂∂xi). Here we provide an alternative proof for general low-degree harmonic multilinear polynomials, with no constraints on the influences. We show that any real-valued harmonic multilinear polynomial on the slice whose degree is o(n) has approximately the same distribution under the slice and cube measures. Our proof is based on ideas and results from the representation theory of Sn, along with a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversible Markov chains, our decomposition is applied in a non-stationary non-reversible setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the known facts that (1) one cannot distinguish between the slice and the cube based on functions of o(n) coordinates and (2) Boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is o(n). NSF (DMS 1106999) NSF (CCF 1320105) DOD ONR (N00014-14-1-0823) Simons Foundation (328025) NSF Agreement (No. DMS-1128155) ISF Grant 1337/16 2022-02-14T23:27:30Z 2021-10-27T20:29:44Z 2022-02-14T23:27:30Z 2019 2019-11-18T13:27:01Z Article http://purl.org/eprint/type/JournalArticle 1432-2064 https://hdl.handle.net/1721.1/135873.2 en https://dx.doi.org/10.1007/S00440-019-00900-W Probability Theory and Related Fields Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/octet-stream Springer Science and Business Media LLC arXiv |
| spellingShingle | Filmus, Yuval Mossel, Elchanan Harmonicity and invariance on slices of the Boolean cube |
| title | Harmonicity and invariance on slices of the Boolean cube |
| title_full | Harmonicity and invariance on slices of the Boolean cube |
| title_fullStr | Harmonicity and invariance on slices of the Boolean cube |
| title_full_unstemmed | Harmonicity and invariance on slices of the Boolean cube |
| title_short | Harmonicity and invariance on slices of the Boolean cube |
| title_sort | harmonicity and invariance on slices of the boolean cube |
| url | https://hdl.handle.net/1721.1/135873.2 |
| work_keys_str_mv | AT filmusyuval harmonicityandinvarianceonslicesofthebooleancube AT mosselelchanan harmonicityandinvarianceonslicesofthebooleancube |