A MOMENT MAJORIZATION PRINCIPLE FOR RANDOM MATRIX ENSEMBLES

STEVEN HEILMAN

Abstract. We prove a moment majorization principle for matrix-valued functions with domain {−1, 1}^{m}, m ∈ ℕ. The principle is an inequality between higher-order moments of a non-commutative multilinear polynomial with different random matrix ensemble inputs, where each variable has small influence and the variables are instantiated independently. This technical result can be interpreted as a noncommutative generalization of one of the two inequalities of the seminal invariance principle of Mossel, O’Donnell and Oleszkiewicz. Applications to noncommutative noise stability and noncommutative anticoncentration are given.

1. Introduction

1.1. A noncommutative moment majorization theorem. We study matrix-valued functions f with domain {−1, 1}^{m} within the context of probability theory and Fourier analysis. More specifically, we study functions f such that, for every σ ∈ {−1, 1}^{m}, the operator norm of f(σ) is at most 1. The special case when f is valued in the two-point space {−1, 1} has been studied extensively within theoretical computer science [KKL88], but also in diverse areas such as combinatorics, isoperimetry [Tal94], or social choice theory [Kal02, MOO10, MN15]. (For a more comprehensive list of references and discussion, see e.g. the survey [O’D14b].) In applications to theoretical computer science, a function f: {−1, 1}^{m} → {−1, 1} can be used to represent an instance of a combinatorial optimization problem. That is, the function f can be thought of as a list of elements of {−1, 1}, seen as a Boolean assignment to the 2^{m} variables of some constraint satisfaction problem. Functions with domain {−1, 1}^{m} and range the simplex {(x_{1}, …, x_{n}) ∈ ℝ^{n}: ∑_{i=1}^{n} x_{i} = 1, x_{1} ≥ 0, …, x_{n} ≥ 0} have also been considered [KN09, KN13, IM12]. Projecting f onto each coordinate gives a family of functions with range [0, 1], so that similar tools to the Boolean case can be applied.

In many of the applications listed above a standard manipulation is to extend f to a multilinear polynomial, so that the distribution of f can be studied under different distributions on its domain, such as the standard Gaussian distribution. In our setting it is natural (and, as we will see, for our purposes necessary) to investigate the behavior of matrix-valued functions under distributions on their domain that allow the possibility for matrix variables. For any set S, let M_{n}(S) denotes the n × n matrices with entries in S. Any f : {−1, 1}^{m} → M_{n}(ℂ) can be extended to a multilinear polynomial in m noncommutative variables with matrix coefficients. Consider for instance the case m = 2 and the polynomial f(σ_{1}, σ_{2}) = σ_{1}σ_{2}, where σ_{1}, σ_{2} ∈ {−1, 1}. Since the variables σ_{1}, σ_{2} commute, it is not necessary to specify the order in which the product of the variables is taken in f. However, once f is extended to matrix variables X_{1}, X_{2}, an ordering needs to be specified. We adopt the convention of ordering matrix variables by increasing order, e.g. f(X_{1}, X_{2}) = X_{1}X_{2}.

2010 Mathematics Subject Classification. 68Q17,60E15,47A50.

Key words and phrases. invariance principle, moment majorization, Lindeberg replacement.

Let d, m, n be positive integers. For us, a noncommutative multilinear polynomial of degree d in m variables can be expressed as

Q(X_{1}, …, X_{m}) = ∑_{S⊆{1,...,m}: |S|≤d} Q̂(S) ∏_{i∈S} X_{i},

where Q̂(S) is an n × n complex matrix for every S ⊆ {1, …, m}, X_{1}, …, X_{m} are noncommutative n × n matrix variables, and the product ∏_{i∈S} X_{i} is always taken in increasing order. For example, ∏_{i∈{1,2}} X_{i} = X_{1}X_{2}. Noncommutative polynomials appear in many other contexts, most notably, within free probability [Voi91, Theorem 3.3]. In addition there is a general theory of so-called nc-functions [KVV14], but this theory does not seem to apply to the noncommutative polynomials we consider here. (An nc function h is a function defined on matrices of any dimension, such that, for any n ≥ 1, and for any n × n matrices A, B, C such that C is invertible, h(CAC^{−1}) = Ch(A)C^{−1} and h(A ⊕ B) = h(A) ⊕ h(B). Neither property is satisfied by a general matrix-valued non-commutative polynomial as defined below.)

Our main goal consists in bounding the moments of Q for different random matrix distributions in the domain, when all partial derivatives of Q are small (i.e. when Q has small influences). In particular, we would like to say that the moments of polynomials Q with small influences under Gaussian random matrix inputs are close to the moments of Q under uniform {−1, 1}^{m} inputs. Unfortunately, this task is in general impossible. For example, consider the linear polynomial Q(X_{1}, …, X_{m}) = (X_{1} + ⋯ + X_{m})/\sqrt{m}. For any square matrix A, let |A| = (AA^{∗})^{1/2}. Let b_{1}, …, b_{m} be i.i.d. uniform random variables in {−1, 1}, and let I denote the n × n identity matrix. Then 𝔼(1/n)Tr |Q(b_{1}I, …, b_{m}I)|^{4} = 3 − 2/m. On the other hand, let G_{1}, …, G_{m} be n × n independent Wigner matrices with real Gaussian entries. In this case Q(G_{1}, …, G_{m}) is equal in distribution to G_{1}, and in particular lim_{n→∞}(1/n)Tr |Q(G_{1}, …, G_{m})|^{4} = 2, by the semicircle law. Thus even though the first and second moments of the input distributions match, i.e. 𝔼b_{1} = 0, 𝔼b_{1}^{2} = 1, 𝔼G_{1} = 0 and 𝔼G_{1}G_{1}^{∗} = I, the associated moments of Q can be very different.

In summary, a general invariance principle cannot hold in this noncommutative setting. We could instead try to prove a weaker statement such as: the moments of Q under noncommutative inputs with 𝔼G_{1} = 0 and 𝔼G_{1}G_{1}^{∗} = I are bounded by the moments of Q under Boolean inputs. We call such a statement a moment majorization theorem. Unfortunately, this is also not true in general, as we now show. For any 1 ≤ i ≤ n, let A_{i} be the n × n matrix with a 1 in the first row and i^{th} column, and zeros in all other entries. Then for any 1 ≤ j, k ≤ n with j ≠ k, we have A_{j}A_{k}^{∗} = 0. Consider the linear polynomial

Q(X_{1}, …, X_{n}) = ∑_{i=0}^{n−1} B^{i}AX_{i},

which is such that 𝔼Tr |Q(b_{1}, …, b_{n})|^{4} = n. Now let H_{1} be a uniformly random Haar distributed n × n unitary matrix, and let H_{2}, …, H_{n} be independent copies of H_{1}. Then

𝔼Tr|Q(H_{1}, …, H_{n})|^{4} = nTr |A_{1}|^{4}+n(n−1)𝔼Tr(|A_{1}|^{2} H_{1} |A_{1}|^{2} H_{1}^{∗}) = n+n(n−1)/n = 2n−1.

Since a general noncommutative majorization principle cannot hold we instead establish a limited moment majorization theorem, which will nevertheless be sufficient for our applications. We make two changes. We first increase the dimension of the random matrix inputs G_{1}, …, G_{m}. That is, we allow the variables of Q to take values in the set of p × p matrices with p > n by defining the p × p matrix

ι(A) = (\begin{matrix}A & 0 \\ 0 & 0 \end{matrix})

for any n × n matrix A, and

Q^{ι}(X_{1}, …, X_{m}) = ∑_{S⊆{1,...,m}} ι(Q̂(S)) ∏_{i∈S} X_{i},

where X_{1}, …, X_{m} are noncommutative p × p matrix variables. Second, we randomly rotate G_{1}, …, G_{m} by p × p Haar-distributed random unitary matrices H_{1}, …, H_{m}.

We state one particular variant of our noncommutative moment majorization theorem. Let n be a positive integer and let p be a positive multiple of n. We write H ∼ H to denote a p × p Haar-distributed random unitary matrix, b ∼ B for a uniformly random b ∈ {−1, 1}, and G ∼ G for any random variable taking values in M_{n}(ℂ) such that 𝔼G = 0 and 𝔼GG^{∗} = I. We also write G′ ∼ G ⊗I to denote G′ = G ⊗ I with G ∼ G, so that G′ is a p×p matrix. We use the succinct notation G_{i} ∼ G to denote a collection G_{1}, …, G_{m} of independent random matrices with distribution G, and denote Q(G_{1}, …, G_{m}) as Q{G_{i}}. The operator norm of a matrix A is denoted ∥A∥.

Theorem 1.1 (Noncommutative Fourth Moment Majorization). Let Q be a noncommutative multilinear polynomial of degree d in m variables such that ∥Q(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m}. Let τ := max_{i=1,...,m} ∑_{S⊆{1,...,m}: i∈S} Tr(Q̂(S)Q̂(S)^{∗}) be the maximum influence of Q. Let G_{i} ∼ G and c_{2} ≥ 1 such that ∥𝔼(G_{1}G_{1}^{∗})^{2}∥ ≤ c_{2}. Then

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{4} ≤ 𝔼_{b_{i}∼B} \frac{1}{n}Tr |Q\{b_{i}\}|^{4} + 8(8c_{2})^{4d}n^{4}τ^{1/4} + O_{m,n}(p^{−1/2}).  (1)

Remark 1.2. This Theorem is a special case of Theorem 3.9 below. The term 8(8c_{2})^{4d}n^{4}τ^{1/4} on the right-hand side of (1) can be replaced by (8c_{2})^{4d}τ by additionally assuming that 𝔼a_{1}a_{2}a_{3} = 0 for any a_{1}, a_{2}, a_{3} which are (possibly repeated) entries of G_{1}. We omit the proof of this strengthened statement, since the details are essentially identical to the proof of Theorem 3.5.

Remark 1.3. Note that, although Q^{ι} takes values in the set of p × p matrices, the trace is normalized by 1/n, and Q^{ι} still “acts like” an n × n matrix. In particular the moments of Q^{ι} do not become arbitrarily small in general; for instance it holds (see Lemma 2.5 below) that

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2} = 𝔼_{b_{i}∼B} \frac{1}{n}Tr |Q\{b_{i}\}|^{2} .

Theorem 1.1 shows that the fourth moment of Q with appropriate random matrix inputs is bounded by the fourth moment of Q with Boolean inputs. We provide a variant of this majorization principle for higher order moments (Theorem 3.9) and for increasing test functions (Theorem 3.5). These majorization principles all have dependence on the degree of the polynomial, but we also give degree-independent bounds for polynomials whose higher order coefficients decay at an exponential rate (Corollary 3.8).

Although majorization principles such as Theorem 1.1 involve the trace norm of a polynomial, we can obtain bounds on the operator norm of Q in the following way. Let t ∈ ℝ and consider the function t ↦ (max(0, |t| − 1))^{2}. This function can be applied to selfadjoint matrices via spectral calculus, and A ↦ (max(0, (AA^{∗})^{1/2} − 1))^{2} = 0 if the singular values of A are all bounded by 1. In particular, if ∥Q(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m} then (max(0, (Q(σ)Q(σ)^{∗})^{1/2}−1))^{2} = 0 for all σ ∈ {−1, 1}^{m}. The following majorization principle gives control on the operator norm of Q when we substitute appropriate random matrices into the domain of Q.

Theorem 1.4 (Noncommutative Operator Norm Majorization). Let Q be a noncommutative multilinear polynomial of degree d. Suppose ∥Q(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m}. Let τ := max_{i=1,...,m} ∑_{S⊆{1,...,m}: i∈S} Tr(Q̂(S)Q̂(S)^{∗}) be the maximum influence of Q. Let G_{i} ∼ G and c_{2}, c_{3} ≥ 1 such that ∥𝔼(G_{1}G_{1}^{∗})^{2}∥ ≤ c_{2} and ∥𝔼(G_{1}G_{1}^{∗})^{3}∥ ≤ c_{3}. Then

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr( max(0, |Q^{ι}\{G_{i}H_{i}\}| − 1))^{2} ≤ (8c_{2}c_{3})^{9d}n^{1/2}τ^{1/6} + O_{m,n}(τ^{−1/3}p^{−1/2}). (2)

This Theorem appears below in Theorem 3.7. We will use this theorem to argue that under the proper normalization condition a low-influence polynomial typically maps random Gaussian matrix inputs to matrices of norm not much larger than 1. The ensemble that will be of most interest for us is the following.

