LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Logarithmic L-r covering bound for VC classes of sets

Statement

Let $C$ be a nonempty class of measurable subsets of a measurable space, with finite VC index $V$ as in Shattering, VC dimension, and first-unshattered index for set classes. Let $Q$ be a probability measure, $1 \leq r < \infty$ , and $0 < δ < 1$ . Put $K : = 3 e^{2} / (e - 1)$ . Then

$N (δ, C, L^{r} (Q)) \leq {[K δ^{- r} \log (\frac{3 e}{δ^{r}})]}^{V - 1} .$

For sets, $∥ 1_{C} - 1_{D} ∥_{Q, r} = Q (C △ D)^{1 / r}$ . In the case $V = 1$ , the exponent is zero and the class consists of one set modulo equality, so the bound is $N = 1$ .

Facts & Assumptions

Given: A nonempty measurable set class $C$ with finite VC index $V$ , a probability measure $Q$ , $1 \leq r < \infty$ , and $0 < δ < 1$ .

[F1]

For a set class, the $L^{r} (Q)$ distance is $Q (C △ D)^{1 / r}$ ; $N$ is the covering number with centers in the class, and $D$ uses strict pairwise separation (Covering, packing, bracketing numbers, and metric entropy).

[F2]

A nonempty class has VC dimension $d = V - 1$ when $V$ is its least positive unshattered size; traces on arbitrary finite ground sets define shattering (Shattering, VC dimension, and first-unshattered index for set classes).

[F3]

A family of subsets of $[n]$ with VC dimension at most $d$ has size at most $\sum_{j = 0}^{d} (\binom{n}{j})$ (Sauer–Shelah: a family on $[n]$ of VC dimension at most $d$ has at most $\sum_{i = 0}^{d} (\binom{n}{i})$ members).

[F4]

The finite product probability $Q^{\otimes n}$ exists and assigns a measurable rectangle $A_{1} \times \dots \times A_{n}$ mass $\prod_{i} Q (A_{i})$ (The product sigma-algebra and its finite iterates, For sigma-finite factors, the product measure exists, has the rectangle formula, is sigma-finite, and is unique).

[F5]

A finite union of events has probability at most the sum of their probabilities (Basic identities for a probability measure).

[F6]

For $0 \leq u \leq 1$ and a natural $n$ , $(1 - u)^{n} \leq e^{- n u}$ , and $1 + x \leq e^{x}$ for real $x$ ( $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ ).

[F7]

The finite binomial theorem is $(1 + x)^{n} = \sum_{j = 0}^{n} ι (\binom{n}{j}) x^{j}$ , where $ι$ is the canonical embedding of naturals into reals and powers are natural powers (The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$ , The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , The canonical natural $ι (n) = n \cdot 1_{F}$ of a field, Integer powers $a^{m}$ ).

[F8]

$N (ϵ, C, d) \leq D (ϵ, C, d) \leq N (ϵ / 2, C, d)$ with strict separation and closed-ball radii as stated (Packing and covering numbers with explicit radius conventions).

[F9]

$\log$ is the increasing inverse of the exponential, $\log e = 1$ , and $\exp (u + v) = \exp (u) \exp (v)$ (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm, The real exponential function and the number $e$ by a power series, The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ , The exponential function is strictly increasing).

[F10]

For $u > 0$ , $\log^{'} (u) = 1 / u$ ; derivative rules and the mean value theorem apply on compact intervals (The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t, Sums, scalar multiples, products and quotients: $(f + g)^{'} (c) = f^{'} (c) + g^{'} (c)$ , $(α f)^{'} (c) = α f^{'} (c)$ , $(f g)^{'} (c) = f^{'} (c) g (c) + f (c) g^{'} (c)$ , and $(f / g)^{'} (c) = (f^{'} (c) g (c) - f (c) g^{'} (c)) / g (c)^{2}$ when $g (c) \neq 0$ , The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

[F11]

Natural powers obey their recursive definition and are monotone in nonnegative bases (Integer powers $a^{m}$ , Monotonicity of $x \mapsto x^{n}$ and of $n \mapsto a^{n}$ ).

[F12]

For $a > 0$ , $a^{r} = \exp (r \log a)$ and positive-base real powers obey their product and iterated-power laws (Real powers for positive bases, with the zero-base positive-exponent convention, The exponent, product, quotient, and iterated-power laws for positive real bases and real exponents).

[F13]

For every $r > 0$ , $t \mapsto t^{r}$ is strictly increasing on $[0, \infty)$ (Positive real powers preserve measurability).

[F14]

The inequality $1 + x \leq e^{x}$ for $x \geq 0$ gives $e \geq 2$ by taking $x = 1$ ( $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ ).

[F15]

For a real $s$ , its integer part $k$ satisfies $k \leq s < k + 1$ , so $n : = k + 1$ obeys $s < n \leq s + 1$ (Integer part: for every real $x$ there is exactly one integer $m$ with $m \leq x < m + 1$ ).

Proof

Given: The class, measure, index, and radii in the statement.

1.1F2given

Put $d : = V - 1$ . If $d = 0$ and two sets $C, D \in C$ differed at a point $x$ , their traces on ${x}$ would be both $\emptyset$ and ${x}$ , so ${x}$ would be shattered, contradicting [F2]. Thus all class members are equal, $N (δ, C, L^{r} (Q)) = 1$ , and the bound holds.

1.2F1F4F15given

