TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

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.

Sauer–Shelah growth bound for indexed samples

Statement

Let $(X, Σ)$ be a nonempty measurable space and let $H$ be a nonempty class of measurable functions $h : X \to {0, 1}$ with finite VC dimension $d$ . For every integer $m \geq 0$ ,

$Π_{H} (m) \leq \sum_{j = 0}^{d} (\binom{m}{j}),$

where $(\binom{m}{j}) = 0$ for $j > m$ . Consequently, $Π_{H} (m) = 1$ when $d = 0$ ; and when $1 \leq d \leq m$ ,

$Π_{H} (m) \leq {(\frac{e m}{d})}^{d},$

where $e : = \exp (1)$ .

Statement references

Indexed shattering and VC dimension of a binary class: shattering uses indexed tuples and $VCdim (H)$ is the largest shattered length.

Growth function of a binary hypothesis class: $Π_{H} (m)$ is the largest number of distinct binary traces on an indexed $m$ -tuple.

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

Mohri et al., Theorem 3.17 and Corollary 3.18: Sauer’s trace bound and its $(e m / d)^{d}$ estimate.

Bartlett and Mendelson, Theorems 5–6: empirical VC dimension enters the classification complexity bound.

Facts & Assumptions

Given: A nonempty measurable binary class $H$ , finite $d = VCdim (H)$ , and an integer $m \geq 0$ .

[F1]

A tuple is shattered when its trace is all binary vectors; repeated coordinates are retained as distinct indices. Indexed shattering and VC dimension of a binary class

[F2]

$Π_{H} (m)$ is the supremum of the finite trace cardinalities on indexed $m$ -tuples. Growth function of a binary hypothesis class

[F3]

If $F \subseteq P ([m])$ has finite-set-family VC dimension at most $d$ , then $∣ F ∣ \leq \sum_{j = 0}^{d} (\binom{m}{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]

$(\binom{m}{j})$ counts $j$ -element subsets of $[m]$ and is zero for $j > m$ . The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$

[F5]

In $R$ , $(1 + u)^{m} = \sum_{j = 0}^{m} ι (\binom{m}{j}) u^{j}$ for every real $u$ and natural $m$ . The binomial theorem in $R$ : $(x + y)^{n} = \sum_{k < n + 1} ι ⁣ (\binom{n}{k}) x^{k} y^{n - k}$

[F6]

For every real $u$ , $1 + u \leq e^{u}$ ; $e = \exp (1)$ ; and $e^{a + b} = e^{a} e^{b}$ . $1 + x \leq \exp (x)$ for every real $x$ , hence $(1 - p)^{m} \leq \exp (- m p)$ , The real exponential function and the number $e$ by a power series, The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$

Proof

Given: The hypotheses in the Statement.

1.1F1F2givenconstruct

Fix an indexed tuple $x = (x_{1}, \dots, x_{m})$ . Associate to it the family $F_{x} : = {{i \in [m] : h (x_{i}) = 1} : h \in H} \subseteq P ([m])$ . The map from a trace vector to its set of $1$ -indices is a bijection, so $∣ F_{x} ∣ = ∣ {tr}_{H} (x) ∣$ . If $F_{x}$ shatters $T \subseteq [m]$ , then every binary labeling of the subtuple $(x_{i})_{i \in T}$ occurs in $H$ ; hence $T$ is a shattered indexed tuple for $H$ and $∣ T ∣ \leq d$ . Thus the finite-family VC dimension of $F_{x}$ is at most $d$ .

2.1F2F3step 1.1

Apply [F3] to $F_{x}$ to get $∣ {tr}_{H} (x) ∣ \leq \sum_{j = 0}^{d} (\binom{m}{j})$ . This bound holds for every tuple, so taking the supremum over tuples gives the first inequality.

3.1F2F3step 2.1given

If $d = 0$ , the first inequality gives $Π_{H} (m) \leq 1$ , while nonemptiness of $H$ makes every trace nonempty; hence $Π_{H} (m) = 1$ .

4.1F4F5F6step 2.1algebra∎

Suppose $1 \leq d \leq m$ and identify natural binomial counts with their real images under $ι$ . For $0 \leq j \leq d$ , $(m / d)^{d - j} \geq 1$ , so $\sum_{j = 0}^{d} (\binom{m}{j}) \leq \sum_{j = 0}^{d} (\binom{m}{j}) (m / d)^{d - j} \leq \sum_{j = 0}^{m} (\binom{m}{j}) (m / d)^{d - j} = (m / d)^{d} (1 + d / m)^{m}$ . The second inequality adds nonnegative terms. By [F5], the last factor satisfies $(1 + d / m)^{m} \leq (e^{d / m})^{m} = e^{d}$ , where the first inequality follows by multiplying $1 + d / m \leq e^{d / m}$ by itself $m$ times and the equality follows from [F6]. Therefore $Π_{H} (m) \leq (e m / d)^{d}$ by step 2.1.

Depends on

Used by

Dependency tree · two levels

50 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

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Theorem 3.17 and Corollary 3.18 (standard reference, not scraped)
Peter L. Bartlett and Shahar Mendelson, Rademacher and Gaussian Complexities: Risk Bounds and Structural Results, Theorems 5–6 (standard reference, not scraped)