Example 1.5. Let N > 0. Let V_{1}, …, V_{N} be n×n complex matrices such that ∑_{i=1}^{N} V_{i}V_{i}^{∗} = 1. Let g_{1}, …, g_{N} be i.i.d. standard complex Gaussian random variables (so that 𝔼g_{1} = 0 and 𝔼 |g_{1}|^{2} = 1.) Define G_{1} = ∑_{i=1}^{N} g_{i}V_{i}, and let G_{2}, …, G_{m} be independent copies of G_{1}. Then it follows from [HT99, Corollary 2.8] that the random matrices G_{1}, …, G_{m} satisfy the hypothesis of Theorem 1.1 with c_{2} = 2. In the case that V_{1}, …, V_{N} are real matrices and g_{1}, …, g_{N} are i.i.d. standard real Gaussians, the hypothesis of Theorem 1.1 is satisfied with c_{2} = 4 · 2 = 8, as follows from the complex case and the inequality ∥𝔼(ℜ(G_{1})ℜ(G_{1})^{∗})^{2}∥ ≤ ∥𝔼(G_{1}G_{1}^{∗})^{2}∥ ≤ 2 when g_{1}, …, g_{N} are complex.

Here are some other examples of random matrix ensembles satisfying the hypothesis of Theorem 1.4.

Example 1.6. Example 1.5 specifically applies to Gaussian Wigner matrices as follows. Let U_{1}, …, U_{n^{2}} be n × n matrices such that these matrices are the standard orthonormal basis of ℂ^{n^{2}}. Then G_{1} is a Wigner matrix and the hypothesis of Theorem 1.1 is satisfied with c_{2} = 2. Similarly, let U_{1}, …, U_{n(n+1)/2} be n × n matrices such that these matrices are the standard orthonormal basis of symmetric n × n matrices. Then G_{1} is a Wigner matrix and the hypothesis of Theorem 1.1 is satisfied with c_{2} = 2 (see [DS01, Theorem II.11] or [Ver12, Theorem 5.32]).

Example 1.7. Let G_{1}, …, G_{m} be i.i.d. n × n Haar-distributed random unitary matrices. Then the random matrices G_{1}, …, G_{m} satisfy the hypothesis of Theorem 1.1 with c_{2} = 1.

We give a brief overview of the strategy of the proof of Theorem 1.4 and its generalization, Theorem 3.9. In order to prove the majorization principle, we first establish some basic facts about Fourier analysis of matrix-valued functions f in Section 2. In particular, starting from a function f: {−1, 1}^{m} → M_{n}(ℂ), we extend f to a noncommutative multilinear polynomial Q = Q_{f} of m variables.

For these polynomials Q, we consider a few different inner products, norms, derivatives, Plancherel identities, and we also define the Ornstein-Uhlenbeck semigroup. We then prove a noncommutative hypercontractive inequality for such polynomials Q. This hypercontractive inequality is developed in Section 3 and proven in Theorem 3.1. It can also be considered a polynomial generalization of the matrix Khintchine inequality.

To prove the noncommutative majorization principle, we use the Lindeberg replacement method from [MOO10, Cha06], but in our (matrix-valued) polynomials, we are replacing one random variable with one random matrix, one at a time. The “second order” terms in this replacement have a noncommutative nature which introduces an error. Instead of trying to bound this error (which seems difficult or impossible in general), we choose particular random matrices such that the “second order” terms are small. This is accomplished by

replacing an n × n random matrix X with a much larger p × p matrix (\begin{matrix}X & 0 \\ 0 & 0 \end{matrix}) H, where H

is a uniformly random p × p unitary matrix and p > n. When p → ∞, the noncommutative “second order” errors in the Lindeberg replacement vanish.

1.2. Applications. The commutative invariance principle [Rot79, Cha06, MOO10] implies that if Q is a commutative multilinear polynomial with small derivatives (i.e. small influences), then the distribution of Q on i.i.d. uniform inputs in {−1, 1} is close to the distribution of Q on i.i.d. standard Gaussian random variables. A more general statement can be made for more general functions and distributions; for details see e.g. [MOO10]. An invariance principle can also be considered as a concentration inequality, generalizing the central limit theorem with error bounds (i.e. the Berry-Esséen Theorem). For other variants of invariance principles, see [Mos10, IM12].

The form of the invariance principle given in [MOO10] is proven by a combination of the Lindeberg replacement argument and the hypercontractive inequality [Bon70, Nel73, Gro75]. That is, one replaces one argument of Q at a time, adding up the resulting errors and controlling them via the hypercontractive inequality. One version of hypercontractivity says that a higher L_{q} norm of a polynomial is bounded by a lower L_{p} norm of that polynomial, where q > p, with a bound dependent on the degree of the polynomial Q. For example, if Q has degree d, then the L_{4} norm of Q is bounded by 9^{d} times the L_{2} norm of Q.

The commutative invariance principle has seen many applications [O’D14b, O’D14a] in recent years. Here is a small sample of such applications and references: isoperimetric problems in Gaussian space and in the hypercube [MOO10, IM12], social choice theory, Unique Games hardness results [KKMO07, IM12], analysis of algorithms [BR15], random matrix theory [MP14], free probability [NPR10], optimization of noise sensitivity [Kan14]. The Lindeberg replacement argument itself has many applications, e.g. in proving the universality of eigenvalue statistics for Wigner matrices [TV11, Theorem 15].

We anticipate that our noncommutative majorization principle will find similar applications. Even though it is impossible to prove a noncommutative invariance principle in general, most applications of the commutative invariance principle only involve one direction of the inequality. That is, most applications of the invariance principle are really just applications of a majorization principle such as Theorem 1.1 or 1.4.

To demonstrate further applications of our majorization principle, we show in Section 4 that one of the two main parts of the proof of the Majority is Stablest Theorem from [MOO10] can be extended to the noncommutative setting. Then, in Section 5, we demonstrate a (probably sub-optimal) anti-concentration estimate for noncommutative multilinear polynomials. Both of these results proceed as in [MOO10] by replacing their invariance principle with our majorization principle.

Since majorization principles such as Theorems 1.1 and 1.4 show the closeness of one distribution to another, these statements could be fit into the “concentration of measure” paradigm. The paper [MS12] proves a concentration inequality for noncommutative polynomials, but these methods seem insufficient to prove a majorization principle. An invariance principle has been proven in the free probability setting [DN14], but the details of exactly what polynomials can be dealt with, and which distributions can be handled, seem incomparable to our majorization principle.

Remark 1.8. We remark that, although it may be tempting to try to prove Theorem 1.4 from the commutative invariance principle of [MOO10], there seems to be no straightforward way to accomplish this task. For example, we could interpret each entry in the output of a noncommutative polynomial Q as a commutative polynomial function of the inputs. But then in order to control Tr |Q|^{4}, we would need information on the joint distribution of the entries of Q, which is not provided by the invariance principle of [MOO10].

2. Definitions, background and notation

2.1. Matrices. For n ∈ ℕ we denote the set of n by n matrices by M_{n}(ℂ). We use M_{n×n}(ℂ) in place of M_{n^{2}} to denote n^{2} by n^{2} matrices when we wish to emphasize that a specific tensor decomposition of the space ℂ^{n^{2}} = ℂ^{n} ⊗ ℂ^{n} on which the matrix acts has been fixed.

For A ∈ M_{n}(ℂ), ∥A∥ is the operator norm of A (the largest singular value). We denote by A^{∗} the conjugate-transpose. The absolute value is |A| = (AA^{∗})^{1/2}. We use I to denote the identity matrix.

Any real function f : ℝ → ℝ can be applied to a Hermitian matrix A by diagonalizing A and applying f to the eigenvalues of A. Define Chop : ℝ → ℝ as Chop(t) = t if |t| ≤ 1, Chop(t) = 1 if t ≥ 1, and Chop(t) = −1 if t ≤ −1.

2.2. Asymptotic Notation. Let a, b, c ∈ ℝ. We write a = O_{c}(b) if there exists a constant C(c) > 0 such that |a| ≤ C(c) |b|. We write a ≤ O_{c}(b) if there exists a constant C(c) > 0 such that a ≤ C(c)b.

2.3. Random variables and expectations. The following notational conventions will be useful when working with functions of multiple variables. Let m, n ∈ ℕ and let S, T be arbitrary sets. Let f : S^{m} → T and let X_{1}, …, X_{n} be independent random variables with the same distribution X taking values in S. Then we will denote 𝔼f(X_{1}, …, X_{m}) by 𝔼_{X_{j}∼X} f{X_{j}}; more generally the curly bracket notation f{A_{j}} will be used to denote f(A_{1}, …, A_{m}).

We will use the following ensembles. Let n, N ∈ ℕ, and let p be a positive multiple of n. H ∼ H denotes a p × p Haar-distributed random unitary matrix, where the dimension p will always be clear from context. b ∼ B denotes a uniformly random b ∈ {±1}. G ∼ G denotes any random variable taking values in M_{n}(ℂ) such that 𝔼G = 0 and 𝔼GG^{∗} = I. And G′ ∼ G ⊗I denotes G′ = G ⊗ I_{p/n} ∈ M_{p}(ℂ), where G ∼ G. G ∼ V denotes a random variable distributed as G = ∑_{i=1}^{N} g_{i}V_{i}, where g_{1}, …, g_{N} are i.i.d. standard complex Gaussian random variables and V_{1}, …, V_{N} are n×n complex matrices satisfying ∑_{i=1}^{N} V_{i}V_{i}^{∗} = ∑_{i=1}^{N} V_{i}^{∗}V_{i} = I_{n}. And G′ ∼ V ⊗ I denotes G′ = G ⊗ I_{p/n} ∈ M_{p}(ℂ), where G ∼ V. Whenever V is used the matrices V_{1}, …, V_{N} will be clear from context. We also sometimes write G_{j} ∼ D to mean G_{1}, …, G_{m} are independent random variables with distribution D, where again m will always be clear from context.

2.4. Fourier expansions. Let n, m ∈ ℕ and f, h: {−1, 1}^{m} → M_{n}(ℂ). We consider the inner product

⟨f, h⟩ := 𝔼_{b_{j}∼B} Tr(f{b_{j}}(h{b_{j}})^{∗}) = 2^{−m} ∑_{σ∈{−1,1}^{m}} Tr(f(σ)h(σ)^{∗}).

Given S ⊆ {1, …, m} and σ = (σ_{1}, … σ_{m}) ∈ {−1, 1}^{m}, define

W_{S}(σ) := ∏_{i∈S} σ_{i}.

The set of functions {W_{S}}_{S⊆{1,...,n}} forms an orthonormal basis for the space of functions from {−1, 1}^{m} to M_{n}(ℂ), when it is viewed as a vector space over ℂ with respect to the inner product ⟨·, ·⟩.

Let f̂(S) := 2^{−m} ∑_{σ∈{−1,1}^{m}} f(σ)W_{S}(σ) be the Fourier coefficient of f associated to S. Note that f̂(S) ∈ M_{n}(ℂ). Then f = ∑_{S⊆{1,...,m}} f̂(S)W_{S}, and

2^{−m} ∑_{σ∈{−1,1}^{m}} f(σ)(g(σ))^{∗} = 2^{−m} ∑_{σ∈{−1,1}^{m}} ∑_{S,S′⊆{1,...,m}} f̂(S)(ĝ(S′))^{∗}W_{S}(σ)W_{S′}(σ)

= ∑_{S,S′⊆{1,...,m}} f̂(S)(ĝ(S′))^{∗} · 2^{−m} ∑_{σ∈{−1,1}^{m}} W_{S}(σ)W_{S′}(σ)

= ∑_{S⊆{1,...,m}} f̂(S)(ĝ(S))^{∗}.  (3)

2.5. Noncommutative polynomials. Let n, m ∈ ℕ be integers. We consider noncommutative multilinear polynomials Q ∈ M_{n}(ℂ)[X_{1}, …, X_{m}], where X_{1}, …, X_{m} are noncommutative indeterminates. Monomials are always ordered by increasing order of the index, e.g. X_{1}X_{2} and not X_{2}X_{1}. Any such polynomial can be expanded as

Q(X_{1}, …, X_{m}) = ∑_{S⊆{1,...,m}: |S|≤d} Q̂(S) ∏_{i∈S} X_{i},  (4)

where Q̂(S) ∈ M_{n}(ℂ) for all S ⊆ {1, …, m} and 0 ≤ d ≤ m is the degree of Q, defined as max{|S| : f̂(S) ≠ 0, S ⊆ {1, …, m}}.

Let f: {−1, 1}^{m} → M_{n}(ℂ). Define the (non-commutative) multilinear polynomial Q_{f} ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] associated to f by

Q_{f}(X_{1}, …, X_{m}) := ∑_{S⊆{1,...,m}} f̂(S) ∏_{i∈S} X_{i}.  (5)

2.6. Partial Derivatives. Let f: {−1, 1}^{m} → M_{n}(ℂ). Let i ∈ {1, …, m}. Define the i^{th} partial derivative of f by

∂_{i}f(σ) := ∑_{S⊆\{1,...,m\}: i∈S} f̂(S)W_{S}(σ) = \frac{1}{2}(f(σ) − f(σ_{1}, …, −σ_{i}, …, σ_{m})),  (6)

