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

Uniform samples have logarithmic fill-distance rate on a cube

Statement

Assume the Axiom of Countable Choice. Let $d \geq 1$ , let $Ω = \prod_{j = 1}^{d} [a_{j}, a_{j} + L]$ be a closed cube with $L > 0$ , and let $U_{1}, U_{2}, \dots$ be independent random vectors, each distributed according to normalized Lebesgue measure on $Ω$ . For $n \geq 1$ , define the Euclidean fill distance

$h_{n} : = \sup_{x \in Ω} \min_{1 \leq i \leq n} ∥ x - U_{i} ∥_{2} .$

There are constants $C_{d} = 2 \sqrt{d} 2^{1 / d}$ and $n_{d}$ such that, for every $n \geq n_{d}$ ,

$P ⁣ {h_{n} \leq C_{d} L {(\frac{\log n}{n})}^{1 / d}} \geq 1 - \frac{1}{n} .$

Statement references

Lebesgue measurable sets, the family $L (R^{n})$ , and the restricted set function $λ_{n}$

The finite union bound

Facts & Assumptions

Given: Countable Choice, the cube $Ω$ , dimension $d$ , and independent uniform sample $U_{1}, U_{2}, \dots$ as in the Statement.

[A1]

Countable Choice means every countable family of nonempty sets has a choice function (The Axiom of Countable Choice ( ${A C}_{ω}$ )).

[F1]

Lebesgue outer measure agrees with volume on half-open boxes (Assuming countable choice, Lebesgue outer measure is an outer measure that restricts to elementary volume, Lebesgue measurable sets, the family $L (R^{n})$ , and the restricted set function $λ_{n}$ ).

[F2]

The probability of a finite union of events is at most the sum of their probabilities (The finite union bound).

[F3]

Independence means mutual independence of the whole family of random elements (Identical distribution and IID families).

[F4]

Under Countable Choice, Lebesgue measure is a complete measure extending volume on half-open boxes, and every coordinate hyperplane is measurable and null (Assuming countable choice, $L (R^{n})$ is a sigma-algebra containing every elementary set and $λ_{n}$ is a complete measure extending elementary volume, A box with a degenerate side is Lebesgue null, and so is every coordinate hyperplane in $R^{n}$ ).

Proof

1.1givenA1F1F4construct

For $n$ large enough that $t_{n} : = (n / (2 \log n))^{1 / d} \geq 2$ , put $m_{n} = ⌊ t_{n} ⌋$ and partition each coordinate interval of $Ω$ into $m_{n}$ equal half-open intervals, closing the last interval at its right endpoint. This gives $m_{n}^{d}$ disjoint cells covering $Ω$ . Each cell differs from a half-open box with the same coordinate bounds only on its boundary faces, which lie in finitely many coordinate hyperplanes. By [F4] those hyperplanes and every subset of their union are measurable and null, so each cell is measurable and has the same measure as that half-open box, namely $(L / m_{n})^{d}$ by [F1]. The same argument for the boundary of $Ω$ gives $λ_{d} (Ω) = L^{d}$ . Hence normalized Lebesgue measure assigns each cell probability $(L / m_{n})^{d} / L^{d} = m_{n}^{- d}$ .

2.1givenF2F3step 1.1algebra

For a fixed cell, independence [F3] gives probability $(1 - m_{n}^{- d})^{n} \leq e^{- n / m_{n}^{d}}$ that it is empty. By [F2], the probability that some cell is empty is at most $m_{n}^{d} e^{- n / m_{n}^{d}} \leq n e^{- 2 \log n} = 1 / n$ , because $m_{n}^{d} \leq n / (2 \log n)$ and hence $n / m_{n}^{d} \geq 2 \log n$ .

3.1givenstep 2.1algebra∎

On the complementary event every cell contains a sample point. Every $x \in Ω$ belongs to one cell, whose Euclidean diameter is $L \sqrt{d} / m_{n}$ ; therefore $h_{n} \leq L \sqrt{d} / m_{n}$ . Since $t_{n} \geq 2$ implies $m_{n} = ⌊ t_{n} ⌋ \geq t_{n} / 2$ , we obtain $h_{n} \leq 2 L \sqrt{d} {(\frac{2 \log n}{n})}^{1 / d} = C_{d} L {(\frac{\log n}{n})}^{1 / d} .$ The event has probability at least $1 - 1 / n$ by step 2.1.

Depends on

Used by

Noiseless Gaussian RKHS interpolation error under uniform sampling Theorem

Dependency tree · two levels

38 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

Belkin, Hsu, Ma and Mandal, Reconciling modern machine learning practice and the bias-variance trade-off (standard reference, not scraped)