LOCALLY DECODABLE CODES AND THE FAILURE OF COTYPE FOR PROJECTIVE TENSOR PRODUCTS

JOP BRIËT, ASSAF NAOR, AND ODED REGEV

Abstract. It is shown that for every p ∈ (1, ∞) there exists a Banach space X of finite cotype such that the projective tensor product ℓ_{p} ˆ⊗X fails to have finite cotype. More generally, if p_{1}, p_{2}, p_{3} ∈ (1, ∞) satisfy \frac{1}{p_{1}} + \frac{1}{p_{2}} + \frac{1}{p_{3}} ⩽ 1 then ℓ_{p_{1}} ˆ⊗ℓ_{p_{2}} ˆ⊗ℓ_{p_{3}} does not have finite cotype. This is proved via a connection to the theory of locally decodable codes.

1. introduction

Throughout this paper all Banach spaces are assumed to be over the reals, though our results apply (with the same proofs) to complex Banach spaces as well. We shall use standard Banach space notation and terminology, e.g., as in [1]. We shall also use the asymptotic notation ≲, ≳ to indicate the corresponding inequalities up to universal constant factors, and we shall denote equivalence up to universal constant factors by ≍, i.e., A ≍ B is the same as (A ≲ B) ∧ (A ≳ B).

The projective tensor product of two Banach spaces (X, ∥ · ∥_{X}) and (Y, ∥ · ∥_{Y}), denoted X ˆ⊗Y, is the completion of their algebraic tensor product X ⊗ Y, equipped with the norm

∥z∥_{X ˆ⊗Y} = inf {∑_{i=1}^{n} ∥x_{i}∥_{X} · ∥y_{i}∥_{Y} : ∃ n ∈ ℕ, ∃{(x_{i}, y_{i})}_{i=1}^{n} ⊆ X × Y,

such that z = ∑_{i=1}^{n} x_{i} ⊗ y_{i}} .

Thus, if X, Y are finite dimensional then the unit ball of X ˆ⊗Y is the convex hull in X ⊗ Y of all the vectors of the form x ⊗ y, where x is a unit vector in X and y is a unit vector in Y. To state two concrete examples of this construction, one always has ℓ_{1} ˆ⊗X = ℓ_{1}(X), and ℓ_{2} ˆ⊗ℓ_{2} can be naturally identified with the Schatten trace class S_{1}, i.e., the space of all compact operators T : ℓ_{2} → ℓ_{2}, equipped with the norm ∥T ∥_{S_{1}} = trace(\sqrt{T^{∗}T}). For these facts, and much more information on projective tensor products, we refer to [15, 24, 12].

J. B. was supported by an NWO Vici grant and the EU project QCS. A. N. was supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation. Part of this work was completed while A. N. was visiting Université Pierre et Marie Curie, Paris, France. O. R. was supported by a European Research Council (ERC) Starting Grant.

The literature contains a significant amount of work on the permanence of various key Banach space properties under projective tensor products; see the survey [11] for some of the known results along these lines. Here we will be mainly concerned with geometric properties of projective tensor products with L_{p}(μ) spaces, p ∈ (1, ∞), in which case examples of known results include that L_{p} ˆ⊗X is weakly sequentially complete iff X is [18], L_{p} ˆ⊗X has the Radon-Nikodým property iff X does [9, 8], and L_{p} ˆ⊗X contains a copy of c_{0} iff X does [10].

When one does not consider projective tensor products with L_{p}(μ) spaces, the above permanence properties are known to fail [21, 7]. Specifically, Bourgain and Pisier [7] showed that there exist a weakly sequentially complete Banach space X with the Radon-Nikodým property, such that X ˆ⊗X contains a copy of c_{0} (thus X ˆ⊗X fails weak sequential completeness and the Radon-Nikodým property).

Here we will be concerned with the permanence of finite cotype under projective tensor products. For q ∈ [2, ∞), a Banach space (X, ∥ · ∥_{X}) is said to have cotype q if there exists C ∈ (0, ∞) such that for every n ∈ ℕ and every x_{1}, …, x_{n} ∈ X we have

(∑_{i=1}^{n} ∥x_{i}∥_{X}^{q})^{1/q} ⩽ C (𝔼 [∥∑_{i=1}^{n} ε_{i}x_{i}∥_{X}^{2} ])^{1/2} ,  (1)

