Lacunary matrices

Asma Harcharras  Stefan Neuwirth  Krzysztof Oleszkiewicz

Abstract

We study unconditional subsequences of the canonical basis (e_{rc} ) of elementary matrices in the Schatten class S^{p}. They form the matrix counterpart to Rudin’s Λ(p) sets of integers in Fourier analysis. In the case of p an even integer, we find a sufficient condition in terms of trails on a bipartite graph. We also establish an optimal density condition and present a random construction of bipartite graphs. As a byproduct, we get a new proof for a theorem of Erdős on circuits in graphs.

1 Introduction

We study the following question on the Schatten class S^{p}.

(†) How many matrix coefficients of an operator x ∈ S^{p} must vanish so that the norm of x has a bounded variation if we change the sign of the remaining nonzero matrix coefficients?

Let C be the set of columns and R be the set of rows for coordinates in the matrix, in general two copies of ℕ. Let I ⊆ R × C be the set of matrix coordinates of the remaining nonzero matrix coefficients of x. Property (†) means that the subsequence (e_{rc})_{(r,c)∈I} of the canonical basis of elementary matrices is an unconditional basic sequence in S^{p}: I forms a σ(p) set in the terminology of [5, §4].

It is natural to wonder about the operator valued case, where the matrix coefficients are themselves operators in S^{p}. As the proof of our main result carries over to that case, we shall state it in the more general terms of complete σ(p) sets.

We show that for our purpose, a set of matrix entries I ⊆ R × C is best understood as a bipartite graph. Its two vertex classes are C and R, whose elements will respectively be termed “column vertices” and “row vertices”. Its edges join only row vertices r ∈ R with column vertices c ∈ C, this occurring exactly if (r, c) ∈ I.

We obtain a generic condition for σ(p) sets in the case of even p (Theorem 3.2) that generalises [5, Prop. 6.5]. These sets reveal in fact as a matrix counterpart to Rudin’s Λ(p) sets and we are able to transfer Rudin’s proof of [9, Theorem 4.5(b)] to a non-commutative context: his number r_{s}(E, n) is replaced by the numbers of Def. 2.4(b) and we count trails between given vertices instead of representations of an integer.

We also establish an upper bound for the intersection of a σ(p) set with a finite product set R′×C′ (Theorem 4.2): this is a matrix counterpart to Rudin’s [9, Theorem 3.5]. In terms of bipartite graphs, this intersection is the subgraph induced by the vertex subclasses C′ ⊆ C and R′ ⊆ R.

The bound of Theorem 4.2 provides together with Theorem 3.2 a generalisation of a theorem by Erdős [4, p. 33] on graphs without circuits of a given even length. In the last part of this article, we present a random construction of maximal σ(p) sets for even integers p.

Terminology. C is the set of columns and R is the set of rows, in general both indexed by ℕ. The set V of all vertices is their disjoint union R ⨿ C. An edge on V is a pair {v, w} ⊆ V. A graph on V is given by its set of edges E. A bipartite graph on V with vertex classes C and R has only edges {r, c} such that c ∈ C and r ∈ R and may therefore be described alternatively by the set I = { (r, c) ∈ R × C : {r, c} ∈ E }. A trail of length s in a graph is a sequence (v_{0}, …, v_{s}) of s + 1 vertices such that {v_{0}, v_{1}}, …, {v_{s−1} , v_{s}} are pairwise distinct edges of the graph. A trail is a path if its vertices are pairwise distinct. A circuit of length p in a graph is a sequence (v_{1}, …, v_{p}) of p vertices such that {v_{1}, v_{2}}, …, {v_{p−1} , v_{p}}, {v_{p}, v_{1}} are pairwise distinct edges of the graph. A circuit is a cycle if its vertices are pairwise distinct.

Notation. 𝕋 = { z ∈ ℂ : |z| = 1 }. Let q = (r, c) ∈ R × C. The transpose of q is q^{∗} = (c, r). The entry (elementary matrix) e_{q} = e_{rc} is the operator on ℓ_{2} that maps the cth basis vector on the rth basis vector and all other basis vectors on 0. The matrix coefficient at coordinate q of an operator x on ℓ_{2} is x_{q} = tr e_{q}^{∗}x and its matrix representation is (x_{q})_{q∈R×C} = ∑ _{q∈R×C} x_{q}e_{q}. The Schatten class S^{p}, 1 ⩽ p < ∞, is the space of those compact operators x on ℓ_{2} such that ∥x∥_{p}^{p} = tr|x|^{p} = tr(x^{∗}x)^{p/2} < ∞. For I ⊆ R × C, the entry space S_{I}^{p} is the space of those x ∈ S^{p} whose matrix representation is supported by I: x_{q} = 0 if q ∉ I. S_{I}^{p} is also the closed subspace of S^{p} spanned by (e_{q})_{q∈I} . The S^{p}-valued Schatten class S^{p}(S^{p}) is the space of those operators x from ℓ_{2} to S^{p} such that ∥x∥_{p}^{p} = tr(tr|x|^{p}) < ∞, where the inner trace is the S^{p}-valued analogue of the usual trace. The S^{p}-valued entry space S_{I}^{p}(S^{p}) is the closed subspace spanned by the x_{q}e_{q} with x_{q} ∈ S^{p} and q ∈ I: x_{q} = tr e_{q}^{∗}x is the operator coefficient of x at matrix coordinate q. Thus, for even integers p and x = (x_{q})_{q∈I} = ∑ _{q∈I} x_{q}e_{q} with x_{q} ∈ S^{p} and I finite,

