Lacunary matrices

Asma Harcharras, Stefan Neuwirth, Krzysztof Oleszkiewicz

► To cite this version:

Asma Harcharras, Stefan Neuwirth, Krzysztof Oleszkiewicz. Lacunary matrices. Indiana University Mathematics Journal, 2001, 50 (4), pp.1675-1690. 10.1512/iumj.2001.50.1952. hal-05519611

HAL Id: hal-05519611

https://hal.science/hal-05519611v1

Submitted on 4 Mar 2026

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# 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 $\Lambda(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 \in 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 $\mathbb{N}$. Let $I \subseteq R \times C$ be the set of matrix coordinates of the remaining nonzero matrix coefficients of $x$. Property (†) means that the subsequence $(e_{rc})_{(r,c) \in I}$ of the canonical basis of elementary matrices is an unconditional basic sequence in $S^p$: $I$ forms a $\sigma(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 $\sigma(p)$ sets.

We show that for our purpose, a set of matrix entries $I \subseteq R \times 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 \in R$ with column vertices $c \in C$, this occurring exactly if $(r, c) \in I$.

We obtain a generic condition for $\sigma(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 $\Lambda(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 $\sigma(p)$ set with a finite product set $R' \times 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' \subseteq C$ and $R' \subseteq 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 $\sigma(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 $\mathbb{N}$. The set $V$ of all vertices is their disjoint union $R \amalg C$. An edge on $V$ is a pair $\{v, w\} \subseteq 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 \in C$ and $r \in R$ and may therefore be described alternatively by the set $I = \{(r, c) \in R \times C : \{r, c\} \in E\}$. A trail of length $s$ in a graph is a sequence $(v_0, \dots, v_s)$ of $s+1$ vertices such that $\{v_0, v_1\}, \dots, \{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, \dots, v_p)$ of $p$ vertices such that $\{v_1, v_2\}, \dots, \{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.** $\mathbb{T} = \{z \in \mathbb{C} : |z| = 1\}$. Let $q = (r, c) \in \mathbb{R} \times \mathbb{C}$. The transpose of $q$ is $q^* = (c, r)$. The entry (elementary matrix) $e_q = e_{rc}$ is the operator on $\ell_2$ that maps the $c$th basis vector on the $r$th basis vector and all other basis vectors on 0. The matrix coefficient at coordinate $q$ of an operator $x$ on $\ell_2$ is $x_q = \text{tr} e_q^* x$ and its matrix representation is $(x_q)_{q \in \mathbb{R} \times \mathbb{C}} = \sum_{q \in \mathbb{R} \times \mathbb{C}} x_q e_q$. The Schatten class $S^p$, $1 \le p < \infty$, is the space of those compact operators $x$ on $\ell_2$ such that $\|x\|_p^p = \text{tr}|x|^p = \text{tr}(x^*x)^{p/2} < \infty$. For $I \subseteq \mathbb{R} \times \mathbb{C}$, the entry space $S_I^p$ is the space of those $x \in S^p$ whose matrix representation is supported by $I$: $x_q = 0$ if $q \notin I$. $S_I^p$ is also the closed subspace of $S^p$ spanned by $(e_q)_{q \in I}$. The $S^p$-valued Schatten class $S^p(S^p)$ is the space of those operators $x$ from $\ell_2$ to $S^p$ such that $\|x\|_p^p = \text{tr}(\text{tr}|x|^p) < \infty$, 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 \in S^p$ and $q \in I$: $x_q = \text{tr} e_q^* x$ is the operator coefficient of $x$ at matrix coordinate $q$. Thus, for even integers $p$ and $x = (x_q)_{q \in I} = \sum_{q \in I} x_q e_q$ with $x_q \in S^p$ and $I$ finite,

$$ \|x\|_p^p = \sum_{q_1, \dots, q_p \in I} \text{tr} x_{q_1}^* x_{q_2} \dots x_{q_{p-1}}^* x_{q_p} \text{tr} e_{q_1}^* e_{q_2} \dots e_{q_{p-1}}^* e_{q_p}. $$

A Schur multiplier $T$ on $S_I^p$ associated to $(\mu_q)_{q \in I} \in \mathbb{C}^I$ is a bounded operator on $S_I^p$ such that $Te_q = \mu_q e_q$ for $q \in 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) = \mu_q x_q e_q$ for $x_q \in S^p$ and $q \in 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(\ell_2 \otimes_2 \ell_2)$ endowed with $\|x\|_p^p = \text{tr} \otimes \text{tr}|x|^p$; one should write $x_q \otimes e_q$ instead of $x_q e_q$; here $x_q = \text{Id}_{S^p} \otimes \text{tr}((\text{Id}_{\ell_2} \otimes e_q^*)x)$; $T$ is c.b. if $\text{Id}_{S^p} \otimes T$ is bounded on $S^p(\ell_2 \otimes_2 \ell_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” $\Lambda(p)$ sets.

**Definition 2.1.** Let $X$ be a Banach space. The sequence $(y_n) \subseteq X$ is an unconditional basic sequence in $X$ if there is a constant $D$ such that

$$ \left\| \sum \vartheta_n c_n y_n \right\|_X \le D \left\| \sum c_n y_n \right\|_X $$

for every real (vs. complex) choice of signs $\vartheta_n \in \{-1, 1\}$ (vs. $\vartheta_n \in \mathbb{T}$) 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 $\pi/2$ times the real one. The notions of unconditionality and multipliers are intimately connected: we have

**Proposition 2.2.** Let $(y_n) \subseteq 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\|_{\mathcal{L}(Y)}$, where $T$ is the multiplication operator defined by $Ty_n = \mu_n y_n$, and the $\mu_n$ range over all real (vs. complex) numbers with $|\mu_n| \le 1$.

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

**Definition 2.3.** Let $I \subseteq \mathbb{R} \times \mathbb{C}$ and $p > 2$.
(a) [5, Def. 4.1] $I$ is a $\sigma(p)$ set if $(e_q)_{q \in 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_{\vartheta}: S_I^p \to S_I^p, x = (x_q)_{q \in I} \mapsto T_{\vartheta}x = (\vartheta_q x_q)_{q \in I} \text{ with } \vartheta_q \in \{-1, 1\}. \quad (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 \in I} = \sum_{q \in I} x_q e_q$ with $x_q \in \mathbb{C}$

$$D^{-1} \|x\|_p \le \|x\|_p \le \|x\|_p, \quad (2)$$

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

$$\|x\|_p^p = \sum_c \left( \sum_r |x_{rc}|^2 \right)^{p/2} \lor \sum_r \left( \sum_c |x_{rc}|^2 \right)^{p/2}. \quad (3)$$

(b) [5, Def. 4.4] $I$ is a complete $\sigma(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 $\sigma(p)$ if and only if there is a constant $D$ such that for every finitely supported operator valued operator $x = (x_q)_{q \in I} = \sum_{q \in I} x_q e_q$ with $x_q \in S^p$

$$D^{-1} \|x\|_p \le \|x\|_p \le \|x\|_p, \quad (4)$$

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

$$\|x\|_p^p = \sum_c \left\| \left( \sum_r x_{rc}^* x_{rc} \right)^{1/2} \right\|_p^p \lor \sum_r \left\| \left( \sum_c x_{rc} x_{rc}^* \right)^{1/2} \right\|_p^p.$$

The notion of a complete $\sigma(p)$ set is stronger than that of a $\sigma(p)$ set: Inequality (2) amounts to Inequality (4) tested on operators of the type $x = \sum_{q \in I} x_q e_q$ with each $x_q$ acting on the same one-dimensional subspace of $\ell_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) \in 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 \subseteq \mathbb{R} \times \mathbb{C}$ and $s \ge 1$ an integer. We consider $I$ as a bipartite graph: its vertex set is $V = \mathbb{R} \amalg \mathbb{C}$ and its edge set is $E = \{(r, c) \subseteq V : (r, c) \in 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

$$\mathcal{C}^s(I; v_0, v_s) = \{(v_0, \dots, v_s) \in V^{s+1} : v_0 \in \mathbb{C} \text{ & all } \{v_i, v_{i+1}\} \in E \text{ are distinct}\},$$

$$\mathcal{R}^s(I; v_0, v_s) = \{(v_0, \dots, v_s) \in V^{s+1} : v_0 \in \mathbb{R} \text{ & all } \{v_i, v_{i+1}\} \in E \text{ 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) = \#\mathcal{C}^s(I; v_0, v_s)$ and $r_s(I; v_0, v_s) = \#\mathcal{R}^s(I; v_0, v_s)$.

**Remark 2.5.** In other words, for an integer $l \ge 1$,

$$c_{2l-1}(I; v_0, v_{2l-1}) = \# \left[ \begin{array}{l} (r_1, c_1), (r_1, c_2), (r_2, c_2), (r_2, c_3), \dots, (r_l, c_l) \\ \text{pairwise distinct in } I : c_1 = v_0, r_l = v_{2l-1} \end{array} \right]$$

$$c_{2l}(I; v_0, v_{2l}) = \# \left[ \begin{array}{l} (r_1, c_1), (r_1, c_2), \dots, (r_l, c_l), (r_l, c_{l+1}) \\ \text{pairwise distinct in } I : c_1 = v_0, c_{l+1} = v_{2l} \end{array} \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) \in \mathbb{C} \times \mathbb{R}$. But if $s$ is even, one Rudin number may be bounded while the other is infinite: see [5, Rem. 6.4(ii)].
### 3 $\sigma(p)$ sets as matrix $\Lambda(p)$ sets

We claim the following result.

**Theorem 3.1.** Let $I \subseteq R \times C$ and $p = 2s$ be an even integer. If $I$ is a union of sets $I_1, \dots, 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 $\sigma(p)$ set.

This follows from Theorem 3.2 below: the union of two complete $\sigma(p)$ sets is a complete $\sigma(p)$ set by [5, Rem. after Def. 4.4]; furthermore the transposed set $I^* = \{q^*: q \in I\} \subseteq C \times R$ is a complete $\sigma(p)$ set provided $I$ is. Note that the case of $\sigma(\infty)$ sets (see [5, Rem. 4.6(iii)]) provides evidence that Theorem 3.1 might be a characterisation of complete $\sigma(p)$ sets for even $p$.

**Theorem 3.2.** Let $I \subseteq R \times 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 $\sigma(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 = \sum_{q \in I} x_q e_q$ with $x_q \in S^p$. We have the following expression for $\|x\|_p$.

$$ \|x\|_p^p = \operatorname{tr} \otimes \operatorname{tr}(x^*x)^s = \|y\|_2^2 \quad \text{with} \quad y = \overbrace{x^*x x^* \cdots x^{(*)}}^{s \text{ 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) \in C \times C^{(*)}$ and $y_{v_0v_s} = \operatorname{tr} e_{v_0v_s}^* y$ be the matrix coefficient of $y$ at coordinate $(v_0, v_s)$. Then we obtain by the rule of matrix multiplication

$$ \begin{aligned} y &= \sum_{q_1, \dots, q_s \in I} (x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)}) \\ y_{v_0 v_s} &= \sum_{(v_1, v_0), (v_1, v_2), \dots \in I} x_{v_1 v_0}^* x_{v_1 v_2} x_{v_2 v_3}^* \dots x_{(v_{s-1}, v_s)_{(s)}}^* \end{aligned} \quad (5) $$

Let $\mathcal{E}$ be the set of equivalence relations on $\{1, \dots, s\}$. Then

$$ y = \sum_{\sim \in \mathcal{E}} \sum_{i \sim j \Leftrightarrow q_i = q_j} (x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)}). \quad (6) $$

We shall bound the sum above in two steps.

(a) Let $\sim$ 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\} \neq \{v_{j-1}, v_j\}$ if $i \neq 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

$$ \begin{aligned} & \left\| \sum_{\substack{q_1, \dots, q_s \\ \text{pairwise distinct}}} (x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)}) \right\|_2^2 \\ &= \sum_{(v_0, v_s) \in C \times C^{(*)}} \left\| \sum_{v \in \mathcal{C}^s(I; v_0, v_s)} x_{v_1 v_0}^* x_{v_1 v_2} x_{v_2 v_3}^* \dots x_{(v_{s-1}, v_s)_{(s)}}^{(*)} \right\|_2^2 \\ &\le c \sum_{(v_0, v_s) \in C \times C^{(*)}} \sum_{v \in \mathcal{C}^s(I; v_0, v_s)} \left\| x_{v_1 v_0}^* x_{v_1 v_2} x_{v_2 v_3}^* \dots x_{(v_{s-1}, v_s)_{(s)}}^{(*)} \right\|_2^2 \\ &= c \sum_{\substack{q_1, \dots, q_s \\ \text{pairwise distinct}}} \left\| (x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)}) \right\|_2^2 \\ &\le c \sum_{\substack{q_1, \dots, q_s \\ \text{pairwise distinct}}} \left\| (x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)}) \right\|_2^2 \\ &= c \left\| \sum_{\substack{q_1, \dots, q_s \\ \text{pairwise distinct}}} |(x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)})|^2 \right\|_1 \end{aligned} $$
Now this last expression may be bounded accordingly to [5, Cor. 0.9] by