where the expectation in (1) is taken with respect to uniformly distributed ε = (ε_{1}, …, ε_{n}) ∈ {−1, 1}^{n}. Thus L_{p} has cotype max{p, 2} for for every p ∈ [1, ∞) (see, e.g., [1]). The infimum over those C ∈ (0, ∞) for which (1) holds true is denoted C_{q}(X, ∥ · ∥_{X}), or, if the norm is clear from the context, simply C_{q}(X). Given k ∈ ℕ and a norm ∥ · ∥ on ℝ^{k}, it will also be convenient to denote C_{∥·∥}^{(q)} = C_{q}(ℝ^{k}, ∥ · ∥). If X has cotype q for some q ∈ [2, ∞) then we say that X has finite cotype, or simply that X has cotype. The Maurey-Pisier theorem [19] implies that X fails to have finite cotype if and only if it is universal in the sense that there exists K ∈ (0, ∞) such that all finite dimensional Banach spaces embed into X with distortion at most K (equivalently, ℓ_{∞}^{n} embeds into X with distortion at most K for all n ∈ ℕ). We are therefore interested in the permanence under projective tensor products of the failure of the above universality property.

Tomczak-Jaegermann proved [25] that ℓ_{2} ˆ⊗ℓ_{2} = S_{1} has cotype 2, and Pisier proved [22, 23] that if p, q ∈ [2, ∞) then L_{p} ˆ⊗L_{q} has cotype max{p, q} (see [22] for a more general result along these lines). Other than these facts and the easy fact that L_{1} ˆ⊗X = L_{1}(X) always inherits the cotype of X, we do not know of other permanence results for cotype under projective tensor products. In particular, it is open whether L_{p} ˆ⊗L_{q} has finite cotype when p ∈ (1, 2) and q ∈ (1, 2], and whether ℓ_{2} ˆ⊗S_{1} = ℓ_{2} ˆ⊗ℓ_{2} ˆ⊗ℓ_{2} has finite cotype (these questions are stated in [23]).

A remarkable theorem of Pisier [21] asserts that there exist two Banach spaces X and Y of finite cotype such that X ˆ⊗Y does not have finite cotype. Specifically, by a famous theorem of Bourgain [5], L_{1}/H^{1} has cotype 2 (H^{1} is the closed span of {θ ↦ e^{2πinθ}}_{n=0}^{∞} ⊆ L_{1}), and Pisier constructs [21] a Banach space Z of cotype 2 such that Z ˆ⊗(L_{1}/H^{1}) contains a copy of c_{0}.

We have seen that projective tensor products with L_{p}(μ) spaces preserve a variety of geometric properties, but that similar results often fail for projective tensor products between general Banach spaces. In this vein, for p ∈ (1, ∞) it was unknown whether L_{p} ˆ⊗X has finite cotype if X has finite cotype. This question was explicitly asked in [11, p. 59], and here we answer it negatively by showing that for every p ∈ (1, ∞) there exists a Banach space X of finite cotype such that ℓ_{p} ˆ⊗X fails to have finite cotype. Thus, L_{p} ˆ⊗X contains copies {ℓ_{∞}^{n}}_{n=1}^{∞} with distortion bounded by a constant independent of n; contrast this statement with the theorem of Bu and Dowling [10] quoted above that asserts that L_{p} ˆ⊗Y contains a copy of c_{0} iff Y itself contains a copy of c_{0}. Note that when p = 2 we see that even the projective tensor product with Hilbert space need not preserve finite cotype.

Our main result is the following theorem.

Theorem 1.1. Fix p_{1}, p_{2}, p_{3} ∈ (1, ∞) such that

\frac{1}{p_{1}} + \frac{1}{p_{2}} + \frac{1}{p_{3}} ⩽ 1.  (2)

Then ℓ_{p_{1}} ˆ⊗ℓ_{p_{2}} ˆ⊗ℓ_{p_{3}} does not have finite cotype. Moreover, there exists a universal constant c ∈ (0, ∞) such that for every p_{1}, p_{2}, p_{3} ∈ (1, ∞) satisfying (2), every q ∈ [2, ∞), and every integer n > 15 we have

C_{q} (ℓ_{p_{1}}^{n} ˆ⊗ℓ_{p_{2}}^{n} ˆ⊗ℓ_{p_{3}}^{n}) ≳ \frac{1}{log n} · exp (\frac{c}{q} · \frac{(log log n)^{2}}{log log log n}) .  (3)

It follows from Theorem 1.1 that for every p ∈ (1, ∞), if we set X = ℓ_{2p/(p−1)} ˆ⊗ℓ_{2p/(p−1)} then ℓ_{p} ˆ⊗X fails to have finite cotype. By the result of Pisier [22] quoted above, X has finite cotype. Another notable consequence of Theorem 1.1 is that there exists a Banach space Y such that Y ˆ⊗Y has finite cotype yet Y ˆ⊗Y ˆ⊗Y fails to have finite cotype. We conjecture that (3) is not sharp, leaving open the determination of the asymptotic behavior of, say, C_{q} (ℓ_{3}^{n} ˆ⊗ℓ_{3}^{n} ˆ⊗ℓ_{3}^{n}).