and the i^{th} influence of f by

Inf_{i}f := ∑_{S⊆{1,...,m}: i∈S} Tr(f̂(S)f̂(S)^{∗}).  (7)

Note that by (3), Inf_{i}f = ⟨∂_{i}f, ∂_{i}f⟩ and ∑_{i=1}^{m} Inf_{i}f = ∑_{S⊆{1,...,m}} |S| Tr(f̂(S)(f̂(S))^{∗}).

2.7. Ornstein-Uhlenbeck semigroup. For f, h : {−1, 1}^{m} → M_{n}(ℂ) define their convolution f ∗ h by

f ∗ h(σ) := 2^{−m} ∑_{ω∈{−1,1}^{m}} f(σ · ω^{−1})h(ω) = ∑_{S⊆{1,...,m}} f̂(S)ĥ(S)W_{S}(σ), ∀ σ ∈ {−1, 1}^{m}. (8)

Here σ·ω denotes the componentwise product of σ and ω and ω^{−1} denotes the multiplicative inverse of ω, so that ω · ω^{−1} = (1, …, 1).

Let 0 < ρ < 1. For any σ = (σ_{1}, …, σ_{m}) ∈ {−1, 1}^{m}, let

R_{ρ}(σ) := ∏_{j=1}^{m}(1 + ρσ_{j}) = ∑_{S⊆{1,...,m}} ρ^{|S|}W_{S}(σ).  (9)

Let f: {−1, 1}^{m} → M_{n}(ℂ). Define the Ornstein-Uhlenbeck semigroup T_{ρ}f by

T_{ρ}f(σ) := ∑_{S⊆{1,...,m}} ρ^{|S|}f̂(S)W_{S}(σ) = f ∗ R_{ρ}(σ), ∀ σ ∈ {−1, 1}^{m}.  (10)

2.8. Truncation of Fourier Coefficients (or Littlewood-Paley Projections). Let f: {−1, 1}^{m} → M_{n}(ℂ), and Q_{f} ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] the multilinear polynomial associated to f. Let d ∈ ℕ. Let P_{d} denote projection onto the level-d Fourier coefficients. That is, ∀ σ ∈ {−1, 1}^{m}, ∀ X_{1}, …, X_{m} ∈ M_{n}(ℂ),

P_{d}f(σ) := ∑_{S⊆{1,...,m}: |S|=d} f̂(S)W_{S}(σ),  P_{d}Q_{f}(X_{1}, …, X_{m}) := ∑_{S⊆{1,...,m}: |S|=d} f̂(S) ∏_{i∈S} X_{i}.

Let P_{≤d} := ∑_{i≤d} P_{i} denote projection onto the Fourier coefficients of degree at most d. Denote P_{>d}f := f − P_{≤d}f, P_{>d}Q_{f} := Q_{f} − P_{≤d}Q_{f}.

2.9. Embeddings.

Definition 2.1 (Matrix embedding). Let A ∈ M_{n}(ℂ) and p ≥ n. Define the embedding ι_{p}: M_{n}(ℂ) → M_{p}(ℂ) by

ι_{p}(A) := (\begin{matrix}A & 0 \\ 0 & 0 \end{matrix}) ∈ M_{p}(ℂ).

If B = ∑_{k=1}^{N} C_{k} ⊗ D_{k} ∈ M_{n×n}(ℂ), extend this definition to

ι_{p}(B) := ∑_{k=1}^{N} ι_{p}(C_{k}) ⊗ ι_{p}(D_{k}) ∈ M_{p×p}(ℂ).

Lastly, if f: {−1, 1}^{m} → M_{n}(ℂ) define ι_{p}(f) : {−1, 1}^{m} → M_{p}(ℂ) by

ι_{p}(f)(σ) = ι_{p}(f(σ)) ∀ σ ∈ {−1, 1}^{m}.

We will sometimes denote the same quantities by A^{ι}, B^{ι} and f^{ι} respectively, leaving the dependence of ι on p and n implicit for clarity of notation.

Note that if Q = ∑_{S⊆{1,...,m}} Q̂(S) ∏_{i∈S} X_{i} ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] is a noncommutative polynomial the last item in Definition 2.1 is equivalent to defining

Q^{ι} = ∑_{S⊆{1,...,m}} ι_{p}(Q̂(S)) ∏_{i∈S} X_{i} ∈ M_{p}(ℂ)[X_{1}, …, X_{m}].

If moreover Q_{f} is defined from f: {−1, 1}^{m} → M_{n}(ℂ) as in (5) then

Q_{f}^{ι} = ∑_{S⊆{1,...,m}} ι_{p}(f̂(S)) ∏_{i∈S} X_{i} ∈ M_{p}(ℂ)[X_{1}, …, X_{m}].

2.10. Coordinate projections.

Definition 2.2. Let U ∈ M_{n}(ℂ^{N}) with UU^{∗} = U^{∗}U = I and Q ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] a noncommutative polynomial. We denote the Gaussian L_{2} norm of Q associated to the ensemble G by

∥Q∥_{L_{2},G} := ( 𝔼_{\begin{matrix}G_{k}∼G \\ H_{k}∼H_{p} \end{matrix}} Tr|Q^{ι}\{G_{k}H_{k}\}|^{2})^{1/2}.

Let N (0, 1) denote the standard complex Gaussian distribution for a random variable. For integers m, N let 𝔼_{g_{ij}∼N (0,1)} denote expectation with respect to g_{1,1}, …, g_{m,N} i.i.d. N (0, 1).

2.11. Bounds on random polynomials. The key difference between the random matrices G_{i} ∼ G and (G_{i} ⊗ I)H_{i} where H_{i} ∼ H_{p} is that the matrices (G_{i} ⊗ I)H_{i} behave well with respect to matrix products. This property is exploited in Corollary 2.4 below.

Lemma 2.3. Let p be a positive multiple of n, let A, B ∈ M_{p}(ℂ). Let I = I_{n} be the n × n identity matrix. Then

𝔼_{H∼H_{p}} ∥I^{ι}AHBI^{ι}∥^{2} ≤ \frac{n^{2}}{p} ∥A∥^{2}∥B∥^{2}.

Proof. The nonzero eigenspace K of HBI^{ι}B^{∗}H^{∗} is a uniformly distributed subspace of dimension at most n of ℂ^{p}. Given a unit vector x, the squared norm of the projection of x on K has expectation at most n/p. Applying this to the eigenvectors of A^{∗}I^{ι}A,

𝔼_{H∼H_{p}}Tr(I^{ι}AHBI^{ι}B^{∗}H^{∗}A^{∗}) ≤ \frac{n}{p}∥B∥^{2}Tr(A^{∗}I^{ι}A) ≤ \frac{n^{2}}{p} ∥B∥^{2} ∥A∥^{2} .

□

Corollary 2.4. Let R, S ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] be multilinear polynomials not depending on the j-th variable such that 𝔼_{b_{j}∼B} \frac{1}{n}Tr|R\{b_{j}\}|^{2} ≤ 1 and 𝔼_{b_{j}∼B} \frac{1}{n}Tr|S\{b_{j}\}|^{2} ≤ 1. Then

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥ (S^{ι}\{G_{i}H_{i}\}) G_{k}H_{k} (R^{ι}\{G_{i}H_{i}\})^{∗} ∥ = O_{n,m}(p^{−1/2}),

where the implicit constant may depend on n and m.

Proof. Write S^{ι} = S_{0} + ∑_{k≠j} S_{k}X_{k} and R^{ι} = R_{0} + ∑_{k≠j} R_{k}X_{k}, where ∀ k ∈ {1, …, m}\{j}, S_{k}, R_{k} ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] depend neither on the k-th or the j-th variable, and S_{0}, R_{0} ∈ M_{n}(ℂ). Then for any k ≠ j, since S = I^{ι}S and R^{∗} = R^{∗}I^{ι},

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥S^{ι}G_{k}H_{k}H_{k}^{∗}G_{k}^{∗}(R_{k}^{ι})^{∗}∥ = 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥I^{ι}S^{ι}G_{k}H_{k}H_{k}^{∗}G_{k}^{∗}(R_{k}^{ι})^{∗}I^{ι}∥

≤ \frac{n}{\sqrt{p}} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥S^{ι}G_{j}∥∥G_{k}^{∗}(R_{k}^{ι})^{∗}∥

≤ \frac{n}{\sqrt{p}}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥S^{ι}G_{j}∥^{2})^{1/2}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥G_{k}^{∗}(R_{k}^{ι})^{∗}∥^{2})^{1/2}

≤ \frac{n^{2}}{\sqrt{p}}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥S^{ι}∥^{2})^{1/2}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} ∥R_{k}^{ι}∥^{2})^{1/2}

where the last inequality used 𝔼_{G∼ι(G)}∥G∥^{2}= 𝔼_{G∼G}∥G∥^{2} ≤ 𝔼_{G∼G}Tr(GG^{∗}) = n and the first inequality used Lemma 2.3. To conclude, we use the normalization assumption on R, S, and (11) and (14) from Lemma 2.5 below. □

Lemma 2.5. Let f: {−1, 1}^{m} → M_{n}(ℂ) and Q ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] the multilinear polynomial associated to f. Let 0 ≤ k ≤ m. Let G_{i} ∼ G and b_{i} ∼ B. Let X = (G_{1}, …, G_{k}) and Y = (b_{k+1}, …, b_{m}). Then

𝔼_{x_{i}∼X ,y_{j}∼Y} |Q{x_{i}, y_{j}}|^{2} = 𝔼_{b_{i}∼B} |Q{b_{i}}|^{2} .  (11)
Inf_{i}(Q^{ι}) = Inf_{i}(Q), ∀ i ∈ {1, …, m}.  (12)
\frac{1}{n}𝔼_{b_{i}∼B}Tr |Q^{ι}\{b_{i}\}|^{2} = \frac{1}{n}𝔼_{b_{i}∼B}Tr |Q\{b_{i}\}|^{2} .  (13)
\frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}\{G_{i}H_{i}\}|^{2} = \frac{1}{n}𝔼_{G_{i}∼G}Tr |Q\{G_{i}\}|^{2} .  (14)

Proof. Recall the variables G_{i} ∼ G are independent, 𝔼G_{i} = 0 and 𝔼G_{i}G_{i}^{∗} = I for all 1 ≤ i ≤ k. Similarly, the b_{i} ∼ B are independent with 𝔼b_{i} = 0 and 𝔼b_{i}b_{i}^{∗} = 1 for all k + 1 ≤ i ≤ m. So,

𝔼_{x∼X ,y∼Y}(Q(x, y)(Q(x, y))^{∗})

= 𝔼 ∑_{S⊆{1,...,m}} (Q̂(S)( ∏_{i∈S: i≤k} G_{i} ∏_{i∈S: i>k} b_{i})( ∏_{i∈S: i≤k} G_{i} ∏_{i∈S: i>k} b_{i})^{∗}(Q̂(S))^{∗})

= ∑_{S⊆{1,...,m}} Q̂(S)(Q̂(S))^{∗}

=^{(3)} 𝔼_{b_{i}∼B} |Q{b_{i}}|^{2} .

Then (11) follows. Equation (12) follows from (7), Definition 2.1, and Lemma 2.5. Equalities (13) and (14) follow from Definition 2.1. □

2.12. Unique Games Conjecture. The Unique Games Conjecture is a commonly assumed conjecture in complexity theory, though its current status is unresolved.

Definition 2.6 (Unique Games). Let m ∈ ℕ. Let G = G(S, W, E) be a bipartite graph with vertex sets S and W and edge set E ⊆ S × W. For all (v, w) ∈ E, let π_{vw}: {1, …, m} → {1, …, m} be a permutation. An instance of the Unique Games problem is L = (G(S, W, E), m, {π_{vw}}_{(v,w)∈E}). m is called the alphabet size of L. A labeling of L is a function η: S ∪ W → {1, …, m}. An edge (v, w) ∈ E is satisfied if and only if η(v) = π_{vw}(η(w)). The goal of the Unique Games problem is to maximize the fraction of satisfied edges of the labeling, over all such labelings η. We call the maximum possible fraction of satisfied edges OPT(L).

Definition 2.7 (Unique Games Conjecture, [Kho02, KKMO07]). For every 0 < β < α < 1 there exists m = m(α, β) ∈ ℕ and a family of Unique Games instances (L_{n})_{n≥1} with alphabet size m such that no polynomial time algorithm can distinguish between OPT(L_{n}) < β or OPT(L_{n}) > α.

3. Majorization Principle

3.1. A noncommutative hypercontractive inequality. One of the main tools used in the proof of our majorization principle is a hypercontractive inequality for noncommutative multilinear polynomials. The inequality bounds the 2K-norm, for K ≥ 1 an integer, of a polynomial Q by the 2-norm of Q . We refer to this inequality as a (2K, 2) hypercontractive inequality; it can be considered as a polynomial generalization of the noncommutative Khintchine inequality between the 2K norm and the 2 norm. (The Khintchine inequality corresponds to the polynomial Q(X_{1}, …, X_{m}) = X_{1} and G_{1} ∼ V; see [MJC^{+}14, Corollary 7.3] or [DR13].)

