THE COHOMOLOGICAL DIMENSIONS OF THE TERMS OF THE JOHNSON FILTRATION

Daniel Minahan

686 Cherry Street NW, Atlanta, GA 30332

We prove that the $k$th term of the Johnson filtration of a closed, orientable surface of genus $g \geq 2$ has cohomological dimension $2g - 3$ for all $k \geq 3$ and $g \geq 2$.  This answers a question of Farb and Bestvina–Bux–Margalit.

§ INTRODUCTION

Let $S_g$ be a closed orientable surface of genus $g$.  The mapping class group $\Mod(S_g)$ is the group of isotopy classes of orientation preserving diffeomorphisms of $S_g$.  Let $\pi_1^{(k)}(S_g)$ denote the $k$th term of the lower central series of $\pi_1(S_g)$, where $\pi_1^{(0)}(S_g) = \pi_1(S_g)$.  The $k$th term of the Johnson filtration of $\Mod(S_g)$ is the kernel of the map

(S_g) →(π_1(S_g)/π_1^(k)(S_g))

and is denoted $\Mod_{(k)}(S_g)$.  The first term, $\Mod_{(1)}(S_g)$, is called the Torelli group and is denoted $\cI_g$.  The second term, $\Mod_{(2)}(S_g)$, is called the Johnson kernel and is denoted $\K_g$.

The cohomological dimension of a group $G$, denoted $\cd(G)$, is the supremum over all $n$ such that there is a $G$–module $M$ with $H^n(G;M) \neq 0$.  The simplest lower bound for $\cd(\Mod_{(k)}(S_g))$ is given by the maximal $n$ such that $\Z^n$ is a subgroup of $\Mod_{(k)}(S_g)$.  The largest known free abelian subgroup of $\Mod_{(k)}(S_g)$ for $k \geq 3$ is of rank $g - 1$ <cit.>.  We have the following theorem, which answers a question of Farb <cit.> and Bestvina–Bux–Margalit <cit.>.

Let $g \geq 2$ and $k \geq 3$.  The cohomological dimension of $\Mod_{(k)}(S_g)$ is $2g - 3$.

If $G$ has torsion, the virtual cohomological dimension of $G$ is $\cd(\Gamma)$ for any $\Gamma \subseteq G$ finite index and torsion free.  The quantity $\vcd(G)$ is indpendent of the choice of $\Gamma$ by a theorem of Serre <cit.>.  The following is the known values for $\cd$ and $\vcd$ of the terms of the Johnson filtration:

* $\vcd(\Mod(S_g))  = 4g - 5$ by the work of Harer <cit.>,

* $\cd(\cI_g) = 3g - 5$ by Bestvina–Bux–Margalit <cit.>, and

* $\cd(\Mod_{(k)}(S_g)) = 2g - 3$ for $k \geq 2$.

The third result in the case that $k=2$ is also due to Bestvina–Bux–Margalit <cit.>.

Outline of the proof of Theorem <ref> Cohomological dimension is monotonic, in the sense that $H \subseteq G$ implies $\cd(H) \leq \cd(G)$.  Our Theorem <ref> is a corollary of monotonicity of cohomological dimension, Bestvina–Bux–Margalit's theorem that $\cd(\K_g) = 2g - 3$ as above <cit.>, and the following theorem.

Let $g \geq 2$ and $k \geq 3$.  The group $H_{2g-3}(\Mod_{(k)}(S_g);\Z)$ is infinitely generated.

Theorem <ref> is a partial answer to the following question (see, e.g., Margalit <cit.>).

For which choices of natural numbers $g, k, j$ and commutative ring $R$ is the $R$–module $H_j(\Mod_{(k)}(S_g);R)$ finitely generated?

Prior partial answers to Question <ref> Mess showed that $\cI_2$ is an infinitely generated free group <cit.>, which answers Question <ref> for all $j, k$ and $R$ when $g = 2$.  Johnson showed that $\cI_g$ is finitely generated for $g \geq 3$, which answers Question <ref> for $j = k = 1$ and any $R$ in the case that $g \geq 3$ <cit.>.  Church–Ershov–Putman <cit.> showed that for $g \geq 2k - 1$, $\Mod_{(k)}(S_g)$ is finitely generated, which answers the question for $j = 1$ and any $R$ when $g \geq 2k - 1$.  In contrast, Bestvina–Bux–Margalit showed that $H_{3g-5}(\cI_g;\Z)$ is infinitely generated for all $g$ <cit.>.  Gaifullin showed that $H_{j}(\cI_g;\Z)$ is infinitely generated for $2g - 3 \leq j \leq 3g - 5$ <cit.>, and also showed that $H_{2g-3}(\K_g;\Z)$ is infinitely generated <cit.>.

The strategy of the proof of Theorem <ref> Our proof of Theorem <ref> follows the same strategy of Bestvina–Bux–Margalit <cit.>.  Gaifullin also used a variant of this approach to prove that $H_{2g-3}(\K_g;\Z)$ is infinitely generated <cit.>.  Bestvina–Bux–Margalit <cit.> define a complex $\calB(S_g)$ called the complex of cycles.  They consider the action of $\K_g$ on $\calB(S_g)$ and the associated equivariant homology spectral sequence $\bE_{p,q}^r$ (see, e.g., <cit.>).  The strategy is to apply the following inductive process for any $k \geq 3$:

* Mess proved that $H_1(\Mod_{(k)}(S_2);\Z)$ is infinitely generated <cit.>.

* We will prove that $H_{2(g-1) - 3}(\Mod_{(k)}(S_{g-1});\Z)$ infinitely generated implies that

is infinitely generated for $c \subseteq S_g$ a nonseparating simple closed curve.

* Bestvina–Bux–Margalit <cit.> show that, for any $k \geq 2$, there is an inclusion

_0,2g-3^1 ↪H_2g-3(_(k)(S_g);).

By construction, the complex $\calB(S_g)$ contains a vertex represented by a nonseparating simple closed curve $c \subseteq S_g$.  By examining the spectral sequence $\bE_{p,q}^r$, we can show that there is a sequence of inclusions

H_2g-3(_c(_(k)(S_g));) ↪_0,2g-3^1 ↪H_2g-3(_(k)(S_g);).

By Step (2), $H_{2g-3}(\Stab_c(\Mod_{(k)}(S_g));\Z)$ is infinitely generated.  Since the composition of injections is an injection, $H_{2g-3}(\Mod_{(k)}(S_g);\Z)$ is infinitely generated as well.

The outline of the paper In Section <ref>, we will construct a variant of the Birman exact sequence for the Johnson filtration.  In Section <ref>, we will prove in Proposition <ref> that for certain vertices $c \in \calB(S_g)$, if Theorem <ref> holds for $g' < g$ and $k \geq 3$, then $H_{2g-3}(\Stab_v(\Mod_{(k)}(S_g);\Z))$ is infinitely generated for every $k \geq 3$.  To do this, we will apply the Leray–Serre spectral sequence to the Birman exact sequence constructed Section <ref>.  In Section <ref>, we prove Theorem <ref> by the inductive process described above.  We then use Theorem <ref> to prove Theorem <ref>.

Acknowledgments The author would like to thank his adviser Dan Margalit for suggesting this problem and for many helpful mathematical discussions.  The author would like to thank Lei Chen pointing out an error in an earlier version of Section <ref>.

§ BIRMAN EXACT SEQUENCES FOR THE JOHNSON FILTRATION

Our goal in this section is to prove Proposition <ref> below, which gives a variant of the Birman exact sequence for the Johnson filtration and verifies that this variant satisfies certain properties.

Curves on a surface For the remainder of this paper, a curve $c$ on a surface $S$ is an isotopy class of essential, simple, closed curves.

Partitioned surfaces Let $S = S_{g}^b$ be an orientable compact surface of genus $g$ with $b$ boundary components. Putman <cit.> defined the notion of a partitioned surface $\Sigma = (S,P)$, which is a surface $S$ equipped with a partition $P$ of $\pi_0(\partial S)$.  Suppose that $S \subseteq S_h$, and this embedding has the property that for each connected component $S' \in \pi_0(S_h \setminus \Int(S))$, there is some $p \in P$ such that $\partial S' = p$.  Additionally, suppose that no connected component of $S_h \setminus \Int(S)$ is a disk or annulus.  The Torelli group $\cI(\Sigma)$, alternatively notated as $\cI(S,P)$, is the subgroup of $\Mod(S)$ generated by all elements $\varphi \in \cI_h$ such that $\varphi$ is supported on $S \subseteq S_h$.  Putman <cit.> showed that $\cI(S,P)$ is well–defined, i.e., independent of the choice of embedding $S \subseteq S_h$.  Later, Church <cit.> showed that the Johnson filtration of $\Sigma$, denoted $\Mod_{(k)}(\Sigma)$ or $\Mod_{(k)}(S,P)$, is also independent of the choice of embedding $S \subseteq S_h$.  Now, let $\Sigma = (S,P)$ be a partitioned surface, and let $\Sigma' = (S',P')$ be another partitioned surface given by capping off one boundary component $b \in S$ with a disk and forgetting the corresponding boundary component from the partition $P$.  Let $\UT S'$ denote the unit tangent bundle of $S'$, let $* \in S'$ be a basepoint, and let $\widetilde{*} \in \UT S'$ be a lift of $*$ to $\UT S'$.  Putman <cit.> showed that the Birman exact sequence <cit.>

1 →π_1(S',*) →(S) →(S') →1

restricts to a short exact sequence