Our proof of Theorem 1.1 is based on a connection between cotype of tensor products and results from theoretical computer science, namely the theory of locally decodable codes. This link allows us to use (as a “black box”) delicate constructions that are available in the computer science literature in order to prove Theorem 1.1. Our initial hope was to use this connection in the reverse direction, namely, to use Banach space theory to address an important question about the length of locally decodable codes, but it turned out that instead locally decodable codes can be used to address the question in Banach space theory described above. Nevertheless, there is hope that the connection presented below, when combined with geometric insights about tensor norms, might lead to improved lower bounds for locally decodable codes. This hope will be made explicit in the following section.

1.1. Locally decodable codes and cotype. Definition 1.2 below is due to Katz and Trevisan [16]; see the surveys [26, 29] for more information on this notion (and the closely related notion of private information retrieval), as well as a description of some of its many applications in cryptography and computational complexity theory. We note that in the present paper no reference to Definition 1.2 will be made other than through the conclusion of Lemma 3.1 below.

Definition 1.2 (3-query locally decodable code). Fix m, n ∈ ℕ and ϕ, θ ∈ (0, 1/2). A function

C : {−1, 1}^{m} → {−1, 1}^{n}

is called a 3-query locally decodable code of quality (ϕ, θ) if for every t ∈ {1, …, m} there exists a distribution A_{t} over 4-tuples (i, j, k, g), where i, j, k ∈ {1, …, n} and g : {−1, 1}^{3} → {−1, 1}, with the property that for every ε ∈ {−1, 1}^{m} and every δ ∈ {−1, 1}^{n} that differs from C(ε) in at most ϕ · n coordinates, with probability (with respect to the distribution A_{t}) at least \frac{1}{2} + θ we have g(δ_{i}, δ_{j}, δ_{k}) = ε_{t}.

The motivation behind Definition 1.2 is as follows. Just like standard error correcting codes, locally decodable codes provide a way to encode an m-bit message into a longer n-bit codeword in a way that allows one to recover the original message from the codeword, even if it is corrupted in any set of coordinates that isn’t too large. However, while standard error correcting codes typically require reading essentially all the n bits of the corrupted codeword in order to recover even one bit of the message, a 3-query locally decodable code allows one to do this while reading only 3 bits.

It is an important open question to determine the asymptotic behavior in m of the smallest n for which 3-query locally decodable codes exist (for some fixed ϕ, θ, say, ϕ = θ = 1/16). The best known upper bound, due to Efremenko [13] using in part key ideas of Yekhanin [28] and a combinatorial construction of Grolmusz [14], is that for every m ∈ ℕ there exists an integer n ∈ ℕ satisfying

log log n ≍ \sqrt{log m log log m},  (4)

for which there exists a code C : {−1, 1}^{m} → {−1, 1}^{n} which is 3-query locally decodable of quality (ϕ, \frac{1}{2} − 6ϕ) for all ϕ ∈ (0, 1/12). See [3] for an improvement of the implicit constant factor in (4).

The best known lower bound, due to Woodruff [27] as a logarithmic improvement over a lower bound of Kerenidis and de Wolf [17], is that for, say, ϕ = θ = 1/16 we necessarily have

n ≳ \frac{m^{2}}{log m}.  (5)

In what follows, given n ∈ ℕ we let e_{1}, …, e_{n} be the standard coordinate basis of ℝ^{n}. Let ∥·∥ be a norm on ℝ^{n} ⊗ℝ^{n} ⊗ℝ^{n}. For K ∈ [1, ∞) say that ∥ · ∥ is K-tensor-symmetric if for every choice of permutations π, σ, τ ∈ S_{n}, every choice of sign vectors ε, δ, η ∈ {−1, 1}^{n}, and every choice of scalars {a_{i,j,k}}_{i=1}^{n} ⊆ ℝ, we have

∥∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} ε_{i}δ_{j}η_{k}a_{π(i),σ(j),τ(k)}e_{i} ⊗ e_{j} ⊗ e_{k}∥

⩽ K ∥∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} a_{i,j,k}e_{i} ⊗ e_{j} ⊗ e_{k}∥ . (6)

Theorem 1.3. Fix m, n ∈ ℕ and ϕ, θ ∈ (0, 1/2). Suppose that there exists a 3-query locally decodable code C : {−1, 1}^{m} → {−1, 1}^{n} of quality (ϕ, θ). For every K ∈ [1, ∞), if ∥ · ∥ is a K-tensor-symmetric norm on ℝ^{3n} ⊗ ℝ^{3n} ⊗ ℝ^{3n} then for every q ∈ [2, ∞) we have

K^{2}C_{∥·∥}^{(q)} · \frac{∥∑_{i=1}^{3n} ∑_{j=1}^{3n} ∑_{k=1}^{3n} e_{i} ⊗ e_{j} ⊗ e_{k}∥}{∥∑_{i=1}^{3n} e_{i} ⊗ e_{i} ⊗ e_{i}∥} ≳ \frac{ϕθ^{2}m^{1/q}}{log(n + 1)}.

Theorem 1.3 implies that if, say, ϕ = θ = 1/16 then there exists a universal constant c ∈ (0, ∞) such that