Recall the definition of the ensembles G and V in Section 2.3.

Theorem 3.1 ((2K, 2) Hypercontractivity). Let K ∈ ℕ. Let Q be a noncommutative multilinear polynomial of degree d ∈ ℕ, as in (4). Let G_{j} ∼ G, where G is such that ∥𝔼(G_{1}G_{1}^{∗})^{K} ∥ ≤ c_{K} for some c_{K} ≥ 1. Then

𝔼_{G_{j}∼V} Tr |Q{G_{j}}|^{2K} ≤ (2K − 1)^{dK}c_{K}^{d}( 𝔼_{G_{j}∼V} Tr |Q{G_{j}}|^{2})^{K}.

Or, more generally,

𝔼_{G_{j}∼G} Tr |Q{G_{j}}|^{2K} ≤ (2K − 1)^{2dK}c_{K}^{d}( 𝔼_{G_{j}∼G} Tr |Q{G_{j}}|^{2})^{K}.

Remark 3.2. As mentioned in [MOO10, Theorem 3.13] or [Nel73, Theorem 4], the best possible constant in this hypercontractive inequality is (2K − 1)^{dK} in the case that G_{j} ∼ V are replaced with b_{i} ∼ B. So, we achieve the optimal constant in this case, since we can use c_{K} = 1 for all K ∈ ℕ in this case.

The result that hypercontractivity also holds for the variables G_{1} = b_{1} ∼ B generalizes a result of [Gro72, Lemma 6.1].

Proof. We begin with the first inequality. It suffices to prove the following hypercontractive estimate: if ρ ≥ 0 satisfies ρ ≤ (2K − 1)^{−1/2}c_{K}^{−1/(2K)}, then

𝔼_{G_{j}∼V} Tr |T_{ρ}Q{G_{j}}|^{2K} ≤ ( 𝔼_{G_{j}∼V} Tr |Q{G_{j}}|^{2})^{K}.  (15)

To see that (15) implies the first inequality of the theorem, choose ρ = (2K − 1)^{−1/2}c_{K}^{−1/(2K)}, and observe that

𝔼_{G_{j}∼V} Tr |Q{G_{j}}|^{2K} =^{(10)} 𝔼_{G_{j}∼V} Tr|T_{ρ}( ∑_{S⊆{1,...,m}: |S|≤d} ρ^{−|S|}Q̂(S) ∏_{i∈S} G_{i})|^{2K}

≤^{(15)} ( 𝔼_{G_{j}∼V} Tr| ∑_{S⊆{1,...,m}: |S|≤d} ρ^{−|S|}Q̂(S) ∏_{i∈S} G_{i}|^{2})^{K} =^{(11)∧(3)} ( ∑_{S⊆{1,...,m}: |S|≤d} ρ^{−2|S|}Tr|Q̂(S)|^{2})^{K} (16)

≤ ρ^{−2dK}( ∑_{S⊆{1,...,m}: |S|≤d} Tr|Q̂(S)|^{2})^{K} =^{(11)∧(3)} (2K − 1)^{dK}c_{K}^{d}( 𝔼_{G_{j}∼V} Tr|Q{G_{j}}|^{2})^{K}.  (17)

The proof of (15) is by induction on the number m of variables of Q. If m = 0 then there are no variables and the inequality follows from the elementary inequality ∑_{i=1}^{n}(λ_{i}(Q))^{2K} ≤ (∑_{i=1}^{n}(λ_{i}(Q))^{2})^{K} applied to the singular values of the (deterministic) matrix Q. To establish the inductive step, write Q = R_{0} + R_{1}X_{m}, where R_{0}, R_{1} depend on at most m − 1 variables each (for clarity we suppress this dependence from the notation). Note that T_{ρ}Q = T_{ρ}R_{0} + ρ(T_{ρ}R_{1})X_{m} We begin with a binomial expansion

|T_{ρ}Q(X_{1}, …, X_{m})|^{2K} = ∑_{(a_{1},...,a_{2K})∈{0,1}^{2K}} ∏_{i=1}^{K} ρ^{a_{2i−1}}T_{ρ}R_{a_{2i−1}}X_{m}^{a_{2i−1}}(X_{m}^{∗})^{a_{2i}}ρ^{a_{2i}}(T_{ρ}R_{a_{2i}})^{∗}. (18)

Any term in the sum for which a_{j} = 0 for an odd number of elements j ∈ {1, …, 2K} has expectation zero. Applying Hölder’s inequality,

𝔼_{G_{j}∼V} Tr |T_{ρ}Q|^{2K} ≤ 𝔼Tr |T_{ρ}R_{0}|^{2K} + ∑_{(a_{1},...,a_{2K})∈\{0,1\}^{2K}: \frac{1}{2} ∑_{i=1}^{2K} a_{i} is a positive integer} ∏_{i=1}^{2K} ρ^{a_{i}}[𝔼Tr |(T_{ρ}R_{a_{i}})G_{m}^{a_{i}}|^{2K} ]^{\frac{1}{2K}} .

(19)

Let (a_{1}, …, a_{2K}) ∈ \{0, 1\}^{2K} such that ℓ := \frac{1}{2} ∑_{i=1}^{2K} a_{i} is a positive integer. The number of

times the term ∏_{i=1}^{2K} ρ^{a_{i}}[𝔼Tr |(T_{ρ}R_{a_{i}})G_{m}^{a_{i}}|^{2K} ]^{\frac{1}{2K}} is repeated in the sum in (19) is \binom{2K}{2ℓ} =

\frac{(2K)!}{(2K−2ℓ)!(2ℓ)!}. That is, (19) can be rewritten as

𝔼_{G_{j}∼V} Tr |T_{ρ}Q|^{2K} ≤ 𝔼Tr |T_{ρ}R_{0}|^{2K} + ∑_{ℓ=1}^{K} ρ^{2ℓ}\binom{2K}{2ℓ}[𝔼Tr |(T_{ρ}R_{1})G_{m}|^{2K} ]^{\frac{ℓ}{K}} [𝔼Tr |T_{ρ}R_{0}|^{2K} ]^{\frac{K−ℓ}{K}} .

(20)

For any A, B ∈ M_{n}(ℂ) it holds that Tr| |B| A^{∗}A |B| |^{K} ≤ Tr| |B|^{K} (A^{∗}A)^{K} |B|^{K} | (see e.g. [Bha97, Theorem IX.2.10]), hence

Tr(ABB^{∗}A^{∗})^{K} = Tr(A^{∗}ABB^{∗})^{K} ≤ Tr((BB^{∗})^{K}(A^{∗}A)^{K}).  (21)

Starting from (20) and applying (21) to each of the inner terms,

𝔼_{G_{j}∼V} Tr |T_{ρ}Q|^{2K} ≤ 𝔼Tr |T_{ρ}R_{0}|^{2K} + ∑_{ℓ=1}^{K} ρ^{2ℓ}\binom{2K}{2ℓ}c_{K}^{ℓ/K}[𝔼Tr |T_{ρ}R_{1}|^{2K} ]^{\frac{ℓ}{K}} [𝔼Tr |T_{ρ}R_{0}|^{2K} ]^{\frac{K−ℓ}{K}}

≤ [𝔼Tr |R_{0}|^{2}]^{K} + ∑_{ℓ=1}^{K} ρ^{2ℓ}\binom{2K}{2ℓ}c_{K}^{ℓ/K}[𝔼Tr |R_{1}|^{2} ]^{ℓ}[𝔼Tr |R_{0}|^{2} ]^{K−ℓ},  (22)

where the second inequality is obtained by applying the inductive hypothesis. For any odd integer J we denote J!! = ∏_{i=0}^{(J−1)/2}(J − 2i), or J!! = 1 if (J − 1)/2 < 1. Now if 1 ≤ ℓ ≤ K,

\binom{2K}{2ℓ}\binom{K}{ℓ}^{−1} = \frac{(2K)!}{K!} \frac{ℓ!}{(2ℓ)!} \frac{(K − ℓ)!}{(2(K − ℓ))!} = \frac{2^{K}(2K − 1)!!}{2^{ℓ}(2ℓ − 1)!!2^{K−ℓ}(2(K − ℓ) − 1)!!}

= \frac{(2K − 1)!!}{(2ℓ − 1)!!(2(K − ℓ) − 1)!!} = ∏_{i=0}^{ℓ−1} \frac{2K − 2i − 1}{2ℓ − 2i − 1} ≤ (2K − 1)^{ℓ}.

Using this inequality and 0 ≤ ρ ≤ (2K − 1)^{−1/2}c_{K}^{−1/(2K)} we get

ρ^{2ℓ}\binom{2K}{2ℓ}c_{K}^{ℓ/K} ≤ ρ^{2ℓ}(2K − 1)^{ℓ}c_{K}^{ℓ/K} \binom{K}{ℓ} ≤ \binom{K}{ℓ}, ∀ 1 ≤ ℓ ≤ K.

Applying this inequality to (22),

𝔼_{G_{j}∼V} Tr |T_{ρ}Q|^{2K} ≤ ∑_{ℓ=0}^{K} \binom{K}{ℓ}[ 𝔼_{G_{j}∼V} Tr |R_{1}|^{2} ]^{ℓ}[ 𝔼_{G_{j}∼V} Tr |R_{0}|^{2} ]^{K−ℓ}

= ( ∑_{i=0}^{1} 𝔼_{G_{j}∼V} Tr(R_{i}R_{i}^{∗}))^{K} = [ 𝔼_{G_{j}∼V} Tr(QQ^{∗})]^{K},

where the last equality follows from 𝔼G_{1}G_{1}^{∗} = I.

We now prove the second inequality of the Theorem. We repeat the above proof, though now the sum in (19) ranges over all (a_{1}, …, a_{2K}) ∈ {0, 1}^{2K} such that ∑_{i=1}^{2K} a_{i} ≥ 2. If ℓ > 0 satisfies 2ℓ + 1 = ∑_{i=1}^{2K} a_{i}, then the corresponding term appears \binom{2K}{2ℓ+1} times in (19), and we bound this term in (19) with the arithmetic-mean geometric-mean inequality as follows.

∏_{i=1}^{2K} [𝔼Tr |(T_{ρ}R_{a_{i}})G_{m}^{a_{i}}|^{2K} ]^{\frac{1}{2K}} = [𝔼Tr |(T_{ρ}R_{1})G_{m}|^{2K} ]^{\frac{2ℓ+1}{2K}} [𝔼Tr |T_{ρ}R_{0}|^{2K} ]^{\frac{2K−2ℓ−1}{2K}}

≤ \frac{1}{2}[𝔼Tr |(T_{ρ}R_{1})G_{m}|^{2K} ]^{\frac{ℓ}{K}} [𝔼Tr |T_{ρ}R_{0}|^{2K} ]^{\frac{K−ℓ}{K}}

+ \frac{1}{2}[𝔼Tr |(T_{ρ}R_{1})G_{m}|^{2K} ]^{\frac{ℓ+1}{K}} [𝔼Tr |T_{ρ}R_{0}|^{2K} ]^{\frac{K−ℓ−1}{K}} .

Then, as above, we have \frac{1}{2} \binom{2K}{2ℓ+1}\binom{K}{ℓ}^{−1} ≤ \frac{K−1}{3}(2K − 1)^{ℓ} and \frac{1}{2} \binom{2K}{2ℓ+1}\binom{K}{ℓ+1}^{−1} ≤ \frac{2}{3}(2K − 1)^{ℓ}. So, if 0 ≤ ρ ≤ (2K − 1)c_{K}^{−1/(2K)}, then ρ^{2ℓ} (\binom{2K}{2ℓ} + \frac{1}{2} \binom{2K}{2ℓ+1} + \frac{1}{2} \binom{2K}{2ℓ−1}) c_{K}^{ℓ/K} ≤ \binom{K}{ℓ}, for all 1 ≤ ℓ ≤ K, and then the proof concludes as above.

□

Corollary 3.3 ((2K, 2) Hypercontractivity). Let K ∈ ℕ. Let Q be a noncommutative multilinear polynomial of degree d ∈ ℕ, as in (4). Then

𝔼_{G_{j}∼V} Tr |Q{G_{j}}|^{2K} ≤ (2K − 1)^{dK}c_{K}^{d}(K!)^{d}( 𝔼_{G_{j}∼V} Tr |Q{G_{j}}|^{2})^{K}.

𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}\{G_{j}H_{j}\}|^{2K} ≤ (2K − 1)^{dK}c_{K}^{d}(K!)^{d}( 𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}\{G_{j}H_{j}\}|^{2})^{K}.