1 →Γ→(Σ) →(Σ') →1.

The subgroup $\Gamma \subseteq \pi_1(\UT S', *)$ is constructed as follows.  If $\varphi:H \rightarrow K$ is a homomorphism of groups, the graph of $\varphi$, denoted $\Gamma(\varphi)$, is the subgroup of $H \oplus K$ generated by elements of the form $(h, \varphi(h))$.  There is a split short exact sequence

1 →→π_1(S', *') →π(S', *) →1,

and the group $\Gamma$ in Putman's Birman exact sequence for the Torelli group is $\Gamma(\kappa)$ for some function $\kappa:F_1 \rightarrow \Z$, where $F_1 \subseteq \pi_1(S',*)$.  We will extend the Birman exact sequence for the Torelli group to $\Mod_{(k)}(\Sigma)$ in the following special case.

Let $g \geq 3$.  Let $\Sigma_1 = (S_{g-1}^1, \pi_0(\partial S_{g-1}^1))$ and $\Sigma_2 = (S_{g-1}^2, \pi_0(\partial S_{g-1}^2))$.  Choose a boundary component $p \subseteq \partial S_{g-1}^2$, and let $\rho_1:\cI(\Sigma_2) \rightarrow \cI(\Sigma_1)$ be the map in Putman's Birman exact sequence for the Torelli group.  Choose a basepoint $* \in S_{g-1}^1$ and a lift of this basepoint to $\widetilde{*} \in \UT S_{g-1}^1$.  Let $\kappa: \pi_1(S_{g-1}^1,*) \rightarrow \Z$ be a map such that there is a subgroup $F_1 \subseteq \pi_1(S_{g-1}^1,*)$ with $\Gamma(\kappa|_{F_1}) \subseteq \pi_1(\UT S_{g-1}^1, \widetilde{*})$ equal to $\ker(\rho_1)$.  For any $k \geq 3$, there a subgroup $F_k \subseteq \left[\pi_1(S_{g-1}^1,*), \pi_1(S_{g-1}^1,*)\right]$ such that there is a short exact sequence

1 →Γ(κ|_F_k) →_(k)(Σ_2)  _(k)(Σ_1)→1,

given by restricting the Birman exact sequence.  Furthermore, for any $k \geq 3$, the group $F_k$ has the following properties:

* the quotient group $F_k/F_{k+1}$ is nontrivial, finitely generated and free abelian,

* the induced action of $\Mod_{(k)}(S_{g-1,1})$ on $F_k/F_{k+1}$ is trivial, and

* the quotient group $\pi_1(S_{g-1}^1,*)/F_k$ is solvable and non–cyclic.

There are several parts to the proof of Proposition <ref>.  We show in Lemma <ref> that the map $\rho_k$ given by restricting $\rho$ to $\Mod_{(k)}(\Sigma_2)$ has $\im(\rho_k) = \Mod_{(k)}(\Sigma_1)$.  We then use the higher Johnson homomorphisms of Morita to show that the group $F_k$ defined in the statement Proposition <ref> has properties (1)–(3) given in Proposition <ref>.  The relationship between $F_k$ and the higher Johnson homomorphisms is described in Lemma <ref>.  Properties (1) and (2) are verified in Lemma <ref>, and property (3) is verified in the proof of Proposition <ref>.

Let $g \geq 3$ and $k \geq 2$.  Let $\Sigma_1 = (S_{g-1}^1, \pi_0(\partial S_{g-1}^1))$ and $\Sigma_2 = (S_{g-1}^2, \pi_0(\partial S_{g-1}^2))$.  Choose a boundary component $p \subseteq \partial S_{g-1}^2$.  Let $\rho:\Mod(S_{g-1}^2) \rightarrow \Mod(S_{g-1}^1)$ be the map in the Birman exact sequence given by capping off $p$ with a disk.  Let $\rho_k$ denote the restriction of $\Mod(S_{g-1}^2)$ to $\Mod_{(k)}(\Sigma_2)$.  Then $\im(\rho_k) = \Mod_{(k)}(\Sigma_1) \subseteq \Mod(S_{g-1}^1)$.

Let $\iota:S_{g-1}^1 \rightarrow S_{g-1}^2$ be an embedding.  Let $\iota_*:\Mod(S_{g-1}^1) \rightarrow \Mod(S_{g-1}^2)$ denote the map given by extending $\varphi \in \Mod(S_{g-1}^1)$ by the identity map on $S_{g-1}^2 \cut \iota(S_{g-1}^1)$.  The map $\iota_*$ splits $\rho$ from the definition of the Birman exact sequence (see, e.g. <cit.>).  Furthermore, Church's work on the Johnson filtration <cit.> says that $\Mod_{(k)}(\Sigma_1) = \iota_*^{-1}(\Mod_{(k)}(\Sigma_2))$.  Since $\iota_*$ splits $\rho$, we therefore have $\im(\rho_k) = \Mod_{(k)}(\Sigma_2)$.

We now study the properties of the groups $F_k = \ker(\rho_k)$.

Higher Johnson homomorphisms Let $h \geq g$.  For each $j \geq 1$, there are maps $\tau_{j,h}:\Mod_{(j)}(S_h) \rightarrow A_{j,h}$ called the higher Johnson homomorphisms, such that:

* the group $A_{j,h}$ is finitely generated and free abelian group, and

* $\ker(\tau_{j,h}) = \Mod_{(j+1)}(S_h)$.

For $j = 1$ these maps were constructed by Johnson <cit.>, and for $j \geq 2$ these were constructed by Morita <cit.>.  We  use the higher Johnson homomorphisms to prove the following result.

Let $\Sigma = (S_g^b, P)$ be a partitioned surface with $g \geq 2$, and let $k \geq 1$.  Let $A_{k,\Sigma}$ be the cokernel of the inclusion map

_(k+1)(Σ) →_(k)(Σ).

The group $A_{k,\Sigma}$ is non–trivial, finitely generated and free abelian.

Let $\iota:\Sigma \rightarrow S_h$ be a map of partitioned surfaces <cit.> such that no connected component of $S_h \cut \iota(S_g^b)$ is a disk or annulus.  We have a morphism of short exact sequences

1 [r]     _(k+1)(S_h) [r]     _(k)(S_h) [r]     A_k,h [r]     1

1 [r]     _(k+1)(Σ) [r][u, "ι_*"]     _(k)(Σ) [r][u, "ι_*"]     A_k,Σ [r][u]     1

By the work of Putman <cit.> for the case $k = 1$ and Church for $k \geq 2$ <cit.> we have $\Mod_{(k)}(\Sigma) = \iota_*^{-1}(\Mod_{(k)}(S_h))$, and similarly for $k + 1$.  In particular, this implies that the left square in the diagram is a pullback square, so the right vertical arrow is injective by a diagram chase.  Since $A_{k,h}$ is finitely generated and free abelian by Johnson <cit.> for $k = 1$ and Morita <cit.> for $k \geq 2$, we see that $A_{k,\Sigma}$ is finitely generated and free abelian as well.

We now prove that $F_k = \ker(\rho_k)$ satisfies properties (1) and (2) in Proposition <ref>.

Let $g \geq 3$ and $k \geq 1$.  Let $\Sigma_1 = (S_{g-1}^1, \pi_0(\partial S_{g-1}^1))$ and $\Sigma_2 = (S_{g-1}^2, \pi_0(\partial S_{g-1}^2))$.  Choose a boundary component $p \subseteq \partial S_{g-1}^2$, and let $\rho:\Mod(S_{g-1}^2) \rightarrow \Mod(S_{g-1}^1)$ be the map in the Birman exact sequence.  Let $\rho_k$ denote the restriction of $\rho$ to $\Mod_{(k)}(\Sigma_2)$.  Let $\kappa:\pi_1(S_{g-1}^1,*) \rightarrow \Z$ be a map such that $\ker(\rho_1) = \Gamma(\kappa|_{K})$ for some $K \subseteq \pi_1(S_{g-1}^1,*)$, and let $F_k \subseteq \pi_1(S_{g-1}^1,*)$ be the group such that $\Gamma(\kappa|_{F_k}) = \ker(\rho_k)$.  For any $k \geq 3$, the group $F_k$ satisfies properties (1) and (2) of Proposition <ref>, namely

* the group $F_k/F_{k+1}$ is finitely generated and free abelian and

* the action of $\Mod_{(k)}(\Sigma_1)$ on $F_k/F_{k+1}$ is trivial.

Note that $F_k$ is canonically isomorphic to $\Gamma(\kappa|_{F_k})$ and the action of $\Mod_{(k)}(\Sigma_2)$ on the $\Z$–factor of $\pi_1(\UT S_{g-1}^1, *)$ is trivial, so we will work with $F_k$ instead of $\Gamma(\kappa|_{F_k})$.  Since $\rho_{k+1}$ is the restriction of $\rho_k$ to $\Mod_{(k+1)}(\Sigma_2)$, we have a short exact sequence of short exact sequences given by

1     1     1

1 [r]     F_k/F_k+1 [r] [u]     A_k, Σ_2 [r] [u]     A_k, Σ_1 [r] [u]     1

1 [r]     F_k [r][u]     _(k)(Σ_2) [r, "ρ_k"][u]     _(k)(Σ_1) [r][u]     1

1 [r]     F_k+1 [r][u]     _(k+1)(Σ_2) [r, "ρ_k+1"][u]     _(k+1)(Σ_1) [r][u]     1.

1 [u]     1[u]     1[u]

We verify properties (1) and (2) in turn.

Property (1) Since $A_{k,\Sigma_2}$ and $A_{k,\Sigma_1}$ are finitely generated free abelian groups by Lemma <ref>, the group $F_k/F_{k+1}$ must be a finitely generated free abelian group as well.

Property (2) To show that the action by $\Mod_{(k)}(\Sigma_1)$ on $F_k/F_{k+1}$ is trivial, recall from the argument in Lemma <ref> that $\rho_k$ is split.  Since $A_{k,\Sigma_2}$ is an abelian group, the conjugation action of $\Mod_{(k)}(\Sigma_2)$ on $A_{k,\Sigma_2}$ is the trivial action.  The fact that $\rho_k$ is split implies that $\Mod_{(k)}(\Sigma_1)$ acts trivially on $A_{k,\Sigma_2}$.  Since $F_{k}/F_{k+1}$ is a subgroup of $A_{k,\Sigma_2}$, the argument is complete.

We are now ready to complete the section.

By Lemma <ref> the claimed short exact sequence exists, and by Lemma <ref> the kernel $F_k$ satisfies properties (1) and (2).  Putman has shown that for $k = 1$, the group $F_1 = [\pi_1(S_{g-1}^1,*), \pi_1(S_{g-1}^1,*)]$ <cit.>. Therefore, it suffices to show that, for $k \geq 3$, $F_k$ satisfies property (3), namely that $\pi_1(S_{g-1}^1,*)/F_k$ is solvable and non–cyclic.

Property (3) By Lemma <ref>, the quotient group $\pi_1(S_{g-1}^1, *)/F_{k}$ is filtered by a sequence of subgroups such that the corresponding graded object consists of abelian groups, which in particular implies that $\pi_1(S_{g-1}^1,*)/F_k$ is solvable.  The fact that $\pi_1(S_{g-1}^1, *)/F_{k}$ is non–cyclic follows  the fact that $\pi_1(S_{g-1}^1,*)/F_1 \cong H_1(S_{g-1}^1;\Z)$.  Then $\pi_1(S_{g-1}^1, *)/F_{k} \twoheadrightarrow \pi_1(S_{g-1}^1,*)/F_1) \cong H_1(S_{g-1}^1;\Z)$, so $\pi_1(S_{g-1}^1, *)/F_{k}$ cannot be cyclic.

We will also record one more fact here, which will be useful in Section <ref>.

Let $F_k$ be as in Proposition <ref>.  Let $\proj: \Gamma(\kappa|_{F_k}) \rightarrow F_k$ denote the isomorphism induced by projection onto the $\pi_1(S_{g-1}^1, *)$–factor.  The pushforward map $\proj_*:H_1(\Gamma(\kappa|_{F_k});\Z) \rightarrow H_1(F_k)$ is an isomorphism of $\Mod_{(k)}(\Sigma_1)$–representations.

The action by conjugation of $\Mod_{(k)}(\Sigma_2)$ on $\pi_1(\UT S_{g-1}^1, \widetilde{*})$ is the restriction of the action of $\Mod(S_{g-1}^2)$ on $\pi_1(\UT S_{g-1}^1, \widetilde{*})$ (see, e.g., Farb and Margalit <cit.>).  Then $\Mod_{(k)}(\Sigma_2)$ acts trivially on the kernel of the map $\pi_1(\UT S_{g-1}^1, \widetilde{*})\rightarrow \pi_1(S_{g-1}^1, *)$, so the lemma follows.

§ THE HOMOLOGY OF CURVE STABILIZERS IN THE JOHNSON FILTRATION

The goal of this section is to prove Proposition <ref> below.  This i part s the main part of the inductive step of the proof of Theorem <ref>.

Let $g \geq 3$ and $k \geq 3$.  Suppose that $H_{2g-5}(\Mod_{(k)}(S_{g-1});\Z)$ is infinitely generated.  Let $c \subseteq S_g$ be a nonseparating simple closed curve.  Then $H_{2g-3}(\Stab_c(\Mod_{(k)}(S_g));\Z)$ is an infinitely generated abelian group.

The proof of Proposition <ref> requires three ingredients:

* Lemma <ref>, a general fact about the homology of a group extension,

* Lemma <ref> and Lemma <ref>, which are general facts about the homology of infinite covers of surfaces, and

* Lemma <ref>, which says that $H_{2g-5}(\Mod_{(k)}(S_{g-1});\Z)$ infinitely generated implies $H_{2g-4}(\Mod_{(k)}(S_{g-1,1});\Z)$ infinitely generated.

Lemma <ref> follows by applying Lemma <ref>, Lemma <ref> and Lemma <ref> to a variant of the Birman exact sequence given by Akin <cit.>.  Proposition <ref> will follow by applying the same argument structure to the short exact sequence constructed in Section <ref>.

Homology of group extensions If $\langle \cdot, \cdot \rangle$ is a symplectic form on a free abelian group $V$, we say that $v \in V$ is degenerate if $\langle v, \cdot \rangle: V \rightarrow \Z$ is the zero map.  We say that a form $\langle \cdot, \cdot \rangle$ on $V$ is degenerate if some element of $V$ is degenerate, and otherwise that $\langle \cdot, \cdot \rangle$ is nondegenerate.  We will say that $V' \subseteq V$ is a degenerate subspace if every $v \in V'$ is degenerate, and denote by $V^{\degen}$ the subspace spanned by all degenerate elements of $V$.  The following lemma is a generalization of a result of Bestvina–Bux–Margalit <cit.>, and is ingredient one in the proof of Proposition <ref>.

Let $F$ be a non–cyclic free group and let

1 →F →G →Q →1

be a short exact sequence of groups.  Equip $H_1(F;\Z)$ with the $Q$–action induced by the conjugation action of $G$ on $F$.  Let $V \subseteq H_1(F;\Z)$ be a $Q$–invariant subgroup such that $H_1(F;\Z)/V$ is torsion free.  Suppose that:

* $H_1(F;\Z)$ admits a nondegenerate $Q$–invariant symplectic form $\langle \cdot, \cdot \rangle$,

* the restriction of $\langle \cdot, \cdot \rangle$ to $V$ is nondegenerate,

* the quotient $H_1(F;\Z)/V$ is a trivial $Q$–module, and

* $H_{\cd(Q)}(Q;\Z)$ is infinitely generated.

Then $H_{\cd(Q) + 1}(G;\Z)$ is infinitely generated.

We begin with the following claim.

Claim There is an isomorphism $H_{\cd(Q) + 1}(G;\Z) \cong H_{\cd(Q)}(Q;H_1(F;\Z))$.

Proof of claim  The cohomological dimension of $F$ is 1 since $F$ is free.  Consider the Lyndon–Hochschild–Serre spectral sequence $\bE_{\cd(Q),1}^2$  <cit.> corresponding to the short exact sequence

1 →F →G →Q →1.

This is the spectral sequence with $\bE_{p,q}^2 = H_p(Q;H_q(F;\Z))$ that converges to $H_{p+q}(G;\Z)$.  We have $\bE_{p,q}^r = 0$ for all $p +q > \cd(Q) + 1$ and $r \geq 2$, since either $p > \cd(Q)$ or $q > \cd(F) = 1$.   Thus there are no non–trivial differentials into or out of $\bE_{\cd(Q), 1}^2$ and therefore $\bE_{\cd(Q),1}^2 \cong \bE_{\cd(Q),1}^\infty$.  By the definition of the Lyndon–Hochschild–Serre spectral sequence, $\bE_{\cd(Q),1}^2 = H_{\cd(Q)}(Q;H_1(F;\Z))$, so the claim holds.

By the claim it suffices to show that $H_{\cd(Q)}(Q;H_1(F;\Z))$ is infinitely generated.  By hypothesis (2), the subspace $V^{\perp} \subseteq H_1(F;\Z)$ is isomorphic to $H_1(F;\Z)/V$ as a $Q$–module.  But the form $\langle \cdot, \cdot \rangle$ is $Q$–invariant by hypothesis (1), so $V \oplus V^{\perp}$ is a decomposition of $H_1(F;\Z)$ into $Q$–modules.  Therefore the short exact sequence

0 →V →H_1(F;) →H_1(F;)/V →0

splits as a sequence of $Q$–modules, and thus $H_{\cd(Q)}(Q;H_1(F;\Z))$ splits as a direct sum

H_(Q)(Q;V) ⊕H_(Q)(Q;H_1(F;)/V).

By hypothesis (3), the action of $Q$ on $H_1(F;\Z)/V$ is trivial.  Therefore there is an isomorphism

H_(Q)(Q; H_1(F;)/V) ≅H_(Q)(Q;) ⊗H_1(F;)/V.

Since $H_{\cd(Q)}(Q;\Z)$ is infinitely generated by hypothesis, $H_{\cd(Q) + 1}(G;\Z)$ contains an infinitely generated free abelian subgroup and thus is infinitely generated as well.

Homology of covers We now discuss the second ingredient of the proof of Proposition <ref>.

Let $S = S_{g}^b$ with $b \in \{0,1\}$.  Let $\Gamma \trianglelefteq \pi_1(S)$ be an infinite index normal subgroup contained in $\pi_1^{(1)}(S)$.  Suppose that $\pi_1(S)/\Gamma$ is solvable and non–cyclic.  Let $S_\Gamma$ be the cover of $S$ corresponding to $\Gamma$.  Suppose that, if $\delta$ is a loop surrounding a boundary component of $S$, then $\delta \not \in \Gamma$.  Then the algebraic intersection form on $H_1(S_{\Gamma};\Z)$ is non–degenerate.

We use the fact that solvable, non–cyclic groups are one–ended (see, e.g., Löh <cit.>).  Choose a basepoint $*_{\Gamma} \in S_{\Gamma}$ and a finite set of generators $\calF \subseteq \pi_1(S)$.  Let $G \subseteq S_{\Gamma}$ be an embedding of the Cayley graph of $\pi_1(S)/\Gamma$ containing $*_{\Gamma}$ such that each edge of $G$ is a lift of a loop $\gamma \in \calF$.  Since $S$ is compact, basic covering space theory tells us that $S_{\Gamma}$ is quasi–isometric to $G$.  Therefore $S_{\Gamma}$ has one end, so if $\delta \subseteq \pi_1(S)$ is a separating simple closed curve, at least one connected component of $S \cut \delta$ has compact closure in $S$.  But since no loop surrounding a boundary component is contained in $\Gamma$,  the surface $S_{\Gamma}$ has no compact boundary components.  Therefore $\delta$ is the boundary of a compact subsurface of $S_{\Gamma}$ given by the closure in $S_{\Gamma}$ of the finite–type connected component of $S_{\Gamma} \setminus \delta$.  In particular, this implies that any class in $H_1(S_{\Gamma};\Z)$ represented by a separating curve is the trivial class, so any nonzero class $v \in H_1(S_{\Gamma};\Z)$ is a multiple of a class represented by a nonseparating curve $a$.  Since $a$ is nonseparating, there is a curve $b \subseteq S_{\Gamma}$ with $\left|b \cap a\right| = 1$.  Therefore the class $v$ has nonzero algebraic intersection with the class $[b]$, so the algebraic intersection form on $H_1(S_{\Gamma};\Z)$ is nondegenerate, as desired.

We need one more fact about the homology of covers.

Let $S = S_{g}^b$ with $b \in \{0,1\}$.  Let $\Gamma \trianglelefteq \pi_1(S)$ be an infinite index normal subgroup such that $\pi_1(S)/\Gamma$ is solvable and non–cyclic.  The subgroup of $H_1(\Gamma;\Z)$ spanned by the $\pi_1(S)$–orbit of any nonzero $v \in H_1(\Gamma;\Z)$ is infinitely generated.

Let $S_{\Gamma} \rightarrow S$ be the regular cover corresponding to the subgroup $\Gamma \subseteq \pi_1(S)$.  Since $\Gamma$ has infinite index in $\pi_1(S_g)$, the cover $S_{\Gamma} \rightarrow S$ is infinite-sheeted.  By way of contradiction, suppose that there is a nonzero $v \in H_1(S_{\Gamma};\Z)$ such that the span of the orbit $\pi_1(S) v$ is finitely generated.  Since $\pi_1(S)v$ is finitely generated if and only if the span of $\pi_1(S)( m v)$ is finitely generated for any $m \in \Z$, we may assume that $v$ is primitive.

Let $\delta \subseteq S_\Gamma$ be a simple closed curve representing $v$.  Such a $\delta$ exists since $v$ is primitive.  By Lemma <ref>, $H_1(S_{\Gamma};\Z)$ is nondegenerate, so there is another simple closed curve $\varepsilon \subseteq S_\Gamma$ such that $\left|\delta \cap \varepsilon\right| = 1$.  Let $T \subseteq S_\Gamma$ be an embedded copy of $S_1^1$ that contains $\delta$ and $\varepsilon$.  Since $T$ is compact and the action of $\pi_1(S_g)/\Gamma$ on $S_{\Gamma}$ is properly discontinuous, there are infinitely many disjoint $\pi_1(S_g)/\Gamma$–translates of $T$.  Hence there are infinitely many elements in the orbit $(\pi_1(S)/\Gamma)  \delta$ that are all supported on disjoint embedded copies $S_{1}^1 \subseteq S_\Gamma$.  Therefore there are infinitely many classes in the orbit $\pi_1(S)/\Gamma  [v]$ that are pairwise orthogonal in $H_1(S_\Gamma;\Z)$, so the lemma holds.

We are almost ready to prove Proposition <ref>.  Let $S_{g,n}$ denote an orientable surface of genus $g$ with $n$ punctures.  If $n = 1$ and $* \in S_{g,1}$ is a basepoint, we define $\Mod_{(k)}(S_{g-1,1})$ to be the subgroup of $\Mod_{(k)}(S_{g-1,1})$ given by the kernel of the natural map

(S_g-1,1) →(π_1(S_g-1,1,*)/π_1^(k)(S_g-1,1^*)).

Akin <cit.> proved that there is a short  exact sequence

1 →π_1^(k-1)(S_g-1) →_(k)(S_g-1,1) →_(k)(S_g-1) →1.

which we call the Akin–Birman exact sequence.  We will apply Lemma <ref> to Akin's sequence to prove the following.

Let $g \geq 3$, $k \geq 2$.  Suppose that $H_{2g-5}(\Mod_{(k)}(S_{g-1});\Z)$ is infinitely generated.  Then $H_{2g-4}(\Mod_{(k)}(S_{g-1,1};\Z))$ is infinitely generated.

We will show that the Akin–Birman exact sequence satisfies the hypotheses of Lemma <ref>.  Let $V \subseteq H_1(\pi_1^{(k-1)}(S_{g-1});\Z)$ be the image of the map

H_1(π_1^(k)(S_g-1);) →H_1(π_1^(k-1)(S_g-1);).

Since $\pi_1^{(k)}(S_{g-1})$ is a characteristic subgroup, the subgroup $V$ is $\Mod_{(k)}(S_{g-1})$–invariant.  We will verify each hypothesis of Lemma <ref> in turn.

* $H_1(\pi_1^{(k-1)}(S_{g-1});\Z)$ admits a nondegenerate $\Mod_{(k)}(S_{g-1})$–invariant symplectic form $\langle \cdot, \cdot \rangle$.

Let $\Gamma = \pi_1^{(k-1)}(S_{g-1})$.  Let $S_{\Gamma}$ denote the cover of $S_{g-1}$ with $\pi_1(S_{\Gamma}) \cong \Gamma$.  There is a canonical isomorphism $H_1(S_\Gamma;\Z) \cong H_1(\Gamma;\Z)$ induced by the canonical map $\Gamma \rightarrow H_1(S_{\Gamma};\Z)$.  The symplectic form on $H_1(\Gamma;\Z)$ will be the pushforward of the algebraic intersection form $\langle \cdot, \cdot \rangle$ on $H_1(S_{\Gamma};\Z)$ under this isomorphism.  We will show that the $\Mod_{(k)}(S_{g-1})$–action on $H_1(\Gamma;\Z)$ given by the $\Mod_{(k)}(S_{g,1})$–conjugation on $\Gamma$ respects this symplectic form.

Choose a basepoint $b \in S_{g-1}$ and a lift of the basepoint $b$ to $b_\Gamma \in S_{\Gamma}$.  The Birman exact sequence coupled with the Dehn–Nielsen–Baer theorem gives an identification

(S_g-1,1) ≅(π_1(S_g)).

The subgroup $\Gamma$ is characteristic, so there is a map

(π_1(S_g-1)) →(Γ).

By composing with the map $\Aut(\Gamma) \rightarrow \Out(\Gamma)$, there is a natural map

(π_1(S_g-1)) →(Γ).

Since $\Gamma$ is characteristic, the choice of basepoints $b$ and $b_\Gamma$ coupled with the lifting criterion for covering spaces yields a map

(S_g-1,1) →(S_Γ).

Hence the algebraic intersection form on $H_1(\Gamma;\Z)$ is a $\Mod(S_{g-1,1})$–invariant symplectic form, and by restriction $\Mod_{(k)}(S_{g-1,1})$–invariant.  By the Akin–Birman exact sequence <cit.>, the map

_(k)(S_g-1,1) →_(k)(S_g-1)

is surjective.  Hence for any $\varphi \in \Mod_{(k)}(S_{g-1})$, there is a lift $\overline{\varphi} \in \Mod_{(k)}(S_{g-1,1})$.  But if $\widehat{\varphi}$ is another such lift, the Akin–Birman exact sequence says that $\overline{\varphi}^{-1} \widehat{\varphi} \in \pi_1^{(k)}(S_{g-1}) = \Gamma$.  Therefore the composition $\overline{\varphi}^{-1} \widehat{\varphi}$ acts trivially on $H_1(S_{\Gamma};\Z) $ since $H_1(S_{\Gamma};\Z) \cong H_1(\Gamma;\Z)$, and so $\Mod_{(k)}(S_{g-1})$ acts in a well–defined way on $H_1(S_{\Gamma};\Z)$ and respects the nondegenerate form $\langle \cdot, \cdot \rangle$ on $H_1(S_{\Gamma};\Z)$.  Thus the $\Mod_{(k)}(S_{g-1})$–action on $H_1(\Gamma;\Z)$ respects the pushforward of the $H_1(S_\Gamma;\Z)$–intersection form.  The nondegeneracy of the form follows from Lemma <ref>, so hypothesis (1) holds.

* The restriction of $\langle \cdot, \cdot \rangle$ to $V$ is nondegenerate

Suppose by way of contradiction that there is a non–zero $v \in V$ such that the linear map $\langle v, \cdot \rangle: H_1(\pi_1^{(k-1)}(S_{g-1});\Z) \rightarrow \Z$ is the zero map.  By Lemma <ref>, the $\pi_1(S_{g-1})$–orbit of $v$ in $H_1(\pi_1^{(k-1)}(S_{g-1});\Z)$ is infinitely generated.  Since $\langle \cdot, \cdot \rangle$ is $\pi_1(S_{g-1,1})$–invariant, any $\gamma v$ is degenerate for $\gamma \in \pi_1(S_{g-1,1})$.  Now, choose $w \in H_1(\pi_1^{(k-1)}(S_{g-1});\Z)$ such that $\langle v, w \rangle = 1$.  By Lemma <ref>, the span of the $\pi_1(S_{g-1})$ orbit of $w$ is infinitely generated.  But $\langle \gamma w, \gamma v \rangle \neq 0$ for any $\gamma \in \pi_1(S_{g-1,1})$.  Since $\gamma v$ is degenerate in $V$ for any $\gamma \in \pi_1(S_{g-1,1})$, it must be the case that $\Span(\{\gamma w: \gamma \in \pi_1(S_{g-1})\})$ embeds into $H_1(\pi_1^{(k-1)}(S_{g-1};\Z))/V$.  But this latter space is finitely generated, which is a contradiction.

* The quotient $H_1(\pi_1^{(k-1)};\Z)/V$ is a trivial $\Mod_{(k)}(S_{g-1})$–module.

Since $\Mod_{(k)}(S_{g-1})$ acts trivially on $\pi_1(S_{g-1})/\pi_1^{(k)}(S_{g-1})$ by definition, $\Mod_{(k)}(S_{g-1})$ acts trivially on $H_1(\pi_1^{(k-1)}(S_{g-1});\Z)/V$ as well.

* $H_{\cd(\Mod_{(k)}(S_{g-1}))}(\Mod_{(k)}(S_{g-1});\Z)$ is infinitely generated.

By hypothesis, $H_{2g-5}(\Mod_{(k)}(S_{g-1});\Z)$ is infinitely generated.  Bestvina–Bux–Margalit <cit.> showed that $\cd(\Mod_{(2)}(S_{g-1})) = 2(g-1) - 3 = 2g - 5$.  Hence

(_(k)(S_g-1) ≤(_(2)(S_g-1)) ≤2g - 5.

Therefore if $H_{2g-5}(\Mod_{(k)}(S_{g-1};\Z)) \neq 0$, we have $\cd(\Mod_{(k)}) = 2g - 5$, so hypothesis (4) of Lemma <ref> holds.

Hence the hypotheses of Lemma <ref> hold for the Akin–Birman sequence, so $H_{2g-4}(\Mod_{(k)}(S_{g-1,1});\Z)$ is infinitely generated.

We are now almost ready to prove the main result of the section.  Before doing so, we will need one more auxiliary lemma which relates the slight variations of $\Mod_{(k)}$ that we have used throughout the paper.

Let $g \geq 3$ and $k \geq 3$.  Let $\Sigma_1 = (S_{g-1}^1, \{\{b_0\}\})$ and $\Sigma_2 = (S_{g-1}^2, \{\{b_0, b_1\}\})$.  Then the following hold:

* $\Mod_{(k)}(S_{g-1,1}) \cong \Mod_{(k)}(\Sigma_1)$, and

* if $c \subseteq S_g$ is a nonseparating simple closed curve $\Stab_c(\Mod_{(k)}(S_g)) = \Mod_{(k)}(\Sigma_2)$.

We prove each of these in turn.

Part (1) Church <cit.> defines $\Mod_{(k)}(\Sigma_1)$ to be the kernel of the action of $\Mod(S_{g-1}^1)$ on the group $\pi_1(S_{g-1}^1, *)/\pi_1^{(k)}(S_{g-1}^1,*)$, where $*$ is a basepoint contained in $\partial S_{g-1}^1$.  Therefore there is a natural map

_(k)(Σ_1) →_(k)(S_g-1,1)

that is surjective and has kernel contained in $\langle T_{\delta} \rangle$, where $T_{\delta}$ is the twist around the boundary component of $S_{g-1}^1$.  But no power of $T_{\delta}$ is contained in $\Mod_{(k)}(\Sigma_1)$ for $k \geq 3$, so the map $\Mod_{(k)}(\Sigma_1) \rightarrow \Mod_{(k)}(S_{g-1,1})$ is an isomorphism.

Part (2) Let $f \in \Mod(S_{g-1}^2)$ denote the bounding pair map corresponding to the bounding pair consisting of the two boundary components of $S_{g-1}^2$.  A result of Birman–Lubotzky–McCarthy <cit.> says that there is a short exact sequence

1 →⟨f ⟩→(S_g-1^2) →_c((S_g)) →1.

The latter map $\Mod(S_{g-1}^2) \rightarrow \Stab_c(\Mod(S_g))$ is induced by the embedding $S_{g-1}^2 \rightarrow S_g$ such that the complement of the image of the embedding contains $c$.  In particular, the work of Church <cit.> says that this short exact sequence restricts to a short exact sequence

1 →F →_(k)(Σ_2) →_c(_(k)(S_g)) →1

for $F \subseteq \langle f \rangle$.  But then no power of $f$ is contained in $\Mod_{(k)}(\Sigma_2)$ for $k \geq 3$, so $F = \{1\}$ and hence $\Mod_{(k)}(\Sigma_2) \cong \Stab_c(\Mod_{(k)}(S_g))$.

Recall that our goal is to show that $H_{2g-5}(\Mod_{(k)}(S_{g-1};\Z))$ is infinitely generated, then the group $H_{2g-3}(\Stab_c(\Mod_{(k)}(S_{g}));\Z))$ is infinitely generated as well, for $c$ a non–separating simple closed curve.

Since $k \geq 3$, Lemma <ref> says that we have isomorphisms $\Mod_{(k)}(\Sigma_1) \cong \Mod_{(k)}(S_{g-1,1})$ and $\Mod_{(k)}(\Sigma_2) \cong \Stab_c(\Mod_{(k)}(S_g))$.  Hence, it suffices to show that if the group $H_{2g-4}(\Mod_{(k)}(\Sigma_1);\Z)$ is infinitely generated, then $H_{2g-3}(\Mod_{(k)}(\Sigma_2);\Z)$ infinitely generated.  We will apply Lemma <ref> to the short exact sequence from Proposition <ref>.  We take $V \subseteq H_1(F_k;\Z)$ to be the image of $F_{k+1}$ in $H_1(F_k;\Z)$.  We verify each hypothesis for Lemma <ref> in turn.

* $H_1(F_k;\Z)$ admits a nondegenerate $\Mod_{(k)}(\Sigma_1)$–invariant symplectic form

This form is the algebraic intersection form on the cover of $S_{F_k} \rightarrow S_{g-1}^1$ corresponding to $F_k$.  The group $\Mod_{(k)}(\Sigma_1)$ acts on $H_1(S_{F_k};\Z)$ as a consequence of Lemma <ref>.  This action respects the algebraic intersection form on $H_1(S_{F_k};\Z)$, since the action of $\varphi \in \Mod_{(k)}(\Sigma_1)$ on $H_1(S_{F_k};\Z)$ is the pushforward of a homeomorphism $S_{F_k} \rightarrow S_{F_k}$.  The group $\pi_1(S_{g-1}^1)/F_k$ is solvable and non–cyclic by property (3) of Lemma <ref>.  Furthermore, if $\delta$ is the loop around the boundary component of $S_{g-1}^1$, then $\delta \not \in F_k$ for $k \geq 3$, since the push along $\delta$ induces a Dehn twist along a separating curve.  Therefore the  algebraic intersection form on $H_1(F_k;\Z)$ is non–degenerate by Lemma <ref>.

* The restriction of $\langle \cdot, \cdot \rangle$ to $V$ is nondegenerate

The form $\langle \cdot, \cdot \rangle$ is non–degenerate when restricted to $V = \im(F_{k+1} \rightarrow H_1(F_k;\Z))$.  In particular, Proposition <ref> says that $H_1(F_k;\Z)/V$ is nontrivial, finitely generated, and free abelian.  Then Lemma <ref> of says that the $\pi_1(S_{g-1}^1)$ orbit of any nontrivial element in $H_1(F_k;\Z)$ spans an infinitely generated subgroup.  The argument is complete by the same argument as step (2) of Lemma <ref>.

* The quotient $H_1(F_k;\Z)/V$ is a trivial $\Mod_{(k)}(\Sigma_2)$–module

This is property (2) of $F_k$ from Proposition <ref>.

* The group $H_{\cd(\Mod_{(k)}(\Sigma_1))}(\Mod_{(k)}(\Sigma_1);\Z)$ is infinitely generated.

By monotonicity and the fact that $\cd(\Mod_{(2)}(S_{g-1})) = 2g - 3$ <cit.>, we have $\cd(\Mod_{(k)}(S_{g-1}) \leq 2g - 3$.  By applying the sub–additivity of cohomological dimension on short exact sequences <cit.> to the Akin–Birman exact sequence,  we have $\cd(\Mod_{(k)}(S_{g-1,1})) \leq 2g - 4$.  Since $H_{2g-4}(\Mod_{(k)}(S_{g-1,1});\Z)$ is non–zero by Lemma <ref>, we must have

(_(k)(S_g-1,1)) = 2g - 4.

Then Lemma <ref> says that $H_{2g-4}(\Mod_{(k)}(S_{g-1,1}))$ is infinitely generated, so the hypothesis is satisfied.

Therefore $H_{2g-3}(\Mod_{(k)}(\Sigma_2);\Z)$ is infinite dimensional by Lemma <ref>.  Since $\Mod_{(k)}(\Sigma_2)$ is isomorphic to $\Stab_c(\Mod_{(k)}(S_g))$ by Lemma <ref>, the proof is complete.

§ THE PROOFS OF THEOREMS <REF> AND <REF>

In this section, we complete the proofs of Theorems <ref> and <ref>.  We begin by briefly discussing the complex of cycles, $\calB(S_g)$, a cell complex defined by Bestvina–Bux–Margalit <cit.>.  The following properties of $\calB(S_g)$ are the relevant properties for the purposes of this paper:

* $\calB(S_g)$ is contractible <cit.>,

* there is a vertex $v \in \calB(S_g)$ represented by a nonseparating simple closed curve $c \subseteq S_g$, and

* $\calB(S_g)$ admits a rotation–free $\cI_g$–action <cit.>.

As discussed in the introduction, we will adopt Bestvina–Bux–Margalit's strategy for their proof that $H_{3g-5}(\cI_g;\Z)$ is infinitely generated <cit.>.  Specifically, we will consider the action of $\cI_g$ on the complex $\calB(S_g)$.  We will apply the equivariant homology spectral sequence <cit.>.  We will use Proposition <ref> and the second property of $\calB(S_g)$ above to show that the entry $\bE_{0,2g-3}^{\infty}$ is infinitely generated.  We begin with the following result.

Let $S = S_g$ with $g \geq 3$, and let $k \geq 3$.  Let $c \subseteq S_g$ be a nonseparating simple closed curve.  The pushforward map

H_2g-3(_c_(k)(S_g);) →H_2g-3(_(k)(S_g);)

is an injection.

Let $\bE_{*,*}^*$ be the equivariant homology spectral sequence given by the action of $\Mod_{(k)}(S_g)$ on $\calB(S_g)$ as discussed in the introduction.  For each $0 \leq k \leq 2g  - 3$, let $\Sigma_k$ be a set of representatives in $\calB(S_g)$ of the $k$–cells in the quotient $\calB(S_g)/\cI_g$.  By property (c) of $\calB(S_g)$, $\Mod_{(k)}(S_g)$ acts on $\calB(S_g)$ without rotations.  Hence there is a decomposition

_p,q^1 ≅⊕_σ∈Σ_p H_q(_σ(_(k)(S_g)).

By property (b) of $\calB(S_g)$, there is a vertex $v$ of $\calB(S_g)$ represented by a simple closed curve $c$, there is an injection

H_2g-3(_c (_(k)(S_g));) ↪_0,2g-3^1.

Bestvina–Bux–Margalit prove that for any $j$–cell $\sigma \subseteq \calB(S)$ <cit.>, we have

(_σ_(2)(S_g)) ≤2g - 3 - j.

Since $H \subseteq G$ implies $\cd(H) \subseteq \cd(G)$ <cit.>, we have

(_σ_(k)(S_g)) ≤2g - 3 - j.

for any $j$–cell $\sigma \subseteq \calB(S)$.  Hence the non–zero entries of the first page of the spectral sequence $\bE_{p,q}^r$ are as in Figure <ref>.

(m) [matrix of math nodes,
nodes in empty cells,
nodes=minimum width=10ex,
minimum height=5ex,
outer sep=-5pt,
text centered,anchor=center]
2g - 3     ⊕_σ∈Σ_0 H_2g-3(_σ(_(k)(S_g)))      0     ⋯    ⋯    0

⋮    ⋮   ⋮    ⋱    ⋱    ⋮

1           ⊕_σ∈Σ_0 H_1(_σ(_(k)(S_g)))        ⋯    ⋯     0     ⋮

0           ⊕_σ∈Σ_0 H_0(_σ(_(k)(S_g)))       ⋯    ⋯    ⋯     0

0        1     ⋯    2g-3    2g-2
[thick] (m-1-1.north east) – (m-5-1.east) ;
[thick] (m-5-1.north) – (m-5-6.north east) ;

Page 1 of the sequence $\bE_{p,q}^r$

On the diagonal $p +q = 2g - 2$, every entry $\bE_{p,q}^1$ is $0$.  Therefore for every $r \geq 1$, the map $d_{r+1,2g-3 - r}^r$ mapping into $\bE_{0,2g-3}^{r}$ is the zero map.  Hence there is an injection

H_2g-3(_c _(k)(S_g);) ↪_0,2g-3^∞.

Property (a) of $\calB(S_g)$ says that $\calB(S_g)$ is contractible.  Hence $\bE_{p,q}^r$ converges to $H_{p+q}(\Mod_{(k)}(S_g);\Z)$ <cit.>, so $\bE_{0,2g-3}^\infty$ injects into $H_{2g-3}(\Mod_{(k)}(S_g);\Z)$.  Hence the composition

H_2g-3(_c _(k)(S_g);) →_0,2g-3^1 ≅_0,2g-3^∞→H_2g-3(_(k)(S_g);)

is an injection, so the proof is complete.

We are now ready to prove Theorem <ref>.

Fix a $k \geq 3$.  We will prove the theorem by induction on $g$.

Base case: $g = 2$  As mentioned in the introduction, Mess showed that $\Mod_{(1)}(S_2)$ is an infinitely generated free group <cit.>.  Since the $k$th term of the lower central series $\Mod_{(1)}^{(k)}(S_2)$ is contained in $\Mod_{(k)}(S_2)$ for every $k \geq 2$, $\Mod_{(k)}(S_2)$ is an infinitely generated free group as well.  Hence $H_1(\Mod_{(k)}(S_2);\Z)$ is infinitely generated.

Inductive step  Suppose that the theorem holds for all $2 \leq g' < g$.  Let $c$ be a nonseparating simple closed curve on $S_g$.  By Proposition <ref> and the inductive hypothesis, $H_{2g-3}(\Stab_c(\Mod_{(k)}(S_g));\Z)$ is infinitely generated.  Then by Lemma <ref>, $H_{2g-3}(\Mod_{(k)}(S_g);\Z))$ is infinitely generated as well, so the proof is complete.

We now prove the main result of the paper.

By Theorem <ref> and the universal coefficient theorem,
(_(k)(S_g)) ≥2g - 3.

Bestvina–Bux–Margalit  showed that $\cd(\Mod_{(2)}(S_g)) = 2g - 3$ <cit.>.  By the monotonicity of cohomological dimension, we have

(_(2)(S_g)) ≥(_(k)(S_g))

for $k \geq 2$.  Hence the equality $\cd(\Mod_{(k)}(S_g)) = 2g - 3$ holds.

Fix an inclusion $S_{g-1}^1 \rightarrow S_{g-1}^2$.  Equip $S_{g-1}^2$ with the one–element partition, turning $S_{g-1}^2$ into a partitioned surface $\Sigma$.  Putman <cit.> showed that there is a short exact sequence

1 →π_1^(1)(S_g-1^1) →_(1)(Σ) →_(1)(S_g-1^1) →1.

By modding out by twists along boundary components, there is a morphism of short exact sequences

1 [r]     1 [r][d]    [r][d]     [r][d]   1

1 [r]    π_1^(1)(S_g-1^1) [r][d]    _(1)(Σ) [r][d]    _(1)(S_g-1^1) [r][d]    1

1 [r]    π_1^(1)(S_g-1,1) [r]    _c(_(1)(S_g)) [r]    _(1)(S_g-1,1) [r]    1.

Hence it suffices to show that the bottom row of the above diagram restricts to a short exact sequence

1 →F →_c(_(k)(S_g)) →_(k)(S_g-1,1) →1.

ρ: _c(_(k)(S_g)) →_(1)(S_g-1,1)

denote the restriction of the map $\Stab_c(\Mod_{(1)}(S_g)) \rightarrow \Mod_{(1)}(S_{g-1,1})$ to $\Stab_c(\Mod_{(k)}(S_g))$.  It suffices to show the following:

* $\im(\rho) \supseteq \Mod_{(k)}(S_{g-1,1})$,

* $\im(\rho) \subseteq \Mod_{(k)}(S_{g-1,1})$, and

* $\ker(\rho)$ is a free group $F \supseteq \pi_1^{(k+1)}(S_{g-1,1})$.

We will prove each of these statements in turn.

* Church <cit.> showed that the inclusion map $\iota:S_{g-1}^1 \rightarrow S_{g-1}^2$ induces an inclusion $\Mod_{(k)}(S_{g-1}^1) \rightarrow \Mod_{(k)}(S_{g-1}^2)$.  Hence $\im(\rho) \supseteq \Mod_{(k)}(S_{g-1,1})$, since the boundary twists in the above commutative diagram are not in the $k$th term of the Johnson filtration.

* Pick a $\varphi \in \im(\rho)$ and let $\widehat{\varphi}$ be a lift of $\varphi$ to $\Mod_{(k)}(S_{g-1}^1)$.

Church <cit.> showed that the inclusion map $\iota:S_{g-1}^1 \rightarrow S_{g-1}^2$ induces an inclusion $\Mod_{(k)}(S_{g-1}^1) \rightarrow \Mod_{(k)}(S_{g-1}^2)$.  Hence $\im(\rho) \supseteq \Mod_{(k)}(S_{g-1,1})$, since the boundary twists in the above commutative diagram are not in the $k$th term of the Johnson filtration.

Hence the map

descends to a map $\Mod_{(k)}(S_{g-1,1}) \rightarrow \Stab_c(\Mod_{(k)}(S_g))$ since twists along boundary components are not in $\Mod_{(k)}(S_{g}^b)$ for $k \geq 3$.  Hence it suffices to show that the restriction of the map

_c(_(1)(S_g)) →_(1)(S_g-1,1)

to $\Stab_c(\Mod_{(k)}(S_g))$ induces a map

_c(_(k)(S_g)) →_(k)(S_g-1,1)

and that the kernel of this map contains $\pi_1^{(k)}(S_{g-1,1})$.  Then $\pi_1^{(k)}(S_{g-1,1}) \subseteq \Stab_c(\Mod_{(k)}(S_g))$ since the push–map in the Birman exact sequence acts by conjugation <cit.>.  Furthermore, if $\varphi \in \Stab_{c}(\Mod_{(1)}(S_g))$ acts trivially on $\pi_1(S_g)/\pi_1^{(k)}(S_g)$, then its image under the map

_c(_(1)(S_g)) →_(1)(S_g-1,1)

acts trivially on $\pi_1(S_{g-1,1})/\pi_1^{(k)}(S_{g-1,1})$, so the proof is complete.


# Universal sampling discretization

F. Dai and V. Temlyakov 111 The first named author’s research was partially
supported by NSERC of Canada Discovery Grant RGPIN-2020-03909. The second
named author’s research was supported by the Russian Federation Government
Grant No. 14.W03.31.0031.

###### Abstract

Let $X_{N}$ be an $N$-dimensional subspace of $L_{2}$ functions on a
probability space $(\Omega,\mu)$ spanned by a uniformly bounded Riesz basis
$\Phi_{N}$. Given an integer $1\leq v\leq N$ and an exponent $1\leq q\leq 2$,
we obtain universal discretization for integral norms $L_{q}(\Omega,\mu)$ of
functions from the collection of all subspaces of $X_{N}$ spanned by $v$
elements of $\Phi_{N}$ with the number $m$ of required points satisfying $m\ll
v(\log N)^{2}(\log v)^{2}$. This last bound on $m$ is much better than
previously known bounds which are quadratic in $v$. Our proof uses a
conditional theorem on universal sampling discretization, and an inequality of
entropy numbers in terms of greedy approximation with respect to dictionaries.

Keywords and phrases: Sampling discretization, universality, entropy numbers.

MSC classification 2000: Primary 65J05; Secondary 42A05, 65D30, 41A63.

##  1 Introduction

A standard approach to solving a continuous problem numerically – the Galerkin
method – suggests to look for an approximate solution from a given finite-
dimensional subspace. A typical way to measure an error of approximation is an
appropriate $L_{p}$ norm, $1\leq p\leq\infty$. Thus, the problem of
discretization of the $L_{p}$ norms of functions from a given finite-
dimensional subspace arises in a very natural way. Approximation by elements
from a linear subspace falls in the category of linear approximation.

It was understood in numerical analysis and approximation theory that in many
problems from signal/image processing it is beneficial to use an $m$-term
approximant with respect to a given system of elements (dictionary)
${\mathcal{D}}_{N}:=\\{g_{i}\\}_{i=1}^{N}$. This means that for $f\in X$ we
look for an approximant of the form

$a_{m}(f):=\sum_{k\in\Lambda(f)}c_{k}g_{k}$ (1.1)

where $\Lambda(f)\subset[1,N]$ is a set of $m$ indices which is determined by
$f$. The complexity of this approximant is characterized by the cardinality
$|\Lambda(f)|=m$ of $\Lambda(f)$. Approximation of this type is referred to as
nonlinear approximation because, for a fixed $m$, approximants $a_{m}(f)$ come
from different linear subspaces spanned by $g_{k}$, $k\in\Lambda(f)$, which
depend on $f$. The cardinality $|\Lambda(f)|$ is a fundamental characteristic
of $a_{m}(f)$ called sparsity of $a_{m}(f)$ with respect to
${\mathcal{D}}_{N}$. It is now well understood that we need to study nonlinear
sparse approximations in order to significantly increase our ability to
process (compress, denoise, etc.) large data sets. Sparse approximations of a
function are not only a powerful analytic tool but they are utilized in many
applications in image/signal processing and numerical computation.

Therefore, here is an important ingredient of the discretization problem,
desirable in practical applications. Suppose we have a finite dictionary
${\mathcal{D}}_{N}:=\\{g_{j}\\}_{j=1}^{N}$ of functions from
$L_{p}(\Omega,\mu)$. Applying our strategy of sparse $m$-term approximation
with respect to ${\mathcal{D}}_{N}$ we obtain a collection of all subspaces
spanned by at most $m$ elements of ${\mathcal{D}}_{N}$ as a possible source of
approximating (representing) elements. Thus, we would like to build a
discretization scheme, which works well for all such subspaces. This kind of
discretization falls in the category of universal discretization. The paper is
devoted to the problem of universal sampling discretization.

Let $\Omega$ be a nonempty set equipped with a probability measure $\mu$. For
$1\leq p\leq\infty$, let $L_{p}(\Omega):=L_{p}(\Omega,\mu)$ denote the real
Lebesgue space $L_{p}$ defined with respect to the measure $\mu$ on $\Omega$,
and $\|\cdot\|_{p}$ the norm of $L_{p}(\Omega)$. By discretization of the
$L_{p}$ norm we understand a replacement of the measure $\mu$ by a discrete
measure $\mu_{m}$ with support on a set
$\xi=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$. This means that integration with
respect to measure $\mu$ is replaced by an appropriate cubature formula. Thus,
integration is replaced by evaluation of a function $f$ at a finite set $\xi$
of points. This is why this way of discretization is called sampling
discretization. The problem of sampling discretization is a classical problem.
The first results in this direction were obtained in the 1930s by Bernstein,
by Marcinkiewicz and by Marcinkiewicz-Zygmund for discretization of the
$L_{p}$ norms of the univariate trigonometric polynomials. Even though this
problem is very important in applications, its systematic study has begun only
recently (see the survey paper [5]). We now give explicit formulations of the
sampling discretization problem (also known as the Marcinkiewicz
discretization problem) and of the problem of universal discretization.

The sampling discretization problem. Let $(\Omega,\mu)$ be a probability
space, and $X_{N}\subset L_{q}$ an $N$-dimensional subspace of
$L_{q}(\Omega,\mu)$ with $1\leq q\leq\infty$ (the index $N$ here, usually,
stands for the dimension of $X_{N}$). We shall always assume that every
function in $X_{N}$ is defined everywhere on $\Omega$, and

$f\in X_{N},\ \|f\|_{q}=0\implies f=0\in X_{N}.$

We say that $X_{N}$ admits the Marcinkiewicz-type discretization theorem with
parameters $m\in{\mathbb{N}}$ and $q$ and positive constants $C_{1}\leq C_{2}$
if there exists a set $\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ such that
for any $f\in X_{N}$ we have in the case $1\leq q<\infty$

$C_{1}\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq
C_{2}\|f\|_{q}^{q}$ (1.2)

and in the case $q=\infty$

$C_{1}\|f\|_{\infty}\leq\max_{1\leq j\leq m}|f(\xi^{j})|\leq\|f\|_{\infty}.$

The problem of universal discretization. Let
$\mathcal{X}:=\\{X(n)\\}_{n=1}^{k}$ be a collection of finite-dimensional
linear subspaces $X(n)$ of the $L_{q}(\Omega)$, $1\leq q\leq\infty$. We say
that a set $\xi:=\\{\xi^{j}\\}_{j=1}^{m}\subset\Omega$ provides universal
discretization for the collection $\mathcal{X}$ if, in the case $1\leq
q<\infty$, there are two positive constants $C_{i}$, $i=1,2$, such that for
each $n\in\\{1,\dots,k\\}$ and any $f\in X(n)$ we have

$C_{1}\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq
C_{2}\|f\|_{q}^{q}.$

In the case $q=\infty$ for each $n\in\\{1,\dots,k\\}$ and any $f\in X(n)$ we
have

$C_{1}\|f\|_{\infty}\leq\max_{1\leq j\leq m}|f(\xi^{j})|\leq\|f\|_{\infty}.$
(1.3)

Note that the problem of universal discretization for the collection
$\mathcal{X}:=\\{X(n)\\}_{n=1}^{k}$ is the sampling discretization problem for
the set $\cup_{n=1}^{k}X(n)$. Also, we point out that the concept of
universality is well known in approximation theory. For instance, the reader
can find a discussion of universal cubature formulas in [26], Section 6.8.

The problem of universal discretization for some special subspaces of the
trigonometric polynomials was studied in [29, 5]. To describe the results in
[29, 5], we need to introduce some necessary notations. First, given a finite
subset $Q$ of $\mathbb{Z}^{d}$, we set

$\mathcal{T}(Q):=\Bigl{\\{}f:f=\sum_{\mathbf{k}\in
Q}c_{\mathbf{k}}e^{i(\mathbf{k},\mathbf{x})},\ \ c_{\mathbf{k}}\in\mathbb{C},\
\ \mathbf{k}\in Q\Bigr{\\}}.$

For $\mathbf{s}=(s_{1},\cdots,s_{d})\in\mathbb{Z}^{d}_{+}$, we define

$R(\mathbf{s}):=\\{\mathbf{k}\in\mathbb{Z}^{d}:|k_{j}|<2^{s_{j}},\quad
j=1,\dots,d\\}.$

The following result, proved in [29], solves the universal discretization
problem for the collection

${\mathcal{C}}(n,d):=\left\\{\mathcal{T}(R(\mathbf{s})):s_{1}+\cdots+s_{d}=n\right\\}$

of subspaces of trigonometric polynomials.

######  Theorem 1.1.

[29] For every $1\leq q\leq\infty$ there exists a large enough constant
$C(d,q)$, which depends only on $d$ and $q$, such that for any
$n\in{\mathbb{N}}$ there is a set
$\xi:=\\{\xi^{\nu}\\}_{\nu=1}^{m}\subset\mathbb{T}^{d}$, with $m\leq
C(d,q)2^{n}$ that provides universal discretization in $L_{q}$ for the
collection ${\mathcal{C}}(n,d)$.

Second, for $n\in{\mathbb{N}}$, let

$\Pi_{n}:=[-2^{n-1}+1,2^{n-1}-1]^{d}\cap\mathbb{Z}^{d}.$

For a positive integer $v\leq|\Pi_{n}|$, define

$\mathcal{S}(v,n):=\left\\{Q:\ \ Q\subset\Pi_{n},\ |Q|=v\right\\}.$

Then it is easily seen that

$|\mathcal{S}(v,n)|=\binom{|\Pi_{n}|}{v}<2^{dnv}.$

The following two theorems provide universal discretization of $L_{1}$ and
$L_{2}$ norms for the collection $\\{\mathcal{T}(Q):\ \
Q\in\mathcal{S}(v,n)\\}$.

######  Theorem 1.2.

[28, 5, Theorem 7.4] For positive integers $n$ and $1\leq v\leq|\Pi_{n}|$, let

$M_{p}(n,v):=\begin{cases}v^{2}n^{9/2},\ \ &\text{if $p=1$},\\\ v^{2}n,\ \
&\text{if $p=2$}.\end{cases}$

Then there exist three positive constants $C_{i}(d)$, $i=1,2,3$, such that for
any $n,v\in{\mathbb{N}}$ with $v\leq|\Pi_{n}|$, and for $p=1$ and $2$, there
is a set $\xi=\\{\xi^{\nu}\\}_{\nu=1}^{m}\subset\mathbb{T}^{d}$, with $m\leq
C_{1}(d)M_{p}(n,v)$ such that for any
$f\in\cup_{Q\in\mathcal{S}(v,n)}\mathcal{T}(Q)$

$C_{2}(d)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{\nu=1}^{m}|f(\xi^{\nu})|^{p}\leq
C_{3}(d)\|f\|_{p}^{p}.$

Let us denote by ${\mathcal{D}}_{N}=\\{g_{i}\\}_{i=1}^{N}$ a system of
functions from $L_{p}$. Denote the set of all $v$-term approximants with
respect to ${\mathcal{D}}_{N}$ as

$\Sigma_{v}({\mathcal{D}}_{N}):=\left\\{f\,:\,f=\sum_{i\in
G}c_{i}g_{i},\quad\text{with any}\,G\subset[1,N],\quad|G|=v\right\\}.$

Theorem 1.2 provides universal discretization for the collection
$\\{\mathcal{T}(Q)\,:\,Q\in\mathcal{S}(v,n)\\}$, which is equivalent to the
sampling discretization of the $L_{p}$ norm of elements from the set
$\Sigma_{v}({\mathcal{D}}_{N})$ with $N=|\Pi_{n}|$,
${\mathcal{D}}_{N}=\\{e^{i(\mathbf{k},\mathbf{x})}\\}_{\mathbf{k}\in\Pi_{n}}$.
The proof of Theorem 1.2 in the case $p=2$ is based on deep results on random
matrices and in the case $p=1$ is based on a chaining technique. We point out
that in both the cases $p=2$ and $p=1$ Theorem 1.2 provides universal
discretization with the number of points growing as $v^{2}$. In this paper we
prove the following estimate (see below for definitions and notations).

######  Theorem 1.3.

Let $1\leq p\leq 2$. Assume that $\Phi_{N}$ is a uniformly bounded Riesz basis
of $X_{N}:=\operatorname{span}(\Phi_{N})$ satisfying (2.8) for some constants
$0<R_{1}\leq R_{2}$. Then for a large enough constant $C=C(p,R_{1},R_{2})$,
and any integer $1\leq v\leq N$, there exist $m$ points
$\xi^{1},\cdots,\xi^{m}\in\Omega$ with

$m\leq Cv(\log N)^{2}(\log(2v))^{2}$

such that for any $f\in\Sigma_{v}(\Phi_{N})$ we have

$\frac{1}{2}\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq\frac{3}{2}\|f\|_{p}^{p}.$
(1.4)

In particular, Theorem 1.3 gives the order of bound $m\ll v(\log
N)^{2}(\log(2v))^{2}$, which is linear in $v$ with extra logarithmic terms in
$N$ and $v$. This bound is much better than previously known bounds (see
Theorem 1.2), which provided quadratic in $v$ bounds. Note that even for each
individual subspace from $\Sigma_{v}(\Phi_{N})$ we have the lower bound $m\geq
v$ for the sampling discretization.

The rest of this paper is organized as follows. Section 2 and Section 3 are
devoted to estimating the entropy numbers
$\varepsilon_{k}(\Sigma_{v}^{p}(\Phi_{N}),L_{\infty})$ of the sets

$\Sigma_{v}^{p}(\Phi_{N}):=\\{f\in\Sigma_{v}(\Phi_{N})\,:\,\|f\|_{p}\leq
1\\},\ \ 1\leq p\leq 2,$

in the $L_{\infty}$-norm, where $\Phi_{N}$ is a uniformly bounded Riesz basis
of $X_{N}:=[\Phi_{N}]\subset L_{2}$ and $1\leq v\leq N$ is an integer. Such
estimates play an important role in the proof of Theorem 1.3. To be more
precise, in Section 2, we prove under the additional condition (2.9) on the
space $X_{N}=\operatorname{span}(\Phi_{N})$ that for $p=2$,

$\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{\infty})\leq C(\log
N)\Bigl{(}\frac{v}{k}\Bigr{)}^{1/2},\quad k=1,2,\dots.$ (1.5)

The proof of (1.5) uses a known result from Greedy approximation in smooth
Banach spaces and its connection with entropy numbers. In Section 3, we show
how the estimate (1.5) can be extended to the case $1\leq p<2$ under the
condition (2.9). This extension step is based on a general inequality for the
entropy, which is given in Lemma 3.1 and apprears to be of independent
interest. In Section 4, we prove Theorem 1.3, using the estimates on entropy
numbers established in the previous two sections, and a conditional theorem on
sampling discretization. A main step in the proof is to show that the
condition (2.9) that is assumed in our estimates of entropy numbers can be
dropped in sampling discretization. The conditional Theorem 2.2 used in the
proof of Theorem 1.3 is given in Section 2 without proof. In Section 5, we
prove a refined conditional theorem for sampling discretization of all
integral norms $L_{q}$ of functions from a subset $\mathcal{W}\subset
L_{\infty}$ satisfying certain conditions, which allows us to estimate the
number of points required for the sampling discretization in terms of an
integral of the $\varepsilon$-entropy
$\mathcal{H}_{\varepsilon}(\mathcal{W},L_{\infty})$, $\varepsilon>0$. This is
an extension of the conditional result proved in [28, 7] for the unit ball of
the space $X_{N}\subset L_{p}$. In particular, it also allows us to prove a
refined version of Theorem 1.3, where the constants $\frac{1}{2}$ and
$\frac{3}{2}$ in (1.4) are replaced by $1-\varepsilon$ and $1+\varepsilon$
respectively for an arbitrarily given $\varepsilon\in(0,1)$. Finally, in
Section 6, we give a few remarks on universal sampling discretization of
$L_{p}$ norms for $p>2$.

Throughout this paper, the letter $C$ denotes a general positive constant
depending only on the parameters indicated as arguments or subscripts, and we
will use the notation $|A|$ to denote the cardinality of a finite set $A$.

##  2 Some general entropy bounds and the case $p=2$

It is well known that bounds of the entropy numbers of the unit ball of an
$N$-dimensional subspace $X_{N}\subset L_{p}$

$X_{N}^{p}:=\\{f\in X_{N}\,:\,\|f\|_{p}\leq 1\\}$

play an important role in sampling discretization of the $L_{p}$ norm of
elements of $X_{N}$ (see [24], [28], [6], and [7]).

Recall the definition of entropy numbers in Banach spaces. Let $X$ be a Banach
space and $B_{X}(g,r)$ denote the closed ball $\\{f\in X:\|f-g\|\leq r\\}$
with center $g\in X$ and radius $r>0$. Given a positive number $\varepsilon$,
the covering number $N_{\varepsilon}(A,X)$ of a compact set $A\subset X$ is
defined as

$N_{\varepsilon}(A,X):=\min\left\\{n\in{\mathbb{N}}:\ \
\exists\;g^{1},\ldots,g^{n}\in A,\
A\subset\bigcup_{j=1}^{n}B_{X}(g^{j},\varepsilon)\right\\}.$

We denote by $\mathcal{N}_{\varepsilon}(A,X)$ the corresponding minimal
$\varepsilon$-net of the set $A$ in $X$; namely,
$\mathcal{N}_{\varepsilon}(A,X)$ is a finite subset of $A$ such that
$A\subset\bigcup_{y\in\mathcal{N}_{\varepsilon}(A,X)}B_{X}(y,\varepsilon)$ and
$N_{\varepsilon}(A,X)=|\mathcal{N}_{\varepsilon}(A,X)|$. The
$\varepsilon$-entropy $\mathcal{H}_{\varepsilon}(A,X)$ of the compact set $A$
in $X$ is defined as $\log_{2}N_{\varepsilon}(A,X)$, and the entropy numbers
$\varepsilon_{k}(A,X)$ of the set $A$ in $X$ are defined as

$\displaystyle\varepsilon_{k}(A,X):$
$\displaystyle=\inf\\{\varepsilon>0:{\mathcal{H}}_{\varepsilon}(A,X)\leq
k\\},\ \ k=1,2,\ldots.$

The following conditional result was proved in [28] for $p=1$, and in [7] for
the full range of $1\leq p<\infty$.

######  Theorem 2.1.

[28, 7] Let $1\leq q<\infty$. Suppose that a subspace $X_{N}\subset
L_{q}(\Omega,\mu)$ satisfies the condition

$\varepsilon_{k}(X^{q}_{N},L_{\infty})\leq B(N/k)^{1/q},\quad 1\leq k\leq N,$
(2.1)

where $B\geq 1$. Then for a large enough constant $C(q)$ there exist $m$
points $\xi^{1},\cdots,\xi^{m}\in\Omega$ with

$m\leq C(q)NB^{q}(\log_{2}(2BN))^{2}$

such that for any $f\in X_{N}$ we have

$\frac{1}{2}\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq\frac{3}{2}\|f\|_{q}^{q}.$

As we explained above the problem of universal discretization of the
collection $\\{X(n)\\}_{n=1}^{k}$ is equivalent to the sampling discretization
of the union $\cup_{n=1}^{k}X(n)$ of the corresponding subsets. Therefore,
instead of bounds of the entropy numbers of the unit ball $X_{N}^{q}$ we are
interested in the entropy bounds of the ”unit ball”

$\Sigma_{v}^{q}({\mathcal{D}}_{N}):=\\{f\in\Sigma_{v}({\mathcal{D}}_{N})\,:\,\|f\|_{q}\leq
1\\}$

which is the union of the corresponding unit balls.

The following version of Theorem 2.1 follows directly from its proof.

######  Theorem 2.2.

Let $1\leq q<\infty$ and $1\leq v\leq N$. Suppose that a dictionary
${\mathcal{D}}_{N}$ is such that the set $\Sigma_{v}^{q}({\mathcal{D}}_{N})$
satisfies the condition

$\varepsilon_{k}(\Sigma_{v}^{q}({\mathcal{D}}_{N}),L_{\infty})\leq
B_{1}(v/k)^{1/q},\quad 1\leq k<\infty,$ (2.2)

where $B_{1}\geq 1$. Assume in addition that there exists a constant
$B_{2}\geq 1$ such that

$\|f\|_{\infty}\leq B_{2}v^{1/q}\|f\|_{q},\ \ \forall
f\in\Sigma_{v}^{q}({\mathcal{D}}_{N}).$ (2.3)

Then for a large enough constant $C(q)$ there exist $m$ points
$\xi^{1},\cdots,\xi^{m}\in\Omega$ with

$m\leq C(q)B_{1}^{q}v(\log(2B_{2}v))^{2}$

such that for any $f\in\Sigma_{v}({\mathcal{D}}_{N})$ we have

$\frac{3}{4}\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq\frac{5}{4}\|f\|_{q}^{q}.$

Theorem 2.2 also follows from a more general conditional theorem that will be
proved in Section 5 (see Corollary 5.1).

######  Remark 2.1.

We point out that (2.2) implies

$\|f\|_{\infty}\leq 3B_{1}v^{1/q},\ \ \forall
f\in\Sigma^{q}_{v}({\mathcal{D}}_{N}).$ (2.4)

Therefore, assumption (2.3) can be dropped with $B_{2}$ replaced by $3B_{1}$
in the bound on $m$. However, in applications, the constant $B_{2}$ in (2.3)
may be significantly smaller than $3B_{1}$. For example, if
${\mathcal{D}}_{N}$ is a uniformly bounded orthonormal system with
$\max_{f\in{\mathcal{D}}_{N}}\|f\|_{\infty}=1$, then we can take $B_{2}=1$.

Proof of (2.4). For $\Lambda\subset[1,N]\cap{\mathbb{N}}$ denote
$X(\Lambda):=\operatorname{span}(g_{i})_{i\in\Lambda}$ and
$X(\Lambda)^{q}:=\\{f\in X(\Lambda):\,\|f\|_{q}\leq 1\\}$. Clearly, (2.2)
implies the same bound for each $X(\Lambda)^{q}$ with $|\Lambda|=v$. Thus, it
is sufficient to prove (2.4) for a $v$-dimensional subspace $X_{v}$. With a
slightly worse constant $4B_{1}$ instead of $3B_{1}$ it was proved in [7,
Remark 1.1]. We now show how to get a better constant. Setting
$\varepsilon_{1}:=e_{1}(X_{v}^{q},L_{\infty})$, we can find two functions
$f_{1},f_{2}\in X_{v}^{q}$ such that $X_{v}^{q}\subset
B_{L_{\infty}}(f_{1},\varepsilon_{1})\cup
B_{L_{\infty}}(f_{2},\varepsilon_{1})$. Since $0\in X_{v}^{q}$, $0$ is
contained in one of the two balls. Without loss of generality, we may assume
that $0\in B_{L_{\infty}}(f_{1},\varepsilon_{1})$ so that
$\|f_{1}\|_{\infty}\leq\varepsilon_{1}$. Since $-f_{2}\in X_{v}^{q}$, we have
either $-f_{2}\in B_{L_{\infty}}(f_{1},\varepsilon_{1})$ or $-f_{2}\in
B_{L_{\infty}}(f_{2},\varepsilon_{1})$, which implies $\|f_{2}\|_{\infty}\leq
2\varepsilon_{1}$. It then follows that $\|f\|_{\infty}\leq 3\varepsilon_{1}$
for all $f\in X_{v}^{q}$. This together with (2.2) proves (2.4).

Theorem 2.2 motivates us to estimate the characteristics
$\varepsilon_{k}(\Sigma_{v}^{q}({\mathcal{D}}_{N}),L_{\infty})$. We now recall
some known general results, which turn out to be useful for that purpose. Let
${\mathcal{D}}_{N}=\\{g_{j}\\}_{j=1}^{N}$ be a system of elements of
cardinality $|{\mathcal{D}}_{N}|=N$ in a Banach space $X$. Consider the best
$m$-term approximations of $f$ with respect to ${\mathcal{D}}_{N}$

$\sigma_{m}(f,{\mathcal{D}}_{N})_{X}:=\inf_{\\{c_{j}\\};\Lambda:|\Lambda|=m}\|f-\sum_{j\in\Lambda}c_{j}g_{j}\|.$

For a set $W\subset X$, we define

$\sigma_{m}(W,{\mathcal{D}}_{N})_{X}:=\sup_{f\in
W}\sigma_{m}(f,{\mathcal{D}}_{N})_{X},\ \ m=1,2,\cdots,$

and $\sigma_{0}(W,{\mathcal{D}}_{N})_{X}=\sup_{f\in W}\|f\|_{X}$. The
following Theorem 2.3 was proved in [22] (see also [26], p.331, Theorem
7.4.3).

######  Theorem 2.3.

Let a compact $W\subset X$ be such that there exist a system
${\mathcal{D}}_{N}\subset X$ with $|{\mathcal{D}}_{N}|=N$, and a number $r>0$
such that

$\sigma_{m}(W,{\mathcal{D}}_{N})_{X}\leq(m+1)^{-r},\quad m=0,1,\cdots,N.$

Then for $k\leq N$

$\varepsilon_{k}(W,X)\leq C(r)\left(\frac{\log(2N/k)}{k}\right)^{r}.$ (2.5)

For a given set ${\mathcal{D}}_{N}=\\{g_{j}\\}_{j=1}^{N}$ of elements we
introduce the octahedron (generalized octahedron)

$A_{1}({\mathcal{D}}_{N}):=\left\\{f\,:\,f=\sum_{j=1}^{N}c_{j}g_{j},\quad\sum_{j=1}^{N}|c_{j}|\leq
1\right\\}$ (2.6)

and the norm $\|\cdot\|_{A}$ on $X_{N}$

$\|f\|_{A}:=\inf\left\\{\sum_{j=1}^{N}|c_{j}|\,:\,f=\sum_{j=1}^{N}c_{j}g_{j}\right\\}.$

We now use a known general result for a smooth Banach space. For a Banach
space $X$ we define the modulus of smoothness

$\rho(u):=\rho(X,u):=\sup_{\|x\|=\|y\|=1}\left(\frac{1}{2}(\|x+uy\|+\|x-uy\|)-1\right).$

The uniformly smooth Banach space is the one with the property

$\lim_{u\to 0}\rho(u)/u=0.$

In this paper we only consider uniformly smooth Banach spaces with power type
modulii of smoothness $\rho(u)\leq\gamma u^{s}$, $1<s\leq 2$. The following
bound is a corollary of greedy approximation results (see, for instance [26],
p.455).

######  Theorem 2.4.

Let $X$ be $s$-smooth: $\rho(X,u)\leq\gamma u^{s}$, $1<s\leq 2$. Then for any
normalized system ${\mathcal{D}}_{N}$ of cardinality $|{\mathcal{D}}_{N}|=N$
we have

$\sigma_{m}(A_{1}({\mathcal{D}}_{N}),X)\leq C(s)\gamma^{1/s}m^{1/s-1}.$

Note that it is known that in the case $X=L_{p}$ we have

$\rho(L_{p},u)\leq(p-1)u^{2}/2,\quad 2\leq p<\infty.$ (2.7)

We now proceed to a special case when $X=L_{p}$ and
${\mathcal{D}}_{N}=\Phi_{N}:=\\{\varphi_{j}\\}_{j=1}^{N}$ is a uniformly
bounded Riesz basis of
$X_{N}:=[\Phi_{N}]:=\operatorname{span}(\varphi_{1},\dots,\varphi_{N})$.
Namely, we assume that $\|\varphi_{j}\|_{\infty}\leq 1$, $1\leq j\leq N$ and
for any $(a_{1},\cdots,a_{N})\in{\mathbb{R}}^{N},$

$R_{1}\left(\sum_{j=1}^{N}|a_{j}|^{2}\right)^{1/2}\leq\left\|\sum_{j=1}^{N}a_{j}\varphi_{j}\right\|_{2}\leq
R_{2}\left(\sum_{j=1}^{N}|a_{j}|^{2}\right)^{1/2},$ (2.8)

where $0<R_{1}\leq R_{2}<\infty$. Assume in addition that for any $f\in X_{N}$
we have

$\|f\|_{\infty}\leq C_{0}\|f\|_{\log N}.$ (2.9)

######  Theorem 2.5.

Assume that $\Phi_{N}$ is a uniformly bounded Riesz basis of
$X_{N}:=[\Phi_{N}]$ satisfying (2.9). Then we have

$\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{\infty})\leq C(R_{1},C_{0})(\log
N)\Bigl{(}\frac{v}{k}\Bigr{)}^{1/2},\quad k=1,2,\dots.$ (2.10)

###### Proof.

First of all, for any $f=\sum_{j\in G}a_{j}\varphi_{j}$, $|G|=v$ we get

$\|f\|_{A}\leq\sum_{j\in G}|a_{j}|\leq v^{1/2}\left(\sum_{j\in
G}|a_{j}|^{2}\right)^{1/2}\leq R_{1}^{-1}v^{1/2}\|f\|_{2}.$ (2.11)

Therefore,

$\Sigma_{v}^{2}(\Phi_{N})\subset R_{1}^{-1}v^{1/2}\Sigma_{v}^{A}(\Phi_{N}),$

where

$R\Sigma_{v}^{A}(\Phi_{N}):=\\{f\in\Sigma_{v}(\Phi_{N})\,:\,\|f\|_{A}\leq
R\\}.$

By Theorem 2.4 with $s=2$ and by (2.7), we have that for $p\in[2,\infty)$

$\sigma_{m}(\Sigma_{v}^{2}(\Phi_{N}),L_{p})\leq
CR_{1}^{-1}v^{1/2}\sqrt{p}m^{-\frac{1}{2}},\quad m=1,2,\cdots,N.$ (2.12)

Thus, Theorem 2.3 implies that for $p\in[2,\infty)$

$\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{p})\leq
C(R_{1})(p\log(2N/k))^{1/2}(v/k)^{1/2},\quad k=1,2,\dots,N.$ (2.13)