∥x∥_{p}^{p} = ∑_{q_{1} ,...q_{p} ∈I} trx_{q_{1}}^{∗}x_{q_{2}} …x_{q_{p−1}}^{∗} x_{q_{p}} tr e_{q_{1}}^{∗} e_{q_{2}} … e_{q_{p−1}}^{∗} e_{q_{p}}.

A Schur multiplier T on S_{I}^{p} associated to (μ_{q})_{q∈I} ∈ ℂ^{I} is a bounded operator on S_{I}^{p} such that T e_{q} = μ_{q}e_{q} for q ∈ I. T is furthermore completely bounded (c.b. for short) if T is bounded as the operator on S_{I}^{p}(S^{p}) defined by T (x_{q}e_{q}) = μ_{q}x_{q}e_{q} for x_{q} ∈ S^{p} and q ∈ I.

We shall stick to this harmonic analysis type notation; let us nevertheless show how these objects are termed with tensor products: S^{p}(S^{p}) is also S^{p}(ℓ_{2} ⊗_{2} ℓ_{2}) endowed with ∥x∥_{p}^{p} = tr⊗ tr|x|^{p}; one should write x_{q}⊗ e_{q} instead of x_{q}e_{q}; here x_{q} = Id_{S^{p}} ⊗tr((Id_{ℓ_{2}} ⊗ e_{q}^{∗})x); T is c.b. if Id_{S^{p}} ⊗T is bounded on S^{p}(ℓ_{2} ⊗_{2} ℓ_{2}).

Acknowledgement. The first-named and last-named authors undertook this research at the Équipe d’Analyse de l’Université Paris 6. It is their pleasure to acknowledge its kind hospitality.

2 Definitions

We use the notion of unconditionality in order to define the matrix analogue of Rudin’s “commutative” Λ(p) sets.

Definition 2.1. Let X be a Banach space. The sequence (y_{n}) ⊆ X is an unconditional basic sequence in X if there is a constant D such that

∥∑ ϑ_{n}c_{n}y_{n} ∥_{X} ⩽ D∥∑ c_{n}y_{n} ∥_{X}

for every real (vs. complex) choice of signs ϑ_{n} ∈ {−1, 1} (vs. ϑ_{n} ∈ 𝕋) and every finitely supported sequence of scalar coefficients (c_{n}). The optimal D is the real (vs. complex) unconditionality constant of (y_{n}) in X.

Real and complex unconditionality are isomorphically equivalent: the complex unconditionality constant is at most π/2 times the real one. The notions of unconditionality and multipliers are intimately connected: we have

Proposition 2.2. Let (y_{n}) ⊆ X be an unconditional basic sequence in X and let Y be the closed subspace of X spanned by (y_{n}). The real (vs. complex) unconditionality constant of (y_{n}) in X is exactly the least upper bound for the norms ∥T ∥_{ℒ (Y)} , where T is the multiplication operator defined by T y_{n} = μ_{n}y_{n}, and the μ_{n} range over all real (vs. complex) numbers with |μ_{n}| ⩽ 1.

Let us encompass the notions proposed in Question (†).

Definition 2.3. Let I ⊆ R × C and p > 2.

(a) [5, Def. 4.1] I is a σ(p) set if (e_{q})_{q∈I} is an unconditional basic sequence in S^{p}. This amounts to the uniform boundedness of the family of all relative Schur multipliers by signs

T_{ϑ} : S_{I}^{p} → S_{I}^{p}, x = (x_{q})_{q∈I} ↦ T_{ϑ}x = (ϑ_{q}x_{q})_{q∈I} with ϑ_{q} ∈ {−1, 1}.  (1)

By [5, Lemma 0.5], this means that there is a constant D such that for every finitely supported operator x = (x_{q})_{q∈I} = ∑ _{q∈I} x_{q}e_{q} with x_{q} ∈ ℂ

D^{−1} ∥x∥_{p} ⩽ |||x|||_{p} ⩽ ∥x∥_{p},  (2)

where the second inequality is a convexity inequality that is always satisfied (see [10, Theorem 8.9]) and

|||x|||_{p}^{p} = ∑_{c} ( ∑_{r} |x_{rc}|^{2})^{p/2} ∨ ∑_{r} ( ∑_{c} |x_{rc}|^{2})^{p/2}.  (3)

(b) [5, Def. 4.4] I is a complete σ(p) set if the family of all relative Schur multipliers by signs (1) is uniformly c.b. By [5, Lemma 0.5], I is completely σ(p) if and only if there is a constant D such that for every finitely supported operator valued operator x = (x_{q})_{q∈I} = ∑ _{q∈I} x_{q}e_{q} with x_{q} ∈ S^{p}

D^{−1} ∥x∥_{p} ⩽ |||x|||_{p} ⩽ ∥x∥_{p},  (4)

where the second inequality is a convexity inequality that is always satisfied and