𝔼_{b_{j}∼B} Tr |Q{b_{j}}|^{2K} ≤ (2K − 1)^{dK}c_{K}^{d}( 𝔼_{b_{j}∼B} Tr |Q{b_{j}}|^{2})^{K}.

Proof. The first inequality follows from Theorem 3.1 using [HT99, Corollary 2.8] to show that for G ∼ V and any ℓ ∈ ℕ, ∥𝔼(GG^{∗})^{ℓ}∥ ≤ ℓ! .

To prove the second inequality, we follow the proof of Theorem 3.1 using ∥𝔼(GG^{∗})^{ℓ}∥ ≤ ℓ! for any G ∼ V ⊗ I, where the Q used in the proof becomes Q^{ι}. Writing Q^{ι} = R_{0}^{ι} + R_{1}^{ι}X_{m}, there are only two required changes. First, the equalities (16) and (17) are justified by combining (14) with (11) and (3). For example, (16) is justified by

( 𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr| ∑_{S⊆\{1,...,m\}: |S|≤d} ρ^{−|S|}Q̂^{ι}(S) ∏_{i∈S} G_{i}^{ι}H_{i}|^{2})^{K}

=^{(14)} ( 𝔼_{G_{j}∼V} Tr| ∑_{S⊆{1,...,m}: |S|≤d} ρ^{−|S|}Q̂(S) ∏_{i∈S} G_{i}|^{2})^{K}

=^{(11)∧(3)} ( ∑_{S⊆{1,...,m}: |S|≤d} ρ^{−2|S|}Tr|Q̂(S)|^{2})^{K}.

And (17) is justified in the same way. Similarly, the last inequality in the proof is justified as

𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |T_{ρ}Q^{ι}|^{2K} ≤ ∑_{ℓ=0}^{K} \binom{K}{ℓ}[ 𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |R_{1}^{ι}|^{2} ]^{ℓ}[ 𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |R_{0}^{ι}|^{2} ]^{K−ℓ}

=^{(14)} ∑_{ℓ=0}^{K} \binom{K}{ℓ}[ 𝔼_{G_{j}∼V} Tr |R_{1}|^{2} ]^{ℓ}[ 𝔼_{G_{j}∼V} Tr |R_{0}|^{2} ]^{K−ℓ}

= ( 𝔼_{G_{j}∼V} Tr |Q|^{2})^{K}

=^{(14)} ( 𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}|^{2} )^{K}.

The last inequality in the Corollary follows directly from Theorem 3.1. □

In summary, Q is hypercontractive when we substitute into Q the noncommutative random variables G_{i}H_{i}. Since Q is also hypercontractive when we substitute into Q commutative random variables distributed uniformly in {−1, 1}, we get the standard consequence that Q is hypercontractive when we substitute into it a mixture of commutative and noncommutative random variables.

Corollary 3.4 ((2K, 2) Hypercontractivity for mixed inputs). Let G_{j} ∼ G be i.i.d. random n × n matrices and let Q be a noncommutative multilinear polynomial of degree d ∈ ℕ such that Q satisfies (2K, 2) hypercontractivity for some K ∈ ℕ. That is, assume there exists c_{K} ≥ 1 such that

𝔼_{G_{j}∼G} Tr |Q{G_{j}}|^{2K} ≤ (2K − 1)^{2dK}c_{K}^{d}( 𝔼_{G_{j}∼G} Tr |Q{G_{j}}|^{2})^{K}.

Let X = (G_{1}, …, G_{k}). Let b_{j} ∼ B and let Y = (b_{k+1}, …, b_{m}). Then

𝔼_{x∼X ,y∼Y}Tr |Q(x, y)|^{2K} ≤ (2K − 1)^{2dK}c_{K}^{d}(𝔼_{x∼X ,y∼Y}Tr |Q(x, y)|^{2} )^{K}.

Proof. For any p ≥ 1, let ∥·∥_{p,Z} denote the norm ∥Q∥_{p,Z} = (𝔼_{z∼Z}Tr |Q(z)|^{p})^{1/p}.

∥Q∥_{2K,X ∪Y} = ∥ ∑_{S⊆{1,...,m}} Q̂(S) ∏_{j∈S: j≤k} G_{j} ∏_{j∈S: j>k} b_{j}∥_{2K,X ∪Y}

= ∥ ∥ ∑_{S⊆{1,...,m}} Q̂(S) ∏_{j∈S: j≤k} G_{j} ∏_{j∈S: j>k} b_{j}∥_{2K,X} ∥_{2K,Y}

≤ (2K − 1)^{k}c_{K}^{k/(2K)}∥ ∥ ∑_{S⊆{1,...,m}} (Q̂(S) ∏_{j∈S: j>k} b_{j}) ∏_{j∈S: j≤k} G_{j}∥_{2,X} ∥_{2K,Y},

by Theorem 3.1. Next, using Minkowski’s inequality, from the above we get

∥Q∥_{2K,X ∪Y} ≤ (2K − 1)^{k}c_{K}^{k/(2K)}∥ ∥ ∑_{S⊆{1,...,m}} (Q̂(S) ∏_{j∈S: j>k} b_{j}) ∏_{j∈S: j≤k} G_{j}∥_{2K,Y} ∥_{2,X}

= (2K − 1)^{k}c_{K}^{k/(2K)}∥ ∥ ∑_{S⊆{1,...,m}} (Q̂(S) ∏_{j∈S: j≤k} G_{j}) ∏_{j∈S: j>k} b_{j}∥_{2K,Y} ∥_{2,X}

≤ (2K − 1)^{d}c_{K}^{d/(2K)}∥ ∥ ∑_{S⊆{1,...,m}} (Q̂(S) ∏_{j∈S: j≤k} G_{j}) ∏_{j∈S: j>k} b_{j}∥_{2,Y} ∥_{2,X}

= (2K − 1)^{d}c_{K}^{d/(2K)}∥ ∑_{S⊆{1,...,m}} Q̂(S) ∏_{j∈S: j≤k} G_{j} ∏_{j∈S: j>k} b_{j}∥_{2,X ∪Y}

= (2K − 1)^{d}c_{K}^{d/(2K)}∥Q∥_{2,X ∪Y},

where the third line is by Theorem 3.1. □

3.2. Majorization principle.

Theorem 3.5 (Noncommutative Majorization Principle for Increasing Test Functions). Let Q ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] be a noncommutative multilinear polynomial of degree d such that 𝔼_{b_{j}∼B} \frac{1}{n}Tr(Q\{b_{j}\}Q\{b_{j}\}^{∗})) ≤ 1. Let τ := max_{1≤j≤m} Inf_{j}Q. Let G_{i} ∼ V ⊗I. Assume ∥𝔼(G_{1}G_{1}^{∗})^{2}∥ ≤ c_{2} and ∥𝔼(G_{1}G_{1}^{∗})^{3}∥ ≤ c_{3} with c_{2}, c_{3} ≥ 1.

Let ψ: [0, ∞) → ℝ be a function with three continuous derivatives such that ψ′(t) ≥ 0 for all t ≥ 0. Let a_{2} = sup_{t≥0} |ψ′′(t)| and a_{3} = sup_{t≥0} |ψ′′′(t)|. Then

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ|Q^{ι}\{G_{i}H_{i}\}|^{2} ≤ 𝔼_{b_{j}∼B} \frac{1}{n}Trψ|Q\{b_{j}\}|^{2} + a_{3}n^{3/2}(5^{6}c_{2}c_{3})^{d}τ^{1/2} + O_{n,m}(a_{2}p^{−1/2}).

Proof. We show the bound using the Lindeberg replacement method, replacing the m variables G_{k}H_{k} by b_{j} one at a time, starting from the last, for each j ∈ {1, …, m}. Suppose variables j + 1, j + 2, …, m have already been replaced, and write Q^{ι} = R + SX_{j} where R, S do not depend on the j^{th} variable.

Any three times continuously differentiable F: [0, ∞) → ℝ has a Taylor expansion

F (1) = F (0) + F′(0) + \frac{1}{2}F′′(0) + \frac{1}{2} ∫_{0}^{1}(1 − s)^{2}F′′′(s)ds.  (23)

Let F (t) = Trψ((R + tSX)(R + tSX)^{∗}) for t ∈ [0, 1]. Then

F (0) = Trψ(RR^{∗}),  (24)
F′(0) = Tr(ψ′(RR^{∗})(SXR^{∗} + RX^{∗}S^{∗})),  (25)
F′′(0) = Tr(ψ′(RR^{∗})2SXX^{∗}S^{∗} + ψ′′(RR^{∗})(SXR^{∗} + RX^{∗}S^{∗})^{2}),  (26)
F′′′(t) = Tr(ψ′′((R + tSX)(R + tSX)^{∗})((SXR^{∗} + RX^{∗}S^{∗}) + 2tSXX^{∗}S^{∗})(SXX^{∗}S^{∗}))

+ Tr(ψ′′((R + tSX)(R + tSX)^{∗})2((SXR^{∗} + RX^{∗}S^{∗}) + 2tSXX^{∗}S^{∗})(SXX^{∗}S^{∗}))

+ Tr(ψ′′′((R + tSX)(R + tSX)^{∗})2((SXR^{∗} + RX^{∗}S^{∗}) + 2tSXX^{∗}S^{∗})^{3}).  (27)

For any t ∈ [0, 1], let F_{1}(t) = Trψ((R+tSb_{j})(R+tSb_{j})^{∗}) and F_{2}(t) = Trψ((R+tSG_{j}H_{j})(R+ tSG_{j}H_{j})^{∗}). From (23),

𝔼F_{2}(1)−𝔼F_{1}(1) = 𝔼F′′_{2}(0)−𝔼F′′_{1}(0)+𝔼\frac{1}{2} ∫_{0}^{1}(1−s)^{2}F′′′_{2}(s)ds−𝔼\frac{1}{2} ∫_{0}^{1}(1−s)^{2}F′′′_{1}(s)ds, (28)

where we used that 𝔼F_{2}(0) = 𝔼F_{1}(0) and 𝔼F′_{2}(0) = 𝔼F′_{1}(0). We bound the two differences on the right-hand side of (28) separately.

For the first, using that ψ′(RR^{∗}) is positive semidefinite the first term can be bounded as

𝔼Tr(ψ′(RR^{∗})2SG_{j}H_{j}H_{j}^{∗}G_{j}S^{∗}) = 𝔼Tr(ψ′(RR^{∗})2S (\begin{matrix}I & 0 \\ 0 & 0 \end{matrix}) S^{∗})
≤ 𝔼Tr(ψ′(RR^{∗})2SS^{∗})
= 𝔼Tr(ψ′(RR^{∗})2Sb_{j}b_{j}^{∗}S^{∗}).  (29)

The second term in (26) is readily bounded using Corollary 2.4, from which it follows that 𝔼∥SG_{k}H_{k}R^{∗} + RH_{j}^{∗}G_{j}^{∗}S^{∗}∥ = O_{n,m}(p^{−1/2}), and |ψ′′(t)| ≤ a_{2} for all t ≥ 0. Combining the two bounds,

𝔼F′′_{2}(0) − 𝔼F′′_{1}(0) ≤ O_{n,m}(a_{2}p^{−1/2}).

For the second difference on the right-hand side of (28), there are two terms, corresponding to the first two lines of (27) and the third line respectively. For the first two terms we apply the Cauchy-Schwarz inequality, isolating the last factor SXX^{∗}S^{∗} and using |ψ′′(t)| ≤ a_{2} for all t ≥ 0 to bound them by

3a_{2}(𝔼Tr((SXX^{∗}S^{∗})^{2}))^{1/2}(𝔼Tr((SXR^{∗} + RX^{∗}S^{∗} + 2tSXX^{∗}S^{∗})^{2}))^{1/2}

≤ 3a_{2}(3^{4}c_{2})^{d}(𝔼Tr(SS^{∗}))(6𝔼Tr(SXR^{∗}RX^{∗}S^{∗}) + 12t^{2}𝔼Tr((SXX^{∗}S^{∗})^{2}))^{1/2}