Second, by (2.9) we obtain

$\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{\infty})\leq
C_{0}\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{\log N}).$ (2.14)

Combining (2.13) and (2.14) we get

$\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{\infty})\leq C(R_{1},C_{0})(\log
N)(v/k)^{1/2},\quad k=1,2,\dots,N.$ (2.15)

Finally, for $k>N$ we use the inequalities

$\varepsilon_{k}(W,L_{\infty})\leq\varepsilon_{N}(W,L_{\infty})\varepsilon_{k-N}(X_{N}^{\infty},L_{\infty})$

and

$\varepsilon_{n}(X_{N}^{\infty},L_{\infty})\leq 3(2^{-n/N}),\qquad 2^{-x}\leq
1/x,\quad x\geq 1,$

to obtain (2.15) for all $k$. This completes the proof.

∎

##  3 A step from $p=2$ to $1\leq p<2$

In this section we show how Theorem 2.5 proved in Section 2 for $p=2$ can be
extended to the case $1\leq p<2$. This extension step is based on a general
inequality for the entropy. For convenience, we set
$\Sigma_{v}({\mathcal{D}}_{N})=X_{N}:=[{\mathcal{D}}_{N}]$ for $v>N$.

######  Lemma 3.1.

For $v=1,2,\dots,N$, $1\leq p<2<q\leq\infty$ and
$\theta:=(\frac{1}{2}-\frac{1}{q})/(\frac{1}{p}-\frac{1}{q})$, we have for
$\varepsilon>0$