$$c\left(\left\|\sum (x_q^* e_q^*)(x_q e_q)\right\|_s \vee \left\|\sum (x_q e_q)(x_q^* e_q^*)\right\|_s\right)^s = c\|x\|_p^p: \quad (7)$$

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

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

$$\Psi(\sim) = \left\| \sum_{i \sim j \Rightarrow q_i = q_j} (x_{q_1}^* e_{q_1}^*)(x_{q_2} e_{q_2}) \dots (x_{q_s}^{(*)} e_{q_s}^{(*)}) \right\|_2 = \left\| \sum_{i \sim j \Rightarrow q_i = q_j} \prod_{i=1}^s f_i(q_i) \right\|_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 \le r \le s - 2$ be the number of one element equivalence classes modulo $\sim$; then

$$\Psi(\sim) \le \|x\|_p^r (B \|x\|_p)^{s-r}, \quad (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 $\sim$, 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 \le c^{1/2} \|x\|_p^s + \sum_{0 \le r \le s-2} \binom{s}{r} (s-r)! \|x\|_p^r \left(\left(\frac{3\pi}{4}\right) \|x\|_p\right)^{s-r} \\ \|x\|_p \le \left(\left(\frac{4c}{p}\right)^{1/p} \vee \frac{9\pi p}{8}\right) \|x\|_p. \quad (9)$$

Let us also record the following consequence of his study of $p$-orthogonal sums. The family $(x_q e_q)_{q \in 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 \ge 4$ be an even integer. If $I$ does not contain any circuit of length $p$, then $I$ is a complete $\sigma(p)$ set with constant at most $3\pi 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 $\Gamma = \mathbb{T}^V$ and $z_v$ denote the $v$th coordinate function on $\Gamma$. Associate to $I$ the set $\Lambda = \{z_r z_c : (r, c) \in I\}$. Let still $p = 2s$ be an even integer. Then $I$ is a complete $\sigma(p)$ set if $\Lambda$ is a complete $\Lambda(p)$ set as defined in [5, Def. 1.5], which in turn holds if $\Lambda$ 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) \vee r_t(I; v_0, v_t) \text{ for } t \le s, v_0, v_t \in V.$$

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

$$I = \bigcup_{i \ge 0} \{(2i, 2i), (2i, 2i+1), (2i+1, 2i+1), (2i+1, 2i)\}$$

satisfies $c_t(I; v_0, v_t) \vee r_t(I; v_0, v_t) \le 2$ whereas $\Lambda$ does not satisfy $Z(s)$ for any $s \ge 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 $\sigma(p)$ set, there is a constant $D$ (the constant $D$ in (4)) such that for every sequence $(\mu_q) \in \mathbb{C}^{R \times C}$ supported by $I$ and every operator $T_\mu : (x_q) \mapsto (\mu_q x_q)$ we have

$$\|T_\mu\|_{\mathcal{L}(S^p(S^p))} \le D \sup_{q \in I} |\mu_q|.$$
## 4 The intersection of a $\sigma(p)$ set with a finite product set

Let $I \subseteq R \times C$ considered as a bipartite graph as in the Introduction and let $I' \subseteq I$ be the subgraph induced by the vertex set $C' \cap R'$, with $C' \subseteq C$ a set of $m$ column vertices and $R' \subseteq R$ a set of $n$ row vertices. In other words, $I' = I \cap R' \times C'$. Let $d(v)$ be the degree of the vertex $v \in C' \cap R'$ in $I'$: in other words,

$$ \forall c \in C' \quad d(c) = \#[I' \cap R' \times \{c\}], $$

$$ \forall r \in R' \quad d(r) = \#[I' \cap \{r\} \times C'], $$

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

$$ \|x\|_{p'} = \inf_{\substack{\alpha, \beta \in S^{p'} \\ \alpha + \beta = x}} \left( \sum_c \left( \sum_r |\alpha_{rc}|^2 \right)^{p'/2} \right)^{1/p'} + \left( \sum_r \left( \sum_c |\beta_{rc}|^2 \right)^{p'/2} \right)^{1/p'}, $$

where $p \ge 2$ and $1/p + 1/p' = 1$ (see [5, Rem. after Lemma 0.5]).

**Lemma 4.1.** Let $1 \le p' \le 2$ and $x = \sum_{q \in I'} x_q$. Then

$$ \|x\|_{p'} \ge \sum_{(r,c) \in I'} \left( \max(d(c), d(r))^{1/2 - 1/p'} |x_{rc}| \right)^{p'}. $$

*Proof.* By the $p'$-Quadratic Mean Inequality and by Minkowski's Inequality,

$$ \begin{aligned} & \left( \sum_{c \in C'} \left( \sum_{(r,c) \in I'} |\alpha_{rc}|^2 \right)^{p'/2} \right)^{1/p'} + \left( \sum_{r \in R'} \left( \sum_{(r,c) \in I'} |\beta_{rc}|^2 \right)^{p'/2} \right)^{1/p'} \\ & \ge \left( \sum_{c \in C'} d(c)^{p'/2 - 1} \sum_{(r,c) \in I'} |\alpha_{rc}|^{p'} \right)^{1/p'} + \left( \sum_{r \in R'} d(r)^{p'/2 - 1} \sum_{(r,c) \in I'} |\beta_{rc}|^{p'} \right)^{1/p'} \\ & \ge \left( \sum_{(r,c) \in I'} \left( d(c)^{1/2 - 1/p'} |\alpha_{rc}| + d(r)^{1/2 - 1/p'} |\beta_{rc}| \right)^{p'} \right)^{1/p'} \end{aligned} $$

The lemma follows by taking the infimum over all $\alpha, \beta$ with $\alpha_q + \beta_q = x_q$ for $q \in I'$ as one can suppose that $\alpha_q = \beta_q = 0$ if $q \notin I$; note further that $1/2 - 1/p' \le 0$. $\square$

**Theorem 4.2.** If $I$ is a $\sigma(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 \cap R' \times C'$ with $\#C' = m$ and $\#R' = n$, satisfies

$$ \begin{aligned} \#I' &\le D^2 (m^{1/p} n^{1/2} + m^{1/2} n^{1/p})^2 & (10) \\ &\le 4D^2 \min(m, n)^{2/p} \max(m, n). \end{aligned} $$

The exponents in this inequality are optimal even for a complete $\sigma(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 $\sigma(p)$ set. Density conditions thus do not so far permit to distinguish $\sigma(p)$ sets and complete $\sigma(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 $\Lambda(p)$ sets.

*Proof.* If (2) holds, then $\|x|_{I'}\|_p \le D \|x\|_p$ for all $x \in S^p$ by Remark 3.5 applied to $(\mu_q)$ the indicator function of $I'$, and by duality $\|x|_{I'}\|_{p'} \le D \|x\|_{p'}$ for all $x \in S^{p'}$ (compare with [5, Rem. 4.6(iv)]). Let

$$ y = \sum_{(r,c) \in I'} d(c)^{1/p' - 1/2} e_{rc}, $$

$$ z = \sum_{(r,c) \in 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,

$$ \begin{aligned} \|y+z\|_{p'} &\le \|y\|_{p'} + \|z\|_{p'} \\ &= n^{1/2} \left( \sum_{c \in C'} d(c)^{2/p'-1} \right)^{1/2} + m^{1/2} \left( \sum_{r \in R'} d(r)^{2/p'-1} \right)^{1/2} \\ &\le n^{1/2} m^{1-1/p'} (\#I')^{1/p'-1/2} + m^{1/2} n^{1-1/p'} (\#I')^{1/p'-1/2}. \end{aligned} $$

We used that $\sum_{c \in C'} d(c) = \sum_{r \in R'} d(r) = \#I'$. By Lemma 4.1 applied to $x = y + z$,

$$ (\#I')^{1/p'} \le 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' \times C$ is a complete $\sigma(p)$ set for any $p$ as a union of $n$ rows and $\#I' = n \cdot m$.

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

**Remark 4.3.** If $n \not\asymp m$, the method used in [5, Theorem 4.8] does not provide optimal $\sigma(p)$ sets but the following lower bound. Let $p = 2s$ with $s \ge 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 \subseteq \{0, \dots, k-1\}$ with $q$ elements whose complete $\Lambda(2s)$ constant is independent of $q$. Let $m \ge k$ and $0 \le n \le m$ and consider the Hankel set

$$ I = \{ (r, c) \in \{0, \dots, n-1\} \times \{0, \dots, m-1\} : r + c \in F + m - k \}. $$

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

$$ \#I \ge \begin{cases} nq & \text{if } n \le m - k + 1 \\ (m - k + 1)q & \text{if } n \ge m - k + 1. \end{cases} $$

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

$$ \#I \ge \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 \ge 4$ be an even integer. If $G$ is a nonempty graph on $v$ vertices with $e$ edges without circuit of length $p$, then

$$ e \le 18\pi^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 \le 9\pi^2 p^2 \min(m, n)^{2/p} \max(m, n). \quad (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 \ge 2$ be an integer.

(i) If

$$e > 8D^2 v^{1+1/s} \quad \text{with } D > 9\pi 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) \quad \text{with } D > 9\pi 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\pi 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$. $\square$

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 \ge 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 \le 4 \max((4c)^{1/2s}, 9\pi 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 \le \alpha \le 1$. A random bipartite graph on $V = C \amalg R$ is defined by selecting independently each edge in $E = \{ \{r, c\} \subseteq V : (r, c) \in R \times C \}$ with the same probability $\alpha$. The resulting random edge set is denoted by $E' \subseteq E$ and $I' \subseteq R \times 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 $\varepsilon > 0$ and for each integer $s \ge 2$, there is an $\alpha$ such that Random construction 6.1 yields subsets $I' \subseteq R \times C$ with size

$$\#I' \sim \min(m, n)^{1/2+1/s} \max(m, n)^{1/2-\varepsilon}$$

and with $\sigma(2s)$ constant independent of $m$ and $n$ for $mn \to \infty$.
Proof. Let us suppose without loss of generality that $m \ge 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) \in C \times C^{(*)}$. Let $l \ge 1$ be a fixed integer. Then

$$
\begin{align*}
\mathbb{P}[c_s(I'; v_0, v_s) \ge l] &= \mathbb{P}[\exists l \text{ distinct trails } (v_0^j, \dots, v_s^j) \text{ in } \mathscr{C}^s(I'; v_0, v_s)] \\
&= \mathbb{P}[E' \supseteq \{\{v_{i-1}^j, v_i^j\}\}_{i,j} : \{(v_0^j, \dots, v_s^j)\}_{j=1}^l \subseteq \mathscr{C}^s(R \times C; v_0, v_s)] \\
&\le \sum_{k=\lceil l^{1/s} \rceil}^{ls} \#A_k \cdot \alpha^k,
\end{align*}
$$

where $A_k$ is the following set of $l$-element subsets of trails in $\mathscr{C}^s(R \times C; v_0, v_s)$ built with $k$ pairwise distinct edges

$$
A_k = \left\{ \{ (v_0^j, \dots, v_s^j) \}_{j=1}^l \subseteq \mathscr{C}^s(R \times C; v_0, v_s) : \#\{ \{v_{i-1}^j, v_i^j\} \}_{i,j} = k \right\};
$$

the lower limit of summation is ⌊*l*¹/`s`⌋ because one can build at most *k*⁴ 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, \dots, v_s^j$)}_{j=1}^l ∈ A_k. We claim that

$$
\# \{ v_i^j : 1 \le i \le s-1, 1 \le j \le l \} \le k(s-1)/s, \quad (12)
$$

$$
\#
\{ v_{2i}^j : 1 \le i \le \lfloor s/2 \rfloor - 1, 1 \le j \le l \} \le k/2. \quad (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, \dots, 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\}, \dots, \{v_{a+h}^j, v_{a+h+1}^j\};
$$

as $h \le s-1$, $h+1 \ge hs/(s-1)$. By (12) and (13),

$$
\# A_k \le m^{k/2} n^{k/2-k/s} (k - k/s)^{ls-l} \le (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 $\alpha = m^{-1/2}n^{-1/2+1/s}(\#C \cdot \#C^{(*)})^{-\epsilon}$. Then

$$
\begin{align*}
\mathbb{P}[\sup_{(v_0,v_s)} c_s(I'; v_0, v_s) \ge l] &\le \#C \cdot \#C^{(*)} \cdot (ls)^{ls} \sum_{k=\lceil l^{1/s} \rceil}^{ls} (\#C \cdot \#C^{(*)})^{-k\epsilon} \\
&\le (ls)^{ls} \frac{(\#C \cdot \#C^{(*)})^{1-\lceil l^{1/s} \rceil \epsilon}}{1 - (\#C \cdot \#C^{(*)})^{-\epsilon}}.
\end{align*}
$$

Choose *l* such that ⌊*l*¹/`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 \ge n$, we get $k = 2l$, $A_k = \binom{n}{l}$ and

$$
\mathbb{P}[ \sup_{(v_0,v_2) \in C \times C} c_2(I'; v_0, v_2) \ge l ] \le m^2 \binom{n}{l} \alpha^{2l}.
$$

Let $l \ge 2$ and $\alpha = m^{-1/l}n^{-1/2}$. This yields sets $I' \subseteq R \times C$ with size

$$
\# I' \sim n^{1/2} m^{1-1/l}
$$
and with $\sigma(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) \le l$ for all $v_0, v_2 \in 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' \le (\ln m(m-1) + n^2/4)^{1/2} + n/2 \sim 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} , \quad m = \frac{q^{r+1} - 1}{q - 1} $$

with $q$ a prime power and $r \ge 2$ an integer, and thus with $m \le n$: there seems to be no constructive example of extremal graphs with $c_2(I'; v_0, v_2) \le 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} \ge \binom{m}{l}n, \quad \#A_{3l} \ge \binom{m}{l}\binom{n}{l}. $$

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

$$ \#I' \le 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 $\Lambda(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 $\Lambda(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).