n ⩾ sup_{∥·∥} sup_{q∈[2,∞)} exp (\frac{cm^{1/q} ∥∑_{i=1}^{3n} e_{i} ⊗ e_{i} ⊗ e_{i}∥}{C_{∥·∥}^{(q)} ∥∑_{i=1}^{3n} ∑_{j=1}^{3n} ∑_{k=1}^{3n} e_{i} ⊗ e_{j} ⊗ e_{k}∥}) , (7)

where the first supremum in (7) is taken over all the 1-tensor-symmetric norms ∥ · ∥ on ℝ^{3n} ⊗ ℝ^{3n} ⊗ ℝ^{3n}. While our initial hope was to use (7) to narrow the large gap between (4) and (5), we do not know if there exists a norm on ℝ^{3n} ⊗ ℝ^{3n} ⊗ ℝ^{3n} with respect to which (7) exhibits an asymptotic improvement over (5). This question is arguably the most important question that the present paper leaves open. However, Theorem 1.3 contains new information when one contrasts it with Efremenko’s upper bound (4), thus yielding the following corollary.

Corollary 1.4. There exists a universal constant c ∈ (0, ∞) such that for every integer n > 15, every q ∈ [2, ∞) and every K ∈ [1, ∞), any K-tensor-symmetric norm ∥ · ∥ on ℝ^{n} ⊗ ℝ^{n} ⊗ ℝ^{n} satisfies

C_{∥·∥}^{(q)} ≳ \frac{∥∑_{i=1}^{n} e_{i} ⊗ e_{i} ⊗ e_{i}∥}{∥∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} e_{i} ⊗ e_{j} ⊗ e_{k}∥} · \frac{exp (\frac{c}{q} · \frac{(log log n)^{2}}{log log log n})}{K^{2} log n}.

Suppose that p_{1}, p_{2}, p_{3} ∈ (1, ∞) satisfy (2) and define r ∈ [1, ∞) by

\frac{1}{r} =^{def} \frac{1}{p_{1}} + \frac{1}{p_{2}} + \frac{1}{p_{3}} .

Denoting e = ∑_{i=1}^{n} e_{i} ∈ ℝ^{n}, we have

∥∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} e_{i} ⊗ e_{j} ⊗ e_{k}∥_{ℓ_{p_{1}}^{n} ˆ⊗ℓ_{p_{2}}^{n} ˆ⊗ℓ_{p_{3}}^{n}} = ∥e ⊗ e ⊗ e∥_{ℓ_{p_{1}}^{n} ˆ⊗ℓ_{p_{2}}^{n} ˆ⊗ℓ_{p_{3}}^{n}}

= ∥e∥_{ℓ_{p_{1}}^{n}} · ∥e∥_{ℓ_{p_{2}}^{n}} · ∥e∥_{ℓ_{p_{3}}^{n}} = n^{1/p_{1}} · n^{1/p_{2}} · n^{1/p_{3}} = n^{1/r}. (8)

It is also well known (see, e.g., Theorem 1.3 in [2]) that

∥∑_{i=1}^{n} e_{i} ⊗ e_{i} ⊗ e_{i}∥_{ℓ_{p_{1}}^{n} ˆ⊗ℓ_{p_{2}}^{n} ˆ⊗ℓ_{p_{3}}^{n}} = n^{1/r}.  (9)

Since ℓ_{p_{1}}^{n} ˆ⊗ℓ_{p_{2}}^{n} ˆ⊗ℓ_{p_{3}}^{n} is 1-tensor-symmetric, it follows from (8) and (9) that Theorem 1.1 is a consequence of Corollary 1.4.

Acknowledgements. We are very grateful to Gilles Pisier for his encouragement and many insightful suggestions.

2. Preliminaries

In this section we briefly recall some standard notation and results on vector-valued Fourier analysis.

For n ∈ ℕ, the Walsh functions {W_{A} : {−1, 1}^{n} → {−1, 1}}_{A⊆{1,...,n}} are given by W_{A}(ε) = ∏_{i∈A} ε_{i}. If (X, ∥ · ∥_{X}) is a Banach space then for every f : {−1, 1}^{n} → X and A ⊆ {1, …, n} we write

f̂(A) = 𝔼 [W_{A}(ε)f(ε)] ,  (10)

where the expectation in (10) is with respect to ε ∈ {−1, 1}^{n} chosen uniformly at random. Then,

∀ ε ∈ {−1, 1}^{n}, f(ε) = ∑_{A⊆{1,...,n}} W_{A}(ε)f̂(A).

The Rademacher projection of f, denoted Rad(f) : {−1, 1}^{n} → X, is defined by

∀ ε ∈ {−1, 1}^{n}, Rad(f)(ε) = ∑_{i=1}^{n} ε_{i}f̂({i}).

Pisier’s famous bound on the K-convexity constant [20] asserts that if X is finite dimensional then every f : {−1, 1}^{n} → X satisfies