${\mathcal{H}}_{\varepsilon}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{q})\leq\sum_{s=0}^{\infty}{\mathcal{H}}_{2^{-3}a^{s-1}\varepsilon^{\theta}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N});L_{q})+{\mathcal{H}}_{\varepsilon^{\theta}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N});L_{q}),$
(3.1)

where $a=a(\theta)=2^{\frac{\theta}{1-\theta}}$.

###### Proof.

In the case when $v=N$ Lemma 3.1 was proved in [7]. A slight modification of
the proof there works equally well for a general case of $1\leq v\leq N$. For
completeness, we include the proof of this lemma here. First, we note that for
any $\varepsilon_{1},\varepsilon_{2}>0$,

${\mathcal{H}}_{\varepsilon_{1}\varepsilon_{2}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{q})\leq{\mathcal{H}}_{\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2})+{\mathcal{H}}_{\varepsilon_{2}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N});L_{q}).$
(3.2)

To see this, let $x_{1},\cdots,x_{N_{1}}\in\Sigma_{v}^{p}({\mathcal{D}}_{N})$
and $y_{1},\cdots,y_{N_{2}}\in\Sigma_{2v}^{2}({\mathcal{D}}_{N})$ be such that

$\Sigma_{v}^{p}({\mathcal{D}}_{N})\subset\bigcup_{i=1}^{N_{1}}\left(x_{i}+\varepsilon_{1}B_{L_{2}}\right)\
\ \text{and}\ \
\Sigma_{2v}^{2}({\mathcal{D}}_{N})\subset\bigcup_{j=1}^{N_{2}}(y_{j}+\varepsilon_{2}B_{L_{q}}),$