≤ 3a_{2}(3^{4}c_{2})^{d}(𝔼Tr(SS^{∗}))(𝔼Tr((SXX^{∗}S^{∗})^{2})(36𝔼Tr((RR^{∗})^{2} + 12^{2}t^{2}𝔼Tr((SXX^{∗}S^{∗})^{2})))^{1/4}

≤ 36a_{2}(3^{4}c_{2})^{d}n^{1/2}(𝔼Tr(SS^{∗}))^{3/2},

where for the first inequality, the first term is bounded using Corollary 3.4 (first using Corollary 3.3 to show that hypercontractivity holds for Q^{ι} and then applying Corollary 3.4 with Q = Q^{ι}) and 𝔼XX^{∗} ≤ I, and the second term is bounded using (A + B + C)(A + B + C)^{∗} ≤ 4(AA^{∗} + BB^{∗} + CC^{∗}), the second inequality uses Cauchy-Schwarz, and the last again Corollary 3.4, 𝔼XX^{∗} ≤ I, and 𝔼RR^{∗} ≤ I.

Finally we turn to the second term which appears in the expansion of the second difference on the right-hand side of (28) according to (27), corresponding to the third line of (27). Letting P = SXR^{∗}+RX^{∗}S^{∗}+2tSXX^{∗}S^{∗}, the term can be bounded using Hölder’s inequality by

a_{3}𝔼Tr|P |^{3} = O(a_{3}) (𝔼Tr|RXS^{∗}|^{3} + 𝔼Tr|SXX^{∗}S^{∗}|^{3})
= O(a_{3})(𝔼Tr|SX|^{6})^{1/2}((𝔼Tr|R|^{6})^{1/2} + (𝔼Tr|SX|^{6})^{1/2})
= O(a_{3})n^{3/2}(5^{6}c_{3})^{d}(𝔼Tr|S|^{2})^{3/2},

where the last line uses Corollary 3.4 (applied as above) and 𝔼SS^{∗} ≤ I, 𝔼RR^{∗} ≤ I. Combining all error estimates and using 𝔼TrSS^{∗} = Inf_{j}(Q) we obtain

𝔼\frac{1}{n}F_{2}(1)

≤ 𝔼\frac{1}{n}F_{1}(1) + O_{n,m}(p^{−1/2}) + 𝔼\frac{1}{2n} ∫_{0}^{1}(1 − s)^{2}|F′′′_{2}(s)|ds + 𝔼\frac{1}{2n} ∫_{0}^{1}(1 − s)^{2}|F′′′_{1}(s)|ds

≤ 𝔼\frac{1}{n}F_{1}(1) + O_{n,m}(a_{2}p^{−1/2}) + a_{3}n^{1/2}(5^{6}c_{3})^{d}(Inf_{j}(Q))^{3/2}.  (30)

Iterating over all m variables,

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ |Q^{ι}\{G_{i}H_{i}\}|^{2} − 𝔼_{b_{i}∼B} \frac{1}{n}Trψ |Q\{b_{i}\}|^{2}

≤ a_{3}n^{1/2}(5^{6}c_{2}c_{3})^{d}( max_{1≤j≤m} Inf_{j}(Q))^{1/2}( ∑_{j=1}^{m} Inf_{j}(Q)) + O_{n,m}(p^{−1/2})

≤ a_{3}n^{3/2}(5^{6}c_{2}c_{3})^{d}( max_{1≤j≤m} Inf_{j}(Q))^{1/2} + O_{n,m}(a_{2}p^{−1/2}).

□

Let ψ: ℝ → ℝ be Lipschitz, so that sup_{x≠y∈ℝ} \frac{|ψ(x)−ψ(y)|}{|x−y|} ≤ 1. Let x ∈ ℝ and let ϕ(x) = e^{−x^{2}/2}/\sqrt{2π}, ϕ: ℝ → ℝ. For any λ > 0, define ϕ_{λ}(x) = λ^{−1}ϕ(x/λ). Define

ψ_{λ}(x) = ψ ∗ ϕ_{λ}(x) = ∫_{ℝ} ψ(t)ϕ_{λ}(x − t)dt.  (31)

Then |ψ(x) − ψ_{λ}(x)| < λ for all x ∈ ℝ, and |\frac{d^{k}}{dx^{k}} ϕ_{λ}(x)| ≤ λ^{1−k} for all x ∈ ℝ, so that

|\frac{d^{k}}{dx^{k}} ψ_{λ}(x)| ≤ 3λ^{1−k},  ∀ x ∈ ℝ,  ∀ 1 ≤ k ≤ 3.

Lemma 3.6. Let λ > 0. If ψ is convex, then ψ_{λ} is convex, and ψ(x) ≤ ψ_{λ}(x) for all x ∈ ℝ.

Proof. The first property is a standard differentiation argument for convolutions. Since ψ(x+h)+ψ(x−h)−2ψ(x) ≥ 0 for all x, h ∈ ℝ, we also have ψ_{λ}(x+h)+ψ_{λ}(x−h)−2ψ_{λ}(x) ≥ 0. The second property follows from Jensen’s inequality. □

Let ψ: ℝ → ℝ be defined by

ψ(t) = max (0, |t| − 1),  ∀t ∈ ℝ.  (32)

Theorem 3.7. Let Q ∈ M_{n}(ℂ)[X_{1}, …, X_{m}] be a noncommutative multilinear polynomial of degree d with 𝔼_{b_{j}∼B} \frac{1}{n}Tr(|Q\{b_{j}\}|^{2}) ≤ 1, and let τ = max_{i=1,...,m} Inf_{i}(Q). Let G_{i} ∼ G ⊗ I. Assume ∥𝔼(G_{1}G_{1}^{∗})^{2}∥ ≤ c_{2} and ∥𝔼(G_{1}G_{1}^{∗})^{3}∥ ≤ c_{3} with c_{2}, c_{3} ≥ 1. Let ψ be as in (32). Then

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ|Q^{ι}\{G_{i}H_{i}\}|^{2} ≤ 𝔼_{b_{j}∼B} \frac{1}{n}Trψ|Q\{b_{j}\}|^{2} + n^{1/2}(5^{6}c_{2}c_{3})^{d}τ^{1/6} + O_{m,n}(τ^{−1/3}p^{−1/2}).

Proof. Let λ > 0, and define ψ_{λ} as in (31). From Lemma 3.6, ψ_{λ}(x) ≥ ψ(x) ≥ 0 for all x ∈ ℝ. So,

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ |Q^{ι}\{G_{i}H_{i}\}|^{2} ≤ 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ_{λ} |Q^{ι}\{G_{i}H_{i}\}|^{2} .  (33)

From Theorem 3.5,

\begin{aligned}𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ_{λ} |Q^{ι}\{G_{i}H_{i}\}|^{2} & ≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ_{λ} |Q\{b_{i}\}|^{2} \\ & + λ^{−2} (O(n^{3/2})(5^{6}c_{2}c_{3})^{d}τ^{1/2} + O_{n,m}(p^{−1/2})) . \end{aligned} (34)

Using ψ_{λ}(x) ≤ ψ(x) + λ for all x ≥ 0,

\frac{1}{n}Trψ_{λ} |Q(σ)|^{2} ≤ \frac{1}{n}Trψ |Q(σ)|^{2} + λ,  ∀ σ ∈ \{−1, 1\}^{m}.  (35)

Combining (33), (34) and (35) completes the proof, with a choice of λ such that λ^{3} = Θ(n^{3/2}τ^{1/2}). □

Recall the definition of T_{ρ} in (10) and the function Chop : ℝ → ℝ, Chop(t) = t if |t| ≤ 1, Chop(t) = 1 if t ≥ 1, and Chop(t) = −1 if t ≤ −1.

Corollary 3.8 (Smoothed Version of Theorem 3.7). Suppose f: {−1, 1}^{m} → M_{n}(ℂ) with ∥f(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m}. Let 0 < ρ < 1 and let τ := max_{i=1,...,m} Inf_{i}f. Assume ∥𝔼(G_{1}G_{1}^{∗})^{2}∥ ≤ c_{2} and ∥𝔼(G_{1}G_{1}^{∗})^{3}∥ ≤ c_{3} for some c_{2}, c_{3} ≥ 1. Then ∥Q_{f}∥_{L_{2},G} ≤ 1 and

\frac{1}{n} ∥T_{ρ}Q_{f}^{ι} − ChopT_{ρ}Q_{f}^{ι} ∥_{L_{2},G}^{2} ≤ 10n^{1/2}τ^{\frac{1−ρ}{30(c_{2}c_{3})}} + O_{m,n}(τ^{−1/3}p^{−1/2}).  (36)

Proof. Using the elementary inequality [max(0, t − 1)]^{2} ≤ ψ(t^{2}) for all t ≥ 0, where ψ is defined in (32), applied to the singular values of T_{ρ}Q_{f}^{ι},

\frac{1}{n} ∥T_{ρ}Q_{f}^{ι} − ChopT_{ρ}Q_{f}^{ι} ∥_{L_{2},G}^{2} ≤ 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} .  (37)

We first apply Theorem 3.7 to P_{≤d}(T_{ρ}Q_{f}^{ι}), where d ∈ ℕ is to be determined later. Since 0 < ρ < 1, (10), (7) imply that

max_{i=1,...,m} Inf_{i}P_{≤d}T_{ρ}Q_{f} ≤ max_{i=1,...,m} Inf_{i}P_{≤d}Q_{f} ≤ max_{i=1,...,m} Inf_{i}Q_{f},

and we get by Theorem 3.7 and (12)

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ|P_{≤d}T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} ≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ|P_{≤d}T_{ρ}Q_{f}\{b_{i}\}|^{2}

+ n^{1/2}(5^{6}c_{2}c_{3})^{d}τ^{1/6} + O_{m,n}(τ^{−1/3}p^{−1/2}).  (38)

For any a, b ∈ ℝ, |ψ((a + b)^{2}) − ψ(a^{2})| ≤ 2 |a| |b|+2 |b|^{2} follows by |ψ((a + b)^{2}) − ψ(a^{2})| ≤ |b| max_{t∈[a,a+b]} |\frac{d}{dt}ψ(t^{2})| ≤ |b| 2(|a| + |b|). Combining with the Cauchy-Schwarz inequality,

Trψ |T_{ρ}Q_{f}^{ι} |^{2} − Trψ |P_{≤d}T_{ρ}Q_{f}^{ι} |^{2} = Trψ |T_{ρ}P_{≤d}Q_{f}^{ι} + T_{ρ}P_{>d}Q_{f}^{ι} |^{2} − Trψ |T_{ρ}P_{≤d}Q_{f}^{ι} |^{2}

≤ 2(Tr|T_{ρ}P_{≤d}Q_{f}^{ι}|^{2})^{1/2}(Tr|T_{ρ}P_{>d}Q_{f}^{ι}|^{2})^{1/2} + 2Tr|T_{ρ}P_{>d}Q_{f}^{ι}|^{2}.

Taking expectation values and using (14), (11) and (10), which imply that

𝔼_{\begin{matrix}G_{k}∼V⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr|T_{ρ}P_{>d}Q_{f}^{ι}|^{2} = 𝔼_{G_{j}∼G} Tr|T_{ρ}P_{>d}Q_{f}^{ι}|^{2}

= 𝔼_{b_{j}∼B} Tr|T_{ρ}P_{>d}Q_{f}^{ι}|^{2}

= ∑_{S⊆{1,...,m}: |S|>d} ρ^{2|S|}Tr(f̂(S)(f̂(S))^{∗})

≤ ρ^{2d} ∑_{S⊆{1,...,m}} Tr(f̂(S)(f̂(S))^{∗})

≤ nρ^{2d},

we get

\frac{1}{n} |𝔼_{b_{i}∼B} (Trψ |T_{ρ}Q_{f}^{ι}\{b_{i}\}|^{2} − Trψ |P_{≤d}T_{ρ}Q_{f}^{ι}\{b_{i}\}|^{2})| ≤ 4ρ^{d},  (39)
\frac{1}{n}| 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} (Trψ |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} − Trψ |P_{≤d}T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2}) | ≤ 4ρ^{d}.  (40)

Using t ≤ |t| for any t ∈ ℝ,

\frac{1}{n}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Trψ |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} − 𝔼_{b_{i}∼B}Trψ |T_{ρ}Q_{f}^{ι}\{b_{i}\}|^{2} )

≤ \frac{1}{n}| 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Trψ |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} − 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Trψ |T_{ρ}P_{≤d}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} |

+ \frac{1}{n}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Trψ |T_{ρ}P_{≤d}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} − 𝔼_{b_{i}∼B}Trψ |T_{ρ}P_{≤d}Q_{f}^{ι}\{b_{i}\}|^{2} )

+ \frac{1}{n}|𝔼_{b_{i}∼B}Trψ |T_{ρ}P_{≤d}Q_{f}^{ι}\{b_{i}\}|^{2} − 𝔼_{b_{i}∼B}Trψ |T_{ρ}Q_{f}^{ι}\{b_{i}\}|^{2} |

≤ n^{1/2}(5^{6}c_{2}c_{3})^{d}τ^{1/6} + 8ρ^{d} + O_{m,n}(τ^{−1/3}p^{−1/2}),

(41)

where the last inequality uses (40) to bound the first term, (38) for the second and (39) for the third. From (9) and (10) we get ∥T_{ρ}Q_{f}(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m}, so by definition of ψ we have 𝔼_{b_{i}∼B}Trψ |T_{ρ}Q_{f}^{ι}{b_{i}}|^{2} = 0. Combining (37) with (41) and choosing d = min(max(1, −\frac{log(τ)}{30(c_{2}c_{3})}), m) completes the proof (using − log ρ ≥ 1 − ρ for all 0 < ρ < 1). □

