LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge 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.

Lower cell-mass bounds give a random fill-distance estimate

Statement

Let $d \geq 1$ , $s > 0$ , and let $X \subset R^{d}$ carry a probability measure $μ$ . Fix an integer $m \geq 1$ and $c > 0$ , and put $ε = (c \sqrt{m})^{- 1 / s}$ . Suppose there is a finite measurable partition $X_{1}, \dots, X_{K}$ of $X$ at this particular scale such that each cell lies in a cube of side $ε$ and $μ (X_{j}) \geq c ε^{s}$ . Let $Y_{1}, \dots, Y_{m}$ be independent random points each with law $μ$ . Then with probability at least $1 - \sqrt{m} {(1 - \frac{1}{\sqrt{m}})}^{m}$ every point of $X$ lies within Euclidean distance $\sqrt{d} c^{- 1 / s} m^{- 1 / (2 s)}$ of at least one sample point. For an interior space of dimension $d$ , use $s = d$ ; for a boundary space of Hausdorff dimension $d - 1 > 0$ , use $s = d - 1$ and its own cell-mass constant. If $d = 1$ and every boundary point is available deterministically, the boundary fill distance is zero and no random boundary sample is needed.

Statement references

probability measure

independent random elements

Shin et al., Appendix B, Lemma B.2: probabilistic space-filling estimate

Shin et al., Appendix B, proof of Lemma B.2

Facts & Assumptions

Given: The finite partition at the selected scale, its cell-mass lower bound, and $m$ independent samples with common law $μ$ .

[F1]

A probability measure is finitely subadditive, so the probability of a finite union of missed-cell events is at most the sum of their probabilities (Measures on sigma-algebras, Finite and countable subadditivity of measures).

[F2]

Independent random elements with common law $μ$ have product law on each finite tuple; hence the probability that all $m$ samples miss a cell of measure $p_{j}$ is $(1 - p_{j})^{m}$ (Independent random elements).

[F3]

Countable additivity, applied to the finite disjoint partition followed by empty sets, makes the cell measures sum to the measure of the whole space (Measures on sigma-algebras).

Proof

Proof strategy: coupon-collector union bound.

1.1givenF3algebra

The cell measures sum to one by [F3], and each is at least $c ε^{s} = 1 / \sqrt{m}$ . Therefore the number of cells is at most $\sqrt{m}$ .

1.2givenF1F2algebra

A fixed cell of mass $p_{j} \geq c ε^{s} = 1 / \sqrt{m}$ is missed by all $m$ independent samples with probability $(1 - p_{j})^{m} \leq (1 - 1 / \sqrt{m})^{m}$ by [F2]. By [F1], the probability that at least one cell is missed is at most $\sqrt{m} (1 - 1 / \sqrt{m})^{m}$ .

2.1step 1.1step 1.2algebra∎

On the complementary event, every cell contains a sample. Since each cell lies in a cube of side $ε$ , any point of the cell is within the cube's Euclidean diameter $\sqrt{d} ε$ of a sample in that same cell. Substituting $ε = (c \sqrt{m})^{- 1 / s}$ gives the stated fill radius and probability.

Remarks

It suffices to assume the partitions exist for $0 < ε \leq ε_{0}$ and then restrict to $m \geq \max {1, c^{- 2} ε_{0}^{- 2 s}}$ . Indeed, this is exactly the condition $(c \sqrt{m})^{- 1 / s} \leq ε_{0}$ . For upper ball-mass bounds used at the fill radius, also require $\sqrt{D} (c \sqrt{m})^{- 1 / s} \leq ρ_{0}$ if their range is $0 < ρ \leq ρ_{0}$ . The normalized Appendix B mass is $c ε^{s} = 1 / \sqrt{m}$ , so its failure probability is $\sqrt{m} (1 - 1 / \sqrt{m})^{m}$ , independently of $c$ . If one deliberately chooses $0 < c \leq 1$ , this is no larger than $\sqrt{m} (1 - c / \sqrt{m})^{m}$ , recovering the weaker later printed probability with those same chosen constants. Replacing a lower-mass constant by a smaller one is valid, but all radii, $C_{m}$ , and regularization thresholds must then use the new constant. No such replacement is made implicitly.

Depends on

Used by

Regularized PINN minimizers have vanishing residuals under sample refinement Theorem

Dependency tree · two levels

13 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

Shin, Darbon, and Karniadakis, On the Convergence of Physics-Informed Neural Networks for Linear Second-Order Elliptic and Parabolic Type PDEs (standard reference, not scraped)