where $N_{1}=N_{\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N}),L_{2})$ and
$N_{2}=N_{\varepsilon_{2}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N}),L_{q})$. Since
$\Sigma_{v}({\mathcal{D}}_{N})+\Sigma_{v}({\mathcal{D}}_{N})\subset\Sigma_{2v}({\mathcal{D}}_{N})$,
we have

$\displaystyle\Sigma_{v}^{p}({\mathcal{D}}_{N})$
$\displaystyle\subset\bigcup_{i=1}^{N_{1}}\left(x_{i}+\varepsilon_{1}B_{L_{2}}\right)\cap\Sigma_{v}({\mathcal{D}}_{N})\subset\bigcup_{i=1}^{N_{1}}\left(x_{i}+\varepsilon_{1}\Sigma_{2v}^{2}({\mathcal{D}}_{N})\right)$
$\displaystyle\subset\bigcup_{i=1}^{N_{1}}\bigcup_{j=1}^{N_{2}}\left(x_{i}+\varepsilon_{1}y_{j}+\varepsilon_{1}\varepsilon_{2}B_{L_{q}}\right).$

Inequality (3.2) then follows.

Next, setting $\varepsilon_{1}:=\varepsilon^{1-\theta}$ and
$\varepsilon_{2}=\varepsilon^{\theta}$ in (3.2), we reduce to showing that