3.3. Moment Majorization. Theorem 3.5 implies that the even moments of a noncommutative multilinear polynomial follow a majorization principle. Although we will not make use of Theorem 3.9 for the applications in this paper, we include it as the statement could be of independent interest; the theorem has analogues in both the commutative [MOO10] and free probability settings [DN14].

Theorem 3.9 (Noncommutative Majorization Principle for 2K^{th} Moments). Let Q be a noncommutative multilinear polynomial of degree d in m variables, as in (4). Suppose ∥Q(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m}. Let p > n, and let Q^{ι} be the zero-padded extension of Q, as defined in Definition 2.1. Let τ := max_{i=1,...,m} Inf_{i}Q. Let G_{i} ∼ G. Assume that ∥𝔼(G_{1}G_{1}^{∗})^{K} ∥ ≤ c_{K}, for some K ∈ ℕ and c_{K} ≥ 1. Then

\begin{matrix}𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} & \frac{1}{n} & Tr & |Q^{ι}\{G_{i}H_{i}\}| & 2K \\ ≤ 𝔼_{b_{i}∼B} \frac{1}{n}Tr |Q\{b_{i}\}|^{2K} + K^{3}(2K − 1)^{2dK}c_{K}^{d}n^{2K}τ^{1/4} + O_{m,n}(p^{−1/2}K^{2}τ^{−1/4}). \end{matrix} (42)

Proof. We begin with an upper tail estimate for Q^{ι}. From Markov’s inequality,

ℙ\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H_{p} \end{matrix}(Tr |Q^{ι}|^{2} > t) = ℙ\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H_{p} \end{matrix}((Tr |Q^{ι}|^{2} )^{K} > t^{K}) ≤ t^{−K} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} [Tr |Q^{ι}|^{2} ]^{K}.  (43)

Since Q^{ι} = I^{ι}Q^{ι} (where here I denotes the n×n identity matrix), Hölder’s inequality implies

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} (Tr |Q^{ι}|^{2} )^{K} = 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} (Tr |I^{ι}Q^{ι}|^{2} )^{K} ≤ n^{K−1} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}|^{2K} .  (44)

Combining (43) and (44) and applying Theorem 3.1,

ℙ\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H_{p} \end{matrix}(Tr |Q^{ι}|^{2} > t) ≤ t^{−K}n^{K−1}(2K − 1)^{2dK}c_{K}^{d}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}|^{2} )^{K}
≤ t^{−K}n^{2K−1}(2K − 1)^{2dK}c_{K}^{d}.  (45)

Let s > 0 be a constant to be fixed later. Define ψ: [0, ∞) → [0, ∞) so that ψ(t) = t^{K} for any 0 ≤ t ≤ s, and ψ is linear with slope Ks^{K−1} on (s + 1, ∞). It is possible to construct such a ψ with all three derivatives bounded, and in particular the third derivative bounded by some a_{3} ≤ K^{3}s^{K−3} on the interval [s, s + 1]. From Theorem 3.5,

\begin{matrix}𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ |Q^{ι}\{G_{i}H_{i}\}|^{2} \\ ≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ |Q\{b_{i}\}|^{2} + K^{3}s^{K−3}n^{3/2}(5^{6}c_{2}c_{3})^{d}τ^{1/2} + O_{n,m}(p^{−1/2}K^{2}s^{K−2}). \end{matrix}  (46)

Finally, defining a = K^{3}s^{K−3}n^{3/2}(5^{6}c_{2}c_{3})^{d}τ^{1/2} + O_{n,m}(p^{−1/2}K^{2}s^{K−2}) and letting D be the event that Trψ |Q^{ι}{G_{i}H_{i}}|^{2} ≤ s, we have

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2K} = 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2K} · 1_{D} + 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2K} · 1_{D^{c}}

= 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ |Q^{ι}\{G_{i}H_{i}\}|^{2} + 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2K} · 1_{D^{c}}.

Using (46) to bound the first term and Cauchy-Schwarz for the second, the above can be bounded as

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2K}

≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ |Q\{b_{i}\}|^{2} + a + ( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} (\frac{1}{n}Tr |Q^{ι}\{G_{i}H_{i}\}|^{2K} )^{2})^{1/2}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} 1_{D^{c}})^{1/2}

≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ |Q\{b_{i}\}|^{2} + a + ( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}\{G_{i}H_{i}\}|^{4K} )^{1/2}(ℙ\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H_{p} \end{matrix}(Tr |Q^{ι}|^{2} > s))^{1/2}

≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ |Q\{b_{i}\}|^{2} + a + (2K − 1)^{2dK}c_{K}^{d}( 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |Q^{ι}\{G_{i}H_{i}\}|^{2} )^{K}s^{−K/2}n^{K−1},

using Theorem 3.1 to bound the first term inside a square root, and (45) for the second. Finally, using Lemma 2.5 and ∥Q(σ)∥ ≤ 1 for all σ ∈ \{−1, 1\}^{m}, 𝔼\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix} Tr |Q^{ι}\{G_{i}H_{i}\}|^{2} ≤ 1.

Choosing s = τ^{−1/(4K)} finishes the proof. □

4. Maximizing Noncommutative Noise Stability

By adapting the proof of the Majority is Stablest Theorem from [MOO10], we can get the following consequence of Corollary 3.8.

Corollary 4.1. Let 0 ≤ ρ < 1 and let ε > 0. Let δ = 20n^{1/2}τ^{\frac{1−ρ}{30(c_{2}c_{3})}} + O_{m,n}(τ^{−1/3}p^{−1/2}). Then there exists τ > 0 such that, if f: {−1, 1}^{m} → M_{n}(ℂ) satisfies ∥f(σ)∥ ≤ 1 for all σ ∈ {−1, 1}^{m}, 𝔼_{b_{i}∼B}f{b_{i}} = 0, and max_{i=1,...,m} Inf_{i}(f) < τ, then

\frac{1}{n} 𝔼_{b_{i}∼B} Tr |T_{ρ}Q_{f}\{b_{i}\}|^{2} ≤ \frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} + O(ε + δ).  (47)

Moreover, |\frac{1}{n} 𝔼\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix} Tr ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}| ≤ δ.

Remark 4.2. In the case n = p = 1, it is known from [MOO10] that the right-hand side of (47) is \frac{2}{π} arcsin ρ + ε. For larger n, the left side of (47) can be interpreted as the noise stability of Q_{f} with discrete inputs, and the right side as the noise stability of a function with operator norm pointwise bounded by 1 under random Gaussian matrix inputs. Eq. (47) can thus be thought of as a matrix-valued version of one of the two main steps in the proof of the Majority is Stablest Theorem. However, for larger n, there seems to be no version of Borell’s isoperimetric inequality that describes what the right-hand side of (47) should be. (Recall that Borell’s isoperimetric inequality states that the noise stability of a subset of Euclidean space of fixed Gaussian measure is maximized when the set is a half space.)

Proof. Since 𝔼_{b_{i}∼B} f{b_{i}} = 0, we have 𝔼_{b_{i}∼B} Q_{f}{b_{i}} = 0. Using the Cauchy-Schwarz inequality and Corollary 3.8,

|\frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} − \frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} |

= |\frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} − \frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr(ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}[T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}]^{∗})|

+ |\frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr(ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}[T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}]^{∗}) − \frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} |

≤ ( ∥T_{ρ}Q_{f}^{ι}{G_{i}H_{i}}∥_{2,V} + ∥ChopT_{ρ}Q_{f}^{ι}{G_{i}H_{i}}∥_{2,V} ) · ∥T_{ρ}Q_{f}^{ι}{G_{i}H_{i}} − ChopT_{ρ}Q_{f}^{ι}{G_{i}H_{i}}∥_{2,V}

≤ 20n^{1/2}τ^{\frac{1−ρ}{30(c_{2}c_{3})}} + O_{m,n}(τ^{−1/3}p^{−1/2}).

Therefore,

\frac{1}{n} 𝔼_{b_{i}∼B} Tr |T_{ρ}Q_{f}\{b_{i}\}|^{2} =^{(11)∧(14)} \frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2}

≤ \frac{1}{n} 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr |ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|^{2} + 20n^{1/2}τ^{\frac{1−ρ}{30(c_{2}c_{3})}} + O_{m,n}(τ^{−1/3}p^{−1/2}),

proving (47).

Using 𝔼_{b_{i}∼B} Q_{f}^{ι}\{b_{i}\} = 𝔼\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix} T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\} = 0 and the Cauchy-Schwarz inequality,

\frac{1}{n}| 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}| = \frac{1}{n}| 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr ChopT_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\} − 𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Tr T_{ρ}Q_{f}^{ι}\{G_{i}H_{i}\}|

≤ 20n^{1/2}τ^{\frac{1−ρ}{30(c_{2}c_{3})}} + O_{m,n}(τ^{−1/3}p^{−1/2}),

using Corollary 3.8 again. □

5. An Anti-Concentration Inequality

As in [MOO10], we can use our invariance principle to prove anti-concentration estimates of polynomials.

Corollary 5.1 (An Anti-Concentration Estimate). There exists a constant C > 0 such that the following holds. Let Q: (M_{n}(ℂ))^{m} → M_{n}(ℂ) be a noncommutative multilinear polynomial of degree d. Assume 𝔼_{b_{i}∼B} \frac{1}{n}Tr |Q\{b_{i}\}|^{2} ≤ 1. Let τ = max_{1≤j≤m} Inf_{j}(Q). Define Var(Q) = 𝔼_{b_{i}∼B}Tr|Q{b_{i}} − (𝔼_{b_{j}∼B}Q{b_{j}})|^{2}. Then, for any t ∈ ℝ,

\frac{1}{n} ℙ_{\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H \end{matrix}}(∥Q^{ι}\{G_{i}H_{i}\}∥ > t) ≤ ℙ_{b_{i}∼B}(∥Q\{b_{i}\}∥ > t) + O(n^{3}c_{3}^{d}τ^{1/100})
+ Cd(4τ^{1/100}n/[Var(Q)]^{1/2})^{1/d} + O_{m,n}(τ^{−1/100}p^{−1/2}).

Remark 5.2. The \frac{1}{n} term on the left side of the inequality seems to be an artifact of our proof method. It comes from (50) below, where we bound the normalized trace of a matrix by its operator norm.

Proof. Define ϕ: ℝ → ℝ by ϕ(x) = c · exp (\frac{−1}{1−x^{2}} ) if |x| < 1 and ϕ(x) = 0 for all other x ∈ ℝ. The constant 1/2 < c < 4 is chosen so that ∫_{ℝ} ϕ(x)dx = 1. It is well-known that ϕ is an infinitely differentiable function with bounded derivatives.

Fix r, s > 0. Define ψ: ℝ → ℝ by

ψ(x) = \begin{cases}0 & if x ≤ r − s \\ \frac{s−r+x}{2s} & if r − s ≤ x ≤ r + s \\ 1 & if x > r + s. \end{cases}  (48)

Define ψ_{λ}(x) = ψ ∗ ϕ_{λ}(x) = ∫_{ℝ} ψ(y)ϕ_{λ}(x − y)dy. Then ψ_{λ}(x) = ψ(x) for any x ∈ ℝ with x > r + s + λ or x < r − s − λ. So,

𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} Trψ_{λ} |Q^{ι}\{G_{i}H_{i}\}|^{2} ≥ ℙ_{\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H \end{matrix}}(∥Q^{ι}\{G_{i}H_{i}\}∥ > r + s + λ).  (49)

𝔼_{b_{i}∼B} \frac{1}{n}Trψ_{λ} |Q\{b_{i}\}|^{2} ≤ ℙ_{b_{i}∼B}(∥Q\{b_{i}\}∥ > r − s − λ).  (50)

Note that |ψ′′′_{λ}(x)| ≤ 10^{10}λ^{−2}s. Applying Theorem 3.5,

\begin{matrix}𝔼_{\begin{matrix}G_{k}∼G⊗I \\ H_{k}∼H_{p} \end{matrix}} \frac{1}{n}Trψ_{λ} |Q^{ι}\{G_{i}H_{i}\}|^{2} \\ ≤ 𝔼_{b_{i}∼B} \frac{1}{n}Trψ_{λ} |Q\{b_{i}\}|^{2} + sλ^{−2}n^{3/2}10^{10}(5^{6}c_{3})^{d}τ^{1/4} + O_{m,n}(λ^{−2}sp^{−1/2}). \end{matrix}  (51)

Combining (49), (50) and (51),

\frac{1}{n} ℙ_{\begin{matrix}G_{i}∼G⊗I \\ H_{i}∼H \end{matrix}}(∥Q^{ι}\{G_{i}H_{i}\}∥ > r + s + λ)