|||x|||_{p}^{p} = ∑_{c} ∥( ∑_{r} x_{rc}^{∗}x_{rc})^{1/2} ∥_{p}^{p} ∨ ∑_{r} ∥( ∑_{c} x_{rc}x_{rc}^{∗})^{1/2} ∥_{p}^{p}.

The notion of a complete σ(p) set is stronger than that of a σ(p) set: Inequality (2) amounts to Inequality (4) tested on operators of the type x = ∑ _{q∈I} x_{q}e_{q} with each x_{q} acting on the same one-dimensional subspace of ℓ_{2}. It is an important open problem to decide whether the notions differ. An affirmative answer would solve Pisier’s conjecture about completely bounded Schur multipliers [8, p. 113].

Notorious examples of 1-unconditional basic sequences in all Schatten classes S^{p} are single columns, single rows, single diagonals and single anti-diagonals — and more generally “column sets” (vs. “row sets”) I such that for each (r, c) ∈ I, no other element of I is in the column c (vs. row r). These sets are called sections in [11, Def. 4.3]

We shall try to express these notions in terms of trails on bipartite graphs. We proceed as announced in the Introduction: then each example above is a union of disjoint star graphs in which one vertex of one class is connected to some vertices of the other class: trails in a star graph have at most length 2.

Definition 2.4. Let I ⊆ R × C and s ⩾ 1 an integer. We consider I as a bipartite graph: its vertex set is V = R ⨿ C and its edge set is E = { {r, c} ⊆ V : (r, c) ∈ I }.

(a) The sets of trails of length s on the graph I from the column (vs. row) vertex v_{0} to the vertex v_{s} are respectively

𝒞^{s}(I; v_{0}, v_{s}) = { (v_{0}, …, v_{s}) ∈ V^{s+1} : v_{0} ∈ C & all {v_{i}, v_{i+1} } ∈ E are distinct},

ℛ^{s}(I; v_{0}, v_{s}) = { (v_{0}, …, v_{s}) ∈ V^{s+1} : v_{0} ∈ R & all {v_{i}, v_{i+1} } ∈ E are distinct}.

(b) We define the Rudin numbers of trails starting respectively with a column vertex and a row vertex by c_{s}(I; v_{0}, v_{s}) = #𝒞^{s}(I; v_{0}, v_{s}) and r_{s}(I; v_{0}, v_{s}) = #ℛ^{s}(I; v_{0}, v_{s}).

Remark 2.5. In other words, for an integer l ⩾ 1,

c_{2l−1} (I; v_{0}, v_{2l−1} ) = # \left[{(r_{1}, c_{1}), (r_{1}, c_{2}), (r_{2}, c_{2}), (r_{2}, c_{3}), …, (r_{l}, c_{l}) \atop pairwise distinct in I : c_{1} = v_{0}, r_{l} = v_{2l−1}}\right]
c_{2l}(I; v_{0}, v_{2l}) = # \left[{(r_{1}, c_{1}), (r_{1}, c_{2}), …, (r_{l}, c_{l}), (r_{l}, c_{l+1} ) \atop pairwise distinct in I : c_{1} = v_{0}, c_{l+1} = v_{2l}}\right]

and similarly for r_{s}(I; v_{0}, v_{s}). If s is odd, then c_{s}(I; v_{0}, v_{s}) = r_{s}(I; v_{s}, v_{0}) for all (v_{0}, v_{s}) ∈ C × R. But if s is even, one Rudin number may be bounded while the other is infinite: see [5, Rem. 6.4(ii)].

3 σ(p) sets as matrix Λ(p) sets

We claim the following result.

Theorem 3.1. Let I ⊆ R × C and p = 2s be an even integer. If I is a union of sets I_{1}, …, I_{l} such that one of the Rudin numbers c_{s}(I_{j}; v_{0}, v_{s}) or r_{s}(I_{j}; v_{0}, v_{s}) is a bounded function of (v_{0}, v_{s}), for each j, then I is a complete σ(p) set.

This follows from Theorem 3.2 below: the union of two complete σ(p) sets is a complete σ(p) set by [5, Rem. after Def. 4.4]; furthermore the transposed set I^{∗} = { q^{∗} : q ∈ I } ⊆ C × R is a complete σ(p) set provided I is. Note that the case of σ(∞) sets (see [5, Rem. 4.6(iii)]) provides evidence that Theorem 3.1 might be a characterisation of complete σ(p) sets for even p.

Theorem 3.2. Let I ⊆ R × C and p = 2s be an even integer. If the Rudin number c_{s}(I; v_{0}, v_{s}) is a bounded function of (v_{0}, v_{s}), then I is a complete σ(p) set.

This is proved for p = 4 in [5, Prop. 6.5]. We wish to emphasise that the proof below follows the scheme of the proof of [5, Theorem 1.13]. In particular, we make crucial use of Pisier’s idea to express repetitions by dependent Rademacher variables ([5, Prop. 1.14]).

Proof. Let x = ∑ _{q∈I} x_{q}e_{q} with x_{q} ∈ S^{p}. We have the following expression for ∥x∥_{p}.

∥x∥_{p}^{p} = tr⊗ tr(x^{∗}x)^{s} = ∥y∥_{2}^{2} with y = \overbrace{x^{∗}xx^{∗} ⋯ x^{(∗)}}^{s terms},