${\mathcal{H}}_{\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2})\leq\sum_{s=0}^{\infty}{\mathcal{H}}_{2^{-3}a^{s-1}\varepsilon^{\theta}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N});L_{q}).$
(3.3)

It will be shown that for $s=0,1,\ldots,$

$\displaystyle{\mathcal{H}}_{2^{s}\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2})-{\mathcal{H}}_{2^{s+1}\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2})\leq{\mathcal{H}}_{2^{-3}a^{s-1}\varepsilon^{\theta}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N});L_{q}),$
(3.4)

from which (3.3) will follow by taking the sum over $s=0,1,\ldots$

To show (3.4), for each nonnegative integer $s$, let
${\mathcal{F}}_{s}\subset\Sigma_{v}^{p}({\mathcal{D}}_{N})$ be a maximal
$2^{s}\varepsilon_{1}$-separated subset of $\Sigma_{v}^{p}({\mathcal{D}}_{N})$
in the metric $L_{2}$; that is, $\|f-g\|_{2}\geq 2^{s}\varepsilon_{1}$ for any
two distinct functions $f,g\in{\mathcal{F}}_{s}$, and
$\Sigma_{v}^{p}({\mathcal{D}}_{N})\subset\bigcup_{f\in{\mathcal{F}}_{s}}B_{L_{2}}(f,2^{s}\varepsilon_{1})$.
Then

${\mathcal{H}}_{2^{s}\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2})\leq\log_{2}|{\mathcal{F}}_{s}|\leq{\mathcal{H}}_{2^{s-1}\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2}).$
(3.5)

Let $f_{s}\in{\mathcal{F}}_{s+2}$ be such that

$\left|B_{L_{2}}(f_{s},2^{s+2}\varepsilon_{1})\cap{\mathcal{F}}_{s}\right|=\max_{f\in{\mathcal{F}}_{s+2}}\left|B_{L_{2}}(f,2^{s+2}\varepsilon_{1})\cap{\mathcal{F}}_{s}\right|.$

Since

$\displaystyle{\mathcal{F}}_{s}=\bigcup_{f\in{\mathcal{F}}_{s+2}}\left(B_{L_{2}}(f,2^{s+2}\varepsilon_{1})\cap{\mathcal{F}}_{s}\right)\subset\Sigma_{v}^{p}({\mathcal{D}}_{N}),$

it follows that

$\displaystyle|{\mathcal{F}}_{s}|\leq|{\mathcal{F}}_{s+2}|\left|B_{L_{2}}(f_{s},2^{s+2}\varepsilon_{1})\cap{\mathcal{F}}_{s}\right|.$
(3.6)

Set

${\mathcal{A}}_{s}:=\left\\{\frac{f-f_{s}}{2^{s+2}\varepsilon_{1}}:\ \ f\in
B_{L_{2}}(f_{s},2^{s+2}\varepsilon_{1})\cap{\mathcal{F}}_{s}\right\\}\subset\Sigma_{2v}({\mathcal{D}}_{N}).$

Clearly, for any $g\in{\mathcal{A}}_{s}$,

$\|g\|_{2}\leq 1,\ \ \|g\|_{p}\leq(2^{s+1}\varepsilon_{1})^{-1}.$ (3.7)

On the one hand, using (3.5) and (3.6), we obtain that

$\displaystyle\log_{2}|{\mathcal{A}}_{s}|$
$\displaystyle\geq\log_{2}|{\mathcal{F}}_{s}|-\log_{2}|{\mathcal{F}}_{s+2}|$
$\displaystyle\geq{\mathcal{H}}_{2^{s}\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2})-{\mathcal{H}}_{2^{s+1}\varepsilon_{1}}(\Sigma_{v}^{p}({\mathcal{D}}_{N});L_{2}).$
(3.8)

On the other hand, since $\frac{1}{2}=\frac{\theta}{p}+\frac{1-\theta}{q}$,
using (3.7) and the fact that ${\mathcal{F}}_{s}$ is
$2^{s}\varepsilon_{1}$-separated in the $L_{2}$-metric, we have that for any
two distinct $g^{\prime},g\in{\mathcal{A}}_{s}$,

$\displaystyle
2^{-2}\leq\|g^{\prime}-g\|_{2}\leq\|g^{\prime}-g\|_{p}^{\theta}\|g-g^{\prime}\|_{q}^{1-\theta}\leq\left(2^{s+1}\varepsilon_{1}\right)^{-\theta}\|g-g^{\prime}\|_{q}^{1-\theta},$

which implies that

$\|g^{\prime}-g\|_{q}\geq
2^{-2}(2^{s-1}\varepsilon_{1})^{\frac{\theta}{1-\theta}}=2^{-2}a^{s-1}\varepsilon^{\theta}.$

This together with (3.7) means that ${\mathcal{A}}_{s}$ is a
$2^{-2}a^{s-1}\varepsilon^{\theta}$-separated subset of
$\Sigma_{2v}^{2}({\mathcal{D}}_{N})$ in the metric $L_{q}$. We obtain

$\displaystyle\log_{2}|{\mathcal{A}}_{s}|\leq{\mathcal{H}}_{2^{-3}a^{s-1}\varepsilon^{\theta}}(\Sigma_{2v}^{2}({\mathcal{D}}_{N});L_{q}).$
(3.9)

Thus, combining (3.9) with (3), we prove inequality (3.4). ∎

Lemma 3.1 with $1\leq p<2$, $q=\infty$, $\theta=p/2$ and Theorem 2.5 imply the
following bound for the entropy numbers.

######  Theorem 3.1.

Assume that $\Phi_{N}$ is a uniformly bounded Riesz basis of
$X_{N}:=[\Phi_{N}]$ satisfying (2.9). Then for $1\leq p\leq 2$, we have

$\varepsilon_{k}(\Sigma_{v}^{p}(\Phi_{N}),L_{\infty})\leq
C(p,R_{1},C_{0})(\log N)^{2/p}(v/k)^{1/p},\quad k=1,2,\dots.$ (3.10)

##  4 Proof of Theorem 1.3

Theorem 3.1 provides bounds on the entropy numbers
$\varepsilon_{k}(\Sigma_{v}^{p}(\Phi_{N}),L_{\infty})$ under additional
assumption (2.9). Thus, a combination of Theorem 3.1 with Theorem 2.2 implies
the statement of Theorem 1.3 under extra assumption (2.9). However, (2.9) is
not assumed in Theorem 1.3. Below we give a proof of Theorem 1.3.

We need the following lemma proved in [7].

######  Lemma 4.1.

[7, Lemma 4.3] Let $1\leq p<\infty$ be a fixed number. Assume that $X_{N}$ is
an $N$-dimensional subspace of $L_{\infty}(\Omega)$ satisfying the following
condition: for some parameter $\beta>0$ and constant $K\geq 2$

$\|f\|_{\infty}\leq(KN)^{\frac{\beta}{p}}\|f\|_{p},\ \ \forall f\in X_{N}.$
(4.1)

Let $\\{\xi_{j}\\}_{j=1}^{\infty}$ be a sequence of independent random points
selected uniformly from the probability space $(\Omega,\mu)$. Then there
exists a positive constant $C_{\beta}$ depending only on $\beta$ such that for
any $0<\varepsilon\leq\frac{1}{2}$ and any integer

$m\geq
C_{\beta}K^{\beta}\varepsilon^{-2}(\log\frac{2}{\varepsilon})N^{\beta+1}\log
N,$ (4.2)

the inequality

$\displaystyle(1-\varepsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi_{j})|^{p}\leq(1+\varepsilon)\|f\|_{p}^{p},$
(4.3)

holds with probability $\geq 1-m^{-N/\log K}$.

For a set $\Omega_{m}:=\\{x_{1},\cdots,x_{m}\\}\subset\Omega$ and a function
$f:\Omega_{m}\to{\mathbb{R}}$, we define
$\|f\|_{L_{\infty}(\Omega_{m})}:=\max_{1\leq j\leq m}|f(x_{j})|$ and

$\|f\|_{L_{q}(\Omega_{m})}:=\Bigl{(}\frac{1}{m}\sum_{j=1}^{m}|f(x_{j})|^{q}\Bigr{)}^{\frac{1}{q}}\
\ \text{for $q<\infty$}.$

Now we turn to the proof of Theorem 1.3. Recall that we do not assume (2.9).
First, since the Riesz basis $\Phi_{N}:=\\{\varphi_{j}\\}_{j=1}^{N}$ is
uniformly bounded by $1$ on $\Omega$, we have by (2.8)

$\|f\|_{\infty}\leq R_{1}^{-1}N^{\frac{1}{2}}\|f\|_{2},\ \ \forall f\in
X_{N},$

which in turn implies that

$\|f\|_{\infty}\leq C(R_{1})N^{\frac{1}{p}}\|f\|_{p},\ \ \forall f\in X_{N},\
\ 1\leq p\leq 2.$