\sqrt{𝔼 [∥Rad(f)(ε)∥_{X}^{2}]} ≲ log (dim(X) + 1) · \sqrt{𝔼 [∥f(ε)∥_{X}^{2}]}. (11)

Recall that the implied constant in (11) is universal, and thus it does not depend on n, f, (X, ∥ · ∥_{X}) or dim(X). Bourgain proved [6] that the logarithmic dependence on dim(X) in (11) cannot be improved in general.

3. Relating locally decodable codes to cotype

Locally decodable codes will be used in what follows via the following lemma which is a slight variant of a result that appears in Appendix B of [4] (the proof in [4] is itself a variant of an argument in [17]).

Lemma 3.1 ([4]). Fix m, n ∈ ℕ and ϕ, θ ∈ (0, 1/2). Suppose that C : {−1, 1}^{m} → {−1, 1}^{n} is a 3-query locally decodable code of quality (ϕ, θ). Then there exists a function C′ : {−1, 1}^{m} → {−1, 1}^{3n} with the following properties. For every i ∈ {1, …, m} there exist three permutations π_{i}, σ_{i}, τ_{i} ∈ S_{3n}, and for every j ∈ {1, …, ⌈ϕθn/9⌉} there exists a sign δ_{i}^{j} ∈ {−1, 1}, such that if ε ∈ {−1, 1}^{m} is chosen uniformly at random then with probability at least \frac{1}{2} + \frac{θ}{16} we have

C′(ε)_{π_{i}(j)}C′(ε)_{σ_{i}(j)}C′(ε)_{τ_{i}(j)} = δ_{i}^{j}ε_{i}.  (12)

Proof. By Appendix B of [4], for every i ∈ {1, …, m} there exists a family of nonempty disjoint subsets F_{i} of {1, …, n} such that

• |F_{i}| ⩾ \frac{ϕθn}{9},

• each S ∈ F_{i} satisfies |S| ⩽ 3,

• for each S ∈ F_{i} there exists a sign δ_{i}(S) ∈ {−1, 1} such that if ε ∈ {−1, 1}^{m} is chosen uniformly at random then

Prob [∏_{s∈S} C(ε)_{s} = δ_{i}(S)ε_{i}] ⩾ \frac{1}{2} + \frac{θ}{16}.  (13)

Define C′ : {−1, 1}^{m} → {−1, 1}^{3n} by setting the first n coordinates of C′(x) to be equal to C(x), and defining the remaining 2n coordinates of C′(x) to be equal to 1. One can then add 3 − |S| elements from {n+1, …, 3n} to each set S ∈ F_{i} so that F_{i} becomes a family of disjoint subsets of {1, …, 3n} of size equal to 3, while not changing the validity of (13) with C replaced by C′. Write F_{i} = {{π_{i}(j), σ_{i}(j), τ_{i}(j)}}_{j=1}^{|F_{i}|} for some π_{i}, σ_{i}, τ_{i} ∈ S_{3n}. Letting δ_{i}^{j} = δ_{i}({π_{i}(j), σ_{i}(j), τ_{i}(j)}), the validity of (12) with probability at least \frac{1}{2} + \frac{θ}{16} is the same as (13). □

Remark 3.1. An inspection of the proof of Efremenko’s result [13] reveals that it directly gives a function C′ as in Lemma 3.1. Therefore, strictly speaking, Lemma 3.1 is only required for statements like Theorem 1.3 that involve arbitrary locally decodable codes, and not for statements like Theorem 1.1 and Corollary 1.4 that use Efremenko’s construction. We also note that the function C′ given by Efremenko’s construction has properties that are slightly stronger than those guaranteed by Lemma 3.1: it satisfies (12) for every ε ∈ {−1, 1}^{m}, and moreover one can take δ_{i}^{j} = 1 for all i, j. It is easy to see, however, that the latter property can be ensured in general, with only a slight loss in constants (say by replacing 3n with 6n).

Fix n ∈ ℕ and let ∥ · ∥ be a seminorm on (ℝ^{n})^{⊗3} =^{def} ℝ^{n} ⊗ ℝ^{n} ⊗ ℝ^{n}. Write

O_{∥·∥} =^{def} max_{ε∈{−1,1}^{n}} ∥ε ⊗ ε ⊗ ε∥.  (14)

For α, β ∈ (0, 1) consider the subset S(α, β) ⊆ (ℝ^{n})^{⊗3} defined by

S(α, β)

=^{def} ⋃_{π,σ,τ∈S_{n}} ⋂_{j=1}^{⌈βn⌉} {x ∈ (ℝ^{n})^{⊗3} : |⟨e_{π(j)} ⊗ e_{σ(j)} ⊗ e_{τ(j)}, x⟩| ⩾ α} , (15)

and write

S_{∥·∥}(α, β) =^{def} min_{x∈S(α,β)} ∥x∥.  (16)

