Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 

 

Strong contraction and influences in tail spaces


Authors: Steven Heilman, Elchanan Mossel and Krzysztof Oleszkiewicz
Journal: Trans. Amer. Math. Soc. 369 (2017), 4843-4863
MSC (2010): Primary 60E15, 47D07, 06E30
DOI: https://doi.org/10.1090/tran/6916
Published electronically: February 13, 2017
MathSciNet review: 3632552
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study contraction under a Markov semi-group and influence bounds for functions in $ L^2$ tail spaces, i.e., functions all of whose low level Fourier coefficients vanish. It is natural to expect that certain analytic inequalities are stronger for such functions than for general functions in $ L^2$. In the positive direction we prove an $ L^{p}$ Poincaré inequality and moment decay estimates for mean 0 functions and for all $ 1<p<\infty $, proving the degree one case of a conjecture of Mendel and Naor as well as the general degree case of the conjecture when restricted to Boolean functions. In the negative direction, we answer negatively two questions of Hatami and Kalai concerning extensions of the Kahn-Kalai-Linial and Harper Theorems to tail spaces. That is, we construct a function $ f\colon \{-1,1\}^{n}\to \{-1,1\}$ whose Fourier coefficients vanish up to level $ c \log n$, with all influences bounded by $ C \log n/n$ for some constants $ 0<c,C< \infty $. We also construct a function $ f\colon \{-1,1\}^{n}\to \{0,1\}$ with nonzero mean whose remaining Fourier coefficients vanish up to level $ c' \log n$, with the sum of the influences bounded by $ C'(\mathbb{E}f)\log (1/\mathbb{E}f)$ for some constants $ 0<c',C'<\infty $.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60E15, 47D07, 06E30

Retrieve articles in all journals with MSC (2010): 60E15, 47D07, 06E30


Additional Information

Steven Heilman
Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095-1555
Email: heilman@cims.nyu.edu

Elchanan Mossel
Affiliation: Department of Statistics, University of Pennsylvania, Philadelphia, Pennsylvania 19104 — and — Departments of Statistics and Computer Science, University of California Berkeley, Berkeley, California 94720
Address at time of publication: Department of Mathematics & Statistics Group, IDSS, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: elmos@mit.edu

Krzysztof Oleszkiewicz
Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
Email: koles@mimuw.edu.pl

DOI: https://doi.org/10.1090/tran/6916
Received by editor(s): November 13, 2014
Received by editor(s) in revised form: July 27, 2015
Published electronically: February 13, 2017
Additional Notes: The first author was supported by NSF Graduate Research Fellowship DGE-0813964 and a Simons-Berkeley Research Fellowship. Part of this work was completed while the first author was visiting the Network Science and Graph Algorithms program at ICERM
The second author was supported by NSF grant DMS-1106999, NSF grant CCF 1320105 and DOD ONR grant N000141110140 and grant 328025 from the Simons Foundation
The third author was supported by NCN grant DEC-2012/05/B/ST1/00412. Part of this work was carried out while the authors were visiting the Real Analysis in Computer Science program at the Simons Institute for the Theory of Computing.
Article copyright: © Copyright 2017 American Mathematical Society