Suppose $d \geq 1$ . Fix any finite subfamily $C_{1}, \dots, C_{m}$ with pairwise $L^{r} (Q)$ distances greater than $δ$ , where $m \geq 2$ , and set $η : = δ^{r} \in (0, 1)$ and $s : = 2 \log (m) / η > 0$ . Let $k : = ⌊ s ⌋$ from [F15] and $n : = k + 1$ ; then $s < n \leq s + 1$ . Sample $X_{1}, \dots, X_{n}$ independently from $Q$ on the finite product probability space supplied by [F4].

1.3F9F10algebra

For $u \geq 1$ , define $h (u) : = u / e - \log u$ . By [F10], $h^{'} (u) = 1 / e - 1 / u$ , so the mean value theorem makes $h$ decreasing on $[1, e]$ and increasing on $[e, \infty)$ . Since $h (e) = 0$ by [F9], $\log u \leq u / e$ for every $u \geq 1$ .

2.1F1F4F5F6F13step 1.2algebra

For $j \neq k$ , the probability that $C_{j}$ and $C_{k}$ have identical traces on this sample is $[1 - Q (C_{j} △ C_{k})]^{n} \leq (1 - η)^{n} \leq e^{- n η}$ : strict separation and [F13] give $Q (C_{j} △ C_{k}) > δ^{r} = η$ , and then [F4] and [F6] apply. The union bound [F5] makes the probability of any collision at most $(\binom{m}{2}) e^{- n η} \leq (\binom{m}{2}) m^{- 2} < 1$ .

2.2F9F14givenalgebrastep 1.2

Define $B : = K η^{- 1} \log (3 e / η)$ . By [F9], $K = 3 e^{2} / (e - 1) > e$ ; by [F14], $e \geq 2$ ; also $η^{- 1} > 1$ and $\log (3 e / η) > \log e = 1$ . Hence $B > e \geq 2$ .

3.1F2F3step 2.1choose

Consequently some sample has $m$ distinct traces on $[n]$ . The induced trace family cannot shatter a set of indices containing a repeated sample value, because those two coordinates always have identical membership. Any shattered set of distinct sampled values is shattered by $C$ , so [F2] bounds its size by $d$ . Applying [F3] to the induced family gives $m \leq \sum_{j = 0}^{d} (\binom{n}{j})$ .

3.2F9F11step 2.2algebrastep 1.2

If $\log m \leq d$ , then $m \leq e^{d} < B^{d}$ by step 2.2 and monotonicity of the exponential.

4.1F6F7F11step 3.1algebrastep 2.2

If $d \geq n$ , [F7], [F11], and step 2.2 give $\sum_{j = 0}^{d} (\binom{n}{j}) = 2^{n} \leq 2^{d} < B^{d}$ , so step 3.1 gives $m < B^{d}$ . If $d < n$ , put $x : = d / n \in (0, 1)$ . For $j \leq d$ , the recursion $x^{k + 1} = x^{k} x$ and $0 < x < 1$ show successively that $x^{d} \leq x^{j}$ . Thus [F7] and [F6] give $x^{d} \sum_{j = 0}^{d} (\binom{n}{j}) \leq \sum_{j = 0}^{d} (\binom{n}{j}) x^{j} \leq (1 + x)^{n} \leq e^{n x} = e^{d}$ , hence $\sum_{j = 0}^{d} (\binom{n}{j}) \leq (e n / d)^{d}$ . By step 3.1, $m \leq (e n / d)^{d}$ .

5.1F9F12step 3.1step 4.1algebrastep 1.2

Suppose $\log m > d$ . Then $n \geq 2 \log (m) / η > 2 d$ , so $d < n$ , and $\log (m) / η > 1$ gives $n \leq 3 \log (m) / η$ . Combining steps 3.1 and 4.1 yields $m \leq (3 e \log (m) / (d η))^{d}$ . Set $y : = 3 e / η$ and $z : = \exp ((\log m) / d) > e$ . By [F9] and [F12], $z^{d} = m$ and $\log z = (\log m) / d$ , hence $z / \log z \leq y$ .

6.1F9F11step 5.1step 1.3algebra

In step 5.1, $z > e$ implies $u : = \log z > 1$ . From $z \leq y \log z$ , monotonicity and the product law in [F9] give $u \leq \log y + \log u \leq \log y + u / e$ by step 1.3. Thus $u \leq \frac{e}{e - 1} \log y$ , and step 5.1 yields $z \leq \frac{e}{e - 1} y \log y = K η^{- 1} \log (3 e / η) = B$ . Therefore $m = z^{d} \leq B^{d}$ by [F11].

7.1F8step 1.1step 2.2step 4.1step 3.2step 5.1step 6.1∎

If $d = 0$ , step 1.1 proves the result. If $d \geq 1$ , step 2.2 gives $B > 1$ , so one-member separated families satisfy the bound, and steps 4.1, 3.2, 5.1 and 6.1 bound every larger finite $δ$ -separated subfamily by $B^{d}$ . Thus the packing number is finite and its largest integer size is attained; [F8] then gives $N (δ, C, L^{r} (Q)) \leq D (δ, C, L^{r} (Q)) \leq B^{d}$ . Substituting $d = V - 1$ proves the statement.

Depends on

Used by

VC-subgraph covering entropy with its finite-r logarithmic bound Theorem

Dependency tree · two levels

124 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Jon A. Wellner, Empirical Processes: Theory and Applications, Chapter 1, Section 8, Theorem 8.1 inequality (2) (standard reference, not scraped)
David Pollard, Probability Tools, Tricks, and Miracles, 2026 manuscript, Chapter 14 (standard reference, not scraped)