Thus, by Lemma 4.1 with $\beta=1$, there exists a discrete set
$\Omega_{m_{1}}:=\\{\xi^{1},\cdots,\xi^{m_{1}}\\}\subset\Omega$ with

$C^{-1}N^{2}\log N\leq m_{1}\leq CN^{2}\log N$

such that for all $f\in X_{N}$,

$\displaystyle\frac{4}{5}\|f\|_{p}^{p}\leq\|f\|_{L_{p}(\Omega_{m_{1}})}^{p}\leq\frac{6}{5}\|f\|_{p}^{p}\
\ \text{and}\ \
\frac{4}{5}\|f\|_{2}^{2}\leq\|f\|_{L_{2}(\Omega_{m_{1}})}^{2}\leq\frac{6}{5}\|f\|_{2}^{2},$
(4.4)

where $C>1$ is an absolute constant.

Second, we consider the discrete norm $\|\cdot\|_{L_{p}(\Omega_{m_{1}})}$
instead of the norm $\|\cdot\|_{L_{p}(\Omega)}$. By (4.4), $\Phi_{N}$ is a
uniformly bounded Riesz basis of the space
$(X_{N},\|\cdot\|_{L_{2}(\Omega_{m_{1}})})$, and moreover,

$\|f\|_{L_{\infty}(\Omega_{m_{1}})}\leq
C(p,R_{1},R_{2})v^{1/p}\|f\|_{L_{p}(\Omega_{m_{1}})},\ \ \forall
f\in\Sigma_{v}(\Phi_{N}).$

Since $\log m_{1}\sim\log N$, by the regular Nikolskii inequality for the
norms $\ell_{q}^{m_{1}}$, $1\leq q\leq\infty$, we also have

$\|f\|_{L_{\infty}(\Omega_{m_{1}})}\leq C\|f\|_{L_{\log N}(\Omega_{m_{1}})},\
\ \forall f\in X_{N},$

where $C>1$ is an absolute constant. Thus, by Theorem 2.2 and Theorem 3.1
applied to the discrete norm $\|\cdot\|_{L_{p}(\Omega_{m_{1}})}$, we can find
a subset $\Omega_{m}\subset\Omega_{m_{1}}$ with

$m=|\Omega_{m}|\leq C(p,R_{1},R_{2})v(\log N)^{2}(\log(2v))^{2}$

such that for any $f\in\Sigma_{v}(\Phi_{N})$,

$\frac{3}{4}\|f\|_{L_{p}(\Omega_{m_{1}})}^{p}\leq\|f\|_{L_{p}(\Omega_{m})}^{p}\leq\frac{5}{4}\|f\|_{L_{p},(\Omega_{m_{1}})}^{p}.$
(4.5)

Combining (4.4) with (4.5), we obtain the stated result of Theorem 1.3.

##  5 A refined version of the conditional theorem

Let us first recall some notations. Let $(\Omega,\mu)$ be a probability space.
For $1\leq p\leq\infty$, denote by $L_{p}(\Omega)$ the usual Lebesgue space
$L_{p}$ defined with respect to the measure $\mu$ on $\Omega$, and by
$\|\cdot\|_{p}$ the norm of $L_{p}(\Omega)$. We also set

$B_{L_{p}}:=\\{f\in L_{p}(\Omega):\ \ \|f\|_{p}\leq 1\\},\ \ 1\leq
p\leq\infty.$

In this section, we prove a refined version of the conditional theorem for
sampling discretization of all integral norms $L_{q}$ of functions from a more
general subset $\mathcal{W}\subset L_{\infty}$, which allows us to estimate
the number of points needed for the sampling discretization in terms of an
integral of the $\varepsilon$-entropy
$\mathcal{H}_{\varepsilon}(\mathcal{W},L_{\infty})$, $\varepsilon>0$.

######  Theorem 5.1.

Let $1\leq p<\infty$, and let $\mathcal{W}$ be a set of uniformly bounded
functions on $\Omega$ with

$1\leq R:=\sup_{f\in\mathcal{W}}\sup_{x\in\Omega}|f(x)|<\infty.$

Assume that ${\mathcal{H}}_{t}(\mathcal{W},L_{\infty})<\infty$ for every
$t>0$, and

$(\lambda\cdot\mathcal{W})\cap B_{L_{p}}\subset\mathcal{W}\subset B_{L_{p}},\
\ \ \forall\lambda>0.$ (5.1)

Then there exist positive constants $C_{p},c_{p}$ depending only on $p$ such
that for any $\varepsilon\in(0,1)$ and any integer

$m\geq
C_{p}\varepsilon^{-5}\left(\int_{10^{-1}\varepsilon^{1/p}}^{R}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{R}\frac{{\mathcal{H}}_{c_{p}\varepsilon
t}(\mathcal{W},L_{\infty})}{t}\,dt\Bigr{)}^{\frac{1}{2}}du\right)^{2},$ (5.2)

there exist $m$ points $x_{1},\cdots,x_{m}\in\Omega$ such that for all
$f\in\mathcal{W}$,

$(1-\varepsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(x_{j})|^{p}\leq(1+\varepsilon)\|f\|_{p}^{p}.$
(5.3)

In particular, Theorem 5.1 allows us to prove refined versions of Theorem 2.2
and Theorem 1.3, where the constants in the Marcinkiewicz type discretization
are replaced by $1-\varepsilon$ and $1+\varepsilon$ for an arbitrarily given
$\varepsilon\in(0,1)$.

First, we have the following refined version of Theorem 2.2.

######  Corollary 5.1.

Let $1\leq q<\infty$ and $1\leq v\leq N$. Suppose that a dictionary
${\mathcal{D}}_{N}$ is such that

$\varepsilon_{k}(\Sigma_{v}^{q}({\mathcal{D}}_{N}),L_{\infty})\leq
B_{1}(v/k)^{1/q},\quad k=1,2,\cdots,$ (5.4)

where $B_{1}\geq 1$. Assume in addition that there exists a constant
$B_{2}\geq 1$ such that

$\|f\|_{\infty}\leq B_{2}v^{1/q}\|f\|_{q},\ \ \forall
f\in\Sigma_{v}^{q}({\mathcal{D}}_{N}).$ (5.5)

Then for a large enough constant $C(q)$ and any $\varepsilon\in(0,1)$, there
exist $m$ points $\xi^{1},\cdots,\xi^{m}\in\Omega$ with

$m\leq C(q)\varepsilon^{-5-q}vB_{1}^{q}(\log(B_{2}v/\varepsilon))^{2}$

such that for any $f\in\Sigma_{v}({\mathcal{D}}_{N})$

$(1-\varepsilon)\|f\|_{q}^{q}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{q}\leq(1+\varepsilon)\|f\|_{q}^{q}.$

###### Proof of Corollary 5.1.

We apply Theorem 5.1 to $p=q$,
$\mathcal{W}:=\Sigma_{v}^{q}({\mathcal{D}}_{N})$ and $R=B_{2}v^{1/q}$. It is
clear that $\mathcal{W}$ satisfies (5.1) with $p=q$. Furthermore, (5.4)
implies that (see by [7, Lemma 2.1])

${\mathcal{H}}_{t}(\mathcal{W},L_{\infty})\leq C(q)v\cdot(B_{1}/t)^{q},\ \
t>0.$ (5.6)

Finally, a straightforward calculation using (5.6) then shows that

$\displaystyle\varepsilon^{-5}\left(\int_{10^{-1}\varepsilon^{1/q}}^{B_{2}v^{1/q}}u^{\frac{q}{2}-1}\Bigl{(}\int_{u}^{B_{2}v^{1/q}}\frac{{\mathcal{H}}_{c_{q}\varepsilon
t}(\mathcal{W},L_{\infty})}{t}\,dt\Bigr{)}^{\frac{1}{2}}du\right)^{2}$
$\displaystyle\leq
C(q)\varepsilon^{-5-q}B_{1}^{q}v(\log(B_{2}v/\varepsilon))^{2}.$

Corollary 5.1 then follows from Theorem 5.1. ∎

Using Corollary 5.1 and following the proof in Section 4, we can also obtain
the $\varepsilon$-version of Theorem 1.3.

######  Corollary 5.2.

Let $\Phi_{N}$ be a uniformly bounded Riesz basis of
$X_{N}:=\operatorname{span}(\Phi_{N})\subset L_{2}(\Omega)$ satisfying (2.8)
for some constants $0<R_{1}\leq R_{2}$. Let $1\leq p\leq 2$, and let $1\leq
v\leq N$ be an integer. Then for a large enough constant $C=C(p,R_{1},R_{2})$,
and any $\varepsilon\in(0,1)$, there exist $m$ points
$\xi^{1},\cdots,\xi^{m}\in\Omega$ with

$m\leq C\varepsilon^{-p-5}v(\log N)^{2}(\log(2v\varepsilon^{-1}))^{2}$

such that for any $f\in\Sigma_{v}(\Phi_{N})$ we have

$(1-\varepsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\varepsilon)\|f\|_{p}^{p}.$

The rest of this section is devoted to the proof of Theorem 5.1, which is
close to the proof of Theorem 2.1 from Section 2 given in [6]. We need the
following lemma:

######  Lemma 5.1.

[6, Lemma 2.4] Let $\\{{\mathcal{F}}_{j}\\}_{j\in G}$ be a collection of
finite sets of bounded functions from $L_{1}(\Omega,\mu)$. Assume that for
each $j\in G$ and all $f\in{\mathcal{F}}_{j}$ we have

$\|f\|_{1}\leq 1,\quad\|f\|_{\infty}:=\sup_{x\in\Omega}|f(x)|\leq M_{j}.$

Suppose that positive numbers $\eta_{j}$ $\in(0,1)$ and a natural number $m$
satisfy the condition

$2\sum_{j\in
G}|{\mathcal{F}}_{j}|\exp\left(-\frac{m\eta_{j}^{2}}{8M_{j}}\right)<1.$

Then there exists a set $\xi=\\{\xi^{\nu}\\}_{\nu=1}^{m}\subset\Omega$ such
that for each $j\in G$ and for all $f\in{\mathcal{F}}_{j}$ we have

$\left|\|f\|_{1}-\frac{1}{m}\sum_{\nu=1}^{m}|f(\xi^{\nu})|\right|\leq\eta_{j}.$

###### Proof of Theorem 5.1.

Let

$\mathcal{W}_{1}:=\\{f/{\|f\|_{p}}:\ \ f\in\mathcal{W}\setminus\\{0\\}\\}.$

Clearly, $\mathcal{W}_{1}\subset\mathcal{W}$, and it suffices to prove (5.3)
for all $f\in\mathcal{W}_{1}$. Let $c^{\ast}=c_{p}^{\ast}\in(0,\frac{1}{2})$
be a sufficiently small constant depending only on $p$. Let
$a:=c^{\ast}\varepsilon$. Let $J,j_{0}$ be two integers such that $j_{0}<0\leq
J$,

$(1+a)^{J-1}\leq R<(1+a)^{J}\ \ \text{and}\ \
(1+a)^{j_{0}p}\leq\frac{1}{5}\varepsilon\leq(1+a)^{(j_{0}+1)p}.$ (5.7)

For $j\in\mathbb{Z}$, let

${\mathcal{A}}_{j}:=\mathcal{N}_{a(1+a)^{j}}(\mathcal{W}_{1},L_{\infty})\subset\mathcal{W}_{1}$

denote the minimal $a(1+a)^{j}$-net of $\mathcal{W}_{1}$ in the norm of
$L_{\infty}$. For $j\in\mathbb{Z}$ and $f\in\mathcal{W}_{1}$, we define
$A_{j}(f)$ to be the function in ${{\mathcal{A}}}_{j}$ that is closest to $f$
in the $L_{\infty}$ norm. Thus, $\|A_{j}(f)-f\|_{\infty}\leq a(1+a)^{j}$ for
all $f\in\mathcal{W}_{1}$ and $j\in\mathbb{Z}$.

Next, for $f\in\mathcal{W}_{1}$ and $j>j_{0}$, define

$U_{j}(f):=\\{\mathbf{x}\in\Omega:|A_{j}(f)(\mathbf{x})|\geq(1+a)^{j-1}\\},$

and

$D_{j}(f):=U_{j}(f)\setminus\bigcup_{k\geq j+1}U_{k}(f).$

We also set

$D_{j_{0}}(f):=\Omega\setminus\bigcup_{k>j_{0}}U_{k}(f).$

Note that by (5.7), $U_{j}(f)=\emptyset$ for $j>J$. Thus, $\\{D_{j}(f):\ \
j=j_{0},\cdots,J\\}$ forms a partition of the domain $\Omega$. Define

$h(f,\mathbf{x}):=\sum_{j=j_{0}+1}^{J}(1+a)^{j}\chi_{D_{j}(f)}(\mathbf{x}),$
(5.8)

where $\chi_{E}(\mathbf{x})$ is a characteristic function of a set $E$.

For $\mathbf{x}\in D_{j_{0}}(f)$, we have

$\displaystyle|f(\mathbf{x})|$
$\displaystyle\leq|A_{j_{0}+1}f(\mathbf{x})|+a(1+a)^{j_{0}+1}\leq(1+a)^{j_{0}}+a(1+a)^{j_{0}+1}$
$\displaystyle\leq(1+a)^{j_{0}}(1+2a),$

which in turn implies that

$|f(\mathbf{x})|^{p}\leq(1+a)^{j_{0}p}(1+2a)^{p}\leq(1+a)^{j_{0}p}(1+C_{p}a)\leq\frac{5}{4}(1+a)^{j_{0}p}<\frac{1}{4}\varepsilon.$

On the other hand, for $f\in D_{j}(f)$ and $j_{0}<j\leq J$, we have

$\displaystyle|f(\mathbf{x})|$
$\displaystyle\geq|A_{j}f(\mathbf{x})|-a(1+a)^{j}\geq(1+a)^{j}(1-2a),\ \
\text{and}$ $\displaystyle|f(\mathbf{x})|$
$\displaystyle\leq|A_{j+1}f(\mathbf{x})|+a(1+a)^{j+1}\leq(1+a)^{j}(1+2a),$

which implies

$\Bigl{|}|f(\mathbf{x})|^{p}-(1+a)^{jp}\Bigr{|}\leq C_{p}a\leq
c^{\ast}C_{p}\varepsilon<\frac{\varepsilon}{4}.$

Therefore,

$\Bigl{|}|f(\mathbf{x})|^{p}-|h(f,\mathbf{x})|^{p}\Bigr{|}\leq\frac{\varepsilon}{4},\
\ \forall\mathbf{x}\in\Omega.$ (5.9)

For $j_{0}+1\leq j\leq J$, let

${\mathcal{F}}_{j}^{p}:=\left\\{(1+a)^{pj}\chi_{D_{j}(f)}:\
f\in\mathcal{W}_{1}\right\\}.$

Our aim is to find $m$ points $\xi^{1},\cdots,\xi^{m}\in\Omega$ for each $m$
satisfying (5.2) so that the following inequality holds for all
$f\in{\mathcal{F}}_{j}^{p}$ and $j_{0}<j\leq J$:

$\displaystyle\Bigl{|}\frac{1}{m}\sum_{k=1}^{m}f(\xi^{k})-\int_{\Omega}f(x)\,d\mu(x)\Bigr{|}\leq\varepsilon_{j},$
(5.10)

where $\\{\varepsilon_{j}\\}_{j=j_{0}+1}^{J}\subset(0,1)$ satisfies
$\sum_{j=j_{0}+1}^{J}\varepsilon_{j}\leq\varepsilon/4$. Once (5.10) is proved,
we obtain by (5.8) that

$\displaystyle\Bigl{|}\frac{1}{m}\sum_{j=1}^{m}|h(f,\xi^{j})|^{p}-\|h(f)\|_{p}^{p}\Bigr{|}\leq\frac{\varepsilon}{4}.$
(5.11)

which, applying (5.9), will prove the desired inequality (5.3).

To see this, we apply Lemma 5.1 for the collection of the above sets
${\mathcal{F}}_{j}^{p}$, and notice that for $j_{0}<j\leq J$,

$\|(1+a)^{pj}\chi_{D_{j}(f)}\|_{1}\leq\|h(f)\|_{p}^{p}\leq\|f\|_{p}^{p}+\frac{\varepsilon}{4}\leq
2$

and

$\|(1+a)^{pj}\chi_{D_{j}(f)}\|_{\infty}\leq(1+a)^{pj}=:M_{j}.$

Thus, by Lemma 5.1, it suffices to show that for each integer $m$ satisfying
(5.2), one can find a sequence $\\{\varepsilon_{j}\\}_{j_{0}<j\leq
J}\subset(0,1)$ such that

$\displaystyle\sum_{j_{0}<j\leq J}\varepsilon_{j}\leq\frac{\varepsilon}{4}$
(5.12)
$\displaystyle\sum_{j=j_{0}+1}^{J}|{\mathcal{F}}_{j}^{p}|\exp\Bigl{(}-\frac{m\varepsilon_{j}^{2}}{8M_{j}}\Bigr{)}<\frac{1}{2}.$
(5.13)

To this end, we need to estimate the cardinalities of the sets
${\mathcal{F}}_{j}^{p}$. By definition, for each $j_{0}<j\leq J$, the set
$D_{j}(f)$ is uniquely determined by the functions
$A_{k}(f)\in{\mathcal{A}}_{k}$, $j\leq k\leq J$. As a result, we have

$|{\mathcal{F}}_{j}^{p}|\leq|{\mathcal{A}}_{j}|\times\cdots\times|{\mathcal{A}}_{J}|=:L_{j},$

and

$\displaystyle\log L_{j}$
$\displaystyle\leq\sum_{k=j}^{J}\log|{\mathcal{A}}_{k}|\leq\sum_{k=j}^{J}{\mathcal{H}}_{a(1+a)^{k}}(\mathcal{W},L_{\infty})$
$\displaystyle\leq\frac{1}{\log(1+a)}\sum_{k=j}^{J}\int_{a(1+a)^{k-1}}^{a(1+a)^{k}}{\mathcal{H}}_{t}(\mathcal{W},L_{\infty})\frac{dt}{t}$
$\displaystyle\leq
C\varepsilon^{-1}\int_{(1+a)^{j-1}}^{R}{\mathcal{H}}_{at}(\mathcal{W},L_{\infty})\frac{dt}{t}.$
(5.14)

For each $j_{0}<j\leq J$, we choose $\varepsilon_{j}>0$ so that

$\displaystyle\log(\lambda L_{j})=\frac{m\varepsilon_{j}^{2}}{16M_{j}},\ \ \
\text{that is}\ \ \varepsilon_{j}:=4\sqrt{M_{j}}\sqrt{\log(\lambda
L_{j})}m^{-\frac{1}{2}},$ (5.15)

where $\lambda>1$ is a large absolute constant to be specified later. Then

$\displaystyle\sum_{j=j_{0}+1}^{J}\varepsilon_{j}$
$\displaystyle=4m^{-1/2}\sum_{j=j_{0}+1}^{J}(M_{j}\log(\lambda
L_{j}))^{\frac{1}{2}}$ $\displaystyle\leq
4m^{-1/2}\sqrt{\log\lambda}\sum_{j=j_{0}+1}^{J}(M_{j}\log(L_{j}))^{\frac{1}{2}},$

and hence (5.12) is ensured once

$m\geq\varepsilon^{-2}\Bigl{(}\sqrt{\log\lambda}\sum_{j=j_{0}+1}^{J}(M_{j}\log(L_{j}))^{\frac{1}{2}}\Bigr{)}^{2}.$
(5.16)

However, using (5.14), we have

$\displaystyle\sum_{j=j_{0}+1}^{J}(M_{j}\log L_{j})^{\frac{1}{2}}$
$\displaystyle\leq
C\varepsilon^{-\frac{1}{2}}\sum_{j=j_{0}+1}^{J}(1+a)^{pj/2}\Bigl{(}\int_{(1+a)^{j-1}}^{R}{\mathcal{H}}_{at}(\mathcal{W},L_{\infty})\frac{dt}{t}\Bigr{)}^{\frac{1}{2}}$
$\displaystyle\leq
C_{p}\varepsilon^{-\frac{3}{2}}\sum_{j=j_{0}+1}^{J}\int_{(1+a)^{j-2}}^{(1+a)^{j-1}}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{R}{\mathcal{H}}_{at}(\mathcal{W},L_{\infty})\frac{dt}{t}\Bigr{)}^{\frac{1}{2}}du$
$\displaystyle\leq
C_{p}\varepsilon^{-\frac{3}{2}}\int_{10^{-1}\varepsilon^{1/p}}^{R}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{R}{\mathcal{H}}_{c_{p}\varepsilon
t}(\mathcal{W},L_{\infty})\frac{dt}{t}\Bigr{)}^{\frac{1}{2}}du.$