≤ ℙ_{b_{i}∼B}(∥Q^{ι}{b_{i}}∥ > r − s − λ) + sλ^{−2}10^{10}(5^{6}c_{3})^{d}τ^{1/4} + O_{m,n}(sλ^{−2}p^{−1/2})

= ℙ_{b_{i}∼B}(∥Q{b_{i}}∥ > r + s + λ) + ℙ_{b_{i}∼B}(r + s + λ > ∥Q{b_{i}}∥ > r − s − λ)

+ sλ^{−2}n^{3/2}10^{10}(5^{6}c_{3})^{d}τ^{1/4} + O_{m,n}(sλ^{−2}p^{−1/2}).  (52)

It remains to show that the second term in (52) is small. To this end we apply the anticoncentration result of [CW01, Theorem 8] (with q = 2d in their notation) to get: there exists an absolute constant C′ > 0 such that, if g_{1}, …, g_{m} are i.i.d. standard real Gaussian random variables, and if Q is any noncommutative multilinear polynomial, then for all ε > 0,

ℙ_{g_{1},...,g_{m}}(∥Q{g_{i}}∥ < ε) ≤ C′d(ε/[𝔼_{g_{1},...,g_{m}} ∥Q{g_{i}}∥^{2}]^{1/2})^{1/d}.

Since 𝔼_{g_{1},...,g_{m}} ∥Q\{g_{i}\}∥^{2} ≥ 𝔼_{g_{1},...,g_{m}} \frac{1}{n}Tr |Q\{g_{i}\}|^{2} ≥ 𝔼_{g_{1},...,g_{m}} \frac{1}{n}Tr|Q\{g_{i}\} − Q̂(∅)|^{2}, we conclude that, for any r ∈ ℝ, we have the following “small ball” probability estimate.

ℙ_{g_{1},...,g_{m}}(|∥Q{g_{i}}∥ − r| < ε) ≤ C′d(εn/[𝔼_{g_{1},...,g_{m}}Tr|Q{g_{i}} − Q̂(∅)|^{2}]^{1/2})^{1/d}.  (53)

Now, applying the invariance principle [IM12, Theorem 3.6] with the function Ψ: M_{n}(ℂ) → ℝ defined by

Ψ(A) = \begin{cases}0 & if ∥A∥ ≤ r − 2s \\ \frac{2s−r+∥A∥}{s} & if r − 2s ≤ ∥A∥ ≤ r − s \\ 1 & if r − s ≤ ∥A∥ ≤ r + s \\ \frac{2s+r−∥A∥}{s} & if r + s ≤ ∥A∥ ≤ r + 2s \\ 0 & if ∥A∥ > r + 2s. \end{cases}

We get

|𝔼_{b_{i}∼B}Ψ(Q\{b_{i}\}) − 𝔼_{g_{1},...,g_{m}}Ψ(Q\{g_{i}\})| ≤ \frac{2}{s}n^{3}C′′τ^{1/50}.  (54)

So, applying the definition of Ψ to (54), we get

ℙ_{b_{i}∼B}(|∥Q\{b_{i}\}∥ − r| < s) ≤ \frac{2}{s}C′′n^{3}τ^{1/50} + ℙ_{g_{1},...,g_{m}}(|∥Q\{g_{i}\}∥ − r| < 2s)

≤^{(53)} \frac{2}{s}C′′n^{3}τ^{1/50} + C′d(2sn/[𝔼_{g_{1},...,g_{m}}Tr|Q\{g_{i}\} − Q̂(∅)|^{2}]^{1/2})^{1/d}

= \frac{2}{s}C′′n^{3}τ^{1/50} + C′d(2sn/[𝔼_{b_{i}∼B}Tr|Q\{b_{i}\} − Q̂(∅)|^{2}]^{1/2})^{1/d}.

Finally, substitute the last inequality into (52) and set s = λ = τ^{1/100}. □

Remark 5.3. The theorem [IM12, Theorem 3.6] used in (54) provides an extra multiplicative factor of 2^{n^{2}} in (54). However, this constant can be removed in the following way. Using their notation, they define a function ϕ: ℝ^{k} → ℝ so that ϕ(x) = exp(\frac{−1}{1−∥x∥_{2}^{2}} ) if ∥x∥_{2} < 1 and ϕ(x) = 0 otherwise. (In the present paper, we set k = n^{2}.) This is the function they use in their convolution formula. If we instead use a function ϕ which is a product of one-dimensional functions, each of which is supported in the interval [−1, 1], e.g. ϕ(x) =

∏_{i=1}^{k} e^{\frac{−1}{1−x^{2}_{i}}}, then the factor 2^{k} no longer appears in their proof.

Remark 5.4. The stronger, though more restrictive anti-concentration inequality

\begin{matrix}sup_{t∈ℝ} | ℙ_{g_{1},...,g_{m}}(∥Q\{g_{i}\}∥ > t) − ℙ_{b_{i}∼B}(∥Q\{b_{i}\}∥ > t)| \\ ≤ O(n^{3}c_{3}^{d}τ^{1/100}) + Cd(2τ^{1/100}n/[Var(Q)]^{1/2})^{1/d}, \end{matrix}  (55)

follows more directly from [CW01, Theorem 8] and [IM12, Theorem 3.6] by repeating the argument above. For example, if we use ψ defined in (48), then [IM12, Theorem 3.6] implies that

|𝔼_{b_{i}∼B}ψ(Q\{b_{i}\}) − 𝔼_{g_{1},...,g_{m}}ψ(Q\{g_{i}\})| ≤ \frac{2}{s}n^{3}C′′τ^{1/50}.

Applying the definition of ψ to this inequality, we get

| ℙ_{g_{1},...,g_{m}}(∥Q\{g_{i}\}∥ > r + s + λ) − ℙ_{b_{i}∼B}(∥Q\{b_{i}\}∥ > r − s − λ)| ≤ \frac{2}{s}n^{3}C′′τ^{1/50}. (56)

Therefore,

| ℙ_{g_{1},...,g_{m}}(∥Q{g_{i}}∥ > r + s + λ) − ℙ_{b_{i}∼B}(∥Q{b_{i}}∥ > r + s + λ)|

= | − ℙ_{g_{1},...,g_{m}}(r + s + λ > ∥Q{g_{i}}∥ > r − s − λ)

+ ℙ_{g_{1},...,g_{m}}(∥Q{g_{i}}∥ > r + s + λ) − ℙ_{b_{i}∼B}(∥Q{b_{i}}∥ > r − s − λ)|

≤ | ℙ_{g_{1},...,g_{m}}(r + s + λ > ∥Q{g_{i}}∥ > r − s − λ)|

+ | ℙ_{g_{1},...,g_{m}}(∥Q{g_{i}}∥ > r + s + λ) − ℙ_{b_{i}∼B}(∥Q{b_{i}}∥ > r − s − λ)|.

The second term is bounded by (56) and the first term is bounded by (53), setting s = λ = τ^{1/100}.

Remark 5.5. It would be desirable to upgrade Corollary 5.1 and (55) to the stronger inequalities presented in [MNV16]. We leave this research direction to future investigations.

Acknowledgements. Thanks to Todd Kemp, Elchanan Mossel, Assaf Naor, Krzysztof Oleszkiewicz, Dimitri Shlyakhtenko and Thomas Vidick for helpful discussions. Thanks also to the anonymous reviewer for several helpful comments and for finding several typos and mistakes.

References

[Bha97] R. Bhatia, Matrix analysis, Graduate Texts in Mathematics, Springer New York, 1997.

[Bon70] 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)

[BR15] Jonah Brown-Cohen and Prasad Raghavendra, Combinatorial optimization algorithms via polymorphisms, Electronic Colloquium on Computational Complexity (ECCC) 22 (2015), 7.

[Cha06] Sourav Chatterjee, A generalization of the Lindeberg principle, Ann. Probab. 34 (2006), no. 6, 2061–2076. MR 2294976 (2008c:60028)

[CW01] Anthony Carbery and James Wright, Distributional and L^{q} norm inequalities for polynomials over convex bodies in ℝ^{n}, Math. Res. Lett. 8 (2001), no. 3, 233–248. MR 1839474

[DN14] Aurélien Deya and Ivan Nourdin, Invariance principles for homogeneous sums of free random variables, Bernoulli 20 (2014), no. 2, 586–603. MR 3178510

[DR13] Sjoerd Dirksen and Éric Ricard, Some remarks on noncommutative Khintchine inequalities, Bull. Lond. Math. Soc. 45 (2013), no. 3, 618–624. MR 3065031

[DS01] Kenneth R. Davidson and Stanislaw J. Szarek, Local operator theory, random matrices and Banach spaces, Handbook of the geometry of Banach spaces, Vol. I, North-Holland, Amsterdam, 2001, pp. 317–366. MR 1863696

[Gro72] Leonard Gross, Existence and uniqueness of physical ground states, J. Functional Analysis 10 (1972), 52–109. MR 0339722 (49 #4479)

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

[HT99] U. Haagerup and S. Thorbjørnsen, Random matrices and K-theory for exact C^{∗}-algebras, Doc. Math. 4 (1999), 341–450 (electronic). MR 1710376 (2000g:46092)

[IM12] Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel J. Math. 189 (2012), 347–396. MR 2931402

[Kal02] Gil Kalai, A Fourier-theoretic perspective on the Condorcet paradox and Arrow’s theorem, Adv. in Appl. Math. 29 (2002), no. 3, 412–426. MR 1942631

[Kan14] Daniel M. Kane, The correct exponent for the Gotsman-Linial conjecture, Comput. Complexity 23 (2014), no. 2, 151–175. MR 3212596

[Kho02] Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (New York), ACM, 2002, pp. 767–775 (electronic). MR MR2121525

[KKL88] 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.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37 (2007), no. 1, 319–357. MR 2306295 (2008d:68035)

[KN09] Subhash Khot and Assaf Naor, Approximate kernel clustering, Mathematika 55 (2009), no. 1-2, 129–165. MR 2573605 (2011c:68166)

[KN13] , Sharp kernel clustering algorithms and their associated grothendieck inequalities, Random Structures & Algorithms 42 (2013), no. 3, 269–300.

[KVV14] Dmitry S. Kaliuzhnyi-Verbovetskyi and Victor Vinnikov, Foundations of free noncommutative function theory, Mathematical Surveys and Monographs, vol. 199, American Mathematical Society, Providence, RI, 2014. MR 3244229

[MJC^{+}14] Lester Mackey, Michael I. Jordan, Richard Y. Chen, Brendan Farrell, and Joel A. Tropp, Matrix concentration inequalities via the method of exchangeable pairs, Ann. Probab. 42 (2014), no. 3, 906–945. MR 3189061

[MN15] Elchanan Mossel and Joe Neeman, Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 2, 433–482. MR 3317748

[MNV16] Raghu Meka, Oanh Nguyen, and Van Vu, Anti-concentration for polynomials of independent random variables, Theory Comput. 12 (2016), Paper No. 11, 16. MR 3542863

[MOO10] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), no. 1, 295–341. MR 2630040 (2012a:60091)

[Mos10] Elchanan Mossel, Gaussian bounds for noise correlation of functions, Geom. Funct. Anal. 19 (2010), no. 6, 1713–1756. MR 2594620 (2011b:60080)

[MP14] Shahar Mendelson and Grigoris Paouris, On the singular values of random matrices, J. Eur. Math. Soc. (JEMS) 16 (2014), no. 4, 823–834. MR 3191978

[MS12] Mark W. Meckes and Stanisław J. Szarek, Concentration for noncommutative polynomials in random matrices, Proc. Amer. Math. Soc. 140 (2012), no. 5, 1803–1813. MR 2869165 (2012j:60048)

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

[NPR10] Ivan Nourdin, Giovanni Peccati, and Gesine Reinert, Invariance principles for homogeneous sums: universality of Gaussian Wiener chaos, Ann. Probab. 38 (2010), no. 5, 1947–1985. MR 2722791 (2011g:60043)

[O’D14a] Ryan O’Donnell, Analysis of Boolean functions, Cambridge University Press, 2014. [O’D14b] , Social choice, computational complexity, gaussian geometry, and boolean functions, Pro-

ceedings of the ICM, 2014.

[Rot79] V. I. Rotar′, Limit theorems for polylinear forms, J. Multivariate Anal. 9 (1979), no. 4, 511–530. MR 556909 (81m:60039)

[Tal94] Michel Talagrand, On Russo’s approximate zero-one law, Ann. Probab. 22 (1994), no. 3, 1576– 1587. MR 1303654 (96g:28009)

[TV11] Terence Tao and Van Vu, Random matrices: universality of local eigenvalue statistics, Acta Math. 206 (2011), no. 1, 127–204. MR 2784665 (2012d:60016)

[Ver12] Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR 2963170

[Voi91] Dan Voiculescu, Limit laws for random matrices and free products, Invent. Math. 104 (1991), no. 1, 201–220. MR 1094052 (92d:46163)

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

  E-mail address: stevenmheilman@gmail.com