STRONG CONTRACTION AND INFLUENCES IN TAIL SPACES

STEVEN HEILMAN, ELCHANAN MOSSEL, AND KRZYSZTOF OLESZKIEWICZ

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 < ∞, 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: {−1, 1}^{n} → {−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 < ∞. We also construct a function f: {−1, 1}^{n} → {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′(𝔼f) log(1/𝔼f) for some constants 0 < c′, C′ < ∞.

1. Introduction

Consider the uniform measure on {−1, 1}^{n}. Any f: {−1, 1}^{n} → ℝ can be written as f = ∑_{S⊆{1,...,n}} f̂(S)W_{S}, where for all x = (x_{1}, …, x_{n}) ∈ {−1, 1}^{n}, W_{S}(x) := ∏_{i∈S} x_{i} and f̂(S) := 2^{−n} ∑_{x∈{−1,1}^{n}} f(x)W_{S}(x). For any t ≥ 0, define P_{t}f := ∑_{S⊆{1,...,n}} e^{−t|S|}f̂(S)W_{S}, and define Lf := ∑_{S⊆{1,...,n}} |S| f̂(S)W_{S}.

Our interest in this paper is in tail spaces. For the case of the uniform measure on {−1, 1}^{n}, we are interested in the linear subspace of all functions satisfying f̂(S) = 0 for all S ⊆ {1, …, n} with |S| ≤ k. Our interest in understanding such functions follows recent conjectures by Mendel and Naor and by Hatami and Kalai.

1.1. Heat Smoothing. In their study of a general notion of expander (with respect to all uniformly convex spaces), Mendel and Naor made the following conjecture:

Conjecture 1.1 (Heat Smoothing). [13, Remark 5.5] Let 1 < p < ∞. Let f: {−1, 1}^{n} → ℝ with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| < k. Then

∀t > 0, ∥P_{t}f∥_{p} ≤ e^{−tkc(p)} ∥f∥_{p} .  (1.1)

2010 Mathematics Subject Classification. 60E15, 47D07, 06E30. S. H. was supported by NSF Graduate Research Fellowship DGE-0813964 and a Simons-Berkeley Research

Fellowship. Part of this work was completed while S. H. was visiting the Network Science and Graph Algorithms program at ICERM.

E. M. was supported by NSF grant DMS-1106999, NSF Grant CCF 1320105 and DOD ONR grant N000141110140 and grant 328025 from the Simons foundation.

K. O. 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.

In our main result we prove a special case of their conjecture for k = 1:

Theorem 1.2 (Heat Smoothing). For every p ∈ (1, ∞) and every f : {−1, 1}^{n} → ℝ with 𝔼f = 0, for every t > 0,

∥P_{t}f∥_{p} ≤ exp (−\frac{(2p − 2)t}{(p^{2} − 2p + 2)}) · ∥f∥_{p}.

The proof of this theorem covers all Markov operators satisfying an L^{2} Poincaré inequality. We also show that if we restrict to {−1, 0, 1}-valued functions, then (1.1) always holds.

Theorem 1.3 (Conjecture 1.1 for {−1, 0, 1}-valued functions). Let 1 < p < ∞ and let f: {−1, 1}^{n} → {−1, 0, 1} with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| < k. Then for all t > 0,

∥P_{t}f∥_{p} ≤ e^{−2tk min(\frac{p−1}{p} , \frac{1}{p})} ∥f∥_{p} .  (1.2)

The constant in Theorem 1.3 for k = 1, which comes from an application of Hölder’s inequality, is strictly worse than that of Theorem 1.2. Again the proof of Theorem 1.3 extends to cover P_{t} being any symmetric Markov semigroup as long as f: Ω → {−1, 0, 1} satisfies ∥P_{t}f∥_{2} ≤ e^{−tk} ∥f∥_{2}.

Our results in Theorem 1.2 and Theorem 1.3 should be compared to the following result of Mendel-Naor below, which they attributed to P. A. Meyer [14].

Theorem 1.4. [13, Lemma 5.4] Let 2 ≤ p < ∞. Then there exists c(p) > 0 such that the following holds. Let f: {−1, 1}^{n} → ℝ with 𝔼fW_{S} = 0 for all |S| < k. Then

∀ t > 0, ∥P_{t}f∥_{p} ≤ e^{−k min(t,t^{2})c(p)} ∥f∥_{p} .
∥Lf∥_{p} ≥ c(p)\sqrt{k} ∥f∥_{p} .

The second inequality can be considered a “higher-order” Poincaré inequality, and it follows from the first by writing f = ∫_{0}^{∞} e^{−tL}Lfdt and then applying the L^{p}({−1, 1}^{n}) triangle inequality.

One should also compare our results to the following result of Hino (in a much more general setting) that is also briefly mentioned at the end of the proof of Theorem 1 in [14].

Theorem 1.5. [6, Theorem 3.6(ii)b] Let 1 < p < ∞. Then there exists ∞ > M(n), δ(n) > 0 such that, for any f: {−1, 1}^{n} → ℝ with 𝔼f = 0, for any t > 0,

∥P_{t}f∥_{p} ≤ M(n)e^{−δ(n)t} ∥f∥_{p}

The dependence of the constants M(n) and δ(n) on the dimension makes this inequality weaker than the previous two in settings where dimension independent inequalities are desired.

1.2. Poincaré Inequalities. This heat smoothing estimate in Theorem 1.2 is equivalent to the following Poincaré inequality.

Theorem 1.6 (Poincaré Inequality). Under the above assumptions for every p ∈ (1, ∞) and every f : {−1, 1}^{n} → ℝ with 𝔼f = 0 there is

𝔼 |f|^{p−1} sign(f)Lf ≥ \frac{2p − 2}{(p^{2} − 2p + 2)} · 𝔼 |f|^{p} .

The usual Poincaré inequality corresponds to the case p = 2 of Theorem 1.6. Theorem 1.6 should be contrasted with Beckner’s Poincaré inequality.

Theorem 1.7. [1] Let f: {−1, 1}^{n} → ℝ. For all 1 ≤ p ≤ 2,

(2 − p)𝔼fLf ≥ 𝔼 |f|^{2} − (𝔼 |f|^{p})^{2/p}.

Specifically, Beckner notes that, for t > 0 with e^{−2t} = p−1, (2−p)𝔼fLf ≥ 𝔼 |f|^{2}−𝔼 |P_{t}f|^{2} by Fourier analysis. He then adds the hypercontractive inequality [3, 15, 4] to this inequality to prove Theorem 1.7. However, Theorem 1.6 does not seem to follow from hypercontractivity so we need to apply different methods.

1.3. The KKL, Talagrand and Harper theorems in Tail Spaces. The KKL Theorem and its strengthening by Talagrand are two of the most fundamental theorems in the theory of Boolean functions. Harper’s theorem is an edge-isoperimetric inequality on the hypercube. Recent questions by Hatami and Kalai asked if the KKL and Harper theorems could be improved for functions in tail spaces. It is natural to ask the same question for Talagrand’s theorem.

We recall some standard definitions.

Definition 1.8 (Influences). Let f: {−1, 1}^{n} → {−1, 1} and let i ∈ {1, …, n}. Define the i’th influence I_{i}(f) ∈ ℝ of a function f : {−1, 1}^{n} → {−1, 1} by

I_{i}(f) := P [f(x_{1}, …, x_{i−1}, x_{i}, x_{i+1}, …, x_{n}) ≠ f(x_{1}, …, x_{i−1}, y, x_{i+1}, …, x_{n})],

where x_{i}, y are i.i.d. uniform random variables on {−1, 1} for all i = 1, …, n.

Since the range of a Boolean function is restricted to {−1, 1}, its Fourier coefficients should satisfy some constraints that general real-valued functions with ∥f∥_{2} = 1 do not satisfy. For instance, the influences of a Boolean function could be slightly larger than expected. For example, the non-Boolean function f = (n(n − 1)/2)^{−1/2} ∑_{S⊆{1,...,n}: |S|=2} W_{S} satisfies ∥f∥_{2} = 1, where I_{i}f = 2/n for all i = 1, …, n. At the opposite extreme, the Boolean function f = W_{{1,...,n}} satisfies ∥f∥_{2} = 1, where I_{i}f = 1 for all i = 1, …, n. With these examples in mind, we may be led to believe that Boolean functions have larger influences than arbitrary functions with ∥f∥_{2} = 1. Indeed, Ben-Or and Linial proved the following Proposition, and they conjectured that their bound on influences was the best possible.

Proposition 1.9. [2, Theorem 3] There exists a universal constant c′ > 0 and there exists a Boolean function f: {−1, 1}^{n} → {−1, 1} with 𝔼f = 0 such that max_{i=1,...,n} I_{i}(f) ≤ c′(log n)/n.

Kahn, Kalai and Linial then showed that the influence bound in Proposition 1.9 is in fact the best possible, thereby proving the conjecture of Ben-Or and Linial.

Theorem 1.10 (KKL). [8, Theorem 3.1] There exists a universal constant c > 0 such that, for any f: {−1, 1}^{n} → {−1, 1}, max_{i=1,...,n} I_{i}(f) ≥ c(𝔼(f − 𝔼f)^{2})(log n)/n.

If a function f: {−1, 1}^{n} → {−1, 1} not only has mean zero, but it also has many Fourier coefficients which are zero, it similarly seems that even more special structure should exist within the Fourier coefficients of f. That is, perhaps this function should have a larger influence than a mean zero function. Hatami and Kalai therefore asked the following question, which would improve upon Theorem 1.10.

Question 1.11. Suppose k = k(n) → ∞ as n → ∞. Does there exist ω(k) > 0 such that ω(k) → ∞ as k → ∞, such that the following statement holds? Let f: {−1, 1}^{n} → {−1, 1} with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| ≤ k. Then max_{i=1,...,n} I_{i}f ≥ ((log n)/n)·ω(k).

Hatami speculated that a positive answer to the question above may help in proving the Entropy Influence Conjecture. Here we prove that the answer to the question is negative by showing that

Theorem 1.12 (Question 1.11 for k = log n). There exists 0 < C, c < ∞ such that, for infinitely many n ∈ ℕ, there exists f: {−1, 1}^{n} → {−1, 1} with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| ≤ c log n such that max_{i=1,...,n} I_{i}f ≤ C(log n)/n.

In other words, there is a phase transition for the maximum influence of Boolean functions with vanishing Fourier coefficients. This phase transition occurs when we require the first k(n) Fourier coefficients to vanish where k(n)/ log n is either bounded or unbounded, as n → ∞. We note that the functions constructed in Theorem 1.12 do not provide a counter example to the Entropy Influence conjecture as their entropy is of the same order as for the standard Tribes function.

We also note that if k = g(n) log n, where g(n) → ∞ then it is trivial to improve the KKL estimate since

∑_{i=1}^{n} I_{i}f = ∑_{S⊆{1,...,n}} |S| |f̂(S)|^{2}

which implies max_{i=1,...,n} I_{i}f ≥ g(n)(log n)/n.

With a similar motivation to Question 1.11, Kalai also asked whether or not the following isoperimetric inequality could be improved.

Theorem 1.13 (Harper’s Inequality). [16, Theorem 2.39],[5] For any f: {−1, 1}^{n} → {0, 1}, ∑_{i=1}^{n} I_{i}f ≥ (2/ log 2)(𝔼f) log(1/𝔼f).

To see the isoperimetric content of Theorem 1.13, we consider the hypercube {−1, 1}^{n} as the vertices of a graph, where an edge connects (x_{1}, …, x_{n}), (y_{1}, …, y_{n}) ∈ {−1, 1}^{n} if and only if |{i ∈ {1, …, n}: x_{i} ≠ y_{i}}| = 1. Then (1/n) ∑_{i=1}^{n} I_{i}f is equal to the fraction of edges of {−1, 1}^{n} between the sets {x ∈ {−1, 1}^{n}: f(x) = 0} and {x ∈ {−1, 1}^{n}: f(x) = 1}. And the quantity (𝔼f) log(1/𝔼f) measures the volume of the set {x ∈ {−1, 1}^{n}: f(x) = 1}.

If f(x_{1}, …, x_{n}) := (x_{1} + 1)/2, then equality nearly holds in Theorem 1.13. Note that, in this case, f has Fourier coefficients only of degrees zero and one. It therefore seems sensible that, if f has only Fourier coefficients of higher order, then f will oscillate, so the perimeter of its level sets should be much larger than the volume of its level sets. Kalai therefore asked if the constant 2 in Theorem 1.13 would become large when a large number of Fourier coefficients of the function are zero.

Question 1.14. Suppose k = k(n) → ∞ as n → ∞. Does there exist ω(k) > 0 such that ω(k) → ∞ as k → ∞, such that the following statement holds? Let f: {−1, 1}^{n} → {0, 1} with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with 1 ≤ |S| ≤ k. Then ∑_{i=1}^{n} I_{i}f ≥ ω(k)(𝔼f) log(1/𝔼f).

A simplification of the function from Theorem 1.12 shows that Question 1.14 has a negative answer.

Theorem 1.15 (Negative Answer to Question 1.14). There exists 0 < C, c < ∞ such that, for infinitely many n ∈ ℕ, there exists f: {−1, 1}^{n} → {0, 1} with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with 1 ≤ |S| ≤ c log n such that ∑_{i=1}^{n} I_{i}f ≤ C(𝔼f) log(1/𝔼f).

A less trivial argument allows to extend Talagrand’s theorem to tail spaces.

Theorem 1.16 (Talagrand Inequality for Tail Space). Let k ≥ 1. Let f: {−1, 1}^{n} → ℝ with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| < k. For i = 1, …, n, define D_{i}f(x) := [f(x_{1}, …, x_{n}) − f(x_{1}, …, x_{i−1}, −x_{i}, x_{i+1}, …, x_{n})]/2. Then

𝔼f^{2} ≤ \frac{3}{k} ∑_{i=1}^{n} 𝔼(D_{i}f)^{2}/ max(1, log(∥D_{i}f∥_{2}/∥D_{i}f∥_{1+e^{−2/k}})) ≤ 8 ∑_{i=1}^{n} \frac{𝔼(D_{i}f)^{2}}{k + log (∥D_{i}f∥_{2}/∥D_{i}f∥_{1})}.

(1.3)

Note that the usual form of Talagrand’s inequality is obtained by setting k = 1 and substituting f − 𝔼f in place of f on the left side of (1.3) (which is redundant for k ≥ 1).

We note that while in principle, Theorem 1.16 may indicate that the answer to Question 1.11 is positive, since the usual Talagrand Inequality implies the Kahn-Kalai-Linial Theorem 1.10. However, the improvement of Theorem 1.16 over Theorem 1.10 only occurs for k of the form k = g(n) log n where g(n) → ∞ as n → ∞.

1.4. General Setting. Theorem 1.2 and Theorem 1.6 are proven in the following general setting:

\{ \begin{matrix}• (Ω, 2^{Ω}, μ) is a finite probability space. \\ • (P_{t})_{t≥0} is a symmetric Markov semigroup on L^{2}(Ω, μ) \\ • (P_{t})_{t≥0} has generator L = −\frac{d}{dt}P_{t}|_{t=0^{+}}. \\ • 𝔼 denotes the expectation with respect to the invariant measure μ. \\ • ∥f∥_{p} will stand for (𝔼|f|^{p})^{1/p} . \end{matrix}  (1.4)

We assume additionally that L satisfies the Poincaré inequality with a positive constant C, i.e.

𝔼f^{2} − (𝔼f)^{2} ≤ C · 𝔼fLf,  (1.5)

for every f : Ω → ℝ, or equivalently, 𝔼(P_{t}f)^{2} ≤ e^{−2t/C} · 𝔼f^{2} for every t ≥ 0 and every mean-zero f. Theorem 1.2 is a special case of the following theorem:

Theorem 1.17 (Heat Smoothing). Assume that (1.4) and (1.5) hold. Then for every p ∈ (1, ∞) and every f : Ω → ℝ with 𝔼f = 0, for every t > 0,

∥P_{t}f∥_{p} ≤ exp (−\frac{(2p − 2)t}{(p^{2} − 2p + 2)C} ) · ∥f∥_{p}.

Theorem 1.6 is a special case of the following result.

Theorem 1.18 (Poincaré Inequality). Assume that (1.4) and (1.5) hold. Then for every p ∈ (1, ∞) and every f: Ω → ℝ with 𝔼f = 0 there is

𝔼 |f|^{p−1} sign(f)Lf ≥ \frac{2p − 2}{(p^{2} − 2p + 2)C} · 𝔼 |f|^{p} .

Theorem 1.18 is equivalent to Theorem 1.17. Below, we will first prove Theorem 1.18 and then deduce Theorem 1.17 as a consequence.

For Ω = ℝ, p = 4 and dμ = e^{−x^{2}/2}dx/\sqrt{2π}, with L being the generator of the Ornstein-Uhlenbeck semigroup, Theorem 1.18 was proven by P. Cattiaux, as noted in [13].

After the proof of Theorem 1.17 we briefly discuss how Theorem 1.17 and Theorem 1.18 can be extended to infinite spaces.

1.5. Organization. We prove Theorem 1.17 in Section 2. Theorem 1.18 is then derived as a Corollary in Section 3, where Theorem 1.3 is also shown. A complex interpolation proof of Theorem 1.17 is given in Section 4, albeit with worse constants. A semigroup proof of Theorem 1.17 is given in Section 5. Theorem 1.16 is proven in Section 6, and Theorem 1.12 is proven in Section 7.

2. Poincaré Inequalities

In this section we prove Theorem 1.17 and Theorem 1.18.

Let x ∈ ℝ. In what follows, we use the standard notation x_{+} := max(x, 0) and x_{−} := max(−x, 0), so that x = x_{+} − x_{−} and |x|^{p} = x_{+}^{p} + x_{−}^{p} for any x ∈ ℝ and p > 0. Also, for s > 0 we will denote by ϕ_{s} the function ϕ_{s}(x) := sign(x) · |x|^{s}, so that ϕ_{s}(x) = x_{+}^{s} − x_{−}^{s} for every x ∈ ℝ.

Lemma 2.1. Let p > 1, and let X be a real random variable with 𝔼 |X|^{p} < ∞ and 𝔼X = 0. For every p ∈ (1, ∞) \ {2},

(𝔼X_{+}^{p/2})^{2} + (𝔼X_{−}^{p/2})^{2} + (𝔼X_{+}^{p/2})^{− \frac{2}{p−2}} (𝔼X_{−}^{p/2})^{\frac{2p−2}{p−2}} + (𝔼X_{−}^{p/2})^{− \frac{2}{p−2}} (𝔼X_{+}^{p/2})^{\frac{2p−2}{p−2}} ≤ 𝔼 |X|^{p} . (2.1)

Proof. Since 𝔼X = 0,

𝔼X_{+} = 𝔼X_{−} = (1/2)𝔼 |X| .  (2.2)

Assume p > 2. Note that Jensen’s inequality implies that

𝔼X_{+}^{p/2} = 𝔼X+^{\frac{p^{2}−2p}{2p−2}} X+^{\frac{p}{2p−2}} ≤ (𝔼X_{+}^{p})^{\frac{p−2}{2p−2}} · (𝔼X_{+})^{\frac{p}{2p−2}} =^{(2.2)} (𝔼X_{+}^{p})^{\frac{p−2}{2p−2}} · (𝔼 |X| /2)^{\frac{p}{2p−2}} . (2.3)

Also, by Hölder’s inequality,

𝔼 |X| /2 =^{(2.2)} 𝔼X_{+} = 𝔼X_{+}1_{\{X>0\}} ≤ (𝔼X_{+}^{p/2})^{2/p} · ℙ(X > 0)^{\frac{p−2}{p}} .  (2.4)

Applying (2.3) to X and (−X) separately, exponentiating both sides to the power (2p − 2)/(p − 2), and then adding the results,

(𝔼X_{+}^{p/2})^{\frac{2p−2}{p−2}} + (𝔼X_{−}^{p/2})^{\frac{2p−2}{p−2}} ≤^{(2.3)} 2^{− \frac{p}{p−2}} (𝔼 |X|)^{\frac{p}{p−2}} (𝔼X_{+}^{p} + 𝔼X_{−}^{p}) = 2^{− \frac{p}{p−2}} (𝔼 |X|)^{\frac{p}{p−2}} 𝔼 |X|^{p} .

(2.5)

Applying (2.4) to X and (−X) separately, exponentiating both sides to the power −p/(p−2), and then adding the results,

(𝔼X_{+}^{p/2})^{− \frac{2}{p−2}} + (𝔼X_{−}^{p/2})^{− \frac{2}{p−2}} ≤^{(2.4)} 2^{\frac{p}{p−2}} [ℙ(X > 0) + ℙ(X < 0)](𝔼 |X|)^{− \frac{p}{p−2}} ≤ 2^{\frac{p}{p−2}} (𝔼 |X|)^{− \frac{p}{p−2}} .

(2.6)

Finally, multiplying (2.5) and (2.6) gives (2.1), if p > 2.

Assume 1 < p < 2. Then (2.5), (2.6) and (2.1) also hold. To see this, we use the following two consequences of Hölder’s inequality.

𝔼X_{+}^{p/2} = 𝔼X_{+}^{p/2}1_{\{X>0\}} ≤ (𝔼X_{+})^{p/2} · ℙ(X > 0)^{\frac{2−p}{2}} =^{(2.2)} (𝔼 |X| /2)^{p/2} · ℙ(X > 0)^{\frac{2−p}{2}} . (2.7)
𝔼 |X| /2 =^{(2.2)} 𝔼X_{+} = 𝔼X_{+}^{p−1}X_{+}^{2−p} ≤ (𝔼X_{+}^{p/2})^{\frac{2p−2}{p}} · (𝔼X_{+}^{p})^{\frac{2−p}{p}} .  (2.8)

Applying (2.7) to X and (−X) separately, exponentiating both sides by the power 2/(2−p), and then adding the results, we obtain (2.6),

(𝔼X_{+}^{p/2})^{\frac{2}{2−p}} + (𝔼X_{−}^{p/2})^{\frac{2}{2−p}} ≤^{(2.7)} 2^{− \frac{p}{2−p}} (𝔼 |X|)^{\frac{p}{2−p}} · [ℙ(X > 0) + ℙ(X < 0)] ≤ 2^{− \frac{p}{2−p}} (𝔼 |X|)^{\frac{p}{2−p}} .

Applying (2.8) to X and (−X) separately, exponentiating both sides to the power −p/(2− p), and then adding the results, we obtain (2.5),

(𝔼X_{+}^{p/2})^{− \frac{2p−2}{2−p}} + (𝔼X_{−}^{p/2})^{− \frac{2p−2}{2−p}} ≤^{(2.8)} 2^{\frac{p}{2−p}} (𝔼 |X|)^{− \frac{p}{2−p}} (𝔼X_{+}^{p} + 𝔼X_{−}^{p}) = 2^{\frac{p}{2−p}} (𝔼 |X|)^{− \frac{p}{2−p}} 𝔼 |X|^{p} .

□

Lemma 2.2. Let p ∈ (1, ∞) \ {2}. For any a, b > 0,

(a − b)^{2} ≤ \frac{p^{2} − 4p + 4}{2p^{2} − 4p + 4} · (a^{2} + b^{2} + a^{\frac{2}{2−p}} · b^{\frac{2p−2}{p−2}} + b^{\frac{2}{2−p}} · a^{\frac{2p−2}{p−2}} ).

Proof. Without loss of generality, a ≥ b. Define s := p/(p−2). Since |s| > 1, for every x ≥ 0 we have

e^{sx} + e^{−sx} ≥ e^{|s|x} − e^{−|s|x} = 2 ∑_{j=0}^{∞} \frac{|s|^{2j+1} x^{2j+1}}{(2j + 1)!} ≥ 2 |s| ∑_{j=0}^{∞} \frac{x^{2j+1}}{(2j + 1)!} = |s| (e^{x} − e^{−x}). (2.9)

Set x := (1/2) log(a/b) and square the inequality (2.9) to get

a^{s}b^{−s} + b^{s}a^{−s} + 2 ≥ s^{2}(ab^{−1} + ba^{−1} − 2).  (2.10)

Multiplying both sides of (2.10) by ab, then adding (a − b)^{2} to both sides,

a^{2} + b^{2} + a^{1−s}b^{1+s} + b^{1−s}a^{1+s} ≥ (1 + s^{2})(a − b)^{2}.  (2.11)

And (2.11) completes the lemma. □

Lemma 2.3. Let p > 1 and let X be a real random variable such that 𝔼 |X|^{p} < ∞ and 𝔼X = 0. Then

(𝔼X_{+}^{p/2} − 𝔼X_{−}^{p/2})^{2} ≤ (1 − \frac{p^{2}}{2(p^{2} − 2p + 2)}) · 𝔼 |X|^{p} .  (2.12)

Proof. If p = 2 or if X = 0 almost surely, then both sides are zero. So, we may assume p ∈ (1, ∞) \ {2} and X is nonzero on a set of positive measure. In this case, set a := 𝔼X_{+}^{p/2}, b := 𝔼X_{−}^{p/2}, and apply Lemma 2.2 and then (2.1). □

Lemma 2.4 (Stroock-Varopoulos). [17, 19] Let a, b ∈ ℝ, p > 1. Then

(ϕ_{p−1}(a) − ϕ_{p−1}(b))(a − b) ≥ \frac{4(p − 1)}{p^{2}}(ϕ_{p/2}(a) − ϕ_{p/2}(b))^{2}.  (2.13)

Proof. Applying the Cauchy-Schwarz inequality,

\frac{4}{p^{2}} (|a|^{p/2} sign(a) − |b|^{p/2} sign(b))^{2} = (∫_{a}^{b} |t|^{(p/2)−1} dt)^{2} ≤ ∫_{a}^{b} |t|^{p−2} dt · ∫_{a}^{b} dt

= \frac{1}{p − 1}(|a|^{p−1} sign(a) − |b|^{p−1} sign(b))(a − b).

□

Proof of Theorem 1.18. Recall that for any g, h : Ω → ℝ we have

𝔼gLh = \frac{1}{2} ∑_{x,y∈Ω} (−𝔼1_{\{x\}}L1_{\{y\}}) · (g(x) − g(y))(h(x) − h(y)),  (2.14)

and that for x ≠ y there is

− 𝔼1_{\{x\}}L1_{\{y\}} = μ(\{y\}) · \frac{d}{dt}(P_{t}1_{\{x\}})(y)|_{t=0^{+}} ≥ 0.  (2.15)

Therefore,

𝔼ϕ_{p−1}(f)Lf ≥^{(2.14)∧(2.15)∧(2.13)} \frac{4(p − 1)}{p^{2}}𝔼ϕ_{p/2}(f)Lϕ_{p/2}(f)

≥^{(1.5)} \frac{4(p − 1)}{Cp^{2}} · (𝔼ϕ_{p/2}(f)^{2} − (𝔼ϕ_{p/2}(f))^{2})

= \frac{4(p − 1)}{Cp^{2}} (𝔼 |f|^{p} − (𝔼f_{+}^{p/2} − 𝔼f_{−}^{p/2})^{2}) ≥^{(2.12)} \frac{4(p − 1)}{Cp^{2}} (\frac{p^{2}}{2(p^{2} − 2p + 2)}) 𝔼 |f|^{p} .

□

3. Heat Smoothing

We now show that Theorem 1.18 implies Theorem 1.17.

Proof of Theorem 1.17. Note that 𝔼f = 0 implies 𝔼P_{t}f = 0 for all t ≥ 0. So, by Theorem 1.18,

\frac{d}{dt} (exp (\frac{(2p − 2)pt}{(p^{2} − 2p + 2)C} ) · 𝔼|P_{t}f|^{p})

= exp (\frac{(2p − 2)pt}{(p^{2} − 2p + 2)C} ) (\frac{(2p − 2)p}{(p^{2} − 2p + 2)C} 𝔼|P_{t}f|^{p} − p · 𝔼ϕ_{p−1}(P_{t}f)LP_{t}f) ≤ 0.

□

Remark 3.1. One easily extends Theorem 1.18 from real-valued functions to f taking values in a Euclidean space, with the same constant. In particular, we get the same statement for complex-valued functions. Indeed, it suffices to apply Theorem 1.17 to f_{v}(x) := ⟨f(x), v⟩ and average over v’s from the unit sphere. Note that |⟨w, v⟩|^{p} averaged over the unit sphere (with respect to the uniform measure) is proportional to ∥w∥^{p}, and the proportionality constant will cancel out.

Remark 3.2. Let κ(p) = inf_{u>1} ^{\frac{u^{\frac{p}{p−2}} +u^{− \frac{p}{p−2}}}{u−u^{−1}}} . Note that κ(p) = κ(p′) since \frac{p}{p−2} = \frac{pp′}{p−p′}. A simple analysis of the proof shows that we may strengthen the assertion of Theorem 1.18 to

∥P_{t}f∥_{p} ≤ exp (−\frac{(4p − 4)t}{Cp^{2}(1 + κ(p)^{−2})}) · ∥f∥_{p}.

We have established (in the proof of Lemma 2.2) the estimate κ(p) ≥ |\frac{p}{p−2}|. One can do better, however. For example, there is κ(4) = κ(4/3) = 2\sqrt{2} and κ(6) = κ(6/5) = 2, so that for every mean-zero f we have

∥P_{t}f∥_{4} ≤ e^{− \frac{2t}{3C}} ∥f∥_{4}, ∥P_{t}f∥_{4/3} ≤ e^{− \frac{2t}{3C}} ∥f∥_{4/3},
∥P_{t}f∥_{6} ≤ e^{− \frac{4t}{9C}} ∥f∥_{6}, ∥P_{t}f∥_{6/5} ≤ e^{− \frac{4t}{9C}} ∥f∥_{6/5}.

Also, one can easily strengthen the lower bound to κ(p) ≥ \sqrt{\frac{p^{2}+4p−4}{p^{2}−4p+4}}. Indeed, for s = \frac{p}{p−2}

we have |s| > 1, so that u^{|s|/2} − u^{−|s|/2} ≥ |s|(u^{1/2} − u^{−1/2}) for every u > 1. Squaring this inequality, we get u^{s} + u^{−s} ≥ 2 + s^{2}(u + u^{−1} − 2), so that

κ(p) = inf_{u>1} \frac{u^{s} + u^{−s}}{u − u^{−1}} ≥ inf_{u>1} \frac{2 + s^{2}(u + u^{−1} − 2)}{u − u^{−1}} = \sqrt{2s^{2} − 1} = \sqrt{\frac{p^{2} + 4p − 4}{p^{2} − 4p + 4}}

which, for p > 1 and mean-zero functions f, yields

∥P_{t}f∥_{p} ≤ e^{−( \frac{2}{pp′} + \frac{8}{p^{2}p′^{2}} )t/C}∥f∥_{p}.

Corollary 3.3. Let p ∈ (1, ∞) \ {2} and let X be a mean-zero real random variable with 𝔼|X|^{p} < ∞. Then

(κ(p)^{2} + 1) · (𝔼X_{+}^{p/2} − 𝔼X_{−}^{p/2})^{2} ≤ 𝔼|X|^{p},

where κ(p) = inf_{u>1} ^{\frac{u^{\frac{p}{p−2}} +u^{− \frac{p}{p−2}}}{u−u^{−1}}} . Moreover, the constant κ(p)^{2} + 1 is optimal. Furthermore, under the assumptions of Theorem 1.18,

𝔼ϕ_{p/2}(f)Lϕ_{p/2}(f) ≥ \frac{C^{−1}}{1 + κ(p)^{−2}} · 𝔼|f|^{p},

and the constant C^{−1}/ (1 + κ(p)^{−2}) is optimal.

Proof. The above bounds follow from an obvious strengthening of the proof of Theorem 1.18 as explained in Remark 3.2. To check the optimality of the constants, choose v > 1 such that v^{\frac{p}{p−2}} + v^{− \frac{p}{p−2}} = κ(p)(v − v^{−1}) and set α = 1/(1 + v^{\frac{4}{p−2}} ) and β = 1 − α, so that β/α = v^{\frac{4}{p−2}} . Then, for a mean-zero random variable X such that ℙ(X = β) = α and ℙ(X = −α) = β, we have

𝔼|X|^{p} = (α + β)𝔼|X|^{p} = (α + β)(αβ^{p} + βα^{p}) = α^{2}β^{p} + β^{2}α^{p} + αβ^{p+1} + βα^{p+1},

and thus

(αβ)^{− \frac{p+2}{2}} 𝔼|X|^{p} = (α/β)^{\frac{p−2}{2}} + (β/α)^{\frac{p−2}{2}} + (α/β)^{p/2} + (β/α)^{p/2}
= v^{2} + v^{−2} + v^{\frac{2p}{p−2}} + v^{− \frac{2p}{p−2}} = (v^{\frac{p}{p−2}} + v^{− \frac{p}{p−2}} )^{2} + (v − v^{−1})^{2}
= (κ(p)^{2} + 1) (v − v^{−1})^{2} = (κ(p)^{2} + 1) ((α/β)^{\frac{p−2}{4}} − (β/α)^{\frac{p−2}{4}} )^{2}
= (αβ)^{− \frac{p+2}{2}} (κ(p)^{2} + 1) (αβ^{p/2} − βα^{p/2})^{2}
= (αβ)^{− \frac{p+2}{2}} (κ(p)^{2} + 1) (𝔼X_{+}^{p/2} − 𝔼X_{−}^{p/2})^{2} .

To see that the constant C^{−1}/ (1 + κ(p)^{−2}) in the second claim is also optimal, consider Ω = {−α, β} with μ = αδ_{β} + βδ_{−α}, L = C^{−1} · (Id − 𝔼), and f(x) = x. With this definition of L, equality holds in (1.5) for any function. So, arguing as in the proof of Theorem 1.18, we have 𝔼ϕ_{p/2}(f)Lϕ_{p/2}(f) = 𝔼|f|^{p} − (𝔼f_{+}^{p/2} − 𝔼f_{−}^{p/2})^{2}, and we then use the equality that holds from the first part of the present corollary. □

Remark 3.4. We now show that the dependence on p of Theorem 1.18 is of optimal order as p → 1 or as p → ∞. In what follows, L is the generator of the standard one-dimensional Ornstein-Uhlenbeck semigroup and γ is the standard N (0, 1) Gaussian measure.

For ε > 0, let g_{ε} : ℝ → ℝ be an increasing 2-Lipschitz function, smooth on ℝ \ {0} and such that g_{ε}(x) = x for |x| > ε and g_{ε} = ϕ_{3p/2} on some neighbourhood of zero. Furthermore, let f_{ε} = ϕ_{2/p} ∘ g_{ε}. Then f_{ε} is a smooth function and it belongs to the domain of L. We have

𝔼_{γ}|f_{ε}|^{p} = 𝔼_{γ}g_{ε}^{2} ≥ ∫_{ℝ\[−ε,ε]} x^{2} dγ(x) ⟶^{ε→0^{+}} 1

and

\frac{p^{2}}{4(p − 1)} · 𝔼_{γ}ϕ_{p−1}(f_{ε})Lf_{ε} = \frac{p^{2}}{4(p − 1)} ∫_{ℝ}(ϕ_{p−1} ∘ f_{ε})′f′_{ε} dγ =

∫_{ℝ} ((ϕ_{p/2} ∘ f_{ε})′)^{2} dγ = ∫_{ℝ}(g′_{ε})^{2}dγ ≤ γ(ℝ \ [−ε, ε]) + 4γ([−ε, ε]) ⟶^{ε→0^{+}} 1.

Remark 3.5. The proof of Theorem 1.17 used the finiteness of the space Ω in a nonessential way. Infinite spaces require a bit more care, so we have chosen the above presentation. However, the reader can find a proof of Theorem 1.17 in Section 5 which applies to infinite spaces, and which only uses the semigroup itself.

To conclude the section, we prove Theorem 1.3.

Proof of Theorem 1.3. Recall that

∀ 1 ≤ q ≤ ∞, ∥P_{t}f∥_{q} ≤ ∥f∥_{q} .  (3.1)

Also, if 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| < k, then for all t > 0,

∥P_{t}f∥_{2} ≤ e^{−tk} ∥f∥_{2} .  (3.2)

Let f: {−1, 1}^{n} → {−1, 0, 1}. For such f we have that 𝔼[|f|^{p}] = 𝔼[|f|] for all p and ∥P_{t}f∥_{∞} ≤ 1 for all t ≥ 0. Now, if p > 2, then

𝔼|P_{t}f|^{p} ≤ 𝔼|P_{t}f|^{2} ≤ e^{−2tk}𝔼f^{2} = e^{−2tk}𝔼|f|^{p}.

If 1 < p < 2, then from Hölder’s inequality,

𝔼 |P_{t}f|^{p} ≤ (𝔼 |P_{t}f|)^{2−p}(𝔼 |P_{t}f|^{2})^{p−1} ≤^{(3.1)∧(3.2)} (𝔼 |f|)^{2−p}e^{−tk2(p−1)}(𝔼 |f|^{2})^{p−1} = e^{−2tk(p−1)}𝔼 |f|^{p} .

□

4. An Interpolation Proof of Heat Smoothing

After the results of this paper were presented at some seminars, Fedor Nazarov informed the authors about an alternative complex interpolation proof of the strong contractivity bounds. With his kind permission, we present a simple version of such an approach, strongly inspired by Nazarov’s proof but different from it. Nazarov proved that a perturbation of a Markov operator P by an appropriately chosen small multiplicity of the expectation, i.e., T = P − δ · 𝔼, is a contraction (a trick he ascribed to Bernstein), and his interpolation bounds were more elaborate than ours.

The L^{p} spaces considered in this section are complex.

Proposition 4.1. Let (Ω, μ) be a probability space (for brevity, we leave simple measurability considerations to the reader) and let P : L^{1}(Ω, μ) → L^{1}(Ω, μ) be a linear operator with P 1 = 1, ∥P ∥_{L^{1}(Ω,μ)→L^{1}(Ω,μ)} ≤ 1, and ∥P ∥_{L^{∞}(Ω,μ)→L^{∞}(Ω,μ)} ≤ 1. Also, we assume that P is mean preserving, i.e., 𝔼P f = 𝔼f for every f ∈ L^{1}(Ω, μ). In particular, these conditions are satisfied by every, not necessarily symmetric, Markov operator P for which μ is an invariant measure. Furthermore, let as assume that there exists ε ∈ [0, 1) such that ∥P g∥_{L^{2}(Ω,μ)}^{2} ≤ (1 − ε)∥g∥_{L^{2}(Ω,μ)}^{2} for every mean-zero g. Then, for p ∈ (1, ∞),

∥P g∥_{L^{p}(Ω,μ)} ≤ (1 − 2^{2−p^{∗}}ε)^{1/p^{∗}} · ∥g∥_{L^{p}(Ω,μ)}

for every mean-zero g, where p^{∗} = max (p, \frac{p}{p−1}).

Proof. Let c be a positive constant, to be specified later. We define a measure μ̃ on a new space Ω̃ = Ω × {0, 1} by setting μ̃(A × {0}) = μ(A) and μ̃(A × {1}) = c^{2}ε · μ(A), and a linear operator T : L^{1}(Ω, μ) → L^{1}(Ω̃, μ̃) by (T f)(ω, 0) = c · (P f)(ω) and (T f)(ω, 1) = f(ω) − 𝔼f for ω ∈ Ω. Clearly, ∥T ∥_{L^{1}(Ω,μ)→L^{1}(Ω̃,μ̃)} ≤ c + 2c^{2}ε and ∥T ∥_{L^{∞}(Ω,μ)→L^{∞}(Ω̃,μ̃)} ≤ max(c, 2).

For f ∈ L^{2}(Ω, μ), let g = f − 𝔼f, so that 𝔼g = 0. Therefore also 𝔼P g = 0 and thus

∥P f∥_{L^{2}(Ω,μ)}^{2} = ∥P g + 𝔼f∥_{L^{2}(Ω,μ)}^{2} = ∥P g∥_{L^{2}(Ω,μ)}^{2} + |𝔼f|^{2}

≤ (1 − ε)∥g∥_{L^{2}(Ω,μ)}^{2} + |𝔼f|^{2} = ∥g + 𝔼f∥_{L^{2}(Ω,μ)}^{2} − ε∥g∥_{L^{2}(Ω,μ)}^{2} = ∥f∥_{L^{2}(Ω,μ)}^{2} − ε∥g∥_{L^{2}(Ω,μ)}^{2}, so that

∥T f∥_{L^{2}(Ω̃,μ̃)}^{2} = c^{2}∥P f∥_{L^{2}(Ω,μ)}^{2} + c^{2}ε∥g∥_{L^{2}(Ω,μ)}^{2} ≤ c^{2}∥f∥_{L^{2}(Ω,μ)}^{2}.

We have proved that ∥T ∥_{L^{2}(Ω,μ)→L^{2}(Ω̃,μ̃)} ≤ c.

• For p ∈ (1, 2], by the Riesz-Thorin theorem,

∥T ∥_{L^{p}(Ω,μ)→L^{p}(Ω̃,μ̃)} ≤ ∥T ∥_{L^{1}(Ω,μ)→L^{1}(Ω̃,μ̃)}^{(2−p)/p}∥T ∥_{L^{2}(Ω,μ)→L^{2}(Ω̃,μ̃)}^{(2p−2)/p} ≤ (c+2c^{2}ε)^{\frac{2−p}{p}} ·c^{\frac{2p−2}{p}} = c(1+2cε)^{\frac{2−p}{p}} .

Thus for any g ∈ L^{p}(Ω, μ) with 𝔼g = 0,

c^{p}∥P g∥_{L^{p}(Ω,μ)}^{p} + c^{2}ε∥g∥_{L^{p}(Ω,μ)}^{p} = ∥T g∥_{L^{p}(Ω̃,μ̃)}^{p} ≤ c^{p}(1 + 2cε)^{2−p}∥g∥_{L^{p}(Ω,μ)}^{p}.

Note that for c = (2^{\frac{1}{p−1}} − 2ε)^{−1}, we have

(1 + 2cε)^{2−p} − c^{2−p}ε = c^{2−p}((c^{−1} + 2ε)^{2−p} − ε) = \frac{c^{1−p}}{2} ,

and therefore

∥P g∥_{L^{p}(Ω,μ)} ≤ ((1 + 2cε)^{2−p} − c^{2−p}ε)^{1/p} ∥g∥_{L^{p}(Ω,μ)} = (1 − 2^{2−p^{∗}}ε)^{1/p^{∗}} ∥g∥_{L^{p}(Ω,μ)}.

• For p ∈ [2, ∞), we simply set c = 2. Then we have ∥T ∥_{L^{2}(Ω,μ)→L^{2}(Ω̃,μ̃)} ≤ 2 and ∥T ∥_{L^{∞}(Ω,μ)→L^{∞}(Ω̃,μ̃)} ≤ 2, and thus, by the Riesz-Thorin theorem, also ∥T ∥_{L^{p}(Ω,μ)→L^{p}(Ω̃,μ̃)} ≤ 2. Therefore, for any mean-zero g ∈ L^{p}(Ω, μ),

2^{p}∥P g∥_{L^{p}(Ω,μ)}^{p} + 4ε∥g∥_{L^{p}(Ω,μ)}^{p} = ∥T g∥_{L^{p}(Ω̃,μ̃)}^{p} ≤ 2^{p}∥g∥_{L^{p}(Ω,μ)}^{p},

so that ∥P g∥_{L^{p}(Ω,μ)} ≤ (1 − 2^{2−p}ε)^{1/p} ∥g∥_{L^{p}(Ω,μ)} = (1 − 2^{2−p^{∗}}ε)^{1/p^{∗}} ∥g∥_{L^{p}(Ω,μ)}. □

Remark 4.2. Obviously, if P : L^{2}(Ω, μ) → L^{2}(Ω, μ) is a Markov operator such that ∥P g∥_{L^{2}(Ω,μ)}^{2} ≤ (1 − ε)∥g∥_{L^{2}(Ω,μ)}^{2} for every real-valued mean-zero function g then we have also ∥P g∥_{L^{2}(Ω,μ)}^{2} ≤ (1 − ε)∥g∥_{L^{2}(Ω,μ)}^{2} for every complex-valued mean-zero function g.

5. A Semigroup Proof of Heat Smoothing

We were asked by experts in operator if the results of Section 2 and Section 3 can be extended to the setting of infinite probability spaces. The proof in this setting, which does not use the notion of the semigroup generator, is outlined in the following section.

We will need some standard and simple bounds.

Lemma 5.1. Let (P_{s})_{s≥0} be a semigroup of symmetric linear contractions on some inner product space (H, ∥ · ∥). Then for any ε, t > 0 we have ∥P_{ε+t} − P_{ε}∥_{H→H} ≤ 2t/ε.

Proof. Indeed, for f ∈ H, let h = P_{t}f − f, so that P_{ε+t}f − P_{ε}f = P_{ε}h. Then

(ε/t)^{2}∥P_{ε+t}f − P_{ε}f∥^{2} ≤ ∑_{k=0}^{[ε/t]} ∑_{l=0}^{[ε/t]} ∥P_{ε− \frac{k+l}{2} t}P_{\frac{k+l}{2} t}h∥^{2} ≤ ∑_{k=0}^{[ε/t]} ∑_{l=0}^{[ε/t]} ∥P_{\frac{k+l}{2} t}h∥^{2} = ∑_{k=0}^{[ε/t]} ∑_{l=0}^{[ε/t]}⟨P_{kt}h, P_{lt}h⟩

= ⟨∑_{k=0}^{[ε/t]} (P_{(k+1)t}f − P_{kt}f) , ∑_{l=0}^{[ε/t]} (P_{(l+1)t}f − P_{lt}f)⟩ = ∥P_{t[ε/t]+t}f − f∥^{2} ≤ (2∥f∥)^{2}.

□

The following is a weak version of the Stroock-Varopoulos inequality.

Lemma 5.2. Let P be a symmetric Markov operator on a probability space (Ω, μ). Then, for any f ∈ L^{∞}(Ω, μ) and p ∈ (1, ∞),

(p − 2)^{2} 𝔼|f|^{p} + 4(p − 1)𝔼ϕ_{p/2}(f)P (ϕ_{p/2}(f)) ≥ p^{2} 𝔼ϕ_{p−1}(f)P f.

Proof. Upon simple algebraic transformations, Lemma 2.4 implies that, μ-a.e.,

∀_{a∈ℚ} (p − 2)^{2}(|a|^{p} + |f|^{p}) + 8(p − 1)ϕ_{p/2}(a)ϕ_{p/2}(f) ≥ p^{2} (aϕ_{p−1}(f) + ϕ_{p−1}(a)f) .

Since P is linear and positivity preserving, μ-a.e. we have also

∀_{a∈ℚ} (p−2)^{2} (|a|^{p} + P (|f|^{p}))+8(p−1)ϕ_{p/2}(a)P (ϕ_{p/2}(f)) ≥ p^{2} (aP (ϕ_{p−1}(f)) + ϕ_{p−1}(a)P f) .

By the continuity in a, the same holds true μ-a.e. when ∀_{a∈ℚ} is replaced by ∀_{a∈ℝ}. In particular, μ-a.e.,

(p − 2)^{2} (|f|^{p} + P (|f|^{p})) + 8(p − 1)ϕ_{p/2}(f)P (ϕ_{p/2}(f)) ≥ p^{2} (fP (ϕ_{p−1}(f)) + ϕ_{p−1}(f)P f) .

We finish by taking the expectation of both sides and using the symmetry of P (together with the fact that symmetric Markov operators are mean-preserving). □

Definition 5.3. Let (P_{t})_{t≥0} be a symmetric Markov semigroup on a probability space (Ω, μ). For M, ε > 0 we will denote by C(M, ε) the class of all functions of the form P_{ε}φ, where φ ∈ L^{∞}(Ω, μ) and ∥φ∥_{∞} ≤ M. Furthermore, for p ∈ (1, ∞) we set

α_{p,M,ε}(t) = sup_{f∈C(M,ε)} ((p − 1)𝔼|f|^{p} + 𝔼|P_{t}f|^{p} − p𝔼ϕ_{p−1}(f)P_{t}f) .

Lemma 5.4. For any p ∈ (1, ∞) and M, ε > 0, we have α_{p,M,ε}(t)/t → 0 as t → 0^{+}.

Proof. Let f ∈ C(M, ε), i.e., f = P_{ε}φ and ∥φ∥_{∞} ≤ M. Let ρ_{p} = sup_{s≠1} \frac{|s|^{p}−ps+p−1}{(|s|+1)^{p−2}(s−1)^{2}} for

p > 2, while for p ∈ (1, 2] let ρ_{p} = sup_{s≠1} \frac{|s|^{p}−ps+p−1}{|s−1|^{p}}. Note that ρ_{p} < ∞. By the homogeneity,

(p−1)𝔼|f|^{p}+𝔼|P_{t}f|^{p}−p𝔼ϕ_{p−1}(f)P_{t}f ≤ ρ_{p} 𝔼(|P_{t}f|+|f|)^{p−2}(P_{t}f−f)^{2} ≤ (2M)^{p−2}ρ_{p}·𝔼(P_{t}f−f)^{2},

for p > 2, and for p ∈ (1, 2] we have

(p − 1)𝔼|f|^{p} + 𝔼|P_{t}f|^{p} − p𝔼ϕ_{p−1}(f)P_{t}f ≤ ρ_{p} 𝔼|P_{t}f − f|^{p} ≤ ρ_{p} · (𝔼(P_{t}f − f)^{2})^{p/2} .

We finish by Lemma 5.1: 𝔼(P_{t}f − f)^{2} = 𝔼(P_{t+ε}φ − P_{ε}φ)^{2} ≤ (2t/ε)^{2}𝔼φ^{2} ≤ (2M/ε)^{2}t^{2}. □

Now we are in a position to recover Remark 3.2 by a purely semigroup approach:

Proposition 5.5. Let (P_{t})_{t≥0} be a symmetric Markov semigroup on a probability space (Ω, μ). We also assume that it is a C_{0}-semigroup on L^{q}(Ω, μ) for some q ∈ [1, ∞), i.e., ∥P_{t}g − g∥_{q} → 0 as t → 0^{+} for every g ∈ L^{q}(Ω, μ). Furthermore, let us assume that there exists a positive constant C such that ∥P_{t}f∥_{2} ≤ e^{−t/C}∥f∥_{2} for every mean-zero function f ∈ L^{2}(Ω, μ) and every t > 0. Then, for every p ∈ (1, ∞), t > 0, and any mean-zero f,

∥P_{t}f∥_{p} ≤ exp (−\frac{(4p − 4)t}{Cp^{2}(1 + κ(p)^{−2})}) · ∥f∥_{p}.  (5.1)

Proof. Let C_{0}(M, ε) = {f ∈ C(M, ε) : 𝔼f = 0} and let L_{0}^{p}(Ω, μ) be the subspace of mean-zero functions in L^{p}(Ω, μ). The C_{0}-semigroup condition implies that ⋃_{M,ε>0} C_{0}(M, ε) is dense in

L_{0}^{p}(Ω, μ). Indeed, for φ ∈ L_{0}^{∞}(Ω, μ) by assumption we have P_{ε}φ →^{ε→0^{+}} φ in L^{q}(Ω, μ), and thus also in L^{p}(Ω, μ), since 𝔼|P_{ε}φ − φ|^{p} ≤ (2∥φ∥_{∞})^{p−q}𝔼|P_{ε}φ − φ|^{q} if p > q and ∥P_{ε}φ − φ∥_{p} ≤ ∥P_{ε}φ − φ∥_{q} if p ≤ q. Now it suffices to note that bounded mean-zero functions are dense in L_{0}^{p}(Ω, μ) and P_{ε}φ ∈ C_{0}(∥φ∥_{∞}, ε) .

Since, as a contraction, P_{t} is uniformly continuous on L^{p}(Ω, μ), it is enough to prove the assertion for f ∈ C_{0}(M, ε) for every M, ε > 0. By assumption,

𝔼ϕ_{p/2}(f)P_{t} (ϕ_{p/2}(f)) − (𝔼ϕ_{p/2}(f))^{2} = ∥P_{t/2} (ϕ_{p/2}(f) − 𝔼ϕ_{p/2}(f))∥_{2}^{2}
≤ e^{−t/C} ∥ϕ_{p/2}(f) − 𝔼ϕ_{p/2}(f)∥_{2}^{2} = e^{−t/C} · (𝔼|f|^{p} − (𝔼ϕ_{p/2}(f))^{2}) .

By Corollary 3.3, (𝔼ϕ_{p/2}(f))^{2} ≤ 𝔼|f|^{p}/ (κ(p)^{2} + 1). These inequalities, together with Lemma 5.2 and Definition 5.3, yield

𝔼|P_{t}f|^{p} ≤ (1 − \frac{(4p − 4)(1 − e^{−t/C})}{(1 + κ(p)^{−2})p}) · 𝔼|f|^{p} + α_{p,M,ε}(t).

Thus, for positive integers k and n, by a simple induction on k, we have

𝔼|P_{kt/n}f|^{p} ≤ (1 − \frac{(4p − 4)(1 − e^{−(t/n)/C})}{(1 + κ(p)^{−2})p})^{k} · 𝔼|f|^{p} + kα_{p,M,ε}(t/n)

– it suffices to consider t/n instead of t and note that f ∈ C_{0}(M, ε) implies P_{s}f ∈ C_{0}(M, ε) for all s ≥ 0. Taking k = n and n → ∞ ends the proof since, by Lemma 5.4, nα_{p,M,ε}(t/n) → 0.

□

Remark 5.6. Some authors include the C_{0}-semigroup assumption for q = 1 into the very definition of Markov semigroups. It is easy to prove that a Markov semigroup is a C_{0}- semigroup on L^{q}(Ω, μ) for some q ∈ [1, ∞) if and only if it is a C_{0}-semigroup on L^{q}(Ω, μ) for every q ∈ [1, ∞). In many cases it is convenient to test the property for q = 2. In particular, if (P_{t})_{t≥0} can be represented, by means of functional calculus, as e^{−tL} for some positive semidefinite self-adjoint operator L on L^{2}(Ω, μ), this property (for q = 2) easily follows from the spectral theorem.

For f belonging to the domain of the generator L, we obtain the L^{p} Poincaré inequality simply by differentiating (5.1) at zero.

6. Talagrand’s Inequality for Tail Space

Proof of Theorem 1.16. The argument follows the one in [10]. Let f: {−1, 1}^{n} → ℝ with 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| < k. Hence ∥P_{1/k}f∥_{2} ≤ e^{−1}∥f∥_{2} and thus

(1 − e^{−2})𝔼f^{2} ≤ 𝔼f^{2} − 𝔼(P_{1/k}f)^{2} = − ∫_{0}^{1/k} \frac{d}{dt}𝔼(P_{t})^{2} dt = 2 ∫_{0}^{1/k} 𝔼P_{t}fLP_{t}f dt  (6.1)

= 2 ∫_{0}^{1/k} ∑_{i=1}^{n} 𝔼(D_{i}P_{t}f)^{2} dt = 2 ∑_{i=1}^{n} ∫_{0}^{1/k} 𝔼(P_{t}D_{i}f)^{2} dt ≤ 2 ∑_{i=1}^{n} ∫_{0}^{1/k} ∥D_{i}f∥_{1+e^{−2t}}^{2} dt,

where the last inequality is the usual hypercontractive bound [3, 15, 4].

By Hölder’s inequality, for 0 < q < p < 2 we have

𝔼|g|^{p} = 𝔼|g|^{\frac{(2−p)q}{2−q}} |g|^{\frac{2(p−q)}{2−q}} ≤ (𝔼|g|^{q})^{\frac{2−p}{2−q}} (𝔼g^{2})^{\frac{p−q}{2−q}} .  (6.2)

Applying this estimate to g = D_{i}f, q = 1 + e^{−2/k}, and p = 1 + e^{−2t} with t ∈ (0, 1/k),

∥D_{i}f∥_{1+e^{−2t}}^{2} ≤ ∥D_{i}f∥_{2}^{2} (∥D_{i}f∥_{1+e^{−2/k}}/∥D_{i}f∥_{2})^{\frac{2 tanh t}{tanh(1/k)}} ≤ ∥D_{i}f∥_{2}^{2} (∥D_{i}f∥_{1+e^{−2/k}}/∥D_{i}f∥_{2})^{2tk} since t ↦ \frac{tanh t}{t} is decreasing on (0, ∞). Therefore

∫_{0}^{1/k} ∥D_{i}f∥_{1+e^{−2t}}^{2} dt ≤ ∥D_{i}f∥_{2}^{2} ∫_{0}^{1/k} (∥D_{i}f∥_{1+e^{−2/k}}/∥D_{i}f∥_{2})^{2tk} dt

= ∥D_{i}f∥_{2}^{2} \frac{1 − (∥D_{i}f∥_{1+e^{−2/k}}/∥D_{i}f∥_{2})^{2}}{2k log (∥D_{i}f∥_{2}/∥D_{i}f∥_{1+e^{−2/k}})}

≤ \frac{1}{k}∥D_{i}f∥_{2}^{2} min (1, \frac{1}{2 log (∥D_{i}f∥_{2}/∥D_{i}f∥_{1+e^{−2/k}})}) ,

where we have used the fact that 1 − a^{−2} ≤ 2 log a for a ≥ 1. Together with (6.1) this ends the proof of the first inequality of Theorem 1.16.

Applying (6.2) to g = D_{i}f, q = 1, and p = 1 + e^{−2/k}, we get ∥D_{i}f∥_{2}/∥D_{i}f∥_{1+e^{−2/k}} ≥ (∥D_{i}f∥_{2}/∥D_{i}f∥_{1})^{tanh(1/k)}. Since k tanh(1/k) ≥ tanh(1), the second inequality of Theorem 1.16 easily follows. □

7. The Coding Tribes Function

Recall that in Proposition 1.9 Ben-Or and Linial constructed a Boolean function with mean zero and all of whose influences are O(log n/n). The results of KKL in Theorem 1.10 imply that it is impossible for the maximum influence of a mean zero Boolean function to be of lower order. In Question 1.11 Hatami and Kalai asked if the KKL result can be strengthened if the function f satisfies additionally that 𝔼[fW_{S}] = 0 for all S with |S| < k where k(n) → ∞ as n → ∞.

The KKL result in fact implies that mean zero Boolean functions which are invariant under permutation of the inputs have an influence sum which is Ω(log n). We first note that, by taking the Ben-Or and Linial tribes function f and letting g(x_{1}, …, x_{n}, y_{1}, …, y_{k}) = f(x)y_{1} … y_{k}, we obtain a function all of whose Fourier coefficients up to level k vanish and such that its sum of influences is O(log n + k). Thus one cannot improve on the KKL sum of influence result unless k/ log n → ∞ as n → ∞. In this section we will construct an example of a function all of whose Fourier coefficients up to level Ω(log n) vanish and all of whose individual influences are at most O(log n/n) thus proving Theorem 1.12 and answering in the negative Question 1.11.

We denote by L^{>k}({−1, 1}^{n}) the space of all functions f: {−1, 1}^{n} → ℝ such that 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with |S| ≤ k. We denote by L_{+}^{>k}({−1, 1}^{n}) the space of all functions f: {−1, 1}^{n} → {−1, 1} such that 𝔼fW_{S} = 0 for all S ⊆ {1, …, n} with 1 ≤ |S| ≤ k. The difference between the two families is that the latter functions are allowed to have non-zero expectation.

We will use the convention that 1 and −1 map to the logical values TRUE and FALSE, respectively. Thus for x_{1}, …, x_{n} ∈ {−1, 1}, we have x_{1} ∨ ⋯ ∨ x_{n} = −1 if and only if x_{1} = ⋯ = x_{n} = −1, and x_{1} ∧ ⋯ ∧ x_{n} = 1 if and only if x_{1} = ⋯ = x_{n} = 1.

Our strategy is to construct a function in L_{+}^{>k}({−1, 1}^{n}) with low influences and small mean and then “correct” it so that it has mean zero

The basic idea behind the construction is the following: we want to mimic the construction of the tribes function. Recall that the tribe function is given by

(x_{1} ∧ … ∧ x_{r}) ∨ … ∨ (x_{(b−1)r+1} ∧ … ∧ x_{br})

In our construction, which we call the Coding Tribes function instead of substituting AND functions into the arguments of an OR function, we will substitute functions in L_{+}^{>k} into the arguments of an OR function.

For example for k = 1, instead of the AND function on r bits we will take the function ALLEQ on r + 1 bits, where ALLEQ(x_{1}, …, x_{r+1}) takes the value 1 exactly if the x_{i} are all 1 or all −1. Clearly the function ALLEQ is in L_{+}^{>1} since it is not correlated with a single bit. To analyze this tribe-like construction we need the following.

Proposition 7.1. Let g: {−1, 1}^{r} → {−1, 1}. Consider a function f: {−1, 1}^{n} → {−1, 1} of the form

f(x) = f_{b,r}(x) := g(x_{1}, …, x_{r}) ∨ g(x_{r+1}, …, x_{2r}) ∨ ⋯ ∨ g(x_{(b−1)r+1}, …, x_{br}), br = n,

and where ℙ(g = 1) ≤ 2^{−m} where m ≤ r. Then

𝔼f = 2(1 − (1 − ℙ(g = 1))^{b}) − 1,  (7.1)
max_{i=1,...,n} I_{i}(f) ≤ 2 × 2^{−m}.  (7.2)

One can choose b so that

|𝔼f| ≤ 2^{−m+1}.  (7.3)

Proof. Equation (7.1) is obvious, and (7.3) follows from the fact that

0 ≤ 𝔼[f_{b,r} − f_{b+1,r}] ≤ 2^{−m+1}.

Equation (7.2) is also easy: for x_{i} to be pivotal where i ∈ {dr + 1, dr + 2, … (d + 1)r}, we need that the g value of the other x_{j} in the block with j ∈ {dr + 1, dr + 2, …, (d + 1)r}, together with either x_{i} = −1 or x_{i} = 1 evaluate to 1. □

We will also need the following fact

Proposition 7.2. Consider a function of the form:

f(x) = F (g_{1}(x_{1}, …, x_{r}), g_{2}(x_{r+1}, …, x_{2r}) … g_{b}(x_{(b−1)r+1}, …, x_{br})), br = n,

where {g_{j}}_{j=1}^{b} are Boolean functions all taking the values {0, 1} or all taking the values {−1, 1}. Assume further that g_{j} ∈ L_{+}^{>k}({−1, 1}^{r}) for all j = 1, …, b. Then f ∈ L_{+}^{>k}({−1, 1}^{n}).

Proof. Since we can write F as a multilinear polynomials of its binary inputs, it suffices to show that each product of a subset of the g_{i} is in L_{+}^{>k}. By induction it suffices to show this for two functions which is immediate. □

We are particularly interested in the case where g is an indicator of a linear code. Recall that a linear code is a linear subspace of {0, 1}^{n}, where we treat {0, 1} as the field of two elements. The minimal weight w(C) of a code C is defined by

w(C) = min{∥x∥_{1} : 0 ≠ x ∈ C},

where ∥(x_{1}, …, x_{n})∥_{1} := ∑_{i=1}^{n} |x_{i}| is the Hamming weight of x. The dual code of C denoted C^{⊥} ⊆ {0, 1}^{n} is given by

C^{⊥} := {y ∈ {0, 1}^{n} : ∑_{i=1}^{n} x_{i}y_{i} = 0 mod 2, ∀ x ∈ C}.

Given a code C ⊆ {0, 1}^{n}, we will write g_{C}: {−1, 1}^{n} → {−1, 1} for the following Boolean function

g_{C}(x_{1}, …, x_{n}) := \begin{cases}1, & if ((1 − x_{1})/2, …, (1 − x_{n})/2) ∈ C \\ −1, & if ((1 − x_{1})/2, …, (1 − x_{n})/2) ∉ C. \end{cases}

By the MacWilliams identities [12], see e.g. [9, Lemma 3.3] we have:

Proposition 7.3. Let C be a linear code. Then g_{C} ∈ L_{+}^{>k} if and only if w(C^{⊥}) > k.

For example, for C = {(0, …, 0), (1 … 1)}, we have g_{C}(x) = 1 if and only if x = ±(1, …, 1), and the code C^{⊥} consists of all codewords x with ∥x∥_{1} even, so C^{⊥} has minimal weight w(C^{⊥}) = 2.

Proposition 7.4. There exists a constant γ > 1 such that for every m > 0, there exists a function g : {−1, 1}^{⌈γm⌉} → {−1, 1} with g ∈ L_{+}^{>m} and 2^{−3m} ≤ ℙ[g = 1] ≤ 2^{−m}.

Proof. The function g will be constructed via the dual of a“good code.” It is well known that good codes exist [11]. Such (linear) codes C ⊆ {0, 1}^{m′} have the following properties (where δ is independent of m′).

• (3/4)m′ ≥ dim(C) ≥ m′/4,

• w(C) ≥ δm′, where δ > 0.

We let g := g_{C^{⊥}}. Then ℙ[g = 1] = 2^{− dim(C^{⊥})}, so

2^{−3m′/4} ≤ ℙ[g = 1] ≤ 2^{−m′/4},

and by Proposition 7.3, g ∈ L_{+}^{>k} where

w(C^{⊥⊥}) = w(C) ≥ δm′ = k.

Setting γ = max(4, δ^{−1}), the proof follows. □

Propositions 7.1 and 7.4 are already enough to prove that Harper’s inequality cannot be improved for tail spaces.

Proof of Theorem 1.15. Let b = 1 in Proposition 7.1 and use g from Proposition 7.4. Setting n := ⌈γm⌉ we get g: {−1, 1}^{n} → {−1, 1} with g ∈ L_{+}^{>m}, 𝔼g = 2ℙ(g = 1)−1, max_{i=1,...,n} I_{i}g ≤ 2ℙ(g = 1). Then, the function f := (1 + h)/2 = 1_{(h=1)} satisfies f: {−1, 1}^{n} → {0, 1}, ∑_{i=1}^{n} I_{i}f ≤ 2nℙ(g = 1) ≤ γmℙ(g = 1), and 𝔼f = 1/2 + 𝔼h/2 = ℙ(g = 1). From Proposition 7.4, ℙ[g = 1] ≤ 2^{−m}. That is,

\frac{∑_{i=1}^{n} I_{i}f}{(𝔼f) log(1/𝔼f)} ≤ \frac{γm}{log(1/𝔼f)} ≤ γ \frac{m}{m} = γ.

□

Substituting g from Proposition 7.4 into Propositions 7.1 and 7.2, and letting n = mb, where b is chosen so that 𝔼[f] is as close to 0 as possible (so that m = O(log n)), we obtain:

Theorem 7.5. There exist a family of Boolean functions f = f_{n} : {−1, 1}^{n} → {−1, 1} such that

• f ∈ L_{+}^{>Ω(log n)}({−1, 1}^{n}).
• For all i ∈ {1, …, n}, I_{i}(f) ≤ O((log n)/n).
• |𝔼f| ≤ O((log n)/n).

We now wish to find similar functions that have zero mean.

Corollary 7.6. There exist a family of functions g = g_{n} : {−1, 1}^{2n} → {−1, 0, 1} such that • g ∈ L^{>Ω(log n)}({−1, 1}^{2n}).

• For all i ∈ {1, …, n}, I_{i}(g) ≤ O(log n/n).
• ℙ[g = 1] = 1/4 − O((log n)/n), ℙ[g = −1] = 1/4 − O((log n)/n).

Proof. Let f from Theorem 7.5 and define

g(x_{1}, …, x_{n}, y_{1}, …, y_{n}) := \frac{1}{2}(f(x_{1}, …, x_{n}) − f(y_{1}, …, y_{n})).

□

With a little more work we can construct functions with the desired properties taking only values 0 and 1. For this we note that Proposition 7.4 implies the following:

Corollary 7.7. There exists a constant γ > 1 such that for every n, there exists a function g : {−1, 1}^{γn} → {0, 1} with g ∈ L_{+}^{>n} and ℙ[g = 1] = 2^{−n−d} for some nonnegative integer d. Moreover, g has the following property: For y ∈ {−1, 1}^{γn}, write g_{y}(x) = g(y_{1}x_{1}, …, y_{n}x_{n}). Then for all y, y′ ∈ {−1, 1}^{γn} we either have g_{y} = g_{y′} or the function g_{y}g_{y′} is identically 0.

Proof. Let h be the function from Proposition 7.4 and let g = 1_{(h=1)} = (h + 1)/2. Then all the stated properties but the last one clearly hold if γ is large enough. The last property follows from the fact that cosets of linear codes are either identical or disjoint. □

Lemma 7.8. The exists a constant γ > 1, such that the following holds. Let 0 ≤ t < 2^{n}, t ∈ ℤ. Then there exists a function f : {−1, 1}^{γn} → {0, 1} such that 𝔼f = t/2^{n} and f ∈ L_{+}^{>n}({−1, 1}^{γn}).

Proof. From Corollary 7.7 in the case t = 1 we can find a function in L_{+}^{>n} and 𝔼[f] = 2^{−n−d}, where d is a nonnegative integer. The general case follows by taking h = ∑_{i} g_{y^{i}} where y^{i} are chosen so that g_{y^{i}}g_{y^{j}} = 0 for i ≠ j. □

Theorem 7.9. There exist a family of Boolean functions G = G_{n} : {−1, 1}^{n} → {−1, 1} such that

• G ∈ L^{>Ω(log n)}

• For all i ∈ {1, …, n}, I_{i}(G) ≤ O((log n)/n).

Proof. We revise the construction of Theorem 7.5 as follows. Using Lemma 7.8, choose g_{0}, …, g_{b}: {−1, 1}^{⌈γm⌉} → {−1, 1} all in L_{+}^{>m}. Moreover, for 1 ≤ i ≤ b, let ℙ[g_{i} = 1] = 2^{−m} and for i = 0, let ℙ[g_{0} = 1] = 4 × 2^{−m}.

We choose b to be the largest integer so that

𝔼f = (1 − (1 − 2^{−m})^{b}(1 − 2^{−m+2})) − 1 > 0.

and let n = (b + 1)⌈γm⌉. Note that m = O(log n) and that

0 ≤ 𝔼f ≤ 2^{−m}.

By Lemma 7.8, let h: {−1, 1}^{⌈γn⌉} → {0, 1} with

2𝔼h = 𝔼f/ℙ[g_{0} = 1]  (7.4)

and such that h is in L_{+}^{>n}({−1, 1}^{γn}).

Let G: {−1, 1}^{γn+n} → {−1, 1} be a function of the x and y given by:

G(x, y) := f(x) − 2 · g_{0}(x) · h(y)

Then clearly G(x, y) ∈ L_{+}^{m}({−1, 1}^{⌈γn⌉+n}) and moreover 𝔼g = 0 by (7.4). So we have G ∈ L^{m}({−1, 1}^{⌈γn⌉+n}). Finally, since f(x) and g_{0}(x) have all of their influences O((log n)/n) the same is true for all of the x variables in g. Moreover, a y variables can be influential if and only if g_{0}(x) = 1. Therefore the influence of all of the y variables is also O((log n)/n). The proof follows. □

Acknowledgement. Thanks for Fedor Nazarov for sharing his complex interpolation arguments of the main theorem which strongly inspired the proof of Section 4. Thanks to Ryan O’Donnell for helpful discussions and references, particularly [18] and [7]. Thanks also to Michel Ledoux, Camil Muscalu, Assaf Naor, and Bob Strichartz for helpful discussions.

References

1. William Beckner, A generalized Poincaré inequality for Gaussian measures, Proc. Amer. Math. Soc. 105 (1989), no. 2, 397–400. MR 954373 (89m:42027)

2. Michael Ben-Or and Nathan Linial, Collective coin flipping, Randomness and Computation (S. Micali, ed.), Academic Press, New York, 1989, pp. 91–115.

3. 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). MR 0283496 (44 #727)

4. Leonard Gross, Logarithmic Sobolev inequalities, Amer. J. Math. 97 (1975), no. 4, 1061–1083. MR 0420249 (54 #8263)

5. L. H. Harper, Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math. 12 (1964), 131–135. MR 0162737 (29 #41)

6. Masanori Hino, Exponential decay of positivity preserving semigroups on L^{p}, Osaka J. Math. 37 (2000), no. 3, 603–624. MR 1789439 (2001k:60109)

7. Svante Janson, Gaussian Hilbert spaces, Cambridge Tracts in Mathematics, vol. 129, Cambridge University Press, Cambridge, 1997. MR 1474726 (99f:60082)

8. 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.

9. Subhash Khot and Assaf Naor, Nonembeddability theorems via Fourier analysis, Math. Ann. 334 (2006), no. 4, 821–852. MR 2209259 (2008a:46016)

10. 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 (2002g:82001)

11. F. J. MacWilliams and N. J. A. Sloane, The theory of error-correcting codes. I, North-Holland Publishing Co., Amsterdam-New York-Oxford, 1977, North-Holland Mathematical Library, Vol. 16. MR 0465509 (57 #5408a)

12. Jessie MacWilliams, A theorem on the distribution of weights in a systematic code, Bell System Tech. J. 42 (1963), 79–94. MR 0149978 (26 #7462)

13. Manor Mendel and Assaf Naor, Nonlinear spectral calculus and super-expanders, Publ. Math. Inst. Hautes Études Sci. 119 (2014), no. 1, 1–95. MR 3210176

14. 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. MR 770960 (86i:60150)

15. Edward Nelson, The free Markoff field, J. Functional Analysis 12 (1973), 211–227. MR 0343816 (49 #8556)

16. Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, 2014.

17. D. W. Stroock, An introduction to the theory of large deviations, Universitext, Springer-Verlag, New York, 1984. MR 755154 (86h:60067a)

18. 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 (91b:47078)

19. N. Th. Varopoulos, Hardy-Littlewood theory for semigroups, J. Funct. Anal. 63 (1985), no. 2, 240–260. MR 803094 (87a:31011)

UCLA Department of Mathematics, Los Angeles, CA 90095-1555

E-mail address: heilman@cims.nyu.edu

Department of Statistics, University of Pennsylvania, Philadelphia, PA 19104 and Departments of Statistics and Computer Science, U.C. Berkeley, Berkeley CA 94720

E-mail address: mossel@wharton.upenn.edu

Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland

E-mail address: koles@mimuw.edu.pl