Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
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
  • 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