Strong contraction and influences in tail spaces
HTML articles powered by AMS MathViewer
- by Steven Heilman, Elchanan Mossel and Krzysztof Oleszkiewicz PDF
- Trans. Amer. Math. Soc. 369 (2017), 4843-4863 Request permission
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
- William Beckner, A generalized Poincaré inequality for Gaussian measures, Proc. Amer. Math. Soc. 105 (1989), no. 2, 397–400. MR 954373, DOI 10.1090/S0002-9939-1989-0954373-7
- Michael Ben-Or and Nathan Linial, Collective coin flipping, Randomness and Computation (S. Micali, ed.), Academic Press, New York, 1989, pp. 91–115.
- Aline Bonami, Étude des coefficients de Fourier des fonctions de $L^{p}(G)$, Ann. Inst. Fourier (Grenoble) 20 (1970), no. fasc. 2, 335–402 (1971) (French, with English summary). MR 283496, DOI 10.5802/aif.357
- Patrick Cattiaux, Arnaud Guillin, and Cyril Roberto, Poincaré inequality and the $L^p$ convergence of semi-groups, Electron. Commun. Probab. 15 (2010), 270–280. MR 2661206, DOI 10.1214/ECP.v15-1559
- Leonard Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083. MR 420249, DOI 10.2307/2373688
- L. H. Harper, Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math. 12 (1964), 131–135. MR 162737, DOI 10.1137/0112012
- Masanori Hino, Exponential decay of positivity preserving semigroups on $L^p$, Osaka J. Math. 37 (2000), no. 3, 603–624. MR 1789439
- Svante Janson, Gaussian Hilbert spaces, Cambridge Tracts in Mathematics, vol. 129, Cambridge University Press, Cambridge, 1997. MR 1474726, DOI 10.1017/CBO9780511526169
- Jeff Kahn, Gil Kalai, and Nathan Linial, The influence of variables on Boolean functions, Proc. of 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 68–80.
- Subhash Khot and Assaf Naor, Nonembeddability theorems via Fourier analysis, Math. Ann. 334 (2006), no. 4, 821–852. MR 2209259, DOI 10.1007/s00208-005-0745-0
- M. Ledoux, Logarithmic Sobolev inequalities for unbounded spin systems revisited, Séminaire de Probabilités, XXXV, Lecture Notes in Math., vol. 1755, Springer, Berlin, 2001, pp. 167–194. MR 1837286, DOI 10.1007/978-3-540-44671-2_{1}3
- F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Mathematical Library, Vol. 16, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977. MR 0465509
- Jessie MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Tech. J. 42 (1963), 79–94. MR 149978, DOI 10.1002/j.1538-7305.1963.tb04003.x
- Manor Mendel and Assaf Naor, Nonlinear spectral calculus and super-expanders, Publ. Math. Inst. Hautes Études Sci. 119 (2014), 1–95. MR 3210176, DOI 10.1007/s10240-013-0053-2
- P.-A. Meyer, Transformations de Riesz pour les lois gaussiennes, Seminar on probability, XVIII, Lecture Notes in Math., vol. 1059, Springer, Berlin, 1984, pp. 179–193 (French). MR 770960, DOI 10.1007/BFb0100043
- Edward Nelson, The free Markoff field, J. Functional Analysis 12 (1973), 211–227. MR 0343816, DOI 10.1016/0022-1236(73)90025-6
- Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, New York, 2014. MR 3443800, DOI 10.1017/CBO9781139814782
- D. W. Stroock, An introduction to the theory of large deviations, Universitext, Springer-Verlag, New York, 1984. MR 755154, DOI 10.1007/978-1-4613-8514-1
- Michel Talagrand, A conjecture on convolution operators, and a non-Dunford-Pettis operator on $L^1$, Israel J. Math. 68 (1989), no. 1, 82–88. MR 1035882, DOI 10.1007/BF02764970
- N. Th. Varopoulos, Hardy-Littlewood theory for semigroups, J. Funct. Anal. 63 (1985), no. 2, 240–260. MR 803094, DOI 10.1016/0022-1236(85)90087-4
Additional Information
- Steven Heilman
- Affiliation: Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095-1555
- MR Author ID: 886889
- 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
- MR Author ID: 637297
- Email: elmos@mit.edu
- Krzysztof Oleszkiewicz
- Affiliation: Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
- MR Author ID: 335188
- Email: koles@mimuw.edu.pl
- 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. - © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 4843-4863
- MSC (2010): Primary 60E15, 47D07, 06E30
- DOI: https://doi.org/10.1090/tran/6916
- MathSciNet review: 3632552