Theorem 3.2. Fix m, n ∈ ℕ and ϕ, θ ∈ (0, 1/2). Suppose that there exists a 3-query locally decodable code C : {−1, 1}^{m} → {−1, 1}^{n} of quality (ϕ, θ). Then for every seminorm ∥ · ∥ on ℝ^{3n} ⊗ ℝ^{3n} ⊗ ℝ^{3n} and every q ∈ [2, ∞) we have

\frac{m^{1/q}}{log(n + 1)} ≲ \frac{C_{∥·∥}^{(q)} · O_{∥·∥}}{S_{∥·∥}(θ/8, ϕθ/27)}.  (17)

Proof. Let C′ : {−1, 1}^{m} → {−1, 1}^{3n} be the function from Lemma 3.1. Define f : {−1, 1}^{m} → ℝ^{3n} ⊗ ℝ^{3n} ⊗ ℝ^{3n} by

f(ε) = C′(ε) ⊗ C′(ε) ⊗ C′(ε).

Recalling the definition (14), we have ∥f(ε)∥ ⩽ O_{∥·∥} for all ε ∈ {−1, 1}^{m}. Combined with Pisier’s bound on the K-convexity constant (11), we therefore have

log ((3n)^{3} + 1) · O_{∥·∥} ≳ (𝔼 ∥∑_{i=1}^{m} ε_{i}f̂({i})∥^{2})^{1/2}

⩾ \frac{1}{C_{∥·∥}^{(q)}} (∑_{i=1}^{m} ∥f̂(\{i\})∥^{q})^{1/q} , (18)

where in the last step of (18) we used the definition of the cotype q constant C_{∥·∥}^{(q)}.

Using the notation of Lemma 3.1, fix i ∈ {1, …, m} and for every j ∈ {1, …, ⌈ϕθn/9⌉} write

P_{i}^{j} =^{def} Prob [⟨e_{π_{i}(j)} ⊗ e_{σ_{i}(j)} ⊗ e_{τ_{i}(j)}, f(ε)⟩ = δ_{i}^{j}ε_{i}] ,  (19)

where the probability in (19) is over ε ∈ {−1, 1}^{m} chosen uniformly at random. Recalling the definition of f, it follows from (12) that

∀(i, j) ∈ \{1, …, m\} × \{1, …, ⌈ϕθn/9⌉\}, P_{i}^{j} ⩾ \frac{1}{2} + \frac{θ}{16}.  (20)

Now, for every (i, j) ∈ {1, …, m} × {1, …, ⌈ϕθn/9⌉} we have

δ_{i}^{j} ⟨e_{π_{i}(j)} ⊗ e_{σ_{i}(j)} ⊗ e_{τ_{i}(j)}, f̂({i})⟩
= ⟨δ_{i}^{j}e_{π_{i}(j)} ⊗ e_{σ_{i}(j)} ⊗ e_{τ_{i}(j)}, 𝔼 [ε_{i}f(ε)]⟩
= 𝔼 [δ_{i}^{j}ε_{i} ⟨e_{π_{i}(j)} ⊗ e_{σ_{i}(j)} ⊗ e_{τ_{i}(j)}, f(ε)⟩]
=^{(19)} P_{i}^{j} − (1 − P_{i}^{j}) ⩾^{(20)} \frac{θ}{8}.  (21)

Recalling (15), it follows from (21) that f̂({i}) ∈ S(θ/8, ϕθ/27) for all i ∈ {1, …, m}. The definition (16) therefore implies that

min_{i∈{1,...,m}} ∥f̂({i})∥ ⩾ S_{∥·∥}(θ/8, ϕθ/27),

which gives the desired estimate (17) due to (18). □

By substituting (4) into Theorem 3.2 we deduce that any seminorm on ℝ^{n} ⊗ ℝ^{n} ⊗ ℝ^{n} must obey the following nontrivial restriction.

Corollary 3.3. There exist universal constants α, β, c ∈ (0, 1) such that for every integer n > 15, if ∥ · ∥ is a seminorm on ℝ^{n} ⊗ ℝ^{n} ⊗ ℝ^{n} and q ∈ [2, ∞) then

\frac{C_{∥·∥}^{(q)} · O_{∥·∥}}{S_{∥·∥}(α, β)} ≳ \frac{1}{log n} · exp (\frac{c}{q} · \frac{(log log n)^{2}}{log log log n}) ,  (22)

Proof. By Efremenko’s bound (4) combined with Theorem 3.2, there exist universal constants α_{1}, β_{1}, c_{1} ∈ (0, 1) and a sequence of integers {n_{m}}_{m=3}^{∞} ⊆ ℕ satisfying

log log n_{m} ≍ \sqrt{log m log log m},  (23)

such that for every integer m ⩾ 3 and q ∈ [2, ∞), if | · | is a seminorm on ℝ^{3n_{m}} ⊗ ℝ^{3n_{m}} ⊗ ℝ^{3n_{m}} then