i.e., y is the product of s terms which are alternatively x^{∗} and x, and we set x^{(∗)} = x for even s, x^{(∗)} = x^{∗} for odd s. Set C^{(∗)} = C for even s and C^{(∗)} = R for odd s. Let (v_{0}, v_{s}) ∈ C × C^{(∗)} and y_{v_{0} v_{s}} = tr e_{v_{0} v_{s}}^{∗} y be the matrix coefficient of y at coordinate (v_{0}, v_{s}). Then we obtain by the rule of matrix multiplication

y = ∑_{q_{1} ,...,q_{s} ∈I} (x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} )

y_{v_{0} v_{s}} = ∑_{(v_{1} ,v_{0} ), (v_{1} ,v_{2} ),... ∈I} x_{v_{1} v_{0}}^{∗} x_{v_{1} v_{2}} x_{v_{3} v_{2}}^{∗} …x(v_{s−1} ,v_{s} )^{(∗)}^{(∗)} .  (5)

Let ℰ be the set of equivalence relations on {1, …, s}. Then

y = ∑_{∼∈ℰ} ∑_{i∼j⇔q_{i} =q_{j}} (x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} ).  (6)

We shall bound the sum above in two steps.

(a) Let ∼ be equality and consider the corresponding term in the sum (6). The number of terms in the sum (5) such that {v_{i−1} , v_{i}} ≠ {v_{j−1} , v_{j} } if i ≠ j is c_{s}(I; v_{0}, v_{s}). If c is an upper bound for c_{s}(I; v_{0}, v_{s}), we have by the expression of the Hilbert–Schmidt norm and the Arithmetic-Quadratic Mean Inequality

∥ ∑_{q_{1} ,...,q_{s} pairwise distinct} (x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} )∥_{2}^{2}

= ∑_{(v_{0} ,v_{s} )∈C×C^{(∗)}}  ∥ ∑_{v∈𝒞^{s} (I;v_{0} ,v_{s} )} x_{v_{1} v_{0}}^{∗} x_{v_{1} v_{2}} x_{v_{3} v_{2}}^{∗} …x(v_{s−1} ,v_{s} )^{(∗)}^{(∗)} ∥_{2}^{2}

⩽ c ∑_{(v_{0} ,v_{s} )∈C×C^{(∗)}}  ∑_{v∈𝒞^{s} (I;v_{0} ,v_{s} )} ∥x_{v_{1} v_{0}}^{∗} x_{v_{1} v_{2}} x_{v_{3} v_{2}}^{∗} …x(v_{s−1} ,v_{s} )^{(∗)}^{(∗)} ∥_{2}^{2}

= c ∑_{q_{1} ,...,q_{s} pairwise distinct} ∥(x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} )∥_{2}^{2}

⩽ c ∑_{q_{1} ,...,q_{s}} ∥(x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} )∥_{2}^{2}
= c∥ ∑_{q_{1} ,...,q_{s}} |(x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} )|^{2} ∥_{1}

Now this last expression may be bounded accordingly to [5, Cor. 0.9] by

c( ∥∑ (x_{q}^{∗}e_{q}^{∗})(x_{q}e_{q})∥_{s} ∨ ∥∑ (x_{q}e_{q})(x_{q}^{∗}e_{q}^{∗})∥_{s})^{s} = c|||x|||_{p}^{p} :  (7)

see [5, Lemma 0.5] for the last equality.

(b) Let ∼ be distinct from equality. The corresponding term in the sum (6) cannot be bounded directly. Consider instead

Ψ(∼) = ∥ ∑_{i∼j⇒q_{i} =q_{j}} (x_{q_{1}}^{∗} e_{q_{1}}^{∗})(x_{q_{2}} e_{q_{2}}) …(xq_{s}^{(∗)} eq_{s}^{(∗)} )∥_{2} = ∥ ∑_{i∼j⇒q_{i} =q_{j}} ∏_{i=1}^{s} f_{i}(q_{i})∥_{2}

with f_{i}(q) = x_{q}e_{q} for even i and f_{i}(q) = x_{q}^{∗}e_{q}^{∗} for odd i. We may now apply Pisier’s Lemma [5, Prop. 1.14]: let 0 ⩽ r ⩽ s − 2 be the number of one element equivalence classes modulo ∼; then

Ψ(∼) ⩽ ∥x∥_{p}^{r}(B|||x|||_{p})^{s−r} ,  (8)

where B is the constant arising in Lust-Piquard’s non-commutative Khinchin inequality. In order to finish the proof, one does an induction on the number of atoms of the partition induced by ∼, along the lines of step 2 of the proof of [5, Theorem 1.13].

The Moebius inversion formula for partitions enabled Pisier [7] to obtain the following explicit bounds in the computation above:

∥y∥_{2} ⩽ c^{1/2} |||x|||_{p}^{s} + ∑_{0⩽r⩽s−2} \binom{s}{r} (s − r)!∥x∥_{p}^{r}((3π/4)|||x|||_{p})^{s−r}

∥x∥_{p} ⩽ ((4c)^{1/p} ∨ 9πp/8)|||x|||_{p}.  (9)

Let us also record the following consequence of his study of p-orthogonal sums. The family (x_{q}e_{q})_{q∈I} is p-orthogonal in the sense of [7] if and only if the graph associated to I does not contain any circuit of length p, so that we have by [7, Theorem 3.1]:

Theorem 3.3. Let p ⩾ 4 be an even integer. If I does not contain any circuit of length p, then I is a complete σ(p) set with constant at most 3πp/2.

Remark 3.4. Pisier proposed to us the following argument to deduce a weaker version of Theorem 3.2 from [5, Theorem 1.13]. Let Γ = 𝕋^{V} and z_{v} denote the vth coordinate function on Γ. Associate to I the set Λ = { z_{r}z_{c} : (r, c) ∈ I }. Let still p = 2s be an even integer. Then I is a complete σ(p) set if Λ is a complete Λ(p) set as defined in [5, Def. 1.5], which in turn holds if Λ has property Z(s) as given in [5, Def. 1.11]. It turns out that this condition implies the uniform boundedness of

c_{t}(I; v_{0}, v_{t}) ∨ r_{t}(I; v_{0}, v_{t}) for t ⩽ s, v_{0}, v_{t} ∈ V.

For p ⩾ 8, this implication is strict: in fact, the countable union of disjoint cycles of length 4 (“quadrilaterals”)

I = ⋃ _{i⩾0}{(2i, 2i), (2i, 2i + 1), (2i + 1, 2i + 1), (2i + 1, 2i)}

satisfies c_{t}(I; v_{0}, v_{t}) ∨ r_{t}(I; v_{0}, v_{t}) ⩽ 2 whereas Λ does not satisfy Z(s) for any s ⩾ 4.

Remark 3.5. Theorem 3.1 is especially useful to construct c.b. Schur multipliers: by [5, Rem. 4.6(ii)], if I is a complete σ(p) set, there is a constant D (the constant D in (4)) such that for every sequence (μ_{q}) ∈ ℂ^{R×C} supported by I and every operator T_{μ} : (x_{q}) ↦ (μ_{q}x_{q}) we have

∥T_{μ}∥_{ℒ (S^{p} (S^{p}))} ⩽ D sup_{q∈I}|μ_{q}|.

4 The intersection of a σ(p) set with a finite product set

Let I ⊆ R × C considered as a bipartite graph as in the Introduction and let I′ ⊆ I be the subgraph induced by the vertex set C′⨿ R′, with C′ ⊆ C a set of m column vertices and R′ ⊆ R a set of n row vertices. In other words, I′ = I ∩ R′× C′. Let d(v) be the degree of the vertex v ∈ C′⨿ R′ in I′: in other words,

∀c ∈ C′ d(c) = #[I′∩ R′× {c}],
∀r ∈ R′ d(r) = #[I′∩ {r} × C′].

Let us recall that the dual norm of (3) is

|||x|||_{p′} = inf_{\begin{matrix}α,β∈S^{p′} \\ α+β=x \end{matrix}} ( ∑_{c} ( ∑_{r} |α_{rc}|^{2})^{p′/2}) ^{1/p′} + ( ∑_{r} ( ∑_{c} |β_{rc}|^{2})^{p′/2}) ^{1/p′} ,

where p ⩾ 2 and 1/p + 1/p′ = 1 (see [5, Rem. after Lemma 0.5]).

Lemma 4.1. Let 1 ⩽ p′ ⩽ 2 and x = ∑ _{q∈I′} x_{q}. Then

|||x|||_{p′}^{p′} ⩾ ∑ ∑_{(r,c)∈I′} ( max(d(c), d(r))^{1/2−1/p′} |x_{rc}|)^{p′}.

Proof. By the p′-Quadratic Mean Inequality and by Minkowski’s Inequality,

( ∑_{c∈C′} ( ∑_{(r,c)∈I′} |α_{rc}|^{2})^{p′/2}) ^{1/p′} + ( ∑_{r∈R′} ( ∑_{(r,c)∈I′} |β_{rc}|^{2})^{p′/2}) ^{1/p′}

⩾ ( ∑_{c∈C′} d(c)^{p′/2−1} ∑_{(r,c)∈I′} |α_{rc}|^{p′})^{1/p′} + ( ∑_{r∈R′} d(r)^{p′/2−1} ∑_{(r,c)∈I′} |β_{rc}|^{p′})^{1/p′}

⩾ ( ∑ ∑_{(r,c)∈I′} (d(c)^{1/2−1/p′} |α_{rc}| + d(r)^{1/2−1/p′} |β_{rc}|)^{p′})^{1/p′}

The lemma follows by taking the infimum over all α, β with α_{q} + β_{q} = x_{q} for q ∈ I′ as one can suppose that α_{q} = β_{q} = 0 if q ∉ I; note further that 1/2 − 1/p′ ⩽ 0.

Theorem 4.2. If I is a σ(p) set with constant D as in (2), then the size #I′ of any subgraph I′ induced by m column vertices and n row vertices, in other words the cardinal of any subset I′ = I ∩ R′× C′ with #C′ = m and #R′ = n, satisfies

#I′ ⩽ D^{2}(m^{1/p}n^{1/2} + m^{1/2} n^{1/p})^{2}  (10)
⩽ 4D^{2} min(m, n)^{2/p} max(m, n).

The exponents in this inequality are optimal even for a complete σ(p) set I in the following cases: (a) if m or n is fixed;

(b) if p is an even integer and m = n.