This combined with (5.16) implies that (5.12) is ensured by (5.2).

Finally, we prove (5.13). Indeed, using (5.15), we have

$\displaystyle\sum_{j=j_{0}+1}^{J}|{\mathcal{F}}_{j}^{p}|\exp\Bigl{(}-\frac{m\varepsilon_{j}^{2}}{8M_{j}}\Bigr{)}\leq\lambda\sum_{j=j_{0}+1}^{J}L_{j}\exp\Bigl{(}-\frac{m\varepsilon_{j}^{2}}{8M_{j}}\Bigr{)}=\sum_{j=j_{0}+1}^{J}\exp\Bigl{(}\log(\lambda
L_{j})-\frac{m\varepsilon_{j}^{2}}{8M_{j}}\Bigr{)}$
$\displaystyle=\sum_{j=j_{0}+1}^{J}\exp\Bigl{(}-\log(\lambda
L_{j})\Bigr{)}=\frac{1}{\lambda}\sum_{j=j_{0}+1}^{J}\frac{1}{L_{j}}\leq\frac{1}{\lambda}\sum_{j=j_{0}+1}^{J}\frac{1}{N_{a(1+a)^{j}}(\mathcal{W},L_{\infty})},$

where the last step uses the fact that

$L_{j}\geq|{\mathcal{A}}_{j}|=N_{a(1+a)^{j}}(\mathcal{W},L_{\infty}).$

We claim that

${\mathcal{H}}_{t}(\mathcal{W},L_{\infty})\geq\log\frac{R}{4t},\ \ \ \forall
0<t<R.$ (5.17)

To see this, let $f^{\ast}\in\mathcal{W}$ be such that
$\|f^{\ast}\|_{\infty}=R$. Let $k=[\frac{R}{t}]$. Define
$f_{j}=\frac{2jt}{R}f^{\ast}$ for $0\leq j\leq k/2$. Then $\\{f_{j}\\}_{0\leq
j\leq\frac{k}{2}}\subset\mathcal{W}$ is $2t$-separated in $L_{\infty}$-norm.
It follows that

$N_{t}(\mathcal{W},L_{\infty})\geq\frac{k}{2}\geq\frac{1}{4}\frac{R}{t},$

which shows (5.17).

Now using (5.17), we obtain

$\displaystyle\frac{1}{\lambda}\sum_{j=j_{0}+1}^{J}\frac{1}{N_{a(1+a)^{j}}(\mathcal{W},L_{\infty})}\leq
CR^{-1}\lambda^{-1}\sum_{j=j_{0}+1}^{J}(1+a)^{j}\leq C\lambda^{-1}<1,$

provided that $\lambda>1$ is large enough. This proves (5.13).

∎

##  6  Concluding remarks on sampling discretization of $L_{p}$ norms for
$2<p<\infty$

In this section, we give a few remarks on sampling discretization of $L_{p}$
norms for $2<p<\infty$.

  1. 1.

The following Nikolskii type inequality plays an important role in the proof
of Theorem 1.3:

$\|f\|_{\infty}\leq Cv^{\frac{1}{p}}\|f\|_{p},\ \ \ \forall
f\in\Sigma_{v}(\Phi_{N}),$ (6.1)

where the constant $C$ is independent of $f$, $v$ and $N$. This inequality
holds for $1\leq p\leq 2$ whenever $\Phi_{N}$ is a uniformly bounded Riesz
basis of $X_{N}$. However, this is no longer true for $p>2$. For example, take
$N=2^{v}$ and consider the system

$\Phi_{N}=\\{e^{2\pi ijx}\\}_{j=1}^{N}$

on the interval $[0,1]$ equipped with the usual Lebesgue measure. By the
Littlewood-Paley inequality, we have that for
$f(x)=\sum_{j=1}^{v}e^{2\pi\mathbf{i}2^{j}x}\in\Sigma_{v}(\Phi_{N})$ and
$2<p<\infty$,

$\displaystyle\|f\|_{\infty}=v>Cv^{\frac{1}{p}}\|f\|_{p}\asymp
v^{\frac{1}{2}+\frac{1}{p}}.$

  2. 2.

Let $\Phi_{N}$ be a uniformly bounded Riesz basis of $X_{N}\subset L_{2}$
satisfying (2.9). By monotonicity of the $L_{p}$ norms, we have that for any
integer $1\leq v\leq N$,

$\Sigma^{p}_{v}(\Phi_{N})\subset\Sigma^{2}_{v}(\Phi_{N}),\ \ p>2,$

which in particular implies that

$\sup_{f\in\Sigma_{v}^{p}(\Phi_{N})}\|f\|_{\infty}\leq\sup_{f\in\Sigma_{v}^{2}(\Phi_{N})}\|f\|_{\infty}\leq
Cv^{1/2}.$

Moreover, using Theorem 2.5, we have that for $p>2$ and all integer $k\geq 1$,

$\varepsilon_{k}(\Sigma_{v}^{p}(\Phi_{N}),L_{\infty})\leq\varepsilon_{k}(\Sigma_{v}^{2}(\Phi_{N}),L_{\infty})\leq
C\cdot(\log N)\Bigl{(}\frac{v}{k}\Bigr{)}^{1/2},$ (6.2)

which also yields

${\mathcal{H}}_{t}(\Sigma_{v}^{p}(\Phi_{N}),L_{\infty})\leq
C(p)v\cdot\Bigl{(}\frac{\log N}{t}\Bigr{)}^{2},\ \ \ \forall t>0.$ (6.3)

On the other hand, a straightforward calculation shows that for any
$\varepsilon\in(0,1)$ and $p>2$,

$\displaystyle\varepsilon^{-5}\left(\int_{10^{-1}\varepsilon^{1/p}}^{Cv^{1/2}}u^{\frac{p}{2}-1}\Bigl{(}\int_{u}^{Cv^{1/2}}\frac{{\mathcal{H}}_{c_{p}\varepsilon
t}(\Sigma_{v}^{p}(\Phi_{N}),L_{\infty})}{t}\,dt\Bigr{)}^{\frac{1}{2}}du\right)^{2}$
$\displaystyle\leq C(p)\varepsilon^{-7}v^{p/2}(\log N)^{2}.$

Thus, an application of Theorem 5.1 leads to

######  Theorem 6.1.

Assume that $\Phi_{N}$ is a uniformly bounded Riesz basis of
$X_{N}:=\operatorname{span}(\Phi_{N})$ satisfying (2.8) for some constants
$0<R_{1}\leq R_{2}$. Let $2<p<\infty$ and let $1\leq v\leq N$ be an integer.
Then for a large enough constant $C=C(p,R_{1},R_{2})$ and any
$\varepsilon\in(0,1)$, there exist $m$ points
$\xi^{1},\cdots,\xi^{m}\in\Omega$ with

$m\leq C\varepsilon^{-7}v^{p/2}(\log N)^{2},$

such that for any $f\in\Sigma_{v}(\Phi_{N})$,

$(1-\varepsilon)\|f\|_{p}^{p}\leq\frac{1}{m}\sum_{j=1}^{m}|f(\xi^{j})|^{p}\leq(1+\varepsilon)\|f\|_{p}^{p}.$

## References

  * [1] J. Batson, D.A. Spielman, and N. Srivastava, Twice-Ramanujan Sparsifiers, SIAM J. Comput., 41 (2012), 1704–1721.
  * [2] E. S. Belinskii, Decomposition theorems and approximation by a ”floating” system of exponentials. Trans. Amer. Math. Soc. 350 (1998), no. 1, 43–53.
  * [3] J. Bourgain, J. Lindenstrauss and V. Milman, Approximation of zonoids by zonotopes, Acta Math., 162 (1989), 73–141.
  * [4] B. Carl, Entropy numbers, $s$-numbers, and eigenvalue problems, J. Funct. Analysis, 41 (1981), 290–306.
  * [5] F. Dai, A. Prymak, V.N. Temlyakov, and S. Tikhonov, Integral norm discretization and related problems, Russian Math. Surveys 74 (2019), 579–630. Translation from Uspekhi Mat. Nauk 74 (2019), 3–58; arXiv:1807.01353v1.
  * [6] F. Dai, A. Prymak, A. Shadrin, V.N. Temlyakov, and S. Tikhonov, Sampling discretization of integral norms, arXiv:2001.09320. To appear in Constructive Approximation.
  * [7] F. Dai, A. Prymak, A. Shadrin, V.N. Temlyakov, and S. Tikhonov, Entropy numbers and Marcinkiewicz-type discretization, J. of Funct. Anal.  281, No. 6.
  * [8] R. A. DeVore, and V. N. Temlyakov, V. N., Nonlinear approximation by trigonometric sums, J. Fourier Anal. Appl. 2 (1995), no. 1, 29-48.
  * [9] Ding Dũng, V.N. Temlyakov, and T. Ullrich, Hyperbolic Cross Approximation, Advanced Courses in Mathematics CRM Barcelona, Birkhäuser, 2018; arXiv:1601.03978v2.
  * [10] A. Hinrichs, J. Prochno, and J. Vybiral, Entropy numbers of embeddings of Schatten classes, J. Functional Analysis, 273 (2017), 3241–3261; arXiv:1612.08105v1.
  * [11] W.B. Johnson and G. Schechtman, Finite dimensional subspaces of $L_{p}$, Handbook of the geometry of Banach spaces, Vol. 1 (2001), 837–870, North-Holland, Amsterdam.
  * [12] E. Kosov, Marcinkiewicz-type discretization of $L_{p}$-norms under the Nikolskii-type inequality assumption, arXiv:2005.01674.
  * [13] A. Marcus, D.A. Spielman, and N. Srivastava, Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem, Annals of Math., 182 (2015), 327–350.
  * [14] S. Nitzan, A. Olevskii, and A. Ulanovskii, Exponential frames on unbounded sets, Proc. Amer. Math. Soc., 144 (2016),109–118.
  * [15] A. Pajor and N. Tomczak-Yaegermann, Subspaces of small codimension of finite-dimensional Banach spaces, Proc. Amer. Math. Soc., 97 (1986), 637–642.
  * [16] M. Rudelson, Almost orthogonal submatrices of an orthogonal matrix, Israel J. Math., 111 (1999), 143–155.
  * [17] G. Schechtman, Tight embedding of subspaces of $L_{p}$ in $\ell_{p}^{n}$ for even $p$, Proc. Amer. Math. Soc. 139 (2011), no. 12, 4419–4421.
  * [18] G. Schechtman, More on embedding subspaces of $L_{p}$ in $\ell^{n}_{r}$, Compositio Math., 61 (1987), no. 2, 159–169.
  * [19] C. Schütt, Entropy numbers of diagonal operators between symmetric Banach spaces, J. Approx. Theory, 40 (1984), 121–128.
  * [20] V.N. Sudakov, Gaussian random processes and measures of solid angles in Hilbert spaces, Sov. Math. Dokl., 12, (1971), 412–415.
  * [21] V.N. Temlyakov, Greedy Approximation, Cambridge University Press, 2011.
  * [22] V.N. Temlyakov, An inequality for the entropy numbers and its application, J. Approx. Theory , 173 (2013), 110–121.
  * [23] V.N. Temlyakov, On the entropy numbers of the mixed smoothness function classes, J. Approx. Theory, 207 (2017), 26–56; arXiv:1602.08712v1.
  * [24] V.N. Temlyakov, The Marcinkewiecz-type discretization theorems for the hyperbolic cross polynomials, Jaen Journal on Approximation, 9 (2017), No. 1, 37–63; arXiv: 1702.01617v2.
  * [25] V.N. Temlyakov, The Marcinkiewicz-type discretization theorems, Constr. Approx. 48 (2018), 337–369; arXiv: 1703.03743v1.
  * [26] V. N. Temlyakov, Multivariate Approximation, Cambridge University Press, 2018.
  * [27] A. Zygmund, Trigonometric Series, Cambridge University Press, 1959.
  * [28] V.N. Temlyakov, The Marcinkiewicz-type discretization theorems, Constr. Approx. 48 (2018), 337–369; arXiv: 1703.03743v1.
  * [29] V.N. Temlyakov, Universal discretization, Journal of Complexity, 47 (2018), 97–109; arXiv:1708.08544v1 [math.NA] 28 Aug 2017.
  * [30] V.N. Temlyakov, A remark on entropy numbers; arXiv:2008.13030.

F. Dai,  Department of Mathematical and Statistical Sciences
University of Alberta
Edmonton, Alberta T6G 2G1, Canada
E-mail<EMAIL_ADDRESS>
V.N. Temlyakov, University of South Carolina,
Steklov Institute of Mathematics,
Lomonosov Moscow State University,
and Moscow Center for Fundamental and Applied Mathematics.
E-mail<EMAIL_ADDRESS>