\frac{C_{|·|}^{(q)} · O_{|·|}}{S_{|·|}(α_{1}, β_{1})} ≳ \frac{m^{1/q}}{log n_{m}} ≳^{(23)} \frac{1}{log n_{m}} · exp (\frac{c_{1}}{q} · \frac{(log log n_{m})^{2}}{log log log n_{m}} ) . (24)

Due to (23), there is N_{0} ∈ ℕ such that if n ⩾ N_{0} then there exists an integer m ⩾ 3 for which

3 (1 − \frac{β_{1}}{7} ) n_{m} ⩽ n ⩽ 3n_{m}.  (25)

Observe that by adjusting the constant c, the desired asymptotic inequality (22) holds true if n ∈ (15, N_{0}). We may therefore assume that n ⩾ N_{0}, in which case we apply (24) to the trivial extension of ∥ · ∥ to a seminorm | · | on ℝ^{3n_{m}} ⊗ ℝ^{3n_{m}} ⊗ ℝ^{3n_{m}}, i.e., for every {a_{i,j,k}}_{i,j,k=1}^{3n_{m}} set

|∑_{i=1}^{3n_{m}} ∑_{j=1}^{3n_{m}} ∑_{k=1}^{3n_{m}} a_{i,j,k}e_{i} ⊗ e_{j} ⊗ e_{k}| =^{def} ∥∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} a_{i,j,k}e_{i} ⊗ e_{j} ⊗ e_{k}∥ .

Then C_{|·|}^{(q)} = C_{∥·∥}^{(q)} and O_{|·|} = O_{∥·∥}, and due to (25) we also have S_{|·|}(α_{1}, β_{1}) ⩾ S_{∥·∥}(α_{1}, β_{1}/2). The desired estimate (22) is therefore a consequence of (24). □

Due to the following simple lemma, Theorem 1.3 and Corollary 1.4 follow from Theorem 3.2 and Corollary 3.3, respectively.

Lemma 3.4. Fix n ∈ ℕ and α, β ∈ (0, 1). For K ∈ [1, ∞), if ∥ · ∥ is a K-tensor-symmetric norm on ℝ^{n} ⊗ ℝ^{n} ⊗ ℝ^{n} then

O_{∥·∥} ⩽ K ∥∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} e_{i} ⊗ e_{j} ⊗ e_{k}∥ .  (26)

and

S_{∥·∥}(α, β) ⩾ \frac{αβ}{K} ∥∑_{i=1}^{n} e_{i} ⊗ e_{i} ⊗ e_{i}∥ .  (27)

Proof. (26) is an immediate consequence of the definitions (6) and (14). Next, fix x ∈ S(α, β). Writing x = ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} a_{i,j,k}e_{i} ⊗ e_{j} ⊗ e_{k} for some {a_{i,j,k}}_{i,j,k=1}^{n} ⊆ ℝ, and recalling (15), there exist π, σ, τ ∈ S_{n} such that

∀ i ∈ {1, …, ⌈βn⌉} , |a_{π(i),σ(i),τ(i)}| ⩾ α.  (28)

For ε, δ, η ∈ {−1, 1}^{n} and ρ ∈ S_{n} define

x_{ε,δ,η}^{ρ} =^{def} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} ε_{i}δ_{j}s_{k}(ε, δ, η, ρ)a_{π∘ρ(i),σ∘ρ(j),τ∘ρ(k)}e_{i} ⊗ e_{j} ⊗ e_{k}, (29)

where

s_{k}(ε, δ, η, ρ) =^{def} \begin{cases}η_{k} & if ρ(k) > ⌈βn⌉, \\ ε_{k}δ_{k}sign(a_{π∘ρ(k),σ∘ρ(k),τ∘ρ(k)}) & otherwise. \end{cases}

Thus, if (ε, δ, η, ρ) ∈ {−1, 1}^{n} × {−1, 1}^{n} × {−1, 1}^{n} × S_{n} is chosen uniformly at random then

𝔼 [x_{ε,δ,η}^{ρ}] = \frac{∑_{i=1}^{⌈βn⌉} |a_{π(i),σ(i),τ(i)}|}{n} ∑_{j=1}^{n} e_{j} ⊗ e_{j} ⊗ e_{j}.  (30)

Consequently,

αβ ∥∑_{j=1}^{n} e_{j} ⊗ e_{j} ⊗ e_{j}∥ ⩽^{(28)∧(30)} ∥𝔼 [x_{ε,δ,η}^{ρ}]∥

⩽ 𝔼 [∥x_{ε,δ,η}^{ρ}∥] ⩽^{(6)∧(29)} K∥x∥. (31)

Recalling (16), the validity of (31) for all x ∈ S(α, β) implies (27). □

References

[1] F. Albiac and N. J. Kalton. Topics in Banach space theory, volume 233 of Graduate Texts in Mathematics. Springer, New York, 2006.