Bound (10) holds a fortiori if I is a complete σ(p) set. Density conditions thus do not so far permit to distinguish σ(p) sets and complete σ(p) sets. One may conjecture that Inequality (10) is also optimal for p not an even integer and m = n: this would be a matrix counterpart to Bourgain’s theorem [3] on maximal Λ(p) sets.

Proof. If (2) holds, then ∥x|_{I′}∥_{p} ⩽ D|||x|||_{p} for all x ∈ S^{p} by Remark 3.5 applied to (μ_{q}) the indicator function of I′, and by duality |||x|_{I′}|||_{p′} ⩽ D∥x∥_{p′} for all x ∈ S^{p′} (compare with [5, Rem. 4.6(iv)]). Let

y = ∑ ∑_{(r,c)∈I′} d(c)^{1/p′−1/2} e_{rc},

z = ∑ ∑_{(r,c)∈I′} d(r)^{1/p′−1/2} e_{rc},

Then the n rows of y are all equal, as well as the m columns of z: y and z have rank 1 and a single singular value. By the norm inequality followed by the (2/p′− 1)-Arithmetic Mean Inequality,

∥y + z∥_{p′} ⩽ ∥y∥_{p′} + ∥z∥_{p′}
= n^{1/2} ( ∑_{c∈C′} d(c)^{2/p′−1} )^{1/2} + m^{1/2} ( ∑_{r∈R′} d(r)^{2/p′−1} )^{1/2}
⩽ n^{1/2} m^{1−1/p′} (#I′)^{1/p′−1/2} + m^{1/2} n^{1−1/p′} (#I′)^{1/p′−1/2} .

We used that ∑ _{c∈C′} d(c) = ∑ _{r∈R′} d(r) = #I′. By Lemma 4.1 applied to x = y + z,

(#I′)^{1/p′} ⩽ D(n^{1/2} m^{1−1/p′} + m^{1/2} n^{1−1/p′} )(#I′)^{1/p′−1/2} ,

and we get therefore the first part of the theorem.

Let us show optimality in the given cases.

(a) Suppose that n is fixed and C′ = C: I′ = R′× C is a complete σ(p) set for any p as a union of n rows and #I′ = n · m.

(b) is proved in [5, Theorem 4.8].

Remark 4.3. If n ≁ m, the method used in [5, Theorem 4.8] does not provide optimal σ(p) sets but the following lower bound. Let p = 2s with s ⩾ 2 an integer. Consider a prime q and let k = s^{s−1} q^{s}. By [9, 4.7] and [5, Theorem 2.5], there is a subset F ⊆ {0, …, k − 1} with q elements whose complete Λ(2s) constant is independent of q. Let m ⩾ k and 0 ⩽ n ⩽ m and consider the Hankel set

I = { (r, c) ∈ {0, …, n − 1} × {0, …, m − 1} : r + c ∈ F + m − k }.

Then the complete σ(p) constant of I is independent of q by [5, Prop. 4.7] and

#I ⩾ \{ \begin{matrix}nq & if n ⩽ m − k + 1 \\ (m − k + 1)q & if n ⩾ m − k + 1. \end{matrix}

If we choose m = (s + 1)k − 1, this yields

#I ⩾ \frac{s^{1/s}}{(s + 1)^{1+1/s}} min(n, m) max(m, n)^{1/s} .

Random construction 6.1 provides bigger sets than this deterministic construction; however, it also does not provide sets that would show the optimality of Inequality (10) unless s = 2.

5 Circuits in graphs

Non-commutative methods yield a new proof to a theorem of Erdős [4, p. 33]. Note that its generalisation by Bondy and Simonovits [2] is stronger than Theorem 5.1 below as it deals with cycles instead of circuits. By Theorem 3.3 and (10)

Theorem 5.1. Let p ⩾ 4 be an even integer. If G is a nonempty graph on v vertices with e edges without circuit of length p, then

e ⩽ 18π^{2}p^{2} v^{1+2/p} .

If G is furthermore a bipartite graph whose two vertex classes have respectively m and n elements, then

e ⩽ 9π^{2}p^{2} min(m, n)^{2/p} max(m, n).  (11)

Proof. For the first assertion, recall that a graph G with e edges contains a bipartite subgraph with more than e/2 edges (see [1, p. xvii]).

Remark 5.2. Łuczak showed to us that (11) cannot be optimal if m and n are of very different order of magnitude. In particular, let p be a multiple of 4. Let e′ be the maximal number of edges of a graph on n vertices without circuit of length p/2. If m > pe′, he shows that (11) may be replaced by e < 3m.

We also get the following result, which enables us to conjecture a generalisation of the theorems of Erdős and Bondy and Simonovits.

Theorem 5.3. Let G be a nonempty graph on v vertices with e edges. Let s ⩾ 2 be an integer.

(i) If

e > 8D^{2} v^{1+1/s} with D > 9πs/4,

then one may choose two vertices v_{0} and v_{s} such that G contains more than D^{2s} /4 pairwise distinct trails from v_{0} to v_{s}, each of length s and with pairwise distinct edges.

(ii) One may draw the same conclusion if G is a bipartite graph whose two vertex classes have respectively m and n elements and

e > 4D^{2} min(m, n)^{1/s} max(m, n) with D > 9πs/4.

Proof. (i) According to [1, p. xvii], the graph G contains a bipartite subgraph with more than e/2 edges, so that we may apply (ii).

(ii) Combining inequalities (9) and (10), if D > 9πs/4, then there are vertices v_{0} and v_{s} such that the number c of pairwise distinct trails from v_{0} to v_{s}, each of length s and with pairwise distinct edges, satisfies (4c)^{1/2s} > D.

Two paths with equal endvertices are called independent if they have only their endvertices in common.

Question 5.4. Let G be a graph on v vertices with e edges. Let s, l ⩾ 2 be integers. Is it so that there is a constant D such that if e > Dv^{1+1/s} , then G contains l pairwise independent paths of length s with equal endvertices?

Remark 5.5. Note that by Theorem 4.2, the exponent 1 + 1/s is optimal in Theorem 5.3(i), whereas optimality of the exponent 1 + 2/p in Theorem 5.1 is an important open question in Graph Theory (see [6]).

One may also formulate Theorem 5.3(ii) in the following way.

Theorem 5.6. If a bipartite graph G_{2}(n, m) with n and m vertices in its two classes avoids any union of c pairwise distinct trails along s pairwise distinct edges between two given vertices as a subgraph, where the class of the first vertex is fixed, then the size e of the graph satisfies

e ⩽ 4 max((4c)^{1/2s} , 9πs/4)) min(m, n)^{1/s} max(m, n).

6 A random construction of graphs

Let us precise our construction of a random graph.

Random construction 6.1. Let C, R be two sets such that #C = m and #R = n. Let 0 ⩽ α ⩽ 1. A random bipartite graph on V = C ⨿ R is defined by selecting independently each edge in E = { {r, c} ⊆ V : (r, c) ∈ R × C } with the same probability α. The resulting random edge set is denoted by E′ ⊆ E and I′ ⊆ R × C denotes the associated random subset.

Our aim is to construct large sets while keeping down the Rudin number c_{s}.

Theorem 6.2. For each ε > 0 and for each integer s ⩾ 2, there is an α such that Random construction 6.1 yields subsets I′ ⊆ R × C with size

#I′ ∼ min(m, n)^{1/2+1/s} max(m, n)^{1/2−ε}

and with σ(2s) constant independent of m and n for mn → ∞.

Proof. Let us suppose without loss of generality that m ⩾ n. We want to estimate the Rudin number of trails in I′. Set C^{(∗)} = C for even s, C^{(∗)} = R for odd s and let (v_{0}, v_{s}) ∈ C × C^{(∗)} . Let l ⩾ 1 be a fixed integer. Then

ℙ[c_{s}(I′; v_{0}, v_{s}) ⩾ l]= ℙ[∃ l distinct trails (v_{0}^{j}, …, v_{s}^{j}) in 𝒞^{s}(I′; v_{0}, v_{s})]

= ℙ[ E′ ⊇ {{v_{i−1}^{j} , v_{i}^{j} }}_{i,j} : {(v_{0}^{j}, …, v_{s}^{j})}_{j=1}^{l} ⊆ 𝒞^{s}(R × C; v_{0}, v_{s}) ]

⩽ ∑_{k=⌈l^{1/s} ⌉}^{ls} #A_{k} · α^{k},

where A_{k} is the following set of l-element subsets of trails in 𝒞^{s}(R × C; v_{0}, v_{s}) built with k pairwise distinct edges

A_{k} = { {(v_{0}^{j}, …, v_{s}^{j})}_{j=1}^{l} ⊆ 𝒞^{s}(R × C; v_{0}, v_{s}) : #{{v_{i−1}^{j} , v_{i}^{j} }}_{i,j} = k };

the lower limit of summation is ⌈l^{1/s} ⌉ because one can build at most k^{s} pairwise distinct trails of length s with k pairwise distinct edges.

In order to estimate #A_{k}, we now have to bound the number of pairwise distinct vertices and the number of pairwise distinct column vertices in each set of l trails {(v_{0}^{j}, …, v_{s}^{j})}_{j=1}^{l} ∈ A_{k}. We claim that

#{ v_{i}^{j} : 1 ⩽ i ⩽ s − 1, 1 ⩽ j ⩽ l } ⩽ k(s − 1)/s,  (12)
#{ v_{2i}^{j} : 1 ⩽ i ⩽ ⌈s/2⌉ − 1, 1 ⩽ j ⩽ l } ⩽ k/2.  (13)

The second estimate is trivial, because each column vertex v_{2i}^{j} accounts for two distinct edges {v_{2i−1}^{j} , v_{2i}^{j}} and {v_{2i}^{j}, v_{2i+1}^{j} }. For the first estimate, note that each maximal sequence of h consecutive pairwise distinct vertices (v_{a+1}^{j} , …, v_{a+h}^{j} ) accounts for h + 1 pairwise distinct edges

{v_{a}^{j}, v_{a+1}^{j} }, {v_{a+1}^{j} , v_{a+2}^{j} }, …, {v_{a+h}^{j} , v_{a+h+1}^{j} };

as h ⩽ s − 1, h + 1 ⩾ hs/(s − 1). By (12) and (13),

#A_{k} ⩽ m^{k/2} n^{k/2−k/s} (k − k/s)^{ls−l} ⩽ (ls)^{ls} m^{k/2} n^{k/2−k/s} :

each element of A_{k} is obtained by a choice of at most k − k/s vertices, of which at most k/2 are column vertices, and the choice of an arrangement with repetitions of ls − l out of at most k − k/s vertices.

Put α = m^{−1/2} n^{−1/2+1/s} (#C · #C^{(∗)} )^{−ε} . Then

ℙ[ sup_{(v_{0} ,v_{s} )} c_{s}(I′; v_{0}, v_{s}) ⩾ l] ⩽ #C · #C^{(∗)} · (ls)^{ls} ∑_{k=⌈l^{1/s} ⌉}^{ls} (#C · #C^{(∗)} )^{−kε}

⩽ (ls)^{ls} \frac{(#C · #C^{(∗)} )^{1−⌈l^{1/s} ⌉ε}}{1 − (#C · #C^{(∗)} )^{−ε}} .

Choose l such that ⌈l^{1/s} ⌉ε > 1. Then this probability is little for mn large. On the other hand, #I′ is of order mnα with probability close to 1.

Remark 6.3. This construction yields much better results for s = 2. Keeping the notation of the proof above and m ⩾ n, we get k = 2l, A_{k} = \binom{n}{l} and

ℙ[ sup_{(v_{0} ,v_{2} )∈C×C} c_{2}(I′; v_{0}, v_{2}) ⩾ l] ⩽ m^{2} \binom{n}{l} α^{2l}.

Let l ⩾ 2 and α = m^{−1/l} n^{−1/2} . This yields sets I′ ⊆ R × C with size

#I′ ∼ n^{1/2} m^{1−1/l}

and with σ(4) constant independent of m and n. This case has been extensively studied in Graph theory as the “Zarankiewicz problem:” if c_{2}(I′; v_{0}, v_{2}) ⩽ l for all v_{0}, v_{2} ∈ C, then the graph I′ does not contain a complete bipartite subgraph on any two column vertices v_{0}, v_{2} and l + 1 row vertices. Reiman (see [1, Theorem VI.2.6]) showed that then

#I′ ⩽ (lnm(m − 1) + n^{2}/4)^{1/2} + n/2 ∼ l^{1/2} n^{1/2} m.

With use of finite projective geometries, he also showed that this bound is optimal for

n = l \frac{q^{r+1} − 1}{q^{2} − 1} \frac{q^{r} − 1}{q − 1} , m = \frac{q^{r+1} − 1}{q − 1}

with q a prime power and r ⩾ 2 an integer, and thus with m ⩽ n: there seems to be no constructive example of extremal graphs with c_{2}(I′; v_{0}, v_{2}) ⩽ l and m > n besides the trivial case of complete bipartite graphs with m > n = l − 1.

Remark 6.4. In the case s = 3, our result cannot be improved just by refining the estimation of #A_{k}. If we consider first l distinct paths that have their second vertex in common and then l independent paths, we get

#A_{2l+1} ⩾ \binom{m}{l} n , #A_{3l} ⩾ \binom{m}{l} \binom{n}{l} .

Therefore any choice of α as a monomial m^{−t} n^{−u} in the proof above must satisfy t ⩾ (l + 1)/(2l + 1), t + u ⩾ (2l + 2)/(3l) and this yields sets with

#I′ ≼ m^{1/2−1/2(4l+2)} n^{5/6−(7l+6)/(12l^{2} +6l)} .

Bibliography

[1] Béla Bollobás. Extremal graph theory. Academic Press, 1978. (pp. 7, 8, and 10).

[2] J. A. Bondy and M. Simonovits. Cycles of even length in graphs. J. Combin. Theory Ser. B, 16:97–105, 1974. (p. 7).

[3] J. Bourgain. Bounded orthogonal systems and the Λ(p)-set problem. Acta Math., 162(3-4):227– 245, 1989. (p. 6).

[4] Paul Erdős. Extremal problems in graph theory. In Theory of Graphs and its Applications (Smolenice, 1963), pages 29–36. Publ. House Czechoslovak Acad. Sci., 1964. (pp. 1 and 7).

[5] Asma Harcharras. Fourier analysis, Schur multipliers on S^{p} and non-commutative Λ(p)-sets. Studia Math., 137(3):203–260, 1999. (pp. 1, 3, 4, 5, 6, and 7).

[6] Felix Lazebnik, Vasiliy A. Ustimenko, and Andrew J. Woldar. Polarities and 2k-cycle-free graphs. Discrete Math., 197/198:503–513, 1999. (p. 8).

[7] Gilles Pisier. An inequality for p-orthogonal sums in non-commutative L_{p}. Illinois J. Math., 44(4):901–923, 2000. (p. 5).

[8] Gilles Pisier. Similarity problems and completely bounded maps, volume 1618 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, expanded edition, 2001. Includes the solution to “The Halmos problem”. (p. 3).

[9] Walter Rudin. Trigonometric series with gaps. J. Math. Mech., 9:203–228, 1960. (pp. 1 and 7).

[10] Barry Simon. Trace ideals and their applications. Cambridge University Press, 1979. (p. 3).

[11] Nicholas Varopoulos. Tensor algebras over discrete spaces. J. Functional Analysis, 3:321–335, 1969. (p. 3).