[2] A. Arias and J. D. Farmer. On the structure of tensor products of l_{p}-spaces. Pacific J. Math., 175(1):13–37, 1996.

[3] A. Beimel, Y. Ishai, E. Kushilevitz, and I. Orlov. Share conversion and private information retrieval. In Proc. 27th IEEE Conf. on Computational Complexity (CCC’12), pages 258–268, 2012.

[4] A. Ben-Aroya, O. Regev, and R. de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In 49th Annual IEEE Symposium on Foundations of Computer Science, pages

477–486, 2008. Available at http://arxiv.org/abs/0705.3806.

[5] J. Bourgain. New Banach space properties of the disc algebra and H^{∞}. Acta Math., 152(1-2):1–48, 1984.

[6] J. Bourgain. On martingales transforms in finite-dimensional lattices with an appendix on the K-convexity constant. Math. Nachr., 119:41–53, 1984.

[7] J. Bourgain and G. Pisier. A construction of L_{∞}-spaces and related Banach spaces. Bol. Soc. Brasil. Mat., 14(2):109–123, 1983.

[8] Q. Bu. Observations about the projective tensor product of Banach spaces. II. L^{p}(0, 1)ˆ⊗X, 1 < p < ∞. Quaest. Math., 25(2):209–227, 2002.

[9] Q. Bu and J. Diestel. Observations about the projective tensor product of Banach spaces. I. l^{p} ˆ⊗X, 1 < p < ∞. Quaest. Math., 24(4):519–533, 2001.

[10] Q. Bu and P. N. Dowling. Observations about the projective tensor product of Banach spaces. III. L^{p}[0, 1]ˆ⊗X, 1 < p < ∞. Quaest. Math., 25(3):303–310, 2002.

[11] J. Diestel, J. Fourie, and J. Swart. The projective tensor product. I. In Trends in Banach spaces and operator theory (Memphis, TN, 2001), volume 321 of Contemp. Math., pages 37–65. Amer. Math. Soc., Providence, RI, 2003.

[12] J. Diestel, J. H. Fourie, and J. Swart. The metric theory of tensor products. American Mathematical Society, Providence, RI, 2008. Grothendieck’s résumé revisited.

[13] K. Efremenko. 3-query locally decodable codes of subexponential length. In STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, pages 39–44. ACM, New York, 2009.

[14] V. Grolmusz. Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs. Combinatorica, 20(1):71–85, 2000.

[15] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

[16] J. Katz and L. Trevisan. On the efficiency of local decoding procedures for error-correcting codes. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 80–86 (electronic), New York, 2000. ACM.

[17] I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. J. Comput. System Sci., 69(3):395–420, 2004.

[18] D. R. Lewis. Duals of tensor products. In Banach spaces of analytic functions (Proc. Pelczynski Conf., Kent State Univ., Kent, Ohio, 1976), pages 57–66. Lecture Notes in Math., Vol. 604. Springer, Berlin, 1977.

[19] B. Maurey and G. Pisier. Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach. Studia Math., 58(1):45–90, 1976.

[20] G. Pisier. Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert. Ann. Sci. École Norm. Sup. (4), 13(1):23–43, 1980.

[21] G. Pisier. Counterexamples to a conjecture of Grothendieck. Acta Math., 151(3-4):181–208, 1983.

[22] G. Pisier. Factorization of operator valued analytic functions. Adv. Math., 93(1):61–125, 1992.

[23] G. Pisier. Random series of trace class operators. In Proceedings Cuarto CLAPEM Mexico 1990. Contribuciones en probabilidad y estadistica matematica, pages 29–42, 1992. Available at http://arxiv.org/abs/1103.2090.

[24] R. A. Ryan. Introduction to tensor products of Banach spaces. Springer Monographs in Mathematics. Springer-Verlag London Ltd., London, 2002.

[25] N. Tomczak-Jaegermann. The moduli of smoothness and convexity and the Rademacher averages of trace classes S_{p}(1 ⩽ p < ∞). Studia Math., 50:163– 182, 1974.

[26] L. Trevisan. Some applications of coding theory in computational complexity. In Complexity of computations and proofs, volume 13 of Quad. Mat., pages 347–424. Dept. Math., Seconda Univ. Napoli, Caserta, 2004.

[27] D. P. Woodruff. New lower bounds for general locally decodable codes. Electronic Colloquium on Computational Complexity (ECCC), 14(006), 2007.

[28] S. Yekhanin. Towards 3-query locally decodable codes of subexponential length. J. ACM, 55(1):Art. 1, 16, 2008.

[29] S. Yekhanin. Locally decodable codes. Found. Trends Theor. Comput. Sci., 7(1):1–117, 2011.

Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 SJ Amsterdam, The Netherlands

E-mail address: j.briet@cwi.nl

Courant Institute, New York University, 251 Mercer Street, New York NY 10012, USA

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

École normale supérieure, Département d’informatique, 45 rue d’Ulm, Paris, France

E-mail address: regev@di.ens.fr